产销不平衡的运输问题--运筹学(课堂PPT)

格式：ppt
大小：1.38 MB
文档页数：30

下载文档原格式

韩伯棠管理运筹学第三版-第七章-运输问题分析ppt课件.ppt

B1 B2 B3 产量
A1 6 4 6
200
A2 6 5 5 销量 250 200 200
300 500
650 23
B1 B2 B3
产量
A1

6
4
6
200
A2
6
5
5
销量 250 200 200
300 500
650
解：增
B1 B2 B3
加一个 A1 6 4 6
虚设的 A2 6 5 5
产地运 A3 0 0 0 输费用销量 250 200 200
6
4 6 200
A2
6
5 5 300
销量 150 150 200
B1
B2
B3 产量
A1
x11
x12
x13 200
A2
x21
x22
x23 300
销量 150 150 200
Min f = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23
A1 A2 销量
B1 6 6 150
B2 4 5 150
§2
运输问题的计算机求解
运行管理运筹学计算机软件：
点击运输问题模块
14
在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么
§2
运输问题的计算机求解
点击新建
选择Min
输入3
输入4
点击确定
15
在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么

运筹学运输问题-图文

❖ 建模：设xij为从产地Ai运往销地Bj的物资数量（i=1， …m；j=1，…n。
销地 B1
B2
...
Bn
产量
产地
A1
X11 X12
...
X1n
a1
A2
X21 X22
...
X2n
a2
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Am
Xm1 Xm2
...
Xmn
am
销量
b1
b2
...
bn
则运输问题的数学模型如下：
产销平衡表
销地 B1
B2
...
Bn
产量
产地
A1
a1
A2
a2
.
.
.
.
.
.
Am
am
销量
b1
b2
...
bn
单位运价表
销地
B1
B2
...
Bn
产地
A1
c11
c12
...
c1n
A2
c21
c22
...
c2n
.
.
.
.
.
.
.
.
.
.
.
.
Am
cm1
cm2
...
cmn
❖ 若总产量等于总销量（产销平衡），试确定总运费最省的调运方案。
Table14 检验数表
销地
B1
B2
B3
B4
产地
A1

产销不平衡的运输问题 ppt课件

• “太阳当空照，花儿对我笑，小鸟说早早早……”
2.供不应求的情况，即
m
i1
a
i
＜
n
j1
b
j
与产大于销类似，当销大于产时，可以在产销平衡表中虚设一个产
地Am+1 ，该产地的产量为
am1j n 1bji m1ai
再令虚设产地Am+1到各销地的单位运价Cm+1,j=0,j=1,2…n，则问题
可以转化为一个产销平衡的运输问题。在最优解中，虚设产地Am+1
（2）用位势法计算检验数
如黄表所示：
产销不平衡的运输问题
（4）再用位势法计算检验数如下表所示：
（8）（1）（9）（5）
（-4）（-7）
（5）第二次调整量θ=1，调（6）再用位势法计算检验数如
整后的方案如下表所示：
下表所示：
产销不平衡的运输问题
（8）（8）（7）（2）（-2）
（3）
到销地Bj的运量实际上就是最后分配方案中销地Bj的缺货量。
在产销不平衡问题中，如果某产地不允许将多余物资就地贮存，
或不允许缺货，则要令相应运价Ci,n+1或Cm+1,j=M（M是相当大正数）
例2 设有A1、A2、A3三个产地生产某种物资，其产量分别为5，6，8 吨，B1、
B2、B3三个销地需要该物资，销量分别为4，8，6 吨，又已知各产销地之间的单位运价如下表所列，试确定总运费最少的调运方案。
解：产地总产量为19 吨，
销地总销量为18 吨，产
大于销。故虚设销地B4，令其销量b4=1 吨，运价 Ci4=0，i=1,2,3,则问题变产销不平衡的运输问题成如下运输问题：
（8）（10）

运输问题(运筹学教学)演示课件.ppt

