运筹学（清华大学第三版）习题集

求解下述LP问题

max z?2x1?3x2?x1?2x2?x3?8? ?4x1?x4?16s.. t??4x2?x5?12?xj?0,j?1,2,,5?解：依据单纯形理论，有以下计算：

（1）令x3,x4,x5为基变量、x1,x2为非基变量，可得

?x1????x3?8?x1?2x2?12100??x2??8??40010??x???16?， 解得?x?16?4x，代入目标函数，得z?0?2x1?3x2。 ?41???3????x?12?4x?2?04001???x4???12???5??x5??此时得到的解为X?(0,0,8,16,12)T，z?0。 由

?z?z?2?0、?3?0可知，x1,x2取正值可使z增大。 ?x1?x2?x3?8?2x2?0?x2?4?若令x2取正值且x1仍为0，由?x4?16?0，可得?，这说明x2最大可以达到3，此

x?3?2?x?12?4x?02?5时x5将变为0，成为非变量。

（2）令x2,x3,x4为基变量、x1,x5为非基变量，可得

?x1????x2?3?x5/4?1010?1/2??x2??2??4001??x???16?，解得?x?2?x?x/2，目标函数变为z?9?2x?3x。 0?31515???3???4?x?16?4x??01001/4???x4???3??1?4??x5??此时得到的解为X?(0,3,2,16,0)T，z?9。 由

?z?2?0可知，x1取正值可使z增大。 ?x1?x2?3?0?x?2?若令x1取正值且x5仍为0，由?x3?2?x1?0，可得?1，这说明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?2x13?4x5，可知此时应让x5取正值，即进入基变量。

经过类似检查，可知应让x4变成非基变量。

（4）令x1,x2,x5为基变量，x3,x4为非基变量，可得解X?(4,2,0,4,0)T，此时z?14?312x3?8x4，达到最优点。

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

z?14。

例1.9 分别用图解法、单纯形法求解例1.8的LP问题，并指出单纯形法迭代的每一步相当于图形上的哪个顶点。

max z?2x1?3x2?x1?2x?2?x3?8s.. t??4x1?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。

用单纯形法求解原问题时，单纯形表如下：

cj 2 3 0 0 0 cB 0 0 0 XB b 8 16 12 x1 1 4 0 2 x2 2 0 [4] 3 0 0 1 0 0 0 1 0 0 0 1 0 x3 1 0 0 0 1 0 0 0 1 －4 0 －2 0 －2 1/2 －3/2 x4 0 1 0 0 0 1 0 0 0 1 0 0 1/4 1/2 －1/8 －1/8 x5 0 0 1 0 －1/2 0 1/4 －3/4 －1/2 [2] 1/4 1/4 0 1 0 0 ?i x3 x4 x5 4 － 3 2 4 － － 4 12 ?j 0 0 3 x3 x4 x2 2 16 3 [1] 4 0 2 ?j 2 0 3 x1 x4 x2 2 8 3 1 0 0 0 ?j 2 0 3 x1 x5 x2 4 4 2 1 0 0 0 ?j 原问题的最优解为X*?(4,2,0,0,4)T，目标函数最大值为z*?2*4?3*2?14。

(1)(2)单纯形法的寻找路径为：X?(0,0,8,16,12)→X?(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构造单纯形表，计算如下：

cj 3 4 0 0 cB 0 0 XB b 40 30 x1 2 1 3 x2 1 [3] 4 0 1 0 0 1 0 x3 1 0 0 1 0 0 3/5 -1/5 -1 x4 0 1 0 -1/3 1/3 -4/3 -1/5 2/5 -1 ?i 40 10 18 30 x3 x4 ?j 0 4 x3 x2 30 10 [5/3] 1/3 5/3 ?j 3 4 x1 x2 18 4 1 0 0 ?j 由此可得，最优解为X*?(18, 4, 0, 0)T，目标函数值为z*?3*18?4*4?70。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库运筹学（清华大学第三版）习题集在线全文阅读。