线性规划习题(19)

解：假设增加一个人戊完成各项工作的时间取 A、B、C、D、E 最小值。 得效率矩阵为：

A B 甲 ?25 乙 ?39 ? 丙 ?34 ? 丁 ?24 戊 ?24 ? 29 38 27 42 27

C

D

E

31 42 37 ? 26 20 33 ? ? 28 40 32 ? ? 36 23 45 ? 26 20 32 ? ?

各行减最小值，各列减最小值：得

A B

C

D

E

甲 ? 0 4 5 17 7 ? 乙 ?19 18 5 0 8 ? ? ? 丙 ? 7 0 ? 13 ? ? ? ? 丁 ? 1 19 12 ? 17 ? 戊? 4 7 5 ? 7 ? ? ?

变换得

A B

C

D

E

甲 ? 0 4 5 18 7 ? 乙 ?18 17 4 0 7 ? ? ? 丙 ? 7 0 ? 14 ? ? ? ? 丁 ? ? 18 11 ? 16 ? 戊? 3 6 4 ? 6 ? ? ?

进一步

A B

C

D

E

甲 ? 0 0 1 18 3 ? 乙 ?18 13 0 0 3 ? ? ? 丙 ?11 0 0 18 0 ? ? ? 丁 ? 0 14 7 0 12 ? 戊? 3 2 0 0 2 ? ? ?

最有指派方案

A B C 甲 ?0 乙 ?0 ? 丙 ?0 ? 丁 ?1 戊 ?0 ?

D E

1 0 0 0? 0 0 1 0? ? 0 0 0 1? ? 0 0 0 0? 0 1 0 0? ?

甲——B，乙——C,D，丙——E，丁——A 最低费用＝29＋26＋20＋32＋24＝131 六、 某公司打算将 3 千万元资金用于改造扩建所属的 3 个工厂， 每个工厂的利润增长额与所 分配的投资有关。 各工厂在获得不同的投资额时所能增加的利润如下表所示， 问应如何分配 资金，使公司总的利润为最大（15 分） 利润 工厂 1 2 3 投资 0 0 0 0 1 千万 2.5 3 2 2 千万 4 5 6 3 千万 10 8.5 9

解：K 为阶段变量，k=1,2,3 Sk:第 k 阶段所剩的资金数 Xk：第 k 阶段分配给第 k 个工厂的资金数 gk（xk） ：将 xk 分配给第 k 个工厂的效益 状态转移方程：Sk+1= Sk-xk 递推关系：

? f k ( s k ) ? max {g k ( x k ) ? f k ?1 ( s k ? x k )} 0? xk ? sk ? ? ? f n ( s n ) ? max g n ( x n ) xn ? sn ?

第三阶段，k=3

k ? n ? 1, ? ,1

X3=s3

f 3 ( s 3) ? max g 3 ( x3 )

x3 ? s 3

x3 s3 0 1 2 3 0 0 2 1

g3(x3) 2 3

f3(s3)

x*3

0 2 6 9 6 9

0 1 2 3

第二阶段： s3=s2-x2， 0?s2?3， 0?x2?s2

f 2 ( s 2 ) ? max {g 2 ( x 2 ) ? f 3 ( s 2 ? x 2 )}

0? x 2? s2

x2 s2 0 0 1 2 3

第三阶段 S1=3 S2=s1-x1, 0?x1?s1

f 2 ( s 2 ) ? max {g 2 ( x 2 ) ? f 3 ( s 2 ? x 2 )}

0 ? x2 ? s 2

f2(s2)

x*2

1

2

3 0 0 1 0 0,1

0+0 0+2 0+6 0+9 3+0 3+2 3+6 5+0 5+2 8.5+0

2 6 9

x1 s1 0 3

f1 ( s1 ) ? max {g1 ( x1 ) ? f1 ( s1 ? x1 )}