运筹学中线性规划图解法动态.ppt

《运筹学中线性规划图解法动态.ppt》由会员分享，可在线阅读，更多相关《运筹学中线性规划图解法动态.ppt（58页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 第二章第二章线性规划的图解法线性规划的图解法 第二章第二章线性规划的图解法线性规划的图解法第1节 问题的提出1、线性规划的概念 由用线性变量所构建的线性目标函数和线性约束组成的数学模型，我们称之为线性规划。即所有变量都是一次的，目标函数和约束条件（方程或不等式）也是线性的。2、具体应用例子。例2.1 某工厂计划用现有的铜、铅两种资源生产甲、乙电缆，生产甲、乙两种电缆的单位售价及资源消耗如下表所示：甲电缆乙电缆资源量铜（吨）2110铅（吨）118价格（万元）64另外，市场对乙电缆的最大需求量为7单位，而对甲乙电缆的需求量无限制。问该工厂应如何安排生产才能使工厂的总收入最大？一、线性数学模型的建

2、立：s.t.Object：解：设x1，x2分别代表甲乙两种电缆的生产量，z代表工厂的总收入，则上述问题可用如下数学模型来表示：铜资源约束铜资源约束铅资源约束铅资源约束市场约束市场约束产量非负产量非负目标函数目标函数LP的基本概念的基本概念目标函数中的变量系数用目标函数中的变量系数用Cj表示表示,Cj称为价称为价值系数值系数;约束条件的变量系数用约束条件的变量系数用aij表示表示,aij称为工艺系数称为工艺系数;约束条件右端的常数用约束条件右端的常数用bi表表示示,bj称为资源限量称为资源限量(系数系数)约束条件(subject to)目标Object：指出模型中的可行解基本概念基本概念:1、什

3、么是可行解、什么是可行解?2、什么是最优解、什么是最优解?二、线性规划模型的求解二、线性规划模型的求解(方法方法)：1、图解法；、图解法；2、单纯形法（时代标志）；、单纯形法（时代标志）；3、计算机软件求解。、计算机软件求解。第2节 图解法条件：只有两个变量的线性规划问题理解:X1,x2代表两个数轴：目标函数：是一条直线（视Z为常量）约束条件：是等式或不等式，代表直线或直线的上方或下方；x1x207x27条件约束图示条件约束图示:x20 x2=7x10 x1x251002x2x1 1+x+x2 2=10=10788x27图示图示:s.t.x x1 1+x+x2 2=8=8可行域x1x25100

4、2x2x1 1+x+x2 21010 x x1 1+x+x2 288788x27max z=6x1+4x20=6x1+4x2可行域最优解(X(X1 1=2=2，x x2 2=6)z=36=6)z=36s.t.线性规划的图解法2x1x2目标函数等值线可行域最优解66-84max z=x1+3x2x1+x26-x1+2x28x1 0,x20s.t.目目标标函数：函数：maxmaxz=50 xz=50 x1 1+100 x+100 x2 2x x1 1+x+x2 23003002x2x1 1+x+x2 2400400 x x1 1 0,x0,x2 200s.t.s.t.图解法例3：x x2 2250

5、250 x1x22004000 x x2 2=250=250250300最优解300（z=27500=50 x1+100 x2)X1=50,x2=25050练习题：教材P24 第1题Global optimal solution found.Objective value:9.857143 Total solver iterations:2 Variable Value Reduced Cost X1 1.714286 0.000000 X2 2.142857 0.000000 Row Slack or Surplus Dual Price 1 9.857143 1.000000 2 0.00

6、0000 1.285714 3 0.000000 0.1428571LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1)9.857142 VARIABLE VALUE REDUCED COST X1 1.714286 0.000000 X2 2.142857 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 1.285714 3)0.000000 0.142857 NO.ITERATIONS=2 RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ C

7、OEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 2.000000 3.000000 0.500000 X2 3.000000 1.000000 1.800000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 6.000000 4.000000 3.000000 3 15.000000 14.999999 6.000000约束条件资源量使用量剩余数量铜（吨）10100铅（吨）

8、880市场量761 在线性规划中，对于一个约束条件中没有使用的资源或能力的大小称之为松驰量。在不等式中添加一个变量Si ，则原约束条件变为：求解结果：X1=2，X2=6，s.t.目标函数：s.t.目标函数：于是，重新得到一个数学模型：上述过程，称为线性规划的标准化过程，其模型被称为线性规划的标准模型。线性规划的标准型规定为：目标函数：目标函数：约约束束条条件件线性规划标准型1.目标函数求最大值(也有的教材规定为求最小)2.约束条件均为等式方程;3.变量Xi为非负;4.常数bj都大于或等于零.max z=x1+3x2x1+x26-x1+2x28 x1 0,x20s.t.max z=x1+3x2+

