结构推理
应用对偶理论证明LP问题:
(P) max z=3x1+2x2+5x3,
s.t. 2x1+x2+x3≤10,
5x1+3x2+2x3≤18,
x1,x2,x3≥0
有最优解,并求出最优值的一个范围.
【正确答案】作出(P)的对偶问题如下:
(D) min ω=10y1+1By2,
s.t. 2y1+5y2≥3,
y1+3y2≥2,
y1+2y2≥5,
y1,y2≥0.
易知(P)有可行解(0,0,9)T,而(D)有可行解(5,0)T.因为(P)和(D)都有可行解,那么,根据教材[1]中定理2.4知,(P)和(D)都有最优解.上述两个可行解对应的目标函数值分别为
z1=3×0+2×0+5×9=45,
ω1=10×5+18×0=50.
故对问题(P)的最优值z*有如下估计:
45=z1≤z*=ω*≤ω1=50,
即最优值z*在45~50之间.
【答案解析】