运筹与决策PPT：运输问题和指派问题

人类法律，事物有规律，这是不 容忽视 的。— —爱献 生
16、业余生活要有意义，不要越轨。——华盛顿 17、一个人即使已登上顶峰，也仍要自强不息。——罗素·贝克 18、最大的挑战和突破在于用人，而用人最大的突破在于信任人。——马云 19、自己活着，就是为了使别人过得更美好。——雷锋 20、要掌握书，莫被书掌握；要为生而读，莫为读而生。——布尔沃
最短路径、指派、运输问题
36、如果我们国家的法律中只有某种 神灵， 而不是 殚精竭 虑将神 灵揉进 宪法， 总体上 来说， 法律就 会更好 。—— 马克·吐 温 37、纲纪废弃之日，便是暴政兴起之 时。— —威·皮 物特
38、若是没有公众舆论的支持，法律 是丝毫 没有力 量的。 ——菲 力普斯 39、一个判例造出另一个判例，它们 迅速累 聚，进 而变成 法律。 ——朱 尼厄斯

产地
能力
Ⅰ
10.8 10.8+0.15 10.8+2*0.15 10.8+3*0.15 25
Ⅱ
－
11.1 11.1+0.15 11.1+2*0.15 35
Ⅲ
－
－
11
11+0.15
30
Ⅳ
－
－
－
11.3
10
销量
10
15
25
20
100
70
销地 Ⅰ
产地
Ⅰ
10
Ⅱ
－
Ⅲ
－
Ⅳ
－
销量
10
生产与储存方案
Ⅱ
A2 6 4 -1 5
0
Vj 6
4
5
以上所有检验数≤0，故初始方案已是最优方案 不用进行第三步的调整
不平衡运输问题
• 当总供应量≠总需求量时，称为不平衡运输问 题
• 不平衡运输问题的求解：先化为平衡的运输 问题，再用表上作业法
• 供＞求，虚设一个收点，收量为供求之差，各发 点到该虚收点的单位运价为0
运输问题的扩展－－指派问题
现实生活之中，我们也经常遇到指派人员做某 项工作的情况。指派问题的许多应用都用来帮 助管理人员解决如何为一项将要开展进行的工 作指派人员的问题。其他的一些应用如为一项 任务指派机器、设备或者是工厂 。
还有哪些这样的问题呢？
想想看！
实例
有4 个工人,要指派他们分别完成4 项 工作,每人做各项工作所消耗的时间如下 表。要求1人只做1件事，如何指派使总 的消耗时间最少?
• 由于某种原因，不能指派某个人做某件事
• 如A1由于技能不达标，不能做B3，只须在一般模 型中去掉x13变量。

A
BCD
甲 85 92 73 90
效率表 乙 95 87 78 95
丙 82 83 79 90
丁 86 90 80 88
例5-15 人事部门欲安排四人到四个不同的岗位工作， 每个岗位一个人。经考核四人在不同岗位的成绩(百 分制)如下表所示，问如何安排他们的工作使总成绩 最好。
➢这个问题的求解可以采用枚举法。将所有分配方案 求出，总分最大的方案就是最优解。本例的方案有 4×3×2×1 = 24 种。
(0) 6 17 17 (0) 6 17 17
x22 x32
x23 x33
x24 x34
1 1
x41 x42 x43 x44 1
A 甲 x11 乙 x21
丙 x31 丁 x41
1
BCD 1 x12 x13 x14 1 x22 x23 x24 1 x32 x33 x34 1 x42 x43 x44
111
x11 x21 x31 x41 1
27 0 45 45
27
0
40
40
27
0
40
40
由于最少直线数 3 m 4 ，因此修改矩阵：
(1)从矩阵未被直线覆盖的数字中找出一个最小数5, 并且减去5； (2)直线相交处的元素加上5，被直线覆盖而没有相交 的元素不变。
重复步骤3，直到最少直线数=4。
3.用最少的直线覆盖所有0，最少直线数= 4。
第五章 运输与指派问题
5.1 运输问题的数学模型及其特征 5.2 运输单纯形法 5.3 运输模型的应用 5.4 指派问题
5.4 指派问题
指派问题也称为分配或配置问题。是资源合理配 置或最优匹配问题。
5.4.1 数学模型
例5-15 人事部门欲安排四人到四个不同的岗位工作， 每个岗位一个人。经考核四人在不同岗位的成绩(百 分制)如下表所示，问如何安排他们的工作使总成绩 最好。

a1 a2
am
18
设xk（ =0或1）表示第k个中转站启用次数，xik表示从第i个仓库运到第k个中转站的 物资数量，ykj表示从第k个中转站运到第j个单位的物资数量，则
p
mp
pn
z f k x k
d ik x ik
e kj y kj
k 1
i1 k 1
k 1 j1
p
x ik a i
… … … …… …
Am cm1 cm2 … cmn am
Am+1 0
0 … 0 am+1
销量 b1 b2 … bn
mn
minz
cij xij
n
i1
xij ai
j1
i 1, 2,..., m
j1
s.t. m xij bj j 1, 2,..., n
i1
xij 0 i 1, 2,..., m; j 1, 2,..., n
mn
minz
cij xij
n
i1 j1
xij ai
i 1, 2,..., m
s.t.
j 1 m
xij
bj
j 1, 2,..., n
i1
xij 0 i 1, 2,..., m; j 1, 2,..., n
若用表上作业法求之,可设一个假想销地, 使其销
量为bn+1=∑ai-∑bj,ci,n+1=0.
已知该厂的生产能力与生产成本如下表。若生产出的产品当季不交货，则需
储存、维护等费用1500元。要求在完成合同的情况下，做出全年生产费用最
小的决策。
生产能力与生产成本
季度
1 2 3 4
生产的能力（台）