对偶单纯形法和对偶问题PPT学习教案

1、会计学1对偶单纯形法和对偶问题对偶单纯形法和对偶问题ABC拥有量工 时1113材 料1479单件利润233第1页/共42页0, 0, 09743. .321321321xxxxxxxxxts321332maxxxxZ+=第2页/共42页ABC拥有量工 时1113材 料1479单件利润233 第3页/共42页ABC拥有量工 时1113材 料1479单件利润233在考虑这个问题时我们应做到：在考虑这个问题时我们应做到：1、价格应该尽量低，这样，才能有竞争力、价格应该尽量低，这样，才能有竞争力; 2、出卖资源获利应不少于生产产品的获利、出卖资源获利应不少于生产产品的获利; 3、价格应该是非负的、价格

2、应该是非负的 第4页/共42页ABC拥有量工 时1113材 料1479单件利润233 现在我们用数学语言描述，设现在我们用数学语言描述，设y1和和y2分别表示单分别表示单位工时和材料的出售价格位工时和材料的出售价格总价格最小总价格最小 min W=3y1+9y2保证获利大于保证获利大于A产品利润产品利润 y1+y22 保证保证获利大于获利大于B产品利润产品利润 y1+4y23 保证保证获利大于获利大于C产品利润产品利润 y1+7y23 售价非负售价非负 y10 y20第5页/共42页ABC拥有量工 时1113材 料1479单件利润2332193minyyW+=0, 037342. .21212

3、121yyyyyyyyts321332maxxxxZ+=0, 0, 09743. .321321321xxxxxxxxxts第6页/共42页第7页/共42页第8页/共42页原问题原问题max z=C X A X b X0第9页/共42页偶问题的约束系数矩阵互为转偶问题的约束系数矩阵互为转置矩阵置矩阵第10页/共42页对偶问题对应表对偶问题对应表原问题（对偶问题）原问题（对偶问题）对偶问题（原问题）对偶问题（原问题）目标函数目标函数max目标函数目标函数min变量数：变量数：n个个第第j个变量个变量 0第第j个变量个变量 0第第j个变量是自由变量个变量是自由变量 目标函数中变量的系数目标函数中变

4、量的系数约束条件：约束条件：n个个第第j个约束类型为个约束类型为“”第第j个约束类型为个约束类型为“”第第j个约束类型为个约束类型为“”约束条件右端项约束条件右端项约束条件：约束条件： m个个第第i个约束类型为个约束类型为“”第第i个约束类型为个约束类型为“”第第i个约束类型为个约束类型为“” 约束条件右端项约束条件右端项变量数：变量数： m个个第第i个变量个变量0第第i个变量个变量0第第i个变量是自由变量个变量是自由变量 目标函数中变量的系数目标函数中变量的系数第11页/共42页第12页/共42页练习写出如下LP问题的对偶问题123min23fxxx123123123123,32642353

5、90,xxxxxxxxxxxx符号不限0,123max659zyyy123123123123,y0,y03412232353yyyyyyyyyy符号不限第13页/共42页第14页/共42页一、对称性一、对称性定理1、对偶问题的对偶就是原始问题定理2 （可行解的目标函数值之间的关系） 设X、Y分别是原始问题和对偶问题的可行解，则 CX YTb弱对偶性弱对偶性第15页/共42页1.如果原问题（对偶问题）具有无界解，则其对偶问题（原问题）无可行解。2.若原问题可行,而对偶问题不可行,则原问题的目标函数值无界3.若对偶问题可行,而原问题不可行,则对偶问题的目标函数值无界推论 :第16页/共42页例如1

6、2123123123 : max22 21,0Zxxxxxxxxx x x 原1212121212: min221 2 0,0Wyyyyyyyyy y对试用对偶理论证明原问题无界。 解： =（0.0.0）是 原问题 的一个可行解，而 对偶 的第一个约束条件不能成立（因为y1 , y2 0)。因此，原问题无界。_X第17页/共42页11 (1,2, ) (1,2,) (1,2, ) (1,2,)jinmjjiijijixjny imc xb yxjny im 如果是原问题的可行解是其对偶问题的可行解且有则是原问题的最优解是其对偶问题的最优解定理3第18页/共42页四、对偶定理四、对偶定理 定理4

7、 如果原问题有最优解，则其对偶问题也一定有最优解，且两者的目标函数值相等 定理5 若X为原问题的满足最优检验的基本解。则Y=CBb-1为对偶问题的可行解 (原问题在得到基本可行解的同时，其检验数的相反数就构成对偶问题的一个基本解，且各自目标函数值恒相等。)第19页/共42页Cj -6 -3 -2 0 0 0jCBXBb X1 X2 X3 X4 X5 X6-20-3X3X6X216104 0 0 1 -2 4 0 -1 0 0 -1 0 1 1 1 0 1 -4 0j = cj-zj -3 0 0 -1 -4 0Cj 20 6 10 0 0 0jCBYBb Y1 Y2 Y3 Y4 Y5 Y606

8、20Y4Y2Y1341 0 0 1 1 1 -10 0 1 0 0 4 -4 1 0 1 0 -1 2j = cj-zj 0 0 -10 0 -4 -16第20页/共42页第21页/共42页第22页/共42页第一第一 步步 找出一个初始正则解正则解B0，要求对应的单纯形表中的全部检验数 0，但右边项中允许有负数第二步第二步 若右边项中各数均非负，则B0已是最优基，即已求得最优解，计算终止；否则转为下一步第三步第三步 取右边项中取值最小（即负的最多）的数所对应的变量为换出变量。二、对偶单纯形法的计算步骤二、对偶单纯形法的计算步骤第23页/共42页第24页/共42页第25页/共42页第一步第一步