9、0s1 1+0s+0s2 2x1+x2+s1=6-x1+2x2+s2=8x1 0,x20s.t.原模型：标准化模型：s1 0,s20线性规划的标准化过程中还有没有其它问题要处理？s.t.1、若碰到0的约束条件该如何标准化？2、Min问题。在第i个约束条件为型，在不等式的左边减去一个非负的变量Si,称为剩余变量；同时令相应的Ci,=0。结果如下：s.t.对于对于Min问题，问题，只需要将系数由正号（+）变为负（-）即要。转化过程对约束条件进行处理：1、对=的减去一个非负变量sJ 使之左右相等；减去的变量称为剩余量(surplus variable)加上的变量称为松弛量(slack variabl

10、e)3、对目标函数:加系数0处理Si量s.t.目标函数：s.t.之前之后s.t.之后s.t.练习：线性规划模型的标准化P25 第3题，可行域的性质 线性规划的最优解在极点上 线性规划的可行域是凸集 极点凸集不是凸集凸集二个重要二个重要结论结论：满足约束条件的可行域一般都构成凸多边形。这一事实可以推广到更多变量的场合。最最优优解必定能在凸多解必定能在凸多边边形的某一个形的某一个顶顶点上取得，点上取得，这这一事一事实实也可以推广到更也可以推广到更多多变变量的量的场场合。合。解的解的讨论讨论：最优解是唯一解；无无穷穷多多组组最最优优解：解：例：例：max z=40 x1+30 x2 s.t.4x1+

11、3x2 120 2x1+x2 50 x1,x2 0 x2 50403020101020 3040 x1 可行域可行域可行域可行域 目目标标函数是同函数是同约约束束条件：条件：4x1 1+3x2 2 120平行的直平行的直线线 x2 50403020101020 3040 x1 可行域可行域可行域可行域 当当z z的值增加时，目标函数与约束条件：的值增加时，目标函数与约束条件：4x4x1 1 1 1+3x+3x2 2 2 2 120 120 重合，重合，Q Q1 1 1 1与与Q Q2 2 2 2之间都是最优解。之间都是最优解。Q1（25，0）Q2（15，20）解的解的讨论讨论：无界解：无界解：

12、例：例：max z=x1+x2 s.t.-2x1+x2 40 x1-x2 20 x1,x2 0 x2 50403020101020 3040 x1 该该可行域无界，目可行域无界，目标标函数函数值值可可增加到无增加到无穷穷大，称大，称这这种情况种情况为为无界解或无最无界解或无最优优解。解。解的解的讨论讨论：无可行解：无可行解：例：例：max S=2x1+3x2 s.t.x1+2x2 8 x1 4 x2 3 -2x1+x2 4 x1,x2 0 该问题可行域为该问题可行域为空集，即无可行空集，即无可行解，也不存在最解，也不存在最优解。优解。解的情况：解的情况：有可行解有可行解 有唯一最优解有唯一最优

13、解 有无穷最优解有无穷最优解 无最优解无最优解 无可行解无可行解 (d)可行域无界可行域无界 (e)可行域无界可行域无界 (f)可行域为空集可行域为空集 多个最优解多个最优解 目标函数无界目标函数无界 无可行解无可行解 (a)可行域有界可行域有界 (b)可行域有界可行域有界 (c)可行域无界可行域无界 唯一最优解唯一最优解 多个最优解多个最优解 唯一最优解唯一最优解第3节 图解法的灵敏度分析一、线性规划的标准化目标函数：目标函数：约约束束条条件件线性规划的标准型规定为：目标函数：目标函数：约约束束条条件件二、灵敏度分析1、什么是灵敏度分析？先看例子:2、如何进行灵敏度分析？例2.1 某工厂计划

14、用现有的铜、铅两种资源生产甲、乙电缆，生产甲、乙两种电缆的单位售价及资源消耗如下表所示：甲电缆甲电缆乙电缆乙电缆资源量资源量铜（吨）铜（吨）2110铅（吨）铅（吨）118价格（价格（万元万元）64另外，市场对乙电缆的最大需求量为7单位，而对甲乙电缆的需求量无限制。问该工厂应如何安排生产才能使工厂的总收入最大？求解结果:X1=2,X2=6,Z=36:X1=2,X2=6,Z=36万元万元 生产甲生产甲,乙电缆乙电缆2 2个单位个单位,6,6个单位个单位,获最大收入获最大收入3636万元万元.问题问题:甲的价格由甲的价格由6 6万元降为万元降为5 5万元万元,生产方案还是最优吗生产方案还是最优吗?怎

