运筹学基础-对偶线性规划(2).ppt

1、线性规划的对偶理论包括以下几个基本定理。,定理1 （对称性定理）,2.2 线性规划的对偶理论,定理2 （弱对偶定理）,即对偶问题的对偶是原问题。,设x和y分别是原问题和对偶问题的可行解，则必有cxyb，即原问题的目标值小于对偶问题的目标值,定理3 （无界性）,若原问题(对偶问题)为无界解，则其对偶问题(原问题)无可行解。,若原（对偶）问题有可行解,对偶（原）问题无可行解，则原（对偶）问题一定无界；,注:此定理可以判定解的情况,定理4 （可行解是最优解的性质）,定理5 （强对偶定理）,设X*是原问题的可行解，Y*是对偶问题的可行解，当CX*=Y*b时， X*与Y*是最优解 。,若原问题有最优解，

2、那么对偶问题也有最优解，且目标函数值相等,综合上述结论得原问题与对偶问题的解的关系,一般是：cxyb,原问题与对偶问题解的对应关系,由原问题与对偶问题的解的关系可以判定线性规划的解。,Min w = 2y1 +y2 S.t. y1 2y2 1 y1 + y2 1 y1 y2 0 y1,y2 0,应用如上关系求解线性规划问题,试用对偶理论证明上述规划问题无最优解。,由第一约束条件可知对偶问题无可行解，则原问题的解无界或无可行解， 由于原问题存在可行解，所以解无界。,解 该问题存在可行解，如X=(0，0，0)；,其对偶问题为：,对偶问题无可行解,定理6（互补松弛定理）,在线性规划问题的最优解中，如

3、果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。,注：证明过程参见教材59页性质5证明,讨论:,互补松弛定理也称松紧定理，它描述了线性规划达到最优时，原问题（或对偶问题）的变量取值和对偶问题（或原问题）约束松紧之间的对应关系。 当线性规划问题达到最优时，我们不仅同时得到了原问题和对偶问题的最优解，而且也还得到了变量和约束之间的一种对应关系。互补松弛定理即揭示了这一点。,1.如果原问题的某一约束为紧约束（严格等式:松弛变量为零），该约束对应的对偶变量应大于或等于零；,2.如果原问题的某一约束为松约束（严格不等式:松弛变量大于

4、零），则对应的对偶变量必为零；,3.如果原问题的某一变量大于零该变量对应的对偶约束必为紧约束(严格等式)；,4.如果原问题的某一变量等于零，该变量对应的对偶约束可能是紧约束(严格等式)，也可能是松约束(严格不等式)。,线性规划达到最优时的关系,22,1/5 3,17/55,7/5 2,3=3,解：写出对偶问题为： Max Z = 4y1 + 3y S.t. y1 + 2y2 2 y1 y2 3 2y1 +3y2 5 y1 + y2 2 3y1 +y2 3 y1,y2 0,又例:应用如上关系求解线性规划问题,已知对偶问题的最优解为 y1 = 4/5, y2 = 3/5, 试应用对偶理论求解原问题

5、。,x2 = 0,x3 = 0,x4 = 0,等号,又因y1,y2 0，故原问题的两个约束必为紧约束，即,解得：x1 = x5 = 1。,maxZ=5=minS=5,得原问题的最优解X*=(1,0,0,0,1) minS=5,Max.Z=2x1+4x2+x3+x4 s.t. x1+3x2 +x48 2x1+x2 6 x2 + x3 +x46 x1 + x2 +x3 9 xj0（j=1,2,3,4）,附 练习答案：y1=4/5, y2=3/5, y3=1, y4=0,已知原问题的最优解为:X*=(2,2,4,0)T，试根据互补松弛定理解出其对偶问题的最优解。,线性规划问题的对偶问题为： Min.

6、Z=8y1+6y2+6y3+9y4 s.t. y1+2y2 +y4 2 3y1+y2 + y3 +y4 4 y3 +y4 1 y1 +y3 1 yj0（j=1,2,3,4）,练习：已知线性规划问题为：,为严格不等式，由互补松弛定知，必有y4 = 0；,Max.Z=2x1+4x2+x3+x4 s.t. x1+3x2 +x48 2x1+x2 6 x2 + x3 +x46 x1 + x2 +x3 9 xj0（j=1,2,3,4）, 8=8, 6=6, 6=6, 89,解之，有： y1=4/5, y2=3/5, y3=1，y4 = 0,答案：因为原问题的最优解为:X*=(2,2,4,0)T ：,又因x

