物流分配规划课件PPT课件(40页)

发布于:2021-06-11 05:29:30

3 物流分配规划
?任务分配问题的数学模型(重点) ?用匈牙利法求解分配问题(自学)

一. 任务分配问题
1.简介
在物流系统中经常面临的一个问题:如何根据有限的资源 (人力、物力、财力等),进行工作任务分配,以达到降低 成本或提高经济效益的目的。如:
? 运输任务的分配问题。有n条航线的运输任务指派给n艘船去完成, 不同的船完成不同的航线其运输成本不同。要求每条船完成一条航 线,并且一条航线只能由一条船去完成。如何分配任务,才能使总 的费用最小?
? 又如:有A、B、C、D四门课程,上课的老师可以从甲、乙、丙、丁 四名老师中选择,不同的老师上不同的课程,其费用是不同的,并 且规定,每人只讲一门课程,每门课程只需要一人讲授。问:如何 安排,才能使总的上课费用最低?
? 这类问题是常见的任务分配问题,也叫指派问题,它的任 务是如何进行合理的任务分配,使总的费用最小。

2. 任务分配问题的数学模型
? 以运输问题的n项任务由n个司机去完成的情况为例:有n个 司机被分配完成n项运输任务,不同的司机完成某一项任务 的费用都不一样。要求每个司机完成其中一项任务,每个 任务只能由一名司机完成,如何分配任务,才能使总的费 用最小?

令:
cij表示第i个司机完成第j项任务的运输成 本(工作成本或工作时间等价值系 数);
xij表示第i个司机去完成第j项任务,其值 为1或0。
? 当其值为1时表示第i个司机被分配去完 成第j项任务;
? 其值为0时,表示第i个司机不被分配去 完成第j项任务。

nn

? ? MinZ ?

c ij x ij

i?1 j?1

n
? s .t . x ij ? 1 j?1

n
? x ij ? 1
i?1
x ij ? 0 或 1

3. 任务分配问题数学模型的求解
? 任务分配问题属于整数规划问题,其变量xij的取值 为整数。(本例为0或1)。
? 任务分配问题可以用一般的整数规划求解方法进 行求解。但是,整数规划问题的求解也是非常困 难的,到目前为止,还缺乏统一的求解方法。
? 本书采用匈牙利法求解任务分配问题。

二. 匈牙利法求解分配问题
? 可以证明,对于分配问题,在其费用矩阵Cij中,各行、各 列均减去一个常数,Cij改变以后的最优解,仍为原问题的 最优解。
? 利用这个性质,通过对Cij的行、列进行加减常数的计算, 把一些矩阵元素变为0,在Cij为0的元素上进行分配,就可 得到原问题的最优解。
? 该方法应用了匈牙利数学家Konig矩阵性质定理,因此这种 方法被称为匈牙利法。

4 其他规划问题
?选址问题 ?货物配装问题 ?物流服务系统中的配置问题

一. 选址问题
简介
? 物流调运规划问题,是一种有固定发点、固定收点和固定 道路的运输规划问题。
? 还有一类运输问题,他的收货点和发货点是待定的,这就 是选址问题。这类问题在物流系统规划中经常遇到。
? 选址问题要考虑多种因素,本节只讨论选址问题中的物流 问题。分为两个问题:
? 单一地址选址方法; ? 图上作业法。

1. 单一地址选址方法
? 单一选址问题:就是从多个候选地址中选取一个最优地址。
(1)问题描述
假设地址候选地点有s个,分别用D1,D2,…,Ds表示;原材料、 燃料、零配件的供应地有m个,分别用A1,A2,…,Am表示, 其供应量分别用P1,P2,…,Pm表示;产品销售地有n个,分别 用B1,B2,…,Bn表示,其销售量分别为Q1,Q2,…,Qn表示。

(2)参数及变量说明 ?设cij为供应地Ai到候选厂址Dj的单位物资运输成本; ?djk为候选厂址Dj到销售地Bk的单位物资运输成本; ?设:选址变量为x=(x1,x2,…,xs),
其中:xj=0或1,1表示在Dj点建厂,0表示不在Dj点建厂。

(3)目标函数及约束条件

从供应点

A

到候选地
i

D

点的
j

