基础运筹学教程（第三版）- 第一章-6 对偶规划.ppt

*y1y2ym4、产品的机会成本机会成本表示减少一件产品所节省的资源可以增加的利润增加单位资源可以增加的利润减少一件产品可以节省的资源*机会成本利润差额成本5、产品的差额成本（ReducedCost）差额成本=机会成本-利润*6、互补松弛关系的经济解释在利润最大化的生产计划中:（1）边际利润大于0的资源没有剩余（2）有剩余的资源边际利润等于0（3）安排生产的产品机会成本等于利润（4）机会成本大于利润的产品不安排生产*单纯形法对偶单纯形法可行条件：优化条件：1.基本原理六、对偶单纯形法*2.基本思想对偶单纯形法的基本思想就是建立在对偶规划基可行解之间的迭代上。也就是说，在迭代的过程中，始终保持对偶规划解的可行性。表现在单纯行表上：即为所有检验数恒为非负，与此同时，使基变量XB的取值逐步变成非负，此时，就得到了原规划的最优解，同时，也得到了对偶规划的最优解。3.定义正则解：单纯形表中检验数均非正时所对应的基解称为正则解。正则基：正则解对应的基为正则基*4.基本步骤（1）选取初始正则基，作出相应的初始单纯形表（2）可行性检验。当时，已得最优解。否则转下步；（3）确定换出变量。按选取xe为换出变量，检验第e行中非基变量xe的系数αej，若所有的αej≥0，则线性规划问题无可行解。否则转下步；（4）确定换入变量。根据确定为xk换入变量，标出主元素αek，应用矩阵的初等行变换得到新的单纯形表；（5）重复2~4中的步骤直到终止。*5.单纯形法和对偶单纯形法步骤比较是是否否所有得到最优解计算典式对应原规划的基本解是可行的所有计算以为中心元素进行迭代停没有最优解没有最优解单纯形法是是否否所有计算典式对应原规划的基本解的检验数所有计算以为中心元素进行迭代对偶单纯形法*6.应用对偶单纯型法求解下面的线性规划问题*由b5＝min{-20,-24,-10}得出基变量为x5；由θ2＝min{-6/(-2),3/(-2),2/(-1)}=3/2，得入基变量为x2，以a52为主元做旋转运算得：[]Cj--6-3-2000CBXBx1x2x3x4x5x60x4-1-1-1100-200x5-2-2-1010-240x6-1-1-1001-10σ－-6-3-2000ZB’＝0θ－33/22*由b4＝min{-8}＝-8得出基变量为x4，由θ2＝min{(-1/2)/(-1/2)，(-3/2)/(-1/2)}={1，3}=1，得入基变量为x3，以a43为主元做旋转运算得：[]Cj--6-3-2000CBXBx1x2x3x4x5x60x400-1/21-1/20-8-3x2111/20-1/20120x600-1/20-1/212σ－－30－1/20－3/20ZB＝-36θ－13*-6-3-2000bCBXBx1x2x3x4x5x6-2x3001-21016-3x21101-1040x6000-10110σ-300110ZB’=-44从上表中可以得出：b=[16,4,10]≥0,故得最优解。采用对偶单纯形法所得原规划问题的最优解和最优值分别为：X*=(0，4，16，0，0，10)T，Z*=44；同时，我们也可以得到其对偶规划问题的最优解和最优值分别为：Y*＝(1，1，0)T，Z*=44思考题：采用单纯形法求解应该怎样的过程和结果？*7.进一步讨论我们回忆一下前面在讲线性规划问题的标准化的时候，给出了线性规划标准型的几个标准如下：目标函数：max约束条件：=右端项：非负变量符号≥0约束方程组的数量变量的个数，即：*当我们学习了对偶规划理论之后，再来看这个问题：在原规划和相应的对偶规划中，决策变量的个数和约束方程的个数正好相反，如果原规划的方程数为，则其对偶规划中的方程数就一