结构推理 应用对偶理论证明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之间.
【答案解析】