运输

费用为:

c ij ? Pi ? x j

所有的供应点到候选地

从候选地

D

到销售地
j

D

的运输费用为:
j

B

的运输费用为:
k

m
? c ij ? Pi ? x j
i?1
d jk ? Q k ? x j

候选地

D

到所有的销售地的运输
j

费用为:

n
? d jk ? Q k ? x j
k ?1

所有供应点、销售点到

D

的运输成本为:
j

m

n

? ? c ij ? Pi ? x j ? d jk ? Q k ? x j

i?1

k ?1

所有候选地的运输成本

sm

n

? ? ? 为:

( c ij ? Pi ? x j ? d jk ? Q k ? x j )

j?1 i?1

k ?1

? 选址问题的数学模型可

以表示为:

sm

n

? ? ? min Z ? ( c ij ? Pi ? d jk ? Q k ) ? x j

j?1 i?1

k ?1

s
s.t. ? x j ? 1 j?1
x j ? 1或 0

(5)求解方法

sm

n

?? ? mZ i? n ( cij?P i? djk?Q k)?xj

j?1 i?1

k?1

? 单一选址问题是一种线性规划问题,并且变量的取值为0或 1,属于整数规划问题。

? 单一地址的选址模型的求解方法比较简单.从目标函数表 达式的右边可以看出:通过计算模型中括号内的算式值, 就能够确定运输成本最小的方案。

? 当要选定的地址不是单一的,而是多个时,问题不再属于 线性规划问题。

2. 图上作业法
对于运输路线不含回路的选址问题,可用图上作业法求解。
例题8 假定有六个矿井.产量分别为5000吨、6000吨、7000吨、2000吨、 4000吨和3000吨,运输路线如图所示,这些矿石要经过加工后才能转运到 其他地方。这些矿井之间道路不含回路,欲选择一个矿井,在此矿井上建 立一个加工厂,使各矿井到工厂的运输总费用最低。
为了便于分析,用一个新的图来代替原图,新图圈内数字表示 矿井编号,产量记在圈的旁边,道路交叉点看作产量为零的矿 井,把那些只有一条道路连接的矿井称为端点。

? 首先计算这些矿井的总产量,本例为27000吨。
? 然后分析各端点,都没有超过总产量的一半,因此把各端点的数量合并 到前一站,即 ① 和 ② 的数量合并到③;把④的数量合并到⑤ ;把⑦ 的数量合并到⑥ ,如下图所示。

3

5

6

11000

9000

7000

? 各端点都合并到前一站后, ③ 和⑥变成了图中的端点。对它们进行分 析,其数量都不超过总产量的一半,所以他们也不是最佳点。

? 再把它们合并到前一站,即把③和⑥的数量合并到⑤ 。则⑤ 的数量为 27000,超过总量的一半,所以⑤是最佳点。

? 结论:加工厂应建在第5号矿井。

二. 货物配装
货物配装的目的是在车辆载重量为额定值的情况下,合理 进行货物的安排,使车辆装载货物的价值最大(如:重量 最大、运费最低等)。

1.装货问题的数学模型

(1)问题描述 设货车的载重量上限为G,用于运送n种不同的货物,货物 的价或重值重量系量分数等别,。为分别W1用,PW1,2,P2.,..,...W,nP,n表每示一,种它货表物示对价应值于、一运个费
(2)数学模型 设Xk表示第k种货物的装入数量,货物配装问题的数学模 型可以表示为:

n
? max f ( x) ? Pk ? X k k ?1

n

? s.t.

Wk ? X k ? G

k ?1

X k ? 0 (k ? 1,..., n)

(3)求解方法
? 可以把装入一件货物作为一个阶段,把装货问题看作动态规划问 题。
? 一般情况下,动态规划问题的求解过程是从最后一个阶段开始由 后向前进行的。
? 由于装入货物的先后次序不影响装货问题的最优解。可以从第一 阶段开始,由前向后逐步进行。
(4)求解过程
1)装入第1种货物X1件,其最大价值为
f1(W )?mP a 1?X x1
其 中 : X1 表 示 第 1 种 货 物 的 装 载 数 量 ; 其 取 值 范 围 : 0<X1< [G/W1] ,方括号表示取整; P1:第1种货物的价值系数(重量、运费、价值等); f1(W):第一种货物的价值。