7、1, x2 , x30，故对偶问题的前三个约束必为紧约束,线性规划问题的对偶问题为： Min.Z=8y1+6y2+6y3+9y4 s.t. y1+2y2 +y4 2 3y1+y2 + y3 +y4 4 y3 +y4 1 y1 +y3 1 yj0（j=1,2,3,4）,等号,（1）写出对偶问题； （2）已知原问题的最优解为X*=（2，0，1，1）T，求对偶问题的最优解。,已知线性规划问题,定理7,结论：用单纯形法求解线性规划时，迭代的每一步在得到原问题一个基本可行解的同时，其：,线性规划原问题及其对偶问题之间存在一对互补的基解，其中原问题的松驰变量对应对偶问题的变量，对偶问题的剩余变量对应原问题

8、的变量；这些互相对应的变量如果在一个问题的解中是基变量，则在另一问题的解中是非基变量；将这两个解代入各自的目标数中有 z=w。,注：证明过程参见教材60页性质6证明,检验数行的-(cj-zj)值是其对偶问题的一个基本解yi ；,用单纯形法同时求解原问题和对偶问题,原问题是：,maxZ=2x1 +x2 5x2 15 6x1 + 2x2 24 x1 + x2 5 x1 , x2 0,原问题的标准型是：,maxZ=2x1 +x2+0 x3+0 x4 +0 x5 5x2 +x3 =15 6x1 + 2x2 +x4 = 24 x1 + x2 +x5 = 5 xi 0,maxZ=2x1 +x2+0 x3+

9、0 x4 +0 x5 5x2 +x3 =15 6x1 + 2x2 +x4 = 24 x1 + x2 +x5 = 5 xi 0,原问题变量,原问题松驰变量,对偶问题剩余变量 y4、y5,对偶问题变量 y1、y2 、y3,得原问题可行解:X=(0,0,15,24,5)T,对偶问题解:Y*=(0,0,0,-2,-1)T,检验数行的 (cj-zj)值是其对偶问题的一个基本解yi ；,得原问题可行解:X=(4,0,15,0,1)T，此时Z=8,同时得对偶问题基础解:Y*=(0,1/3,0, 0,-1/3)T，W=8,检验数行的-(cj-zj)值是其对偶问题的一个基本解yi ；,变换单纯形表,此时得原问题

10、最优解:X*=(7/2,3/2,15/2,0,0)T，Z*=17/2,原问题变量,原问题松驰变量,对偶问题剩余变量 y4、y5,对偶问题变量 y1、y2 、y3,则对偶问题最优解:Y*=(0,1/4,1/2,0,0)T，S*=17/2,检验数行的-(cj-zj)值是其对偶问题的一个基本解yi ；,又例：用单纯形法同时求解原问题和对偶问题,maxZ= 100 x1 + 80 x2 2 x1+4 x2 80 3 x1+ x2 60 x1, x2 0,将线性规划问题标准化,maxZ= 100 x1 + 80 x2 + 0 x3 + 0 x4 2 x1+4 x2 + x3 = 80 3 x1+ x2

11、+ x4 =60 x1, x2 x3 x4 0,此时得原问题的最优解：X0=(16,12,0,0)T , maxZ=2560,初等变换,2 x1+ 4 x2 + x3 = 80 3 x1+ x2 + x4 =60 -Z+100 x1 + 80 x2 + 0 x3 + 0 x4=0,-Z x1 x2 x3 x4 b,同时得对偶问题的最优解：y1=14,y2 =24,y3 =0,y4 =0,即Y0=(14,24,0,0)T , minS=2560,2.3 对偶单纯形方法,原问题是：,原问题的标准型是：,maxw= -15y1-24y2-5y3 +0y4 +0y5 6y2+y3 - y4 = 2 5

12、y1 +2y2 +y3 - y5 =1 y1 , y2 , y3 , y4 , y5 0,利用单纯形法：,maxw= -15y1-24y2-5y3 +0y4 +0y5-My6-My7 6y2+y3 - y4 +y6 = 2 5y1 +2y2 +y3 - y5 +y7 =1 y1 , y2 , y3 , y4 , y5 , y6 , y7 0,一、 用对偶单纯形方法解线性规划,对偶单纯形方法是使用对偶原理求解原问题解的一种方法，而不是求解对偶问题解的单纯形方法。与对偶单纯形方法相对应，原已有的单纯形方法称原始单纯形方法。,用对偶单纯形方法解下述线性规划问题,原问题是：,原问题的标准型是：,max

