第二章-对偶理论PPT格式课件下载.ppt

第二章-对偶理论PPT格式课件下载.ppt

《第二章-对偶理论PPT格式课件下载.ppt》由会员分享，可在线阅读，更多相关《第二章-对偶理论PPT格式课件下载.ppt（103页珍藏版）》请在冰点文库上搜索。

,例三、,（原问题）,（对偶问题）,模型对比：

已知P，写出D。

（二）对称形式下对偶问题的一般形式,例一：

写出线性规划问题的对偶问题,解：

首先将原式变形,注意：

以后不强调等式右段项b0，原因在对偶单纯型表中只保证而不保证，故b可以是负数。

（三）非对称形式的原-对偶问题关系,例二：

原问题,混合型对偶问题,例三：

原问题,对偶问题,综上所述，其变换形式归纳如下：

例四、线性规划问题如下：

练习：

235,317,146,224,Maxw=2y1+3y2+5y3,y10,y20,y30,y3y3y3,y2+y2+y2+,y1+y1+y1+,正反,无约束,1-234,0134,2-3-7-4,32-34,MinW=0y1-5y2+2y3,y1,y3,y2,反正,0,0,无约束,0,0,=0,=0,单纯形法计算的矩阵描述,二、对偶问题的基本性质,CBB-1：

单纯形乘子,单纯形法计算的矩阵描述,原问题检验数与对偶问题解的关系,设原问题是maxz=CX;

AX+IXS=b;

X,XS0它的对偶问题是min=Yb;

YA-IYS=C;

Y,YS0则原问题单纯形表的检验数行对应其对偶问题的一个基解，其对应关系如表所示。

YS1是对应原问题中基变量XB的剩余变量，YS2是对应原问题中非基变量XN的剩余变量,YS=（YS1,YS2）T,证:

设B是原问题的一个可行基，于是A=（B,N）；

原问题可以改写为,maxz=CBXB+CNXNBXB+NXN+XS=bXB，XN，XS0相应地对偶问题可表示为min=YbYB-YS1=CB

（1）YN-YS2=CN

（2）Y，YS1,YS20这里YS=（YS1，YS2）T。

当求得原问题的一个解：

XB=B-1b其相应的检验数为CN-CBB-1N与-CBB-1现分析这些检验数与对偶问题的解之间的关系：

令Y=CBB-1，将它代入

（1）式，

（2）式得YS1=0,-YS2=CN-CBB-1N,minZ=-CXs.t.-AX-bX0,1、对称性定理：

对偶问题的对偶是原问题。

maxW=-Ybs.t.YACY0,对偶问题的基本性质,弱对偶定理定理对偶问题（min）的任何可行解Y0，其目标函数值总是不小于原问题（max）任何可行解X0的目标函数值,为了便于讨论，下面不妨总是假设,推论若和分别是问题（P）和（D）的可行解，则是（D）的目标函数最小值的一个下界；

是（P）的目标函数最大值的一个上界。

2、弱对偶性（弱对偶原理）：

设和分别是问题（P）和（D）的可行解，则必有,推论.在一对对偶问题（P）和（D）中，若其中一个问题可行但目标函数无界，则另一个问题不可行；

反之不成立。

这也是对偶问题的无界性。

推论.在一对对偶问题（P）和（D）中，若一个可行（如P），而另一个不可行，（如D），则该可行的问题无界。

例1、,试估计它们目标函数的界，并验证弱对偶性原理。

（P）,解：

（D）,例2、已知,试用对偶理论证明原问题无界。

解：

=（0,0,0）T是P的一个可行解，而D的第一个约束条件不能成立（因为y1,y20）。

因此，对偶问题不可行，由推论可知，原问题无界。

3、最优性若X*和Y*分别是P和D的可行解且CX*=Y*b，则X*.Y*分别是问题P和D的最优解。

例如，在例1中，可找到X*=（0,0,4,4）T，Y*=（1.2，0.2）,则Z=28，W=28.故X*、Y*分别是P和D的最优解。

4、强对偶性（对偶定理）：

