线性规划习题(35)

X3 1 0 0 0 0 1 0 0 0 0

X4 -1 0 -2 1/2 -5/2 －2 1 -4 0 -2

X5 -1/4 1/4 1/2 -1/8 1/8 0 0 1 0 0

X6 0 0 1 0 0 1/2 -1/2 2 1/4 -1/4

X3 1 0 0 0 0 1 0 0 0 0

X4 -1 0 -2 1/2 -3/2 0 0 1 0 0

X5 -1/4 1/4 1/2 -1/8 -1/8 -1/2 1/4 -1/4 0 -1/2

X6 0 0 1 0 0 1 0 -1/2 1/4 -3/4

X4 -1 0 -2 1/2 0 -3/2

X5 -1/4 1/4 1/2 -1/8 0 -1/8

X6 0 0 1 0 0 0

X7 0 0 0 0 1 0

X3 0 0 0 1 -1 -1/4 0 0 X1 4 1 0 0 0 1/4 0 0 X6 4 0 0 0 -2 1/2 1 0 X2 2 0 1 0 1/2 -1/8 0 0 X7 2 0 0 0 －1/2 －3/8 0 1 σj 0 0 0 -3/2 -1/8 0 0 由于 X7＝2 大于 0，所以最优解不变 二、给出线性规划问题（20 分） MinZ=2X1+3X2+ 5X3+ 6X4 X1+ 2X2+3X3+ X4≥2 -2X1+X2- X3 +3X4≤-3 Xj≥0（j=1,…4） 1）写出其对偶问题 2）用图解法求解对偶问题 3）利用 2）的结果及根据对偶问题性质写出原问题的最小值 解： 对偶问题为 Maxw =2y1-3y2 y1-2y2≤2 2y1+y2≤3 3y1-y2≤5 y1+3y2≤6 y1≥0,y2≤0 2)根据图解法得对偶问题最优解为 Y＝(8/5,-1/5) W=19/5 3)原问题和对偶问题如果都有最优解，则他们的最优解目标函数值相等，所以原 问 题 B1 B2 B3 B4 产量/t 的 A1 8 14 17 12 100 最 小 值 ＝ 19/ 5 三、某公司从三个产地 A1，A2，A3 将物品运往四个销售地 B1，B2，B3，B4， 各产地的产量、 各销售地的销量和各产地运往各销售地每件物品的运费如表，问 如何调运，使总运费最小（20 分）

A2 A3 销量/t

5 17 80

8 7 70

13 12 90

15 9 110

100 150

解：初始解为

B1 A1 A2 A3 销量/t 80 80 70 70 90 B2 B3 70 20 80 110 B4 30 产量/t 100 100 150

计算检验数

B1 A1 A2 A3 销量/t －1 0 11 80 B2 4 2 0 70 B3 0 0 －2 90 B4 0 7 0 110 产量/t 100 100 150

由于 X11 和 X33 的检验数小于 0，所以不是最优解，调整得

B1 A1 A2 A3 销量/t 80 80 70 70 20 70 90 10 110 B2 B3 B4 100 产量/t 100 100 150

重新计算检验数

B1 A1 A2 A3 销量/t 1 0 13 80 B2 4 0 0 70 B3 2 0 0 90 B4 0 5 0 110 产量/t 100 100 150

由于所有的检验数都大于等于 0，所以得到最优解。

四、有 4 个工人，要指派他们分别完成 4 项工作，每人做各项工作所消耗的时间 如下表：(20 分) 工作 工人 甲 乙 丙 丁 A 7 6 4 6 B 9 7 8 9 C 17 14 7 12 D 14 6 15 8

问指派哪个人去完成哪项工作，可使总的消耗时间为最小？ 解： 最优解为 X= 0 1 0 0 0 0 0 1 0 0 1 0 1 0 0 0 总消耗时间为 28