第四章 对偶单纯形法和对偶问题

1、整理ppt4.1 4.1 对偶问题的提出对偶问题的提出整理pptABC拥有量工 时1113材 料1479单件利润233整理ppt0, 0, 09743. .321321321xxxxxxxxxts321332maxxxxZ+=整理pptABC拥有量工 时1113材 料1479单件利润233 整理pptABC拥有量工 时1113材 料1479单件利润233在考虑这个问题时我们应做到：在考虑这个问题时我们应做到：1、价格应该尽量低，这样，才能有竞争力、价格应该尽量低，这样，才能有竞争力; 2、出卖资源获利应不少于生产产品的获利、出卖资源获利应不少于生产产品的获利; 3、价格应该是非负的、价格应该是

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

3、yyts321332maxxxxZ+=0, 0, 09743. .321321321xxxxxxxxxts整理ppt任何一个线性规划问题都有一个与之相对应任何一个线性规划问题都有一个与之相对应的线性规划问题，如果前者称为原始问题，后者的线性规划问题，如果前者称为原始问题，后者就称为就称为“对偶对偶”问题。问题。对偶问题是对原问题从另一角度进行的描述对偶问题是对原问题从另一角度进行的描述. .其最优解与原问题的最优解有着密切的联系，在其最优解与原问题的最优解有着密切的联系，在求得一个线性规划最优解的同时也就得到对偶线求得一个线性规划最优解的同时也就得到对偶线性规划的最优解，反之亦然。性规划的最优

4、解，反之亦然。对偶理论就是研究线性规划及其对偶问题的对偶理论就是研究线性规划及其对偶问题的理论，是线性规划理论的重要内容之一。理论，是线性规划理论的重要内容之一。 整理ppt4.2 4.2 建立对偶问题的规则建立对偶问题的规则整理ppt原问题原问题max z=C X A X b X0对偶问题对偶问题min w=b T YAT Y C TY0整理ppt二、对偶问题的特点二、对偶问题的特点（1）目标函数在一个问题中是求最大值在另）目标函数在一个问题中是求最大值在另一问题中则为求最小值一问题中则为求最小值（2）一个问题中目标函数的系数是另一个问）一个问题中目标函数的系数是另一个问题中约束条件的右端项

5、题中约束条件的右端项（3）一个问题中的约束条件个数等于另一个）一个问题中的约束条件个数等于另一个问题中的变量数问题中的变量数（4）原问题的约束系数矩阵与对偶问题的约）原问题的约束系数矩阵与对偶问题的约束系数矩阵互为转置矩阵束系数矩阵互为转置矩阵整理ppt对偶问题对应表对偶问题对应表原问题（对偶问题）原问题（对偶问题）对偶问题（原问题）对偶问题（原问题）目标函数目标函数max目标函数目标函数min变量数：变量数：n个个第第j个变量个变量 0第第j个变量个变量 0第第j个变量是自由变量个变量是自由变量 目标函数中变量的系数目标函数中变量的系数约束条件：约束条件：n个个第第j个约束类型为个约束类型为

6、“”第第j个约束类型为个约束类型为“”第第j个约束类型为个约束类型为“”约束条件右端项约束条件右端项约束条件：约束条件： m个个第第i个约束类型为个约束类型为“”第第i个约束类型为个约束类型为“”第第i个约束类型为个约束类型为“” 约束条件右端项约束条件右端项变量数：变量数： m个个第第i个变量个变量0第第i个变量个变量0第第i个变量是自由变量个变量是自由变量 目标函数中变量的系数目标函数中变量的系数整理ppt原问题： 对偶问题：maxZ=70X1+120X2 min=360y1+200y2+300y3 9X1+4X2360 9y1+4y2+3y3 70 4X1+5X2 200 4y1+5y2

7、+10y3 1203X1+10X2 300 y1 0, y2 0, y3 0X10 X20整理ppt练习写出如下LP问题的对偶问题123min23fxxx123123123123,3264235390,xxxxxxxxxxxx符号不限0,123max659zyyy123123123123,y0,y03412232353yyyyyyyyyy符号不限整理ppt4.3 4.3 对偶问题的基本性质对偶问题的基本性质( (选学选学) )整理ppt一、对称性一、对称性定理1、对偶问题的对偶就是原始问题定理2 （可行解的目标函数值之间的关系） 设X、Y分别是原始问题和对偶问题的可行解，则 CX YTb弱对偶