若一对对偶问题P和D都有可行解，则它们都有最优解，且目标函数的最优值必相等。

推论若P和D的任意一个有最优解，则另一个也有最优解，且目标函数的最优值相等。

综上所述，一对对偶问题的关系，只能有下面三种情况之一出现：

都有最优解，分别设为X*和Y*，则必有CX*=Y*b；

一个问题无界，则另一个问题无可行解；

两个都无可行解。

5、互补松弛定理：

设X*和Y*分别是问题P和D的可行解，则它们分别是最优解的充要条件是,同时成立,一般而言，我们把某一可行点（如X*和Y*）处的严格不等式约束（包括对变量的非负约束）称为松约束，而把严格等式约束称为紧约束。

所以有如下推论：

设一对对偶问题都有可行解，若原问题的某一约束是某个最优解的松约束，则它的对偶约束一定是其对偶问题最优解的紧约束。

例3、已知,试通过求对偶问题的最优解来求解原问题的最优解。

对偶问题为,用图解法求出：

Y*=（1,3），W=11。

将y*1=1，y*2=3代入对偶约束条件，

（1）

（2）（5）式为紧约束，（3）（4）为松约束。

令原问题的最优解为X*=（x1,x2,x3,x4,x5）T，则根据互补松弛条件，必有x3=x4=0,（1,3）,

（1）,

（2）,（3）,（4）,（5）,又由于y*10，y*20，原问题的约束必为等式，即,此方程组为无穷多解,令x5=0,得到x1=1，x2=2即X*1=（1,2,0,0,0）T为原问题的一个最优解Z*=11,再令x5=2/3，得到x1=5/3，x2=0即X*2=（5/3,0,0,0,2/3）T也是原问题的一个最优解Z*=11,例4、已知原问题的最优解为X*=（0，0，4）T，Z=12。

试求对偶问题的最优解。

（1）,

（2）,（3）,将X*=（0，0，4）T代入原问题中，有下式：

所以，根据互补松弛条件，必有y*1=y*2=0，代入对偶问题（3）式，y3=3。

因此，对偶问题的最优解为Y*=（0，0，3），W=12。

6、对偶问题的解,利用原问题的最优单纯形表和改进单纯形表求解对偶问题的最优解。

.设原问题为：

maxZ=CXAXbX0引入xs，构建初始基变量，然后，用单纯形法求解。

当检验数满足j0，则求得最优解。

此时，xs对应的js为-Y*，故求对偶Y*，只要将最优单纯形表上xs对应的检验数反号即可。

例1、,初始表,最终表,由上表可知：

X*=（50/7,200/7），Z=4100/7对偶问题的最优解：

Y*=（0,32/7,6/7），W=4100/7也就是外加工时的收费标准。

.设原问题：

maxZ=CXAX=bX0此时，矩阵A中没有现成的矩阵I，必须通过加入人工变量来凑一个单位矩阵，再用大M法或两阶段法求解。

如何求Y*，经分析得出如下结论：

B=0最优基变量检验数向量I=CICBB-1初始基变量检验数向量D=CDCBB-1D非基变量检验数向量所以，Y*=CII,例2、,初始表,最终表,所以，X*=（4,1,9），Z=2,y*1=（04）=1/3y*2=（M6）=M（1/3M）=1/3y*3=（M7）=M（2/3M）=2/3Y*=（1/3,1/3,2/3）W=2,初始基变量的检验数4=1/3，6=1/3M,7=2/3M,定义：

在一对P和D中，若P的某个约束条件的右端项常数bi增加一个单位时，所引起的目标函数最优值Z*的改变量y*i称为第i个约束条件的影子价格，又称为边际价格。

三、对偶问题的经济解释影子价格,设：

B是问题P的最优基，由前式可知，Z*=CBB-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*mbmZ*=Z*Z*=y*i,也可以写成：

经济意义：

在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。

即对偶变量yi就是第i个约束条件的影子价格。

也可以理解为目标函数最优值对资源的一阶偏导数（但问题中所有其它数据都保持不变）。

即y*i表示Z*对bi的变化率。

影子价格在管理决策中的作用：

