运筹学清华第四版答案

??3?

0??x3???16?，解得?x3?2?x1?x5/2，目标函数变为z?9?2x1?x5。 ?????4?x?16?4x??1/4?x31?4??4??? ??x5?? ?1010

?4001???0100

此时得到的解为x?(0,3,2,16,0)t，z?9。 由 ?z?x1

?2?0可知，x1取正值可使z增大。 ?x2?3?0 ?x1?2?

若令x1取正值且x5仍为0，由?x3?2?x1?0，可得?，这说明x1最大可以达到2，此 x?4?1?x?16?4x?0 ?41

时x3将变为0，成为非基本变量。

（3）令x1,x2,x4为基变量、x3,x5为非基变量，可得解x?(2,3,0,8,0)t，z?13。 此时z?13?2x3? 14

x5，可知此时应让x5取正值，即进入基变量。 经过类似检查，可知应让x4变成非基变量。

（4）令x1,x2,x5为基变量，x3,x4为非基变量，可得解x?(4,2,0,4,0)t，此时z?14?32x3? 18

x4，达到最优点。

上述过程可以编制表格计算，这就是单纯形法。 z?14。

例1.9 分别用图解法、单纯形法求解例1.8的lp问题，并指出单纯形法迭代的每一步相当于图形上的哪个顶点。 max z?2x1?3x2 ?x1?2x2?x3?8? s.t. ?4x? 1?x4?16

?4x2?x5?12

??xj?0,j?1,2,?,5解：原问题可等价转化为： max z?2x1?3x2?x1?2x2?8? s.t. ?4x1?16 ?

?4x2?12

??xj?0,j?1,2图解如下：

可知，目标函数在b(4, 2)处取得最大值，故原问题的最优解为x*?(4,2)t，目标函数最大值为z*?2*4?3*2?14。 用单纯形法求解原问题时，单纯形表如下：

原问题的最优解为x*?(4,2,0,0,4)t，目标函数最大值为z*?2*4?3*2?14。 单纯形法的寻找路径为：x(1)?(0,0,8,16,12)→x(2)?(0,3,2,16,0)→ x(3)?(2,3,0,8,0) → x(4)?(4,2,0,0,4)

与图解法对照，寻找相当于o(0, 0) → d(0, 3) → c(2, 3) → b(4, 2)。 例1： 用单纯形法求解下述lp问题。 max z?3x1?4x2?2x1?x2?40 ， ?

s.t. ?x1?3x2?30 ?x,x?0?12

解：首先将原问题转化为线性规划的标准型，引入松弛变量x3、x4，可得：

max z?3x1?4x2?2x1?x2?x3?40 ?

s.t. ?x1?3x2?x4?30 ?x,x,x,x?0?1234

构造单纯形表，计算如下：

由此可得，最优解为x*?(18, 4, 0, 0)t，目标函数值为z*?3*18?4*4?70。