最新对偶理论教学讲义ppt课件.ppt

《最新对偶理论教学讲义ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、对偶理论2.1对偶理论一、对偶问题的提出二、原问题和对偶问题的变换规则三、对偶问题的性质2016/3/232《运筹学》Ⅰ史慧萍一、对偶问题的提出解：设x1为每周生产产品Ⅰ的数量；x2为每周生产产品Ⅱ的数量。线性规划模型为生产线1时间限制生产线2时间限制生产线3时间限制2016/3/233《运筹学》Ⅰ史慧萍原问题与对偶问题的标准形式比较2016/3/237《运筹学》Ⅰ史慧萍原问题与对偶问题的标准形式的比较xjyix1x2….xn原关系minwy1y2…yma11a12…a1na21a22…a2n…………am1am2…amn≤≤…≤b1b2…bm对偶关系≥≥…≥Maxz=minwmaxzc1

2、c2….cn2016/3/238《运筹学》Ⅰ史慧萍二、线性规划的原问题和对偶问题的变换规则原问题(或对偶问题)对偶问题(或原问题)目标函数maxz目标函数minw变量n个n个约束条件≥0≥≤0≤无约束＝约束条件m个m个变量≤≥0≥≤0＝无约束约束条件右端项目标函数变量的系数目标函数变量的系数约束条件右端项2016/3/239《运筹学》Ⅰ史慧萍例：写出下面线性规划的对偶规划2016/3/2310《运筹学》Ⅰ史慧萍解：该线性规划有3个变量→3个约束条件：x1、x2变量≥0→第1、2约束条件≥,x3变量无约束→第3约束条件＝,约束条件3个→3个变量：第1约束条件≥→第1变量≤0,第2约束条件≤

3、→第2变量≥0,第3约束条件＝→第3无约束变量。2016/3/2311《运筹学》Ⅰ史慧萍三、线性规划对偶问题的基本性质（理论）(7个)1)对称性一个线性规划的对偶问题的对偶问题恰是原问题。2)弱对偶性假定X是原规划(P)的任一可行解，Y是对偶规划(D)的任一可行解，则有CTX≤bTY3)无界性若原问题(对偶问题)为无界解，则其对偶问题(原问题)无可行解(逆命题不成立)。4)可行解是最优解的性质（最优性）设X是原问题的可行解，Y是对偶问题的可行解。当CTX＝bTY时，则X、Y皆为最优解。2016/3/2312《运筹学》Ⅰ史慧萍5)强对偶性（对偶定理）原规划有最优解，则对偶规划也有最优解，且

4、它们的最优解的最优值相同。可以证明，(P)和(D)的解一般说来共有下述三种情况：①两个问题都有有限最优解；②两个问题都无可行解；③一个问题有无界解，另一问题无可行解。2016/3/2313《运筹学》Ⅰ史慧萍2016/3/2314《运筹学》Ⅰ史慧萍对偶约束对于问题P与问题D，我们可以在其各有的m+n个约束条件中建立对偶关系：ailxl+ai2x2+…+ainxn≤bi与yi≥0(i＝1，2，…，m)称为一对对偶约束。xj≥0与aljy1+a2jy2+…+amjym≥cj(j＝1，2，…，n)也称为一对对偶约束。称某个约束条件是紧约束，如果每个最优解都能使这个约束取等号。不是紧约束的约束是松

5、约束。2016/3/2315《运筹学》Ⅰ史慧萍原问题与对偶问题的对偶约束2016/3/2316《运筹学》Ⅰ史慧萍原问题与对偶问题的对偶约束maxz＝5x1+x2-3x32x1+2x2－x3≥1x1－3x2+4x3≤102x1+2x2+x3＝5x1≥0x2≥0x3无约束minw＝y1+10y2+5y32y1+y2+2y3≥52y1－3y2+2y3≥1－y1+4y2+y3＝－3y1≤0y2≥0y3无约束。2016/3/2317《运筹学》Ⅰ史慧萍6)互补松弛性在线性规划问题的最优解中，若对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；另一方面，如果约束条件取严格不等式，则其对应的对

6、偶变量一定为零。设xj*(j=1,…,n),yi*(i=1,…,m)为线性规划问题的最优解。若yi*＞0，则有ailxl*+ai2x2*+…+ainxn*＝bi，即xsi*＝0若ailxl*+ai2x2*+…+ainxn*＜bi，即xsi*＞0,则有yi*＝0（将互补松弛性应用其对偶问题时类似可得：若xj*＞0，则有aljyl*+a2jy2*+…+amjym*＝cj，若aljyl*+a2jy2*+…+amjym*＞cj，则xj*=0。）方程(最终单纯形表)BV系数右边zx1x2x3x4x5z＋(3/2)x4＋2x5＝36z10003/2136x3+(1/3)x4－(1/3)x5＝2x30

7、0011/3-1/32x2＋(1/2)x4＝6x200101/2063x1－(1/3)x4＋(1/3)x5＝2x10100-1/31/32第i个方程的松弛变量2016/3/2318《运筹学》Ⅰ史慧萍互补松弛性：y1*＝0y2*＝3/2y3*＝1x1<42x2=123x1+2x2=18x1<4x2=6x1=22016/3/2319《运筹学》Ⅰ史慧萍7)检验数原问题单纯形表中的检验数对应对偶问题的一个基本解(由基产生的解，但不满足非负约