运筹学04运输问题

因σ13=-2＜0，所以表中的解不是最优解
（三）解的改进
1.取最小负检验数σij对应的变量xij作为换入变量， 相应格（Ai，Bj）称为调整格； 2.以调整格为出发点（第一奇数点），做一闭回路， 对闭回路上的顶点依次编号（奇数顶点（+1），偶 数顶点（-1））； 3.调整量θ是选择闭回路上具有（-1）的运输量中 的最小者，该格中的变量为换出变量； 4.将闭回路上所有奇数顶点的运输量增加θ，所有 偶数顶点的运输量减去θ，从而得到一个新的运输 方案； 5.再用闭回路法或位势法计算各空格检验数，直到 求到最优解
初始解 解的改进
A1 A2 A3 需求量
15 -15 35 +15
书例4.7
B1 A1 A2 A3 需求量 50 50 10 11 16 25 B2 25 8 14 14 B3 15 12 10 15 10 18 35 35 35 B4 11 9 7 产量 40 60 45 145
新的方案
得到新的基变量，再用位势法或闭回路法计算各空格检验数，所 有检验数均≥0，故得到最优解:x12=25，x13=15，x21=50， x23=10，x33=10，x34=35。总运价z=1505 思路转换：如果表中数字格右上角的数字为单位利润，目标 函数为求利润最大，则采用最大元素法求初始解，当所有的 检验数≤0时，得到最优解。
B3
6 0 7 11
产量 12 14 4 30
费
A1 A2 A3 销量
（一）寻找初始可行解 有西北角法、最小元素法、伏格尔法 最小元素法
基本思想：从单位运价表中最小运价开始确定供销 关系，然后次小，直到给出初始基可行解为止。 具体方法：从单位运价表中找出最小元素，比较产 量和销量，当产大于销，划去该元素所在列，当 销大于产，划去该元素所在的行，然后在未划去 的元素中找最小元素，再确定供销关系。这样每 填入一个数字，在运价表上就划去一行或一列。 当表中只剩一个元素时，填入数字时，在运价表 上同时划去一行和一列。这样共可划m+n条直线， 在产销平衡表中填了m+n-1个数字（即给出了 m+n-1个基变量的值）
其余为0。
2.位势法（对偶变量法）
供需平衡的运输问题：
min C ( x) cij xij
i 1 j 1 m n
对偶问题：
maxC' aiui bj v j
i 1 j 1 m n
s.t.
x
j 1 m
n
ij
ai , i 1,2,..., m b j , j 1,2,..., n

B1 A1 A2 A3 需求量 +12 3 -14 9 5 2 3 +1
B2 10-1 1 4 6 10
B3 6 11 0 7 11
产量 12 14 4 30
初始解
σ32=C32-C12+C11-C31=6-1+5-3=7>0
=C22-C12+C11-C21=4-1+5-2=6>0 σ 13=C13-C11+C21-C23=6-5+2-0=3>0 σ 33=C33-C23+C21-C31=7-0+2-3=6>0 所有检验数都非负，所以这是最优解
B3 12 15
B4
产量
0 15 11 40
25
A2
35 11
25
9
0 25 60 0 10
A3 需求量
16 35
0
14
0
10 10 0
18
35 0
7
45 145
50
25
35
35
检验上面初始基本可行解的最优性（方法一）
闭回路法
B1 A1 15 A2 35 A3 需求量 50 16 25 14 10 35 11 10 25 14 25 18 35 35 145 7 45 15 9 60 B2 8 B3 12 B4 供应量 11 40
ui
0 -3 -2
由上表计算非基变量（空格）的检验数得 σ13=c13-(u1+v3)=6-(0+3)=3 σ22=4-(-3+1)=6 σ32=6-(-2+1)=7 σ33=7-(-2+3)=6 因检验数都≥0，故为最优解
例4.7（用最小元素法求初始基本可行解）
B1 A1
15
B2 10 8 14
总运费= 2*5+10*1+3*2+11*0+4*3=38 （元）
（二）解的最优性检验
计算各非基变量（空格）的检验数，因运输问题 的目标函数要求实现最小化，若所有的空格的检 验数非负（≥0），则当前解为最优解。 两种方法：闭回路法、位势法