（2）影子价格反映了资源的稀缺性，影子价格越高，则越稀缺。

影子价格市场价格，,影子价格市场价格，,则应买进该资源,则应卖出该资源,

（1）影子价格市场价格,Y1=0,多了32/7,Y2=32/7,多了6/7,Y3=6/7,5.由最优单纯形表求对偶问题最优解标准形式：

Maxz=50x1+100x2s.t.x1+x2+x3=3002x1+x2+x4=400x2+x5=250x1,x2,x3,x4,x50,cBB-1,B=（p1,p2,p4）,B-1,最优解x1=50x2=250x4=50（松弛变量，表示原料A有50个单位的剩余）影子价格y1=50y2=0y3=50,B-1对应的检验数cBB-1。

对偶单纯形法是求解线性规划的另一基本方法。

它是根据对偶原理和单纯形法的原理而设计出来的，因此称为对偶单纯形法。

不要简单理解为是求解对偶问题的单纯形法。

由对偶理论可以知道，对于一个线性规划问题，我们能够通过求解它的对偶问题来找到它的最优解。

四、对偶单纯形法,对偶单纯形法的基本思想对偶单纯形法的基本思想是：

从原规划的一个基本解出发，此基本解不一定可行，但它对应着一个对偶可行解（检验数非正j0），所以也可以说是从一个对偶可行解出发；

然后检验原规划的基本解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解（检验数非正）。

4.对偶单纯形法,对偶单纯形法在什么情况下使用：

应用前提：

有一个基，其对应的基满足:

单纯形表的检验数行全部非正（对偶可行）；

变量取值可有负数（非可行解）。

注：

通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯性表。

4.对偶单纯形法,1.建立初始对偶单纯形表,对应一个基本解,所有检验数均非正,转2；

2.若b0,则得到最优解,停止;

否则,令bk=minbi0则选k行的基变量为出基变量,转33.若所有akj0（j=1,2,n），则原问题无可行解,停止;

否则,若有akj0则选=minj/akjakj0=r/akr那么xr为进基变量,转4；

4.以akr为转轴元,作矩阵行变换使其变为1,该列其他元变为0,转2。

对偶单纯形法求解线性规划问题过程：

例一、用对偶单纯形法求解：

将模型转化为,（-9/-1,-12/-1,-15/-5）,（-30/-9,-45/-14,-15/-1）,（-3/-9,-45/-9,-33/-1）,所以，X*=（2,2,2,0,0,0），Z*=72，原问题Z*=72其对偶问题的最优解为：

Y*=（1/3,3,7/3），W*=72,对偶单纯形法的优点1初始解可以是非可行解，当检验数都为负数时，就可以进行基的变换，这时不需要加入人工变量，因此可以简化计算。

2当变量多于约束条件，对这样的线性规划问题，用对偶单纯形法计算可以减少计算工作量，因此对变量较少，而约束条件很多的线性规划问题，可先将变换成对偶问题，然后用对偶单纯形法求解。

3在灵敏度分析中，有时需要用对偶单纯形法，这样可使问题的处理简化。

对偶纯形法的局限性主要是，对大多数线性规划问题，很难找到一个初始可行基，因而这方法在求解线性规划问题时很少单独应用,练习：

单纯形法和对偶单纯形法步骤,对偶单纯形法的适用范围对偶单纯形法适合于解如下形式的线性规划问题,4.对偶单纯形法,在引入松弛变量化为标准型之后，约束等式两侧同乘-1，能够立即得到检验数全部非正的原规划基本解，可以直接建立初始对偶单纯形表进行求解，非常方便。

五、灵敏度分析,以前讨论线性规划问题时，假定aij，bi，cj都是常数。

但实际上这些系数往往是估计值和预测值。

如市场条件一变，cj值就会变化；

aij往往是因工艺条件的改变而改变；

bi是根据资源投入后的经济效果决定的一种决策选择。

因此提出这样两个问题：

（1）当这些系数有一个或几个发生变化时，已求得的线性规划问题的最优解会有什么变化；

（2）或者这些系数在什么范围内变化时，线性规划问题的最优解或最优基不变。

