数 学 规 划 模 型
I 引言一个复杂系统往往要受诸多因素的影响，而这些因素又要受到一定的限制。最优化就是在一定约束下，如何选取这些因素的值，使某项（或某些）
指标达到最优的一门学科。它包括数学规划、决策分析、最优控制等等。
最优化方法在经济、军事、科技等领域内都有广泛的应用。
例 1 把一根直径为 d 的圆木锯成矩形横梁。已知横梁强度 z 与宽度 x 成正比，与高度 y 的平方成正比。求宽、高各为多少时强度最大？
该问题的数学模型为：
)0(2 kkxyz
用微分法容易求出其解。
0,0,222 yxdyx
数学规划模型 格式：
)0(2 kkxyzmax
0,0
,222
yx
dyxs.t.
例 2 施工点 j 的坐标为 njba jj,,2,1),,(
对某材料的需求量为 njq j,,2,1,
第 i个料场的容量为,,,2,1,miM i吨求料场的 位置 及各料场向各施工点的 供应量,使材料运输的总吨公里最小。
解 设各料场到各施工点的距离为直线距离，且各施工点可在不同料场取料。
个料场坐标为第设 iyx ii ),(
提供的材料数量向施工点为料场 jiw ij 则
m
i
n
j
jijiij byaxwz
1 1
22 )()(
m
i
jij njqw
1
,,2,1,?
n
j
iij miMw
1
,,2,1,?
njmiw ij,,2,1;,,2,1,0
总吨公里数需求限制容量限制非负限制
min
s.t.
学习这一部分需注意的地方：
1,对给定的实际问题，如何作 合理的假设,并建立模型。如何处理分段函数、矛盾约束等问题。
2,怎样将一类模型化为另一类模型，易于求解。
3,同一问题可建立不同模型第二个问题不便用微分法求解，可用数学规划方法求解。
II 数学规划模型的建立数学规划模型 的一般形式：
)(min Xfz?
)( nRSX
TnxxxX ),,,( 21
）或 )(m a x( Xfz?
例如,)0(2 kkxyzmax
0,0
,222
yx
dyxs.t.
}0,,|),{( 222 yxdyxyxS
TyxX ),(?
若能写出描述 S的数学式子，则可直接写出。
这里
)( nRSX
TnxxxX ),,,( 21
)(min Xfz? ）或 )(m a x( Xfz?
目标函数可行域可行解决策变量描述 S 的数学式子 约束条件
S
问题 可行问题 不可行
X 最优解
z 最优目标值几个概念：
特别,nn xcxcxcz2211m i n (或 max)
或?
n
j
jj xcz
1
m in
mibxats i
n
j
jij,,2,1,),(..
1
11212111.,bxaxaxats nn
22222121 bxaxaxa nn
mnmnmm bxaxaxa2211
），（或 1b
），（或 2b
），（或 mb
njx j,,2,1,0
njx j,,2,1,0
线性规划模型或 CXz?m in
bAXts?..
OX?
等约束注：
M? CXz?m in
bAXts?..
OX?
M是常数与 CXz?m in
bAXts?..
OX?
有相同的最优解
1.
2,CXz?m in
bAXts?..
OX?
CXz0m a x
bAXts?..
OX?
与 有相同的最优解另外：
1,取整数，称模型为 整数规划模型jx
jx2,中部分取整数，称模型为 混合整数规划模型
jx3,只取 0或 1两个值，称为 0 — 1 规划模型
4,目标函数或约束条件是非线性的，
称为 非线性规划模型
5,若目标函数只有一个，称为 单目标规划模型 ；
若目标函数不只一个，称为 多目标规划模型。
nBBB?21
m
A
A
A
2
1
m
a
a
a
2
1
nbbb?21
mnmm
n
n
ccc
ccc
ccc
21
22221
11211
产地销地运 价例 1
求使总运费最少的调运方案。试建模。
产量需求量
42
一、运输问题
m
j
j
m
i
i ba
11
假设解的运量。到销地为产地设 jiij BAx
则
m
i
n
j
ijij xcz
1 1
m in
n
j
iij miaxts
1
,,2,1,.,?
m
i
jij njbx
1
,,2,1,?
njmix ij,,2,1;,,2,1,0
产销平衡注,若产大于销，则?
n
j
iij miax
1
,,2,1,
若产小于销，则?
m
i
jij njbx
1
,,2,1,
线性规划模型重要结论：
当供应量 与需求量 均为整数时，
模型的最优解 是整数解。
ia jb
X
例 2 自来水输送问题某市有甲、乙、丙、丁四个居民区，自来水由 A,B、
C由三个水库供应。四个区每天必须的基本生活用水分别为 30,70,10,10千吨，但三个水库每天最多只能分别供应 50,60,50千吨自来水。由于地理位置的差别，自来水公司从各水库向各区送水所付出的引水管理费不同（如表，其中 C水库与丁区间无输水管道），其它管理费均为 450元 /千吨。各区用户每千吨收费 900元。此外，各区用户都向公司申请了额外用水量，分别为每天 50,70,20,40千吨。问公司应如何分配供水量，才能获利最多？
丁丙乙甲
C
B
A
/23 020 019 0
15 019 013 014 0
17 022 013 016 0引水管理费 (元 /千吨 )
将有关数据整理列表：
丁丙乙甲
C
B
A
50
60
50
10107030
/23 020 019 0
15 019 013 014 0
17 022 013 016 0
水库居民区供应量生活用水额外用水 40207050
成水输 本
ijc
ia
jb
160
i
ia
300
j
jb
问题分析,… 可看成是“产小于销”的运输问题。
解设 xij 分别表示水库 A,B,C(i=1,2,3)向居民区甲,乙,
丙,丁 (j=1,2,3,4)的供水量。其中 X34=0.
模型建立由题意目标函数为,
3
1
4
1
1 160450160900m a x
i j
ijij xcz
可转化为,
3
1
4
1
m i n
i j
ijij xcz
50
60
50..
333231
24232221
14131211
xxx
xxxx
xxxxts
50
30
140
80
2414
332313
322212
312111
xx
xxx
xxx
xxx
10
10
70
30
供给限制需求限制一般问题中：
供给限制用,?”
需求限制用,?”
“?”
引水管理费因 160千吨水须全部输出
.4,3,2,1;3,2,1,0 jix ij
注,为了增加供水，公司考虑改造水库，使三个水库的供水能力提高一倍，问模型将作何改动？
分析,由于总供水能力为 320千吨，总需求量为 300千吨，水不能全部卖出，所以不能将获利最多转化为引水管理费最少。须算出每千吨净利润。
每千吨净利润＝
用户交的 900元－其它管理费 450元－引水管理费
/2 2 02 5 02 6 0
3 0 02 6 03 2 03 1 0
2 8 02 3 03 2 02 9 0
C
B
A净利润 (元 /千吨 ) 丁丙乙甲
ijc
模型改为：
ji
ijij xcZM ax
,
50
60
50..
333231
24232221
14131211
xxx
xxxx
xxxxts
100
120
100
其它同前例 3 最大流问题
①
②
③
④
⑤
⑥
⑦
20
14
15
12
10
13
8
8
9
10
12
图中弧上的数字表示每小时两结点沿箭头方向的最大车流量，求 ① 到 ⑦ 每小时的最大车流量。
二、网络（规划）问题设 v 为从 出发的车流量，1 为 到 的车流量，i jijx
则 vmax
vxxts 1312..
252412 xxx
vxxx 675747
流量守恒条件
120
200
67
12
x
x
弧容量限制
0?v
)(m a x 1312 xx?
去掉
6757471312 xxxxx
去掉若不设 v,则模型有四处需修改如果源、汇不止一个时，建模方法类似。可增加一个虚拟源、虚拟汇化成单源单汇的问题。
图中的结点 称为 源 （发点），结点 称为汇 （收点）。图是单源单汇的情形。
1 7
例 4 20
1 3
4
5
6
7
20
12
6 3
2 6 5
8
9
7
4
s
12
20 T
0 1 5 6 7求从 流出，到 的最大流量。
解 设 为 到 的流量，ijx i j 0sx 1sx 0 1,为流入,的量，
Tx5 Tx6 Tx7 5 6 7、,为流入,,的量。
10m a x ss xx?
020.,xxts s?
131 xx s?
2524234202 xxxxx
Txxx 77637
40
120
76
02
x
x
例 5 设有工作 件，人员 个，且一人做一件工作，
第 人作第 件工作的时间（或费用）为,问：
如何分派可使总时间（或总费用）最少。
mm
ijci j
解 本题需确定：第 人 做 或 不做 第 件工作，i j
这是 定性变量,首先将其 定量化 。
设
否则件工作人做第第
,0
,1 jix
ij mji,,2,1,
mixts
m
j
ij,,2,1,1..
1
mjx
m
i
ij,,2,1,1
1
mjix
ij,,2,1,10,或
0—1规划模型则
m
i
m
j
ijij xcz
1 1
m in
注,若 表示效益，则目标函数应极大化
ijc
问：各人员类不止 1人，
各工作类不止 1件工作，
决策变量为何？
若人数,>”
工作件数
三、分派问题四、生产活动问题 (分段函数、矛盾约束等的处理方法 )
nAAA?21
m
B
B
B
2
1
m
b
b
b
2
1
nccc?21
mnmm
n
n
aaa
aaa
aaa
21
22221
11211
资源产品单 耗资源量单位利润例 6 问如何安排生产使总利润最大。
解 设 表示第 种产品的产量，jx j 则
n
j
jj xcz
1
m a x
n
j
ijij mibxats
1
,,2,1,.,?
njx j,,2,1,0
资源分配问题分段函数问题例中 ＝单位收益－单位成本（ 可变成本 ）jc
若还要考虑 固定成本 jM
则第 j 种产品的利润为：
00
0,
j
jjjj
j x
xMxc
c
于是引入 0—1变量,
否则，
种产品生产第
0
,1 jy
j
0?jx即
0?jx nj,,2,1
设 Lj 是 xj的上界，则模型改写为：
n
j
jj xcz
1
m a x
n
j
ijij mibxats
1
,,2,1,.,?
njy j,,2,1,10 或
,jj yL? nj,,2,1
混合整数规划模型等价性：
（ 1） 10 jj yx 由
0?jx 由Z的极大化 0?jy
（ 2） 1?jy 由 0?jx
00 jj xy 由注,将目标函数变成 jj
n
j
jj yMxcz )(
1
则为非线性的。
n
j
jj yM
1
jx?0
若不考虑固定成本，则不引入 0-1变量。
更复杂的分段函数的处理方法 *
设 B1是某种原料（单位：吨），还可以从市场上购买到不超过 1500吨的原料。若购买量不超过 500吨，
其价格为 10千元 /吨；购买量多于 500吨但不超过
1000吨时，超过 500吨的部分 8千元 /吨；购买量超过
1000吨时，超过 1000吨的部分 6千元 /吨。问怎样安排生产和采购？
增设 x为采购量，则可得采购支出（千元）：
1 5 0 01 0 0 0,63 0 0 0
1 0 0 0500,81 0 0 0
5000,10
)(
xx
xx
xx
xc
)(m ax
1
xcxcz
n
j
jj
这时，目标函数为,
处理法 1：
设三种价格的采购量分别为,321,,xxx
则目标函数为：
)6810(m ax 321
1
xxxxcz
n
j
jj
约束条件增加：
500,,0
0)500(
0)500(
321
32
21
xxx
xx
xx
只有当 x1 =500时，才能以每吨 8千元的价格购买 x2(>0)
非线性规划模型！
处理法 1：
x 321 aaa
1b
2b
3b
)(xc
0;1500,1000,500 321 aaa
.12000,9000,5000 321 bbb
可用端点的凸组合来表示线段上的值，
如,上时有在上，在 ],[)(],[ 2121 bbxcaax
1
)(
21
2211
2211
bbxc
aax
为了统一表示，引入 0－ 1变量
否则，
个区间取值在第
0
,1 kx
k?
则
0,1
0)(
0
210
22110
22110
in
nn
nn
bbbxc
aaax
且
1
121
212
101
00
nn
nnn
1,,1,010
1110
nii
n
，或?
至多两个相邻的
i取非零值可得混合整数规划模型产品种类限制问题（不考虑固定成本）
n种产品中只生产其中 k种
njjy j,,2,1,0,1
否则，
种产品生产第设
n
j
jj xcz
1
m a x
n
j
ijij mibxats
1
,,2,1,.,?
njy j,,2,1,10 或
,jj yL? nj,,2,1jx?0
则
jy01.0
kyyy n21
要求产量不小于 80单位
80
矛盾约束问题设,为机器 1,2的可用工时（资源），1b 2b
n 种产品只在一台机器上加工，则以下两个约束条件是矛盾的，不能同时出现在一个模型中。
n
j
jj bxa
1
11,?
n
j
jj bxa
1
22
若引入 0—1变量：
否则，
上加工在机器
1
,0 iy
i 2,1?i
设 M 是充分大的常数，则两个矛盾约束可统一在一个模型中：
n
j
jj xcz
1
m a x
n
j
ijij mibxats
1
,,4,3,.,?;,,2,1,0 njx j
n
j
iijij iMybxa
1
2,1,
121 yy
2,110 iy i,或一般，若 m 种资源中只用其中 k 种资源，则令
否则，
种资源用第
1
,0 iy
i mi,,2,1
约束条件改为：
n
j
iijij miyMbxats
1
,,2,1,.,?
kmy
m
i
i
1
例 7 生产存储问题 （多阶段问题）
某公司生产一种产品，最大生产能力为 100单位，第月的单位存储费为 元，预定的销售量和单位成本如表。求使生产成本与存储费之和最低的生产计划。
i
ie
解 先作 合理 假设
1月初无库存；
4月底卖完；
当月生产的不入库；
库存量无限制。
假设：
4
3
2
1
76
80
72
70
60
120
70
60
月份 单位成本 ic (元 ) 销售量 id (件 )
模型一
4
1j
jj xcz 1
1
3
1 1
)(?
j
j
i
i
j
j
i
i edxmin
,..
11
j
i
i
j
i
i dxts 3,2,1?j
4
1
4
1 i
i
i
i dx
1 0 00 ix,4,3,2,1?i且为整数，
第 j+1月初的库存量整数规划模型设 为第 月的产量,为单位存储费，ix i ie 则模型二若设 为第 月初 的库存量,则is i
4
1j
jj xczmin i
i
i se?
4
1
4,3,2,1,.,1 idxssts iiii
0,0 51 ss
1 0 00 ix,4,3,2,1?i且为整数，
增加了决策变量,但模型简洁了。is
本问题还可建立 动态规划模型几点说明：
1,增加投资扩大生产能力若每投资 k 元可增加一个单位的生产能力。
设 表示第 月的投资，ik i
则第 月的产量限制条件变为：i
1 0 00 ix?
i
t
tkk
1
1
第 月前的投资在第 月仍起作用，ii
生产投资问题。
2,均衡生产问题前例中的最优月产量为,TX )60,50,1 0 0,1 0 0(
月初库存量为,TS )0,70,40,0(
为使生产尽量均衡，可增加相继两个月产量差的限制：
iiii zyxx 1
),(0 上升的量?iy
同时希望非负变量,越小越好。iy iz
则目标函数可提为：
i
i
i
i
i
i sczbyazm i n
其中 a 为第 月比第 月增加一个产品要支付的费用,b 为减少一个产品支付的费用,c为库存费。
i 1?i
)(0 下降的量?iz
根据要求还可提为：
i
i
i
i sczbzm i n
i
i
i
i scyazm i n或不希望减少不希望增加
＃
例 8 （ P.7例 1.8 ） 求生产、存储、维修计划将有关数据整理列表 (同例 1.6)：
5
1
t
1
1
3
2
4
336
336
1008
672
1344
71 ttjt aaa
71 j
71 ccc j
机床单 耗 产品 台数 tl 月台时 tb
单位利润月台时＝台数 小时 天数。1344＝ 4 16 21如一台机床维修一次需 160(台时 )＝ 10(天 ) 16(小时 )?
19
假定,? 没有轮到维修的和维修后的机床在使用期间能正常工作；
维修一台机床是在某月内完成，不会跨入下一月。
设
— 第 月初、第 种产品的库存量，ijs i j
— 第 月、第 种产品的产量，ijx i j
— 第 月、第 种机床的维修量。itk i t
6
1
7
1
6
1
7
1
m a x
i j
ij
i j
ijj asxcz
,.,1 jiijijij sdxsts 7,,1;6,,1 ji
,1 60
7
1
itt
j
ijtj kbxa
5,,1;6,,1 ti
5,,1,
6
1
tlk t
i
it
需求限制资源限制维修限制
且为整数tit lk0
i? 第 月维修哪几台机床可由人安排，只安排未维修的；
例 9 （下料问题）
某厂要做 100套钢架，每套由长为 2.9米,2.1米和 1.5
米的圆钢各一根组成。已知原料长 7.4米。问如何下料使原料最省。试建模。
问题分析：
“最节省”可以是“所用原料根数最少”，也可以是
“余料最少”。 基于前者建模。
一根原料钢管有不同的切割组合 ….,。找出每一种组合用去多少根原料钢管。所以首先列出所有可能组合即
“模式”。
解 将 8种下料方案列表,
10130234
02103210
21110000
87654321
5.1
1.2
9.2 方案根 数长度合计 6.0 6.6 7.2 6.3 7.4 6.5 7.1 7.3
余料 1.4 0.8 0.2 1.1 0 0.9 0.3 0.1
100
100
100需求量则种方案所用原料根数，为第设 ix i
8
1
m i n
i
ixz
1 0 02,8765 xxxxts
100232 76432 xxxxx
1 0 03234 865321 xxxxxx
8,,2,1
0
j
x j 且为整数若希望余料最少，则
8764321 1.03.09.01.12.08.04.1 xxxxxxxz
余料超过 1.5米
约束条件取“＝ 100”
设需 根原料，第 根下第 种圆钢 根，n i j ijx
3,2,1;,,2,1 jni?
3,2,1,,,2,1
3,2,1,1 0 0
,,2,1,4.75.11.29.2.
m i n
1
321
jni
jx
nixxxts
n
n
i
ij
iii
n是决策变量，而线性规划模型中是定数！该模型 不易计算 ！
以下几种作法欠妥：
客户拟定的设施地址
（ 1）离散型选址问题
（ 2）连续型选址问题设施的地址未拟定，可选在所论区域（很大）的任何地方。
问题,第 个设施是否需修建？若要修建，应为周围哪些客户服务？ 选址 — 分配问题
i
五、选址问题例 10（离散型）
施工点 j 对某材料的需求量为 njq j,,2,1,
第 i个料场的容量为
.,,2,1 mi
的单位运费 (元 / 吨 ),求使总费用最少的场址。
可基于两种考虑建模：
2° 施工点 只能在某一料场获取全部所需材料。j
1° 施工点 可在任何料场获取部分材料，以满足需求；j
建场费为 di 元,
解
1° 假定,
任何施工点到任何料场的道路是通的；
施工点 可在任何料场获取部分材料，以满足需求；j
拟定 m 个地方建料场，,吨iM
ijc 为地址 到施工点i j
一个大型工程有 n个施工点，
提供的材料数量向施工点为料场设 jix ij
则
m
i
ii
m
i
n
j
ijij ydxcz
11 1
m
i
jij njqx
1
,,2,1,?
n
j
iiij miyMx
1
,,2,1,?
njmix ij,,2,1;,,2,1,0
总费用需求限制容量限制非负限制
min
s.t.
否则，
建料场在地址
0
,1 iy
i
miy i,,2,110,或混合整数规划模型
2° 假定,? 任何施工点到任何料场的道路是通的；
施工点 只能在某一料场获取全部所需材料。j
设
否则，
供料向施工点地址
0
,1 jix
ij
否则，
建料场在地址
0
,1 iy
i则
m
i
ii
m
i
n
j
ijij ydxcz
11 1
,1
1
m
i
ijx
n
j
iiij miyMx
1
,,2,1,?
总费用需求限制容量限制
min
s.t.
njmix ij,,2,1;,,2,1,10 或非负限制
miy i,,2,110,或
jq
jq
nj,,2,1
0—1规划模型由于区域很大，所以施工点到料场间的距离视为直线距离
njba jj,,2,1),,(
例 11（连续型）
设工程所涉及的区域很大，第 j 个施工点的坐标为：
单位运费为 c (元 /吨 /公里 ),
欲建的 m个料场地址未拟定，其余条件与例 11相同。
求使总费用最少的场址。
解 基于第二种考虑建模设料场 的坐标为i 与前例相同iijii yxsr,),,(
m
i
ii
m
i
n
j
jijijij ydbsarcqxz
11 1
22 )()(min
s.t,同前例对 可不作非负限制，称为 自由变量ii sr,
非线性规划模型注,(1) 若 m个料场都要修建，则不设 0—1变量 iy
（ 3）若区域小，且道路呈网状，则使用 矩形距离
|||| jiji bsar
（ 2） 指标 不一定是“费用”，可以是“客户”到
“设施”
的最大距离最小等。
相当于将 取成 1。iy
目标函数中的常数项 应去掉。?
m
i i
d
1
),,,2,1)(,( nibai ii个用户的坐标为设第解若希望用户到中心的最大距离越小越好，则
|]||[|m a xm in
1,iiniyx
byax
且为整数,0,0,byaxts
1
1
2
20
),( yx
),( ii ba
也可以是用户到中心的距离之和最小建模。
均在第一象限内，
例 12 设某城市的街道成纵横交叉的网状，今欲建一物资供应中心，供 n个用户。问该中心建在什么位置合适。试建模。
),,( yx处，坐标为供应中心建在街道拐角问题！
以下几种作法不妥：
用直线距离
没设“中心”建在街道拐角处
将“中心”取在坐标原点,)|||(|m i n
1
n
i
ii yxz
决策变量？
设第 个用户的需求量为,单位运费为,… 得i iq ic
i iiii
byaxqcz |)||(|m i n （总运费）
例 13
某公司有工厂 A1,A2生产某种产品，生产能力分别为
Q1,Q2,有四个容量为 Mk的仓库 Bk(k=1,2,3,4)存放该产品，
工厂和仓库均可向 n个客户 Cj(j=6,7,…n+5) 供货，客户需求量为 qj(j=6,7,…n+5),现公司打算：扩建仓库 B1,其月费用为 e1，库容量增加 M；新建仓库 B5,月费用为 e5，
库容量为 M5;关闭仓库 B2或 B3,关闭后可节约费用 e2或 e3;
并要求总的仓库数不得超过 4个。已知工厂 Ai向仓库或客户供货的运费每单位为 cij(i=1,2;j=1,2,3,4,5为向仓库供货的运费,j=6,7,…,n+5 为向客户供货的运费 )。第 k
个仓库向第 j个客户供货的单位运费 dkj(k=1,2,3,4,5;
j= 6,7,…,n+5) 。以上费用均由公司负担。问公司该作何选择可使总费用最少。
解 为便于理解，先作网络图。
1A
2A
1B
5B
6C
5?nC
11c
16c
15c
5,1?nc
21c 26c
25c
5,2?nc
16d
5,1?nd
56d
5,5?nd
工厂 仓库 客户可仿运输问题，将有关数据列表。
5651?nCCBB
5,2262521
5,1161511
n
n
cccc
cccc
5,556
5,116
n
n
dd
dd
5
1
2
1
B
B
A
A
2
1
Q
Q
51 MM 56 nqq?
产地销地运 价 总量
)5,,6(),5,,1( njCjBA jjxi ij设
)5,,6( njCB jyk kj?
2
1 1i i
x
2
1 5i i
x
2,1?i
5,,1k
9
,,0,1 11
否则扩 B?
)3,2(,0,1?
iB i
i,否则留? 。
否则建
,0
,1 5
5
B?
55332211
5
1
5
6
2
1
5
1
mi n eeeeydxcz
k
n
j
ijkj
i
n
j
ijij
2,1,..
5
1
iQxts i
n
j
ij
5,,1,
2
1
5
6
kxy
i
ik
n
j
kj
5,,6,
5
1
2
1
njqyx j
k
kj
i
ij?
,112
1
1?MMx
i
i
),5,3,2(2
1
jMx jj
i
ij?,4
2
1
4 Mx
i
i
2532
产量限制客户需求限制仓库数量限制六、曲线拟合问题（ 去绝对值符号、化极大极小化模型为线性规划模型 ）
已知变量 y （随机变量）随 x（非随机变量）变化。
并已知一组样本观测值：
niyx ii,,2,1,),(
求近似表示 y 与 x 之关系的经验方程 —回归方程 。
),(
ii yx
),( ii yx ^
1 对观测值作 散点图,若点子沿一直线变化，则可用直线方程
^ bxay
作为经验方程。
（ 回归方程 ）
2 所给的准则不同，求出的 a,b 也不同。
常用方法 — 最小二乘法,
n
i
ii bxay
1
2)]([?
n
i
iyz
1
2)(
iy
^求使 最小的 a,b.
由
0
0
b
z
a
z
可解得 a,b。
求回归直线这一过程，称为 拟合 一条回归直线。
于是得到回归方程 ^ bxay^
ii bxay称函数值,为 回归值 。
所求回归方程能否用于预测和控制，还需作 假设检验。
类似可拟合 回归曲线 和 回归平面 。
例 14
（ 1）拟合一条回归直线，使回归值与观测值的绝对偏差之和最小；
（ 2）拟合一条回归直线，使回归值与观测值的最大偏差最小。
解 设回归方程为,^ bxay
（ 1）依题意，求解
n
i
ii bxayz
1
|)(|m i n
这是一个无约束的非线性规划模型，不便用微分法处理。
已知变量 y随变量 x变化，并已知一组观察值
.,,2,1),,( niyx ii
去掉绝对值符号，化为线性规划模型令)]([|)(|21 iiiii bxaybxayu
)]([|)(|21 iiiii bxaybxayv 0?
0?
iiii vubxay |)(|
iiii vubxay )(
则模型化为,?
n
i
ii vuz
1
)(m i n
niyvubxats iiii,,2,1,.,
nivu ii,,2,1,0,
为自由变量。ba,
是 2n+2个决策变量,n个约束方程的线性规划模型。
（ 2）依题意，得一 极大极小化模型,
|)(|m ax ii
i
bxaymin a,b
|)(|m ax ii
i
bxayu令因对任何 i都有,|)(| ii bxayu
于是得非线性规划模型：
um in
nibxayuts ii,,2,1,0|)(|.,
0?u
又因对任何 i都有,ubxayu ii )(
化线性规划模型
niubxayts ii,,2,1,0)(.,
0?u
um in
则得线性规划模型：
niubxay ii,,2,1,0)(
该模型中只有三个决策变量。 ＃
例 15
某公司上午 8点到 21点各时段需要的服务人员数量如表 1，四个班次的作息时间及月工资如表 2。求既满足需求又使公司所付工资总额最少的人员安排。
6
5
4
3
2
1
00:2100:18
00:1800:16
00:1600:14
00:1400:12
00:1200:10
00:1000:8
10
20
30
10
25
20
序号 时间区间 需求人数表 1
七、人员时间安排问题
4
3
2
1
00:2100:12
00:2100:12
00:1700:8
00:1700:8
00:1800:17
00:1700:16
00:1400:13
00:1300:12
900
900
800
800
班次 工作时间 休息时间 月工资表 2
解 利用表 1、表 2的各时间区间端点，将营业时间区间细分，并用,1”表示工作，,0”表示休息，
得一 关联表 （表 3）。
00:2100:18
00:1800:17
00:1700:16
00:1600:14
00:1400:13
00:1300:12
00:1200:10
00:1000:8
10
20
20
30
10
10
25
20
1100
0100
1011
1111
1101
1110
0011
0011
4321
班 次时 段需求人数表 3
列 给出了各班在哪几个时段工作，
行 给出了各时段有哪几个班在工作。
设 为第 班安排的人数ix i )4,3,2,1(?i
则得整数规划模型：
4321 9 0 09 0 08 0 08 0 0m i n xxxxz
25.,21 xxts
10432 xxx
10431 xxx
304321 xxxx
20421 xxx
203?x
1043 xx
且为整数，0?ix 4,3,2,1?i
建该模型的 关键 是：找出各班次工作的关联表，
根据关联表写出约束条件。
有多余的约束条件
！
例 16 （选课策略）
某校规定，运筹学专业的学生毕业时必须至少学习过两门数学课、三门运筹学课和两门计算机课。
这些课程的编号、名称、学分、所属 类别和先修课要求如表。问：毕业时，学生最少可以学习哪些课程？
编号 名称 学分 所属类别 先修课要求
1 微积分 5 数学
2 线性代数 4 数学
3 最优化 4 数学；运筹学 微积分；线代
4 数据结构 3 数学；计算机 计算机编程
5 应用统计 4 数学；运筹学 微积分；线代
6 计算机模拟 3 计算机；运筹学 计算机编程
7 计算机编程 2 计算机
8 预测理论 2 运筹学 应用统计
9 数学实验 3 运筹学；计算机 微积分；线代课程情况表建立课程与课程类别的关联表：
110110100
101101000
000011111
类别数学计算机运筹学课程微积分 线代 优化 结构 统计 模拟 编程 预测 实验 需求量
2
3
2
9,,2,1
0
,1
iix
i,否则，
门课选修第则得 0－ 1规划模型：
是前例中需求量为 2,3,2的特别情形。
解编号 名称 先修课要求
1 微积分
2 线性代数
3 最优化 微积分；线代
4 数据结构 计算机编程
5 应用统计 微积分；线代
6 计算机模拟 计算机编程
7 计算机编程
8 预测理论 应用统计
9 数学实验 微积分；线代课程情况表
9
1
m i n
i
ixz 课程总数类别（需求）限制
2
3
2
9764
98653
54321
xxxx
xxxxx
xxxxx
..ts
先修要求
)(
)()(
ji
xx ji
先修后修
9,,2,1,10 jx j 或
13 xx?
23 xx?
74 xx?
02
0
0
02
0
02
219
58
76
215
74
213
xxx
xx
xx
xxx
xx
xxx
注意表述方法！
例 17 一个生产问题，有关数据如表。问如何安排生产可使总利润最大，产量之和最小。要求第二种原料用完。 C
B
A
01
24
54
6
48
80
1 0 080单位利润产品原料 单 耗 甲 乙 总量解 设 为甲，乙的产量21,xx
则 211m i n xxz
212 10080m a x xxz
8054.,21 xxts
4824 21 xx
61?x
0,21?xx
双目标规划模型一般形式：
)(min XQ
)(m a x XR
OX
MXFts
)(..
矛盾的八、线性 多 目标规划模型化成单目标规划模型化法一 )(min XQ aXRts?)(..
OX
MXF
)(
或 bXQts?)(..
)(m a x XR
OX
MXF
)(
化法二)()1()(m i n XRXQ
OX
MXFts
)(..
为目标权重或偏好系数。
均可看成参数，对不同的参数值求出最优解，然后加以讨论，选出 满意解 。
,,ba
例 17中，要求利润最大，同时产量之和最小，这种目标称为 理想目标 。这些目标往往是相互矛盾的，
不可能同时达到最优。更现实的做法是：给出目标值，将理想目标转化为 现实目标,求出 尽量达到 目标值的生产方案。
如要求：总利润 100010080 21 xx
产量之和 2021 xx
把目标函数转化成了约束条件引入正负偏差变量,,将多目标规划模型转化为目标规划模型。
id?id
九、线性目标规划模型
2021 xx
100010080 21 xx
8054 21 xx
4824 21 xx
61?x
20.,1121 ddxxts
Min
要,”成立，只需 min1d
1d
1 0 0 01 0 080 2221 ddxx
2d
8054 3321 ddxx
3d
4824 4421 ddxx 要“＝”成立，需 min 44 dd
)( 44 dd
6551 ddx
5
0,, iii ddx
目标规划模型达成函数一般方法：
bXf?)(
bXf?)(
bXf?)(
bddXf)(
bddXf)(
bddXf)(
d
dd
目标类型 目标规划格式 极小化
0, dd
注：
1,对于 硬约束,,,? 可不设正偏差变量,?d
即直接取 。0d 对于,”，可直接取 。 0d
2,关于 优先级 问题例如,上例中，目标的重要性依次为：
1° A,B两种原料一定不能超过限量；
2° 原料 B尽量用完；
3° 利润超过 1000；
4° 产量之和尽量少。
于是，达成函数可写为：
Min )( 14 dP)( 23 dP)( 531 ddP )( 442 ddP
1P 2P 3P,4P其中 iP 为 优先因子或 Min )( 1?d),( 2?d),( 53 dd ),( 44 dd
实验作业
1.某厂生产甲乙两种口味的饮料,每百箱甲饮料需用原料 6千克,工人 10名,可获利 10万元 ;每百箱乙饮料需用原料 5千克,工人 20名,可获利 9万元,今工厂共有原料 60千克,工人 150名,又由于其他条件所限甲饮料产量不超过 8百箱,问如何安排生产计划,即两种饮料各生产多少使获利最大,
79
2.某厂向用户提供发动机，合同规定，第一、二、
三季度末分别交货 40台,60台,80台．每季度的生产费用为 （元），其中 x是该季生产的台数．若交货后有剩余，可用于下季度交货，但需支付存储费，每台每季度 c元．已知工厂每季度最大生产能力为 100台，第一季度开始时无存货，设
a=50,b=0.2,c=4，问工厂应如何安排生产计划，
才能既满足合同又使总费用最低．
2bxaxxf
3.某商店有五位工作人员,经理 1人,主任 1人,售货员 3人,有关情况见下表,设广告费对销售额的贡献为其投入的 15倍,各工作人员的收入相当于其完成销售额的 5.5%.问如何安排才能达到以下的目标,P1保证全体人员正常工作时间 ;P2 至少完成销售额 70000元 ;P3主任的月收入不少于
1200元,售货员 A和 B的月收入不少于 600元和 400元 ;P4 全体人员加班时间不超过规定 ; P5广告费不超过 3000元,力争销售额增加 10000元,前者的重要性为后者的两倍,
每小时对销售额的贡献 (元 ) 每月总工时每月加班限量 (工时 )
经理 144 200 24
主任 96 200 24
售货员 A 54 172 52
售货员 B 30 160 32
售货员 C 9 100 32
I 引言一个复杂系统往往要受诸多因素的影响，而这些因素又要受到一定的限制。最优化就是在一定约束下，如何选取这些因素的值，使某项（或某些）
指标达到最优的一门学科。它包括数学规划、决策分析、最优控制等等。
最优化方法在经济、军事、科技等领域内都有广泛的应用。
例 1 把一根直径为 d 的圆木锯成矩形横梁。已知横梁强度 z 与宽度 x 成正比，与高度 y 的平方成正比。求宽、高各为多少时强度最大？
该问题的数学模型为：
)0(2 kkxyz
用微分法容易求出其解。
0,0,222 yxdyx
数学规划模型 格式：
)0(2 kkxyzmax
0,0
,222
yx
dyxs.t.
例 2 施工点 j 的坐标为 njba jj,,2,1),,(
对某材料的需求量为 njq j,,2,1,
第 i个料场的容量为,,,2,1,miM i吨求料场的 位置 及各料场向各施工点的 供应量,使材料运输的总吨公里最小。
解 设各料场到各施工点的距离为直线距离，且各施工点可在不同料场取料。
个料场坐标为第设 iyx ii ),(
提供的材料数量向施工点为料场 jiw ij 则
m
i
n
j
jijiij byaxwz
1 1
22 )()(
m
i
jij njqw
1
,,2,1,?
n
j
iij miMw
1
,,2,1,?
njmiw ij,,2,1;,,2,1,0
总吨公里数需求限制容量限制非负限制
min
s.t.
学习这一部分需注意的地方：
1,对给定的实际问题，如何作 合理的假设,并建立模型。如何处理分段函数、矛盾约束等问题。
2,怎样将一类模型化为另一类模型，易于求解。
3,同一问题可建立不同模型第二个问题不便用微分法求解，可用数学规划方法求解。
II 数学规划模型的建立数学规划模型 的一般形式：
)(min Xfz?
)( nRSX
TnxxxX ),,,( 21
）或 )(m a x( Xfz?
例如,)0(2 kkxyzmax
0,0
,222
yx
dyxs.t.
}0,,|),{( 222 yxdyxyxS
TyxX ),(?
若能写出描述 S的数学式子，则可直接写出。
这里
)( nRSX
TnxxxX ),,,( 21
)(min Xfz? ）或 )(m a x( Xfz?
目标函数可行域可行解决策变量描述 S 的数学式子 约束条件
S
问题 可行问题 不可行
X 最优解
z 最优目标值几个概念：
特别,nn xcxcxcz2211m i n (或 max)
或?
n
j
jj xcz
1
m in
mibxats i
n
j
jij,,2,1,),(..
1
11212111.,bxaxaxats nn
22222121 bxaxaxa nn
mnmnmm bxaxaxa2211
），（或 1b
），（或 2b
），（或 mb
njx j,,2,1,0
njx j,,2,1,0
线性规划模型或 CXz?m in
bAXts?..
OX?
等约束注：
M? CXz?m in
bAXts?..
OX?
M是常数与 CXz?m in
bAXts?..
OX?
有相同的最优解
1.
2,CXz?m in
bAXts?..
OX?
CXz0m a x
bAXts?..
OX?
与 有相同的最优解另外：
1,取整数，称模型为 整数规划模型jx
jx2,中部分取整数，称模型为 混合整数规划模型
jx3,只取 0或 1两个值，称为 0 — 1 规划模型
4,目标函数或约束条件是非线性的，
称为 非线性规划模型
5,若目标函数只有一个，称为 单目标规划模型 ；
若目标函数不只一个，称为 多目标规划模型。
nBBB?21
m
A
A
A
2
1
m
a
a
a
2
1
nbbb?21
mnmm
n
n
ccc
ccc
ccc
21
22221
11211
产地销地运 价例 1
求使总运费最少的调运方案。试建模。
产量需求量
42
一、运输问题
m
j
j
m
i
i ba
11
假设解的运量。到销地为产地设 jiij BAx
则
m
i
n
j
ijij xcz
1 1
m in
n
j
iij miaxts
1
,,2,1,.,?
m
i
jij njbx
1
,,2,1,?
njmix ij,,2,1;,,2,1,0
产销平衡注,若产大于销，则?
n
j
iij miax
1
,,2,1,
若产小于销，则?
m
i
jij njbx
1
,,2,1,
线性规划模型重要结论：
当供应量 与需求量 均为整数时，
模型的最优解 是整数解。
ia jb
X
例 2 自来水输送问题某市有甲、乙、丙、丁四个居民区，自来水由 A,B、
C由三个水库供应。四个区每天必须的基本生活用水分别为 30,70,10,10千吨，但三个水库每天最多只能分别供应 50,60,50千吨自来水。由于地理位置的差别，自来水公司从各水库向各区送水所付出的引水管理费不同（如表，其中 C水库与丁区间无输水管道），其它管理费均为 450元 /千吨。各区用户每千吨收费 900元。此外，各区用户都向公司申请了额外用水量，分别为每天 50,70,20,40千吨。问公司应如何分配供水量，才能获利最多？
丁丙乙甲
C
B
A
/23 020 019 0
15 019 013 014 0
17 022 013 016 0引水管理费 (元 /千吨 )
将有关数据整理列表：
丁丙乙甲
C
B
A
50
60
50
10107030
/23 020 019 0
15 019 013 014 0
17 022 013 016 0
水库居民区供应量生活用水额外用水 40207050
成水输 本
ijc
ia
jb
160
i
ia
300
j
jb
问题分析,… 可看成是“产小于销”的运输问题。
解设 xij 分别表示水库 A,B,C(i=1,2,3)向居民区甲,乙,
丙,丁 (j=1,2,3,4)的供水量。其中 X34=0.
模型建立由题意目标函数为,
3
1
4
1
1 160450160900m a x
i j
ijij xcz
可转化为,
3
1
4
1
m i n
i j
ijij xcz
50
60
50..
333231
24232221
14131211
xxx
xxxx
xxxxts
50
30
140
80
2414
332313
322212
312111
xx
xxx
xxx
xxx
10
10
70
30
供给限制需求限制一般问题中：
供给限制用,?”
需求限制用,?”
“?”
引水管理费因 160千吨水须全部输出
.4,3,2,1;3,2,1,0 jix ij
注,为了增加供水，公司考虑改造水库，使三个水库的供水能力提高一倍，问模型将作何改动？
分析,由于总供水能力为 320千吨，总需求量为 300千吨，水不能全部卖出，所以不能将获利最多转化为引水管理费最少。须算出每千吨净利润。
每千吨净利润＝
用户交的 900元－其它管理费 450元－引水管理费
/2 2 02 5 02 6 0
3 0 02 6 03 2 03 1 0
2 8 02 3 03 2 02 9 0
C
B
A净利润 (元 /千吨 ) 丁丙乙甲
ijc
模型改为：
ji
ijij xcZM ax
,
50
60
50..
333231
24232221
14131211
xxx
xxxx
xxxxts
100
120
100
其它同前例 3 最大流问题
①
②
③
④
⑤
⑥
⑦
20
14
15
12
10
13
8
8
9
10
12
图中弧上的数字表示每小时两结点沿箭头方向的最大车流量，求 ① 到 ⑦ 每小时的最大车流量。
二、网络（规划）问题设 v 为从 出发的车流量，1 为 到 的车流量，i jijx
则 vmax
vxxts 1312..
252412 xxx
vxxx 675747
流量守恒条件
120
200
67
12
x
x
弧容量限制
0?v
)(m a x 1312 xx?
去掉
6757471312 xxxxx
去掉若不设 v,则模型有四处需修改如果源、汇不止一个时，建模方法类似。可增加一个虚拟源、虚拟汇化成单源单汇的问题。
图中的结点 称为 源 （发点），结点 称为汇 （收点）。图是单源单汇的情形。
1 7
例 4 20
1 3
4
5
6
7
20
12
6 3
2 6 5
8
9
7
4
s
12
20 T
0 1 5 6 7求从 流出，到 的最大流量。
解 设 为 到 的流量，ijx i j 0sx 1sx 0 1,为流入,的量，
Tx5 Tx6 Tx7 5 6 7、,为流入,,的量。
10m a x ss xx?
020.,xxts s?
131 xx s?
2524234202 xxxxx
Txxx 77637
40
120
76
02
x
x
例 5 设有工作 件，人员 个，且一人做一件工作，
第 人作第 件工作的时间（或费用）为,问：
如何分派可使总时间（或总费用）最少。
mm
ijci j
解 本题需确定：第 人 做 或 不做 第 件工作，i j
这是 定性变量,首先将其 定量化 。
设
否则件工作人做第第
,0
,1 jix
ij mji,,2,1,
mixts
m
j
ij,,2,1,1..
1
mjx
m
i
ij,,2,1,1
1
mjix
ij,,2,1,10,或
0—1规划模型则
m
i
m
j
ijij xcz
1 1
m in
注,若 表示效益，则目标函数应极大化
ijc
问：各人员类不止 1人，
各工作类不止 1件工作，
决策变量为何？
若人数,>”
工作件数
三、分派问题四、生产活动问题 (分段函数、矛盾约束等的处理方法 )
nAAA?21
m
B
B
B
2
1
m
b
b
b
2
1
nccc?21
mnmm
n
n
aaa
aaa
aaa
21
22221
11211
资源产品单 耗资源量单位利润例 6 问如何安排生产使总利润最大。
解 设 表示第 种产品的产量，jx j 则
n
j
jj xcz
1
m a x
n
j
ijij mibxats
1
,,2,1,.,?
njx j,,2,1,0
资源分配问题分段函数问题例中 ＝单位收益－单位成本（ 可变成本 ）jc
若还要考虑 固定成本 jM
则第 j 种产品的利润为：
00
0,
j
jjjj
j x
xMxc
c
于是引入 0—1变量,
否则，
种产品生产第
0
,1 jy
j
0?jx即
0?jx nj,,2,1
设 Lj 是 xj的上界，则模型改写为：
n
j
jj xcz
1
m a x
n
j
ijij mibxats
1
,,2,1,.,?
njy j,,2,1,10 或
,jj yL? nj,,2,1
混合整数规划模型等价性：
（ 1） 10 jj yx 由
0?jx 由Z的极大化 0?jy
（ 2） 1?jy 由 0?jx
00 jj xy 由注,将目标函数变成 jj
n
j
jj yMxcz )(
1
则为非线性的。
n
j
jj yM
1
jx?0
若不考虑固定成本，则不引入 0-1变量。
更复杂的分段函数的处理方法 *
设 B1是某种原料（单位：吨），还可以从市场上购买到不超过 1500吨的原料。若购买量不超过 500吨，
其价格为 10千元 /吨；购买量多于 500吨但不超过
1000吨时，超过 500吨的部分 8千元 /吨；购买量超过
1000吨时，超过 1000吨的部分 6千元 /吨。问怎样安排生产和采购？
增设 x为采购量，则可得采购支出（千元）：
1 5 0 01 0 0 0,63 0 0 0
1 0 0 0500,81 0 0 0
5000,10
)(
xx
xx
xx
xc
)(m ax
1
xcxcz
n
j
jj
这时，目标函数为,
处理法 1：
设三种价格的采购量分别为,321,,xxx
则目标函数为：
)6810(m ax 321
1
xxxxcz
n
j
jj
约束条件增加：
500,,0
0)500(
0)500(
321
32
21
xxx
xx
xx
只有当 x1 =500时，才能以每吨 8千元的价格购买 x2(>0)
非线性规划模型！
处理法 1：
x 321 aaa
1b
2b
3b
)(xc
0;1500,1000,500 321 aaa
.12000,9000,5000 321 bbb
可用端点的凸组合来表示线段上的值，
如,上时有在上，在 ],[)(],[ 2121 bbxcaax
1
)(
21
2211
2211
bbxc
aax
为了统一表示，引入 0－ 1变量
否则，
个区间取值在第
0
,1 kx
k?
则
0,1
0)(
0
210
22110
22110
in
nn
nn
bbbxc
aaax
且
1
121
212
101
00
nn
nnn
1,,1,010
1110
nii
n
，或?
至多两个相邻的
i取非零值可得混合整数规划模型产品种类限制问题（不考虑固定成本）
n种产品中只生产其中 k种
njjy j,,2,1,0,1
否则，
种产品生产第设
n
j
jj xcz
1
m a x
n
j
ijij mibxats
1
,,2,1,.,?
njy j,,2,1,10 或
,jj yL? nj,,2,1jx?0
则
jy01.0
kyyy n21
要求产量不小于 80单位
80
矛盾约束问题设,为机器 1,2的可用工时（资源），1b 2b
n 种产品只在一台机器上加工，则以下两个约束条件是矛盾的，不能同时出现在一个模型中。
n
j
jj bxa
1
11,?
n
j
jj bxa
1
22
若引入 0—1变量：
否则，
上加工在机器
1
,0 iy
i 2,1?i
设 M 是充分大的常数，则两个矛盾约束可统一在一个模型中：
n
j
jj xcz
1
m a x
n
j
ijij mibxats
1
,,4,3,.,?;,,2,1,0 njx j
n
j
iijij iMybxa
1
2,1,
121 yy
2,110 iy i,或一般，若 m 种资源中只用其中 k 种资源，则令
否则，
种资源用第
1
,0 iy
i mi,,2,1
约束条件改为：
n
j
iijij miyMbxats
1
,,2,1,.,?
kmy
m
i
i
1
例 7 生产存储问题 （多阶段问题）
某公司生产一种产品，最大生产能力为 100单位，第月的单位存储费为 元，预定的销售量和单位成本如表。求使生产成本与存储费之和最低的生产计划。
i
ie
解 先作 合理 假设
1月初无库存；
4月底卖完；
当月生产的不入库；
库存量无限制。
假设：
4
3
2
1
76
80
72
70
60
120
70
60
月份 单位成本 ic (元 ) 销售量 id (件 )
模型一
4
1j
jj xcz 1
1
3
1 1
)(?
j
j
i
i
j
j
i
i edxmin
,..
11
j
i
i
j
i
i dxts 3,2,1?j
4
1
4
1 i
i
i
i dx
1 0 00 ix,4,3,2,1?i且为整数，
第 j+1月初的库存量整数规划模型设 为第 月的产量,为单位存储费，ix i ie 则模型二若设 为第 月初 的库存量,则is i
4
1j
jj xczmin i
i
i se?
4
1
4,3,2,1,.,1 idxssts iiii
0,0 51 ss
1 0 00 ix,4,3,2,1?i且为整数，
增加了决策变量,但模型简洁了。is
本问题还可建立 动态规划模型几点说明：
1,增加投资扩大生产能力若每投资 k 元可增加一个单位的生产能力。
设 表示第 月的投资，ik i
则第 月的产量限制条件变为：i
1 0 00 ix?
i
t
tkk
1
1
第 月前的投资在第 月仍起作用，ii
生产投资问题。
2,均衡生产问题前例中的最优月产量为,TX )60,50,1 0 0,1 0 0(
月初库存量为,TS )0,70,40,0(
为使生产尽量均衡，可增加相继两个月产量差的限制：
iiii zyxx 1
),(0 上升的量?iy
同时希望非负变量,越小越好。iy iz
则目标函数可提为：
i
i
i
i
i
i sczbyazm i n
其中 a 为第 月比第 月增加一个产品要支付的费用,b 为减少一个产品支付的费用,c为库存费。
i 1?i
)(0 下降的量?iz
根据要求还可提为：
i
i
i
i sczbzm i n
i
i
i
i scyazm i n或不希望减少不希望增加
＃
例 8 （ P.7例 1.8 ） 求生产、存储、维修计划将有关数据整理列表 (同例 1.6)：
5
1
t
1
1
3
2
4
336
336
1008
672
1344
71 ttjt aaa
71 j
71 ccc j
机床单 耗 产品 台数 tl 月台时 tb
单位利润月台时＝台数 小时 天数。1344＝ 4 16 21如一台机床维修一次需 160(台时 )＝ 10(天 ) 16(小时 )?
19
假定,? 没有轮到维修的和维修后的机床在使用期间能正常工作；
维修一台机床是在某月内完成，不会跨入下一月。
设
— 第 月初、第 种产品的库存量，ijs i j
— 第 月、第 种产品的产量，ijx i j
— 第 月、第 种机床的维修量。itk i t
6
1
7
1
6
1
7
1
m a x
i j
ij
i j
ijj asxcz
,.,1 jiijijij sdxsts 7,,1;6,,1 ji
,1 60
7
1
itt
j
ijtj kbxa
5,,1;6,,1 ti
5,,1,
6
1
tlk t
i
it
需求限制资源限制维修限制
且为整数tit lk0
i? 第 月维修哪几台机床可由人安排，只安排未维修的；
例 9 （下料问题）
某厂要做 100套钢架，每套由长为 2.9米,2.1米和 1.5
米的圆钢各一根组成。已知原料长 7.4米。问如何下料使原料最省。试建模。
问题分析：
“最节省”可以是“所用原料根数最少”，也可以是
“余料最少”。 基于前者建模。
一根原料钢管有不同的切割组合 ….,。找出每一种组合用去多少根原料钢管。所以首先列出所有可能组合即
“模式”。
解 将 8种下料方案列表,
10130234
02103210
21110000
87654321
5.1
1.2
9.2 方案根 数长度合计 6.0 6.6 7.2 6.3 7.4 6.5 7.1 7.3
余料 1.4 0.8 0.2 1.1 0 0.9 0.3 0.1
100
100
100需求量则种方案所用原料根数，为第设 ix i
8
1
m i n
i
ixz
1 0 02,8765 xxxxts
100232 76432 xxxxx
1 0 03234 865321 xxxxxx
8,,2,1
0
j
x j 且为整数若希望余料最少，则
8764321 1.03.09.01.12.08.04.1 xxxxxxxz
余料超过 1.5米
约束条件取“＝ 100”
设需 根原料，第 根下第 种圆钢 根，n i j ijx
3,2,1;,,2,1 jni?
3,2,1,,,2,1
3,2,1,1 0 0
,,2,1,4.75.11.29.2.
m i n
1
321
jni
jx
nixxxts
n
n
i
ij
iii
n是决策变量，而线性规划模型中是定数！该模型 不易计算 ！
以下几种作法欠妥：
客户拟定的设施地址
（ 1）离散型选址问题
（ 2）连续型选址问题设施的地址未拟定，可选在所论区域（很大）的任何地方。
问题,第 个设施是否需修建？若要修建，应为周围哪些客户服务？ 选址 — 分配问题
i
五、选址问题例 10（离散型）
施工点 j 对某材料的需求量为 njq j,,2,1,
第 i个料场的容量为
.,,2,1 mi
的单位运费 (元 / 吨 ),求使总费用最少的场址。
可基于两种考虑建模：
2° 施工点 只能在某一料场获取全部所需材料。j
1° 施工点 可在任何料场获取部分材料，以满足需求；j
建场费为 di 元,
解
1° 假定,
任何施工点到任何料场的道路是通的；
施工点 可在任何料场获取部分材料，以满足需求；j
拟定 m 个地方建料场，,吨iM
ijc 为地址 到施工点i j
一个大型工程有 n个施工点，
提供的材料数量向施工点为料场设 jix ij
则
m
i
ii
m
i
n
j
ijij ydxcz
11 1
m
i
jij njqx
1
,,2,1,?
n
j
iiij miyMx
1
,,2,1,?
njmix ij,,2,1;,,2,1,0
总费用需求限制容量限制非负限制
min
s.t.
否则，
建料场在地址
0
,1 iy
i
miy i,,2,110,或混合整数规划模型
2° 假定,? 任何施工点到任何料场的道路是通的；
施工点 只能在某一料场获取全部所需材料。j
设
否则，
供料向施工点地址
0
,1 jix
ij
否则，
建料场在地址
0
,1 iy
i则
m
i
ii
m
i
n
j
ijij ydxcz
11 1
,1
1
m
i
ijx
n
j
iiij miyMx
1
,,2,1,?
总费用需求限制容量限制
min
s.t.
njmix ij,,2,1;,,2,1,10 或非负限制
miy i,,2,110,或
jq
jq
nj,,2,1
0—1规划模型由于区域很大，所以施工点到料场间的距离视为直线距离
njba jj,,2,1),,(
例 11（连续型）
设工程所涉及的区域很大，第 j 个施工点的坐标为：
单位运费为 c (元 /吨 /公里 ),
欲建的 m个料场地址未拟定，其余条件与例 11相同。
求使总费用最少的场址。
解 基于第二种考虑建模设料场 的坐标为i 与前例相同iijii yxsr,),,(
m
i
ii
m
i
n
j
jijijij ydbsarcqxz
11 1
22 )()(min
s.t,同前例对 可不作非负限制，称为 自由变量ii sr,
非线性规划模型注,(1) 若 m个料场都要修建，则不设 0—1变量 iy
（ 3）若区域小，且道路呈网状，则使用 矩形距离
|||| jiji bsar
（ 2） 指标 不一定是“费用”，可以是“客户”到
“设施”
的最大距离最小等。
相当于将 取成 1。iy
目标函数中的常数项 应去掉。?
m
i i
d
1
),,,2,1)(,( nibai ii个用户的坐标为设第解若希望用户到中心的最大距离越小越好，则
|]||[|m a xm in
1,iiniyx
byax
且为整数,0,0,byaxts
1
1
2
20
),( yx
),( ii ba
也可以是用户到中心的距离之和最小建模。
均在第一象限内，
例 12 设某城市的街道成纵横交叉的网状，今欲建一物资供应中心，供 n个用户。问该中心建在什么位置合适。试建模。
),,( yx处，坐标为供应中心建在街道拐角问题！
以下几种作法不妥：
用直线距离
没设“中心”建在街道拐角处
将“中心”取在坐标原点,)|||(|m i n
1
n
i
ii yxz
决策变量？
设第 个用户的需求量为,单位运费为,… 得i iq ic
i iiii
byaxqcz |)||(|m i n （总运费）
例 13
某公司有工厂 A1,A2生产某种产品，生产能力分别为
Q1,Q2,有四个容量为 Mk的仓库 Bk(k=1,2,3,4)存放该产品，
工厂和仓库均可向 n个客户 Cj(j=6,7,…n+5) 供货，客户需求量为 qj(j=6,7,…n+5),现公司打算：扩建仓库 B1,其月费用为 e1，库容量增加 M；新建仓库 B5,月费用为 e5，
库容量为 M5;关闭仓库 B2或 B3,关闭后可节约费用 e2或 e3;
并要求总的仓库数不得超过 4个。已知工厂 Ai向仓库或客户供货的运费每单位为 cij(i=1,2;j=1,2,3,4,5为向仓库供货的运费,j=6,7,…,n+5 为向客户供货的运费 )。第 k
个仓库向第 j个客户供货的单位运费 dkj(k=1,2,3,4,5;
j= 6,7,…,n+5) 。以上费用均由公司负担。问公司该作何选择可使总费用最少。
解 为便于理解，先作网络图。
1A
2A
1B
5B
6C
5?nC
11c
16c
15c
5,1?nc
21c 26c
25c
5,2?nc
16d
5,1?nd
56d
5,5?nd
工厂 仓库 客户可仿运输问题，将有关数据列表。
5651?nCCBB
5,2262521
5,1161511
n
n
cccc
cccc
5,556
5,116
n
n
dd
dd
5
1
2
1
B
B
A
A
2
1
Q
Q
51 MM 56 nqq?
产地销地运 价 总量
)5,,6(),5,,1( njCjBA jjxi ij设
)5,,6( njCB jyk kj?
2
1 1i i
x
2
1 5i i
x
2,1?i
5,,1k
9
,,0,1 11
否则扩 B?
)3,2(,0,1?
iB i
i,否则留? 。
否则建
,0
,1 5
5
B?
55332211
5
1
5
6
2
1
5
1
mi n eeeeydxcz
k
n
j
ijkj
i
n
j
ijij
2,1,..
5
1
iQxts i
n
j
ij
5,,1,
2
1
5
6
kxy
i
ik
n
j
kj
5,,6,
5
1
2
1
njqyx j
k
kj
i
ij?
,112
1
1?MMx
i
i
),5,3,2(2
1
jMx jj
i
ij?,4
2
1
4 Mx
i
i
2532
产量限制客户需求限制仓库数量限制六、曲线拟合问题（ 去绝对值符号、化极大极小化模型为线性规划模型 ）
已知变量 y （随机变量）随 x（非随机变量）变化。
并已知一组样本观测值：
niyx ii,,2,1,),(
求近似表示 y 与 x 之关系的经验方程 —回归方程 。
),(
ii yx
),( ii yx ^
1 对观测值作 散点图,若点子沿一直线变化，则可用直线方程
^ bxay
作为经验方程。
（ 回归方程 ）
2 所给的准则不同，求出的 a,b 也不同。
常用方法 — 最小二乘法,
n
i
ii bxay
1
2)]([?
n
i
iyz
1
2)(
iy
^求使 最小的 a,b.
由
0
0
b
z
a
z
可解得 a,b。
求回归直线这一过程，称为 拟合 一条回归直线。
于是得到回归方程 ^ bxay^
ii bxay称函数值,为 回归值 。
所求回归方程能否用于预测和控制，还需作 假设检验。
类似可拟合 回归曲线 和 回归平面 。
例 14
（ 1）拟合一条回归直线，使回归值与观测值的绝对偏差之和最小；
（ 2）拟合一条回归直线，使回归值与观测值的最大偏差最小。
解 设回归方程为,^ bxay
（ 1）依题意，求解
n
i
ii bxayz
1
|)(|m i n
这是一个无约束的非线性规划模型，不便用微分法处理。
已知变量 y随变量 x变化，并已知一组观察值
.,,2,1),,( niyx ii
去掉绝对值符号，化为线性规划模型令)]([|)(|21 iiiii bxaybxayu
)]([|)(|21 iiiii bxaybxayv 0?
0?
iiii vubxay |)(|
iiii vubxay )(
则模型化为,?
n
i
ii vuz
1
)(m i n
niyvubxats iiii,,2,1,.,
nivu ii,,2,1,0,
为自由变量。ba,
是 2n+2个决策变量,n个约束方程的线性规划模型。
（ 2）依题意，得一 极大极小化模型,
|)(|m ax ii
i
bxaymin a,b
|)(|m ax ii
i
bxayu令因对任何 i都有,|)(| ii bxayu
于是得非线性规划模型：
um in
nibxayuts ii,,2,1,0|)(|.,
0?u
又因对任何 i都有,ubxayu ii )(
化线性规划模型
niubxayts ii,,2,1,0)(.,
0?u
um in
则得线性规划模型：
niubxay ii,,2,1,0)(
该模型中只有三个决策变量。 ＃
例 15
某公司上午 8点到 21点各时段需要的服务人员数量如表 1，四个班次的作息时间及月工资如表 2。求既满足需求又使公司所付工资总额最少的人员安排。
6
5
4
3
2
1
00:2100:18
00:1800:16
00:1600:14
00:1400:12
00:1200:10
00:1000:8
10
20
30
10
25
20
序号 时间区间 需求人数表 1
七、人员时间安排问题
4
3
2
1
00:2100:12
00:2100:12
00:1700:8
00:1700:8
00:1800:17
00:1700:16
00:1400:13
00:1300:12
900
900
800
800
班次 工作时间 休息时间 月工资表 2
解 利用表 1、表 2的各时间区间端点，将营业时间区间细分，并用,1”表示工作，,0”表示休息，
得一 关联表 （表 3）。
00:2100:18
00:1800:17
00:1700:16
00:1600:14
00:1400:13
00:1300:12
00:1200:10
00:1000:8
10
20
20
30
10
10
25
20
1100
0100
1011
1111
1101
1110
0011
0011
4321
班 次时 段需求人数表 3
列 给出了各班在哪几个时段工作，
行 给出了各时段有哪几个班在工作。
设 为第 班安排的人数ix i )4,3,2,1(?i
则得整数规划模型：
4321 9 0 09 0 08 0 08 0 0m i n xxxxz
25.,21 xxts
10432 xxx
10431 xxx
304321 xxxx
20421 xxx
203?x
1043 xx
且为整数，0?ix 4,3,2,1?i
建该模型的 关键 是：找出各班次工作的关联表，
根据关联表写出约束条件。
有多余的约束条件
！
例 16 （选课策略）
某校规定，运筹学专业的学生毕业时必须至少学习过两门数学课、三门运筹学课和两门计算机课。
这些课程的编号、名称、学分、所属 类别和先修课要求如表。问：毕业时，学生最少可以学习哪些课程？
编号 名称 学分 所属类别 先修课要求
1 微积分 5 数学
2 线性代数 4 数学
3 最优化 4 数学；运筹学 微积分；线代
4 数据结构 3 数学；计算机 计算机编程
5 应用统计 4 数学；运筹学 微积分；线代
6 计算机模拟 3 计算机；运筹学 计算机编程
7 计算机编程 2 计算机
8 预测理论 2 运筹学 应用统计
9 数学实验 3 运筹学；计算机 微积分；线代课程情况表建立课程与课程类别的关联表：
110110100
101101000
000011111
类别数学计算机运筹学课程微积分 线代 优化 结构 统计 模拟 编程 预测 实验 需求量
2
3
2
9,,2,1
0
,1
iix
i,否则，
门课选修第则得 0－ 1规划模型：
是前例中需求量为 2,3,2的特别情形。
解编号 名称 先修课要求
1 微积分
2 线性代数
3 最优化 微积分；线代
4 数据结构 计算机编程
5 应用统计 微积分；线代
6 计算机模拟 计算机编程
7 计算机编程
8 预测理论 应用统计
9 数学实验 微积分；线代课程情况表
9
1
m i n
i
ixz 课程总数类别（需求）限制
2
3
2
9764
98653
54321
xxxx
xxxxx
xxxxx
..ts
先修要求
)(
)()(
ji
xx ji
先修后修
9,,2,1,10 jx j 或
13 xx?
23 xx?
74 xx?
02
0
0
02
0
02
219
58
76
215
74
213
xxx
xx
xx
xxx
xx
xxx
注意表述方法！
例 17 一个生产问题，有关数据如表。问如何安排生产可使总利润最大，产量之和最小。要求第二种原料用完。 C
B
A
01
24
54
6
48
80
1 0 080单位利润产品原料 单 耗 甲 乙 总量解 设 为甲，乙的产量21,xx
则 211m i n xxz
212 10080m a x xxz
8054.,21 xxts
4824 21 xx
61?x
0,21?xx
双目标规划模型一般形式：
)(min XQ
)(m a x XR
OX
MXFts
)(..
矛盾的八、线性 多 目标规划模型化成单目标规划模型化法一 )(min XQ aXRts?)(..
OX
MXF
)(
或 bXQts?)(..
)(m a x XR
OX
MXF
)(
化法二)()1()(m i n XRXQ
OX
MXFts
)(..
为目标权重或偏好系数。
均可看成参数，对不同的参数值求出最优解，然后加以讨论，选出 满意解 。
,,ba
例 17中，要求利润最大，同时产量之和最小，这种目标称为 理想目标 。这些目标往往是相互矛盾的，
不可能同时达到最优。更现实的做法是：给出目标值，将理想目标转化为 现实目标,求出 尽量达到 目标值的生产方案。
如要求：总利润 100010080 21 xx
产量之和 2021 xx
把目标函数转化成了约束条件引入正负偏差变量,,将多目标规划模型转化为目标规划模型。
id?id
九、线性目标规划模型
2021 xx
100010080 21 xx
8054 21 xx
4824 21 xx
61?x
20.,1121 ddxxts
Min
要,”成立，只需 min1d
1d
1 0 0 01 0 080 2221 ddxx
2d
8054 3321 ddxx
3d
4824 4421 ddxx 要“＝”成立，需 min 44 dd
)( 44 dd
6551 ddx
5
0,, iii ddx
目标规划模型达成函数一般方法：
bXf?)(
bXf?)(
bXf?)(
bddXf)(
bddXf)(
bddXf)(
d
dd
目标类型 目标规划格式 极小化
0, dd
注：
1,对于 硬约束,,,? 可不设正偏差变量,?d
即直接取 。0d 对于,”，可直接取 。 0d
2,关于 优先级 问题例如,上例中，目标的重要性依次为：
1° A,B两种原料一定不能超过限量；
2° 原料 B尽量用完；
3° 利润超过 1000；
4° 产量之和尽量少。
于是，达成函数可写为：
Min )( 14 dP)( 23 dP)( 531 ddP )( 442 ddP
1P 2P 3P,4P其中 iP 为 优先因子或 Min )( 1?d),( 2?d),( 53 dd ),( 44 dd
实验作业
1.某厂生产甲乙两种口味的饮料,每百箱甲饮料需用原料 6千克,工人 10名,可获利 10万元 ;每百箱乙饮料需用原料 5千克,工人 20名,可获利 9万元,今工厂共有原料 60千克,工人 150名,又由于其他条件所限甲饮料产量不超过 8百箱,问如何安排生产计划,即两种饮料各生产多少使获利最大,
79
2.某厂向用户提供发动机，合同规定，第一、二、
三季度末分别交货 40台,60台,80台．每季度的生产费用为 （元），其中 x是该季生产的台数．若交货后有剩余，可用于下季度交货，但需支付存储费，每台每季度 c元．已知工厂每季度最大生产能力为 100台，第一季度开始时无存货，设
a=50,b=0.2,c=4，问工厂应如何安排生产计划，
才能既满足合同又使总费用最低．
2bxaxxf
3.某商店有五位工作人员,经理 1人,主任 1人,售货员 3人,有关情况见下表,设广告费对销售额的贡献为其投入的 15倍,各工作人员的收入相当于其完成销售额的 5.5%.问如何安排才能达到以下的目标,P1保证全体人员正常工作时间 ;P2 至少完成销售额 70000元 ;P3主任的月收入不少于
1200元,售货员 A和 B的月收入不少于 600元和 400元 ;P4 全体人员加班时间不超过规定 ; P5广告费不超过 3000元,力争销售额增加 10000元,前者的重要性为后者的两倍,
每小时对销售额的贡献 (元 ) 每月总工时每月加班限量 (工时 )
经理 144 200 24
主任 96 200 24
售货员 A 54 172 52
售货员 B 30 160 32
售货员 C 9 100 32