2)装入第2种货物X2件,其最大价值为
f 2 ( w ) ? m ? P 2 ? X 2 a ? f 1 ( W x ? W 2 X 2 ) ?
其 中 : X2 表 示 第 2 种 货 物 的 装 载 数 量 ; 其 取 值 范 围 : 0<X2< [G/W2] ;
P2:第2种货物的价值系数(重量、运费、价值等); W?W2X2:第一种货物的重量;
f1(W?W2X2):第一种货物的价值。
3)装入第3种货物X3件,其最大价值为
f 3 ( w ) ? m ? P 3 ? X 3 a ? f 2 ( W x ? W 3 X 3 ) ?
其中:X3表示第3种货物的装载数量;其取值范围:0<X3< [G/W3]; P3:第3种货物的价值系数; W?W3X3 : 前两种货物的重量; f2(W?W3X3) :前两种货物的价值。

……
n) 装入第n种货物Xn件,其最大价值为
f n ( w ) ? m ? P n ? X n a ? f n ? 1 ( x W ? W n X n ) ?
其中:Xn表示第n种货物的装载数量; 其取值范围:0<Xn< [G/Wn] ; Pn:第n种货物的价值系数;

(5)货物配装例题求解
例题9 载重量为8t的载*担耸4种机电产品,产品重量分别为 3吨、3吨、4吨、5吨,试问如何配装才能充分利用货车的运载能力?
解: 第一步,按照前面的公式,分成四个阶段计算每一阶段的价值。 计算结果以表格表示如下:

载重量 件数 价值(重量)

载重量

第2种货 物的件数

第1种货 物的重量

价值计算

价值 Max

载重量

第3种货 物的件数

第1、2种货物的重量

价值计算

Max

价值

第二步:寻找最优方案。
? 寻找最优解方案的次序与计算顺序相反,由第4阶段向第1阶 段进行。
? 选择最后一个阶段价值最大的装载情况,逐步向前寻找最优 方案。

载重量

第3种货 物的件数

第1、2种货物的 重量

价值计算

价值

载重量

第2种货 物的件数

第1种货 物的重量

价值计算

价值 Max

最终的最优装载方案为: 第一组:X1=1,X2=0,X3=0,X4=1; 第二组:X1=0,X2=1,X3=0,X4=1; 第三组:X1=0,X2=0,X3=2,X4=0;
以上三组装载方案,都最大限度地发挥了车辆的载重能力, 都是最优方案。

2. 品种混装问题
(1)品种混装问题简介
?在实际的物流过程中,储运仓库(或货运车站)要把客户 所需的零担货物组成整车,运往各地。
?不同客户的货物,要分别在一站或多站卸货。 ?在装货、运输和卸货过程中,为了减少装卸、运输过程
中出现差错,一般要按照品种、形状、颜色、规格、到 达地点,把货物分为若干类,在装车时分别进行处理。 这就是品种混装问题。

(2)品种混装问题描述

? 设装车的货物可以分为1类,2类,…,m类。共有N件待运货物。

其中:第1类货物有N1件,它们的重量分别G11,G12,……,G1N1; 第2类货物有N2件,它们的重量分别为G21,G22,……,G2N2; 第s类货物共有Ns件,它们的重量分别为Gs1,Gs2,……,GsNs; 以此类推,可以看出:

货物总的件数:

m
N ? ? Ns s ?1

s ? 1, 2 ,...., m

其中,Ns:第s类货物的件数; m:货物的种类数; N:货物的总件数;

(3)数学模型

品种混装问题要求同一货车内每类货物至多装入一件,在此假设条件

下,可以建立品种混装问题的数学模型:

设:

?1

Xrs ???0

第r类第 s件货物装入 第r类第 s件货物不装入

m Nr

? ? max G ?

G rs X rs

r ?1 s?1

s .t.

?? m
?? s ? 1

X rs

?1

r ? 1, 2 ,..., m

? ? ?
?

m

?? r ? 1

Nr
G rs X rs
s ?1

?

G0

其中 m:货物的类别数; Nr:第r类货物的件数; Grs:第r类第s件货物的重量; G0:货车载重量的上限。