后一个问题将在第6节参数线性规划中讨论。

线性规划问题中某一个或几个系数发生变化?

显然，当线性规划问题中某一个或几个系数发生变化后，原来已得结果一般会发生变化。

可以用单纯形法从头计算，以便得到新的最优解。

这样做很麻烦，而且也没有必要。

因在单纯形法迭代时，每次运算都和基变量的系数矩阵B有关，因此可以把发生变化的个别系数，经过一定计算后直接填入最终计算表中，并进行检查和分析，可按下表中的几种情况进行处理。

灵敏度分析步骤：

1.将参数的改变通过计算反映到最终单纯形表上,2.检查原问题是否仍为可行解。

3.检查对偶问题是否仍为可行解。

表2-9,4.按表2-9所列情况得出结论或决定继续计算的步骤。

一、目标函数中价值系数cj的变化分析,可以分别就cj是对应的非基变量和基变量两种情况来讨论。

（1）若cj是非基变量xj的系数，这时它在计算表中所对应的检验数是j=cj-CBB-1Pj或当cj变化cj后，要保证最终表中这个检验数仍小于或等于零，即j=cj-CBB-1Pj0那么cj+cjYPj，即cj的值必须小于或等于YPj-cj，才可以满足原最优解条件。

这就可以确定cj的范围了。

例3：

某企业利用三种资源生产两种产品的最优计划问题归结为下列线性规划,已知最优表如下。

（1）确定x2的系数c2的变化范围，使原最优解保持最优；

（2）若c2=6，求新的最优计划。

一、价值系数cj的变化分析,最优单纯形表,4,c2,最优解不变？

4=c2505=52c205/2c25,最优解X*=（35，10，25，0，0）保持不变。

（1）,x1*=45/2，x2*=45/2，x4*=25/2，x3*=x5*=0，z*=495/2,

（2）,二、资源数量变化的分析（b）,资源数量变化是指资源中某系数br发生变化，即br=br+br。

并假设规划问题的其他系数都不变。

这样使最终表中原问题的解相应地变化为XB=B-1（b+b）这里b=（0,，br,0,，0）T。

只要XB0，因最终表中检验数不变，故最优基不变，但最优解的值发生了变化，所以XB为新的最优解。

新的最优解的值可允许变化范围用以下方法确定。

B-1是最终计算表中的最优基的逆,例1：

求下列LP问题,B3=（P2，P3，P6）=,B31=,例4：

对于上例中的线性规划作下列分析：

（1）b3在什么范围内变化，原最优基不变？

（2）若b3=55，求出新的最优解。

二、右端常数bi的变化分析,解得40b350，即当b340，50时，最优基B不变,

（2）当b3=55时,=,对偶单纯形,三、增加一个变量的分析例5：

（续例3）设企业研制了一种新产品，对三种资源的消耗系数列向量以P6表示P6=。

问它的价值系数c6符合什么条件才必须安排它的生产？

设c6=3，新的最优生产计划是什么？

6=c6CBB1P6=c6（0，5，4）=c65/2,四、增加新的约束条件的分析,4x1+2x2+x6=150,X*=（35，10，25，0，0）T,例6:

假设在例3中，还要考虑一个新的资源约束：

4x1+2x2150,4x1+2x2+x6=150,变化：

基变量x1、x2、x3所对应的矩阵不再是单位矩阵。

五、其它变化情况的分析1.cj和bi同时变化的情况,例7:

在例3中，假定c2由4上升为6，b3增加到55，试问最优解将会发生什么变化？

B1=,B=,代替最优表的b列，并把c2改为6,原问题与对偶问题均非可行解，表中第一方程是:

x3+2x45x5=25，两边乘以（-1），得x32x4+5x5=25，再引入人工变量x6：

x32x4+5x5+x6=25以x6为基变量，增添第6列，应用大M法继续求解。

新的最优计划产量为x1*=30，x2*=20，z*=270。

x32x4+5x5+x6=25,2.技术系数aij的变化例8:

在例3中，第一种产品的消耗系数改变为,价值系数不变，求新的最优解。

B1=,