13、w= -15y1-24y2-5y3 +0y4 +0y5 6y2+y3 - y4 = 2 5y1 +2y2 +y3 - y5 =1 y1 , y2 , y3 , y4 , y5 0,maxw= -15y1-24y2-5y3 +0y4 +0y5 -6y2 - y3 + y4 = - 2 -5y1 -2y2 -y3 + y5 = - 1 y1 , y2 , y3 , y4 , y5 0,对偶单纯形方法,maxw= -15y1-24y2-5y3 +0y4 +0y5 -6y2 - y3 + y4 = - 2 -5y1 -2y2 -y3 + y5 = - 1 y1 , y2 , y3 , y4 , y5

14、0,最优解:Y*=(0,1/4,1/2,0,0)T，maxw*=-17/2,MinZ=17/2,应用对偶单纯形方法之矩阵法,maxw= -15y1-24y2-5y3 +0y4 +0y5 -6y2 - y3 + y4 = - 2 -5y1 -2y2 -y3 + y5 = - 1 y1 , y2 , y3 , y4 , y5 0,最优解:Y*=(0,1/4,1/2,0,0)T， max w*=-17/2 Min Z=17/2,两种方法的主要区别在于：,而对偶单纯形方法在整个迭代过程中，则是始终保持对偶问题的可行性即 亦即, ，也就是全部检验数0，最后达到全部右边项所有负分量逐步变为全部右边项0,即

15、满足原问题的可行性时为止。,所以,对偶单纯形方法实质就是在保证对偶问题可行的条件下向原问题可行的方向迭代。,原始单纯形方法在整个迭代过程中，始终是保持原问题的可行性，最后达到检验数 即 即maxZ取得最优值时为止。,相当于：直到对偶问题的解可行为止,相当于：即直到原问题的解可行为止,用对偶单纯形方法解下述线性规划问题,原问题是：,原问题的标准型是：,maxZ= -2x1-3x2-4x3 +0 x4 +0 x5 x1+ 2x2+x3 - x4 = 3 2x1 - x2 +3x3 - x5 =4 x1 , x2 , x3 , x4 , x5 0,maxw= -2x1-3x2-4x3 +0 x4 +

16、0 x5 -x1 -2x2 - x3 +x4 = - 3 -2x1 + x2 -3x3 + x5 = - 4 x1 , x2 , x3 , x4 , x5 0,应用对偶单纯形方法之矩阵法,最优解:Y*=(11/5,2/5,0,0,0)T，Maxw =-28/5,maxw= -2x1-3x2-4x3 +0 x4 +0 x5 -x1 -2x2 - x3 +x4 = - 3 -2x1 + x2 -3x3 + x5 = - 4 x1 , x2 , x3 , x4 , x5 0,MinZ* = 28/5,小结：对偶单纯形方法的解题过程一般分为四步,（1）写出与已有的初始基B对应的初始单纯形表。根据模型的

17、标准型，若右边项的数字都为非负，且检验数都为非正，则已得到最优解，计算结束；否则，若右边项中至少有一个负分量，且检验数也仍然非正，则进行如下计算。,（2）确定出基变量。若有： 则以对应的变量 xr为出基变量。,（3）确定入基变量。在单纯形表中观察xr所在行的各系数arj，若所有的arj0，则无可行解，停止计算；否则若存在：,， 则以xk为入基变量。,（4） 以ark为主元按原始单纯形方法的迭代方法进行迭代，得到新的单纯形表。,对偶单纯形方法的显著优点：,（1）初始解可以是不可行解，当检验数都非正时，即可以进行基的变换，这时不需要引进人工变量 ，因此就简化了计算。,（2）对于变量个数多于约束方程个数的线性规划问题，采用对偶单纯形法计算量较少。因此对于变量较少、约束较多的线性规划问题, 可以先将它转化成对偶问题，然后用对偶单纯形方法求解。,2.4 影子价格,从对偶问题的基本性质可以看出，在单纯形法的每步迭代中有目标函数,其中bi原来代表第i种资源的拥有量；现在代表第i种资源的估价。此时的估价不是市场价格，而是根据资源在生产中的贡献而作的估价。此时的定价区别于市场价格称为影子价格。,说明,1、市场价格主要随市场供求变化；而它的影子价格有赖于资源的利用情况。生产任务、结构的改变会影响影子价格。,2、影子价格是一种边际价