精选课件
2、求检验数--闭回路法: 例1
销地产地
B1 3
B2 11
B3 3
B4
ai
10
注: 1)数字格检验数均为0
A1
④
③
7 2)空格检验数
1
2
A2
③1
9
2
①
8
以某空格为起点，用水平或垂直
4 线往前划，每碰到一个数字格转
1
-1
90。，然后继续前进，直到回到起
7
4
10
5
A3
⑥
③
9 点。根据回路计算该空格对应变
精选课件
用网络优化软件
运费一区1 一区2 二区三区1 三区2 供应量
山西盂县 1.65 1.65 1.7 1.75 1.75 4000
河北临城 1.6 1.6 1.65 1.7
1.7 1500
假想地点 M
0
M
M
0
500
6000 需求量 2700 300 1000 1500 500
6000
精选课件
运输问题的表格表示
需求地
1
供应地
16
28
35
合计 13
2
7 4 9 21
3
5 2 10 9
4
3 7 6 7
合计
25 10 15
精选课件
运输问题线性规划模型
min z = 6x11 + 7x12 + 5x13 + 3x14 + 8x21 + 4x22 + 2x23 + 7x24 + 5x31 + 9x32 +10x33 + 6x34

产销不平衡的运输问题-运筹学 PPT课件

j 1
i 1
就可以作为一个初始基可行解。
运输问题
3、按最小元素法（或伏格尔法）给出的初始基可行解，从每一空格出发可以找出而且仅能找出唯一的闭回路。
4、当所有产地产量和销地销量均为整数值，运输问题的最优解也为整数值。
5、如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数k，最优调运方案将不会发生变化。
0
1n 1n1 1
x x a c2n
0
2n 2n1 2
x x a cmn
0
mn mn1 m
bn bn1
运输问题
例:某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产
量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？
运输问题
解：增加一个虚设的销地运输费用为0
j 1,2, n
运输问题
修改后产大于销平衡问题的数学模型
m n1
min z
cij xij
i 1 j 1
n 1
xij ai , i 1,2, , m
j 1
m
xij
b j , j 1,2, , n, n 1
i 1
xij 0, i 1,2, , m
j 1,2, n, n 1
ci n+1=0 i= 1,2,…,m。于是，这个运输问题就转化成了一个产销平衡的问题。
运输问题
原产大于销平衡问题的数学模型
mn
min z
cij xij
i 1 j 1
n
xij ai , i 1,2, , m
j 1
m
xij
b j , j 1,2, , n

运输问题-课件

Cij表示把物资从产地Ai运到销地Bj的单位运价。同样设Xij表示从产地Ai运到销地Bj的运输量。
《运筹学》
第三章运输问题
Slide 5
则产销平衡的运输问题的线性规划模型如下所示：
运输问题有mn个决策变量，m+n 个约束条件。由于产销平衡条件，只有m+n–1个相互独立，因此，运输问题的基变量只有m+n–1 个。
3、调整改进的闭环回路方法——迭代
若有两个或两个以上的负检验数时，一般选其中最小的负检验数。以(24)格为调入格，以此格为出发点，作一闭环回路。
在闭回路上进行运量调整，使选定空格处的运量尽可能地增加（即取相邻两数字格中较小的）。
运量调整后，必然使某个数字格变成零。把一个变成零的数字格抹去，得新的调运方案。经检验，所有检验数都非负，故达到最优，最优方案总运费最小是85元。
例4．设有三个化肥厂供应四个地区的农用化肥。假定等量的化肥在这些地区使用效果相同。各化肥厂年产量，各地区年需要量及从各化肥厂到各地区运送单位化肥的运价如下表所示，试求出总的运费最节省的化肥调运方案。
《运筹学》
第三章运输问题
Slide 36
三个化肥厂共可供应化肥160吨。问：根据现有三个化肥厂的产量，地区 IV 最高需求是否可以不限？最高需求是多少？ 160－ 30－70－0＝60吨
产销平衡表
《运筹学》
第三章运输问题
Slide 10
43
3
1
6
3
1 找出最小运价为1，先将A2的产品供应给B1，因a2>b1， A2除满足B1的全部需要外，还可多余1吨产品。在(A2,B1)的交叉格处填上3。并将B1列运价划去。
2 在未划去的元素中再找出最小运价2，确定A2多余的1 吨供应B3。在(A2,B3)的交叉格处填上1。并将A2行运价划去 3 在未划去的元素中再找出最小的运价3，这样一步步进行下去，直到运价表上的所有元素划去为止。

运输问题 PPT课件

