《ch1数学模型及单纯形法ppt课件》由会员分享，可在线阅读，更多相关《ch1数学模型及单纯形法ppt课件（85页珍藏版）》请在金锄头文库上搜索。
1、Chapter1 线性规划及单纯形法 1.1 线性规划问题及数学模型 1.2 图解法 1.3 单纯形法 1.4 单纯形法的进一步讨论本章主要内容：本章主要内容：本章主要内容：本章主要内容：page11.1 线性规划问题及数学模型1.1.1 问题的提出规划问题Program 生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是规划问题。线性linear 量与量之间按比例、成直线的关系，在数学上可以理解为一阶导数为常数的函数。page21.1 线性规划问题及数学模型v线性规划 Linear Programming v 求线性目标函数在线性约束条件下的最大
2、值或最小值的问题，统称为线性规划问题。通常解决下列两类问题：v（1在一定的资源条件限制下，如何组织安排生产获得最好的经济效益如产品量最多 、利润最大。）v（2当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源 （如资金、设备、资料、人工、时间等去完成确定的任务或目标。page31.1 线性规划问题及数学模型例1 美佳公司计划制造、两种家电产品。已知各制造1件时分别占用的设备A，B的台时、调试工序时间及每天可用于这两种家电的能力、各售出1件时的获利情况，如下表所示。问该公司应制造两种家电各多少件，使获取的利润为最大。page41.1 线性规划问题及数学模型例2 捷运公司在下一年度的14月的
3、4个月内拟租用仓库堆放物资。已知各月份所需仓库面积列于表1-2。仓库租借费用随合同期而定，期限越长，折扣越大，具体数字见表1-3。租借仓库的合同每月初都可办理，每份合同具体规定租用面积和期限。因此该厂可根据需要，在任何一个月初办理租借合同。每次办理时可签一份合同，也可签若干份租用面积和租借期限不同的合同，试确定该公司签订租借合同的最优决策，目的是使所付租借费用最小。表1-2单位：100m2表1-3单位：元/100m2page51.1 线性规划问题及数学模型1.1.2 线性规划问题的数学模型1线性规划问题的数学定义： 求取一组变量xj (j=1,2,.,n)，使之既满足线性约束条件，又使具有线性
4、的目标函数取得极值的一类最优化问题称为线性规划问题。怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？ （1问题的目标函数是多个决策变量的线性函数，通常是求最大值或最问题的目标函数是多个决策变量的线性函数，通常是求最大值或最小值；小值；（2问题的约束条件是一组多个决策变量的线性不等式或等式。问题的约束条件是一组多个决策变量的线性不等式或等式。page61.1 线性规划问题及数学模型1.1.2 线性规划问题的数学模型2） 线性规划的数学模型由三个要素构成 例1 例2决策变量决策变量决策变量决策变量 Decision variables Decision variables 目标函数
5、目标函数目标函数目标函数 Objective function Objective function约束条件约束条件约束条件约束条件 Constraints Constraintspage7例1page8(1.1c)目标函数约束条件(1.1a)(1.1b)(1.1d)max: maximize的缩写， “最大化”，s.t. subject to的缩写， “受限制于”例1page9目标函数约束条件 s.t.min：minimize ， “最小化”1.1.2 线性规划问题的数学模型目标函数：目标函数：目标函数：目标函数：约束条件：约束条件：约束条件：约束条件：3 3线性规划数学模型的一般形式线性规
6、划数学模型的一般形式线性规划数学模型的一般形式线性规划数学模型的一般形式简写为：简写为：page101.1.2 线性规划问题的数学模型向量形式：向量形式：向量形式：向量形式：其中：其中：page111.1.2 线性规划问题的数学模型矩阵形式：矩阵形式：矩阵形式：矩阵形式：其中：其中：page121.1 线性规划问题及数学模型v课堂练习v 某企业有三个工厂甲、乙、丙生产某种产品销往四个销售点A、B、C、D。每个计划期内甲乙丙的供应量分别为150、200和250件，销售点A、B、C、D的需求量分别是120、140、160和180件。各工厂运送至各销售点 的运价如表所示，试制定总运价最小的调运方案建
7、立该问题的线性规划模型）。 销售点运价（元/件）工厂 A B C D 甲 4 6 8 10 乙 6 410 4 丙8 2 4 6page131.1 线性规划问题及数学模型v1.1.3 1.1.3 1.1.3 1.1.3 线性规划问题的标准形式线性规划问题的标准形式线性规划问题的标准形式线性规划问题的标准形式特点：特点：(1) 目标函数求最大值有时求最小值）目标函数求最大值有时求最小值）(2) 约束条件都为等式方程，且右端常数项约束条件都为等式方程，且右端常数项bi都大于或等于零都大于或等于零(3) 决策变量决策变量xj为非负。为非负。page141.1.3 线性规划问题的标准形式如何化标准形式
8、？如何化标准形式？如何化标准形式？如何化标准形式？ 目标函数的转换目标函数的转换 如果是求极小值即如果是求极小值即 ，则可将目标函数乘以，则可将目标函数乘以(-1)(-1)，可化为求极大值问题。，可化为求极大值问题。也就是：令也就是：令 ，可得到上式。，可得到上式。即即 若存在取值无约束的变量若存在取值无约束的变量 ，可令，可令 其中：其中： 变量的变换变量的变换page151.1.3 线性规划问题的标准形式 约束方程的转换：由不等式转换为等式。约束方程的转换：由不等式转换为等式。称为松弛变量称为松弛变量称为剩余变量称为剩余变量 变量变量 的变换的变换 可令可令 ，显然，显然page16例3
9、将下述线性规划化为标准形式 page171.1.3 线性规划问题的标准形式课堂练习课堂练习 将下列线性规划问题化为标准形式将下列线性规划问题化为标准形式用用 交换交换 ，且，且 解解:（因为（因为x3无符号要求无符号要求 ，即，即x3取正值也可取负值，标准取正值也可取负值，标准型中要求变量非负，所以型中要求变量非负，所以page181.1.3 线性规划问题的标准形式(2) 第一个约束条件是第一个约束条件是“”号，在号，在“”左端加入松驰变量左端加入松驰变量x4，x40,化为等式；化为等式；(3) 第二个约束条件是第二个约束条件是“”号，在号，在“”左端减去剩余变量左端减去剩余变量x5，x50；
10、(4) 第第3个约束方程右端常数项为个约束方程右端常数项为-5，方程两边同乘以，方程两边同乘以(-1),将右将右端常数项化为正数；端常数项化为正数； (5) 目标函数是最小值，为了化为求最大值，令目标函数是最小值，为了化为求最大值，令z=-z,得到得到max z=-z，即当，即当z达到最小值时达到最小值时z达到最大值，反之亦然达到最大值，反之亦然;page191.1.3 线性规划问题的标准形式标准形式如下：标准形式如下：page20作业v某药厂生产某药厂生产A、B、C三种药品，有甲乙丙丁四种原料可供选择原材三种药品，有甲乙丙丁四种原料可供选择原材料供应不限），四种原料成本分别为每公斤料供应不限
11、），四种原料成本分别为每公斤4、7、9、5元。每公斤不元。每公斤不同原料提取的各种药品数量同原料提取的各种药品数量g如下表所示：如下表所示：v该厂要求每天生产药品该厂要求每天生产药品A恰好恰好115g，B至少至少260g，C不超过不超过130g。使确。使确定各种原料的每天需要量，使每天的总成本最小。试建立该问题的数定各种原料的每天需要量，使每天的总成本最小。试建立该问题的数学模型，并将模型化成标准型。学模型，并将模型化成标准型。 原料每公斤提取药量（g）药品甲乙丙丁A2132B6625C3223page211.2 图解法v线性规划问题的求解方法一一 般般 有有两种方法两种方法图图 解解 法法单
12、纯形法单纯形法两个变量、直角坐标两个变量、直角坐标三个变量、立体坐标三个变量、立体坐标适用于任意变量、但必需将适用于任意变量、但必需将一般形式变成标准形式一般形式变成标准形式 可行解：满足所有约束条件的解。可行解：满足所有约束条件的解。 可行域：所有可行解的集合。可行域：所有可行解的集合。 最优解：使目标函数达到最大值的可行解。最优解：使目标函数达到最大值的可行解。page221.2 图解法v只有两个决策变量的线性规划问题，这时可以通过图解的只有两个决策变量的线性规划问题，这时可以通过图解的方法来求解。方法来求解。v图解法具有简单、直观、便于初学者窥探线性规划基本原图解法具有简单、直观、便于初
13、学者窥探线性规划基本原理和几何意义等优点。其目的表现为：理和几何意义等优点。其目的表现为：v 判别线性规划问题的求解结局；判别线性规划问题的求解结局；v 若存在最优解，将其找出。若存在最优解，将其找出。page231.2 图解法图解法的步骤：1建立平面直角坐标系，标出坐标原点, 坐标轴的指向和单位长度。2对约束条件加以图解，找出可行域。 3画出目标函数等值线。4结合目标函数的要求求出最优解。page241.2 图解法(1.5c)(1.5a)(1.5b)(1.5d)例例1 用图解法求解线性规划问题用图解法求解线性规划问题page251.2 图解法page261.2 图解法max Z = 2X1
14、+ X2 X1 + 1.9X2 3.8 X1 - 1.9X2 3.8s.t. X1 + 1.9X2 10.2 X1 - 1.9X2 -3.8 X1 ，X2 0例例 用图解法求解线性规划问题用图解法求解线性规划问题page271.2 图解法x1x2oX1 - 1.9X2 = 3.8()X1 + 1.9X2 = 3.8()X1 - 1.9X2 = -3.8 ()X1 + 1.9X2 = 10.2()4 = 2X1 + X2 20 = 2X1 + X2 17.2 = 2X1 + X2 11 = 2X1 + X2 Lo： 0 = 2X1 + X2 （7.6，2）Dmax Zmin Z此点是唯一最优解，
15、此点是唯一最优解，且最优目标函数值且最优目标函数值 max Z=17.2可行域可行域max Z = 2X1 + X2page281.2 图解法max Z=3X1+5.7X2x1x2oX1 - 1.9X2 = 3.8 ()X1 + 1.9X2 = 3.8()X1 - 1.9X2 = -3.8()X1 + 1.9X2 = 10.2 ()（7.6，2）DL0： 0=3X1+5.7X2 max Z（3.8，4）34.2 = 3X1+5.7X2 蓝色线段上的所有点都是最蓝色线段上的所有点都是最优解这种情形为有无穷多最优解这种情形为有无穷多最优解，但是最优目标函数值优解，但是最优目标函数值max Z=34
16、.2是唯一的。是唯一的。可行域可行域page291.2 图解法vmin Z=5X1+4X2x1x2oX1 - 1.9X2 = 3.8 ()X1 + 1.9X2 = 3.8()X1 + 1.9X2 = 10.2 ()DL0： 0=5X1+4X2 max Z min Z 8=5X1+4X2 43=5X1+4X2 （0，2）可行域可行域此点是唯一最优解此点是唯一最优解page301.2 图解法246x1x2246无界解无界解( (无最优解无最优解) )maxZ=x1+2x2例例1.6x1+x2=4()x1+3x2=6()3x1+x2=6() max Z min Zpage31x1x2O1020304
17、0102030405050无可行解无可行解(即无最优解即无最优解)max Z=3x1+4x2例例1.7page321.2 图解法 (a)可行域有界可行域有界 (b)可行域有界可行域有界 (c)可行域无界可行域无界 唯一最优解唯一最优解多个最优解多个最优解 唯一最优解唯一最优解 (d)可行域无界可行域无界 (e)可行域无界可行域无界 (f)可行域为空集可行域为空集 多个最优解多个最优解 目标函数无界目标函数无界 无可行解无可行解page331.2 图解法学习要点：学习要点：1. 通过图解法了解线性规划有几种解的形式通过图解法了解线性规划有几种解的形式（唯一最优解；无穷多最优解；无界解；无可行解）
18、（唯一最优解；无穷多最优解；无界解；无可行解）2. 若线性规划问题的可行域存在，则可行域是一个若线性规划问题的可行域存在，则可行域是一个凸集；凸集； 3. 若线性规划问题的最优解存在，则最优解一定是若线性规划问题的最优解存在，则最优解一定是可行域凸集的某个顶点；可行域凸集的某个顶点； 4.解题思路：先找凸集的任意顶点，计算在顶点处的解题思路：先找凸集的任意顶点，计算在顶点处的目标函数值。目标函数值。page341.3 单纯形法v1.3.1 1.3.1 1.3.1 1.3.1 线性规划问题的解线性规划问题的解线性规划问题的解线性规划问题的解线性规划问题线性规划问题求解线性规划问题，就是从满足约束
19、条件求解线性规划问题，就是从满足约束条件(2)、(3)的方程的方程组中找出一个解，使目标函数组中找出一个解，使目标函数(1)达到最大值。达到最大值。page351.3.1 线性规划问题的解 可行解：满足约束条件可行解：满足约束条件、的解为可行解。所有可行解的解为可行解。所有可行解的集合为可行域。的集合为可行域。 最优解：使目标函数达到最大值的可行解。最优解：使目标函数达到最大值的可行解。 基：设基：设A A为约束条件为约束条件的的mnmn阶系数矩阵阶系数矩阵(mn)(m04010换换出出行行将将3化为化为15/311801/301/31011/3303005/304/3乘乘以以1/3后后得得到
20、到103/51/518011/52/540011page49 CB 基 cj21000 b x1x2x3x4x50x315051000x424620100x5511001cj-zj21000解：表1-7page5001/602/614x120-1/301/30cj-zj1-1/604/601x500015015x30x5x4x3x2x1b 00012 cj 基 CB表1-8-1/21/40017/2x12-1/2-1/4000cj-zj3/2-1/40103/2x21-15/25/410015/2x30x5x4x3x2x1 b 00012 cj 基CB表1-9page51表1-9中所有j=0,
21、且基变量中不含人工变量，最优解 X=(7/2, 3/2, 15/2, 0, 0) ; 最优值 Z=17/2.page52算法思路求一个初始基本可行解是判断基本可行解是否最优结束不是求使目标得到改善的基本可行解是否存在？如何得到？是否唯一？如何判断？如何改善？如何判断没有有限最优解？page53处理方法一处理方法一 大法大法人造基添加人工变量造成基去掉人工变量人工变量5 单纯形法进一步讨论page545 单纯形法进一步讨论原问题的可行解新问题的可行解目标值结论：新问题的最优解中，如果人工变量均为零，则得到的解也是原问题的最优解，否则原问题无可行解page55例6大M法-M0-10x500010x
22、6-M00-11-21x6-M0014M -2M-3cj-zj101309x7-M011114x40x7x4x3x2x1 b -M010-3 cjXB CB表1-10page560x400011-1/2-1/2-1/20x23011/30001/3-3x11102/301/2-1/21/6cj-zj00303/2-M-3/2-M+1/2CBXB cj-30100-M-M b x1x2x3x4x5x6x70x4331110000x21-21-10-110-Mx766310001cj-zj6M-30 4M+103M-4M00x400001-1/21/2-1/20x25/2-1/2100-1/41/
23、41/4-3x33/23/20103/401/4cj-zj-9/2000-3/4-M+3/4-M-1/4最优解:X=(0,5/2,3/2,0,0,0,0)最优值：Z=3/2page57处理方法二处理方法二 两阶段法两阶段法人造基添加人工变量造成基去掉人工变量人工变量page58两阶段法 如果线性规划问题中的aij、bi或cj等参数值与这个代表M的数相对比较接近，或远远小于这个数字，由于计算机计算时取值上的误差，有可能使计算结果发生错误。为了克服这个困难，可以对添加人工变量后的线性规划问题分两个阶段来计算，称两阶段法。page595单纯形法进一步讨论第一阶段第一阶段第一阶段最优解中:如果Z0且且
24、aiki=1，2,m则线性则线性规划具有无界解。规划具有无界解。4无可行解的判断：当用大无可行解的判断：当用大M单纯形法计算得到最优解并单纯形法计算得到最优解并且存在且存在Ri0时，则表明原线性规划无可行解。时，则表明原线性规划无可行解。5退化解的判别：存在某个基变量为零的基本可行解。退化解的判别：存在某个基变量为零的基本可行解。page67无可行解010x5-M-1-40-54x5-M-M-2-4M0-1-5Mcj-zj01122x22x4x3x2x1 b 0023 cj XB CBpage68有可行解，但无最优解101-34x23-30011cj-zj110-26x30x4x3x2x1 b
25、 0032 cj XB CBpage69退化解-3/43/4-1/4-1/2x50001-1/25/2x20000-9/2cj-zj0103/23/2x3110000x40x4x3x2x1 b 0000 cj XB CBpage70无穷多个最优解7/45-2/45017/3x140-200cj-zj-2/457/45107/3x214x4x3x2x1 b 00144 cj XB CBpage71单纯形法的进一步讨论人工变量法v单纯性法小结:建立模型个 数取 值右 端 项等式或不等式极大或极小新加变量系数两个三个以上xj0xj无约束xj 0 bi 0bi 0=maxZminZxs xa求解图解法
26、、单纯形法单纯形法不处理令xj = xj - xj xj 0xj 0令 xj =- xj不处理约束条件两端同乘以-1加松弛变量xs加入人工变量xa减去xs加入xa不处理令z=- ZminZ=max z0-Mpage72A Apage73 线性规划模型的应用v一般而言，一个经济、管理问题凡是满足以下条件时，才能建立线性规划模型。 要求解问题的目标函数能用数值指标来反映，且要求解问题的目标函数能用数值指标来反映，且为线性函数为线性函数 存在着多种方案存在着多种方案 要求达到的目标是在一定条件下实现的，这些约要求达到的目标是在一定条件下实现的，这些约束可用线性等式或不等式描述束可用线性等式或不等式描
27、述page74 线性规划在管理中的应用1. 人力资源分配问题例例1.11 某昼夜服务的公交线路每天各时间段内某昼夜服务的公交线路每天各时间段内所需司机和乘务人员人数如下表所示：所需司机和乘务人员人数如下表所示：班次时间所需人员16:0010:0060210:0014:0070314:0018:0060418:0022:0050522:002:002062:006:0030设司机和乘务人员分别在各时间段开始时上班，并连续工作设司机和乘务人员分别在各时间段开始时上班，并连续工作8小时，问该公交线路应怎样安排司机和乘务人员，即能满小时，问该公交线路应怎样安排司机和乘务人员，即能满足工作需要，又使配备
28、司机和乘务人员的人数减少足工作需要，又使配备司机和乘务人员的人数减少?page75 线性规划在管理中的应用v解：设xi表示第i班次时开始上班的司机和乘务人员人数。此问题最优解：此问题最优解：x150， x220， x350， x40， x520， x610，一共需要司机和乘务员，一共需要司机和乘务员150人。人。page76 线性规划在管理中的应用v2. 生产计划问题某厂生产某厂生产、三种产品，都分别经三种产品，都分别经A、B两两道工序加工。设道工序加工。设A工序可分别在设备工序可分别在设备A1和和A2上完成，上完成，有有B1、B2、B3三种设备可用于完成三种设备可用于完成B工序。已知产工序。
29、已知产品品可在可在A、B任何一种设备上加工；产品任何一种设备上加工；产品可在任何可在任何规格的规格的A设备上加工，但完成设备上加工，但完成B工序时，只能在工序时，只能在B1设设备上加工；产品备上加工；产品只能在只能在A2与与B2设备上加工。加工设备上加工。加工单位产品所需工序时间及其他各项数据如下表，试单位产品所需工序时间及其他各项数据如下表，试安排最优生产计划，使该厂获利最大。安排最优生产计划，使该厂获利最大。page77 线性规划在管理中的应用设备产品设备有效台时设备加工费（单位小时）A15106000300A27910 000321B168124000250B247000783B3711
30、4000200原料费（每件）0.250.350.5售价（每件）1.252.002.8page78 线性规划在管理中的应用v解：设xijk表示产品i在工序j的设备k上加工的数量。约束条件有：page79 线性规划在管理中的应用v目标是利润最大化，即利润的计算公式如下：带入数据整理得到：带入数据整理得到：page80 线性规划在管理中的应用v因此该规划问题的模型为：page81 线性规划在管理中的应用v3. 套裁下料问题例：现有一批某种型号的圆钢长例：现有一批某种型号的圆钢长8米，需要截取米，需要截取2.5米米长的毛坯长的毛坯100根，长根，长1.3米的毛坯米的毛坯200根。问如何才能根。问如何才
31、能既满足需要，又能使总的用料最少？既满足需要，又能使总的用料最少？解：为了找到一个省料的套裁方案，必须先设计出较好的几解：为了找到一个省料的套裁方案，必须先设计出较好的几个下料方案。其次要求这些方案的总体能裁下所有各种规格个下料方案。其次要求这些方案的总体能裁下所有各种规格的圆钢，以满足对各种不同规格圆钢的需要并达到省料的目的圆钢，以满足对各种不同规格圆钢的需要并达到省料的目的，为此可以设计出的，为此可以设计出4种下料方案以供套裁用。种下料方案以供套裁用。2.5m32101.3m0246料头00.40.30.2page82 线性规划在管理中的应用设按方案设按方案、下料的原材料根数分别为下料的原材料根数分别为xj (j=1，2,3,4)，可列出下面的数学模型：，可列出下面的数学模型：page83 线性规划在管理中的应用v4. 配料问题例：某人每天食用甲、乙两种食物如猪肉、鸡蛋），例：某人每天食用甲、乙两种食物如猪肉、鸡蛋），其资料如下：问两种食物各食用多少，才能既满足需其资料如下：问两种食物各食用多少，才能既满足需要、又使总费用最省？要、又使总费用最省？2 1.5原料单价1.007.5010.00 0.1 0.15 1.7 0.75 1.10 1.30A1A2A3 最 低需要量甲 乙含量 食物成分page84 线性规划在管理中的应用v解：设Xj 表示Bj 种食物用量page85