8、性弱对偶性整理ppt1.如果原问题（对偶问题）具有无界解，则其对偶问题（原问题）无可行解。2.若原问题可行,而对偶问题不可行,则原问题的目标函数值无界3.若对偶问题可行,而原问题不可行,则对偶问题的目标函数值无界推论 :整理ppt例如12123123123 : max22 21,0Zxxxxxxxxx x x 原1212121212: min221 2 0,0Wyyyyyyyyy y对试用对偶理论证明原问题无界。 解： =（0.0.0）是 原问题 的一个可行解，而 对偶 的第一个约束条件不能成立（因为y1 , y2 0)。因此，原问题无界。_X整理ppt11 (1,2, ) (1,2,) (1

9、,2, ) (1,2,)jinmjjiijijixjny imc xb yxjny im 如果是原问题的可行解是其对偶问题的可行解且有则是原问题的最优解是其对偶问题的最优解定理3整理ppt四、对偶定理四、对偶定理 定理4 如果原问题有最优解，则其对偶问题也一定有最优解，且两者的目标函数值相等 定理5 若X为原问题的满足最优检验的基本解。则Y=CBb-1为对偶问题的可行解 (原问题在得到基本可行解的同时，其检验数的相反数就构成对偶问题的一个基本解，且各自目标函数值恒相等。)整理pptCj -6 -3 -2 0 0 0jCBXBb X1 X2 X3 X4 X5 X6-20-3X3X6X216104

10、 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 Y60620Y4Y2Y1341 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整理ppt4.4 4.4 对偶单纯形法对偶单纯形法整理ppt 当一个线性规划问题是求目标函数值最小，约束方程是时，求解时用大M法或两阶段法比较麻烦，此时较有效的算法是将要介绍的对偶单纯形法 对偶单纯形法并不是求解对偶问题解的方法，而是

11、利用对偶理论求解原问题的解的方法。整理ppt第一第一 步步 找出一个初始正则解正则解B0，要求对应的单纯形表中的全部检验数 0，但右边项中允许有负数第二步第二步 若右边项中各数均非负，则B0已是最优基，即已求得最优解，计算终止；否则转为下一步第三步第三步 取右边项中取值最小（即负的最多）的数所对应的变量为换出变量。二、对偶单纯形法的计算步骤二、对偶单纯形法的计算步骤整理ppt第四步第四步 按公式 其中j c j z j 计算最小比值,则该列所对应的变量即为换入变量第五步第五步 以换出变量的行和换入变量列交点处的元素为主元进行单纯形迭代，再转入第二步整理ppt 用对偶单纯形法求解线性规划问题：

12、min w=15y1+24y2+5y3 6y2+y32 5y1+2y2+y31 yj0，对一切j解：先将问题改写为 max w=-15y1-24y2-5y3 max w=-15y1-24y2-5y3 6y2+y3-y4 =2 -6y2-y3+y4 =-2 5y1+2y2+y3 -y5=1 -5y1-2y2-y3 +y5=-1 yj0，对一切j yj0，对一切j整理ppt第一步第一步 建立一个初始单纯形表，使表中检验行的值全部 0 即对其对偶问题而言是一基本可行解。Cj-15 -24 -5 0 0CBYBb Y1 Y2 Y3 Y4 Y500Y4Y5-2-1 0 -6 -1 1 0 -5 -2 -

13、1 0 1j=cj-zj-15 -24 -5 0 0整理ppt第二步第二步 检验当前可行解是否可行，若可行，已得最优解，否则转入下一步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整理pptCj-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整理ppt第四步第四步 按公式 计算最小比值,则该列所对应的变量即为入基变量。（其中j

14、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 / /整理ppt第五步第五步 用换入变量替换对偶问题中的换出变量得到一个新的单纯形表。表中数字计算同用单纯形法时完全一样。新表中对偶问题仍保持基本可行解 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

15、/整理pptCj-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 -7/2 -3/2 Y1=0，Y2=1/4,Y3=1/2,W最优为17/2整理ppt四、练习四、练习课本60页 2整理ppt4.5 对偶问题的经济意义影子价格整理ppt定义：约束条件方程右端的定义：约束条件方程右端的bi增加一单位时，最优增加一单位时，最优目标函数目标函数z的变化量称为资源的变化量称为资源i的影子价格的影子价格.影子价格越大，说明这种资源越是相对紧缺影子价格越大，说

16、明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于的影子价格一定等于0种资源的边际利润第种资源的增量第最大利润的增量iibzwiooiqi整理ppt4.6 对偶单纯形法的一个应用（增加约束条件）整理ppt 在求出线性规划问题的最优解后，又增加一个约束条件，此时可以利用对偶单纯形法求解，不必对原问题从头做起。其步骤如下：1、将最优解代入新的约束条件，若满足，则最优解不变2、若不满足，则当前最优解要发生变化；将新增约束条件加入松弛变量或剩余变量后加入到原

17、来的最优单纯形表，令原来的基变量和新增加的变量组成新的基，进行初等变换将基变量对应的系数矩阵变为单位矩阵。3、利用对偶单纯形法继续迭代整理ppt二、例题0,1000354312004345800232435max43214321432143214321xxxxxxxxxxxxxxxxxxxxz4321435maxxxxxz整理pptCj 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/

18、4 0 -11/4 0 0 -1/4 -1X1=0，X2=100，X3=0，X4=200， X5=100，X6=0，X7=0,Z=1300整理pptj, 06503321000354312004345800232435max43214321432143214321对一切jxxxxxxxxxxxxxxxxxxxxxz4321435maxxxxxz整理pptCj 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 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 -