运筹学：C9影子价格及对偶单纯形法

1、运筹学线性规划与目标规划第二章 对偶问题与灵敏度分析上节内容回顾上节内容回顾大约变，小相反，实例参考定价与生产！大约变，小相反，实例参考定价与生产！(P) max . .0zCXAXbstX(D) min . .0YbYACs tY本节内容摘要本节内容摘要1 对称性对称性 ：对偶问题的对偶是原问题。：对偶问题的对偶是原问题。2 弱对偶性：弱对偶性： CX YbYb3 无界性无界性若原问题若原问题(对偶问题对偶问题)为无界解，则其对偶问题为无界解，则其对偶问题(原问题原问题)无可行解。无可行解。4 可行解是最优解的性质可行解是最优解的性质 若若X、Y为可行解，则当为可行解，则当CX=Yb时可得时

2、可得X、Y为最优解。为最优解。5 对偶定理对偶定理若原问题有最优解，则对偶问题也有最优解，且目标函若原问题有最优解，则对偶问题也有最优解，且目标函数值相等。数值相等。设设X为原问题的最优解，它对应的基矩阵为原问题的最优解，它对应的基矩阵B必存在必存在10BCC B A1BYC B0Y YAC10BC BBXNXSX1B BI1BBCC BB1B N1NBCC B N11B IB10BC B I1Bb1BCBby1 yi ym ym+1 ym+j yn+m x1 xj xn xn+1xn+ixn+m xjym+j=0yixn+i=0(i=1,2,m; j=1,2,n)在一对变量中，其中一个大于0

3、，另一个一定等于06 互补松弛定理互补松弛定理*0*0ssYXY X*XY，为最优解6. 互补松弛定理互补松弛定理,XYCXYb因为 、 是最优解，所以即 ()(),ssYA Y I XY AXIX ,0,ssssY XY XY X Y X故有-。而 (P) (D)( ) () 0ssXYXYPDY XY X若 与 分别是、 的可行解，则 和 是、最优解的充要条件是。(P) (D) ,ssAXIXb YA Y IC证：将、 的约束化为等式： 0ssY XY X故只有。 （自证）。7 7 原问题单纯形表的检验数行对应其对偶问题的一个基解原问题单纯形表的检验数行对应其对偶问题的一个基解该性质是该性

4、质是对偶单纯形法对偶单纯形法的一个基础。的一个基础。BXNXSX1SY2SYY1NBCC B N1BC Bmax ,0BBNNBNSBNSzC XC XBXNXXbXXX1212min , , ,0SBSNSSYbYBYCYNYCY YY12123123123max221,0zxxxxxxxxxxx试用对偶理论试用对偶理论证明左边线性证明左边线性规划问题无最规划问题无最优解。优解。123451234512345min235232342330,1,.,5jxxxxxxxxxxxxxxxxj*124/5,3/5,5yyz本节内容摘要本节内容摘要定义：定义：在一对在一对 P 和和 D 中，若中，若

5、P 的某个的某个 约束条件的右端项常约束条件的右端项常数数 bi 增加一个单位时，所引起的目标函数最优值增加一个单位时，所引起的目标函数最优值 Z* 的改变量的改变量 yi* 称为第称为第 i 个约束条件的个约束条件的影子价格影子价格()，又称为，又称为边际价格边际价格(Marginal Prices)。 若若x*, y* 分别为（分别为（LP）和（）和（DP）的最优解，那么，）的最优解，那么， cx* = y*b 。根据。根据Z *= y*b = b1y1*+b2y2*+bmym*可知可知 Z/ bi = yi*。其中。其中 yi* 表示表示bi 变化变化1个单位对目标个单位对目标Z 产生的

6、影响，称产生的影响，称 yi* 为为bi 的影子价格。的影子价格。影子价格反映了不同的局部或个影子价格反映了不同的局部或个体的增量可以获得不同的整体经济效体的增量可以获得不同的整体经济效益。如果为了扩大生产能力，考虑增益。如果为了扩大生产能力，考虑增加设备，就应该从影子价格高的设备加设备，就应该从影子价格高的设备入手。这样可以用较少的局部努力，入手。这样可以用较少的局部努力，获得较大的整体效益。获得较大的整体效益。2）影子价格表明资源增加对总效益产）影子价格表明资源增加对总效益产生的影响。生的影响。需要指出，影子价格不是固定不变的，需要指出，影子价格不是固定不变的，当约束条件、产品利润等发生变

7、化时，有当约束条件、产品利润等发生变化时，有可能使影子价格发生变化。可能使影子价格发生变化。 另外，影子价格的经济含义（另外，影子价格的经济含义（2 2），是），是指资源在一定范围内增加时的情况，当某指资源在一定范围内增加时的情况，当某种资源的增加超过了这个种资源的增加超过了这个“一定的范围一定的范围”时，总利润的增加量则不是按照影子价格时，总利润的增加量则不是按照影子价格给出的数值线性地增加。这个问题还将在给出的数值线性地增加。这个问题还将在灵敏度分析一节中讨论。灵敏度分析一节中讨论。本节内容摘要本节内容摘要对偶单纯形法的基本思想对偶单纯形法的基本思想 从原规划的一个从原规划的一个基本解基本

