第2章 线性规划的对偶理论与灵敏度分析(2).ppt

《第2章 线性规划的对偶理论与灵敏度分析(2).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二节对偶问题的基本性质一单纯形法计算的矩阵描述对称形式线性规划问题（2.9）加上松驰变量Xs后:初始单纯形表为（假设通过若干次迭代后基变量由XsXB）：项目非基变量基变量XBXNXs0XsbBNIcj-zjCBCN0当迭代若干步基变量为XB时，其单纯形表为：项目基变量非基变量XBXNXsCBXBB-1bIB-1NB-1cj-zj0CN-CBB-1N-CBB-1（1）对应初始单纯形表中的单位矩阵IB-1；（2）初始单纯形表中基变量Xs=bXB=B-1b；（3）初始单纯形表中约束系数矩阵为[A,I]=[B,N

2、,I][B-1A,B-1I]=[B-1B,B-1N,B-1I]=[I,B-1N,B-1]（4）若初始矩阵中变量xj的系数向量为Pj，迭代后为P'j，则有P'j=B-1Pj.（5）当B为最优基时，则有CN-CBB-1N0(2.14)-CBB-10(2.15)因xB的检验数可表示为：CB-CBI=0(1.16)(1.14)~(2.16)可重写为C-CBB-1A0(2.17)-CBB-10(2.18)CBB-1称为单纯形乘子，若Y'=CBB-1，则(2.17)式、(2.18)式可改写为A'YC'Y0(2.

3、19)恰好为对偶问题的可行解。代入对偶问题的目标函数有：w=b'Y=CBB-1b=z。当原问题有最优解时，这时对偶问题为可行解，且目标函数值相同。例3本章例1列出了两个互为对偶的线性规划问题,两者分别加上松弛和剩余变量后项目原问题变量原问题松弛变量x1x2x3x4x5x315/2x17/2x23/200100115/4-15/201/4-1/20-1/43/2cj-zj000-1/4-1/2对偶问题的剩余变量对偶问题的变量y4y5y1y2y3项目对偶问题变量对偶问题剩余变量y1y2y3y4y5y21/4y31/2

4、-4/50015/201-1/41/41/2-3/2cj-zj-15/200-7/2-3/2原问题松弛变量原问题的变量x3x4x5x1x2例：已知某线性规划问题，用单纯形法计算时得到的中间某两步的计算表如下，试将表中空白处数字填上。cj354000CBXBbx1x2x3x4x5x6x2x5x68/314/320/32/3-4/35/31000541/3-2/3-2/3010001cj-zj-1/304-5/300….…..……x2x3x115/41-6/41-2/418/415/41-12/41-10/414/

5、4115/41cj-zj二对偶问题的基本性质由弱对偶性，可得出以下推论（1）原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。（2）如原问题有可行解且目标函数值无界，则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界，则其原问题无可行解。（3）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。例：已知线性规划问题maxz=x1+x2-x1+x2+x32-2

6、x1+x2-x31x1,x2,x30试用对偶理论证明上述线性规划问题无最优解。证：（1）该线性规划问题存在可行解。（2）证明无最优解。其对偶问题为：原问题无可行解3.强对偶性（或称对偶定理）。若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。证：（1）有最优解。根据弱对偶性推论（1），对原问题的目标函数值具有上界，对偶问题的目标函数值具有下界，因此两者均具有最优解。（2）目标函数相等。由本节公式(2.19)和(2.20)知，当原问题为最优解时，其对偶问题的解为可行解，且有z=

7、w，由最优性知，这时两者的解均为最优解。首先看一个例子对偶变量y1=0y2=1/4>0y3=1/2>0x1=7/2x2=3/2最优解对偶变量x1=7/2>0x2=3/2>0最优解y1=0y2=1/4y3=1/2不等号等号等号约束条件等号等号约束条件如果某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之约束条件取严格不等式，则其对应的对偶变量一定为零。4.互补松驰性。在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的以偶变量一

8、定为零。也即：证：由弱对偶性知例：已知线性规划问题minw=2x1+3x2+5x3+2x4+3x5x1+x2+2x3+x4+3x542x1-x2+3x3+x4+x53xj0,j=1,2,…,5已知其对偶问题的最优解为y*1=4/5,y*2=3/5,z=5试用对偶理论找了原问题的最优解。解：先写出它的对偶问题max=z=4y1+3y2y1+2y22①y1-y23②