由于还有检验数小于零，所以需调整，调整二： 销地 B1 产地 A1 A2 20 A3 5 A4 销量 25 检验： B2 25 25 B3 20 0 20 B4 10 10 B5 0 20 20 产量 20 30 30 20

从上表可以看出所有的检验数都大于零，即为最优方案

最小运费为：zmin?3?20?5?20?4?10?6?5?3?25?8?0?0?20?0?0?305

P127 4.8 用割平面法求解整数规划问题。

maxz?7x1?9x2??x1?3x2?6a） ?

7x?x?35?12?x,x?0,且为整数?12解：该问题的松弛问题为：

maxz?7x1?9x2??x1?3x2?6??7x1?x2?35?x,x?0?12

则单纯形法求解该松弛问题得最后一单纯形表为：

7 9 0 0 cj? CB XB b x1 x2 x3 x4 9 7 x2 x1 7/2 0 9/2 1 0 1 0 0 7/22 1/22 -1/22 3/22 -28/11 -15/11 Cj?Zj 割平面1为：(3?1/2)?x2?(0?7/22)x3?(0?1/22)x4

171711?x3?x4?x2?3?0?x3?x4?x5? 2222222222从而有 7 9 0 0 0 cj? ?CB XB b x1 x2 x3 x4 x5 9 7 0 x2 x1 x5 7/2 0 9/2 1 -1/2 0 0 3 0 1 0 0 0 1 0 0 0 7/22 1/22 0 0 -1/22 3/22 -7/22 -1/22 1 -28/11 -15/11 0 0 0 1 0 0 1/7 1/7 -1 1 -1/7 -22/7 -8 Cj?Zj 9 7 0 x2 x1 x3 32/7 1 11/7 0 0 Cj?Zj 割平面2为：(4?4/7)?x1?(0?1/7)x4?(?1?6/7)x5

?cj? 416164?x4?x5?x1?x5?4?0?x4?x5?x6? 7777777 9 0 0 0 3 b 3 x1 x2 x3 x4 x5 x6 CB XB x2 x1 x3 x6 9 7 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1/7 1/7 1 0 32/7 1 11/7 0 -4/7 0 0 3 4 1 4 0 1 0 0 0 -1/7 0 -22/7 0 -1/7 -6/7 1 -1 0 0 0 1 0 -8 1 -1 -4 6 -2 0 0 1 1 -7 -7 Cj?Zj 9 7 0 0 x2 x1 x3 x4 Cj?Zj 由上表可知该问题已经达到整数解了，所以该整数解就是原问题的最优解，即x*??4,3?，最优值为zmax?7?4?9?3?55

TP144 5.3 用图解分析法求目标规划模型

min Z = P1 d1-+ P2 d2++ P3（2d3- +1d4-）

c）

s.t.

解:由下图可知，满足目标函数的满意解为图中的A 点。

x1 + x2 + d1- - d1+= 40

x1 + x2 + d2- - d2+= 40+10=50 x1 + d3- - d3+= 24 x2 + d4- - d4+= 30

x1 、x2 、d1+、d1-、d2+、d2- 、d3+、d3- 、d4+、d4- ≥ 0

P170 6.4 求下图中的最小树

解：避圈法为：

得到最小树为：

P171 6.7 用标号法求下图中点v1到各点的最短路。