一、 （15 分）某棉纺厂生产甲、乙两种布，甲种布每米赢利 5 元，乙种布每米赢利 6 元。两种布 都要经过三个车间（粗纱、细纱、织布） ，每种布每米在各个车间所需工时以及每天各个车间可用 的总工时如下： 车间 甲种布 乙种布 总工时 粗纱 2 1 16 细纱 1 2 16 织布 1 1 10 (1) 试建立使该棉纺厂获得最大盈利的生产计划的数学规划模型。 (2) 用图解法求解以上数学规划模型，并求最大盈利。 解：(1) 设该棉纺厂生产甲种布 1 x米，乙种布 2 x米为使棉纺厂获得最大盈利，建立数学规划 模型如下： 12 12 12 12 12 max56 21 21 s.t. 10 ,0. zxx xx xx xx x x =+ + + + 6 6 (8 分) (2) 最优解为: x*=(4,6); 最大盈利: z*=56. x* Ox1 x2 16 8 8 16 10 10 (15 分) 二、 （10 分）将下列线性规划问题的数学模型化为标准型。 1 min23zxx2=+ s.t. 12 23xx5+ 12 32xx= 6 7 12 45xx+ 第 1 页 1 0, 2 xx无约束 解：令 1122222 ,0,zz xxxxxxx = = = 0 2 5 6 7 12 max233zxxx = + s.t. 1223 233xxxx += 122 322xxx += ， 1224 455xxxx += 12234 ,0xxxx x （12 分） 三、（10 分）用对偶单纯形法求以下线性规划问题。 12 minwxx=+ s.t. 12 24xx+ 12 26xx+ 1 4x 12 ,0x x 解： 12 max zxx= s.t. 123 24xxx+= 124 26xxx+= 15 4xx+= (2 分) 12345 ,0x x x xx j c 1 1 0 0 0 B c 基 b 1 x 2 x 3 x 4 x 5 x 0 4 3 x 0 6 4 x 0 5 x 4 2 1 1 0 0 1 2 0 1 0 1 0 0 0 1 j 1 1 0 0 0 0 1 3 x 1 2 x 3 0 5 x 4 3/2 0 1 -1/2 0 1/2 1 0 -1/2 0 1 0 0 0 1 -1/2 0 0 -1/2 0 第 2 页 -1 1 x 2/3 -1 2 x 8/3 0 5 x 10/3 1 0 -2/3 1/3 0 0 1 1/3 -2/3 0 0 0 2/3 -1/3 1 * 2 810 ( , ) , 3 33 T Xz= （10 分） j 0 0 0 -1/3 -1/3 四、 （10 分）一个最优分配问题的费用矩阵如下，试求最优分配。 29357 61566 947103 25441 96246 C = 解： 2935707135(0)7115 61566504555(0)435 947103614706145(0) 254411433014310 962467402474(0)04 07005(0)7005 503255(0)325 613406134 14200 74114 C = (0) 142(0)0 85(0)05 五、 （10 分）对下面的连通图，请给出最小生成树。 第 3 页 5(4) 3(2) 2(0) 5(5) 6(4) 6(6) 8(6) 4(4) 2(0) 3(3) 2(2) 3(3)v3 v2v1 vt vs v5v4 （第六题） （第五题） 解：最小生成数如图： * ()14w T= （10 分） 六、 （10 分）求容量网络中从 s v到的最大流，图中括弧旁数字为容量，括弧中为流量 t v ij c ij f。 解： 标号算法. 5(4) 3(2) 2(0) 5(5) 6(4) 6(6) 8(6) 4(4) 2(0) 3(3) 2(2) 3(3) (1, V2) (1, V1) (1, V3) (1, V5) (1, V4)(2, Vs) v3 v2v1 v4v5 vs vt 5(5) 3(3) 2(0) 5(5) 6(5) 6(6) 8(7) 4(4) 2(0) 3(2) 2(1) 3(3) (1, Vs) v3 v2v1 v4v5 vs vt 该网络的最大流为 13. （10 分） 七、 （10 分）已知运输问题的产销以及运价表如下，求最优解。 第 4 页 A B C D 产量 X 10 6 7 12 4 Y 16 10 5 9 9 Z 5 4 10 10 4 销量 5 2 4 6 解： (1) 由 Vogel 法求得初始的运输方案如下： (5 分) A B C D 产量 X 1 2 1 4 Y 4 5 9 Z 4 4 销量 5 2 4 6 (2) 对应的检验数表为： A B C D X -1 Y 9 7 Z 3 7 3 有一个负元素，故进行一次闭回路调整，产生新的运输方案如下： A B C D 产量 X 1 2 1 4 Y 3 6 9 Z 4 4 销量 5 2 4 6 新的检验数表为： A B C D X 1 Y 8 6 Z 3 8 4 没有负元素，故该新的运输方案就是最优解 (10 分) 八、 （10 分）简述线性规划问题的解的类型，并说明如何从单纯形表中判断。 第 5 页 解：线性规划问题的解有四种类型：惟一最优解，无穷多最优解，无界解，无可行解 (4 分) 若基变量中有人工变量且不为零，则线性规划问题无可行解 如果存在某个0 j ，又 j P向量的所有分量0 ij a ，这时线性规划存在无界解 当所有变量的检验数都小于等于 0，若有某一非基变量的检验数0 s =，且 s P向量中至少存在 一个元素大于 0，且能找出另一最优解，则有无穷多最优解 若所有非基变量的检验数都小于 0，或在的条件下找不出另一最优解，则线性规划问题有唯 一最优解 (10 分) 九、 （15 分）已知线性规划问题 12 123 12 123 max2 6 s.t.24 ,0 zxxx xxx xx x xx 3 =+ + + (1) 用单纯形法求出最优解。 (2) 若目标函数中变量 1 x的系数 2 变为 1 2c+，为使最优基不变，求 1 c的变化范围。 (3) 增添一个新的约束条件，寻求新的最优解。 13 2xx+ 2 解：(1) 先化成标准型 12345 1234 125 12345 max200 6 s.t.24 ,0 zxxxxx xxxx xxx x xx xx =+ += += 单纯型表如下： Cj 2 -1 1 0 0 CB B XB B b x1x2x3x4x5 1 x36 1 1 1 1 0 0 x54 -1 2 0 0 1 j 1 -2 0 -1 0 2 x16 1 1 1 1 0 0 x510 0 3 1 1 1 j 0 -3 -1 -2 0 最优解：X*=(6,0,0), 最优值为：Z*=12. (5 分) (2) 第 6 页 Cj 1 2c+ -1 1 0 0 CB B XB B b x1x2x3x4x5 1 2c+ x16 1 1 1 1 0 0 x510 0 3 1 1 1 j 0 1 3c 1 1c 0 1 2c 要使最优基不变，则 1 1 1 30 10 20 c c c 1 1c，故有 2 0. (5 分) (3) 等价于 13 2xx+ 1366 22,xxxx+= 2 x110/3 1 2/3 0 2/3 Cj 2 -1 1 0 0 0 CB B XB B b x1x2x3x4x5x6 2 x16 1 1 1 1 0 0 0 x510 0 3 1 1 1 0 0 x6-2 1 0 -2 0 0 1 2 x16 1 1 1 1 0 0 0 x510 0 3 1 1 1 0 0 x6-8 0 -1 -3 -1 0 1 j 0 -3 -1 -2 0 0 1/3 0 x522/3 0 8/3 0 2/3 0 1 1/3 1 x38/3 0 1/3 1 1/3 0 -1/3 j 0 -8/3 0 -5/3 0 -1/3 (5 分) 第 7 页