《对偶单纯刑法》由会员分享，可在线阅读，更多相关《对偶单纯刑法（47页珍藏版）》请在金锄头文库上搜索。
1、变换形式归纳如下：,练习：,min Z= - CX s.t. - AX- b X 0,1、对称性定理：对偶问题的对偶是原问题。,max W = -Yb s.t. YA C Y 0,（二）对偶问题的性质,2、弱对偶原理（弱对偶性）：设 和 分别是问题（P）和（D）的可行解，则必有,推论.若 和 分别是问题（P）和（D）的可行解，则 是（D）的目标函数最小值的一个下界； 是（P）的目标函数最大值的一个上界。,推论在一对对偶问题（P）和（D）中，若其中一个问题可行但目标函数无界，则另一个问题不可行；反之不成立。这也是对偶问题的无界性。,推论在一对对偶问题（P）和（D）中，若一个可行（如P），而另一个
2、不可行，（如D），则该可行的问题无界。,例一、,试估计它们目标函数的界，并验证弱对偶性原理。,（P）,解：,（D）,例二 已知,试用对偶理论证明原问题无界。,解： =（0,0,0）是 P 的一个可行解，而 D 的第一个约束条件不能成立（因为y1 , y2 0)。因此，对偶问题不可行，由推论可知，原问题无界。,例3、已知,显然，这两个问题都无可行解。,3、最优性判别定理： 若 X* 和 Y* 分别是 P 和 D 的可行解且 CX* = Y* b， 则X*. Y*分别是问题 P和D 的最优解。,例如，在例1中，可找到 X*=（0,0,4,4）， Y*=（1.2，0.2）,则Z=28，W=28.故X
3、* .Y*分别是 P和D 的最优解。,4、对偶定理（强对偶性）： 若一对对偶问题 P 和 D 都有可行解，则它们都有最优解，且目标函数的最优值必相等。,推论若 P 和 D 的任意一个有最优解，则另一个也有最优解，且目标函数的最优值相等。,综上所述，一对对偶问题的关系，只能有下面三种情况之一出现： 都有最优解，分别设为X* 和 Y*，则必有CX* =Y*b； 一个问题无界，则另一个问题无可行解； 两个都无可行解。,5、互补松弛定理： 设X*和Y*分别是问题 P 和 D 的可行解，则它们分别是最优解的充要条件是,同时成立,一般而言，我们把某一可行点（如X*和Y* ）处的严格不等式约束（包括对变量的
4、非负约束）称为松约束，而把严格等式约束称为紧约束。所以有如下推论： 设一对对偶问题都有可行解，若原问题的某一约束是某个最优解的松约束，则它的对偶约束一定是其对偶问题最优解的紧约束。,例4、已知,试通过求对偶问题的最优解来求解原问题的最优解。,解：对偶问题为,用图解法求出： Y*=（1 , 3）， W=11。 将y*1=1， y*2=3 代入对偶约束条件， （1）（2）（5）式为紧约束，（3）（4）为松约束。 令原问题的最优解为X* = （x1,x2,x3,x4,x5），则根据互补松弛条件，必有x3 = x4 =0,(1 . 3),（1）,（2）,（3）,（4）,（5）,又由于y*10， y*2
5、 0，原问题的约束必为等式，即,化简为,此方程组为无穷多解,令x5 =0,得到x1=1，x2=2 即X*1 =（1,2,0,0,0）为原问题的 一个最优解，Z=11。 再令 x5 =2/3，得到x1=5/3，x2=0 即X*2 （5/3,0,0,0,2/3） 也是原问题的一个最优解，Z=11。,例5、已知原问题的最优解为X* =（0,0,4），Z=12 试求对偶问题的最优解。,解：,（1）,（2）,（3）,将X* =（0 , 0 , 4）代入原问题中，有下式：,所以，根据互补松弛条件，必有y*1= y*2=0，代入对偶问题 （3）式， y3 =3。因此，对偶问题的最优解为 Y*=（0 , 0
6、, 3），W=12。,6、对偶问题的解,利用原问题的最优单纯形表和改进单纯形表求解对偶问题的最优解。,设原问题为： maxZ=CX AX b X0 引入xs ，构建初始基变量，然后，用单纯形法求解。当检验数满足j0 ，则求得最优解。此时， xs对应的js 为- Y* ，故求对偶Y* ，只要将最优单纯形表上xs 对应的检验数反号即可。,例一,初 始 表,最终表,由上表可知： X*=（50/7 ,200/7），Z=4100/7 对偶问题的最优解： Y*=（0 ,32/7 ,6/7），W=4100/7 也就是外加工时的收费标准。,设原问题： maxZ=CX AX=b X0 此时，矩阵A中没有现成的矩
7、阵I，必须通过加入人工变量来凑一个单位矩阵，再用大M法或两阶段法求解。 如何求Y* ，经分析得出如下结论： B =0 最优基变量检验数向量 I =CI CB B-1 初始基变量检验数向量 D = CD CB B-1D 非基变量检验数向量 所以， Y* = CI I,例二,所以， X*=（4 ,1 , 9），Z = 2, y*1= (0 4 )=1/3 y*2=(M 6 )= M(1/3M)=1/3 y*3 =(M 7 )= M(2/3 M)=2/3 Y*=（1/3,1/3 ,2/3） W = 2,初始基变量的检验数4 =1/3，6 =1/3M, 7 =2/3M,定义：在一对 P 和 D 中，若
8、 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 时（其余右端项不变，也不影响B），,目标函数最优值变为： Z*= y*1b1+ y*2b2+y*I （ bi+1 ）+y*mbm Z*= Z* Z* = y*i,也可以写成： 即y*i 表示Z*对 bi的变化率。,其经济意义是：在其它条件不变的情况下，单位资源变化所引起
9、的目标函数的最优值的变化。即对偶变量yi 就是第 i 个约束条件的影子价格。 也可以理解为目标函数最优值对资源的一阶偏导数（但问题中所有其它数据都保持不变）。,若第i 种资源的单位市场价格为mi ，当yi mi 时，企业愿意购进这种资源，单位纯利为yimi ，则有利可图；如果yi mi ，则企业有偿转让这种资源，可获单位纯利miyi ，否则，企业无利可图，甚至亏损。,多了 32/7,多了 6/7,0,1 2 3 4 5 6 7 8,1 2 3 4 5 6,x2,x1,(4,2),X*=（4, 2 , 0 ,0,0,4）,Y*=（0 , 3/2 ,1/8 ,0）,0,1 2 3 4 5 6 7
10、8,1 2 3 4 5 6,x2,x1,(3,3),少了0.5,0,1 2 3 4 5 6 7 8,1 2 3 4 5 6,x2,x1,(4.25,1.75),少了0.25,0,1 2 3 4 5 6 7 8,1 2 3 4 5 6,x2,x1,(4,2),对偶单纯形法是求解线性规划的另一的基本方法。它是根据对偶原理和单纯形法的原理而设计出来的，因此称为对偶单纯形法。不要简单理解为是求解对偶问题的单纯形法。,由对偶理论可以知道，对于一个线性规划问题，我们能够通过求解它的对偶问题来找到它的最优解。,四、对 偶 单 纯 形 法,也就是说，求解原问题（P）时，可以从（P）的一个基本解（非基可行解）开始，逐步迭代，使目标函数值（Z=Y b= CB B-1b =CX）减少，当迭代到 XB=B-1b0时，即找到了（P）的最优解，这就是对偶单纯形法。,同原始单纯形求法一样，求解对偶问题（D），也可以从（D）的一个基本可行解开始，从一个基本可行解（迭代）到另一个基本可行解，使目标函数值减少。,例一、用对偶单纯形法求解：,解：将模型转化为,所以， X*=（2,2 , 2 , 0 , 0 , 0）， Z* =72， 原问题 Z* =72 其对偶问题的最优解为： Y*= (1/3 , 3 , 7/3)，W*= 72,练习：,五、 灵敏度分析,