15、么解决?(1)重新计算;(2)另想简单办法?二、灵敏度分析1、什么是灵敏度分析？在实际工作中，我们往往已经求得了最优解，可是有时，模型中的某个系数或若干个系会发生变化，如原材料的购买单价由原来的50元上涨到为60元，那么，生产安排的最优方案是否还是最优？值得重新考虑？线性规划模型中系数的变化，引起最优解的变化，属于灵敏度分析的研究范围。定义：在建立数学模型和求得最优解之后，研究线性规划的一引起系数 变化时，对最优解产生什么影响？（最优解是否会改变？）2、如何进行灵敏度分析？2、如何进行灵敏度分析？（1）目标函数中的系数 的灵敏度分析 当 改变时，Z会如何改变？先看例子：二、灵敏度分析AB资源限

16、制设备11300台时原料A21400千克原料B01250千克获利（元）50100问该工厂应如何安排生产才能使工厂的总收入最大？目目标标函数：函数：maxmaxz=50 xz=50 x1 1+100 x+100 x2 2x x1 1+x+x2 23003002x2x1 1+x+x2 2400400 x x1 1 0,x0,x2 200s.t.s.t.图解法例3：x x2 2250250 x1x22004000 x x2 2=250=250200300最优解(50,250)300当X1=50,x2=250时,MAX Z=50 x1+100 x2=27500当产品A或B的价格系数发生变化时，增加或减

17、少时，是大利润将发生变化，也就将改变最优解。我们现在就要求出系数的最大变化范围。Ci改变时，Z不变。目目标标函数：函数：maxmaxz=50 xz=50 x1 1+100 x+100 x2 2图解法例3：x1x22004000 x x2 2=250=250200300300 x x1 1+x+x2 23003002x2x1 1+x+x2 2400400 x x1 1 0,x0,x2 200s.t.s.t.x x2 2250250目目标标函数：函数：maxmaxz=C1 xz=C1 x1 1+C2 x+C2 x2 2直线F：直线E从图中可知，直线F的斜率K=0直线E的斜率K=-1而目标函数:z=

18、C1x1+c2x2的斜率k=-C1/C2那么，当-1-c1/c2 0时顶点B仍然是最优解目目标标函数：函数：maxmaxz=50 xz=50 x1 1+100 x+100 x2 2x x1 1+x+x2 23003002x2x1 1+x+x2 2400400 x x1 1 0,x0,x2 200s.t.s.t.图解法例3：x x2 2250250 x1x22004000 x x2 2=250=250200300最优解300（z=27500=50 x1+100 x2)X1=50,x2=250目目标标函数：函数：maxmaxz=50 xz=50 x1 1+100 x+100 x2 2图解法例3：x

19、1x22004000 x x2 2=250=250200300300目标函数斜率:K=-c1/c2条件条件:目目标标函数：函数：maxmaxz=50 xz=50 x1 1+100 x+100 x2 2图解法例3：条件条件:x1x2先来固定C2=100,让C1变化,讨论C1的变化范围,使得Z不变.只要C2=100,C1在0和100之间变化,那么工厂生产获取最大利润的方案将不变.即仍然是X1=50,X2=250,即生产量不变，但获取的利润可能会变（因为产品的单价变了）。假设C2=100不变，C1=70上涨20元，则当生产方案不变时，工厂获利变为：50X70+100X250=3500+25000=2

20、8500，比原来多1000当C1和C2同时变化时，则可通过不等式：来判断原最优解是否仍然最优。如：C1=60，C2=55，-C1/C2=-60/55=-1.09要重新求解.三、约束条件中右边系数bj的灵敏度分析讨论bj的变化范围，使得Z最优解不变。由于bj的变化，使得可行域发生变化，变大或缩小；x x1 1+x+x2 2300300 x x1 1+x+x2 2310310生产设备台时增加10小时x1x2x x1 1+x+x2 2300300 x x1 1+x+x2 2310310ABCDOBCB点（点（60，250）最大利润为：最大利润为：Z=50X60+100X250=28000 x x1

21、1+x+x2 2300300由于新增10台时，增加了500元利润，故在300台时的基础上，每增加1台时可增加500/10=50元的利润，这个增加量被称为该约束条件的对偶价格（简称为对偶价格）。现修改另一个右边系数B2：2x2x1 1+x+x2 24004002x2x1 1+x+x2 2410410 x1x22x2x1 1+x+x2 2400400 x x1 1+x+x2 2410410ABCDOCDB点（点（50，250）最大利润为：最大利润为：Z=50X50+100X250=27500原料A增加10千克，而利润增加为0元，27500-27500=0元；故原料A的对偶价格为0元，（理由是原料A还有剩余未用完，即使增加数量，仍然用不上，故利润不影响）。约束条件的对偶价格性质：（1）如果对偶价格大于0，则其最优目标函数值得到改进，MAX变大，MIN变小；（2）如果对偶价格小于0，则其最优目标函数值变坏，即求最大值时，变得更小，求最小值时，变得更大；（3）如果对偶价格等于0，则其最优目标值不变。