运筹学基础对偶线性规划精品文稿.ppt

《运筹学基础对偶线性规划精品文稿.ppt》由会员分享，可在线阅读，更多相关《运筹学基础对偶线性规划精品文稿.ppt（37页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运筹学基运筹学基础对偶偶线性性规划划第1页，本讲稿共37页一、对偶线性规划问题一、对偶线性规划问题某工厂计划安排生产、两种产品，已知每种单位产品的利润、生产单位产品所需的设备台时及A、B两种原材料的消耗、现有原材料和设备台时的定额如下表所示：【例1】设 备128台时原 材 料 A4016Kg原 材 料 B0412Kg每单位产品利润（万元）23n原问题的策略原问题的策略:n问应如何安排生产才能使工厂问应如何安排生产才能使工厂获利最大？获利最大？n现在的策略现在的策略:n假设不生产假设不生产、产品产品 ,而是计划将现有资而是计划将现有资源出租或出售源出租或出售,从而获得利润从而获得利润,这时需要考

2、虑这时需要考虑如何定价才合理如何定价才合理?第2页，本讲稿共37页 设x1、x2分别表示计划生产产品、的单位数量，由题意原问题的模型为：工厂获得最大利润符合资源限制 设 备128台时原 材 料 A4016Kg原 材 料 B0412Kg每单位产品利润（万元）23原问题的模型原问题的模型第3页，本讲稿共37页 改变策略后，需要考虑如何给资源定价的问题！设y1、y2、y3分别表示出租单位设备台时的租金和出售单位原材料A、B的利润.y y1 1+4y+4y2 222，2y1+4y33则：vv 工厂出租设备工厂出租设备工厂出租设备工厂出租设备、原材料的租金要大于生产的利润才合算。、原材料的租金要大于生产

3、的利润才合算。、原材料的租金要大于生产的利润才合算。、原材料的租金要大于生产的利润才合算。工厂把所有设备台时和资源都出租和出让，其收入为：vv 要寻找使租用者支付的租金最少的策略。要寻找使租用者支付的租金最少的策略。要寻找使租用者支付的租金最少的策略。要寻找使租用者支付的租金最少的策略。设 备128台时原 材 料 A4016Kg原 材 料 B0412Kg每单位产品利润（万元）23新问题的模型新问题的模型第4页，本讲稿共37页工厂改变策略以后改变策略以后的数学模型为：工厂获得相应利润用户所付租金最少第5页，本讲稿共37页 联系在于，它们都是关于工厂生产经营的模型,并且使用相同的数据；原模型和对偶

4、模型既有联系又有区别原模型和对偶模型既有联系又有区别原模型和对偶模型既有联系又有区别原模型和对偶模型既有联系又有区别 区别在于,它们所反映的实质内容是完全不同的：前者是站在工厂经营经营经营经营者者者者的立场上追求工厂的销售收入最大销售收入最大销售收入最大销售收入最大，而后者则是站在谈判对手谈判对手谈判对手谈判对手的立场上寻求应付工厂租金最少租金最少租金最少租金最少的策略。第6页，本讲稿共37页 所谓对偶规划对偶规划对偶规划对偶规划，就是与线性规划原问题相对应并使用同一组数据按照特定方法形成的另一种反映不同性质问题的线性规划模型。第7页，本讲稿共37页 原模型与对偶模型有很多的内在联系和相似之处

5、。如原问题如求目标函数最大化，对偶问题即求目标函数最小化；原问题目标函数的系数变成为对偶问题的右边项，而原问题的约束的右边项则变成为对偶问题目标函数的系数；对偶问题的系数矩阵是原问题系数矩阵的转置。就象一个人对着镜子会左右颠倒一样，原问题与对偶问题之间存在着严格的对应关系。原问题的一般模型可定义为：二、对偶规划的一般数学模型nnxcxcxcZ+=.max2211s.t.11212111.bxaxaxann+22222121.bxaxaxann+.mnmnmmbxaxaxa+.22110,.,21nxxx相应的对偶问题的一般模型可定义为：mmybybybS+=.min2211 s.t.11221

