管理运筹学第二章-1.ppt
第二章线性规划的对偶问题
与灵敏度分析;A
B
C;资源价格问题;LP;资源价格问题;原问题
MaxZ〔X〕=c1x1+c2x2+…+cnxn
a11x1+a12x2+…+a1nxn≤b1
a21x1+a22x2+…+a2nxn≤b2
………………….
am1x1+am2x2+…+amnxn≤bm
x1,x2,…,xn≥0;2.1.3非对称型对偶问题
例:求以下线性规划的对偶问题;MaxZ〔X〕=2x2-5x3
x1+x3≥2
2x1+x2+6x3≤6
x1-x2+3x3=0
x1,x2,x3≥0;2.1.3非对称型对偶问题
例:求以下线性规划的对偶问题;对应关系可归纳成下表:;练习:
MinZ〔X〕=x1+2x2+x3
x1+x2+x3≤2
x1-x2+x3=1
2x1+x2+x3≥1
x1≥0;一般情形:混合型对偶问题的对应关系;〔P〕与(D)的关系对应表:;练习:;2.1.4对偶问题的根本性质
以对称型为例
设原问题〔P〕为其对偶问题〔D〕为
maxZ〔X〕=CXminW(Y)=Yb
AX≤bYA≥C
X≥0Y≥0;对偶问题为:
MinW(y〕=b1y1+b2y2+…+bmym
a11y1+a21y2+…+am1ym≥c1
a12y1+a22y2+…+am2ym≥c2
…………..
a1ny1+a2ny2+…+amnym≥cn
y1,y2,…,ym≥0;根据条件有:;〔3〕假设X*,Y*分别为问题(P)和问题(D)的可行解,且CX*=Y*b
;那么,X*和Y*分别为问题(P)和问题(D)的最优解。;〔5〕对偶定理:假设问题(P)和问题〔D〕之一有最优解,那么
另一个问题也一定有最优解,且目标函数值相等。;2.1.5对偶问题的解
由对偶定理可知,从原问题的最终单纯表中
可直接得到其对偶问题的最优解。;X*=(45/2,45/2,0,25/2,0)
Y*=〔7/2,0,1/2,0,0〕;假设将资源价格问题作为原问题求解〔两阶段法〕,;假设将资源价格问题作为原问题求解〔两阶段法〕,;例:求以下线性规划的解
MaxZ〔X〕=4x1+3x2
x1≤6
x2≤8
x1+x2≤7
3x1+x2≤15
-x2≤1
x1,x2≥0;[