第三章第三章 线性规划对偶理论及其应用线性规划对偶理论及其应用3.1 3.1 线性规划的对偶问题线性规划的对偶问题3.3 3.3 对偶单纯形法对偶单纯形法3.4 3.4 影子价格和灵敏度分析影子价格和灵敏度分析3.2 3.2 对偶规划的基本性质对偶规划的基本性质3.4 3.4 影子价格和灵敏度分析影子价格和灵敏度分析原问题是利润最大化的生产计划问题原问题是利润最大化的生产计划问题单位产品的利润元单位产品的利润元/件）件）产品产量件）产品产量件）总利润元）总利润元）资源限量吨）资源限量吨）单位产品消耗的资源吨单位产品消耗的资源吨/件）件）剩余的资源吨）剩余的资源吨）消耗的资源吨）消耗的资源吨）对偶问题对偶问题资源限量吨）资源限量吨）资源价格元资源价格元/吨）吨）总利润元）总利润元）对偶问题是资源定价问题，对偶问题的最优解对偶问题是资源定价问题，对偶问题的最优解w1、w2、.、wm称为称为m种资源的影子价格种资源的影子价格Shadow Price）原始和对偶问题都取得最优解时，最大利润原始和对偶问题都取得最优解时，最大利润 max z=min y 定义：在一对定义：在一对 P 和和 D 中，假设中，假设 P 的某个约束的某个约束条件的右端项常数条件的右端项常数bi 增加一个单位时，所引起的增加一个单位时，所引起的目标函数最优值目标函数最优值Z* 的改变量的改变量y*i 称为第称为第 i 个约束个约束条件的影子价格，又称为边际价格。条件的影子价格，又称为边际价格。 一、影子价格的概念一、影子价格的概念 设：设：B是问题是问题 P的最优基，由前表可知，的最优基，由前表可知， Z*=CB B-1b = Y*b =y*1b1+ y*2b2+.+y*Ibi+.+y*mbm 当当bi 变为变为bi+1 时时(其它条件不变），其它条件不变），CCBCN0CBXBbXBXNXSCBXBB-1bIB-1NB-1ZCB B-1b0CB B-1N CNCB B-1 目标函数最优值变为：目标函数最优值变为： Z*= y*1b1+ y*2b2+.+y*I （ bi+1 ）+.+y*mbm 所以所以 Z*= Z* Z* = y*i 也可以写成：也可以写成：即即y*i 表示表示Z*对对 bi的变化率。的变化率。 其经济意义是：在其它条件不变的情况下，单位其经济意义是：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。即对资源变化所引起的目标函数的最优值的变化。即对偶变量偶变量yi 就是第就是第 i 个约束条件的影子价格。个约束条件的影子价格。 也可以理解为目标函数最优值对资源的一阶偏导也可以理解为目标函数最优值对资源的一阶偏导数但问题中所有其它数据都保持不变）。数但问题中所有其它数据都保持不变）。考虑具有三种资源的优化问题：考虑具有三种资源的优化问题：302010由图示可知最优点为由图示可知最优点为由图示可知最优点为由图示可知最优点为B B3535，1010），最优值为），最优值为），最优值为），最优值为215215。例例14 影子价格的图解法影子价格的图解法x18060402020406080100Bx22010 由图示可知最优点为由图示可知最优点为由图示可知最优点为由图示可知最优点为B(35,10) ,B(35,10) ,最优值为最优值为最优值为最优值为215215。故资源故资源故资源故资源A A的影子价格为的影子价格为的影子价格为的影子价格为0 0。假设资源假设资源A增加增加1个单位，其它条件不变：个单位，其它条件不变：8060402020406080x1100Bx2302010由图示可知最优点为由图示可知最优点为由图示可知最优点为由图示可知最优点为B B （3636，9 9），最优值为），最优值为），最优值为），最优值为216216。故资源故资源故资源故资源B B的影子价格为的影子价格为的影子价格为的影子价格为1 1。8060402020406080x1100Bx2假设资源假设资源B增加增加1个单位，其它条件不变：个单位，其它条件不变：2010由图示可知最优点为由图示可知最优点为由图示可知最优点为由图示可知最优点为B(34B(34，1212），最优值为），最优值为），最优值为），最优值为218218，故故故故C C的影子价格为的影子价格为的影子价格为的影子价格为3 3。8060402020406080x1100Bx2假设资源假设资源C增加增加1个单位，其它条件不变：个单位，其它条件不变： 若第若第i 种资源的单位市场价格为种资源的单位市场价格为mi ，当，当yi mi 时，企业愿意购进这种资源，单位纯利为时，企业愿意购进这种资源，单位纯利为yimi ，则有利可图；如果，则有利可图；如果yi 0，则应投产，则应投产,若若n+1=Cn+1CBB-1Pn+10，则不应投产。，则不应投产。 即即新新产产品品的的机机会会成成本本小小于于目目前前的的市市场场价价格格时时，应应投投产否则不应投产。产否则不应投产。 在企业生产过程中，经常有新情况发生，造成原本在企业生产过程中，经常有新情况发生，造成原本不紧缺的某种资源变成为紧缺资源，对生产计划造成不紧缺的某种资源变成为紧缺资源，对生产计划造成影响，如水、电和资源的供应不足等，对生产过程提影响，如水、电和资源的供应不足等，对生产过程提出了新约束等。出了新约束等。 对增加新约束条件的分析方法步骤是：对增加新约束条件的分析方法步骤是：五、对增加新约束条件的分析五、对增加新约束条件的分析 第一步：将目前的最优解代入新增加的约束，若能满足约束条件，则说明新增约束对目前的最优解即最优生产方案不构成影响称此约束为不起作用约束），可暂时不考虑新增约束条件。否则转下一步；第第二二步步：把把新新增增约约束束添添加加到到原原问问题题最最终终表表中中，并并作作初初等等行行变变换换，构构成成对对偶偶可可行行的的单单纯纯形形表表，并并用用对对偶偶单单纯纯形形法法迭代，求出新的最优解。迭代，求出新的最优解。例例18 对于生产计划问题例对于生产计划问题例10），设增加电力约束，生），设增加电力约束，生产产1单位甲产品需耗电单位甲产品需耗电3个单位，生产个单位，生产1单位乙产品需耗电单位乙产品需耗电4个单位，且每天供电量不超过个单位，且每天供电量不超过30单位。试分析此时最优解单位。试分析此时最优解的变化情况。的变化情况。 解：将最优解解：将最优解x1=6,x2=4代入约束条件代入约束条件 ， 不满足，说明约束条件起作用。不满足，说明约束条件起作用。将约束条件加入松驰变量，化为等式将约束条件加入松驰变量，化为等式 加入最优单纯形表中。加入最优单纯形表中。C 4 3 0 0 0 CBXBb x1 x2 x3 x4 x5340x2x1x54630 0 1 3/5 -2/5 0 1 0 2/5 3/5 0 3 4 0 0 1 Z36 0 0 -1/5 - 6/5 0在这个表中，由于在这个表中，由于x1,x2是基变量，其系数必须为单位向是基变量，其系数必须为单位向量，因此将量，因此将p1,p2化为单位向量得化为单位向量得:C 4 3 0 0 0 CBXBb x1 x2 x3 x4 x5340x2x1x546-4 0 1 3/5 -2/5 0 1 0 2/5 3/5 0 0 0 -6/5 -1/5 1 Z36 0 0 -1/5 -6/5 0再用对偶单纯形法求得新的最优表如下：再用对偶单纯形法求得新的最优表如下：C 4 3 0 0 0 CBXBb x1 x2 x3 x4 x5340x2x1x3222/310/3 0 1 0 -1/2 1/2 1 0 0 2/3 -1/3 0 0 1 1/6 -5/6 Z106/3 0 0 0 -6/7 -1/6作业作业1.复习：影子价格和灵敏度分析；复习：影子价格和灵敏度分析；2.预习：线性规划进一步讨论预习：线性规划进一步讨论3.书面作业：书面作业：4. P76-79：习题：习题3.11， 3.13，3.15。