(4)求解方法 ? 品种混装问题的数学模型属于整数规划问题,可以用单纯形法进行求解 ? 动态规划法
图5-20表示8件货物分为4类的混装网络示意图。在图中同一列的方框表 示同一类货物,方框内的数字(符号)表示货物重量。
上述品种混装问题就是在网络中自右向左寻找一条路线,使路线所经过的 方框中的重量之和达到最大,但又不超过货车的载重量的上限Go。 ? 可以用穷举法求解。 ? 如果将四类货物看作4个阶段,将上述问题化为动态规划问题求解。

(5)求解实例
例题10 货车载重量上限Go=50;第1类货物2件,G11=20,G12=11;第 2类货物1件,G21=13;第3类货物3件,G31=6,G32=11,G33=8;第4 类货物2件,G41=19,G42=17。

20

6

19

13 11

11

17

8

计算过程见表5-31~34,分成四个阶段进行。

可装重量 实装重量 剩余容量

装载情况计算表

第1阶段的可装容量W值对应第2阶 段的剩余容量W-G

可装重量 实装重量 剩余容量

最优解的寻找过程

第1阶段的可装容量W值对应第2阶 段的剩余容量W-G

最后的最优解为:G1=20 G2=0 G3=11 G4=19
G1=20 G2=13 G3=0 G4=17 每组方案的装载量都是50,达到满载,充分利用了货车的装
载能力。

三. 物流服务系统中的配置问题
? 随机服务系统
? 物流服务系统由服务的机构和顾客组成。 ? 物流服务系统是一个综合服务系统,许多服务项目具有随机性质。
如:装卸系统、运输系统。 ? 物流服务系统中的顾客(人、货物等)到来的时间和服务时间随不
同的时机和条件而变化,这种变化具有随机性质,这类系统称为随 机服务系统。 ? 随机服务系统包含三个过程:顾客输入、排队、服务三个过程。 ? 排队论是处理随机服务系统的专门理论。
? 服务系统中的设备配置
? 服务机构越大,顾客越方便,但机构过大,导致成本升高或浪费。 ? 服务机构过小,便不能完全满足顾客的需要,使服务质量降低,导
致信誉损失和顾客流失。 ? 合理配置服务系统,使他既能满足顾客的需要,又能使系统的花费
最为经济,是物流系统配置所关心的主要问题。

本章重点
? 物流调运规划
?表上作业法确定产、销地之间的供需联系和数量最优搭 配
?图上作业法进行运输线路的选择 ?最短路径与最大流量
? 分配规划 ? 选址问题 ? 货物配装

?

1、这世上,没有谁活得比谁容易 ,只是 有人在 呼天抢 地,有 人在默 默努力 。

?

2、当热诚变成*惯,恐惧和忧虑 即无处 容身。 缺乏热 诚的人 也没有 明确的 目标。 热诚使 想象的 轮子转 动。一 个人缺 乏热诚 就象汽 车没有 汽油。 善于安 排玩乐 和工作 ,两者 保持热 诚,就 是最快 乐的人 。热诚 使*凡 的话题 变得生 动。

?

3、起点低怕什么,大不了加倍努 力。人 生就像 一场马 拉松比 赛,拼 的不是 起点, 而是坚 持的耐 力和成 长的速 度。只 要努力 不止, 进步也 会不止 。

?

4、如果你不相信努力和时光,那 么时光 第一个 就会辜 负你。 不要去 否定你 的过去 ,也不 要用你 的过去 牵扯你 的未来 。不是 因为有 希望才 去努力 ,而是 努力了 ,才能 看到希 望。

?

5、人生每天都要笑,生活的下一 秒发生 什么, 我们谁 也不知 道。所 以,放 下心里 的纠结 ,放下 脑中的 烦恼, 放下生 活的不 愉快, 活在当 下。人 生喜怒 哀乐, 百般形 态,不 如在心 里全部 淡然处 之,轻 轻一笑 ,让心 更自在 ,生命 更恒久 。积极 者相信 只有推 动自己 才能推 动世界 ,只 要推动 自己就 能推动 世界。

?

