第四章 规划模型
4.1 奶制品的生产与销售
4.2 自来水输送与货机装运
4.3 汽车生产与原油采购
4.4 接力队选拔和选课策略
4.5 饮料厂的生产与检修
4.6 钢管和易拉罐下料
y
数学规划模型实际问题中的优化模型
mixgts
xxxxfzM a xM i n
i
T
n
,2,1,0)(..
),(),()( 1
或
x~决策变量 f(x)~目标函数 gi(x)?0~约束条件多元函数条件极值决策变量个数 n和约束条件个数 m较大最优解在可行域的边界上取得数学规划线性规划非线性规划整数规划重点在模型的建立和结果的分析企业生产计划
4.1 奶制品的生产与销售空间层次工厂级：根据外部需求和内部设备、人力、原料等条件，以最大利润为目标制订产品生产计划；
车间级：根据生产计划、工艺流程、资源约束及费用参数等，以最小成本为目标制订生产批量计划。
时间层次若短时间内外部需求和内部资源等不随时间变化，可制订 单阶段生产计划,否则应制订多阶段生产计划。
本节课题例 1 加工奶制品的生产计划
1桶牛奶
3公斤 A112小时
8小时 4公斤 A2
或获利 24元 /公斤获利 16元 /公斤
50桶牛奶 时间 480小时 至多加工 100公斤 A1
制订生产计划，使每天获利最大
35元可买到 1桶牛奶，买吗？若买，每天最多买多少?
可聘用临时工人，付出的工资最多是每小时几元?
A1的获利增加到 30元 /公斤，应否改变生产计划？
每天：
1桶牛奶
3公斤 A112小时
8小时 4公斤 A2
或获利 24元 /公斤获利 16元 /公斤
x1桶牛奶生产 A1 x2桶牛奶生产 A2
获利 24× 3x1 获利 16× 4 x2
原料供应 50
21 xx
劳动时间 480812 21 xx
加工能力 1003 1?x
决策变量目标函数
21 6472 xxzM ax
每天获利约束条件非负约束 0,21?xx
线性规划模型
(LP)
时间 480小时 至多加工 100公斤 A150桶牛奶每天模型分析与假设比例性可加性连续性
xi对目标函数的
“贡献”与 xi取值成正比x
i对约束条件的
“贡献”与 xi取值成正比x
i对目标函数的
“贡献”与 xj取值无关x
i对约束条件的
“贡献”与 xj取值无关 x
i取值连续
A1,A2每公斤的获利是与各自产量无关的常数每桶牛奶加工出 A1,A2的数量和时间是与各自产量无关的常数
A1,A2每公斤的获利是与相互产量无关的常数每桶牛奶加工出 A1,A2的数量和时间是与相互产量无关的常数加工 A1,A2的牛奶桶数是实数线性规划模型模型求解 图解法
x1
x2
0
A
B
C
D
l1
l2
l3
l4
l5
5021 xx
480812 21 xx
1003 1?x
0,21?xx
约束条件
50,211 xxl
4 8 0812,212 xxl
1003,13?xl
0:,0,2514 xlxl
21 6472 xxzM ax目标函数 Z=0
Z=2400
Z=3600
z=c (常数 ) ~等值线
c
在 B(20,30)点得到最优解目标函数和约束条件是线性函数可行域为直线段围成的凸多边形目标函数的等值线为直线最优解一定在凸多边形的某个顶点取得。
模型求解 软件实现 LINDO 6.1
max 72x1+64x2
st
2） x1+x2<50
3） 12x1+8x2<480
4） 3x1<100
end
OBJECTIVE FUNCTION VALUE
1) 3360.000
VARIABLE VALUE REDUCED COST
X1 20.000000 0.000000
X2 30.000000 0.000000
ROW SLACK OR SURPLUS DUALPRICES
2) 0.000000 48.000000
3) 0.000000 2.000000
4) 40.000000 0.000000
NO,ITERATIONS= 2
DO RANGE
(SENSITIVITY)
ANALYSIS? No
20桶牛奶生产 A1,30桶生产 A2，利润 3360元。
结果解释
OBJECTIVE FUNCTION VALUE
1) 3360.000
VARIABLE VALUE REDUCED COST
X1 20.000000 0.000000
X2 30.000000 0.000000
ROW SLACK OR SURPLUS DUALPRICES
2) 0.000000 48.000000
3) 0.000000 2.000000
4) 40.000000 0.000000
NO,ITERATIONS= 2
原料无剩余时间无剩余加工能力剩余 40
max 72x1+64x2
st
2） x1+x2<50
3） 12x1+8x2<480
4） 3x1<100
end
三种资源
―资源” 剩余为零的约束为紧约束（有效约束）
结果解释OBJECTIVE FUNCTION VALUE1) 3360.000
VARIABLE VALUE REDUCED COST
X1 20.000000 0.000000
X2 30.000000 0.000000
ROW SLACK OR SURPLUS DUALPRICES
2) 0.000000 48.000000
3) 0.000000 2.000000
4) 40.000000 0.000000
NO,ITERATIONS= 2
最优解下“资源”增加
1单位时“效益”的增量原料增加 1单位,利润增长 48
时间增加 1单位,利润增长 2
加工能力增长不影响利润影子价格
35元可买到 1桶牛奶，要买吗？ 35 <48,应该买！
聘用临时工人付出的工资最多每小时几元？ 2元！
RANGES IN WHICH THE BASIS IS UNCHANGED:
OBJ COEFFICIENT RANGES
VARIABLE CURRENT ALLOWABLE ALLOWABLE
COEF INCREASE DECREASE
X1 72.000000 24.000000 8.000000
X2 64.000000 8.000000 16.000000
RIGHTHAND SIDE RANGES
ROW CURRENT ALLOWABLE ALLOWABLE
RHS INCREASE DECREASE
2 50.000000 10.000000 6.666667
3 480.000000 53.333332 80.000000
4 100.000000 INFINITY 40.000000
最优解不变时目标函数系数允许变化范围
DO RANGE(SENSITIVITY) ANALYSIS? Yes
x1系数范围 (64,96)
x2系数范围 (48,72)
A1获利增加到 30元 /千克，应否改变生产计划
x1系数由 24?3=72
增加 为 30?3=90，
在 允许范围内不变！
(约束条件不变 )
结果解释
RANGES IN WHICH THE BASIS IS UNCHANGED:
OBJ COEFFICIENT RANGES
VARIABLE CURRENT ALLOWABLE ALLOWABLE
COEF INCREASE DECREASE
X1 72.000000 24.000000 8.000000
X2 64.000000 8.000000 16.000000
RIGHTHAND SIDE RANGES
ROW CURRENT ALLOWABLE ALLOWABLE
RHS INCREASE DECREASE
2 50.000000 10.000000 6.666667
3 480.000000 53.333332 80.000000
4 100.000000 INFINITY 40.000000
影子价格有意义时约束右端的允许变化范围原料最多增加 10
时间最多增加 53
35元可买到 1桶牛奶，每天最多买多少？ 最多买 10桶 !
(目标函数不变 )
例 2 奶制品的生产销售计划 在例 1基础上深加工
1桶牛奶
3千克 A112小时
8小时 4公斤 A2
或获利 24元 /公斤获利 16元 /公斤
0.8千克 B1
2小时,3元
1千克 获利 44元 /千克
0.75千克 B22小时,3元1千克 获利 32元 /千克制订生产计划，使每天净利润最大
30元可增加 1桶牛奶,3元可增加 1小时时间，应否投资？现投资 150元，可赚回多少？
50桶牛奶,480小时至多 100公斤 A1
B1,B2的获利经常有 10%的波动，对计划有无影响？
1桶牛奶
3千克 A112小时
8小时 4千克 A2
或获利 24元 /千克获利 16元 /kg
0.8千克 B12小时,3元1千克 获利 44元 /千克
0.75千克 B22小时,3元1千克 获利 32元 /千克出售 x1 千克 A1,x2 千克 A2,X3千克 B1,x4千克 B2
原料供应劳动时间加工能力决策变量目标函数 利润约束条件非负约束
0,61?xx?
x5千克 A1加工 B1,x6千克 A2加工 B2
654321 3332441624 xxxxxxzM a x
5043 6251 xxxx
48022
)(2)(4
65
6251
xx
xxxx
10051 xx
附加约束 53 80 x.x?
64 750 x.x?
模型求解软件实现 LINDO 6.1
5043)2 6251 xxxx
48022
)(2)(4)3
65
6251
xx
xxxx
OBJECTIVE FUNCTION VALUE
1) 3460.800
VARIABLE VALUE REDUCED COST
X1 0.000000 1.680000
X2 168.000000 0.000000
X3 19.200001 0.000000
X4 0.000000 0.000000
X5 24.000000 0.000000
X6 0.000000 1.520000
ROW SLACK OR SURPLUS DUALPRICES
2) 0.000000 3.160000
3) 0.000000 3.260000
4) 76.000000 0.000000
5) 0.000000 44.000000
6) 0.000000 32.000000
NO,ITERATIONS= 2
6 0 0334)2 6521 xxxx 4
4 8 04624)3 6521 xxxx
DO RANGE
(SENSITIVITY)
ANALYSIS? No
OBJECTIVE FUNCTION VALUE
1) 3460.800
VARIABLE VALUE REDUCED COST
X1 0.000000 1.680000
X2 168.000000 0.000000
X3 19.200001 0.000000
X4 0.000000 0.000000
X5 24.000000 0.000000
X6 0.000000 1.520000
ROW SLACK OR SURPLUS DUALPRICES
2) 0.000000 3.160000
3) 0.000000 3.260000
4) 76.000000 0.000000
5) 0.000000 44.000000
6) 0.000000 32.000000
NO,ITERATIONS= 2
结果解释每天销售 168 千克 A2
和 19.2 千克 B1，
利润 3460.8（元）
8桶牛奶加工成 A1,42桶牛奶加工成 A2，
将得到的 24千克 A1全部加工成 B1
除加工能力外均为紧约束结果解释
OBJECTIVE FUNCTION VALUE
1) 3460.800
VARIABLE VALUE REDUCED COST
X1 0.000000 1.680000
X2 168.000000 0.000000
X3 19.200001 0.000000
X4 0.000000 0.000000
X5 24.000000 0.000000
X6 0.000000 1.520000
ROW SLACK OR SURPLUS DUALPRICES
2) 0.000000 3.160000
3) 0.000000 3.260000
4) 76.000000 0.000000
5) 0.000000 44.000000
6) 0.000000 32.000000
增加 1桶牛奶使利润增长 3.16× 12=37.92
5043)2 6251 xxxx
6 0 0334)2 6521 xxxx 4
增加 1小时时间使利润增长 3.26
30元可增加 1桶牛奶,3元可增加 1小时时间，
应否投资？现投资 150元，可赚回多少？
投资 150元增加 5桶牛奶，
可赚回 189.6元。（大于增加时间的利润增长）
结果解释 B1,B2的获利有 10%的波动，对计划有无影响
RANGES IN WHICH THE BASIS IS UNCHANGED:
OBJ COEFFICIENT RANGES
VARIABLE CURRENT ALLOWABLE ALLOWABLE
COEF INCREASE DECREASE
X1 24.000000 1.680000 INFINITY
X2 16.000000 8.150000 2.100000
X3 44.000000 19.750002 3.166667
X4 32.000000 2.026667 INFINITY
X5 -3.000000 15.800000 2.533334
X6 -3.000000 1.520000 INFINITY
…… ……
DO RANGE
(SENSITIVITY)
ANALYSIS? Yes
B1获利下降 10%，超出 X3 系数允许范围
B2获利上升 10%，超出 X4 系数允许范围波动对计划有影响生产计划应重新制订：如将 x3的系数改为 39.6
计算，会发现结果有很大变化。
4.2 自来水输送与货机装运生产、生活物资从若干供应点运送到一些需求点，
怎样安排输送方案使运费最小，或利润最大；
运输问题各种类型的货物装箱，由于受体积、重量等限制，
如何搭配装载，使获利最高，或装箱数量最少。
其他费用,450元 /千吨
应如何分配水库供水量，公司才能获利最多？
若水库供水量都提高一倍，公司利润可增加到多少？
元 /千吨 甲 乙 丙 丁
A 160 130 220 170
B 140 130 190 150
C 190 200 230 /
引水管理费例 1 自来水输送收入,900元 /千吨支出
A,50
B,60
C,50
甲,30； 50
乙,70； 70
丙,10； 20
丁,10； 40
水库供水量(
千吨)
小区基本用水量(
千吨)
小区额外用水量(
千吨)（以天计）
总供水量,160
确定送水方案 使利润最大问题分析
A,50
B,60
C,50
甲,30； 50
乙,70； 70
丙,10； 20
丁,10； 40
< 总需求量,120+180=300
总收入 900?160=144,000(元 ) 收入,900元 /千吨其他费用,450元 /千吨支出 引水管理费其他 支出 450?160=72,000(元 )
使引水管理费最小供应限制约束条件需求限制线性规划模型
(LP)
5014131211 xxxx
50
60
333231
24232221
xxx
xxxx
8030 312111 xxx
14070 322212 xxx
3010 332313 xxx
5010 2414 xx
目标函数
33323124232221
14131211
2 302 001 901 501 901 301 40
1 702 201 301 60
xxxxxxx
xxxxZM i n
水库 i 向 j 区的日供水量为 xij（ x34=0）决策变量模型建立 确定 3个水库向 4个小区的供水量模型求解 OBJECTIVE FUNCTION VALUE
1) 24400.00
VARIABLE VALUE REDUCED COST
X11 0.000000 30.000000
X12 50.000000 0.000000
X13 0.000000 50.000000
X14 0.000000 20.000000
X21 0.000000 10.000000
X22 50.000000 0.000000
X23 0.000000 20.000000
X24 10.000000 0.000000
X31 40.000000 0.000000
X32 0.000000 10.000000
X33 10.000000 0.000000
利润 =总收入 -其它费用 - 引 水 管 理 费
=144000-72000-24400
= 47600（ 元 ）
A(50)
B(60)
C(50)
甲 (30;50)
乙 (70;70)
丙 (10;20)
丁 (10;40)
50
50 40
10
10
引水管理费 24400(元 )
目标函数总供水量 (320) > 总需求量 (300)
每个水库最大供水量都提高一倍利润 = 收入 (900) –其它费用 (450) –引水管理费利润 (元 /千吨 ) 甲 乙 丙 丁
A 290 320 230 280
B 310 320 260 300
C 260 250 220 /
33323124232221
14131211
220250260300260320310
280230320290
xxxxxxx
xxxxZM ax
供应限制 B,C 类似处理 50:A 14131211 xxxx
10014131211 xxxx
问题讨论确定送水方案 使利润最大需求约束可以不变求解 OBJECTIVE FUNCTION VALUE
1) 88700.00
VARIABLE VALUE REDUCED COST
X11 0.000000 20.000000
X12 100.000000 0.000000
X13 0.000000 40.000000
X14 0.000000 20.000000
X21 30.000000 0.000000
X22 40.000000 0.000000
X23 0.000000 10.000000
X24 50.000000 0.000000
X31 50.000000 0.000000
X32 0.000000 20.000000
X33 30.000000 0.000000
这类问题一般称为
“运输问题”
(Transportation
Problem)
总利润 88700（ 元 ）
A(100)
B(120)
C(100)
甲 (30;50)
乙 (70;70)
丙 (10;20)
丁 (10;40)
40
100
50 30
50
30
如何 装运，
使本次飞行获利最大？
三个货舱 最大 载 重 (吨 ),最大容积 (米 3)例 2 货机装运重量（吨） 空间 ( 米 3/
吨）
利润（元 /
吨）
货物 1 18 480 3100
货物 2 15 650 3800
货物 3 23 580 3500
货物 4 12 390 2850
三个货舱中实际载重必须与其最大 载 重成比例前仓：
10； 6800
中仓：
16； 8700
后仓：
8； 5300
飞机平衡决策变量
xij--第 i 种货物装入第 j 个货舱的重量 (吨）
i=1,2,3,4,j=1,2,3 (分别代表前、中、后仓 )
模型假设每种货物可以分割到任意小；
货机装运每种货物可以在一个或多个货舱中任意分布；
多种货物可以混装，并保证不留空隙；
模型建立货舱容积目标函数
(利润 )
约束条件
)(28 50)(35 00
)(38 00)(31 00
434241333231
232221131211
xxxxxx
xxxxxxZM ax
6 8 0 03 9 05 8 06 5 04 8 0 41312111 xxxx
8 7 0 0390580650480 42322212 xxxx
5 3 0 03 9 05 8 06 5 04 8 0 43332313 xxxx
货机装运 模型建立货舱重量
1041312111 xxxx
1642322212 xxxx
843332313 xxxx
10；
6800
16；
8700
8；
5300
xij--第 i 种货物装入第 j 个货舱的重量约束条件平衡要求
8
16
10
43332313
42322212
41312111
xxxx
xxxx
xxxx
货物供应 18131211 xxx
15232221 xxx
23333231 xxx
12434241 xxx
货机装运 模型建立
10；
6800
16；
8700
8；
5300
xij--第 i 种货物装入第 j 个货舱的重量
OBJECTIVE FUNCTION VALUE
1) 121515.8
VARIABLE VALUE REDUCED COST
X11 0.000000 400.000000
X12 0.000000 57.894737
X13 0.000000 400.000000
X21 10.000000 0.000000
X22 0.000000 239.473679
X23 5.000000 0.000000
X31 0.000000 0.000000
X32 12.947369 0.000000
X33 3.000000 0.000000
X41 0.000000 650.000000
X42 3.052632 0.000000
X43 0.000000 650.000000
货物 2：前仓 10,后仓 5；
货物 3,中仓 13,后仓 3；
货物 4,中仓 3。
货机装运 模型求解最大利润约 121516元货物 ~供应点货舱 ~需求点平衡要求运输问题运输问题的扩展
如果生产某一类型汽车，则至少要生产 80辆，
那么最优的生产计划应作何改变？
例 1 汽车厂生产计划汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量。
小型 中型 大型 现有量钢材（吨） 1.5 3 5 600
劳动时间（小时） 280 250 400 60000
利润（万元） 2 3 4
制订月生产计划,使工厂的利润最大 。
4.3 汽车生产与原油采购设每月生产小、中、大型汽车的数量分别为 x1,x2,x3
321 432 xxxzM a x
600535.1.,321 xxxts
6 0 0 0 0400250280 321 xxx
0,,321?xxx
汽车厂生产计划模型建立 小型 中型 大型 现有量钢材 1.5 3 5 600
时间 280 250 400 60000
利润 2 3 4
线性规划模型
(LP)
模型求解
3） 模型中增加条件,x1,x2,x3 均为整数,重新求解 。
OBJECTIVE FUNCTION VALUE
1) 632.2581
VARIABLE VALUE REDUCED COST
X1 64.516129 0.000000
X2 167.741928 0.000000
X3 0.000000 0.946237
ROW SLACK OR SURPLUS DUAL PRICES
2) 0.000000 0.731183
3) 0.000000 0.003226
结果为小数，
怎么办？
1）舍去小数：取 x1=64,x2=167，算出目标函数值 z=629，与
LP最优值 632.2581相差不大。
2） 试探：如取 x1=65,x2=167； x1=64,x2=168等,计算函数值 z,通过比较可能得到更优的解 。
但必须检验它们是否满足约束条件。为什么？
IP可用 LINDO直接求解整数规划 (Integer Programming,简记 IP)
―gin 3‖表示,前 3个变量为整数,,等价于：
gin x1
gin x2
gin x3
IP 的最优解 x1=64,x2=168,x3=0，最优值 z=632
max 2x1+3x2+4x3
st
1.5x1+3x2+5x3<600
280x1+250x2+400x3<60000
end
gin 3
OBJECTIVE FUNCTION VALUE
1) 632.0000
VARIABLE VALUE REDUCED COST
X1 64.000000 -2.000000
X2 168.000000 -3.000000
X3 0.000000 -4.000000
321 432 xxxzM a x
600535.1.,321 xxxts
60000400250280 321 xxx
为非负整数321,,xxx
模型求解
IP 结果输出其中 3个 子模型应 去掉，然后逐一求解，比较目标函数值，
再加上整数约束，得最优解：
80,0,0 321 xxx
0,80,0 321 xxx
80,80,0 321 xxx
0,0,80 321 xxx
0,80,80 321 xxx
80,0,80 321 xxx
80,80,80 321 xxx
0,,321?xxx
方法 1：分解为 8个 LP子模型汽车厂生产计划
若生产某类汽车，则至少生产 80辆，求生产计划。
321 432 xxxzM a x
600535.1.,321 xxxts
60000400250280 321 xxx
x1,x2,,x3=0 或?80
x1=80,x2= 150,x3=0，最优值 z=610
LINDO中对 0-
1变量的限定：
int y1
int y2
int y3
方法 2,引入 0-1变量，化为整数规划
M为大的正数，
可取 1000
OBJECTIVE FUNCTION VALUE
1) 610.0000
VARIABLE VALUE REDUCED COST
X1 80.000000 -2.000000
X2 150.000000 -3.000000
X3 0.000000 -4.000000
Y1 1.000000 0.000000
Y2 1.000000 0.000000
Y3 0.000000 0.000000
若生产某类汽车，则至少生产 80辆，求生产计划。
x1=0 或?80
x2=0 或?80
x3=0 或?80
}1,0{,80,11111 yyxMyx
}1,0{,80,22222 yyxMyx
}1,0{,80,33333 yyxMyx
最优解同前
NLP 虽然可用现成的数学软件求解 (如 LINGO,
MATLAB),但是其结果常依赖于初值的选择 。
方法 3,化为非线性规划非线性规划（ Non- Linear Programming，简记 NLP）
实践表明,本例仅当初值非常接近上面方法算出的最优解时,才能得到正确的结果 。
若生产某类汽车，则至少生产 80辆，求生产计划。
x1=0 或?80
x2=0 或?80
x3=0 或?80
0)80( 11xx
0)80( 22xx
0)80( 33xx
应如何安排原油的采购和加工？
例 2 原油采购与加工市场上可买到不超过 1500吨的原油 A：
购买量不超过 500吨时的单价为 10000元 /吨；
购买量超过 500吨但不超过 1000吨时，超过 500吨的部分 8000元 /吨；
购买量超过 1000吨时，超过 1000吨的部分 6000元 /吨。
售价 4800元 /吨售价 5600元 /吨库存 500吨库存 1000吨汽油甲
(A?50%) 原油 A
原油 B 汽油乙
(A?60%)
决策变量目标函数问题分析
利润：销售汽油的收入 - 购买原油 A的支出
难点：原油 A的购价与购买量的关系较复杂
)()(6.5)(8.4 22122111 xcxxxxzM ax
甲 (A?50%) A
B 乙 (A?60%)
购买 x?
x11
x12
x21
x22
4.8千元 /吨
5.6千元 /吨原油 A的购买量,原油 A,B生产 汽油 甲,乙的数量
c(x) ~ 购买原油 A的支出利润 (千元 )
c(x)如何表述？
原油供应约束条件
xxx 5 0 01211
1 0 0 02221 xx
1500?x
5 0 0 )1( 1 0 0 0 3 0 0 06
1 0 0 0 )( 5 0 0 1 0 0 0 8
5 0 0 )(0 10
)(
xx
xx
xx
xc
x? 500吨单价为 10千 元 /吨；
500吨? x? 1000吨，超过 500吨的 8千 元 /吨；
1000吨?x? 1500吨，超过 1000吨的 6千 元 /吨。
目标函数购买 x?
A
B
x11
x12
x21
x22
库存 500吨库存 1000吨
目标函数中 c(x)不是线性函数，是非线性规划；
对于用分段函数定义的 c(x)，一般的非线性规划软件也难以输入和求解；
想办法将模型化简，用现成的软件求解。
汽油含原油 A
的比例限制
5.0
2111
11?
xx
x
6.0
2212
12?
xx
x
2111 xx
2212 32 xx
约束条件甲 (A?50%) A
B 乙 (A?60%)
x11
x12
x21
x22
x1,x2,x3 ~以价格 10,8,6(千元 /吨 )采购 A的吨数目标函数只有当以 10千元 /吨的价格购买 x1=500(吨 )时，才能以
8千元 /吨的价格购买 x2
方法 1
)6810()(6.5)(8.4 32122122111 xxxxxxxzM a x
0)5 0 0( 32 xx 5 0 0,,0 321 xxx
非线性规划模型,可以用 LINGO求解模型求解
x= x1+x2+x3,c(x) = 10x1+8x2+6x3
500吨? x? 1000吨，超过 500吨的 8千 元 /吨增加约束
0)500( 21 xx
方法 1,LINGO求解Model:Max= 4.8*x11 + 4.8*x21 + 5.6*x12
+ 5.6*x22 - 10*x1 - 8*x2 - 6*x3;
x11+x12 < x + 500;
x21+x22 < 1000;
x11 - x21 > 0;
2*x12 - 3*x22 > 0;
x=x1+x2+x3;
(x1 - 500) * x2=0;
(x2 - 500) * x3=0;
x1 < 500;
x2 < 500;
x3 < 500;
x > 0;
x11 > 0;
x12 > 0;
x21 > 0;
x22 > 0;
x1 > 0;
x2 > 0;
x3 > 0;
end
Objective value,4800.000
Variable Value Reduced Cost
X11 500.0000 0.0000000E+00
X21 500.0000 0.0000000E+00
X12 0.0000000E+00 0.0000000E+00
X22 0.0000000E+00 0.0000000E+00
X1 0.1021405E-13 10.00000
X2 0.0000000E+00 8.000000
X3 0.0000000E+00 6.000000
X 0.0000000E+00 0.0000000E+00
LINGO得到的是局部最优解，还能得到更好的解吗？
用库存的 500吨原油 A,500吨原油 B
生产汽油甲，不购买新的原油 A，
利润为 4,800千 元。
y1,y2,y3=1 ~以价格 10,8,6(千元 /吨 )采购 A
增加约束方法 2
0-1线性规划模型,可用 LINDO求解
112 500500 yxy 223 5 0 05 0 0 yxy
33 5 00 yx?
y1,y2,y3 =0或 1
OBJECTIVE FUNCTION VALUE
1) 5000.000
VARIABLE VALUE REDUCED
COST
Y1 1.000000 0.000000
Y2 1.000000 2200.000000
Y3 1.000000 1200.000000
X11 0.000000 0.800000
X21 0.000000 0.800000
X12 1500.000000 0.000000
X22 1000.000000 0.000000
X1 500.000000 0.000000
X2 500.000000 0.000000
X3 0.000000 0.400000
X 1000.000000 0.000000
购买 1000吨原油 A，与库存的 500吨原油 A和
1000吨原油 B一起，生产汽油乙，利润为 5,000
千元 。
x1,x2,x3 ~以价格 10,8,6(千元 /吨 )采购 A的吨数
y=0? x=0
x>0? y=1
优于方法 1的结果
b1 b2 b3 b4
方法 3
b1? x?b2,x= z1b1+z2b2，
z1+z2=1,z1,z2?0,
c(x)= z1c(b1)+z2c(b2).
c(x)
x
12000
9000
5000
0 500 1000 1500
b2? x? b3,x= z2b2+z3b3，
z2+z3=1,z2,z3? 0,
c(x)= z2c(b2)+z3c(b3),
b3? x? b4,x= z3b3+z4b4，
z3+z4=1,z3,z4? 0,
c(x)= z3c(b3)+z4c(b4),
500)1( 1 0 0 0 30006
1 0 0 0 )( 5 0 0 1000 8
500)(0 10
)(
xx
xx
xx
xc
直接处理处理分段线性函数 c(x)
IP模型,LINDO求解，得到的结果与方法 2相同,
处理分段线性函数,方法 3更具一般性
44332211 bzbzbzbzx
)()()()()( 44332211 bczbczbczbczxc
bk?x?bk+1?yk=1,否则,yk=0
3432321211,,,yzyyzyyzyz
)4,3,2,1(0,14321 kzzzzz k
10,,,1 321321 或 yyyyyy
方法 3
bk?x?bk+1,x= zkbk+z k+1 bk+1
zk+zk+1 =1,zk,zk+1?0,
c(x)= zkc(bk)+zk+1 c(bk+1 ).
c(x)
x
12000
9000
5000
0 500 1000 1500
b1 b2 b3 b4
对于 k=1,2,3
分派问题
4.4 接力队选拔和选课策略若干项任务分给一些候选人来完成，每人的专长不同，
完成每项任务取得的效益或需要的资源就不同，如何分派任务使获得的总效益最大，或付出的总资源最少。
若干种策略供选择，不同的策略得到的收益或付出的成本不同，各个策略之间有相互制约关系，如何在满足一定条件下作出决择，使得收益最大或成本最小。
丁的蛙泳成绩退步到 1’15‖2；戊的自由泳成绩进步到 57‖5,组成接力队的方案是否应该调整？
如何选拔队员组成 4?100米混合泳接力队?
例 1 混合泳接力队的选拔甲 乙 丙 丁 戊蝶泳 1’06‖8 57‖2 1’18‖ 1’10‖ 1’07‖4
仰泳 1’15‖6 1’06‖ 1’07‖8 1’14‖2 1’11‖
蛙泳 1’27‖ 1’06‖4 1’24‖6 1’09‖6 1’23‖8
自由泳 58‖6 53‖ 59‖4 57‖2 1’02‖4
5名候选人的 百米成绩穷举法,组成接力队的方案共有 5!=120种 。
目标函数若选择队员 i参加泳姿 j 的比赛，记 xij=1,否则记 xij=0
0-1规划模型 cij(秒 )~队员 i 第 j 种泳姿的百米成绩约束条件每人最多入选泳姿之一
cij i=1 i=2 i=3 i=4 i=5
j=1 66.8 57.2 78 70 67.4
j=2 75.6 66 67.8 74.2 71
j=3 87 66.4 84.6 69.6 83.8
j=4 58.6 53 59.4 57.2 62.4
4
1
5
1j i
ijij xcZM i n
每种泳姿有且只有 1人
5,1,1
4
1
ix
j
ij
4,1,1
5
1
jx
i
ij
模型求解最优解,x14 = x21 = x32 =
x43 = 1,其它变量为 0;
成绩为 253.2(秒 )=4’13‖2
MIN 66.8x11+75.6x12+87x13+58.6x14
+… …
+67.4x51+71 x52+83.8x53+62.4x54
SUBJECT TO
x11+x12+x13+x14 <=1
… …
x41+x42+x43+x44 <=1
x11+x21+x31+x41+x51 =1
… …
x14+x24+x34+x44+x54 =1
END
INT 20
输入 LINDO求解甲 乙 丙 丁 戊蝶泳 1’06‖8 57‖2 1’18‖ 1’10‖ 1’07‖4
仰泳 1’15‖6 1’06‖ 1’07‖8 1’14‖2 1’11‖
蛙泳 1’27‖ 1’06‖4 1’24‖6 1’09‖6 1’23‖8
自由泳 58‖6 53‖ 59‖4 57‖2 1’02‖4
甲 ~ 自由泳、乙 ~ 蝶泳、
丙 ~ 仰泳、丁 ~ 蛙泳,
丁蛙泳 c43=69.6?75.2，戊自由泳 c54=62.4?
57.5,方案是否调整？ 敏感性分析？
乙 ~ 蝶泳、丙 ~ 仰泳、
丁 ~ 蛙泳、戊 ~ 自由泳
IP规划一般没有与 LP规划相类似的理论,LINDO
输出的敏感性分析结果通常是没有意义的。
最优解,x21 = x32 = x43 = x51 = 1,成绩为 4’17‖7
c43,c54 的新数据重新输入模型，用 LINDO求解指派 (Assignment)问题,每项任务有且只有一人承担，
每人只能承担一项,效益不同，怎样分派使总效益最大,
讨论甲 ~ 自由泳、乙 ~ 蝶泳、
丙 ~ 仰泳、丁 ~ 蛙泳,
原方案为了选修课程门数最少，应学习哪些课程？
例 2 选课策略要求至少选两门数学课、三门运筹学课和两门计算机课课号 课名 学分 所属类别 先修课要求
1 微积分 5 数学
2 线性代数 4 数学
3 最优化方法 4 数学；运筹学 微积分；线性代数
4 数据结构 3 数学；计算机 计算机编程
5 应用统计 4 数学；运筹学 微积分；线性代数
6 计算机模拟 3 计算机；运筹学 计算机编程
7 计算机编程 2 计算机
8 预测理论 2 运筹学 应用统计
9 数学实验 3 运筹学；计算机 微积分；线性代数选修课程最少，且学分尽量多，应学习哪些课程？
0-1规划模型 决策变量目标函数
xi=1 ~选修课号 i 的课程（ xi=0 ~不选）
9
1i
ixZM i n
选修课程总数最少约束条件最少 2门数学课，
3门运筹学课，
2门计算机课。
254321 xxxxx
398653 xxxxx
29764 xxxx
课号 课名 所属类别
1 微积分 数学
2 线性代数 数学
3 最优化方法 数学；运筹学
4 数据结构 数学；计算机
5 应用统计 数学；运筹学
6 计算机模拟 计算机；运筹学
7 计算机编程 计算机
8 预测理论 运筹学
9 数学实验 运筹学；计算机先修课程要求
74 xx?
02 215 xxx
076 xx
058 xx
02 219 xxx
最优解,x1 = x2 = x3 = x6 = x7 = x9
=1,其它为 0； 6门课程，总学分 21
02 213 xxx
0-1规划模型 约束条件
x3=1必有 x1 = x2 =1
2313,xxxx
074 xx
模型求解（ LINDO）
课号 课名 先修课要求
1 微积分
2 线性代数
3 最优化方法 微积分；线性代数
4 数据结构 计算机编程
5 应用统计 微积分；线性代数
6 计算机模拟 计算机编程
7 计算机编程
8 预测理论 应用统计
9 数学实验 微积分；线性代数学分最多多目标优化的处理方法：化成单目标优化。
两目标 (多目标 )规划
9876
54321
3223
43445
xxxx
xxxxxWM a x
},{ WZM i n?
讨论：选修课程最少，学分尽量多，应学习哪些课程？
9
1i
ixZM i n
课程最少
以 学分最多为目标，
不管课程多少。
以课程最少 为目标，
不管学分多少。
最优解如上,6门课程，总学分 21 。
最优解显然是选修所有 9门课程 。
多目标规划
在 课程最少的前提下以 学分最多为目标。
最优解,x1 = x2 = x3 = x5
= x7 = x9 =1,其它为 0； 总学分由 21增至 22。
注意：最优解不唯一！
课号 课名 学分
1 微积分 5
2 线性代数 4
3 最优化方法 4
4 数据结构 3
5 应用统计 4
6 计算机模拟 3
7 计算机编程 2
8 预测理论 2
9 数学实验 3
LINDO无法告诉优化问题的解是否唯一。
可将 x9 =1 易为 x6 =1
增加约束,
以学分最多为目标求解。
6
9
1
i
ix
多目标规划
对学分数和课程数加权形成一个目标，如三七开。
9876
54321
3223
43445
xxxx
xxxxxW
9
1i
ixZ
最优解,x1 = x2 = x3 = x4
= x5 = x6 = x7 = x9 =1，
其它为 0； 总学分 28。
课号 课名 学分
1 微积分 5
2 线性代数 4
3 最优化方法 4
4 数据结构 3
5 应用统计 4
6 计算机模拟 3
7 计算机编程 2
8 预测理论 2
9 数学实验 3
WZWZYM i n 3.07.021
讨论与思考
WZYM i n 21
3/21
1,0,1 2121
最优解 与?1=0,?2=1的结果相同 ——学分最多
4/31
多目标规划
9876
54321
3223
43445
xxxx
xxxxxW
9
1i
ixZ
最优解 与?1=1,?2=0的结果相同 ——课程最少
4.5 饮料厂的生产与检修单阶段生产计划多阶段生产计划
生产批量问题
企业生产计划考虑与产量无关的固定费用给优化模型求解带来新的困难外部需求和内部资源随时间变化
安排生产计划,满足每周的需求,使 4周总费用最小。
存贮费,每周每千箱饮料 0.2千元。
例 1 饮料厂的生产与检修计划
在 4周内安排一次设备检修，占用当周 15千箱生产能力，能使检修后每周增产 5千箱，检修应排在哪一周?
周次 需求量 (千箱 ) 生产能力 (千箱 ) 成本 (千元 /千箱 )
1 15 30 5.0
2 25 40 5.1
3 35 45 5.4
4 25 20 5.5
合计 100 135
某种饮料 4周的需求量、生产能力和成本问题分析
除第 4周外每周的生产能力超过每周的需求；
生产成本逐周上升；
前几周应多生产一些。
周次 需求 能力
1 15 30
2 25 40
3 35 45
4 25 20
合计 100 135
成本
5.0
5.1
5.4
5.5
饮料厂在第 1周开始时没有库存；
从费用最小考虑,第 4周末不能有库存；
周末有库存时需支出一周的存贮费；
每周末的库存量等于下周初的库存量。
模型假设目标函数约束条件产量、库存与需求平衡决策变量
)(2.05.54.51.50.5 3214321 yyyxxxxzM i n
1511 yx
25212 yyx
35323 yyx
2534 yx
20,45
40,30
43
21
xx
xx
能力限制非负限制
0,,,,,,3214321?yyyxxxx
模型建立
x1~ x4：第 1~4周 的生产量
y1~ y3：第 1~3周末 库存量周次 需求 能力
1 15 30
2 25 40
3 35 45
4 25 20
成本
5.0
5.1
5.4
5.5 存贮费,0.2 (千元 /周?千箱 )
模型求解
4周生产计划的总费用为 528 (千元 )
最优解,x1~ x4,15,40,25,20；
y1~ y3,0,15,5,
周次 需求 能力
1 15 30
2 25 40
3 35 45
4 25 20
成本
5.0
5.1
5.4
5.5
产量
15
40
25
20
库存
0
15
5
0
LINDO求解检修计划
0-1变量 wt,wt=1~ 检修安排在第 t周 (t=1,2,3,4）
在 4周内安排一次设备检修，占用当周 15千箱生产能力，能使检修后每周增产 5千箱，检修应排在哪一周?
检修安排在任一周均可周次 需求 能力
1 15 30
2 25 40
3 35 45
4 25 20
成本
5.0
5.1
5.4
5.5
约束条件能力限制 20
45
40
30
4
3
2
1
x
x
x
x 3015
11 wx
122 54015 wwx
1233 554515 wwwx
32144 5552015 wwwwx
产量、库存与需求平衡条件不变增加约束条件：检修 1次
14321 wwww
检修计划 目标函数不变
0-1变量 wt,wt=1~ 检修安排在第 t周 (t=1,2,3,4）
LINDO求解总费用由 528千元降 为 527千元检修所导致的生产能力提高的作用,
需要更长的时间才能得到充分体现。
最优解,w1=1,w2,w3,w4=0;
x1~ x4,15,45,15,25；
y1~ y3,0,20,0,
例 2 饮料的生产批量问题
安排生产计划,满足每周的需求,使 4周总费用最小。
存贮费,每周每千箱饮料 0.2千元。
饮料厂使用同一条生产线轮流生产 多种 饮料。
若某周开工生产 某种 饮料,需支出 生产准备费 8千元。
某种饮料 4周的需求量、生产能力和成本周次 需求量 (千箱 ) 生产能力 (千箱 ) 成本 (千元 /千箱 )
1 15 30 5.0
2 25 40 5.1
3 35 45 5.4
4 25 20 5.5
合计 100 135
生产批量问题的一般提法
ct ~时段 t 生产费用 (元 /件 )；
ht ~时段 t (末 )库存费 (元 /件 )；
st ~时段 t 生产准备费 (元 )；
dt ~时段 t 市场需求 (件 )；
Mt ~时段 t 生产能力 (件 )。
假设初始库存为 0
制订生产计划,满足需求,并使 T个时段的总费用最小。
tttt dyxy 1
)( m i n
1
ttttt
T
t
t yhxcwsz
0,,00 ttT yxyy
tt
t
t
t Mxx
xw?
,0,0
,0,1
决策变量
xt ~时段 t 生产量；
yt ~时段 t (末 )库存量；
wt =1 ~时段 t 开工 生产
(wt =0 ~不开工 )。
目标约束混合 0-1规划模型最优解,x1~ x4,15,40,45,0； 总费用,554.0(千元 )
生产批量问题的一般提法
tttt dyxyts 1..
)( m i n
1
ttttt
T
t
t yhxcwsz
Tt
yxyy ttT
,2,1
0,,00
tt
t
t
t Mxx
xw?
,0,0
,0,1
将所给参数代入模型，用 LINDO求解
0 ttt wMx
生产中通过切割、剪裁、冲压等手段，将原材料加工成所需大小
§ 6 钢管和易拉罐下料原料下料问题按照工艺要求，确定下料方案，
使所用材料最省，或利润最大问题 1,如何下料最节省?
例 1 钢管下料问题 2,客户增加需求：
原料钢管,每根 19米
4米 50根 6米 20根 8米 15根客户需求节省的标准是什么？
由于采用不同切割模式太多，会增加生产和管理成本，
规定切割模式不能超过 3种。如何下料最节省？
5米 10根按照客户需要在一根原料钢管上安排切割的一种组合。
切割模式余料 1米4米 1根 6米 1根 8米 1根余料 3米4米 1根 6米 1根 6米 1根合理切割模式 的余料应小于客户需要钢管的最小尺寸余料 3米8米 1根 8米 1根钢管下料为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？
合理切割模式
2,所用原料钢管总根数最少模式 4米钢管根数 6米钢管根数 8米钢管根数 余料 (米 )
1 4 0 0 3
2 3 1 0 1
3 2 0 1 3
4 1 2 0 3
5 1 1 1 1
6 0 3 0 1
7 0 0 2 3
钢管下料问题 1
两种标准
1,原料钢管剩余总余量最小
xi ~按第 i 种模式切割的原料钢管根数 (i=1,2,…7 )
约束 满足需求决策变量目标 1（总余量）
76543211 3333 xxxxxxxZM i n
50234 54321 xxxxx
2032 6542 xxxx
152 753 xxx
按模式 2切割 12根,按模式 5切割 15根，余料 27米模式
4米根数
6米根数
8米根数余料
1 4 0 0 3
2 3 1 0 1
3 2 0 1 3
4 1 2 0 3
5 1 1 1 1
6 0 3 0 1
7 0 0 2 3
需求
50 20 15
最优解,x2=12,x5=15,
其余为 0；
最优值,27。
整数约束,xi 为整数当余料没有用处时,通常以总根数最少为目标
76543212 xxxxxxxZM i n
目标 2（总根数）
钢管下料问题 1
约束条件不变最优解,x2=15,
x5=5,x7=5,
其余为 0；
最优值,25。
50234 54321 xxxxx
2032 6542 xxxx
152 753 xxx
xi 为整数按模式 2切割 15根，
按模式 5切割 5根，
按模式 7切割 5根，
共 25根，余料 35米 虽余料增加 8米，但减少了 2根与 目标 1的结果“共切割
27根，余料 27米” 相比钢管下料问题 2
对大规模问题,用模型的约束条件界定合理模式增加一种需求,5米 10根；切割 模式不超过 3种 。
现有 4种 需求,4米 50根,5米 10根,6米 20根,8米
15根，用枚举法确定合理切割模式，过于复杂。
决策变量
xi ~按第 i 种模式切割的原料钢管根数 (i=1,2,3)
r1i,r2i,r3i,r4i ~ 第 i 种切割模式下，每根原料钢管生产 4米,5米,6米和 8米长的钢管的数量满足需求
50313212111 xrxrxr
10323222121 xrxrxr
20333232131 xrxrxr
15343242141 xrxrxr
模式合理：每根余料不超过 3米
19865416 41312111 rrrr
19865416 42322212 rrrr
19865416 43332313 rrrr
整数非线性规划模型钢管下料问题 2
目标函数（ 总根数）
321 xxxM i n
约束条件整数约束,xi,r1i,r2i,
r3i,r4i (i=1,2,3)为整数增加约束，缩小可行域，便于求解
321 xxx
原料钢管总根数下界,2619 158206105504
特殊生产计划：对每根原料钢管模式 1：切割成 4根 4米钢管，需 13根；
模式 2：切割成 1根 5米和 2根 6米钢管，需 10根；
模式 3：切割成 2根 8米钢管，需 8根。
原料钢管总根数上界,13+10+8=31
3126 321 xxx
模式排列顺序可任定钢管下料问题 2
需求,4米 50根,5米 10
根,6米 20根,8米 15根每根原料钢管长 19米
LINGO求解整数非线性规划模型
Local optimal solution found at
iteration,12211
Objective value,28.00000
Variable Value Reduced Cost
X1 10.00000 0.000000
X2 10.00000 2.000000
X3 8.000000 1.000000
R11 3.000000 0.000000
R12 2.000000 0.000000
R13 0.000000 0.000000
R21 0.000000 0.000000
R22 1.000000 0.000000
R23 0.000000 0.000000
R31 1.000000 0.000000
R32 1.000000 0.000000
R33 0.000000 0.000000
R41 0.000000 0.000000
R42 0.000000 0.000000
R43 2.000000 0.000000
模式 1：每根原料钢管切割成 3
根 4米和 1根 6米钢管，共 10根；
模式 2：每根原料钢管切割成 2
根 4米,1根 5米和 1根 6米钢管，
共 10根；
模式 3：每根原料钢管切割成 2
根 8米钢管，共 8根。
原料钢管总根数为 28根。
板材 规格 2：
长方形，
32?28cm，
2万张。
例 2 易拉罐下料每周工作 40小时，每只易拉罐利润 0.10元，原料余料损失 0.001元
/ cm2（不能装配的罐身,盖,底也是余料）
模式 1,1.5秒 模式 2,2秒 模式 3,1秒模式 4,3秒上盖下底罐身罐身高 10cm，
上 盖,下底直径均 5cm。
板材规格 1：
正方形，边长
24cm,5万张。
如何安排每周生产？
罐身个数 底、盖个数余料损失
（ cm2）
冲压时间
（秒）
模式 1 1 10 222.6 1.5
模式 2 2 4 183.3 2
模式 3 0 16 261.8 1
模式 4 4 5 169.5 3
模式 1:
正方形边长 24cm
问题分析 计算各种模式下的余料损失上、下底直径 d=5cm，
罐身高 h=10cm。
模式 1 余料损失 242-10d2/4 -?dh=222.6 cm2
问题分析目标,易拉罐利润扣除原料余料损失后的净利润最大约束,每周工作时间不超过 40小时；
原料数量,规格 1（模式 1 ~3） 5万张，
规格 2（模式 4） 2万张；
罐身和底、盖的配套组装 。
注意：不能装配的罐身、上下底也是余料决策变量
xi ~ 按照第 i 种模式的生产张数 (i=1,2,3,4)；
y1 ~ 一周生产的易拉罐个数；
y2 ~ 不配套的罐身个数；
y3 ~ 不配套的底、盖个数。
模型建立目标约束条件
)6.191.1575.1698.261
3.1836.222(001.01.0
3243
211
yyxx
xxyM ax
时间约束 1 4 4 0 0 0325.1 4321 xxxx
原料约束,50000
321 xxx 2 0 0 0 04?x
产量 余料 时间
x1 222.6 1.5
x2 183.3 2
x3 261.8 1
x4 169.5 3
模型建立 y1 ~ 易拉罐个数； y2 ~ 不配套的罐身；
y3 ~ 不配套的底、盖。
每只易拉罐利润 0.10元，
余料损失 0.001元 / cm2
罐身 面积?dh=157.1 cm2
底盖 面积?d2/4=19.6 cm2
(40小时 )
约束条件配套约束
}2/)516410(,42m i n { 43214211 xxxxxxxy
14212 42 yxxxy
143213 2516410 yxxxxy
,42 4211 xxxy 2/)516410( 43211 xxxxy
y1 ~ 易拉罐个数； y2 ~ 不配套的罐身；
y3 ~ 不配套的底、盖。
罐身 底、盖
1 10
2 4
0 16
4 5
产量
x1
x2
x3
x4
虽然 xi和 y1,y2,y3应是整数，但是因生产量很大，
可以把它们看成实数，从而用线性规划模型处理 。
将所有决策变量扩大 10000倍（ xi ~万张,yi ~万件）
LINDO发出警告信息：,数据之间的数量级差别太大，建议进行预处理，缩小数据之间的差别,
模式 2生产 40125张，
模式 3生产 3750张，
模式 4生产 20000张，
共产易拉罐 160250个
(罐身和底、盖无剩余 )，
净利润为 4298元
,5321 xxx 24?x
模型求解
OBJECTIVE FUNCTION VALUE
1) 0.4298337
VARIABLE VALUE REDUCED COST
Y1 16.025000 0.000000
X1 0.000000 0.000050
X2 4.012500 0.000000
X3 0.375000 0.000000
X4 2.000000 0.000000
Y2 0.000000 0.223331
Y3 0.000000 0.036484
,4.14325.1 4321 xxxx
下料问题的建模
确定下料模式? 构造优化模型规格不太多，可枚举下料模式，建立整数线性规划模型，
否则要构造整数非线性规划模型，求解困难，可用 缩小可行域 的方法进行化简，但要保证最优解的存在。
一维问题（如钢管下料）
二维问题（如易拉罐下料）
具体问题具体分析（比较复杂 ）
4.1 奶制品的生产与销售
4.2 自来水输送与货机装运
4.3 汽车生产与原油采购
4.4 接力队选拔和选课策略
4.5 饮料厂的生产与检修
4.6 钢管和易拉罐下料
y
数学规划模型实际问题中的优化模型
mixgts
xxxxfzM a xM i n
i
T
n
,2,1,0)(..
),(),()( 1
或
x~决策变量 f(x)~目标函数 gi(x)?0~约束条件多元函数条件极值决策变量个数 n和约束条件个数 m较大最优解在可行域的边界上取得数学规划线性规划非线性规划整数规划重点在模型的建立和结果的分析企业生产计划
4.1 奶制品的生产与销售空间层次工厂级：根据外部需求和内部设备、人力、原料等条件，以最大利润为目标制订产品生产计划；
车间级：根据生产计划、工艺流程、资源约束及费用参数等，以最小成本为目标制订生产批量计划。
时间层次若短时间内外部需求和内部资源等不随时间变化，可制订 单阶段生产计划,否则应制订多阶段生产计划。
本节课题例 1 加工奶制品的生产计划
1桶牛奶
3公斤 A112小时
8小时 4公斤 A2
或获利 24元 /公斤获利 16元 /公斤
50桶牛奶 时间 480小时 至多加工 100公斤 A1
制订生产计划，使每天获利最大
35元可买到 1桶牛奶，买吗？若买，每天最多买多少?
可聘用临时工人，付出的工资最多是每小时几元?
A1的获利增加到 30元 /公斤，应否改变生产计划？
每天：
1桶牛奶
3公斤 A112小时
8小时 4公斤 A2
或获利 24元 /公斤获利 16元 /公斤
x1桶牛奶生产 A1 x2桶牛奶生产 A2
获利 24× 3x1 获利 16× 4 x2
原料供应 50
21 xx
劳动时间 480812 21 xx
加工能力 1003 1?x
决策变量目标函数
21 6472 xxzM ax
每天获利约束条件非负约束 0,21?xx
线性规划模型
(LP)
时间 480小时 至多加工 100公斤 A150桶牛奶每天模型分析与假设比例性可加性连续性
xi对目标函数的
“贡献”与 xi取值成正比x
i对约束条件的
“贡献”与 xi取值成正比x
i对目标函数的
“贡献”与 xj取值无关x
i对约束条件的
“贡献”与 xj取值无关 x
i取值连续
A1,A2每公斤的获利是与各自产量无关的常数每桶牛奶加工出 A1,A2的数量和时间是与各自产量无关的常数
A1,A2每公斤的获利是与相互产量无关的常数每桶牛奶加工出 A1,A2的数量和时间是与相互产量无关的常数加工 A1,A2的牛奶桶数是实数线性规划模型模型求解 图解法
x1
x2
0
A
B
C
D
l1
l2
l3
l4
l5
5021 xx
480812 21 xx
1003 1?x
0,21?xx
约束条件
50,211 xxl
4 8 0812,212 xxl
1003,13?xl
0:,0,2514 xlxl
21 6472 xxzM ax目标函数 Z=0
Z=2400
Z=3600
z=c (常数 ) ~等值线
c
在 B(20,30)点得到最优解目标函数和约束条件是线性函数可行域为直线段围成的凸多边形目标函数的等值线为直线最优解一定在凸多边形的某个顶点取得。
模型求解 软件实现 LINDO 6.1
max 72x1+64x2
st
2） x1+x2<50
3） 12x1+8x2<480
4） 3x1<100
end
OBJECTIVE FUNCTION VALUE
1) 3360.000
VARIABLE VALUE REDUCED COST
X1 20.000000 0.000000
X2 30.000000 0.000000
ROW SLACK OR SURPLUS DUALPRICES
2) 0.000000 48.000000
3) 0.000000 2.000000
4) 40.000000 0.000000
NO,ITERATIONS= 2
DO RANGE
(SENSITIVITY)
ANALYSIS? No
20桶牛奶生产 A1,30桶生产 A2，利润 3360元。
结果解释
OBJECTIVE FUNCTION VALUE
1) 3360.000
VARIABLE VALUE REDUCED COST
X1 20.000000 0.000000
X2 30.000000 0.000000
ROW SLACK OR SURPLUS DUALPRICES
2) 0.000000 48.000000
3) 0.000000 2.000000
4) 40.000000 0.000000
NO,ITERATIONS= 2
原料无剩余时间无剩余加工能力剩余 40
max 72x1+64x2
st
2） x1+x2<50
3） 12x1+8x2<480
4） 3x1<100
end
三种资源
―资源” 剩余为零的约束为紧约束（有效约束）
结果解释OBJECTIVE FUNCTION VALUE1) 3360.000
VARIABLE VALUE REDUCED COST
X1 20.000000 0.000000
X2 30.000000 0.000000
ROW SLACK OR SURPLUS DUALPRICES
2) 0.000000 48.000000
3) 0.000000 2.000000
4) 40.000000 0.000000
NO,ITERATIONS= 2
最优解下“资源”增加
1单位时“效益”的增量原料增加 1单位,利润增长 48
时间增加 1单位,利润增长 2
加工能力增长不影响利润影子价格
35元可买到 1桶牛奶，要买吗？ 35 <48,应该买！
聘用临时工人付出的工资最多每小时几元？ 2元！
RANGES IN WHICH THE BASIS IS UNCHANGED:
OBJ COEFFICIENT RANGES
VARIABLE CURRENT ALLOWABLE ALLOWABLE
COEF INCREASE DECREASE
X1 72.000000 24.000000 8.000000
X2 64.000000 8.000000 16.000000
RIGHTHAND SIDE RANGES
ROW CURRENT ALLOWABLE ALLOWABLE
RHS INCREASE DECREASE
2 50.000000 10.000000 6.666667
3 480.000000 53.333332 80.000000
4 100.000000 INFINITY 40.000000
最优解不变时目标函数系数允许变化范围
DO RANGE(SENSITIVITY) ANALYSIS? Yes
x1系数范围 (64,96)
x2系数范围 (48,72)
A1获利增加到 30元 /千克，应否改变生产计划
x1系数由 24?3=72
增加 为 30?3=90，
在 允许范围内不变！
(约束条件不变 )
结果解释
RANGES IN WHICH THE BASIS IS UNCHANGED:
OBJ COEFFICIENT RANGES
VARIABLE CURRENT ALLOWABLE ALLOWABLE
COEF INCREASE DECREASE
X1 72.000000 24.000000 8.000000
X2 64.000000 8.000000 16.000000
RIGHTHAND SIDE RANGES
ROW CURRENT ALLOWABLE ALLOWABLE
RHS INCREASE DECREASE
2 50.000000 10.000000 6.666667
3 480.000000 53.333332 80.000000
4 100.000000 INFINITY 40.000000
影子价格有意义时约束右端的允许变化范围原料最多增加 10
时间最多增加 53
35元可买到 1桶牛奶，每天最多买多少？ 最多买 10桶 !
(目标函数不变 )
例 2 奶制品的生产销售计划 在例 1基础上深加工
1桶牛奶
3千克 A112小时
8小时 4公斤 A2
或获利 24元 /公斤获利 16元 /公斤
0.8千克 B1
2小时,3元
1千克 获利 44元 /千克
0.75千克 B22小时,3元1千克 获利 32元 /千克制订生产计划，使每天净利润最大
30元可增加 1桶牛奶,3元可增加 1小时时间，应否投资？现投资 150元，可赚回多少？
50桶牛奶,480小时至多 100公斤 A1
B1,B2的获利经常有 10%的波动，对计划有无影响？
1桶牛奶
3千克 A112小时
8小时 4千克 A2
或获利 24元 /千克获利 16元 /kg
0.8千克 B12小时,3元1千克 获利 44元 /千克
0.75千克 B22小时,3元1千克 获利 32元 /千克出售 x1 千克 A1,x2 千克 A2,X3千克 B1,x4千克 B2
原料供应劳动时间加工能力决策变量目标函数 利润约束条件非负约束
0,61?xx?
x5千克 A1加工 B1,x6千克 A2加工 B2
654321 3332441624 xxxxxxzM a x
5043 6251 xxxx
48022
)(2)(4
65
6251
xx
xxxx
10051 xx
附加约束 53 80 x.x?
64 750 x.x?
模型求解软件实现 LINDO 6.1
5043)2 6251 xxxx
48022
)(2)(4)3
65
6251
xx
xxxx
OBJECTIVE FUNCTION VALUE
1) 3460.800
VARIABLE VALUE REDUCED COST
X1 0.000000 1.680000
X2 168.000000 0.000000
X3 19.200001 0.000000
X4 0.000000 0.000000
X5 24.000000 0.000000
X6 0.000000 1.520000
ROW SLACK OR SURPLUS DUALPRICES
2) 0.000000 3.160000
3) 0.000000 3.260000
4) 76.000000 0.000000
5) 0.000000 44.000000
6) 0.000000 32.000000
NO,ITERATIONS= 2
6 0 0334)2 6521 xxxx 4
4 8 04624)3 6521 xxxx
DO RANGE
(SENSITIVITY)
ANALYSIS? No
OBJECTIVE FUNCTION VALUE
1) 3460.800
VARIABLE VALUE REDUCED COST
X1 0.000000 1.680000
X2 168.000000 0.000000
X3 19.200001 0.000000
X4 0.000000 0.000000
X5 24.000000 0.000000
X6 0.000000 1.520000
ROW SLACK OR SURPLUS DUALPRICES
2) 0.000000 3.160000
3) 0.000000 3.260000
4) 76.000000 0.000000
5) 0.000000 44.000000
6) 0.000000 32.000000
NO,ITERATIONS= 2
结果解释每天销售 168 千克 A2
和 19.2 千克 B1，
利润 3460.8（元）
8桶牛奶加工成 A1,42桶牛奶加工成 A2，
将得到的 24千克 A1全部加工成 B1
除加工能力外均为紧约束结果解释
OBJECTIVE FUNCTION VALUE
1) 3460.800
VARIABLE VALUE REDUCED COST
X1 0.000000 1.680000
X2 168.000000 0.000000
X3 19.200001 0.000000
X4 0.000000 0.000000
X5 24.000000 0.000000
X6 0.000000 1.520000
ROW SLACK OR SURPLUS DUALPRICES
2) 0.000000 3.160000
3) 0.000000 3.260000
4) 76.000000 0.000000
5) 0.000000 44.000000
6) 0.000000 32.000000
增加 1桶牛奶使利润增长 3.16× 12=37.92
5043)2 6251 xxxx
6 0 0334)2 6521 xxxx 4
增加 1小时时间使利润增长 3.26
30元可增加 1桶牛奶,3元可增加 1小时时间，
应否投资？现投资 150元，可赚回多少？
投资 150元增加 5桶牛奶，
可赚回 189.6元。（大于增加时间的利润增长）
结果解释 B1,B2的获利有 10%的波动，对计划有无影响
RANGES IN WHICH THE BASIS IS UNCHANGED:
OBJ COEFFICIENT RANGES
VARIABLE CURRENT ALLOWABLE ALLOWABLE
COEF INCREASE DECREASE
X1 24.000000 1.680000 INFINITY
X2 16.000000 8.150000 2.100000
X3 44.000000 19.750002 3.166667
X4 32.000000 2.026667 INFINITY
X5 -3.000000 15.800000 2.533334
X6 -3.000000 1.520000 INFINITY
…… ……
DO RANGE
(SENSITIVITY)
ANALYSIS? Yes
B1获利下降 10%，超出 X3 系数允许范围
B2获利上升 10%，超出 X4 系数允许范围波动对计划有影响生产计划应重新制订：如将 x3的系数改为 39.6
计算，会发现结果有很大变化。
4.2 自来水输送与货机装运生产、生活物资从若干供应点运送到一些需求点，
怎样安排输送方案使运费最小，或利润最大；
运输问题各种类型的货物装箱，由于受体积、重量等限制，
如何搭配装载，使获利最高，或装箱数量最少。
其他费用,450元 /千吨
应如何分配水库供水量，公司才能获利最多？
若水库供水量都提高一倍，公司利润可增加到多少？
元 /千吨 甲 乙 丙 丁
A 160 130 220 170
B 140 130 190 150
C 190 200 230 /
引水管理费例 1 自来水输送收入,900元 /千吨支出
A,50
B,60
C,50
甲,30； 50
乙,70； 70
丙,10； 20
丁,10； 40
水库供水量(
千吨)
小区基本用水量(
千吨)
小区额外用水量(
千吨)（以天计）
总供水量,160
确定送水方案 使利润最大问题分析
A,50
B,60
C,50
甲,30； 50
乙,70； 70
丙,10； 20
丁,10； 40
< 总需求量,120+180=300
总收入 900?160=144,000(元 ) 收入,900元 /千吨其他费用,450元 /千吨支出 引水管理费其他 支出 450?160=72,000(元 )
使引水管理费最小供应限制约束条件需求限制线性规划模型
(LP)
5014131211 xxxx
50
60
333231
24232221
xxx
xxxx
8030 312111 xxx
14070 322212 xxx
3010 332313 xxx
5010 2414 xx
目标函数
33323124232221
14131211
2 302 001 901 501 901 301 40
1 702 201 301 60
xxxxxxx
xxxxZM i n
水库 i 向 j 区的日供水量为 xij（ x34=0）决策变量模型建立 确定 3个水库向 4个小区的供水量模型求解 OBJECTIVE FUNCTION VALUE
1) 24400.00
VARIABLE VALUE REDUCED COST
X11 0.000000 30.000000
X12 50.000000 0.000000
X13 0.000000 50.000000
X14 0.000000 20.000000
X21 0.000000 10.000000
X22 50.000000 0.000000
X23 0.000000 20.000000
X24 10.000000 0.000000
X31 40.000000 0.000000
X32 0.000000 10.000000
X33 10.000000 0.000000
利润 =总收入 -其它费用 - 引 水 管 理 费
=144000-72000-24400
= 47600（ 元 ）
A(50)
B(60)
C(50)
甲 (30;50)
乙 (70;70)
丙 (10;20)
丁 (10;40)
50
50 40
10
10
引水管理费 24400(元 )
目标函数总供水量 (320) > 总需求量 (300)
每个水库最大供水量都提高一倍利润 = 收入 (900) –其它费用 (450) –引水管理费利润 (元 /千吨 ) 甲 乙 丙 丁
A 290 320 230 280
B 310 320 260 300
C 260 250 220 /
33323124232221
14131211
220250260300260320310
280230320290
xxxxxxx
xxxxZM ax
供应限制 B,C 类似处理 50:A 14131211 xxxx
10014131211 xxxx
问题讨论确定送水方案 使利润最大需求约束可以不变求解 OBJECTIVE FUNCTION VALUE
1) 88700.00
VARIABLE VALUE REDUCED COST
X11 0.000000 20.000000
X12 100.000000 0.000000
X13 0.000000 40.000000
X14 0.000000 20.000000
X21 30.000000 0.000000
X22 40.000000 0.000000
X23 0.000000 10.000000
X24 50.000000 0.000000
X31 50.000000 0.000000
X32 0.000000 20.000000
X33 30.000000 0.000000
这类问题一般称为
“运输问题”
(Transportation
Problem)
总利润 88700（ 元 ）
A(100)
B(120)
C(100)
甲 (30;50)
乙 (70;70)
丙 (10;20)
丁 (10;40)
40
100
50 30
50
30
如何 装运，
使本次飞行获利最大？
三个货舱 最大 载 重 (吨 ),最大容积 (米 3)例 2 货机装运重量（吨） 空间 ( 米 3/
吨）
利润（元 /
吨）
货物 1 18 480 3100
货物 2 15 650 3800
货物 3 23 580 3500
货物 4 12 390 2850
三个货舱中实际载重必须与其最大 载 重成比例前仓：
10； 6800
中仓：
16； 8700
后仓：
8； 5300
飞机平衡决策变量
xij--第 i 种货物装入第 j 个货舱的重量 (吨）
i=1,2,3,4,j=1,2,3 (分别代表前、中、后仓 )
模型假设每种货物可以分割到任意小；
货机装运每种货物可以在一个或多个货舱中任意分布；
多种货物可以混装，并保证不留空隙；
模型建立货舱容积目标函数
(利润 )
约束条件
)(28 50)(35 00
)(38 00)(31 00
434241333231
232221131211
xxxxxx
xxxxxxZM ax
6 8 0 03 9 05 8 06 5 04 8 0 41312111 xxxx
8 7 0 0390580650480 42322212 xxxx
5 3 0 03 9 05 8 06 5 04 8 0 43332313 xxxx
货机装运 模型建立货舱重量
1041312111 xxxx
1642322212 xxxx
843332313 xxxx
10；
6800
16；
8700
8；
5300
xij--第 i 种货物装入第 j 个货舱的重量约束条件平衡要求
8
16
10
43332313
42322212
41312111
xxxx
xxxx
xxxx
货物供应 18131211 xxx
15232221 xxx
23333231 xxx
12434241 xxx
货机装运 模型建立
10；
6800
16；
8700
8；
5300
xij--第 i 种货物装入第 j 个货舱的重量
OBJECTIVE FUNCTION VALUE
1) 121515.8
VARIABLE VALUE REDUCED COST
X11 0.000000 400.000000
X12 0.000000 57.894737
X13 0.000000 400.000000
X21 10.000000 0.000000
X22 0.000000 239.473679
X23 5.000000 0.000000
X31 0.000000 0.000000
X32 12.947369 0.000000
X33 3.000000 0.000000
X41 0.000000 650.000000
X42 3.052632 0.000000
X43 0.000000 650.000000
货物 2：前仓 10,后仓 5；
货物 3,中仓 13,后仓 3；
货物 4,中仓 3。
货机装运 模型求解最大利润约 121516元货物 ~供应点货舱 ~需求点平衡要求运输问题运输问题的扩展
如果生产某一类型汽车，则至少要生产 80辆，
那么最优的生产计划应作何改变？
例 1 汽车厂生产计划汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量。
小型 中型 大型 现有量钢材（吨） 1.5 3 5 600
劳动时间（小时） 280 250 400 60000
利润（万元） 2 3 4
制订月生产计划,使工厂的利润最大 。
4.3 汽车生产与原油采购设每月生产小、中、大型汽车的数量分别为 x1,x2,x3
321 432 xxxzM a x
600535.1.,321 xxxts
6 0 0 0 0400250280 321 xxx
0,,321?xxx
汽车厂生产计划模型建立 小型 中型 大型 现有量钢材 1.5 3 5 600
时间 280 250 400 60000
利润 2 3 4
线性规划模型
(LP)
模型求解
3） 模型中增加条件,x1,x2,x3 均为整数,重新求解 。
OBJECTIVE FUNCTION VALUE
1) 632.2581
VARIABLE VALUE REDUCED COST
X1 64.516129 0.000000
X2 167.741928 0.000000
X3 0.000000 0.946237
ROW SLACK OR SURPLUS DUAL PRICES
2) 0.000000 0.731183
3) 0.000000 0.003226
结果为小数，
怎么办？
1）舍去小数：取 x1=64,x2=167，算出目标函数值 z=629，与
LP最优值 632.2581相差不大。
2） 试探：如取 x1=65,x2=167； x1=64,x2=168等,计算函数值 z,通过比较可能得到更优的解 。
但必须检验它们是否满足约束条件。为什么？
IP可用 LINDO直接求解整数规划 (Integer Programming,简记 IP)
―gin 3‖表示,前 3个变量为整数,,等价于：
gin x1
gin x2
gin x3
IP 的最优解 x1=64,x2=168,x3=0，最优值 z=632
max 2x1+3x2+4x3
st
1.5x1+3x2+5x3<600
280x1+250x2+400x3<60000
end
gin 3
OBJECTIVE FUNCTION VALUE
1) 632.0000
VARIABLE VALUE REDUCED COST
X1 64.000000 -2.000000
X2 168.000000 -3.000000
X3 0.000000 -4.000000
321 432 xxxzM a x
600535.1.,321 xxxts
60000400250280 321 xxx
为非负整数321,,xxx
模型求解
IP 结果输出其中 3个 子模型应 去掉，然后逐一求解，比较目标函数值，
再加上整数约束，得最优解：
80,0,0 321 xxx
0,80,0 321 xxx
80,80,0 321 xxx
0,0,80 321 xxx
0,80,80 321 xxx
80,0,80 321 xxx
80,80,80 321 xxx
0,,321?xxx
方法 1：分解为 8个 LP子模型汽车厂生产计划
若生产某类汽车，则至少生产 80辆，求生产计划。
321 432 xxxzM a x
600535.1.,321 xxxts
60000400250280 321 xxx
x1,x2,,x3=0 或?80
x1=80,x2= 150,x3=0，最优值 z=610
LINDO中对 0-
1变量的限定：
int y1
int y2
int y3
方法 2,引入 0-1变量，化为整数规划
M为大的正数，
可取 1000
OBJECTIVE FUNCTION VALUE
1) 610.0000
VARIABLE VALUE REDUCED COST
X1 80.000000 -2.000000
X2 150.000000 -3.000000
X3 0.000000 -4.000000
Y1 1.000000 0.000000
Y2 1.000000 0.000000
Y3 0.000000 0.000000
若生产某类汽车，则至少生产 80辆，求生产计划。
x1=0 或?80
x2=0 或?80
x3=0 或?80
}1,0{,80,11111 yyxMyx
}1,0{,80,22222 yyxMyx
}1,0{,80,33333 yyxMyx
最优解同前
NLP 虽然可用现成的数学软件求解 (如 LINGO,
MATLAB),但是其结果常依赖于初值的选择 。
方法 3,化为非线性规划非线性规划（ Non- Linear Programming，简记 NLP）
实践表明,本例仅当初值非常接近上面方法算出的最优解时,才能得到正确的结果 。
若生产某类汽车，则至少生产 80辆，求生产计划。
x1=0 或?80
x2=0 或?80
x3=0 或?80
0)80( 11xx
0)80( 22xx
0)80( 33xx
应如何安排原油的采购和加工？
例 2 原油采购与加工市场上可买到不超过 1500吨的原油 A：
购买量不超过 500吨时的单价为 10000元 /吨；
购买量超过 500吨但不超过 1000吨时，超过 500吨的部分 8000元 /吨；
购买量超过 1000吨时，超过 1000吨的部分 6000元 /吨。
售价 4800元 /吨售价 5600元 /吨库存 500吨库存 1000吨汽油甲
(A?50%) 原油 A
原油 B 汽油乙
(A?60%)
决策变量目标函数问题分析
利润：销售汽油的收入 - 购买原油 A的支出
难点：原油 A的购价与购买量的关系较复杂
)()(6.5)(8.4 22122111 xcxxxxzM ax
甲 (A?50%) A
B 乙 (A?60%)
购买 x?
x11
x12
x21
x22
4.8千元 /吨
5.6千元 /吨原油 A的购买量,原油 A,B生产 汽油 甲,乙的数量
c(x) ~ 购买原油 A的支出利润 (千元 )
c(x)如何表述？
原油供应约束条件
xxx 5 0 01211
1 0 0 02221 xx
1500?x
5 0 0 )1( 1 0 0 0 3 0 0 06
1 0 0 0 )( 5 0 0 1 0 0 0 8
5 0 0 )(0 10
)(
xx
xx
xx
xc
x? 500吨单价为 10千 元 /吨；
500吨? x? 1000吨，超过 500吨的 8千 元 /吨；
1000吨?x? 1500吨，超过 1000吨的 6千 元 /吨。
目标函数购买 x?
A
B
x11
x12
x21
x22
库存 500吨库存 1000吨
目标函数中 c(x)不是线性函数，是非线性规划；
对于用分段函数定义的 c(x)，一般的非线性规划软件也难以输入和求解；
想办法将模型化简，用现成的软件求解。
汽油含原油 A
的比例限制
5.0
2111
11?
xx
x
6.0
2212
12?
xx
x
2111 xx
2212 32 xx
约束条件甲 (A?50%) A
B 乙 (A?60%)
x11
x12
x21
x22
x1,x2,x3 ~以价格 10,8,6(千元 /吨 )采购 A的吨数目标函数只有当以 10千元 /吨的价格购买 x1=500(吨 )时，才能以
8千元 /吨的价格购买 x2
方法 1
)6810()(6.5)(8.4 32122122111 xxxxxxxzM a x
0)5 0 0( 32 xx 5 0 0,,0 321 xxx
非线性规划模型,可以用 LINGO求解模型求解
x= x1+x2+x3,c(x) = 10x1+8x2+6x3
500吨? x? 1000吨，超过 500吨的 8千 元 /吨增加约束
0)500( 21 xx
方法 1,LINGO求解Model:Max= 4.8*x11 + 4.8*x21 + 5.6*x12
+ 5.6*x22 - 10*x1 - 8*x2 - 6*x3;
x11+x12 < x + 500;
x21+x22 < 1000;
x11 - x21 > 0;
2*x12 - 3*x22 > 0;
x=x1+x2+x3;
(x1 - 500) * x2=0;
(x2 - 500) * x3=0;
x1 < 500;
x2 < 500;
x3 < 500;
x > 0;
x11 > 0;
x12 > 0;
x21 > 0;
x22 > 0;
x1 > 0;
x2 > 0;
x3 > 0;
end
Objective value,4800.000
Variable Value Reduced Cost
X11 500.0000 0.0000000E+00
X21 500.0000 0.0000000E+00
X12 0.0000000E+00 0.0000000E+00
X22 0.0000000E+00 0.0000000E+00
X1 0.1021405E-13 10.00000
X2 0.0000000E+00 8.000000
X3 0.0000000E+00 6.000000
X 0.0000000E+00 0.0000000E+00
LINGO得到的是局部最优解，还能得到更好的解吗？
用库存的 500吨原油 A,500吨原油 B
生产汽油甲，不购买新的原油 A，
利润为 4,800千 元。
y1,y2,y3=1 ~以价格 10,8,6(千元 /吨 )采购 A
增加约束方法 2
0-1线性规划模型,可用 LINDO求解
112 500500 yxy 223 5 0 05 0 0 yxy
33 5 00 yx?
y1,y2,y3 =0或 1
OBJECTIVE FUNCTION VALUE
1) 5000.000
VARIABLE VALUE REDUCED
COST
Y1 1.000000 0.000000
Y2 1.000000 2200.000000
Y3 1.000000 1200.000000
X11 0.000000 0.800000
X21 0.000000 0.800000
X12 1500.000000 0.000000
X22 1000.000000 0.000000
X1 500.000000 0.000000
X2 500.000000 0.000000
X3 0.000000 0.400000
X 1000.000000 0.000000
购买 1000吨原油 A，与库存的 500吨原油 A和
1000吨原油 B一起，生产汽油乙，利润为 5,000
千元 。
x1,x2,x3 ~以价格 10,8,6(千元 /吨 )采购 A的吨数
y=0? x=0
x>0? y=1
优于方法 1的结果
b1 b2 b3 b4
方法 3
b1? x?b2,x= z1b1+z2b2，
z1+z2=1,z1,z2?0,
c(x)= z1c(b1)+z2c(b2).
c(x)
x
12000
9000
5000
0 500 1000 1500
b2? x? b3,x= z2b2+z3b3，
z2+z3=1,z2,z3? 0,
c(x)= z2c(b2)+z3c(b3),
b3? x? b4,x= z3b3+z4b4，
z3+z4=1,z3,z4? 0,
c(x)= z3c(b3)+z4c(b4),
500)1( 1 0 0 0 30006
1 0 0 0 )( 5 0 0 1000 8
500)(0 10
)(
xx
xx
xx
xc
直接处理处理分段线性函数 c(x)
IP模型,LINDO求解，得到的结果与方法 2相同,
处理分段线性函数,方法 3更具一般性
44332211 bzbzbzbzx
)()()()()( 44332211 bczbczbczbczxc
bk?x?bk+1?yk=1,否则,yk=0
3432321211,,,yzyyzyyzyz
)4,3,2,1(0,14321 kzzzzz k
10,,,1 321321 或 yyyyyy
方法 3
bk?x?bk+1,x= zkbk+z k+1 bk+1
zk+zk+1 =1,zk,zk+1?0,
c(x)= zkc(bk)+zk+1 c(bk+1 ).
c(x)
x
12000
9000
5000
0 500 1000 1500
b1 b2 b3 b4
对于 k=1,2,3
分派问题
4.4 接力队选拔和选课策略若干项任务分给一些候选人来完成，每人的专长不同，
完成每项任务取得的效益或需要的资源就不同，如何分派任务使获得的总效益最大，或付出的总资源最少。
若干种策略供选择，不同的策略得到的收益或付出的成本不同，各个策略之间有相互制约关系，如何在满足一定条件下作出决择，使得收益最大或成本最小。
丁的蛙泳成绩退步到 1’15‖2；戊的自由泳成绩进步到 57‖5,组成接力队的方案是否应该调整？
如何选拔队员组成 4?100米混合泳接力队?
例 1 混合泳接力队的选拔甲 乙 丙 丁 戊蝶泳 1’06‖8 57‖2 1’18‖ 1’10‖ 1’07‖4
仰泳 1’15‖6 1’06‖ 1’07‖8 1’14‖2 1’11‖
蛙泳 1’27‖ 1’06‖4 1’24‖6 1’09‖6 1’23‖8
自由泳 58‖6 53‖ 59‖4 57‖2 1’02‖4
5名候选人的 百米成绩穷举法,组成接力队的方案共有 5!=120种 。
目标函数若选择队员 i参加泳姿 j 的比赛，记 xij=1,否则记 xij=0
0-1规划模型 cij(秒 )~队员 i 第 j 种泳姿的百米成绩约束条件每人最多入选泳姿之一
cij i=1 i=2 i=3 i=4 i=5
j=1 66.8 57.2 78 70 67.4
j=2 75.6 66 67.8 74.2 71
j=3 87 66.4 84.6 69.6 83.8
j=4 58.6 53 59.4 57.2 62.4
4
1
5
1j i
ijij xcZM i n
每种泳姿有且只有 1人
5,1,1
4
1
ix
j
ij
4,1,1
5
1
jx
i
ij
模型求解最优解,x14 = x21 = x32 =
x43 = 1,其它变量为 0;
成绩为 253.2(秒 )=4’13‖2
MIN 66.8x11+75.6x12+87x13+58.6x14
+… …
+67.4x51+71 x52+83.8x53+62.4x54
SUBJECT TO
x11+x12+x13+x14 <=1
… …
x41+x42+x43+x44 <=1
x11+x21+x31+x41+x51 =1
… …
x14+x24+x34+x44+x54 =1
END
INT 20
输入 LINDO求解甲 乙 丙 丁 戊蝶泳 1’06‖8 57‖2 1’18‖ 1’10‖ 1’07‖4
仰泳 1’15‖6 1’06‖ 1’07‖8 1’14‖2 1’11‖
蛙泳 1’27‖ 1’06‖4 1’24‖6 1’09‖6 1’23‖8
自由泳 58‖6 53‖ 59‖4 57‖2 1’02‖4
甲 ~ 自由泳、乙 ~ 蝶泳、
丙 ~ 仰泳、丁 ~ 蛙泳,
丁蛙泳 c43=69.6?75.2，戊自由泳 c54=62.4?
57.5,方案是否调整？ 敏感性分析？
乙 ~ 蝶泳、丙 ~ 仰泳、
丁 ~ 蛙泳、戊 ~ 自由泳
IP规划一般没有与 LP规划相类似的理论,LINDO
输出的敏感性分析结果通常是没有意义的。
最优解,x21 = x32 = x43 = x51 = 1,成绩为 4’17‖7
c43,c54 的新数据重新输入模型，用 LINDO求解指派 (Assignment)问题,每项任务有且只有一人承担，
每人只能承担一项,效益不同，怎样分派使总效益最大,
讨论甲 ~ 自由泳、乙 ~ 蝶泳、
丙 ~ 仰泳、丁 ~ 蛙泳,
原方案为了选修课程门数最少，应学习哪些课程？
例 2 选课策略要求至少选两门数学课、三门运筹学课和两门计算机课课号 课名 学分 所属类别 先修课要求
1 微积分 5 数学
2 线性代数 4 数学
3 最优化方法 4 数学；运筹学 微积分；线性代数
4 数据结构 3 数学；计算机 计算机编程
5 应用统计 4 数学；运筹学 微积分；线性代数
6 计算机模拟 3 计算机；运筹学 计算机编程
7 计算机编程 2 计算机
8 预测理论 2 运筹学 应用统计
9 数学实验 3 运筹学；计算机 微积分；线性代数选修课程最少，且学分尽量多，应学习哪些课程？
0-1规划模型 决策变量目标函数
xi=1 ~选修课号 i 的课程（ xi=0 ~不选）
9
1i
ixZM i n
选修课程总数最少约束条件最少 2门数学课，
3门运筹学课，
2门计算机课。
254321 xxxxx
398653 xxxxx
29764 xxxx
课号 课名 所属类别
1 微积分 数学
2 线性代数 数学
3 最优化方法 数学；运筹学
4 数据结构 数学；计算机
5 应用统计 数学；运筹学
6 计算机模拟 计算机；运筹学
7 计算机编程 计算机
8 预测理论 运筹学
9 数学实验 运筹学；计算机先修课程要求
74 xx?
02 215 xxx
076 xx
058 xx
02 219 xxx
最优解,x1 = x2 = x3 = x6 = x7 = x9
=1,其它为 0； 6门课程，总学分 21
02 213 xxx
0-1规划模型 约束条件
x3=1必有 x1 = x2 =1
2313,xxxx
074 xx
模型求解（ LINDO）
课号 课名 先修课要求
1 微积分
2 线性代数
3 最优化方法 微积分；线性代数
4 数据结构 计算机编程
5 应用统计 微积分；线性代数
6 计算机模拟 计算机编程
7 计算机编程
8 预测理论 应用统计
9 数学实验 微积分；线性代数学分最多多目标优化的处理方法：化成单目标优化。
两目标 (多目标 )规划
9876
54321
3223
43445
xxxx
xxxxxWM a x
},{ WZM i n?
讨论：选修课程最少，学分尽量多，应学习哪些课程？
9
1i
ixZM i n
课程最少
以 学分最多为目标，
不管课程多少。
以课程最少 为目标，
不管学分多少。
最优解如上,6门课程，总学分 21 。
最优解显然是选修所有 9门课程 。
多目标规划
在 课程最少的前提下以 学分最多为目标。
最优解,x1 = x2 = x3 = x5
= x7 = x9 =1,其它为 0； 总学分由 21增至 22。
注意：最优解不唯一！
课号 课名 学分
1 微积分 5
2 线性代数 4
3 最优化方法 4
4 数据结构 3
5 应用统计 4
6 计算机模拟 3
7 计算机编程 2
8 预测理论 2
9 数学实验 3
LINDO无法告诉优化问题的解是否唯一。
可将 x9 =1 易为 x6 =1
增加约束,
以学分最多为目标求解。
6
9
1
i
ix
多目标规划
对学分数和课程数加权形成一个目标，如三七开。
9876
54321
3223
43445
xxxx
xxxxxW
9
1i
ixZ
最优解,x1 = x2 = x3 = x4
= x5 = x6 = x7 = x9 =1，
其它为 0； 总学分 28。
课号 课名 学分
1 微积分 5
2 线性代数 4
3 最优化方法 4
4 数据结构 3
5 应用统计 4
6 计算机模拟 3
7 计算机编程 2
8 预测理论 2
9 数学实验 3
WZWZYM i n 3.07.021
讨论与思考
WZYM i n 21
3/21
1,0,1 2121
最优解 与?1=0,?2=1的结果相同 ——学分最多
4/31
多目标规划
9876
54321
3223
43445
xxxx
xxxxxW
9
1i
ixZ
最优解 与?1=1,?2=0的结果相同 ——课程最少
4.5 饮料厂的生产与检修单阶段生产计划多阶段生产计划
生产批量问题
企业生产计划考虑与产量无关的固定费用给优化模型求解带来新的困难外部需求和内部资源随时间变化
安排生产计划,满足每周的需求,使 4周总费用最小。
存贮费,每周每千箱饮料 0.2千元。
例 1 饮料厂的生产与检修计划
在 4周内安排一次设备检修，占用当周 15千箱生产能力，能使检修后每周增产 5千箱，检修应排在哪一周?
周次 需求量 (千箱 ) 生产能力 (千箱 ) 成本 (千元 /千箱 )
1 15 30 5.0
2 25 40 5.1
3 35 45 5.4
4 25 20 5.5
合计 100 135
某种饮料 4周的需求量、生产能力和成本问题分析
除第 4周外每周的生产能力超过每周的需求；
生产成本逐周上升；
前几周应多生产一些。
周次 需求 能力
1 15 30
2 25 40
3 35 45
4 25 20
合计 100 135
成本
5.0
5.1
5.4
5.5
饮料厂在第 1周开始时没有库存；
从费用最小考虑,第 4周末不能有库存；
周末有库存时需支出一周的存贮费；
每周末的库存量等于下周初的库存量。
模型假设目标函数约束条件产量、库存与需求平衡决策变量
)(2.05.54.51.50.5 3214321 yyyxxxxzM i n
1511 yx
25212 yyx
35323 yyx
2534 yx
20,45
40,30
43
21
xx
xx
能力限制非负限制
0,,,,,,3214321?yyyxxxx
模型建立
x1~ x4：第 1~4周 的生产量
y1~ y3：第 1~3周末 库存量周次 需求 能力
1 15 30
2 25 40
3 35 45
4 25 20
成本
5.0
5.1
5.4
5.5 存贮费,0.2 (千元 /周?千箱 )
模型求解
4周生产计划的总费用为 528 (千元 )
最优解,x1~ x4,15,40,25,20；
y1~ y3,0,15,5,
周次 需求 能力
1 15 30
2 25 40
3 35 45
4 25 20
成本
5.0
5.1
5.4
5.5
产量
15
40
25
20
库存
0
15
5
0
LINDO求解检修计划
0-1变量 wt,wt=1~ 检修安排在第 t周 (t=1,2,3,4）
在 4周内安排一次设备检修，占用当周 15千箱生产能力，能使检修后每周增产 5千箱，检修应排在哪一周?
检修安排在任一周均可周次 需求 能力
1 15 30
2 25 40
3 35 45
4 25 20
成本
5.0
5.1
5.4
5.5
约束条件能力限制 20
45
40
30
4
3
2
1
x
x
x
x 3015
11 wx
122 54015 wwx
1233 554515 wwwx
32144 5552015 wwwwx
产量、库存与需求平衡条件不变增加约束条件：检修 1次
14321 wwww
检修计划 目标函数不变
0-1变量 wt,wt=1~ 检修安排在第 t周 (t=1,2,3,4）
LINDO求解总费用由 528千元降 为 527千元检修所导致的生产能力提高的作用,
需要更长的时间才能得到充分体现。
最优解,w1=1,w2,w3,w4=0;
x1~ x4,15,45,15,25；
y1~ y3,0,20,0,
例 2 饮料的生产批量问题
安排生产计划,满足每周的需求,使 4周总费用最小。
存贮费,每周每千箱饮料 0.2千元。
饮料厂使用同一条生产线轮流生产 多种 饮料。
若某周开工生产 某种 饮料,需支出 生产准备费 8千元。
某种饮料 4周的需求量、生产能力和成本周次 需求量 (千箱 ) 生产能力 (千箱 ) 成本 (千元 /千箱 )
1 15 30 5.0
2 25 40 5.1
3 35 45 5.4
4 25 20 5.5
合计 100 135
生产批量问题的一般提法
ct ~时段 t 生产费用 (元 /件 )；
ht ~时段 t (末 )库存费 (元 /件 )；
st ~时段 t 生产准备费 (元 )；
dt ~时段 t 市场需求 (件 )；
Mt ~时段 t 生产能力 (件 )。
假设初始库存为 0
制订生产计划,满足需求,并使 T个时段的总费用最小。
tttt dyxy 1
)( m i n
1
ttttt
T
t
t yhxcwsz
0,,00 ttT yxyy
tt
t
t
t Mxx
xw?
,0,0
,0,1
决策变量
xt ~时段 t 生产量；
yt ~时段 t (末 )库存量；
wt =1 ~时段 t 开工 生产
(wt =0 ~不开工 )。
目标约束混合 0-1规划模型最优解,x1~ x4,15,40,45,0； 总费用,554.0(千元 )
生产批量问题的一般提法
tttt dyxyts 1..
)( m i n
1
ttttt
T
t
t yhxcwsz
Tt
yxyy ttT
,2,1
0,,00
tt
t
t
t Mxx
xw?
,0,0
,0,1
将所给参数代入模型，用 LINDO求解
0 ttt wMx
生产中通过切割、剪裁、冲压等手段，将原材料加工成所需大小
§ 6 钢管和易拉罐下料原料下料问题按照工艺要求，确定下料方案，
使所用材料最省，或利润最大问题 1,如何下料最节省?
例 1 钢管下料问题 2,客户增加需求：
原料钢管,每根 19米
4米 50根 6米 20根 8米 15根客户需求节省的标准是什么？
由于采用不同切割模式太多，会增加生产和管理成本，
规定切割模式不能超过 3种。如何下料最节省？
5米 10根按照客户需要在一根原料钢管上安排切割的一种组合。
切割模式余料 1米4米 1根 6米 1根 8米 1根余料 3米4米 1根 6米 1根 6米 1根合理切割模式 的余料应小于客户需要钢管的最小尺寸余料 3米8米 1根 8米 1根钢管下料为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？
合理切割模式
2,所用原料钢管总根数最少模式 4米钢管根数 6米钢管根数 8米钢管根数 余料 (米 )
1 4 0 0 3
2 3 1 0 1
3 2 0 1 3
4 1 2 0 3
5 1 1 1 1
6 0 3 0 1
7 0 0 2 3
钢管下料问题 1
两种标准
1,原料钢管剩余总余量最小
xi ~按第 i 种模式切割的原料钢管根数 (i=1,2,…7 )
约束 满足需求决策变量目标 1（总余量）
76543211 3333 xxxxxxxZM i n
50234 54321 xxxxx
2032 6542 xxxx
152 753 xxx
按模式 2切割 12根,按模式 5切割 15根，余料 27米模式
4米根数
6米根数
8米根数余料
1 4 0 0 3
2 3 1 0 1
3 2 0 1 3
4 1 2 0 3
5 1 1 1 1
6 0 3 0 1
7 0 0 2 3
需求
50 20 15
最优解,x2=12,x5=15,
其余为 0；
最优值,27。
整数约束,xi 为整数当余料没有用处时,通常以总根数最少为目标
76543212 xxxxxxxZM i n
目标 2（总根数）
钢管下料问题 1
约束条件不变最优解,x2=15,
x5=5,x7=5,
其余为 0；
最优值,25。
50234 54321 xxxxx
2032 6542 xxxx
152 753 xxx
xi 为整数按模式 2切割 15根，
按模式 5切割 5根，
按模式 7切割 5根，
共 25根，余料 35米 虽余料增加 8米，但减少了 2根与 目标 1的结果“共切割
27根，余料 27米” 相比钢管下料问题 2
对大规模问题,用模型的约束条件界定合理模式增加一种需求,5米 10根；切割 模式不超过 3种 。
现有 4种 需求,4米 50根,5米 10根,6米 20根,8米
15根，用枚举法确定合理切割模式，过于复杂。
决策变量
xi ~按第 i 种模式切割的原料钢管根数 (i=1,2,3)
r1i,r2i,r3i,r4i ~ 第 i 种切割模式下，每根原料钢管生产 4米,5米,6米和 8米长的钢管的数量满足需求
50313212111 xrxrxr
10323222121 xrxrxr
20333232131 xrxrxr
15343242141 xrxrxr
模式合理：每根余料不超过 3米
19865416 41312111 rrrr
19865416 42322212 rrrr
19865416 43332313 rrrr
整数非线性规划模型钢管下料问题 2
目标函数（ 总根数）
321 xxxM i n
约束条件整数约束,xi,r1i,r2i,
r3i,r4i (i=1,2,3)为整数增加约束，缩小可行域，便于求解
321 xxx
原料钢管总根数下界,2619 158206105504
特殊生产计划：对每根原料钢管模式 1：切割成 4根 4米钢管，需 13根；
模式 2：切割成 1根 5米和 2根 6米钢管，需 10根；
模式 3：切割成 2根 8米钢管，需 8根。
原料钢管总根数上界,13+10+8=31
3126 321 xxx
模式排列顺序可任定钢管下料问题 2
需求,4米 50根,5米 10
根,6米 20根,8米 15根每根原料钢管长 19米
LINGO求解整数非线性规划模型
Local optimal solution found at
iteration,12211
Objective value,28.00000
Variable Value Reduced Cost
X1 10.00000 0.000000
X2 10.00000 2.000000
X3 8.000000 1.000000
R11 3.000000 0.000000
R12 2.000000 0.000000
R13 0.000000 0.000000
R21 0.000000 0.000000
R22 1.000000 0.000000
R23 0.000000 0.000000
R31 1.000000 0.000000
R32 1.000000 0.000000
R33 0.000000 0.000000
R41 0.000000 0.000000
R42 0.000000 0.000000
R43 2.000000 0.000000
模式 1：每根原料钢管切割成 3
根 4米和 1根 6米钢管，共 10根；
模式 2：每根原料钢管切割成 2
根 4米,1根 5米和 1根 6米钢管，
共 10根；
模式 3：每根原料钢管切割成 2
根 8米钢管，共 8根。
原料钢管总根数为 28根。
板材 规格 2：
长方形，
32?28cm，
2万张。
例 2 易拉罐下料每周工作 40小时，每只易拉罐利润 0.10元，原料余料损失 0.001元
/ cm2（不能装配的罐身,盖,底也是余料）
模式 1,1.5秒 模式 2,2秒 模式 3,1秒模式 4,3秒上盖下底罐身罐身高 10cm，
上 盖,下底直径均 5cm。
板材规格 1：
正方形，边长
24cm,5万张。
如何安排每周生产？
罐身个数 底、盖个数余料损失
（ cm2）
冲压时间
（秒）
模式 1 1 10 222.6 1.5
模式 2 2 4 183.3 2
模式 3 0 16 261.8 1
模式 4 4 5 169.5 3
模式 1:
正方形边长 24cm
问题分析 计算各种模式下的余料损失上、下底直径 d=5cm，
罐身高 h=10cm。
模式 1 余料损失 242-10d2/4 -?dh=222.6 cm2
问题分析目标,易拉罐利润扣除原料余料损失后的净利润最大约束,每周工作时间不超过 40小时；
原料数量,规格 1（模式 1 ~3） 5万张，
规格 2（模式 4） 2万张；
罐身和底、盖的配套组装 。
注意：不能装配的罐身、上下底也是余料决策变量
xi ~ 按照第 i 种模式的生产张数 (i=1,2,3,4)；
y1 ~ 一周生产的易拉罐个数；
y2 ~ 不配套的罐身个数；
y3 ~ 不配套的底、盖个数。
模型建立目标约束条件
)6.191.1575.1698.261
3.1836.222(001.01.0
3243
211
yyxx
xxyM ax
时间约束 1 4 4 0 0 0325.1 4321 xxxx
原料约束,50000
321 xxx 2 0 0 0 04?x
产量 余料 时间
x1 222.6 1.5
x2 183.3 2
x3 261.8 1
x4 169.5 3
模型建立 y1 ~ 易拉罐个数； y2 ~ 不配套的罐身；
y3 ~ 不配套的底、盖。
每只易拉罐利润 0.10元，
余料损失 0.001元 / cm2
罐身 面积?dh=157.1 cm2
底盖 面积?d2/4=19.6 cm2
(40小时 )
约束条件配套约束
}2/)516410(,42m i n { 43214211 xxxxxxxy
14212 42 yxxxy
143213 2516410 yxxxxy
,42 4211 xxxy 2/)516410( 43211 xxxxy
y1 ~ 易拉罐个数； y2 ~ 不配套的罐身；
y3 ~ 不配套的底、盖。
罐身 底、盖
1 10
2 4
0 16
4 5
产量
x1
x2
x3
x4
虽然 xi和 y1,y2,y3应是整数，但是因生产量很大，
可以把它们看成实数，从而用线性规划模型处理 。
将所有决策变量扩大 10000倍（ xi ~万张,yi ~万件）
LINDO发出警告信息：,数据之间的数量级差别太大，建议进行预处理，缩小数据之间的差别,
模式 2生产 40125张，
模式 3生产 3750张，
模式 4生产 20000张，
共产易拉罐 160250个
(罐身和底、盖无剩余 )，
净利润为 4298元
,5321 xxx 24?x
模型求解
OBJECTIVE FUNCTION VALUE
1) 0.4298337
VARIABLE VALUE REDUCED COST
Y1 16.025000 0.000000
X1 0.000000 0.000050
X2 4.012500 0.000000
X3 0.375000 0.000000
X4 2.000000 0.000000
Y2 0.000000 0.223331
Y3 0.000000 0.036484
,4.14325.1 4321 xxxx
下料问题的建模
确定下料模式? 构造优化模型规格不太多，可枚举下料模式，建立整数线性规划模型，
否则要构造整数非线性规划模型，求解困难，可用 缩小可行域 的方法进行化简，但要保证最优解的存在。
一维问题（如钢管下料）
二维问题（如易拉罐下料）
具体问题具体分析（比较复杂 ）
