1
1
17
1
19
3
57
2
1
3
1
5
2
10
j 1
4
xij b j
i 1
xij
0Hale Waihona Puke 最优解为 : x11 10, x12 15, x23 5, x33 20, x34 10, x44 10
44
最小生产费用为 :
min z
cij xij 77.3
i1 j1
2 航运公司的船只配备问题
某航运公司承担六个港口城市A.B.C.D.E.F的四条固定航 线的物资运输任务，已知各条航线的起点城市．终点 城市及每天的航班数如表4－13所示。
cij (i 1,2,m, j 1,2,n)
汇总于单位运价表中（如表4－8）．
表4－7 产销平衡表
产地
销地 1
2
…
1
x11 x12
2
x21 x22
m 销量
xm1 xm2 b1 b2
n 产量
x1n a1 x2n a2
xmn am
b2n
在该表中，第 j列的物理含义为：从各产地 Ai (i 1,2,m) 发往销地的部分运输量 x1 j ，x2 j ，…，xmj 的和对应等于销 量 b j ．第 i 行的物理含义类同．
x11 10
xx1132
x22 x23
15 x33
25
x14 x24 x34 x44 20
又每月生产用于当月和以后各月交货的引擎不可能超过 该公司的实际生产能力，故还应满足
x11 x12 x13 x14 25
xx3232
x23 x34
x24 30
35
x44 10
构造“单位运价表”，它应等价于这里的“成本费用 表” .
4.3 运输问题模型
问题模型概述
运输问题是一类特殊的线性规划模型，该模型 最初用于解决部门的运输网络所要求的最经 济的运输路线和产品的调配问题，并取得了 成功．
在实际应用中，除运输问题外，许多非运输问题 一样可以建立其相应的运输问题模型，并由 此求出其最优解．
下面以“产销平衡模型”对运输问题进行简单 的概述和描述．
j 1
xij 0
在实际中，常出现产销不平衡的情形，此时需要把产销
不平衡问题转化为产销平衡问题来进行讨论．如当产量
m
n
ai 大于销量 bj 时，只需增加一个虚似的销地j n ，1
i 1
j 1
而该销地的需要量为
m
n
aibi
即可.销量大于产量的情
形类同.
i 1
j 1
应用实例
1 生产时序的安排
北方飞机公司制造商用飞机，其生产过程的最后阶段为 生产喷射引擎，然后装置于(一极速工作)机体，该公 司有若干近期必须交付使用飞机的合同，现要安排今 后四个月飞机喷射引擎的生产计划，必须在每月末分 别提供10，15，25，20台引擎．
表4－13 某航运公司的航线情况
航线 1 2 3 4
起点城市 E B A D
终点城市 D C F B
每天航班数 3 2 1 1
假定各条航线使用相同型号的船只，且各城市间的航程 天数如表4－14所示。 表4－14 各城市间的航程天数
A B C D EF
A
0
1 2 14 7 7
B
1
0 3 13 8 8
某产品的生产有 m个产地 Ai (i 1,2,m) ，其生产 量分别为ai (i 1,2,m) ，而该产品的销售有n 个销地 B j (i 1,2,n) ，其需要量分别为bj ( j 1,2,n) 已知该产品从产地 Ai (i 1,2,m) 到销地 Bj (i 1,2,n) 的单位运价为 cij (i 1,2,m, j 1,2,n) ，试建 立该运输问题的线性规划模型．
销地
月
1
1
1.08
2
M
3
M
4
M
2
1.095 1.110 M M
3
1.110 1.125 1.100 M
4
1.125 1.140 1.115 1.130
D 产量(ai)
0
25
0
35
0
30
0
10
销量（bj） 10
15
25
20 30
模型建立与求解
44
min z
cij xij
i1 j1
4
xij ai
假设从产地 Ai (i 1,2,m) 到销地 Bi (i 1,2,n) 的 运输量为 xij ，因为从产地 Ai到销地B j 的单位 运价为cij (i 1,2,m, j 1,2,n) ，所以可把运 输量 xij (i 1,2,m, j 1,2,n) 汇总于产销平衡 表中（如表4－7），而把单位运价
已知该公司各月的生产能力和生产每台引擎的成本如表4 －9所示(单位：百万元)，且如果生产出来的引擎当月 不能交货，则每台引擎每积压一个月需存储费和维护 费用0.015百万元，试在完成合约的情况下，制定一引 擎数量的生产安排方案，以使该公司今后四个月的生 产费用最小．
表4－9 生产成本表
月份
合约数
生产能力 单位成本 存储和维护费
表4－8 单位运价表
销地
产地
1
2
…
n
1
c11
c12
c1n
2
c21
c22
c2n
m
cm1
cm2
cmn
模型建立
mn
min z c11x11 c12 x12 cm1 xm2 cmn xmn
cij xij
m
xij b j ( j 1,2,, n)
i1 j1
i 1
n
xij ai (i 1,2,, m)
1
10
25
1.08
0.015
2
15
35
1.11
0.015
3
25
30
1.10
0.015
4
20
10
1.13
模型建立与求解
求该问题最优解的关键: 建立该问题的产销平衡表及元
xi素j 和单位运价表及c元ij 素 ．为此，x假ij 设 表i 示第
月生产并用于j 第 月交货的引擎数，因公司必须完成
合同，则xij 应满足
表4－10 成本费用表
销地
月
1
1
1.08
2
2 1.095 1.110
3 1.110 1.125
4 1.125 1.140
3
1.100 1.115
4
1.130
由于这是产销不平衡问题，故增加一虚拟的销地，使之 能构造为产销平衡模型，并把 “产销平衡表和单位运 价表”合二为一，如表4－11所示 。
表4－11 产销平衡表和单位运价表
C
2
3 0 15 5 5
D 14 13 15 0 17 20
E
7
8 5 17 0 3
F
7
8 5 20 3 0
若每条船只每次装．卸货的时间各需要一天，则航运公 司至少应配备多少条船只才能满足所有航线的运营要 求？
模型分析 、变量假设
表4－15 各航线所需的最少在航船只数
航线 装货天数 航程天数 卸货天数 小计 航班数 周转数