6、人性本善,纯如清溪流水凝露 莹烁。 欲望与 情绪如 风沙袭 扰,把 原本如 天空旷 蔚蓝的 心蒙蔽 。但我 知道, 每个人 的心灵 深处, 不管乌 云密布 还是阴 淤苍茫 ,但依 然有一 道彩虹 ,亮丽 于心中 某处。

?

7、每个人的心里,都藏着一个了 不起的 自己, 只要你 不颓废 ,不消 极,一 直悄悄 酝酿着 乐观, 培养着 豁达, 坚持着 善良, 只要在 路上, 就没有 到达不 了的远 方!

?

8、不要活在别人眼中,更不要活 在别人 嘴中。 世界不 会因为 你的抱 怨不满 而为你 改变, 你能做 到的只 有改变 你自己 !

?

9、欲戴王冠,必承其重。哪有什 么好命 天赐, 不都是 一路披 荆斩棘 才换来 的。

?

10、放手如拔牙。牙被拔掉的那 一刻, 你会觉 得解脱 。但舌 头总会 不由自 主地往 那个空 空的牙 洞里舔 ,一天 数次。 不痛了 不代表 你能完 全无视 ,留下 的那个 空缺永 远都在 ,偶尔 甚至会 异常挂 念。适 应是需 要时间 的,但 牙总是 要拔, 因为太 痛,所 以终归 还是要 放手, 随它去 。

?

11、这个世界其实很公*,你想 要比别 人强, 你就必 须去做 别人不 想做的 事,你 想要过 更好的 生活, 你就必 须去承 受更多 的困难 ,承受 别人不 能承受 的压力 。

?

12、逆境给人宝贵的磨炼机会。 只有经 得起环 境考验 的人, 才能算 是真正 的强者 。自古 以来的 伟人, 大多是 抱着不 屈不挠 的精神 ,从逆 境中挣 扎奋斗 过来的 。

?

13、不同的人生,有不同的幸福 。去发 现你所 拥有幸 运,少 抱怨上 苍的不 公,把 握属于 自己的 幸福。 你,我 ,我们 大家都 可以经 历幸福 的人生 。

?

14、给自己一份坚强,擦干眼泪 ;给自 己一份 自信, 不卑不 亢;给 自己一 份洒脱 ,悠然 前行。 轻轻品 ,静静 藏。为 了看阳 光,我 来到这 世上; 为了与 阳光同 行,我 笑对忧 伤。

?

15、总不能流血就喊痛,怕黑就 开灯, 想念就 联系, 疲惫就 放空, 被孤立 就讨好 ,脆弱 就想家 ,不要 被现在 而蒙蔽 双眼, 终究是 要长大 ,最漆 黑的那 段路终 要自己 走完。

?

16、在路上,我们生命得到了肯 定,一 路上, 我们有 失败也 有成功 ,有泪 水也有 感动, 有曲折 也有坦 途,有 机遇也 有梦想 。一路 走来, 我们熟 悉了陌 生的世 界,我 们熟悉 了陌生 的面孔 ,遇人 无数, 匆匆又 匆匆, 有些成 了我们 忘不掉 的背影 ,有些 成了我 们一生 的风景 。我笑 ,便面 如春花 ,定是 能感动 人的, 任他是 谁。

?

17、努力是一种生活态度,与年 龄无关 。所以 ,无论 什么时 候,千 万不可 放纵自 己,给 自己找 懒散和 拖延的 借口, 对自己 严格一 点儿, 时间长 了,努 力便成 为一种 心理* 惯,一 种生活 方式!

?

18、自己想要的东西,要么奋力 直追, 要么干 脆放弃 。别总 是逢人 就喋喋 不休的 表决心 或者哀 怨不断 ,做别 人茶余 饭后的 笑点。

?

19、即使不能像依米花那样画上 完美的 感叹号 ,但我 们可以 歌咏最 感人的 诗篇; 即使不 能阻挡 暴风雨 的肆虐 ,但我 们可以 左右自 己的心 情;即 使无法 预料失 败的打 击,但 我们可 以把它 当作成 功的一 个个驿 站。

?

20、能力配不上野心,是所有烦 扰的根 源。这 个世界 是公* 的,你 要想得 到,就 得学会 付出和 坚持。 每个人 都是通 过自己 的努力 ,去决 定生活 的样子 。

