OR2 1
OPERATIONS RESEARCH
运筹学 Ⅱ
—— 怎样把事情做得最好郝英奇
OR2 2
第四章 运输问题本章要求：
掌握运输问题的数学模型掌握运输问题的求解方法化产销不平衡问题为平衡问题学会用计算机求解
OR2 3
4.1运输问题的数学模型
运输问题一般表述为：
某企业有 m个产地（生产厂） Ai,其产量分别为 ai,i=1,2,…m,n 个销地 （ 销售商）
Bj,其销售量分别为 bj,j=1,2,…n,从 Ai到 Bj
的每单位物资的运费为 Cij.要求拟定总运费最小的调运方案 。
OR2 4
运输表
.
销地产地 B1 B2 … Bn 产量
A1 C11 C12 … C1n a1
A2 C21 C22 … C2n a2
… … … … … …
Am Cm1 Cm2 … Cmn am
销量 b1 b2 … bn
OR2 5
运输问题的数学模型设从 Ai 到 Bj的运输量为 xij,（ 假定产销平衡）
则总运费,minZ= ∑∑ Cij xij
产量约束,∑xij = ai i=1,2,…m,
销量约束,∑xij = bj j=1,2,…n,
非负性约束,xij ≥0
n m
j=1 i=1n
j=1m
i=1
OR2 6
4.2表上作业法
计算步骤：
1、给出初始方案
2、检验是否最优
3、调整调运方案,Go to 2
OR2 7
例题 1
某建材公司有三个水泥厂 A1,A2,A3，
四个经销商 B1,B2,B3,B4,其产量、
销量、运费如下表：
销地产地 B1 B2 B3 B4 产量
A1
A2
A3
8
4
2
7
7
4
3
5
9
2
1
6
1
9
4
销量 3 2 4 5 14
OR2 8
4.2.1求初始调运方案
用最小元素法（也可用西北角法或 vogel
法）给出初始基可行解：
在运费表中找出最小元素，尽最大可能用完一个厂的产量，或满足一个商家的销量。得到满足者用线划去。
逐次寻找最小元素，直至分配完毕注意：如填写一个数字同时满足了一厂一商，则需在同行或同列中填写一个数字 0，以保证恰好有 m+n-1个数字。
OR2 9
例 1 之初始方案（ P119）
最小元素法：圈定 C24
B1 B2 B3 B4 产量
A1 8 7 3 2 1
A2 4 7 5?/5 9 4
A3 2 4 9 6 4
销量 3 2 4 5
OR2 10
例 1初始方案（续 1）
圈定 C31
B1 B2 B3 B4 产量
A1 8 7 3 2 1
A2 4 7 5?/5 9 4
A3?/3 4 9 6 4 1
销量 3 2 4 5
OR2 11
例 1初始方案（续 2）
圈定 C13
B1 B2 B3 B4 产量
A1 8 7?/1 2 1
A2 4 7 5?/5 9 4
A3?/3 4 9 6 4 1
销量 3 2 4 3 5
OR2 12
例 1 初始方案（续 3）
圈定 C32
B1 B2 B3 B4 产量
A1 8 7?/1 2 1
A2 4 7 5?/5 9 4
A3?/3?/ 1 9 6 4 1
销量 3 2 1 4 3 5
OR2 13
例 1 初始方案（续 4）
圈定 C23
B1 B2 B3 B4 产量
A1 8 7?/1 2 1
A2 4 7?/3?/5 9 4 1
A3?/3?/1 9 6 4 1
销量 3 2 1 4 3 5
OR2 14
例 1 初始方案（续 5）
圈定 C22
B1 B2 B3 B4 产量
A1 8 7?/1 2 1
A2 4?/1?/3?/5 9 4 1
A3?/3?/1 9 6 4 1
销量 3 2 1 43 5
OR2 15
例 1初始方案 —— 初始基可行解
中心数字为分配的运输量
B1 B2 B3 B4 产量
A1 1 1
A2 1 3 5 9
A3 3 1 4
销量 3 2 4 5
此方案费用为 40
OR2 16
4.2.2 最优性检验
最优性检验与单纯形法原理一致，计算方法有位势法和闭回路法，这里讲位势法。
位势法是任意给出一组数 ui和 vj,称之为位势，有数字的格满足,ui+vj=cij
没数字的格计算,σij=cij-(ui+vj)
OR2 17
位势计算,ui+vj
先填写初始方案相应的运费，任意给出一个 ui或 vj值，推出其它位势值。
计算 ui+vj,填于空格处
B1 B2 B3 B4 ui
A1 （ 3） （ 5） 3 （ -1） 2
A2 （ 5） 7 5 1 4
A3 2 4 （ 2） （ -2） 1
vj 1 3 1 -3
OR2 18
检验数计算,σij=cij-(ui+vj)
B1 B2 B3 B4 ui
A1 8-（ 3） =5 7-（ 5） =2 3-3=0 2-（ -1） =3 2
A2 4-（ 5） =-1 7-7=0 5-5=0 1-1=0 4
A3 2-2=0 4-4=0 9-（ 2） =7 6-（ -2） =8 1
vj 1 3 1 3
σ 21=-1
OR2 19
方案调整：
σij < 0 处，增加运输量，可节约运费。故做如下调整：
B1 B2 B3 B4 产量
A1 1 1
A2 +1 1-1 3 5 9
A3 3-1 1+1 4
销量 3 2 4 5
OR2 20
新方案：
B1 B2 B3 B4 产量
A1 1 1
A2 1 3 5 9
A3 2 2 4
销量 3 2 4 5
此方案费用为,1?3+1?4+3?5+5?1+2?2+4? 2=39
OR2 21
新方案检验
新方案相应的运费填于表上,给定位势初值，计算各位势值。
B1 B2 B3 B4 ui
A1 （ 2） （ 4） 3 （ -1） 0
A2 4 （ 6） 5 1 2
A3 2 4 （ 3） （ -1） 0
vj 2 4 3 -1
OR2 22
新方案检验
计算空格处（即非基变量）的检验数，
σij=cij-(ui+vj),所有 σij ≥0,已得最优解。
B1 B2 B3 B4 ui
A1 6 3 0 3
A2 0 1 0 0
A3 0 0 6 7
vj
OR2 23
4.3产销不平衡问题
产销不平衡是最常见的现象，此类问题可以转化为产销平衡的模型，而后求解。
运输问题产销平衡模型，实质上就是一个求解运输问题的标准型。
解决的办法是：增加一个虚拟的产地或销地，从而变成标准型 —— 产销平衡问题。
OR2 24
例题 2.供大于求的运输问题
运费及产销量表
B1 B2 B3 产量
A1
A2
A3
A4
6 4 5
8 3 2
7 5 6
5 1 2
70
40
50
20
销量 30 40 30 180
100
OR2 25
例 2 解：
引入虚拟销地 B4，（ 或理解为仓库），
就地“销售”，运费为零
B1 B2 B3 B4 产量
A1
A2
A3
A4
6 4 5 0
8 3 2 0
7 5 6 0
5 1 2 0
70
40
50
20
销量 30 40 30 80 180
180
OR2 26
例 2 求初始方案：（ P128）
用最小元素法，但零视为最大元素。（？）
B1 B2 B3 B4 产量
A1
A2
A3
A4
6 /30 4 /10 5 0/30
8 3 /10 2 / 30 0
7 5 6 0/50
5 1 /20 2 0
70 60 30
40 10
50
20
销量 30 40 30 80 50
20 10
180
180
OR2 27
例 2 初始方案：
.
B1 B2 B3 B4 产量
A1
A2
A3
A4
30 10 30
10 30
50
20
70
40
50
20
销量 30 40 30 80 180
180
OR2 28
例 2检验初始方案
计算位势 ui+vj
B1 B2 B3 B4 ui
A1
A2
A3
A4
6 4 (3) 0
(5) 3 2 (-1)
(6) (4) (3) 0
（ 3) 1 (0) (-3)
3
2
3
0
vj 3 1 0 -3
OR2 29
例 2计算检验数
σij=cij-(ui+vj),所有 σij ≥0,已得最优解。
B1 B2 B3 B4 ui
A1
A2
A3
A4
0 0 (2) 0
(3) 0 0 （ 1）
(1) (1) (3) 0
（ 2) 0 (2) (3)
vj
OR2 30
例题 3：弹性需求问题
设有三煤矿供应四地区，资料如下：
运价 地区煤矿 甲 乙 丙 丁产量
A
B
C
16
14
19
13
13
20
22
19
23
17
15
25
50
60
50
最低需求最高需求
30
50
70
70
0
30
10
不限
OR2 31
例题 3：解题思路：
设法转化为标准型
本题产量 160万吨，最低需求 110万吨，最高需求无限。实质上比较现实的最高需求 210万吨
产量大于最小需求；小于最大需求。而标准型是：产量 =销量。
处理办法：设想一个虚拟煤矿 D,生产 50万吨，
但这个产量只能供应可有可无的最高需求部分，
于是各地的需求也应分为两个部分：基本需求、
机动需求
虚拟产量的运输费用为零，但它对于基本需求来讲，运费为无穷大。
OR2 32
例题 3：建模：
1
运价 地区煤矿 甲 1 甲 2 乙 丙 丁 1 丁 2
产量
A
B
C
D
16
14
19
M
16
14
19
0
13
13
20
M
22
19
23
0
17
12
25
M
17
12
25
0
50
60
50
50
需求量 30 20 70 30 10 50 210
210
OR2 33
例题 3：最优解：
1
运价 地区煤矿 甲 1 甲 2 乙 丙 丁 1 丁 2
产量
A
B
C
D
30 20
50
20
0
30
10 30
20
50
60
50
50
需求量 30 20 70 30 10 50 210
210
OR2 34
4.4运输问题的计算机求解
AB,QM软件包，在 module中选择
transportation,在 file中点击 new,输入数据，
点击 solve,出现结果。
OR2 35
4.5 运输模型的应用
例题 4：某机床厂定下一年合同分别于各季度末交货。已知各季度生产成本不同，
允许存货，存储费 0.12万元 /台季，三、
四季度可以加班生产，加班生产能力 8台 /
季，加班费用 3万元 /台季度 正常生产能力 单位成本（万元） 交货台数
1
2
3
4
30
32
20
28
10.55
10.8
11
11.1
25
30
15
45
OR2 36
例四,分析：
可用线性规划，但用运输问题更简单
要决策的问题是各季度生产量和交货量设 xij表示第 i季度生产第 j季度交货的台数
因加班时间生产成本不同，故要区别开来，三四季度可加班，视同增加两个季度
需求量合计 115台，生产能力合计 126台，
供需不平衡，因此，增加一项闲置能力。
OR2 37
例四,建模：
,成本 交货生产 闲置1 2 3 4 能力 产量
1季度正常生产
2季度正常生产
3季度正常生产
3季度加班生产
4季度正常生产
4季度加班生产
10.55 10.67 10.79 10.91 0
M 10.8 10.92 11.04 0
M M 11 11.12 0
M M 14 14.12 0
M M M 11.1 0
M M M 14.1 0
30
32
20
8
28
8
需求量 25 30 15 45 11 126
126
OR2 38
例四 结果：
,生产 交货生产 闲置1 2 3 4 能力 产量
1季度正常生产
2季度正常生产
3季度正常生产
3季度加班生产
4季度正常生产
4季度加班生产
25 5
30 2
10 10
8
28
5 3
30
32
20
8
28
8
需求量 25 30 15 45 11 126
126
OR2 39
例题 5 航运调度问题
某航运公司承担六个城市 A,B,C,D,E,F
之间的四条航线，已知各航线的起点、终点及每天所需的航班数如下表。又知各城市之间的航行天数，假定船只型号相同，装卸货时间各一天，问该公司至少要配备多少条船才能满足需要？ 航线 起点 终点 每天航班数
1
2
3
4
E
B
A
D
D
C
F
B
3
2
1
1
OR2 40
例 5 城市之间航行天数表
,Cij A B C D E F
A
B
C
D
E
F
0 1 2 14 7 7
1 0 3 13 8 8
2 3 0 15 5 5
14 13 15 0 17 20
7 8 5 17 0 3
7 8 5 20 3 0
OR2 41
例 5 问题分析问题要求的是在保证需要的前提下，
至少需要多少船只。
所需船只包括两个部分：载货船、空驶船 。
航线 航行天数装卸天数合计 航班数载货船数
1
2
3
4
17
3
7
13
2
2
2
2
19
5
9
15
3
2
1
1
57
10
9
15
OR2 42
例 5 问题分析（续 1）
上表显示：载货船共需 91条，此船何来？
港口 到达 开出 余缺
A
B
C
D
E
F
0
1
2
3
0
1
1
2
0
1
3
0
-1
-1
2
2
-3
1
A B
C
DE
F
1 21
3
调度中心若无空驶，则 91条船刚好够用，
但虚线箭头都是空驶
OR2 43
例五 问题分析（续 2）
所需 91条货船要经调度而来，有的可在一个港口卸货后装运（如一条船从 E到 D
后再起程赴 B）。 若港口没有空船，则要从其它港口调度而来。（规模效益）
由上表可知,C,D,F港口有多余船只可供调出，而 A,B,E港口则需要调入空船。
问题的核心是：如何使空驶船的数量为最少？亦即如何按照最近原则调度船只
OR2 44
例五 问题分析（续 3）
为此建立运输问题数学模型。设 xij表示每天从 i港口调往 j港口的空船数，则 cijxij
就表示 i j航线上周转的船只数,∑cijxij
表示各条线上周转的船只总数
A B E 每天多余船只
C
D
F
2
14
7
3
13
8
5
17
3
2
2
1
每天缺少船只 1 1 3
OR2 45
例五 解题结果
上机求解：
A B E 每天多余船只
C
D
F
1
1
1
1
1
2
2
1
每天缺少船只
1 1 3
空船总需求量 2+5+13+17+3=40条空驶船 40条 +载重船 91条 =131条
OR2 46
例题 6 增产调度问题
工厂 市场
A,B,C 1,2,3,4
1000 1500 1750 900 1000 1900 1500
产量 4250 < 需求 5300
增产方案：
1、加班生产，能力增长 50%，费用增长 50%
2、新建 D厂，产能 2000，投资 200万元
3、新建 E厂，产能 2000，投资 300万元
4、新建 F厂，产能 2000，投资 400万元如何增加生产能力？
OR2 47
例题 6 问题分析
各工厂位于不同城市，原材料、劳动力、
以及运输费各不相同（为什么只考虑可变费用？），计算不同方案对应不同市场的费用，将生产费用和运费统一考虑，
从而决定产销方案。
将四个方案，在可变成本的意义上，分别求其最优产销分配计划，比较优劣。
再加入固定投资因素，进行综合比较。
OR2 48
第五章 目标规划
要求
1、理解概念
2、学会建模
3、学会图解法和单纯形解法
4、计算机求解
5、举一反三，学会应用
OR2 49
5.1目标规划的概念及数学模型 1
多目标问题
多目标线性规划
例 1 产品资源 A B 限量
1车间
2车间
2 1.5
1 2
50
40
单位利润 80 100
求利润最大的生产方案
OR2 50
5.1目标规划的概念及数学模型 2
例 2：例 1的要求多元化：
1,B产品不超过 10单位
2、利润不低于 1600元
3、充分利用 2车间的生产能力，尽量不加班。
解：问题分析：找差别、定概念
1）系统约束：原有约束条件是一种刚性约束，
称之为 系统约束,2x1+1.5x2≤50 (1)
x1+ 2x2 ≤40 (2)
OR2 51
5.1目标规划的概念及数学模型 3
2）目标约束：新提出的目标要求实际上也是约束条件，称之为 目标约束
3） 目标期望值：目标约束的目标一定要明确，
给出确切的量值，即 目标期望值
4）偏差变量：目标约束不是刚性的，而是弹性的，允许在一定范围内有偏差，这更接近于实际。为表达这种灵活性，便引入了 偏差变量的概念，偏差变量有正负之分，表示为,d+和
d-,d+表示超过目标值的部分； d-表示不足目标值的部分,显然有 d-·d+=0
OR2 52
本题三个目标约束依次表示为：
x2+ d1- -d1+=10
80x1+100x2+ d2- -d2+ =1600
x1 + 2x2+ d3- -d3+ =40
5） 目标的重要程度不同，因此目标的满足有先有后，即有优先级别。设最重要的为 P1级，次之者为 P2级 ……
P看成实数 P1>>P2
5.1目标规划的概念及数学模型 4
OR2 53
5.1目标规划的概念及数学模型 5
6） 目标规划的目标函数：
目标规划有多个目标，我们已经把它转化为目标约束，整个问题的目标就是使得实施结果与目标期望值的偏差最小于是本题目标函数表示为：
minZ=P1 d1+ +P2 d2- +P3(d3- +d3+)
OR2 54
5.1目标规划的概念及数学模型 6
综上所述，本题的数学模型为：
minZ=P1 d1+ +P2 d2- +P3(d3- +d3+)
2x1+1.5x2 ≤50
x2+ d1- -d1+=10
80x1+100x2+ d2- -d2+ =1600
x1 + 2x2+ d3- -d3+ =40
x1,x2,di-,di+ ≥0,i=1,2,3
OR2 55
5.1目标规划的概念及数学模型 7
说明,1）有时系统约束转化为目标约束，
则不再表示为系统约束。 2）有时同级别的目标中，其重要程度又有差别，则设置不同的权重。
设问题有 K个目标,L个优先等级，数学模型为,minZ= ∑PL (∑WL-i?di-+WL+i?di+ )
∑aijxj+ di- - di+ =bi,i=1,2,…,k
∑aijxj≤(= ≥) bi i=k+1,…,k+m
xj,di-,di+≥0,j=1,…n;i=1,2,…,k
OR2 56
5.2目标规划的图解法
图解例 2
x1
x2
10
20
30
40
10 20 30 40
d1-
d1+d2-d2
+
d3+
d3-
O A
B
C
OR2 57
5.3 目标规划的单纯形解法
目标规划使用单纯形法求解,di-,di+ 视为普通变量,P1>>P2 >> … >> PL
例题 4
加工方式 单产耗时工时费用优质率资源量正常生产 2.0 100 0.99 100
加班生产 2.0 150 0.98 ——
转承包 2.5 80 0.95 ——
临时工 3.0 80 0.90 ——
OR2 58
例题 4建模
要求,P1,尽量满足市场需求（ 100件）
P2,优质率不低于 98%
P3,生产费用不超过 22000元解：设四种生产方式依次为 x1,x2,x3,x4
则,minZ=P1 d1
- +P
2 d2
- +P
3 d3+
2x1 ≤ 100
x1+x2+x3+ x4+d1
- -d
1+ =100
x1- 5x3-8x4+ d2
- - d
2+ =0
200x1+300x2+200x3+240x4+ d3
-- d
3+ =22000
xj,di
-,d
i+ ≥0 j=1,2,3,4 i=1,2,3
OR2 59
例题 4 求解
,Cj 0 0 0 0 0 P1 0 P2 0 0 P3
CB XB b x1 x2 x3 x4 x5 d1- d1+ d2- d2+ d3- d3+ θj
0
P1
P2
0
X5
d1-
d2-
d3-
100
100
0
22000
2
1
(1)
200
0
1
0
300
0
1
3
200
0
1
-8
204
1
0
0
0
0
1
0
0
0
-1
0
0
0
0
1
0
0
0
-1
0
0
0
0
1
0
0
0
-1
50
100
0
110
σj
P1
P2
P3
-1
-1
0
-1
0
0
-1
-3
0
-1
8
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
1
OR2 60
5.5 目标规划应用举例之一例 5,A B C 工时限制工时 /件 5 8 12 120
利润 /件 100 140 252
要求,P1:充分利用工时
P2,A,B,C分别达到 5,5,8件，并按工时利润确定权重
P3,加班时间不要超过 16小时
P4,A,B,C月销售量 10,12,10件
P5,尽量减少加班时间
OR2 61
5.5 目标规划应用举例之一
8X1+5X2+12X3 +d1- - d1+ =170
X1+ d2- -d2+= 5
X2+ d3- -d3+= 5
X3+ d4- -d4+= 8
8X1+5X2+12X3 +d5- - d5+ =170+16
X1 + d6- -d6+= 10 ……
Xj,di
-,d
i+ ≥0,j=1,2,3 i=1,2,…,5
minZ=P1d1-+P2(20 d2- +18 d3- +21d4-)+P3 d5+
+P4(d6-+d7-+d8-)+P5 d1+
OR2 62
5.5 目标规划应用举例之二
例 7：多目标运输问题如下表。目标要求：
P1,产地不存货，且销量至少满足一半
P2,满足 B1需求，且 A4— B2尽量少运
P3,总运费最小销地产地 B1 B2 B3 产量
A1
A2
A3
A4
5 8 3
7 4 5
2 6 9
4 6 6
100
40
40
120
销量 120 140 140 400/300
OR2 63
5.5 目标规划应用举例之二
解：设 Ai到 Bj的运输量为 xij
X11+ X12 + X13 +d1--d1+=100
X21+ X22 + X23 +d2--d2+=40
X31+ X32 + X33 +d3--d3+=40
X41+ X42 + X43 +d4--d4+=120
X11+ X21 + X31 + X41+d5--d5+=120/2
X12+ X22 + X32+ X42+d6--d6+=140/2
X13+ X23+ X33 + X43 +d7--d7+=140/2
X11+ X21 + X31 + X41 +d8--d8+=120
X42 +d9--d9+=0
∑ ∑Cij Xij +d10--d10+=0
Xij,dL--dL+ ≥0 i=1,2,3,4 j=1,2,3 L=1,2,…,10
minZ=P1(d1-+d1++ …+ d 7+)+P2(d8-+d8+ +d9+)+P3 d10+
OR2 64
习题课
P178—— 5.11
设 A台广告 X1分钟,B台广告 X2分钟,C台广告 X3分钟
系统约束,40X1+60X2+80X3 ≤ 2400
P1级目标：
2000X1+4000X2+1000X3+ d1- -d1+= 80000
P2级目标,X1+X2+X3 +d2- -d2+= 30
P3级目标,X3 +d3- -d3+= 0
目标函数,minZ=P1 d1
- +P
2（ 2 d2
-+ d
2+ ） +P3 d3+
OPERATIONS RESEARCH
运筹学 Ⅱ
—— 怎样把事情做得最好郝英奇
OR2 2
第四章 运输问题本章要求：
掌握运输问题的数学模型掌握运输问题的求解方法化产销不平衡问题为平衡问题学会用计算机求解
OR2 3
4.1运输问题的数学模型
运输问题一般表述为：
某企业有 m个产地（生产厂） Ai,其产量分别为 ai,i=1,2,…m,n 个销地 （ 销售商）
Bj,其销售量分别为 bj,j=1,2,…n,从 Ai到 Bj
的每单位物资的运费为 Cij.要求拟定总运费最小的调运方案 。
OR2 4
运输表
.
销地产地 B1 B2 … Bn 产量
A1 C11 C12 … C1n a1
A2 C21 C22 … C2n a2
… … … … … …
Am Cm1 Cm2 … Cmn am
销量 b1 b2 … bn
OR2 5
运输问题的数学模型设从 Ai 到 Bj的运输量为 xij,（ 假定产销平衡）
则总运费,minZ= ∑∑ Cij xij
产量约束,∑xij = ai i=1,2,…m,
销量约束,∑xij = bj j=1,2,…n,
非负性约束,xij ≥0
n m
j=1 i=1n
j=1m
i=1
OR2 6
4.2表上作业法
计算步骤：
1、给出初始方案
2、检验是否最优
3、调整调运方案,Go to 2
OR2 7
例题 1
某建材公司有三个水泥厂 A1,A2,A3，
四个经销商 B1,B2,B3,B4,其产量、
销量、运费如下表：
销地产地 B1 B2 B3 B4 产量
A1
A2
A3
8
4
2
7
7
4
3
5
9
2
1
6
1
9
4
销量 3 2 4 5 14
OR2 8
4.2.1求初始调运方案
用最小元素法（也可用西北角法或 vogel
法）给出初始基可行解：
在运费表中找出最小元素，尽最大可能用完一个厂的产量，或满足一个商家的销量。得到满足者用线划去。
逐次寻找最小元素，直至分配完毕注意：如填写一个数字同时满足了一厂一商，则需在同行或同列中填写一个数字 0，以保证恰好有 m+n-1个数字。
OR2 9
例 1 之初始方案（ P119）
最小元素法：圈定 C24
B1 B2 B3 B4 产量
A1 8 7 3 2 1
A2 4 7 5?/5 9 4
A3 2 4 9 6 4
销量 3 2 4 5
OR2 10
例 1初始方案（续 1）
圈定 C31
B1 B2 B3 B4 产量
A1 8 7 3 2 1
A2 4 7 5?/5 9 4
A3?/3 4 9 6 4 1
销量 3 2 4 5
OR2 11
例 1初始方案（续 2）
圈定 C13
B1 B2 B3 B4 产量
A1 8 7?/1 2 1
A2 4 7 5?/5 9 4
A3?/3 4 9 6 4 1
销量 3 2 4 3 5
OR2 12
例 1 初始方案（续 3）
圈定 C32
B1 B2 B3 B4 产量
A1 8 7?/1 2 1
A2 4 7 5?/5 9 4
A3?/3?/ 1 9 6 4 1
销量 3 2 1 4 3 5
OR2 13
例 1 初始方案（续 4）
圈定 C23
B1 B2 B3 B4 产量
A1 8 7?/1 2 1
A2 4 7?/3?/5 9 4 1
A3?/3?/1 9 6 4 1
销量 3 2 1 4 3 5
OR2 14
例 1 初始方案（续 5）
圈定 C22
B1 B2 B3 B4 产量
A1 8 7?/1 2 1
A2 4?/1?/3?/5 9 4 1
A3?/3?/1 9 6 4 1
销量 3 2 1 43 5
OR2 15
例 1初始方案 —— 初始基可行解
中心数字为分配的运输量
B1 B2 B3 B4 产量
A1 1 1
A2 1 3 5 9
A3 3 1 4
销量 3 2 4 5
此方案费用为 40
OR2 16
4.2.2 最优性检验
最优性检验与单纯形法原理一致，计算方法有位势法和闭回路法，这里讲位势法。
位势法是任意给出一组数 ui和 vj,称之为位势，有数字的格满足,ui+vj=cij
没数字的格计算,σij=cij-(ui+vj)
OR2 17
位势计算,ui+vj
先填写初始方案相应的运费，任意给出一个 ui或 vj值，推出其它位势值。
计算 ui+vj,填于空格处
B1 B2 B3 B4 ui
A1 （ 3） （ 5） 3 （ -1） 2
A2 （ 5） 7 5 1 4
A3 2 4 （ 2） （ -2） 1
vj 1 3 1 -3
OR2 18
检验数计算,σij=cij-(ui+vj)
B1 B2 B3 B4 ui
A1 8-（ 3） =5 7-（ 5） =2 3-3=0 2-（ -1） =3 2
A2 4-（ 5） =-1 7-7=0 5-5=0 1-1=0 4
A3 2-2=0 4-4=0 9-（ 2） =7 6-（ -2） =8 1
vj 1 3 1 3
σ 21=-1
OR2 19
方案调整：
σij < 0 处，增加运输量，可节约运费。故做如下调整：
B1 B2 B3 B4 产量
A1 1 1
A2 +1 1-1 3 5 9
A3 3-1 1+1 4
销量 3 2 4 5
OR2 20
新方案：
B1 B2 B3 B4 产量
A1 1 1
A2 1 3 5 9
A3 2 2 4
销量 3 2 4 5
此方案费用为,1?3+1?4+3?5+5?1+2?2+4? 2=39
OR2 21
新方案检验
新方案相应的运费填于表上,给定位势初值，计算各位势值。
B1 B2 B3 B4 ui
A1 （ 2） （ 4） 3 （ -1） 0
A2 4 （ 6） 5 1 2
A3 2 4 （ 3） （ -1） 0
vj 2 4 3 -1
OR2 22
新方案检验
计算空格处（即非基变量）的检验数，
σij=cij-(ui+vj),所有 σij ≥0,已得最优解。
B1 B2 B3 B4 ui
A1 6 3 0 3
A2 0 1 0 0
A3 0 0 6 7
vj
OR2 23
4.3产销不平衡问题
产销不平衡是最常见的现象，此类问题可以转化为产销平衡的模型，而后求解。
运输问题产销平衡模型，实质上就是一个求解运输问题的标准型。
解决的办法是：增加一个虚拟的产地或销地，从而变成标准型 —— 产销平衡问题。
OR2 24
例题 2.供大于求的运输问题
运费及产销量表
B1 B2 B3 产量
A1
A2
A3
A4
6 4 5
8 3 2
7 5 6
5 1 2
70
40
50
20
销量 30 40 30 180
100
OR2 25
例 2 解：
引入虚拟销地 B4，（ 或理解为仓库），
就地“销售”，运费为零
B1 B2 B3 B4 产量
A1
A2
A3
A4
6 4 5 0
8 3 2 0
7 5 6 0
5 1 2 0
70
40
50
20
销量 30 40 30 80 180
180
OR2 26
例 2 求初始方案：（ P128）
用最小元素法，但零视为最大元素。（？）
B1 B2 B3 B4 产量
A1
A2
A3
A4
6 /30 4 /10 5 0/30
8 3 /10 2 / 30 0
7 5 6 0/50
5 1 /20 2 0
70 60 30
40 10
50
20
销量 30 40 30 80 50
20 10
180
180
OR2 27
例 2 初始方案：
.
B1 B2 B3 B4 产量
A1
A2
A3
A4
30 10 30
10 30
50
20
70
40
50
20
销量 30 40 30 80 180
180
OR2 28
例 2检验初始方案
计算位势 ui+vj
B1 B2 B3 B4 ui
A1
A2
A3
A4
6 4 (3) 0
(5) 3 2 (-1)
(6) (4) (3) 0
（ 3) 1 (0) (-3)
3
2
3
0
vj 3 1 0 -3
OR2 29
例 2计算检验数
σij=cij-(ui+vj),所有 σij ≥0,已得最优解。
B1 B2 B3 B4 ui
A1
A2
A3
A4
0 0 (2) 0
(3) 0 0 （ 1）
(1) (1) (3) 0
（ 2) 0 (2) (3)
vj
OR2 30
例题 3：弹性需求问题
设有三煤矿供应四地区，资料如下：
运价 地区煤矿 甲 乙 丙 丁产量
A
B
C
16
14
19
13
13
20
22
19
23
17
15
25
50
60
50
最低需求最高需求
30
50
70
70
0
30
10
不限
OR2 31
例题 3：解题思路：
设法转化为标准型
本题产量 160万吨，最低需求 110万吨，最高需求无限。实质上比较现实的最高需求 210万吨
产量大于最小需求；小于最大需求。而标准型是：产量 =销量。
处理办法：设想一个虚拟煤矿 D,生产 50万吨，
但这个产量只能供应可有可无的最高需求部分，
于是各地的需求也应分为两个部分：基本需求、
机动需求
虚拟产量的运输费用为零，但它对于基本需求来讲，运费为无穷大。
OR2 32
例题 3：建模：
1
运价 地区煤矿 甲 1 甲 2 乙 丙 丁 1 丁 2
产量
A
B
C
D
16
14
19
M
16
14
19
0
13
13
20
M
22
19
23
0
17
12
25
M
17
12
25
0
50
60
50
50
需求量 30 20 70 30 10 50 210
210
OR2 33
例题 3：最优解：
1
运价 地区煤矿 甲 1 甲 2 乙 丙 丁 1 丁 2
产量
A
B
C
D
30 20
50
20
0
30
10 30
20
50
60
50
50
需求量 30 20 70 30 10 50 210
210
OR2 34
4.4运输问题的计算机求解
AB,QM软件包，在 module中选择
transportation,在 file中点击 new,输入数据，
点击 solve,出现结果。
OR2 35
4.5 运输模型的应用
例题 4：某机床厂定下一年合同分别于各季度末交货。已知各季度生产成本不同，
允许存货，存储费 0.12万元 /台季，三、
四季度可以加班生产，加班生产能力 8台 /
季，加班费用 3万元 /台季度 正常生产能力 单位成本（万元） 交货台数
1
2
3
4
30
32
20
28
10.55
10.8
11
11.1
25
30
15
45
OR2 36
例四,分析：
可用线性规划，但用运输问题更简单
要决策的问题是各季度生产量和交货量设 xij表示第 i季度生产第 j季度交货的台数
因加班时间生产成本不同，故要区别开来，三四季度可加班，视同增加两个季度
需求量合计 115台，生产能力合计 126台，
供需不平衡，因此，增加一项闲置能力。
OR2 37
例四,建模：
,成本 交货生产 闲置1 2 3 4 能力 产量
1季度正常生产
2季度正常生产
3季度正常生产
3季度加班生产
4季度正常生产
4季度加班生产
10.55 10.67 10.79 10.91 0
M 10.8 10.92 11.04 0
M M 11 11.12 0
M M 14 14.12 0
M M M 11.1 0
M M M 14.1 0
30
32
20
8
28
8
需求量 25 30 15 45 11 126
126
OR2 38
例四 结果：
,生产 交货生产 闲置1 2 3 4 能力 产量
1季度正常生产
2季度正常生产
3季度正常生产
3季度加班生产
4季度正常生产
4季度加班生产
25 5
30 2
10 10
8
28
5 3
30
32
20
8
28
8
需求量 25 30 15 45 11 126
126
OR2 39
例题 5 航运调度问题
某航运公司承担六个城市 A,B,C,D,E,F
之间的四条航线，已知各航线的起点、终点及每天所需的航班数如下表。又知各城市之间的航行天数，假定船只型号相同，装卸货时间各一天，问该公司至少要配备多少条船才能满足需要？ 航线 起点 终点 每天航班数
1
2
3
4
E
B
A
D
D
C
F
B
3
2
1
1
OR2 40
例 5 城市之间航行天数表
,Cij A B C D E F
A
B
C
D
E
F
0 1 2 14 7 7
1 0 3 13 8 8
2 3 0 15 5 5
14 13 15 0 17 20
7 8 5 17 0 3
7 8 5 20 3 0
OR2 41
例 5 问题分析问题要求的是在保证需要的前提下，
至少需要多少船只。
所需船只包括两个部分：载货船、空驶船 。
航线 航行天数装卸天数合计 航班数载货船数
1
2
3
4
17
3
7
13
2
2
2
2
19
5
9
15
3
2
1
1
57
10
9
15
OR2 42
例 5 问题分析（续 1）
上表显示：载货船共需 91条，此船何来？
港口 到达 开出 余缺
A
B
C
D
E
F
0
1
2
3
0
1
1
2
0
1
3
0
-1
-1
2
2
-3
1
A B
C
DE
F
1 21
3
调度中心若无空驶，则 91条船刚好够用，
但虚线箭头都是空驶
OR2 43
例五 问题分析（续 2）
所需 91条货船要经调度而来，有的可在一个港口卸货后装运（如一条船从 E到 D
后再起程赴 B）。 若港口没有空船，则要从其它港口调度而来。（规模效益）
由上表可知,C,D,F港口有多余船只可供调出，而 A,B,E港口则需要调入空船。
问题的核心是：如何使空驶船的数量为最少？亦即如何按照最近原则调度船只
OR2 44
例五 问题分析（续 3）
为此建立运输问题数学模型。设 xij表示每天从 i港口调往 j港口的空船数，则 cijxij
就表示 i j航线上周转的船只数,∑cijxij
表示各条线上周转的船只总数
A B E 每天多余船只
C
D
F
2
14
7
3
13
8
5
17
3
2
2
1
每天缺少船只 1 1 3
OR2 45
例五 解题结果
上机求解：
A B E 每天多余船只
C
D
F
1
1
1
1
1
2
2
1
每天缺少船只
1 1 3
空船总需求量 2+5+13+17+3=40条空驶船 40条 +载重船 91条 =131条
OR2 46
例题 6 增产调度问题
工厂 市场
A,B,C 1,2,3,4
1000 1500 1750 900 1000 1900 1500
产量 4250 < 需求 5300
增产方案：
1、加班生产，能力增长 50%，费用增长 50%
2、新建 D厂，产能 2000，投资 200万元
3、新建 E厂，产能 2000，投资 300万元
4、新建 F厂，产能 2000，投资 400万元如何增加生产能力？
OR2 47
例题 6 问题分析
各工厂位于不同城市，原材料、劳动力、
以及运输费各不相同（为什么只考虑可变费用？），计算不同方案对应不同市场的费用，将生产费用和运费统一考虑，
从而决定产销方案。
将四个方案，在可变成本的意义上，分别求其最优产销分配计划，比较优劣。
再加入固定投资因素，进行综合比较。
OR2 48
第五章 目标规划
要求
1、理解概念
2、学会建模
3、学会图解法和单纯形解法
4、计算机求解
5、举一反三，学会应用
OR2 49
5.1目标规划的概念及数学模型 1
多目标问题
多目标线性规划
例 1 产品资源 A B 限量
1车间
2车间
2 1.5
1 2
50
40
单位利润 80 100
求利润最大的生产方案
OR2 50
5.1目标规划的概念及数学模型 2
例 2：例 1的要求多元化：
1,B产品不超过 10单位
2、利润不低于 1600元
3、充分利用 2车间的生产能力，尽量不加班。
解：问题分析：找差别、定概念
1）系统约束：原有约束条件是一种刚性约束，
称之为 系统约束,2x1+1.5x2≤50 (1)
x1+ 2x2 ≤40 (2)
OR2 51
5.1目标规划的概念及数学模型 3
2）目标约束：新提出的目标要求实际上也是约束条件，称之为 目标约束
3） 目标期望值：目标约束的目标一定要明确，
给出确切的量值，即 目标期望值
4）偏差变量：目标约束不是刚性的，而是弹性的，允许在一定范围内有偏差，这更接近于实际。为表达这种灵活性，便引入了 偏差变量的概念，偏差变量有正负之分，表示为,d+和
d-,d+表示超过目标值的部分； d-表示不足目标值的部分,显然有 d-·d+=0
OR2 52
本题三个目标约束依次表示为：
x2+ d1- -d1+=10
80x1+100x2+ d2- -d2+ =1600
x1 + 2x2+ d3- -d3+ =40
5） 目标的重要程度不同，因此目标的满足有先有后，即有优先级别。设最重要的为 P1级，次之者为 P2级 ……
P看成实数 P1>>P2
5.1目标规划的概念及数学模型 4
OR2 53
5.1目标规划的概念及数学模型 5
6） 目标规划的目标函数：
目标规划有多个目标，我们已经把它转化为目标约束，整个问题的目标就是使得实施结果与目标期望值的偏差最小于是本题目标函数表示为：
minZ=P1 d1+ +P2 d2- +P3(d3- +d3+)
OR2 54
5.1目标规划的概念及数学模型 6
综上所述，本题的数学模型为：
minZ=P1 d1+ +P2 d2- +P3(d3- +d3+)
2x1+1.5x2 ≤50
x2+ d1- -d1+=10
80x1+100x2+ d2- -d2+ =1600
x1 + 2x2+ d3- -d3+ =40
x1,x2,di-,di+ ≥0,i=1,2,3
OR2 55
5.1目标规划的概念及数学模型 7
说明,1）有时系统约束转化为目标约束，
则不再表示为系统约束。 2）有时同级别的目标中，其重要程度又有差别，则设置不同的权重。
设问题有 K个目标,L个优先等级，数学模型为,minZ= ∑PL (∑WL-i?di-+WL+i?di+ )
∑aijxj+ di- - di+ =bi,i=1,2,…,k
∑aijxj≤(= ≥) bi i=k+1,…,k+m
xj,di-,di+≥0,j=1,…n;i=1,2,…,k
OR2 56
5.2目标规划的图解法
图解例 2
x1
x2
10
20
30
40
10 20 30 40
d1-
d1+d2-d2
+
d3+
d3-
O A
B
C
OR2 57
5.3 目标规划的单纯形解法
目标规划使用单纯形法求解,di-,di+ 视为普通变量,P1>>P2 >> … >> PL
例题 4
加工方式 单产耗时工时费用优质率资源量正常生产 2.0 100 0.99 100
加班生产 2.0 150 0.98 ——
转承包 2.5 80 0.95 ——
临时工 3.0 80 0.90 ——
OR2 58
例题 4建模
要求,P1,尽量满足市场需求（ 100件）
P2,优质率不低于 98%
P3,生产费用不超过 22000元解：设四种生产方式依次为 x1,x2,x3,x4
则,minZ=P1 d1
- +P
2 d2
- +P
3 d3+
2x1 ≤ 100
x1+x2+x3+ x4+d1
- -d
1+ =100
x1- 5x3-8x4+ d2
- - d
2+ =0
200x1+300x2+200x3+240x4+ d3
-- d
3+ =22000
xj,di
-,d
i+ ≥0 j=1,2,3,4 i=1,2,3
OR2 59
例题 4 求解
,Cj 0 0 0 0 0 P1 0 P2 0 0 P3
CB XB b x1 x2 x3 x4 x5 d1- d1+ d2- d2+ d3- d3+ θj
0
P1
P2
0
X5
d1-
d2-
d3-
100
100
0
22000
2
1
(1)
200
0
1
0
300
0
1
3
200
0
1
-8
204
1
0
0
0
0
1
0
0
0
-1
0
0
0
0
1
0
0
0
-1
0
0
0
0
1
0
0
0
-1
50
100
0
110
σj
P1
P2
P3
-1
-1
0
-1
0
0
-1
-3
0
-1
8
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
1
OR2 60
5.5 目标规划应用举例之一例 5,A B C 工时限制工时 /件 5 8 12 120
利润 /件 100 140 252
要求,P1:充分利用工时
P2,A,B,C分别达到 5,5,8件，并按工时利润确定权重
P3,加班时间不要超过 16小时
P4,A,B,C月销售量 10,12,10件
P5,尽量减少加班时间
OR2 61
5.5 目标规划应用举例之一
8X1+5X2+12X3 +d1- - d1+ =170
X1+ d2- -d2+= 5
X2+ d3- -d3+= 5
X3+ d4- -d4+= 8
8X1+5X2+12X3 +d5- - d5+ =170+16
X1 + d6- -d6+= 10 ……
Xj,di
-,d
i+ ≥0,j=1,2,3 i=1,2,…,5
minZ=P1d1-+P2(20 d2- +18 d3- +21d4-)+P3 d5+
+P4(d6-+d7-+d8-)+P5 d1+
OR2 62
5.5 目标规划应用举例之二
例 7：多目标运输问题如下表。目标要求：
P1,产地不存货，且销量至少满足一半
P2,满足 B1需求，且 A4— B2尽量少运
P3,总运费最小销地产地 B1 B2 B3 产量
A1
A2
A3
A4
5 8 3
7 4 5
2 6 9
4 6 6
100
40
40
120
销量 120 140 140 400/300
OR2 63
5.5 目标规划应用举例之二
解：设 Ai到 Bj的运输量为 xij
X11+ X12 + X13 +d1--d1+=100
X21+ X22 + X23 +d2--d2+=40
X31+ X32 + X33 +d3--d3+=40
X41+ X42 + X43 +d4--d4+=120
X11+ X21 + X31 + X41+d5--d5+=120/2
X12+ X22 + X32+ X42+d6--d6+=140/2
X13+ X23+ X33 + X43 +d7--d7+=140/2
X11+ X21 + X31 + X41 +d8--d8+=120
X42 +d9--d9+=0
∑ ∑Cij Xij +d10--d10+=0
Xij,dL--dL+ ≥0 i=1,2,3,4 j=1,2,3 L=1,2,…,10
minZ=P1(d1-+d1++ …+ d 7+)+P2(d8-+d8+ +d9+)+P3 d10+
OR2 64
习题课
P178—— 5.11
设 A台广告 X1分钟,B台广告 X2分钟,C台广告 X3分钟
系统约束,40X1+60X2+80X3 ≤ 2400
P1级目标：
2000X1+4000X2+1000X3+ d1- -d1+= 80000
P2级目标,X1+X2+X3 +d2- -d2+= 30
P3级目标,X3 +d3- -d3+= 0
目标函数,minZ=P1 d1
- +P
2（ 2 d2
-+ d
2+ ） +P3 d3+
