运筹学清华大学第三版习题集.doc

1、求解下述 LP 问题 1231425max 86. 0,jzxstx解：依据单纯形理论，有以下计算：（1）令 为基变量、 为非基变量，可得345,12,x， 解得 ，代入目标函数，得 。1234520864x3124586x 1203zx此时得到的解为 ， 。(0,81,2)TX0z由 、 可知， 取正值可使 z 增大。12zx23zx12,x若令 取正值且 仍为 0，由 ，可得 ，这说明 最大可以达到 3，2132458061x243x2x此时 将变为 0，成为非变量。5x（2）令 为基变量、 为非基变量，可得234, 15,x，解得 ，目标函数变为 。2345101/46/x25314/2

2、6xx 153924zx此时得到的解为 ， 。(0,21,)TX9z由 可知， 取正值可使 z 增大。12zx1x若令 取正值且 仍为 0，由 ，可得 ，这说明 最大可以达到 2，1x5x231406x124x1x此时 将变为 0，成为非基本变量。3（3）令 为基变量、 为非基变量，可得解 ， 。124,x35,x(2,308)TX13z此时 ，可知此时应让 取正值，即进入基变量。35z5经过类似检查，可知应让 变成非基变量。4x（4）令 为基变量， 为非基变量，可得解 ， 。125,x34, (4,20)TX14z此时 ，达到最优点。348zx上述过程可以编制表格计算，这就是单纯形法。例 1

3、.9 分别用图解法、单纯形法求解例 1.8 的 LP 问题，并指出单纯形法迭代的每一步相当于图形上的哪个顶点。 1231425max 86. 0,jzxstx解：原问题可等价转化为： 1212ma 3846. 0,jzxstx图解如下：可知，目标函数在 B(4, 2)处取得最大值，故原问题的最优解为 ，目*(4,2)TX标函数最大值为 。*2431z用单纯形法求解原问题时，单纯形表如下：jc2 3 0 0 0BBXb1x23x45xi0 3x8 1 2 1 0 0 40 416 4 0 0 1 0 0 5x12 0 4 0 0 1 3j2 3 0 0 00 3x2 1 0 1 0 1/2 20

4、 416 4 0 0 1 0 43 2x3 0 1 0 0 1/4 j2 0 0 0 3/42 1x2 1 0 1 0 1/2 0 48 0 0 4 1 2 43 2x3 0 1 0 0 1/4 12j0 0 2 0 1/42 1x4 1 0 0 1/4 00 54 0 0 2 1/2 13 2x2 0 1 1/2 1/8 0j0 0 3/2 1/8 0原问题的最优解为 ，目标函数最大值为 。*(4,)TX*2431z单纯形法的寻找路径为： (1)0,86,12)(2)0,16,)X (3)2,08)X(4)4X与图解法对照，寻找相当于 O(0, 0) D(0, 3) C(2, 3) B(4,

5、 2)。例 1： 用单纯形法求解下述 LP 问题。， 1212max 340. ,zxst解：首先将原问题转化为线性规划的标准型，引入松弛变量 、 ，可得：3x4123124max z0. ,xst构造单纯形表，计算如下： jc3 4 0 0BBXb1x23x4i0 3x40 2 1 1 0 400 430 1 3 0 1 10j3 4 0 00 3x30 5/3 0 1 -1/3 184 210 1/3 1 0 1/3 30j5/3 0 0 -4/33 1x18 1 0 3/5 -1/54 24 0 1 -1/5 2/5j0 0 -1 -1由此可得，最优解为 ，目标函数值为 。*(18, )

6、TX*318470z例 2：用单纯形法求解下述 LP 问题。1212max .53. 0,zxst解：引入松弛变量 、 ，化为标准形式：3x4123124ma .5. 0,zstx构造单纯形表，计算如下： jc2.5 1 0 0BBXb1x23x4i0 3x15 3 5 1 0 50 410 5 2 0 1 2j2.5 1 0 00 3x9 0 19/5 1 3/5 45/192.5 12 1 2/5 0 1/5 5j0 0 0 1/21 2x45/19 0 1 5/19 3/192.5 120/19 1 0 2/19 5/19j0 0 0 1/2由单纯形表，可得两个最优解 、(1)2,9)T

7、X，所以两点之间的所有解都是最优解，即最优解集(2)0/19,45,TX合为： ，其中 。()(2)0例 2b 用单纯形法求解下述线性规划 123123max 804.,zxstx解：引入松弛变量 、 和 ，列单纯形表计算如下：45x6jc1 2 3 0 0 0BXbxx45x6i0 4x8 2 1 8 1 0 0 10 54 1 3 10 0 1 0 1/30 6x8 1 1 4 0 0 1j1 2 3 0 0 00 4x24/5 -14/5 17/5 0 1 -4/5 03 32/5 1/10 -3/10 1 0 1/10 0 40 6x48/5 7/5 -11/5 0 0 2/5 1 4

8、8/7j7/10 -11/10 0 0 -3/10 00 4x16 0 -5 28 1 2 01 14 1 -3 10 0 1 00 6x4 0 2 -14 0 -1 1j0 1 -7 0 -1 00 4x26 0 0 -7 1 -1/2 5/21 110 1 0 -11 0 -1/2 3/22 2x2 0 1 -7 0 -1/2 1/2j0 0 0 0 -1/2 -1/2故，原问题的最优解为 ， ，其*333(1,27,6,)TXxx*6z中 。30x例 3：用单纯形法求解下述 LP 问题。123124min z0. ,xst解：构造单纯形表计算如下： jc3 4 0 0BBXb1x23x4

9、i0 3x40 2 1 1 0 400 430 1 3 0 1 10j3 4 0 00 3x30 5/3 0 1 1/3 184 210 1/3 1 0 1/3 30j5/3 0 0 4/33 1x18 1 0 3/5 1/54 24 0 1 1/5 2/5j0 0 1 1故，最优解为 ，目标函数值为 。*(18, 4)TX*384*70z例 4：某个求解最大值的线性规划问题用单纯形法计算时得到下表：BcBXb1x23x45x63xf 2 c 1 0 e 042 -1 5 0 1 1 06x3 a 3 0 0 4 1jb d 0 0 3 0其中，a, b, c, d, e, f 是未知数，原问题中要求各变量为非负。问 a, b, c, d, e, f 满足什么条件时，有下面各解成立？（1）不是基可行解；（2）是唯一最优解；（3）有无穷多最优解；（4）是退化的基本可行解；（5）无界解；（6）是可行解但非最优解，只有 可以进基且出基变量必为第 3 个基变量。1x解：（1）f=0, b=0, b=0, d=0, b=0, d0, c=0, b0, d3/a