第三节 产销不平衡的运输问题及其

第四天送洗：y451200
xj0，yij0，zij0，（i=1,┈,4；j=1,┈,5）
2008/11
--22--
--《Ⅵ 产量
新购 1 第一天 M 第二天 M 第三天 M
第四天 M
1 1 1 1 0 5200
0.2 0.1 0.1 0.1 0 1000
2008/11
--21--
建立模型：
--《运筹学》 运输问题--
设 xj—第j天使用新毛巾的数量；yij—第i天送第j天使用快洗 餐巾的数量；zij—第i天送第j天使用慢洗餐巾的数量；
Min z=∑xj+∑∑0.2yij+∑∑0.1zij
第一天：x1=1000
需 第二天：x2+y12=700
求 约
m1
xij b j (j 1,2,...,n)
i1
x 0 (i 1,...,m,m 1; j 1,...,n) ij
2008/11
--16--
--《运筹学》 运输问题--
销＞产问题单位运价表
产地销地 B1 B2 ┈
A1
C11 C12 ┈
A2
C21 C22 ┈
┊ ┆┊┈
Am Cm1 Cm2 ┈
2008/11
--8--
产销平衡表
--《运筹学》 运输问题--
单位运价表
B1 B2 B3 B4 产量
A1 (1) (2) 4 3 7 A2 3 (1) 1 (-1) 4 A3 (10) 6 (12) 3 9 销量 3 6 5 6
B1 B2 B3 B4 A1 3 11 3 10 A2 1 9 2 8 A3 7 4 10 5
Ⅰ Ⅱ
示。又如果生产出来的柴
Ⅲ

B1
A1 A2 A3 A4 bj 5 M 3 4 20
B2
9 4 6 8 60
B3
2 7 4 10 35
B4
3 8 2 11 45
B5
0 0 0 0 20
ai
60 40 30 50 180
4
用前面的方法求运输方案：

下表为计算结果。可看出：产地A4还有20个单位没有运出。
B1
A1 A2 A3 A4 Bj 20 20 40 10 10 60 35 45 20 20 20
2
例3.4 求下列表中极小化运输问题的最优解。
B1 A1 5 B2 9 B3 2 B4 3 ai 60
A2
A3 A4 bj
-3 4 20
4
6 8 60
4
7
4 10 35
8
2 11 45
40
30 50
180
160
因为有： 4
a
i 1
i
180 b j 160
j 1
3
是一个产大于销的运输问题。表中A2不可达B1，用一个很大的正数M 表示运价C21。虚设一个销量为b5=180-160=20，Ci5=0，i=1,2,3,4，表的 右边增添一列 ，得到新的运价表。
A1
产 地 中 转 站 销 地
A1 A2 A3 T1 T2 T3 T4 B1 B2 B3 B4
A2 1 --3 5 --2 1 9 2 8
1 3 2 1 4 3 3 11 3 10
A3 3 --1 --2 3 7 4 10 5
T1 2 3 1 1 3 2 2 8 4 6
T2 1 5 --1 1 1 4 5 2 7
A1
8

i 1 j 1 m n i 1 j 1 i 1
m
n 1
m
n
m
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)
（二）最优解的判别 计算非基变量（空格）的检验数,当所有 的检验数 cij CB B 1 Pij 0 时，为最优解。 求空格检验数的方法有：
闭回路法
以某一空格为起点找一条闭回路，用水 平或垂直线向前划，每碰到一数字格转900后， 继续前进，直到回到起始空格为止。
闭回路如图5.3.1的（a）、（b）、（c） 等所示。从每一个空格出发一定存在并且可以 找到唯一的闭回路。因为，m+n-1个数字格 （基变量）对应的系数向量是一个基，任一空 格（非基变量）对应的系数向量是这个基的线 性组合。
1
CB B
[u1 , u 2 , , u m ; v1 , v , , v n ]
2
而每一个决策变量Xij的系数向量 P ei em j ，所以 ij
c ij (ui v j ) 0
(i, j B)
由单纯形法可知，所有基变量的检验数等于0，即
ij cij CB B 1 Pij c ij (ui v j )
第2步，在表5.3.5未划去的元素中再找出 最小运价为2，确定A2多余的1 t物资供应B3 。 得表5.3.6。将表5.3.5的行运价划去，得表5.3.7。
表5.3.6
销地
产地
A1 A2 A3 销量 销地

2021/5/1
产销平衡的运输问题
2021/5/1
例2 设有三个化肥厂(A，B，C)供应四个地区(Ⅰ， Ⅱ，Ⅲ，Ⅳ)的农用化肥。假定等量的化肥在这些地 区使用效果相同。各化肥厂年产量，各地区年需要 量及从各化肥厂到各地区运送单位化肥的运价如表 所示。试求出总的运费最节省的化肥调拨方案。
2021/5/1
2021/5/1
解 由于每个季度生产出来的柴油机不一定当 季交货，所以设xij为第i季度生产的用于第j季 度交货的柴油机数。根据合同要求，必须满足
x1110 x12 x2215 x13 x23 x3325 x14 x24 x34 x4420
2021/5/1
又每季度生产的用于当季和以后各季交货的柴
• 解 这是一个产销不平衡的运输问题，总产 量为160万吨，四个地区的最低需求为110万 吨，最高需求为无限。根据现有产量，第Ⅳ 个地区每年最多能分配到60万吨，这样最高 需求为210万吨，大于产量。为了求得平衡， 在产销平衡表中增加一个假想的化肥厂D，其 年产量为50万吨。由于各地区的需要量包含 两部分，如地区Ⅰ，其中30万吨是最低需求 ，故不能由假想化肥厂D供给，令相应运价为 M(任意大正数)，而另一部分20万吨满足或不 满足均可以，因此可以由假想化肥厂D供给， 按前面讲的，令相应运价为0。对凡是需求分 两种情况的地区，实际上可按照两个地区看 待。这样可以写出这个问题的产销平衡表和
比单纯形法简单得多。所以在解决实际问题时，人们 常常尽可能把某些线性规划的问题化为运输问题的数 学模型。下面介绍几个典型的例子。
2021/5/1
• 例3 某厂按合同规定须于当年每个季度末分别 提供10，15，25，20台同一规格的柴油机。已 知该厂各季度的生产能力及生产每台柴油机的 成本如表所示。又如果生产出来的柴油机当季 不交货的，每台每积压一个季度需储存、维护 等费用0.15万元。要求在完成合同的情况下， 作出使该厂全年生产(包括储存、维护)费用最 小的决策