?

1、许多人企求着生活的完美结局 ,殊不 知美根 本不在 结局, 而在于 追求的 过程。

?

2、慢慢的才知道:坚持未必就是 胜利, 放弃未 必就是 认输, 。给自 己一个 迂回的 空间, 学会思 索,学 会等待 ,学会 调整。 人生没 有假设 ,当下 即是全 部。背 不动的 ,放下 了;伤 不起的 ,看淡 了;想 不通的 ,不想 了;恨 不过的 ,抚* 了。

?

3、在比夜更深的地方,一定有比 夜更黑 的眼睛 。

?

4、一切伟大的行动和思想,都有 一个微 不足道 的开始 。

?

5、从来不跌倒不算光彩,每次跌 倒后能 再站起 来,才 是最大 的荣耀 。

?

6、这个世界到处充满着不公*, 我们能 做的不 仅仅是 接受, 还要试 着做一 些反抗 。

?

7、一个最困苦、最卑贱、最为命 运所屈 辱的人 ,只要 还抱有 希望, 便无所 怨惧。

?

8、有些人,因为陪你走的时间长 了,你 便淡然 了,其 实是他 们给你 撑起了 生命的 天空; 有些人 ,分开 了,就 忘了吧 ,残缺 是一种 大美。

?

9、照自己的意思去理解自己,不 要小看 自己, 被别人 的意见 引入歧 途。

?

10、没人能让我输,除非我不想 赢!

?

11、花开不是为了花落,而是为 了开的 更加灿 烂。

?

12、随随便便浪费的时间,再也 不能赢 回来。

?

13、不管从什么时候开始,重要 的是开 始以后 不要停 止;不 管在什 么时候 结束, 重要的 是结束 以后不 要后悔 。

?

14、当你决定坚持一件事情,全 世界都 会为你 让路。

?

15、只有在开水里,茶叶才能展 开生命 浓郁的 香气。

?

16、别想一下造出大海,必须先 由小河 川开始 。

?

17、不要让未来的你,讨厌现在 的自己 ,困惑 谁都有 ,但成 功只配 得上勇 敢的行 动派。

?

18、人生最大的喜悦是每个人都 说你做 不到, 你却完 成它了 !

?

19、如果你真的愿意为自己的梦 想去努 力,最 差的结 果,不 过是大 器晚成 。

?

20、不忘初心,方得始终。

?

21、每个人都有潜在的能量,只 是很容 易:被 *惯所 掩盖, 被时间 所迷离 ,被惰 性所消 磨。

?

22、不论你在什么时候开始,重 要的是 开始之 后就不 要轻言 放弃。

?

23、恨别人,痛苦的却是自己。

?

24、每天醒来,敲醒自己的不是 钟声, 而是梦 想。

?

25、你不能拼爹的时候,你就只 能去拼 命!

?

26、如果人生的旅程上没有* ,人还 有什么 可做的 呢。

?

27、我们无法选择自己的出身, 可是我 们的未 来是自 己去改 变的。 励志名 言:比 别人多 一点执 着,你 就会创 造奇迹

?

28、伟人之所以伟大,是因为他 与别人 共处逆 境时, 别人失 去了信 心,他 却下决 心实现 自己的 目标。

?

29、人生就像一道漫长的阶梯, 任何人 也无法 逆向而 行,只 能在急 促而繁 忙的进 程中, 偶尔转 过头来 ,回望 自己留 下的蹒 跚脚印 。

?

30、时间,带不走真正的朋友; 岁月, 留不住 虚幻的 拥有。 时光转 换,体 会到缘 分善变 ;*淡 无语, 感受了 人情冷 暖。有 心的人 ,不管 你在与 不在, 都会惦 念;无 心的情 ,无论 你好与 不好, 只是漠 然。走 过一段 路,总 能有一 次领悟 ;经历 一些事 ,才能 看清一 些人。

?

31、我们无法选择自己的出身, 可是我 们的未 来是自 己去改 变的。

?

32、命好不如*惯好。养成好* 惯,一 辈子受 用不尽 。

?

33、比别人多一点执着,你就会 创造奇 迹。


相关推荐

最新更新

猜你喜欢