6、111.cyayayamm+22222112.cyayayamm+nmmnnncyayaya+.22110,.,21myyy第8页，本讲稿共37页 上述的原问题P和对偶问题 D D还可以用矩阵形式写为：(P)max Z=cx s.t.Ax b x 0其中),.,(21myyyy=上述的对偶模型都称作为对称型对偶模型对称型对偶模型对称型对偶模型对称型对偶模型。而在当原问题转化为标准型以后所建立的对偶模型则是非对称非对称非对称非对称型的型的型的型的，如：(P)maxZ=cx s.t.Ax=b x0s.t.yAy c 0(D)min S=ybs.t.yAcy为自由变量(D)minS=yb原问题与对偶

7、问题的矩阵形式问题：如何由原模型写出对偶模型？其规律是什么问题：如何由原模型写出对偶模型？其规律是什么?第9页，本讲稿共37页三、原问题与对偶问题的对应关系 当我们讨论对偶问题时必定是指一对问题，因为没有原问题也就不可能有对偶问题。原问题和对偶问题总是相依存在的。同时，原问题和对偶问题之间也并没有严格的界线，它们互为对偶，谁都可以是原问题，谁也都可以是对偶问题。下列的表给出了原问题模型和模型的对应关系，这些也可以看作是一个线性规划原问题转化为对偶问题的一般规律。原问题线性规划模型原问题线性规划模型对偶线性规划模型对偶线性规划模型第10页，本讲稿共37页原问题为maxZ的线性规划问题对偶关系表原

8、问题原问题原问题原问题（或对偶问题）对偶问题对偶问题对偶问题对偶问题（或原问题）目标函数最大化(maxZ)n个变量 m个约束 约束条件限定向量（右边项）目标函数价值向量（系数）0 变量 0 无限制 约束 目标函数最小化（minS）n个约束 m个变量 目标函数价值向量（系数）约束条件限定向量（右边项）约束 0 0 变量 0 无限制 同号同号反号反号第11页，本讲稿共37页 原问题原问题对偶问题对偶问题目标函数目标函数max 目标函数目标函数min原问题(maxZ)与对偶之关系：原问题原问题原问题原问题(maxZ)(maxZ)口诀口诀口诀口诀:约束决定变量是反号约束决定变量是反号约束决定变量是反号

9、约束决定变量是反号原问题原问题原问题原问题(maxZ)(maxZ)口诀口诀口诀口诀:变量决定约束是同号变量决定约束是同号变量决定约束是同号变量决定约束是同号第12页，本讲稿共37页解：由原模型三个约束条件确定对偶模型有三个变量y1,y2,y3（还可依对偶问题写出原问题）例1写出下列问题的对偶问题：变量决定约束是同号变量决定约束是同号变量决定约束是同号变量决定约束是同号,约束决定变量是反号约束决定变量是反号约束决定变量是反号约束决定变量是反号 max Z=2x1+x2 5x2 15 6x1+2x2 24 x1+x2 5 x1,x2 0 min w=15y1+24y2+5y3 6y2+y3 2s.

10、t.y1,y2,y3 0 5y1+2y2+y3 1第13页，本讲稿共37页原问题为minS的线性规划问题对偶关系表原问题原问题原问题原问题（或对偶问题）对偶问题对偶问题对偶问题对偶问题（或原问题）目标函数最小化(minS)n个变量 m个约束 约束条件限定向量（右边项）目标函数价值向量 0 变量 0 无限制 约束 目标函数最大化（maxZ）n个约束 m个变量 目标函数价值向量（系数）约束条件限定向量 约束 0 0 变量 0 0无限制 同号同号反号反号第14页，本讲稿共37页原问题原问题对偶问题对偶问题目标函数目标函数min 目标函数目标函数max原问题(minS)与对偶之关系：原问题原问题原问题

11、原问题(minS)(minS)口诀口诀口诀口诀:约束决定变量是同号约束决定变量是同号约束决定变量是同号约束决定变量是同号原问题原问题原问题原问题(minS)(minS)口诀口诀口诀口诀:变量决定约束是反号变量决定约束是反号变量决定约束是反号变量决定约束是反号第15页，本讲稿共37页解：由原模型三个约束条件确定对偶模型有三个变量y1,y2,y332134maxyyyZ+-=s.t.1232 1-yy2y-332 1+-y4y42321+yyy（还可依对偶问题写出原问题）例2 写出下列问题的对偶问题：32143MinxxxS+-=s.t.1321+-4xx2x423321-+-xxx3-23 1+

12、x xx1,x2,x3 0变量决定约束是反号变量决定约束是反号变量决定约束是反号变量决定约束是反号,约束决定变量是同号约束决定变量是同号约束决定变量是同号约束决定变量是同号01y，02y03y，第16页，本讲稿共37页练习：试求下列线性规划问题的对偶问题321342maxxxxZ-+=s.t.10321+-xxx534321-=-+-xxx8523321-+xxx01x，02x 第17页，本讲稿共37页练习：试求下列线性规划问题的对偶问题 答案：答案：答案：答案：321342maxxxxZ-+=s.t.10321+-xxx534321-=-+-xxx8523321-+xxx01x，02x 32

13、18510minyyyS+-=s.t.23321+-yyy424321+-yyy353321-=-yyy01y，03y第18页，本讲稿共37页练习：试求下列线性规划问题的对偶问题 maxZ=5y1+4y2+6y3 y1+2y2 2 y1+2y2+y3 3 -3y1 +y3 -5 y1 -y2 +y31 y1 0,y2,y3 0 答案：答案：答案：答案：第19页，本讲稿共37页线性规划的对偶理论包括以下几个基本定理。定理1（对称性定理）2.2 线性规划的对偶理论定理2（弱对偶定理）即对偶问题的对偶是原问题。设x和y分别是原问题和对偶问题的可行解，则必有cxyb，即原问题的目标值小于对偶问题的目标

14、值定理3（无界性）若原问题(对偶问题)为无界解无界解无界解无界解，则其对偶问题(原问题)无可行解无可行解。若原（对偶）问题有可行解有可行解,对偶（原）问题无可行解无可行解，则原（对偶）问题一定无界无界；注:此定理可以判定解的情况第20页，本讲稿共37页定理4（可行解是最优解的性质）定理5（强对偶定理）设X*是原问题的可行解，Y*是对偶问题的可行解，当CX*=Y*b时，X*与Y*是最优解。若原问题有最优解，那么对偶问题也有最优解，且目标函数值相等 综合上述结论得原问题与对偶问题的解的关系一般是：一般是：cxyb第21页，本讲稿共37页 对 偶 问 题 有最优解 无界 无可行解原 有最优解 一定

15、不可能 不可能问 无 界 不可能 不可能 一定题 无可行解 不可能 可能 可能原问题与对偶问题解的对应关系原问题与对偶问题解的对应关系 由原问题与对偶问题的解的关系可以判定线性规划的解。第22页，本讲稿共37页例4 已知线性规划问题 Max z=x1+x2 S.t.x1+x2+x3 2 2x1+x2 x3 1 xi 0(i=1,2,3)Min w=2y1+y2 S.t.y1 2y2 1 y1+y2 1 y1 y2 0 y1,y2 0应用如上关系求解线性规划问题试用对偶理论证明上述规划问题无最优解。由第一约束条件可知对偶问题无可行解，则原问题的解无界或无可行解，由于原问题存在可行解，所以解无界。

16、表2：原问题与对偶问题解的对应关系 对 偶 问 题 有最优解 无界 无可行解原 有最优解 一定 不可能 不可能问 无 界 不可能 不可能 一定题 无可行解 不可能 可能 可能解 该问题存在可行解，如X=(0，0，0)；其对偶问题为：对偶问题无可行解第23页，本讲稿共37页定理6（互补松弛定理）在线性规划问题的最优解中，如果对应某一约束条件的对对对对偶变量值为非零偶变量值为非零偶变量值为非零偶变量值为非零，则该约束条件取严格等式严格等式严格等式严格等式；反之如果约束条件约束条件约束条件约束条件取严格不等式取严格不等式取严格不等式取严格不等式，则其对应的对偶变量一定为零对偶变量一定为零对偶变量一定

17、为零对偶变量一定为零。注：证明过程参见教材注：证明过程参见教材5959页性质页性质5 5证明证明第24页，本讲稿共37页讨论:互补松弛定理也称松紧定理，它描述了线性规划达到最优时，原问题（或对偶问题）的变量取值和对偶问题（或原问题）约束松紧之间的对应关系。当线性规划问题达到最优时，我们不仅同时得到了原问题和对偶问题的最优解，而且也还得到了变量和约束之间的一种对应关系。互补松弛定理即揭示了这一点。第25页，本讲稿共37页1.如果原问题的某一约束为紧约束（严格等式:松弛变量为零），该约束对应的对偶变量应大于或等于零；2.如果原问题的某一约束为松约束（严格不等式:松弛变量大于零），则对应的对偶变量必

18、为零；3.如果原问题的某一变量大于零该变量对应的对偶约束必为紧约束(严格等式)；4.如果原问题的某一变量等于零，该变量对应的对偶约束可能是紧约束(严格等式)，也可能是松约束(严格不等式)。线性规划达到线性规划达到最优最优时的关系时的关系第26页，本讲稿共37页例5 已知线性规划问题 Min S=2x1+3x2+5x3+2x4 +3x5 S.t.x1+x2+2x3+x4+3x5 4 2x1 x2+3x3+x4+x5 3 xi 0(i=1,2,3,4,5)221/5 317/557/5 23=3 解：写出对偶问题为：Max Z=4y1+3y S.t.y1+2y2 2 y1 y2 3 2y1+3y2

19、 5 y1+y2 2 3y1+y2 3 y1,y2 0又例:应用如上关系求解线性规划问题已知对偶问题的最优解为 y1=4/5,y2=3/5,试应用对偶理论求解原问题。x2=0 x3=0 x4=0等号又因y1,y2 0，故原问题的两个约束必为紧约束，即x1+3 x5=42x1+x5=3解得：x1=x5=1。maxZ=5=minS=5得原问题的最优解X*=(1,0,0,0,1)minS=5第27页，本讲稿共37页 Max.Z=2x1+4x2+x3+x4 s.t.x1+3x2 +x48 2x1+x2 6 x2 +x3 +x46 x1 +x2 +x3 9 xj0（j=1,2,3,4）附 练习答案：y1

20、=4/5,y2=3/5,y3=1,y4=0已知原问题的最优解为:X*=(2,2,4,0)T，试根据互补松弛定理解出其对偶问题的最优解。线性规划问题的对偶问题为：Min.Z=8y1+6y2+6y3+9y4 s.t.y1+2y2 +y4 2 3y1+y2+y3 +y4 4 y3 +y4 1 y1 +y3 1 yj0（j=1,2,3,4）练习：已知线性规划问题为：第28页，本讲稿共37页为严格不等式，由互补松弛定知，必有y4=0；Max.Z=2x1+4x2+x3+x4 s.t.x1+3x2 +x48 2x1+x2 6 x2 +x3 +x46 x1 +x2 +x3 9 xj0（j=1,2,3,4）8=

21、8 6=6 6=6 89解之，有：y1=4/5,y2=3/5,y3=1，y4=0答案：因为原问题的最优解为:X*=(2,2,4,0)T：又因x1,x2,x30，故对偶问题的前三个约束必为紧约束 线性规划问题的对偶问题为：Min.Z=8y1+6y2+6y3+9y4 s.t.y1+2y2 +y4 2 3y1+y2+y3 +y4 4 y3 +y4 1 y1 +y3 1 yj0（j=1,2,3,4）y1+2y2=2 3y1+y2+y3 =4 y3 =1等号第29页，本讲稿共37页（1）写出对偶问题；（2）已知原问题的最优解为X*=（2，0，1，1）T，求对偶问题的最优解。已知线性规划问题第30页，本讲

22、稿共37页定理7结论：用单纯形法求解线性规划时，迭代的每一步在得到原问题一个基本可行解基本可行解的同时，其：线性规划原问题及其对偶问题之间存在一对互补的基解，其中原原原原问问问问题题题题的的的的松松松松驰驰驰驰变变变变量量量量对应对对对对偶偶偶偶问问问问题题题题的的的的变变变变量量量量，对对对对偶偶偶偶问问问问题题题题的的的的剩剩剩剩余余余余变变变变量量量量对应原原原原问问问问题题题题的的的的变变变变量量量量；这些互相对应的变量如果在一个问题的解中是基基变变量量，则在另一问题的解中是是是是非非非非基基基基变变变变量量量量；将这两个解代入各自的目标数中有 z=w。注：证明过程参见教材注：证明过程

23、参见教材6060页性质页性质6 6证明证明检验数行的-(cj-zj)值是其对偶问题的一个基本解基本解基本解基本解yi ；第31页，本讲稿共37页用单纯形法同时求解用单纯形法同时求解原问题原问题和和对偶问题对偶问题 原问题是：maxZ=2x1+x2 5x2 15 6x1+2x2 24 x1+x2 5 x1,x2 0原问题的标准型是：maxZ=2x1+x2+0 x3+0 x4+0 x5 5x2+x3 =15 6x1+2x2 +x4 =24 x1+x2 +x5=5 xi 0第32页，本讲稿共37页 Cj比比值值CBXBb检验数检验数 jx1x2x3x4x52100015051002462010511

24、001x3x4x5000021000 maxZ=2x1+x2+0 x3+0 x4+0 x5 5x2+x3 =15 6x1+2x2 +x4 =24 x1+x2 +x5=5 xi 0-24/6=45/1=5原问题变量原问题松驰变量对偶问题剩余变量y4、y5对偶问题变量y1、y2、y3得原问题可行解得原问题可行解得原问题可行解得原问题可行解:X X=(0,0,15,24,5)=(0,0,15,24,5)T T对偶问题解对偶问题解对偶问题解对偶问题解:Y*Y*=(0,0,0,-2,-1)=(0,0,0,-2,-1)T T检验数行的(cj-zj)值是其对偶问题的一个基本解基本解基本解基本解yi ；第33

25、页，本讲稿共37页 检验数检验数 j1505100411/301/60102/30-1/61x3x1x5020-801/30-1/303121.5得原问题可行解得原问题可行解得原问题可行解得原问题可行解:X X=(4,0,15,0,1)=(4,0,15,0,1)T T，此时，此时，此时，此时Z=8Z=8同时得对偶问题基础解同时得对偶问题基础解同时得对偶问题基础解同时得对偶问题基础解:Y*Y*=(0,1/3,0,0,-1/3)=(0,1/3,0,0,-1/3)T T，W=8W=8对偶问题剩余变量y4、y5对偶问题变量y1、y2、y3原问题变量原问题松驰变量检验数行的-(cj-zj)值是其对偶问题

26、的一个基本解基本解基本解基本解yi ；第34页，本讲稿共37页变换单纯形表变换单纯形表Cj比比值值CBXBb检验数检验数 j=cj-zjx1x2x3x4x52100015/20 0 15/4-15/27/21001/4-1/23/2010-1/43/2x3x1x2021-17/2000-1/4-1/2此时得原问题最优解此时得原问题最优解此时得原问题最优解此时得原问题最优解:X X*=(7/2,3/2,15/2,0,0)=(7/2,3/2,15/2,0,0)T T，Z Z*=17/2=17/2原问题变量原问题松驰变量对偶问题剩余变量y4、y5对偶问题变量y1、y2、y3则对偶问题最优解则对偶问题

27、最优解则对偶问题最优解则对偶问题最优解:Y Y*=(0,1/4,1/2,0,0)=(0,1/4,1/2,0,0)T T，S S*=17/2=17/2检验数行的-(cj-zj)值是其对偶问题的一个基本解基本解基本解基本解yi ；第35页，本讲稿共37页又例：又例：用单纯形法同时求解用单纯形法同时求解原问题原问题和和对偶问题对偶问题maxZ=100 x1+80 x2 2 x1+4 x2 80 3 x1+x2 60 x1,x2 0将线性规划问题标准化将线性规划问题标准化将线性规划问题标准化将线性规划问题标准化maxZ=100 x1+80 x2+0 x3+0 x4 2 x1+4 x2+x3 =80 3

28、 x1+x2 +x4=60 x1,x2 x3 x4 0第36页，本讲稿共37页 00080100-Z60101308001420 此时得原问题的最优解：X0=(16,12,0,0)T,maxZ=2560初等变换初等变换-2000-100/30140/30-Z201/301/31 1040-2/3110/300 2 x1+4 x2 +x3 =80 3 x1+x2 +x4=60-Z+100 x1+80 x2+0 x3+0 x4=0-2560-24-1400-Z162/5-1/1001012-1/53/101 100-Z x1 x2 x3 x4 b 同时得对偶问题的最优解：y1=14,y2=24,y3=0,y4=0,即Y0=(14,24,0,0)T,minS=2560第37页，本讲稿共37页