《运筹学》第三章运输问题 Slide 4
使运输费最小的目标函数为： minz＝6X11+4X12+6X13+6X21+5X22+5X23 Xij>=0 一般运输问题的线性规划的模型：有m个产地生产某种物资，有n个地区需要该类物资。 Al，A2，…，Am表示某种物资的m个产地；Bl，B2，… ，Bn表示某种物资的n个销地；令a1, a2, …, am表示各产地产量， b1, b2, …, bn表示各销地的销量，ai=bj 称为产销平衡。 Cij表示把物资从产地Ai运到销地Bj的单位运价。同样设Xij表示从产地Ai运到销地Bj的运输量。
《运筹学》第三章运输问题 Slide 8
证：记∑ai= ∑bj=Q Xij=aibj/Q就是一个可行解，因为Xij≥0，且满足 ∑Xij=ai, ∑Xij=bj 又因为Cij≥0,Xij≥0,所以目标函数有下界零。因而运输问题一定有最优解。 1、确定初始基可行解最常用的方法是最小元素法。——既简便，又尽可能接近最优解。最小元素法的基本思想是就近供应，即从单位运价表中最小的运价开始确定供销关系，同时兼顾各产销地的需求，然后次小，一直到给出初始基可行解为止。
销地运输量产地 A1 A2 销量 B1 X11 X21 150 B2 X12 X22 150 B3 X13 X23 200 产量（件） 200 300 500
满足产地产量的约束条件为： X11+X12+X13=200 X21+X22+X23=300 满足销地销量的约束条件为： X11+X21＝150 X12+X22＝150 X13+X23＝200
《运筹学》第三章运输问题 Slide 9

产销不平衡的运输问题(课堂PPT)

1460
48
例1用伏格尔法得到的初始基可行解
B1 B2 B3 B4 产量
A1
4 12 12 4 4 11 16
A2
82
10
3 2 9 10
A3
8 14 5
11 用8最小6 元2素2 法
求出的目标函
销量 8 14 12 数z1=4246 48
目标函一数般值说来z ，1伏2 格4 尔4法1 得1 出8的2 初始解2 的质9 量1最4 好5，8常用6 来2作44 为运输问题最优解的近似解。
解：增加一个虚设的销地运输费用为0
B1 B2 B3 B4 产量 A1 6 4 6 0 300 A2 6 5 5 0 300
销量 150 150 200 100
一、产销不平衡的运输问题
（Ⅱ）若总产量小于总销量，即
m
n
ai bj
i 1
j 1
令假象产地的销量为：
n
m
am1 bj ai
j1
i1
仿照上述类似处理。
这里，松弛变量 x m+1,j 可以视为从产地 A m+1 运往销地 B j 的运输量，由于实际并不运送，它们的运费为
c m+1,j = 0 j = 1,2,…,n。于是，这个运输问题就转化成了一个产销平衡
的问题。
例:某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产
产销不平衡的运输问题
实际问题中产销往往是不平衡的，就需要把产销不平衡的问题转化成产销平衡问题。
产大于销
销大于产
一、产销不平衡的运输问题
（Ⅰ）若总产量大于总销量，即
m
n
ai bj

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

