课程

1 1 x1 x2 Cj —Zj 3/2 10/3 1 0 0 0 1 0 7/16 7/8 —21/16 —9/32 7/16 —5/32 因而最优解为（因为Z=0<=Z <=

31029，，0,0）T ，Z = 23629=Z，将原问题分解为两个子问题： 6max z = x1+x2 951x1+ x2<=

14141—2x1+ x2<=

3x1<=1 x1，x2>=0

710得最优解x1=1，x2=，z1=

33max z = x1+x2 951x1+ x2<=

14141—2x1+ x2<=

3x1>=2 x2>=0

2341得最优解x1=2，x2=，z2=

9941由此判定可取Z=0<=Z<==Z

9再分解B1为两支B3和B4：

max z = 3x1+2x2

951x1+ x2<=

14141—2x1+ x2<=

30<=x1<=1 0<=x2<=1 517得最优解x1= x2= 2 z3=

66max z = 3x1+2x2

951x1+ x2<=

14141—2x1+ x2<=

3x1<=1 x2>=3

无可行解，故剪去B4分支。 再分解B2为两支B5和B6：

max z = 3x1+2x2

951x1+ x2<=

14141—2x1+ x2<=

3x1<=1 0<=x2<=2

得最优解x1=2，x2=2，z5=4为整数解，由此判定可取Z=4<=Z<=

41=Z 9max z = 3x1+2x2

951x1+ x2<=

14141—2x1+ x2<=

3x1>=2 x2>=3

无可行解，故剪去B6分支。

因为Z3< Z =4，故剪去B3分支。从而可以断定X1 =2，X2 =2为最优解，Z =4 。

P（154）6.8 解0-1规划 （1） min z=4x1+3x2+2x3

2x1-5x2+3x3<=4 4x1+x2+3x3>=3 x2+x3>=1 x1，x2，x3=0或1

先找到（0，0，1）T为可行解，相应的Z=2，故增加约束条件

4x1+3x2+2x3<=2 (x1,x2,x3) 条件 是否满足 Z 条件 (0) (1) (2) (3) (0，0，0) (0，0，1) (0，1，0) (0，1，1) 0 2 3 5 0 3 0 3 3 × √ × × 2 (1，0，0) (1，0，1) (1，1，1) (1，1，1) 4 6 7 9 × × × × 所以，可判断最优解X =（0，0，1）T，目标函数最优解Z =2 。 P（154）6.9 有4 个工人，在指派他们分别完成4种工作，每天做各种工作所消耗的时间如图所示，问指派哪个人去完成哪种工作，可使总的消耗时间为最

小？ 工人 工种 A 甲 乙 丙 丁 15 19 26 19 B 18 23 17 21 C 21 22 17 23 D 24 18 19 17 解：本题考查的是指派问题，用匈奴利法求解。 变换系数矩阵为

15 18 21 24 15 0 3 6 9 29 23 22 18 18 1 5 4 0

min (Cij)= 26 17 16 19 16 10 1 0 3 =

19 21 23 17 17 2 4 6 0

再进行试分配，得 ◎ 2 6 9 1 4 4 ◎ 10 ◎ Ф 3 2 3 6 Φ

因为m = 3 < n = 4，试指派不成功转下步，所以

指派成功，故此项工作有多种指派方案，Z = 70，指派矩阵如下：

1 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 1

即最优指派方案为：

（1） 甲→A，乙→D，丙→C，丁→B； （2） 甲→B，乙→A，丙→C，丁→D。

P（198）7.3 计算从A到B、C和D的最短路线。已知各段路线的长度如图所示。

解：本题是最短路线问题，使得动态规划逆序解法求解

求从A到B、C和D的最短路线等价于求从B、C和D到A的最短路线。 设阶段变量k=1，2，3，4，依次表示4个阶段选路的过程，第1阶段从B、C到D出发到B3、C3或D3，第2阶段从B3、C3或D3出发到B2、C2或D2，第3阶段从B2、C2或D2出发到B1、C1或D1，第4阶段从B1、C1或D1出

发到A；

状态变量Sk表示k阶段初可能处的位置； 决策Xk表示k阶段初可能选择的路线；

阶段指标Vk表示k阶段与所选择的路线相应的路长；

指标函数Vk4=?Vi 表示k至4阶段的总路长；

i?k4递推公式：fk=min{Vk+ fk+1}，k=4，3，2，1；f5 =0。

k 4 Sk B1 C1 D1 3 B2 C2 Xk A A A B1 C1 B1 C1 D1 D2 C1 D1 Vk 3 8 7 4 2 3 8 7 4 6 Vkn=Vk+fk+1 3+0 8+0 7+0 4+3 2+8 3+3 8+8 7+7 4+8 6+7 12 C1 fk 3 8 7 7 6 Xk A A A B1 B1