运筹学第五、六、七、八章答案
5.2 用元素差额法直接给出表5-53及表5-54下列两个运输问题的近似最优解． 表5-53 B1 B2 B3 B4 B5 Ai A1 19 16 10 21 9 18 A2 14 13 5 24 7 30 A3
25 30 20 11 23 10 A4 7 8 6 10 4 42 Bj 15 25 35 20 5 表5-54 B1 B2 B3 B4
Ai A1 5 3 8 6 16 A2 10 7 12 15 24 A3 17 4 8 9 30 Bj 20 25 10 15 【解】表5-53。Z=824 表5-54 Z=495 5.3 求表5-55及表5-56所示运输问题的最优方案． （1）用闭回路法求检验数（表5-55） 表5-55 B1 B2 B3 B4 Ai A1 10 5 2
3 70 A2 4 3 1 2 80 A3 5 6 4 4 30 bj 60 60 40 20 （2）用位势法求检验数（表5-56） 表5-56 B1 B2 B3 B4 Ai A1 9 15 4 8 10 A2 3 1 7 6 30 A3 2 10
13 4 20 A4 4 5 8 3 43 bj 20 15 50 15 【解】（1） (2) 5.4 求下列运输问题的最优解 （1）C1目标函数求最小值；（2）C2目标函数求最大值 15 45 20 40 60
30 50 40 (3)目标函数最小值,B1的需求为30≤b1≤50, B2的需求为40，B3的需求为20≤b3≤60,A1不可达A4 ，B4的需求为30． 【解】（1） （2） （3）先化为平衡表 B11 B12 B2 B31 B32 B4 ai A1 4 4 9 7 7 M 70 A2 6 6 5 3 3
2 20 A3 8 8 5 9 9 10 50 A4 M 0 M M 0 M 40 bj 30 20 40 20 40 30 180 最优解： 5.5（1）建立数学模型 设xij(I=1,2,3;j=1,2)为甲、乙、丙三种型号的客车每天发往B1，B2两城市的台班数，则 (2)写平衡运价表 将第一、二等式两边同除以40，加入松驰变量x13,x23和x33将不等式化为等式，则平衡表为： B1
第五章 刼 态规刻(Dynamic programming)
研究多阶段决策问题
R.E.Bellman 1951年提出动态规划。 1957年出版Dynamic
Programming
应用：最优调度、资源分配
最优路径、最优控制 设备更新、库存问题
§ 2•多卧段决策问龜
例.
某产品从A城运至F城，其间要经过若干 个城镇和若干条道路，路线结构如图所示, 图中给出了每段道路的运费（元），试选 择一条合理的运输路线，使总运费最小？
分析：力案①：A-Bl-Cl-El-F运费：26元 方案②：A->B3->C3-E3-F
运费:22元 方案③：A->B2->Cl->E2->F 运费:18元
锻优方案：方案③
§ 3•基本概念
1 •阶段和阶段变量 壬尸"〜
阶段：过程的划分，包括时间、空间的划分，
阶段数:n
阶段变量：描述阶段的变量用£表示，&1,2,.•…,n
2 •状态和状态变量
状态：描述过程的必要信息。
状态应具仃无后效性：若给定了某阶段状态，则在这阶 段以后过程的发展不受这阶段以前各阶段状态的影响. 状态变量：描述状态的变量，用s表示。
»:表示第阶段的状态变量
SA :表示第阶段状态变量篠合 Sk e Sk
如 £[ = 4 = S],
52 = B\ e S2 = {B[,82,83}
53 = {C],C2,C3} , S4 = {Ex£"2,E3}
S4+l={F} = F
决策：决定（选择），从一个阶段的状态到 下一个阶段状态的选择。 '
决策变量：描述决策的变量，月U表示. uk=uk（sk）表示第邓介段处于》的决策变量 Dk = Dg表示第郊介段处于时 决策变量的集合心wDg
如 》2（31）= {w2（^l）= G，W2（^I） =
%2（B]） = C] W Z）2（B1）4
•策略
策略：决策按顺序构成的序列，用卩表示。 P“g：第郑介段起至第2阶段止的策略
Pkyn(sk)= {uk (»)，％« + 1(»+1)・・・，知(》)}
运筹学第五、六、七、八章答案
1 2 3 4 5 ai 1 2 3 4 1 M M M 1.15 1.25 M M 1.3 1.4 0.87 M 1.45
1.55 1.02 0.98 0 0 0 0 65 65 65 65 bj 50 40 60 80 30 (3)用表上作业法，最优生产方案如下表： 1 2 3 4 5 ai 1 2 3 4 50 15 25
60 10 5 65 30 65 65 65 65 Bi 50 40 60 80 30 上表说明：一月份生产65台，当月交货50台；二月份交货15台,二月份生产35台，当月交货25台，四月份交货10台；三月份生产65台，当月交货60台，四月份交货5台，4月份生产65台当月交货。最小费用Z=235万元。
5.8 求解以下最小值的指派问题，其中第（2）题某人要作两项工作，其余3人每人做一项工作． （1） 【解】最优解 （2）【解】虚拟一个人，其效率取4人中最好的，构造效率表为 1 2 3 4 5 甲 26
38 41 52 27 乙 25 33 44 59 21 丙 20 30 47 56 25 丁 22 31 45 53
20 戊 20 30 41 52 20 最优解：甲～戊完成工作的顺序为3、5、1、2、4，最优值Z=165 最优分配方案：甲完成第3、4两项工作，乙完成第5项工作，丙完成第1项工作，丁完成第2项工作。
5.9 求解以下最大值的指派问题： （1）【解】最优解 （2）【解】最优解 第5人不安排工作。
表5-58 成绩表(分钟) 游泳 自行车 长跑 登山 甲 20 43 33 29 乙
15 33 28 26 丙 18 42 38 29 丁 19 44 32 27 戊 17 34 30 28 5.10
学校 游泳、自行车、长跑和登山四项接力赛，五名运发动完成各工程的成绩（分钟）如表5-58所示．如何从中选拔一个接力队，使预期的比赛成绩最好． 【解】设xij为第i人参加第j工程的状态，那么数学模型为 接力队最优组合 乙 长跑 丙 游泳 丁 登山 戊 自行车 甲淘汰。预期时间为107分钟。
运筹学第五、六、七、⼋章答案
5.2⽤元素差额法直接给出表5-53及表5-54下列两个运输问题的近似最优解．
表5-53
表5-54
【解】表5-53。
表5-54 Z=495
5.3 求表5-55及表5-56所⽰运输问题的最优⽅案．
（1）⽤闭回路法求检验数（表5-55）表5-55
（2）⽤位势法求检验数（表5-56）
表5-56
【解】（1）
(2)
5.4求下列运输问题的最优解
（1）C1⽬标函数求最⼩值；（2）C2⽬标函数求最⼤值1359250 648525 111312730
C
=??
90
30
60
10
7
8
5
6
9
13
14
20
15
10
7
=
C
15 45 20 40 60 30 50 40
(3)⽬标函数最⼩值,B1的需求为30≤b1≤50, B2的需求为40，B3的需求为20≤b3≤60,A1不可达A4，B4的需求为30．
50
2070109482356794- 【解】（1）
（2）
5.5（1）建⽴数学模型
设x ij (I=1,2,3;j=1,2)为甲、⼄、丙三种型号的客车每天发往B 1，B 2两城市的台班数，则11122122313211213112
2232111211223132max 40(806560505040)404040400404040600
510150(1,2,3;1,2)
ij Z x x x x x x x x x x x x x x x x x x x i j =+++++++=??++=??+≤??
+≤??+≤?≥==??
(2)写平衡运价表
（3）最优调度⽅案：
即甲第天发5辆车到B 1城市，⼄每天发5辆车到B 1城市，5辆车到B 2城市，丙每天发10辆车到B 2城市，多余5辆，最⼤收⼊为Z=40（5×80+5×60+5×50+10×40）=54000（元）5.6（1）设x ij 为第i ⽉⽣产的产品第j ⽉交货的台数，则此⽣产计划问题的数学模型为
111213142144112131411222324213233343142434441112131421222324