B1 最B优2解 B3 B4 产量 A1 0 4 2 12 12 4 4 11 16 A2 8 2 2 10 1 3 2 9 10 A3 9 8 14 5 12 11 8 6 22 销量 8 14 12 14 48
ij 0, 此时的解为最优解。
z 8 2 145 12 4 411 29 8 6 244 246 2
量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？
运
解：增加一个虚设的产地运输费用为0
运
举例
产销不平衡运输问题举例
设有A、B、C三个化肥厂供应1、2、3、4四个地区的农用化肥。假设效果相同，有关数据如下表
1
2
3
4 产量
A
16 13 22 17 50
运
原产大于销平衡问题的数学模型
mn
min z
cij xij
i 1 j 1
n
xij ai , i 1,2, , m
j 1
m
xij
b j , j 1,2, , n
i1
xij 0, i 1,2, , m
j 1,2, n
运
修改后产大于销平衡问题的数学模型
m n1
min z
运
几点说明：
当检验数为的负的变量超过两个，选择最小者对应的变量换入；在最优解的表中，若有检验数=0，则该运输问题有无穷多最优解；迭代过程中，若某一格填数时需同时划去一行和一列，此时出现退化。为保证 m+n-1个非空格，需在上述的行或列中填入数字0。
运
产销不平衡的运输问题
实际问题中产销往往是不平衡的，就需要把产销不平衡的问题转化成产销平衡问题。
运
第一步：确定初始基可行解 ——最小元素法、伏格尔法
最小元素法思路：
从单价中最小运价确定供应量，逐步次小，直至得到m+n-1个数字格。
运
最小元素法举例
B1 B2 B3 B4 产量
A1
4 12 10 4 6 11 166 0
A2 8 2 10 2 3 9 102 0
A3
8 14 5 11 8 6 228 0
销量
8
0
140
12 14 48
10 0
60
运
例1用伏格尔法得到的初始基可行解
B1 B2 B3 B4 产量
A1
4 12 12 4 4 11 16
A2 A3
销量
82
10
3 2 9 10
8 14 5 11 用8最小6 元2素2法
求出的目标函
8 14 12 数z1=4246 48
目标函一数般值说来z ，12伏格4 尔4法1得1出8的 2 初始解 2的质9 量1最4 好5， 8常用6 来2作44 为运输问题最优解的近似解。
j 1,2, n
运
表上作业法是单纯形法在求解运输问题的一种简便方法。单纯形法与表上作业法的关系：
（1）找出初始基可行解表上给出m+n-1个数字格
（2）求各非基变量的检验数计算表中空格检验数
（3）判断是否最优解检验是否所有检验数非负
运
？是
最优解
停止
否
换基：
（4）确定换入变量和换出变量找出新的基可行解。
cij xij
i 1 j 1
n 1
xij ai , i 1,2, , m
j 1
m
xij
b j , j 1,2, , n, n 1
i 1
xij 0, i 1,2, , m
j 1,2, n, n 1
运
注决最意策后：变一用量列最x的小ij 表零元示运素由价法最求A后i初到考始B虑调i 的。运物方品案数时量，。
表上调整（闭回路调整）
（5）重复（2）、（3）直至求出最优
解。
（运输问题必有最优解）
运
举例说明表上作业法
例1、某部门三个工厂生产同一产品的产量、四个销售点的销量及单位运价如下表：
B1 B2 B3 B4 产量
A1
4 12
4 11 16
A2
2 10
3 9 10
A3
8
5 11 6 22
销量 8 14 12 14 48
运筹学--产销不平衡运输问题
1 运输问题 2 运输问题的表上作业法 3 运输问题的进一步讨论
1
产销平衡问题的数学模型
mn
min z
cij xij
i 1 j 1
n
xij ai , i 1,2, , m
j 1
m
xij
b j , j 1,2, , n
i1
xij 0, i 1,2, , m
B1 B2
A x x c11
c12
1 11 12
A x x c21
c22
2 21 22
A x x cm1
cm 2
m m1 m2
b 销量 1 b2
B B n
n1 产量
x x a c1n
0
1n 1n1 1
x x a c2n
0
2n 2n1 2
x x a cmn
0
mn mn1 m
bn bn1
运
例:某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产
量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？
运
解：增加一个虚设的销地运输费用为0
运
一、产销不平衡的运输问题
（Ⅱ）若总产量小于总销量，即
m
n
ai b j
i 1
j 1
令假象产地的销量为：
n
m
am1
bj
ቤተ መጻሕፍቲ ባይዱ
ai
j 1
i 1
仿照上述类似处理。
B
14 13 19 15 60
运
第三步：解的调整
调整位置（2，4）非空，回路角上的格至少为空，且保证数字的非负性。
A1
B1
4
B2（12+2B ）103 4
B6（41-12）1产6量
A2 8 2 10 2 3 -1 9 10
A3
8 1（4 -25） 11 8（+62）22
销量 8 14 12 14 48
运
调整后的解为：
有无穷多
运
这里，松弛变量 x m+1,j 可以视为从产地 A m+1 运往销地 B j 的运输量，由于实际并不运送，它们的运费为 c m+1,j = 0 j = 1,2,…,n。于是，这个运输问题就转化成了一个产销平衡的问题。
运
例:某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产
产大于销
销大于产
运
一、产销不平衡的运输问题
（Ⅰ）若总产量大于总销量，即
m
n
ai b j
i 1
j 1
令假象销地的销量为：
m
n
bn1
ai
bj
i 1
j 1
运
这里，松弛变量 xi n+1 可以视为从产地 A i 运往销地 Bn+1 的运输量，由于实际并不运送，它们的运费为
ci n+1=0 i= 1,2,…,m。于是，这个运输问题就转化成了一个产销平衡的问题。