1.闭回路法
从每一空格出发找一条闭回路，用水平或垂直线 向前划，当碰到一数字格时转90°后，继续前进， 直到回到起始空格为止。 从每一空格出发一定存在唯一的闭回路，在回路 上奇数顶点加一个单位，偶数顶点减一个单位， 这样由于在该空格供应一个单位引起的总费用的 变化是该空格的检验数。 计算每一个空格的检验数，若全都非负，则为最 优解。
σ 22
B1 A1 A2 A3 需求量 2 3 4 9 5 2 3
B2 10 1 4 6 10
B3 6 11 0 7 11
产量 12 14 4 30
总运费=2*5+10*1+3*2+11*0+4*3=38（元）
最优解
x11 2, x12 10, x21 3, x23 11, x31 4
第四章 运输问题
教学要求：
掌握运输问题数学模型的建立和算法 了解产销不平衡的运输问题及其求解
目
录
运输问题的数学模型和求解 几种特殊形式的运输问题 运用Excel求解运输问题
目
录
运输问题的数学模型和求解 几种特殊形式的运输问题 运用Excel求解运输问题
一、问题的提出
s.t. ui v j cij , i 1,2,...,ห้องสมุดไป่ตู้; j 1,2,...,n ui , v j 无约束
x
i 1
ij
xij 0
1 c B ( u1 , u 2 ,..., u m ; v1 , v 2 ,..., v n )。 由对偶理论知， B
每个决策变量Xij的系数列向量 P ij ei em j ，所以
某公司现将产品从三个工厂A1、A2、A3运往四个分销中心B1、 某公司现将产品从三个工厂A1、A2、A3运往四个分销中心B1、 B2、B3、B4。三个工厂的生产能力、四个分销中心的预测需求以及 B2、B3、B4。三个工厂的生产能力、四个分销中心的预测需求以及 从三个工厂运往四个分销中心单位运输成本见下表。现在的问题是， 从三个工厂运往四个分销中心单位运输成本见下表。现在的问题是， 决定使用哪些路线，并且每条路线分别运送多少货物可以使总运输 决定使用哪些路线，并且每条路线分别运送多少货物可以使总运输 成本达到最小。 成本达到最小。 单位运输成本
运输问题例子1
某公司经销甲产品，它下设三个工厂和三个销售点。各工厂每 日的产量和各销售点每日的销量，以及从各工厂到销售点的单 位产品运价如表。问该公司应如何调运产品，在满足各销售点 的需求量的前提下，使总运费为最小。 产销平衡和单位运价表
单 产 位 地 销 运 地
B1
5 2 3 9
B2
1 4 6 10
在表格中，任选一个空格作一个闭回路，计算各空格的检验数， 其中σ13=-2＜0，所以表中的解不是最优解。
检验上面初始基本可行解的最优性（方法二）
位势法
10 15 11 35 16 2 v1=10 2 v2=8 5 14 10 v3=14 25 14 25 18 35 v4=3 8 －2 15 5 7 u3=4 12 8 9 11 u1=0 u2=1
B1 A1 A2 A3 分销中心 需求 3 7 2 6000 B2 2 5 5 4000 B3 7 2 4 2000 B4 6 3 5 1500 工厂 生产能力 5000 6000 2500 13500
供给=需求
已知在点A1，A2，…，Am生产同样的商品，在 Ai产出的商品量为ai(i=1，2，…，m) ，货物 发送到消费点B1，B2，…，Bn去，其中在Bj的 消费量为bj（j=1，2，…，n）。假定最终产品 的运输可能从任何生产点到任何消费点，而从Ai 到Bj运送单位货物所需运输费用为Cij。 设从Ai到Bj运送的货物量为Xij，i=1，2，3； j=1，2，3，4，则模型如下：

书例4.7 平衡运输问题
B1 A1 A2 A3 需求量 50 B1 15 35 10 11 16 25 B2 10 25 11 16 50 25 8 +15 14 25 -15 14 10 35 B2 25 8 14 14 B3 12 25 15 10 18 35 B3 12 15 18 35 35 35 35 B4 11 9 7 B4 11 9 7 产量 40 60 45 145 产量 40 60 45 145
令u1=0,由以上5个方程求得： u1=0,u2=-3,u3=-2,v1=5,v2=1,v3=3
在初始调运方案最右边加一列ui，最下边加一行vj，ui表示 第i行的位势，vj表示第j列的位势
B1 A1 A2 A3 需求量 vj 2 3 4 9 5 5 2 3 10 1 B2 10 1 4 6 11 3 11 B3 6 0 7 产量 12 14 4 30
二、运输问题的一般模型
min cij xij s.t.
目标函数
x
j 1 m i 1
n
ij
ai
供给约束
xij b j