1
鲁志波信息工程大学理学院数学规划模型
2
1 规划模型的基本概念
2 规划模型与 LINDO求解主要内容
3
规划模型的一般形式 三要素
(1) 决策变量,通常是该问题要求解的那些未知量,不妨用 n 维向量 x =(x1,x2,…,xn )T表示,当对 x 赋值后通常称为该问题的一个解
(2) 目标函数,通常是该问题要优化 (最大或最小 )
的那个目标的数学表达式,它是决策变量 x 的函数,可以记作 f(x)
1 规划模型的基本概念
(3) 约束条件,由该问题对决策的限制条件给出,
即 x允许取值的范围 x∈ Ω,Ω称为可行域。通常
4
用一组关于 x的等式 gi(x)=0(i=1,2,…,k)或不等式
hj(x)≤0(j= 1,2,…,l )来界定,分别称为等式约束和不等式约束规划模型的一般数学形式：
opt z=f(x) (1)
s.t,gi(x)=0 (i=1,2,…,k） (2)
hj(x)≤0 (j= 1,2,…,l) (3)
其中 opt是最优化的意思,可以是 min或 max两者之一 ; s,t.是“受约束于” (subject to)的意思
5
可行解和最优解同时满足约束条件⑵和⑶的解 x(x?Ω)称为 可行解,否则 称 为 不可行解满足条件 (1)的可行解 x* 称为 最优解,在最优解
x* 处目标函数的取值 f (x*)称为 最优值基本类型规划模型连续型规划离散型规划线性规划非线性规划整数规划
0-1规划
6
例 1 加工奶制品的生产计划
1桶牛奶
3千克 A112小时
8小时 4千克 A2
或获利 24元 /千克获利 16元 /千克制订生产计划,使每天获利最大
35元可买到 1桶牛奶,买吗? 若买,每天最多买多少?
可聘用临时工人,付出的工资最多是每小时几元?
A1的获利增加到 30元 /千克,是否改变生产计划?
50桶牛奶 时间 480小时 至多加工 100千克 A1每天,
2 规划模型与 LINDO求解
7
x1桶牛奶生产 A1 x2桶牛奶生产 A2
获利 24× 3x1 获利 16× 4 x2
原料供应 5021 xx
劳动时间 480812 21 xx
加工能力 1003 1?x
决策变量目标函数
21 6472 xxzM ax
每天获利约束条件 非负约束
0,21?xx
线性规划模型
(LP)
50桶牛奶 时间 480小时 至多加工 100千克 A1每天,
模型建立
1桶牛奶
3千克 A112小时
8小时 4千克 A2
或获利 24元 /千克获利 16元 /千克
8
模型求解 图解法
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=3360
z=c (常数 ) ~等值线
c
在 B(20,30)点得到最优解目标函数和约束条件是线性函数可行域为直线段围成的凸多边形目标函数的等值线为直线最优解在凸多边形的某个顶点取得
9
模型求解 软件实现 --LINDO
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 DUAL PRICES
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元
10
结果解释原料无剩余时间无剩余三种资源
“资源” 剩余为零的约束为紧约束 (有效约束 )
OBJECTIVE FUNCTION VALUE
1) 3360.000
VARIABLE VALUE REDUCED COST
X1 20.000000 0.000000
X2 30.000000 0.000000
ROW SLACK OR SURPLUS DUAL PRICES
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
11
影子价格
35元可买到 1桶牛奶,要买吗? 35 <48,应该买 !
聘用临时工人付出的工资最多每小时几元? 2元 !
OBJECTIVE FUNCTION VALUE
1) 3360.000
VARIABLE VALUE REDUCED COST
X1 20.000000 0.000000
X2 30.000000 0.000000
ROW SLACK OR SURPLUS DUAL PRICES
2) 0.000000 48.000000
3) 0.000000 2.000000
4) 40.000000 0.000000
NO,ITERATIONS= 2
原料增加 1单位,利润增长 48
时间增加 1单位,利润增长 2
加工能力增长不影响利润最优解下“资源”增加 1单位时“效益”的增量
12
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
在 允许范围内不变 !
约束条件不变最优解不变时目标函数系数允许变化范围
13
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桶 !
目标函数不变
14
例 2 奶制品的生产销售计划在例 1基础上深加工
0.8千克 B1
2小时,3元
1千克 44元 /千克
0.75千克 B22小时,3元1千克 32元 /千克制订生产销售计划,使每天净利润最大
50桶牛奶,480小时 至多 100千克 A1
12小时
8小时
3千克 A1
4千克 A2
获利 24元 /千克获利 16元 /公斤
1桶牛奶 或
30元可增加 1桶牛奶,3元可增加 1小时时间,是否投资? 现投资 150元,可赚回多少?
15
销售 x1千克 A1,x2千克 A2,x3千克 B1,x4千克 B2决策变量目标函数非负约束
16,,0xx?
x5千克 A1加工 B1,x6千克 A2加工 B2
654321 3332441624 xxxxxxzM a x
原料供应
5043 6251 xxxx
劳动时间 48022)(2)(4
656251 xxxxxx
加工能力 100
51 xx
附加约束
53 8.0 xx? 64
750 x.x?
约束条件模型建立
16
模型求解 软件实现 --LINDO
max 24x1+16x2+44x3+32x4-3x5-3x6
st
2) 4x1+3x2 +4x5 +3x6 <600
3) 4x1+2x2 +6x5 +4x6 <480
4) x1 +x5 <100
5) x3-0.8x5=0
6) x4-0.75x6 =0
end
5043)2 6251 xxxx 6 0 0334)2 6521 xxxx 4
1 5 2 6
56
3 ) 4 ( ) 2 ( )
2 2 4 8 0
x x x x
xx
4 8 04624)3 6521 xxxx
17
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元
42桶牛奶加工成 A2
8桶牛奶加工成 A1
并将得到的 24千克
A1全部加工成 B1
除加工能力外均为紧约束
18
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
6 0 0334)2 6521 xxxx 4
5043)2 6251 xxxx
增加 1小时时间使利润增长 3.26
30元可增加 1桶牛奶,3元可增加 1
小时时间,应否投资? 现投资 150
元,可赚回多少?
投资 150元增加 5桶牛奶,可赚回 189.6元 (大于增加时间的利润增长 )
19
B1获利下降 10%,超出 x3 系数允许范围
B1,B2的获利有 10%的波动,对计划有无影响
DO RANGE
(SENSITIVITY)
ANALYSIS? Yes
B2获利上升 10%,超出 x4 系数允许范围波动对计划有影响生产计划应重新制订,若将目标函数中 x3的系数改为 39.6,重新 计算,会发现结果有很大变化
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
…… ……
20
1,用,TITLE” 对模型命名 (最多 72个字符 ),如：
TITLE This Model is only an Example
2.,!”符号的后面部分为注释,如,! It’s Comment,
3,目标函数所在行是第一行，第二行起为约束条件
4,行号 (行名 )自动产生或人为定义,以“）”结束
5,变量名不区分大小写,且以字母开头,不超过 8个字符
6,变量与系数间可有空格 (甚至回车 ),但无运算符
7.,>”（或,<”）号与,>=”（或,<=”）功能相同
8,变量不能出现在约束条件的右端使用 LINDO的一些注意事项
21
9,表达式中不接受括号和逗号等任何符号,如,
400(X1+X2)需写为 400X1+400X2
10,表达式应化简,如 2X1+3X2-4X1应写成 -2X1+3X2
11,缺省假定所有变量非负 ; 可在模型的,END”语句后用,FREE name”将变量 name的非负假定取消
12,可在,END”后用,SUB” 或,SLB” 设定变量上下界例如：,sub x1 10”的作用等价于,x1<=10”
13.,END”后对 0-1变量说明,INT n 或 INT name
14.,END”后对整数变量说明,GIN n 或 GIN name
22
为了选修课程门数最少，应学习哪些课程？
例 2 选课策略要求至少选两门数学课、三门运筹学课和两门计算机课课号 课名 学分 所属类别 先修课要求
1 微积分 5 数学
2 线性代数 4 数学
3 最优化方法 4 数学；运筹学 微积分；线性代数
4 数据结构 3 数学；计算机 计算机编程
5 应用统计 4 数学；运筹学 微积分；线性代数
6 计算机模拟 3 计算机；运筹学 计算机编程
7 计算机编程 2 计算机
8 预测理论 2 运筹学 应用统计
9 数学实验 3 运筹学；计算机 微积分；线性代数选修课程最少，且学分尽量多，应学习哪些课程？
23
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 数学实验 运筹学；计算机
24
先修课程要求
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 数学实验 微积分；线性代数
25
学分最多多目标优化的处理方法：化成单目标优化。
两目标 (多目标 )规划
9876
54321
3223
43445
xxxx
xxxxxWM a x
},{ WZM in?
讨论：选修课程最少，学分尽量多，应学习哪些课程？
9
1i
ixZM in
课程最少
以 学分最多为目标，
不管课程多少。
以课程最少 为目标，
不管学分多少。
最优解如上,6门课程，总学分 21 。
最优解显然是选修所有 9门课程 。
26
多目标规划
在 课程最少的前提下以 学分最多为目标。
最优解,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
27
多目标规划
对学分数和课程数加权形成一个目标，如三七开。
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
28
讨论与思考
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的结果相同 ——课程最少
29
作业：
教材 260页 第 1题
鲁志波信息工程大学理学院数学规划模型
2
1 规划模型的基本概念
2 规划模型与 LINDO求解主要内容
3
规划模型的一般形式 三要素
(1) 决策变量,通常是该问题要求解的那些未知量,不妨用 n 维向量 x =(x1,x2,…,xn )T表示,当对 x 赋值后通常称为该问题的一个解
(2) 目标函数,通常是该问题要优化 (最大或最小 )
的那个目标的数学表达式,它是决策变量 x 的函数,可以记作 f(x)
1 规划模型的基本概念
(3) 约束条件,由该问题对决策的限制条件给出,
即 x允许取值的范围 x∈ Ω,Ω称为可行域。通常
4
用一组关于 x的等式 gi(x)=0(i=1,2,…,k)或不等式
hj(x)≤0(j= 1,2,…,l )来界定,分别称为等式约束和不等式约束规划模型的一般数学形式：
opt z=f(x) (1)
s.t,gi(x)=0 (i=1,2,…,k） (2)
hj(x)≤0 (j= 1,2,…,l) (3)
其中 opt是最优化的意思,可以是 min或 max两者之一 ; s,t.是“受约束于” (subject to)的意思
5
可行解和最优解同时满足约束条件⑵和⑶的解 x(x?Ω)称为 可行解,否则 称 为 不可行解满足条件 (1)的可行解 x* 称为 最优解,在最优解
x* 处目标函数的取值 f (x*)称为 最优值基本类型规划模型连续型规划离散型规划线性规划非线性规划整数规划
0-1规划
6
例 1 加工奶制品的生产计划
1桶牛奶
3千克 A112小时
8小时 4千克 A2
或获利 24元 /千克获利 16元 /千克制订生产计划,使每天获利最大
35元可买到 1桶牛奶,买吗? 若买,每天最多买多少?
可聘用临时工人,付出的工资最多是每小时几元?
A1的获利增加到 30元 /千克,是否改变生产计划?
50桶牛奶 时间 480小时 至多加工 100千克 A1每天,
2 规划模型与 LINDO求解
7
x1桶牛奶生产 A1 x2桶牛奶生产 A2
获利 24× 3x1 获利 16× 4 x2
原料供应 5021 xx
劳动时间 480812 21 xx
加工能力 1003 1?x
决策变量目标函数
21 6472 xxzM ax
每天获利约束条件 非负约束
0,21?xx
线性规划模型
(LP)
50桶牛奶 时间 480小时 至多加工 100千克 A1每天,
模型建立
1桶牛奶
3千克 A112小时
8小时 4千克 A2
或获利 24元 /千克获利 16元 /千克
8
模型求解 图解法
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=3360
z=c (常数 ) ~等值线
c
在 B(20,30)点得到最优解目标函数和约束条件是线性函数可行域为直线段围成的凸多边形目标函数的等值线为直线最优解在凸多边形的某个顶点取得
9
模型求解 软件实现 --LINDO
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 DUAL PRICES
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元
10
结果解释原料无剩余时间无剩余三种资源
“资源” 剩余为零的约束为紧约束 (有效约束 )
OBJECTIVE FUNCTION VALUE
1) 3360.000
VARIABLE VALUE REDUCED COST
X1 20.000000 0.000000
X2 30.000000 0.000000
ROW SLACK OR SURPLUS DUAL PRICES
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
11
影子价格
35元可买到 1桶牛奶,要买吗? 35 <48,应该买 !
聘用临时工人付出的工资最多每小时几元? 2元 !
OBJECTIVE FUNCTION VALUE
1) 3360.000
VARIABLE VALUE REDUCED COST
X1 20.000000 0.000000
X2 30.000000 0.000000
ROW SLACK OR SURPLUS DUAL PRICES
2) 0.000000 48.000000
3) 0.000000 2.000000
4) 40.000000 0.000000
NO,ITERATIONS= 2
原料增加 1单位,利润增长 48
时间增加 1单位,利润增长 2
加工能力增长不影响利润最优解下“资源”增加 1单位时“效益”的增量
12
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
在 允许范围内不变 !
约束条件不变最优解不变时目标函数系数允许变化范围
13
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桶 !
目标函数不变
14
例 2 奶制品的生产销售计划在例 1基础上深加工
0.8千克 B1
2小时,3元
1千克 44元 /千克
0.75千克 B22小时,3元1千克 32元 /千克制订生产销售计划,使每天净利润最大
50桶牛奶,480小时 至多 100千克 A1
12小时
8小时
3千克 A1
4千克 A2
获利 24元 /千克获利 16元 /公斤
1桶牛奶 或
30元可增加 1桶牛奶,3元可增加 1小时时间,是否投资? 现投资 150元,可赚回多少?
15
销售 x1千克 A1,x2千克 A2,x3千克 B1,x4千克 B2决策变量目标函数非负约束
16,,0xx?
x5千克 A1加工 B1,x6千克 A2加工 B2
654321 3332441624 xxxxxxzM a x
原料供应
5043 6251 xxxx
劳动时间 48022)(2)(4
656251 xxxxxx
加工能力 100
51 xx
附加约束
53 8.0 xx? 64
750 x.x?
约束条件模型建立
16
模型求解 软件实现 --LINDO
max 24x1+16x2+44x3+32x4-3x5-3x6
st
2) 4x1+3x2 +4x5 +3x6 <600
3) 4x1+2x2 +6x5 +4x6 <480
4) x1 +x5 <100
5) x3-0.8x5=0
6) x4-0.75x6 =0
end
5043)2 6251 xxxx 6 0 0334)2 6521 xxxx 4
1 5 2 6
56
3 ) 4 ( ) 2 ( )
2 2 4 8 0
x x x x
xx
4 8 04624)3 6521 xxxx
17
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元
42桶牛奶加工成 A2
8桶牛奶加工成 A1
并将得到的 24千克
A1全部加工成 B1
除加工能力外均为紧约束
18
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
6 0 0334)2 6521 xxxx 4
5043)2 6251 xxxx
增加 1小时时间使利润增长 3.26
30元可增加 1桶牛奶,3元可增加 1
小时时间,应否投资? 现投资 150
元,可赚回多少?
投资 150元增加 5桶牛奶,可赚回 189.6元 (大于增加时间的利润增长 )
19
B1获利下降 10%,超出 x3 系数允许范围
B1,B2的获利有 10%的波动,对计划有无影响
DO RANGE
(SENSITIVITY)
ANALYSIS? Yes
B2获利上升 10%,超出 x4 系数允许范围波动对计划有影响生产计划应重新制订,若将目标函数中 x3的系数改为 39.6,重新 计算,会发现结果有很大变化
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
…… ……
20
1,用,TITLE” 对模型命名 (最多 72个字符 ),如：
TITLE This Model is only an Example
2.,!”符号的后面部分为注释,如,! It’s Comment,
3,目标函数所在行是第一行，第二行起为约束条件
4,行号 (行名 )自动产生或人为定义,以“）”结束
5,变量名不区分大小写,且以字母开头,不超过 8个字符
6,变量与系数间可有空格 (甚至回车 ),但无运算符
7.,>”（或,<”）号与,>=”（或,<=”）功能相同
8,变量不能出现在约束条件的右端使用 LINDO的一些注意事项
21
9,表达式中不接受括号和逗号等任何符号,如,
400(X1+X2)需写为 400X1+400X2
10,表达式应化简,如 2X1+3X2-4X1应写成 -2X1+3X2
11,缺省假定所有变量非负 ; 可在模型的,END”语句后用,FREE name”将变量 name的非负假定取消
12,可在,END”后用,SUB” 或,SLB” 设定变量上下界例如：,sub x1 10”的作用等价于,x1<=10”
13.,END”后对 0-1变量说明,INT n 或 INT name
14.,END”后对整数变量说明,GIN n 或 GIN name
22
为了选修课程门数最少，应学习哪些课程？
例 2 选课策略要求至少选两门数学课、三门运筹学课和两门计算机课课号 课名 学分 所属类别 先修课要求
1 微积分 5 数学
2 线性代数 4 数学
3 最优化方法 4 数学；运筹学 微积分；线性代数
4 数据结构 3 数学；计算机 计算机编程
5 应用统计 4 数学；运筹学 微积分；线性代数
6 计算机模拟 3 计算机；运筹学 计算机编程
7 计算机编程 2 计算机
8 预测理论 2 运筹学 应用统计
9 数学实验 3 运筹学；计算机 微积分；线性代数选修课程最少，且学分尽量多，应学习哪些课程？
23
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 数学实验 运筹学；计算机
24
先修课程要求
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 数学实验 微积分；线性代数
25
学分最多多目标优化的处理方法：化成单目标优化。
两目标 (多目标 )规划
9876
54321
3223
43445
xxxx
xxxxxWM a x
},{ WZM in?
讨论：选修课程最少，学分尽量多，应学习哪些课程？
9
1i
ixZM in
课程最少
以 学分最多为目标，
不管课程多少。
以课程最少 为目标，
不管学分多少。
最优解如上,6门课程，总学分 21 。
最优解显然是选修所有 9门课程 。
26
多目标规划
在 课程最少的前提下以 学分最多为目标。
最优解,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
27
多目标规划
对学分数和课程数加权形成一个目标，如三七开。
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
28
讨论与思考
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的结果相同 ——课程最少
29
作业：
教材 260页 第 1题