8、解出发，此基本解不一出发，此基本解不一定可行，定可行，由性质由性质7 7知知，它的检验数行对应着一个，它的检验数行对应着一个对偶基本解，对偶基本解， 如果这个对偶解是可行的（检验数非正），如果这个对偶解是可行的（检验数非正），就从这个对偶可行解出发进行迭代；就从这个对偶可行解出发进行迭代； 然后检验原规划的基本解是否可行，即是否然后检验原规划的基本解是否可行，即是否有负的分量，有负的分量，如果有负的分量，则进行迭代，求如果有负的分量，则进行迭代，求另一个基本解另一个基本解，此基本解对应着另一个对偶可行，此基本解对应着另一个对偶可行解（检验数非正）。解（检验数非正）。如果得到的基本解的分量皆如果

9、得到的基本解的分量皆非负则该基本解为最优解。非负则该基本解为最优解。对偶单纯形法在迭代过程中始终对偶单纯形法在迭代过程中始终保持对偶解的保持对偶解的可行性（即检验数非正），可行性（即检验数非正），使原规划的基本解使原规划的基本解由不可行逐步变为可行，当得到对偶规划与原由不可行逐步变为可行，当得到对偶规划与原规划的可行解时，便同时得到原规划的最优解。规划的可行解时，便同时得到原规划的最优解。对偶单纯形法在什么情况下使用对偶单纯形法在什么情况下使用: :有一个有一个解，其对应的基解，其对应的基满足满足: : 单纯形表的检验数行全部非正（对偶可行单纯形表的检验数行全部非正（对偶可行解）；解）； 变量

10、取值可有负数（非可行解）。变量取值可有负数（非可行解）。注：注：对偶单纯形法是对偶单纯形法是 通过矩阵行变换运算，通过矩阵行变换运算，使所有相应变量取值均为非负数使所有相应变量取值均为非负数, , 即得到即得到最优单纯最优单纯形表。形表。123123123123min23423234,0 xxxxxxxxxxxx123671234612357max234 2 32 3 40,1,.,7jxxxMxMxxxxxxxxxxxxj 1231234123512345max234 2 32 3 4,0 xxxxxxxxxxxx x x x x BxBCb1x2x3x4x5xjjcz5x4xjc BxBC

11、b1x2x3x4x5xjjcz5x4xjc 11min|0iiiB bB bmin|0jjljjljczaaBxBCb1x2x3x4x5xjjcz4x1xBxBCb1x2x3x4x5xjjcz1x2x11 2*(,0)5 5X8 1*( , )5 5Y 1.建立初始对偶单纯形表建立初始对偶单纯形表,对应一个基本解对应一个基本解,所有检验数所有检验数均非正均非正,转转2；2.若若b0,则得到最优解则得到最优解,停止停止; 否则否则,Min(B-1b)i| (B-1b) i 0= (B-1b)l,则选第则选第l行的基变量行的基变量xl为为出基变量出基变量（最小）（最小）,转转3；3.若所有若所有a

12、lj0(j = 1,2,n )，则原问题无可行解，则原问题无可行解,停止停止;否否则则,若有若有alj0,则选则选 = min j/aljalj0= k/alk （最小）（最小） 那么那么xk为进基变量为进基变量,转转4；4.以以alk为转轴元为转轴元,作矩阵行变换使其变为作矩阵行变换使其变为1,该列其他元变该列其他元变为为0,转转2。对偶单纯形法求解线性规划问题的过程：对偶单纯形法适合解如下形式的线性规划问题对偶单纯形法适合解如下形式的线性规划问题njxmibxacxcfjnjijijnjjjj, 2 , 1, 0, 2 , 10min11对偶单纯形法的适用范围对偶单纯形法的适用范围在引入松弛变量化为标准型之后，约束等式在引入松弛变量化为标准型之后，约束等式两侧同乘两侧同乘-1，能够立即得到检验数全部非正，能够立即得到检验数全部非正的原规划基本解，可以直接建立初始对偶单的原规划基本解，可以直接建立初始对偶单纯形表进行求解，非常方便。纯形表进行求解，非常方便。对于有些线性规划模型，如果在开始求解时不能对于有些线性规划模型，如果在开始求解时不能很快使所有检验数非正，最好还是采用单纯形法求很快使所有检验数非正，最好还是采用单纯形法求解。因为，这样可以免去为使检验数全部非正而作解。因为，这样可以免去为使检验数全部非正而作的许多工作。从这个意