运筹学-运输问题

产销平衡运输问题的数学模型。 产销平衡运输问题的数学模型。 运输问题的数学模型
平衡表、 平衡表、运价表合二为一
销 产 A1 B1 c11 x11 c21 A2 ┇ x21 ┇
cm1
B2 c12 x12 c22 x22 ┇
cm2
… … … ┇
Bn c1n x1n c2n x2n ┇ cmn
产量 a1
A ij = ( 0 , , 0 ,1 , 0 , , 0 ,1 , 0 , , 0 ) T
个决策变量， 3. 运输问题有m×n个决策变量，m+n 个约 由于产销平衡条件，只有m+n m+n–1 束条 件。由于产销平衡条件，只有m+n 1 个相互独立，因此， 个相互独立，因此，运输问题的基变量只 有m+n–1 个。每个变量的系数列向量中有 m+n 1 两个1 其它元素均为0 两个1、其它元素均为0。 所有结构约束条件都是等式约束。 4. 所有结构约束条件都是等式约束。
a2 ┇
Am 销量
xm1 b1
xm2 b1
… …
xmn bn
am
二、运输问题数学模型的特点
1．运输问题有有限最优解 ．
若令其变量 ai b j xij = , i = 1,2, , m; j = 1,2, , n Q 其中
Q =
4.1
∑
m
i =1
ai =
∑ ቤተ መጻሕፍቲ ባይዱj
j =1
n
就是运输问题的一个可行解； 则(4.1)就是运输问题的一个可行解；另一方面，运 就是运输问题的一个可行解 另一方面， 输问题的目标函数有下界， 输问题的目标函数有下界，目标函数值不会趋于 由此可知，运输问题必存在有限最优解。 由此可知，运输问题必存在有限最优解。
供量 7 4 9
A3 销量 3
6 6 5
3 6
调运方案的任意空格存在唯一闭回路。 调运方案的任意空格存在唯一闭回路。 唯一闭回路
∞
2．运输问题约束条件的系数矩阵 ． m×n
x 11 x 12 x 1n x 21 1 1 1 1 1 1 1 1
其系数列向量 的结构是： 的结构是：
x 22 x 2n x m1 x m2 x mn 1 1 1 1 1
第 i个 ↓ ↓
1
11 1 1
j个
第 m +
① 闭回路法
闭回路：从空格出发顺时针(或逆时针)画水平(或垂直)直线， 闭回路：从空格出发顺时针(或逆时针)画水平(或垂直)直线， 遇到填有运量的方格可转90°，然后继续前进，直到到达出发的 遇到填有运量的方格可转90° 然后继续前进， 可转90 空格所形成的闭合回路。 空格所形成的闭合回路。
调运方案的任意空格存在唯一闭回路。 差 调运方案的任意空格存在唯一闭回路。 额 销 法 B1 B2 B3 B4 方 A1 5 2 案 3 1 A2
（2） 最小元素法 ）
销 产 A1 1 A2 9 B1 3 B2 11 B3 3 B4 10 产量 7 8 4
4
2
3
3
7 4
1
10 5 9
A3 销量 3
6
6 5
3
6
该方案总运费Z=4×3+3×10+3×1+1×2+6×4+3×5=86 该方案总运费Z=4×3+3×10+3×1+1×2+6×4+3× Z=4
B1
B2 11 9 4 5
B2
B3 3 2 10 1
B3
B4 10 8 5 3
B4
行差额
0 1 1
供量 7 4
6
3 6 5 6
9
A1 A2 A3
列差额 销 产 A1 A2 A3 销量
B1 3 1 7 2
B1
B2 11 9 4
B3 3 2 10 1
B3
B4 10 8 5 3
B4
行差额
0 1 2
B2
供量 7 4
第四章
运输问题
运输问题及其数学模型 用表上作业法求解运输问题 运输问题的进一步讨论 应用问题举例
第一节 运输问题及其数学模型
一、运输问题的一般数学模型
个产地生产某种物资， ●有m个产地生产某种物资，有n个地区需要该类物资 个产地生产某种物资 个地区需要该类物资 表示各产地产量， ●令a1, a2, …, am表示各产地产量， b1, b2, …, bn表示各 销地的销量，∑ai=∑bj 称为产销平衡 销地的销量， ∑ 的物资量， ●设xij表示产地 i 运往销地 j 的物资量，cij表示对应的 单位运费。 单位运费。
（3）(沃格尔)Vogel法 沃格尔)Vogel法 )Vogel
分别计算各行、各列次小、最小运价的差额， 分别计算各行、各列次小、最小运价的差额，优先在最大差额处进行供 需搭配。 需搭配。
销地 产地 A1 A2 A3 列差额
步骤： 步骤：
B1 3 1 7 2
B2 11 9 4 5
B3 3 2 10 1
B3 3 2 10 1
B3
B4 10 8 5 2
B4
差额
7 6
B1
B2
供量 7 4 9
5 3 6
3 6 5
2 1 3
6
该方案总运费Z=1×3+4×6+3×5+10×2+8×1+5× 该方案总运费Z=1×3+4×6+3×5+10×2+8×1+5×3=85 Z=1
3.最优解的判别 （检验数的求法） 最优解的判别 检验数的求法）
销 产 A1 A2 销量
B1 3 3 3
B2 4 5 5
B3 2 3 6
产量 10 4 14
解：本例中的仓库相当于物品的产地，使用地即为销地： 本例中的仓库相当于物品的产地，使用地即为销地： 设由A 运到B 的物品数量分别为x 设由 1运到 1，B2和B3，的物品数量分别为 11， x12和x13，由A2运到B1，B2和B3的物品数量分别为x21， 运到 的物品数量分别为 x22和x23，则可写出其数学模型如下： 则可写出其数学模型如下：
三、运输问题的对偶规划
min z = ∑ ∑ cij xij
i =1 j =1 m n
ui
vj
n x =a ( i = 1, , m ) m个 个 i ∑ ij j =1 m ∑ xij = b j ( j = 1, , n ) i =1 n个 个 xij ≥ 0 ( i = 1, , m ; j = 1, , n )
min z =
Ai的产品全 部供应出去 Bj的需求全 部得到满足
∑∑c
j=1 i =1
n
m
ij
x ij
∑x
j=1 m
n
ij
= ai
(i = 1,2,, m)
∑xij = b j
i =1
( j = 1,2,, n)
∑a =∑b
i= 1 i j= 1
m
n
j
xij ≥ 0
(i =1,2,, m; j =1,2,, n)
为对偶变量， 设ui,vj为对偶变量，对偶问题模型为
max
w=
∑a u +∑b v
i =1 i i j= i j
m
n
j
u i + v j ≤ cij
uivj无约束 （i=1,2, …,m;j=1,2, …,n)
例 4.1
某种物品先存放在两个仓库A 再运往三个使用地B 某种物品先存放在两个仓库 1和A2中．再运往三个使用地 1， B2和B3，其间的距离 或单位运价 如表小方格中的数据所示。各 其间的距离(或单位运价 如表小方格中的数据所示。 或单位运价)如表小方格中的数据所示 仓库的存量和使用地的需用量也都示于表中， 仓库的存量和使用地的需用量也都示于表中，试建立使总运输量 (或总运费 最小的运输问题数学模型。 或总运费)最小的运输问题数学模型 或总运费 最小的运输问题数学模型。
6 3 6 5
3
6
9
A1 A2 A3
列差额 销 产 A1 A2 A3 销量
B1 3 1 7 2
B1
B2 11 9 4
B3 3 2 10 1
B3
B4 10 8 5 2
B4
行差额
0 1
B2
供量 7
3 6
3 6 5
3
6
4 9
A1 A2 A3
差额 产 销 A1 A2 A3 销量
B1 3 1 7
B2 11 9 4
第二节 用表上作业法求解运输问题
一、计算步骤： 计算步骤：
找出初始调运方案。即在(m n)产销平衡 (m× (1) 找出初始调运方案。即在(m×n)产销平衡 表上给出m+n 个数字格。 m+n表上给出m+n-1个数字格。 (2) 求检验数。（闭回路法或位势法） 判别是否达 求检验数。（闭回路法或位势法） 。（闭回路法或位势法 到最优解。如已是最优解，则停止计算， 到最优解。如已是最优解，则停止计算，否则转到下 一步。 一步。 对方案进行改善，找出新的调运方案。（ 。（表上闭回 (3) 对方案进行改善，找出新的调运方案。（表上闭回 路法调整） 路法调整） 重复（ ）、（3），直到求得最优调运方案 直到求得最优调运方案。 (4) 重复（2）、（3），直到求得最优调运方案。
min z = 3x11 + 4x12 + 2x13 + 3x21 + 5x22 + 3x23 x11 + x12 + x13 = 10 x + x + x = 4 21 22 23 x11 + x21 = 3 x12 + x22 = 5 x13 + x23 = 6 x11, x12 , x13, x21, x22 , x23 ≥ 0