9、建立一个初始单纯形表，使表中检验行的值全部 0 即对其对偶问题而言是一基本可行解。Cj-15 -24 -5 0 0CBYBb Y1 Y2 Y3 Y4 Y500Y4Y5-2-1 0 -6 -1 1 0 -5 -2 -1 0 1j=cj-zj-15 -24 -5 0 0第26页/共42页第二步第二步 检验当前可行解是否可行，若可行，已得最优解，否则转入下一步Cj-15 -24 -5 0 0CBYBb Y1 Y2 Y3 Y4 Y500Y4Y5-2-1 0 -6 -1 1 0 -5 -2 -1 0 1j=cj-zj-15 -24 -5 0 0第27页/共42页第三步第三步 选择选择b列中取值最小（即负

10、的最多）的数所对应的变量为出列中取值最小（即负的最多）的数所对应的变量为出基变量。基变量。Cj-15 -24 -5 0 0CBYBb Y1 Y2 Y3 Y4 Y500Y4Y5-2-1 0 -6 -1 1 0 -5 -2 -1 0 1j=cj-zj-15 -24 -5 0 0第28页/共42页第四步第四步 按公式 计算最小比值,则该列所对应的变量即为入基变量。（其中j c j z j ）Cj-15 -24 -5 0 0CBYBb Y1 Y2 Y3 Y4 Y500Y4Y5-2-1 0 -6 -1 1 0 -5 -2 -1 0 1j=cj-zj-15 -24 -5 0 0 / 4 5 / /第29页

11、/共42页第五步第五步 用换入变量替换对偶问题中的换出变量得到一个新的单纯形表。表中数字计算同用单纯形法时完全一样。新表中对偶问题仍保持基本可行解 Cj-15 -24 -5 0 0CBYBb Y1 Y2 Y3 Y4 Y5-240Y2Y51/3-1/3 0 1 1/6 -1/6 0 -5 0 -2/3 -1/3 1j=cj-zj-15 0 -1 -4 0 3 / 3/2 12 /第30页/共42页Cj-15 -24 -5 0 0CBYBb Y1 Y2 Y3 Y4 Y5-24-5Y2Y31/41/2-5/4 1 0 -1/4 1/415/2 0 1 1/2 -3/2j=cj-zj-15/2 0 0

12、 -7/2 -3/2 Y1=0，Y2=1/4,Y3=1/2,W最优为17/2第31页/共42页四、练习四、练习课本60页 2第32页/共42页第33页/共42页定义：约束条件方程右端的定义：约束条件方程右端的bi增加一单位时，最优增加一单位时，最优目标函数目标函数z的变化量称为资源的变化量称为资源i的影子价格的影子价格.影子价格越大，说明这种资源越是相对紧缺影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于的影子价格一定等于0种资源的

13、边际利润第种资源的增量第最大利润的增量iibzwiooiqi第34页/共42页第35页/共42页第36页/共42页二、例题0,1000354312004345800232435max43214321432143214321xxxxxxxxxxxxxxxxxxxxz4321435maxxxxxz第37页/共42页Cj 1 5 3 4 0 0 0CBXBb X1 X2 X3 X4 X5 X6 X7 045X5X4X2100200100 1/4 0 -13/4 0 1 1/4 -1 2 0 -2 1 0 1 -1-3/4 1 11/4 0 0 -3/4 1j=cj-zj-13/4 0 -11/4 0

14、 0 -1/4 -1X1=0，X2=100，X3=0，X4=200， X5=100，X6=0，X7=0,Z=1300第38页/共42页j, 06503321000354312004345800232435max43214321432143214321对一切jxxxxxxxxxxxxxxxxxxxxxz4321435maxxxxxz第39页/共42页Cj 1 5 3 4 0 0 0 0CBXBb X1 X2 X3 X4 X5 X6 X7 X80450X5X4X2X8100200100650 1/4 0 -13/4 0 1 1/4 -1 0 2 0 -2 1 0 1 -1 0-3/4 1 11/4

15、 0 0 -3/4 1 0 1 2 3 3 0 0 0 1Cj 1 5 3 4 0 0 0 0CBXBb X1 X2 X3 X4 X5 X6 X7 X80450X5X4X2X8100200100450 1/4 0 -13/4 0 1 1/4 -1 0 2 0 -2 1 0 1 -1 0-3/4 1 11/4 0 0 -3/4 1 0 5/2 0 -5/2 3 0 3/2 -2 1Cj 1 5 3 4 0 0 0 0CBXBb X1 X2 X3 X4 X5 X6 X7 X80450X5X4X2X8100200100-150 1/4 0 -13/4 0 1 1/4 -1 0 2 0 -2 1 0 1 -1 0-3/4 1 11/4 0 0 -3/4 1 0-7/2 0 7/2 0 0 -3/2 1 1第40页/共42页Cj 1 5 3 4 0 0 0 0CBXBb X1 X2 X3 X4 X5 X6 X7 X80450X5X4X2X8100200100-150 1/4 0 -13/4 0 1 1/4 -1 0 2 0 -2 1 0 1 -1 0-3/4 1 11/4 0 0 -3/4 1 0-7/2 0 7/2 0 0 -3/2 1 1j=cj-zj-13/4 0 -11