优 化 建 模优化建模与 LINDO/LINGO软件第 1 章 引 言
［原书相关信息］
谢金星,薛毅编著,清华大学出版社,2005年 7月第 1版,
http://faculty.math.tsinghua.edu.cn/~jxie/lindo
优 化 建 模内容提要
1,优化模型的基本概念
2,优化问题的建模实例
3,LINDO/LINGO 软件简介优 化 建 模
1,优化模型的基本概念优 化 建 模最优化是工程技术、经济管理、科学研究、社会生活中经常遇到的问题,如,
优化模型和算法的重要意义结构设计 资源分配 生产计划 运输方案解决优化问题的手段
经验积累，主观判断
作试验，比优劣
建立数学模型，求解最优策略最优化,在一定条件下，寻求使目标最大 (小 )的决策优 化 建 模优化问题三要素,决策变量 ； 目标函数 ； 约束条件约束条件决策变量优化问题的一般形式
n
j
i
Dx
ljxg
mixhts
xf
,.,,,1,0)(
,.,,,1,0)(..
)(m i n
无约束优化 (没有约束 )与约束优化 (有约束 )
可行解（只满足约束）与最优解 (取到最优值 )
目标函数优 化 建 模局部最优解与整体最优解
局部最优解 (Local Optimal Solution,如 x1 )
整体最优解 (Global Optimal Solution,如 x2 )
x
*
f(x)
x1
x2o
优 化 建 模优化模型的简单分类
线性规划 (LP) 目标和约束均为线性函数
非线性规划 (NLP) 目标或约束中存在非线性函数
二次规划 (QP) 目标为二次函数、约束为线性
整数规划 (IP) 决策变量 (全部或部分 )为整数
整数 线性 规划 (ILP)，整数 非线性 规划 (INLP)
纯整数规划 (PIP),混合整数规划 (MIP)
一般整数规划,0-1（整数）规划
n
j
i
Dx
ljxg
mixhts
xf
,.,,,1,0)(
,.,,,1,0)(..
)(m i n
连续优化离散优化数学规划优 化 建 模优化模型的简单分类和求解难度优化线性规划 非线性规划二次规划连续优化 整数规划问题求解的难度增加优 化 建 模
2,优化问题的建模实例优 化 建 模
1桶牛奶
3公斤 A112小时
8小时 4公斤 A2
或获利 24元 /公斤获利 16元 /公斤
50桶牛奶 时间 480小时 至多加工 100公斤 A1
制订生产计划，使每天获利最大
35元可买到 1桶牛奶，买吗？若买，每天最多买多少?
可聘用临时工人，付出的工资最多是每小时几元?
A1的获利增加到 30元 /公斤，应否改变生产计划？
每天：
线性规划模型－例 1.1,奶制品生产计划优 化 建 模
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)点得到最优解目标函数和约束条件是线性函数可行域为直线段围成的凸多边形目标函数的等值线为直线最优解一定在凸多边形的某个顶点取得。
优 化 建 模求解 LP的基本思想思路：从可行域的某一顶点开始，只需在有限多个顶点中一个一个找下去，一定能得到 最优解 。
LP的约束和目标函数均为线性函数
2维可行域 线段组成的凸多边形目标函数 等值线为直线最优解 凸多边形的某个顶点
n维超平面组成的凸多面体等值线是超平面凸多面体的某个顶点
LP的通常解法是单纯形法 (G,B,Dantzig,1947)
优 化 建 模内点算法 (Interior point method)
20世纪 80年代人们提出的一类新的算法 —— 内点算法
也是迭代法，但不再从可行域的一个顶点转换到另一个顶点，而是直接从可行域的内部逼近最优解。
LP其他算法有效集 (Active Set)方法
LP是 QP的特例（只需令所有二次项为零即可）
可以用 QP的算法解 QP(如,有效集方法 )
优 化 建 模线性规划模型的解的几种情况线性规划问题有可行解 (Feasible)
无可行解
（ Infeasible）
有最优解 （ Optimal） 无最优解
(Unbounded)
优 化 建 模牌号 产量 成本 价格甲 x1 q1 p1
乙 x2 q2 p2假设 A 产销平衡假设 B p随 x (两种牌号 )增加而减小，呈线性关系
12111211121211111,0,,,aaaabxaxabp
某厂生产两个牌号的同一种产品，如何确定产量使利润最大
21222221222212122,0,,,aaaabxaxabp
二次规划模型－例 1.2：产销计划问题优 化 建 模
22211121,)()(),(m a x
21
xqpxqpxxz
xx
目标 利润最大
= （ 100-x1-0.1 x2-2） x1
+（ 280-0.2x1-2x2-3） x2
=98 x1 + 277 x2 － x12 － 0.3 x1 x2 － 2x22
约束
x1 + x2 ≤100
x1 ≤ 2 x2
x1,x2 ≥ 0
二次规划模型 (QP)
若还要求产量为整数，则是整数二次规划模型 (IQP)
优 化 建 模非线性规划模型－例 1.3：选址问题某公司有 6个建筑工地，位置坐标为 (ai,bi) (单位：公里 ),
水泥日用量 di (单位：吨）i １ ２ ３ ４ ５ ６
a 1,2 5 8,7 5 0,5 5,7 5 3 7,2 5
b 1,2 5 0,7 5 4,7 5 5 6,5 7,7 5
d 3 5 4 7 6 11
1) 现有 2 料场，位于 A ( 5,1 ),B ( 2,7 ),
记 ( x j,y j ),j = 1,2,日储量 e j 各有 20 吨。
假设,料场和工地之间有直线道路目标,制定每天的供应计划，即从 A,B 两料场分别向各工地运送多少吨水泥，使总的吨公里数最小。
优 化 建 模用例中数据计算，
最优解为
i 1 2 3 4 5 6
1i
c （料场 A ） 3 5 0 7 0 1
2i
c （料场 B ） 0 0 4 0 6 10
总吨公里数为 136.2
2,1,
6,.,,,1,..
])()[(m i n
6
1
2
1
2
1
6
1
2/122
jec
idcts
byaxc
jij
i
iij
j
j i
ijijij
线性规划模型 (LP)
决策变量,ci j
(料场 j到 工地 i的运量） ~12维优 化 建 模选址问题,NLP
2）改建两个新料场，需要确定新料场位置 (xj,yj)和运量 cij,在其它条件不变下使总吨公里数最小。
2,1,
6,.,,,1,..
])()[(m i n
6
1
2
1
2
1
6
1
2/122
jec
idcts
byaxc
jij
i
iij
j
j i
ijijij
决策变量：
ci j,(xj,yj)~16维非线性规划模型
(NLP)
优 化 建 模整数规划 - 例 1.4,聘用方案某服务部门一周中每天需要不同数目的雇员：周一到周四每天至少 50 人，周五和周日每天至少 80 人，周六至少 90 人。
决策变量,周一至周日每天 (新 )聘用人数 x1,x2,? x7
目标函数,7天 (新 )聘用人数之和约束条件,周一至周日每天需要人数现规定应聘者需 连续工作 5 天，试确定聘用方案，即周一到周日每天聘用多少人，使在满足需要的条件下聘用总人数最少。
优 化 建 模
80
90
80
50
50
50
50..
m i n
76543
65432
54321
74321
76321
76521
76541
7654321
xxxxx
xxxxx
xxxxx
xxxxx
xxxxx
xxxxx
xxxxxts
xxxxxxxz
连续工作 5天
5017654 xxxxx
周一工作的应是 (上 )周四至周一聘用的设系统已进入稳态（不是开始的几周）聘用方案即为非负整数
， Zx i
整数规划模型 (IP)
优 化 建 模丁的蛙泳成绩退步到 1’15”2；戊的自由泳成绩进步到 57”5,组成接力队的方案是否应该调整？
如何选拔队员组成 4?100米混合泳接力队?
0-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
例 1.5,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
0-1规划,
整数规划的特例优 化 建 模整数规划问题一般形式
ljxg
mixhts
xf
j
i
Zx
n
,.,,,1,0)(
,.,,,1,0)(..
)(m i n
整数线性规划 (ILP) 目标和约束均为线性函数
整数非线性规划 (NLP) 目标或约束中存在非线性函数整数规划问题的分类
纯 (全 )整数规划 (PIP) 决策变量均为整数
混合整数规划 (MIP) 决策变量有整数，也有实数
0-1规划 决策变量只取 0或 1
优 化 建 模取消整数规划中决策变量为整数的限制（ 松弛 ），对应的连续优化问题称为原问题的 松弛问题整数规划问题对应的松弛问题松弛问题松弛整数规划问题 最优解最优解整数非整数 整数舍入下界（对 Min问题）
上界（对 Max问题）
非最优解优 化 建 模用连续优化方法求解松弛问题，如果松弛问题最优解
（分量）全为整数，则也是原整数规划问题的最优解对松弛问题的最优解（分量）舍入为整数，得到的往往不是原整数规划问题的最优解（甚至不是可行解）
IP可行解对应于整点 A(2,2)和 B(1,1),而最优解为 A点,
但 LP松弛的最优解为 C(3.5,2.5)
目标函数下降方向
x1
x2
C
A
B
O
优 化 建 模且为整数0,
4595
6..
85m ax
21
21
21
21
xx
xx
xxts
xxz
．,,．
．,．,,
．．,．,
．．,,,
x1
x2
0
Po
6
9
Zmax
5
6
去掉整数限制后，可行域为点（ 0,0),(6,0),(0,5),
P (2.25,3.75) 围成的 4边形
LP 最优解 P P 的舍入解 最靠近 P 的可行解 IP 最优解
（ 2,2 5,3,7 5 ） （ 2,4 ） （ 2,3 ） （ 0,5 ）
z = 4 1,2 5 不可行 z = 3 4 z = 4 0
从 LP最优解经过简单的,移动”不一定能得到 IP最优解例 1.6
优 化 建 模基本思想,隐式地枚举一切可行解（,分而治之,）
所谓分枝,就是逐次对解空间 （ 可行域 ） 进行划分；而所谓定界,是指对于每个分枝 （ 或称子域 ）,要计算原问题的最优解的下界 （ 对极小化问题 ）,这些下界用来在求解过程中判定是否需要对目前的分枝进一步划分,
也就是尽可能去掉一些明显的非最优点,避免完全枚举,
分枝定界法（ B&B,Branch and Bound）
对于 极小化 问题，在子域上解 LP，其最优值是 IP限定在该子域时的下界； IP任意可行点的函数值是 IP的上界。
这里仅介绍整数线性规划的分枝定界算法优 化 建 模无约束优化更多的优化问题线性规划非线性规划网络优化组合优化整数规划不确定规划多目标规划目标规划动态规划连续优化 离散优化 从其他角度分类
应用广泛,生产和运作管理、经济与金融、图论和网络优化、目标规划问题、对策论、排队论、存储论，
以及更加综合、更加复杂的决策问题等
实际问题规模往往较大，用软件求解比较方便优 化 建 模
3,LINDO/LINGO软件简介优 化 建 模常用优化软件
1,LINDO/LINGO软件
2,MATLAB优化工具箱 / Mathematic的优化功能
3,SAS(统计分析 )软件的优化功能
4,EXCEL软件的优化功能
5,其他（如 CPLEX等）
优 化 建 模
MATLAB优化工具箱能求解的优化模型优化工具箱 3.0 (MATLAB 7.0 R14)
连续优化 离散优化无约束优化非线性极小
fminunc
非光滑 (不可微 )优化
fminsearch
非线性方程 (组 )
fzero
fsolve
全局优化暂缺非线性最小二乘
lsqnonlin
lsqcurvefit
线性规划
linprog
纯 0-1规划 bintprog
一般 IP(暂缺 )
非线性规划
fmincon
fminimax
fgoalattain
fseminf
上下界约束
fminbnd
fmincon
lsqnonlin
lsqcurvefit
约束线性最小二乘
lsqnonneg
lsqlin
约束优化二次规划
quadprog
优 化 建 模
LINDO 公司软件产品简要介绍美国芝加哥 (Chicago)大学的 Linus Schrage教授于 1980
年前后开发,后来成立 LINDO系统公司（ LINDO
Systems Inc.）,网址,http://www.lindo.com
LINDO,Linear INteractive and Discrete Optimizer (V6.1)
LINDO API,LINDO Application Programming Interface (V4.1)
LINGO,Linear INteractive General Optimizer (V10.0)
What’s Best!,(SpreadSheet e.g,EXCEL) (V8.0)
演 示 (试用 )版、高级版、超级版、工业版、扩展版 …
（求解 问题规模 和 选件 不同）
优 化 建 模
LINDO/LINGO软件能求解的模型优化线性规划 非线性规划二次规划连续优化 整数规划
LINDO LINGO
优 化 建 模
LINGO软件的功能与特点
LINGO模型的优点
集成了线性 (非线性 ) / 连续 (整数 ) 优化功能
具有多点搜索 / 全局优化功能
提供了灵活的编程语言 (矩阵生成器 )，可方便地输入模型
提供与其他数据文件的接口
提供与其他编程语言的接口
LINDO API 可用于自主开发
运行速度较快优 化 建 模
LP QP NLP IP 全局优化 (选 )
ILP IQP INLP
LINGO软件的求解过程
LINGO预处理程序线性优化求解程序 非线性优化求解程序分枝定界管理程序
1,确定常数
2,识别类型
1,单纯形算法
2,内点算法 (选 )
1、顺序线性规划法 (SLP)
2、广义既约梯度法 (GRG) (选 )
3、多点搜索 (Multistart) (选 )
优 化 建 模建模时需要注意的几个基本问题
1,尽量使用实数优化，减少整数约束和整数变量
2,尽量使用光滑优化，减少非光滑约束的个数如：尽量少使用绝对值、符号函数、多个变量求最大 /最小值、四舍五入、取整函数等
3,尽量使用线性模型，减少非线性约束和非线性变量的个数 （如 x/y <5 改为 x<5y）
4,合理设定变量上下界，尽可能给出变量初始值
5,模型中使用的参数数量级要适当 (如小于 103)
优 化 建 模自己练习，或课上布置布置作业内容
Thank you very much!
［原书相关信息］
谢金星,薛毅编著,清华大学出版社,2005年 7月第 1版,
http://faculty.math.tsinghua.edu.cn/~jxie/lindo
优 化 建 模内容提要
1,优化模型的基本概念
2,优化问题的建模实例
3,LINDO/LINGO 软件简介优 化 建 模
1,优化模型的基本概念优 化 建 模最优化是工程技术、经济管理、科学研究、社会生活中经常遇到的问题,如,
优化模型和算法的重要意义结构设计 资源分配 生产计划 运输方案解决优化问题的手段
经验积累，主观判断
作试验，比优劣
建立数学模型，求解最优策略最优化,在一定条件下，寻求使目标最大 (小 )的决策优 化 建 模优化问题三要素,决策变量 ； 目标函数 ； 约束条件约束条件决策变量优化问题的一般形式
n
j
i
Dx
ljxg
mixhts
xf
,.,,,1,0)(
,.,,,1,0)(..
)(m i n
无约束优化 (没有约束 )与约束优化 (有约束 )
可行解（只满足约束）与最优解 (取到最优值 )
目标函数优 化 建 模局部最优解与整体最优解
局部最优解 (Local Optimal Solution,如 x1 )
整体最优解 (Global Optimal Solution,如 x2 )
x
*
f(x)
x1
x2o
优 化 建 模优化模型的简单分类
线性规划 (LP) 目标和约束均为线性函数
非线性规划 (NLP) 目标或约束中存在非线性函数
二次规划 (QP) 目标为二次函数、约束为线性
整数规划 (IP) 决策变量 (全部或部分 )为整数
整数 线性 规划 (ILP)，整数 非线性 规划 (INLP)
纯整数规划 (PIP),混合整数规划 (MIP)
一般整数规划,0-1（整数）规划
n
j
i
Dx
ljxg
mixhts
xf
,.,,,1,0)(
,.,,,1,0)(..
)(m i n
连续优化离散优化数学规划优 化 建 模优化模型的简单分类和求解难度优化线性规划 非线性规划二次规划连续优化 整数规划问题求解的难度增加优 化 建 模
2,优化问题的建模实例优 化 建 模
1桶牛奶
3公斤 A112小时
8小时 4公斤 A2
或获利 24元 /公斤获利 16元 /公斤
50桶牛奶 时间 480小时 至多加工 100公斤 A1
制订生产计划，使每天获利最大
35元可买到 1桶牛奶，买吗？若买，每天最多买多少?
可聘用临时工人，付出的工资最多是每小时几元?
A1的获利增加到 30元 /公斤，应否改变生产计划？
每天：
线性规划模型－例 1.1,奶制品生产计划优 化 建 模
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)点得到最优解目标函数和约束条件是线性函数可行域为直线段围成的凸多边形目标函数的等值线为直线最优解一定在凸多边形的某个顶点取得。
优 化 建 模求解 LP的基本思想思路：从可行域的某一顶点开始，只需在有限多个顶点中一个一个找下去，一定能得到 最优解 。
LP的约束和目标函数均为线性函数
2维可行域 线段组成的凸多边形目标函数 等值线为直线最优解 凸多边形的某个顶点
n维超平面组成的凸多面体等值线是超平面凸多面体的某个顶点
LP的通常解法是单纯形法 (G,B,Dantzig,1947)
优 化 建 模内点算法 (Interior point method)
20世纪 80年代人们提出的一类新的算法 —— 内点算法
也是迭代法，但不再从可行域的一个顶点转换到另一个顶点，而是直接从可行域的内部逼近最优解。
LP其他算法有效集 (Active Set)方法
LP是 QP的特例（只需令所有二次项为零即可）
可以用 QP的算法解 QP(如,有效集方法 )
优 化 建 模线性规划模型的解的几种情况线性规划问题有可行解 (Feasible)
无可行解
（ Infeasible）
有最优解 （ Optimal） 无最优解
(Unbounded)
优 化 建 模牌号 产量 成本 价格甲 x1 q1 p1
乙 x2 q2 p2假设 A 产销平衡假设 B p随 x (两种牌号 )增加而减小，呈线性关系
12111211121211111,0,,,aaaabxaxabp
某厂生产两个牌号的同一种产品，如何确定产量使利润最大
21222221222212122,0,,,aaaabxaxabp
二次规划模型－例 1.2：产销计划问题优 化 建 模
22211121,)()(),(m a x
21
xqpxqpxxz
xx
目标 利润最大
= （ 100-x1-0.1 x2-2） x1
+（ 280-0.2x1-2x2-3） x2
=98 x1 + 277 x2 － x12 － 0.3 x1 x2 － 2x22
约束
x1 + x2 ≤100
x1 ≤ 2 x2
x1,x2 ≥ 0
二次规划模型 (QP)
若还要求产量为整数，则是整数二次规划模型 (IQP)
优 化 建 模非线性规划模型－例 1.3：选址问题某公司有 6个建筑工地，位置坐标为 (ai,bi) (单位：公里 ),
水泥日用量 di (单位：吨）i １ ２ ３ ４ ５ ６
a 1,2 5 8,7 5 0,5 5,7 5 3 7,2 5
b 1,2 5 0,7 5 4,7 5 5 6,5 7,7 5
d 3 5 4 7 6 11
1) 现有 2 料场，位于 A ( 5,1 ),B ( 2,7 ),
记 ( x j,y j ),j = 1,2,日储量 e j 各有 20 吨。
假设,料场和工地之间有直线道路目标,制定每天的供应计划，即从 A,B 两料场分别向各工地运送多少吨水泥，使总的吨公里数最小。
优 化 建 模用例中数据计算，
最优解为
i 1 2 3 4 5 6
1i
c （料场 A ） 3 5 0 7 0 1
2i
c （料场 B ） 0 0 4 0 6 10
总吨公里数为 136.2
2,1,
6,.,,,1,..
])()[(m i n
6
1
2
1
2
1
6
1
2/122
jec
idcts
byaxc
jij
i
iij
j
j i
ijijij
线性规划模型 (LP)
决策变量,ci j
(料场 j到 工地 i的运量） ~12维优 化 建 模选址问题,NLP
2）改建两个新料场，需要确定新料场位置 (xj,yj)和运量 cij,在其它条件不变下使总吨公里数最小。
2,1,
6,.,,,1,..
])()[(m i n
6
1
2
1
2
1
6
1
2/122
jec
idcts
byaxc
jij
i
iij
j
j i
ijijij
决策变量：
ci j,(xj,yj)~16维非线性规划模型
(NLP)
优 化 建 模整数规划 - 例 1.4,聘用方案某服务部门一周中每天需要不同数目的雇员：周一到周四每天至少 50 人，周五和周日每天至少 80 人，周六至少 90 人。
决策变量,周一至周日每天 (新 )聘用人数 x1,x2,? x7
目标函数,7天 (新 )聘用人数之和约束条件,周一至周日每天需要人数现规定应聘者需 连续工作 5 天，试确定聘用方案，即周一到周日每天聘用多少人，使在满足需要的条件下聘用总人数最少。
优 化 建 模
80
90
80
50
50
50
50..
m i n
76543
65432
54321
74321
76321
76521
76541
7654321
xxxxx
xxxxx
xxxxx
xxxxx
xxxxx
xxxxx
xxxxxts
xxxxxxxz
连续工作 5天
5017654 xxxxx
周一工作的应是 (上 )周四至周一聘用的设系统已进入稳态（不是开始的几周）聘用方案即为非负整数
， Zx i
整数规划模型 (IP)
优 化 建 模丁的蛙泳成绩退步到 1’15”2；戊的自由泳成绩进步到 57”5,组成接力队的方案是否应该调整？
如何选拔队员组成 4?100米混合泳接力队?
0-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
例 1.5,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
0-1规划,
整数规划的特例优 化 建 模整数规划问题一般形式
ljxg
mixhts
xf
j
i
Zx
n
,.,,,1,0)(
,.,,,1,0)(..
)(m i n
整数线性规划 (ILP) 目标和约束均为线性函数
整数非线性规划 (NLP) 目标或约束中存在非线性函数整数规划问题的分类
纯 (全 )整数规划 (PIP) 决策变量均为整数
混合整数规划 (MIP) 决策变量有整数，也有实数
0-1规划 决策变量只取 0或 1
优 化 建 模取消整数规划中决策变量为整数的限制（ 松弛 ），对应的连续优化问题称为原问题的 松弛问题整数规划问题对应的松弛问题松弛问题松弛整数规划问题 最优解最优解整数非整数 整数舍入下界（对 Min问题）
上界（对 Max问题）
非最优解优 化 建 模用连续优化方法求解松弛问题，如果松弛问题最优解
（分量）全为整数，则也是原整数规划问题的最优解对松弛问题的最优解（分量）舍入为整数，得到的往往不是原整数规划问题的最优解（甚至不是可行解）
IP可行解对应于整点 A(2,2)和 B(1,1),而最优解为 A点,
但 LP松弛的最优解为 C(3.5,2.5)
目标函数下降方向
x1
x2
C
A
B
O
优 化 建 模且为整数0,
4595
6..
85m ax
21
21
21
21
xx
xx
xxts
xxz
．,,．
．,．,,
．．,．,
．．,,,
x1
x2
0
Po
6
9
Zmax
5
6
去掉整数限制后，可行域为点（ 0,0),(6,0),(0,5),
P (2.25,3.75) 围成的 4边形
LP 最优解 P P 的舍入解 最靠近 P 的可行解 IP 最优解
（ 2,2 5,3,7 5 ） （ 2,4 ） （ 2,3 ） （ 0,5 ）
z = 4 1,2 5 不可行 z = 3 4 z = 4 0
从 LP最优解经过简单的,移动”不一定能得到 IP最优解例 1.6
优 化 建 模基本思想,隐式地枚举一切可行解（,分而治之,）
所谓分枝,就是逐次对解空间 （ 可行域 ） 进行划分；而所谓定界,是指对于每个分枝 （ 或称子域 ）,要计算原问题的最优解的下界 （ 对极小化问题 ）,这些下界用来在求解过程中判定是否需要对目前的分枝进一步划分,
也就是尽可能去掉一些明显的非最优点,避免完全枚举,
分枝定界法（ B&B,Branch and Bound）
对于 极小化 问题，在子域上解 LP，其最优值是 IP限定在该子域时的下界； IP任意可行点的函数值是 IP的上界。
这里仅介绍整数线性规划的分枝定界算法优 化 建 模无约束优化更多的优化问题线性规划非线性规划网络优化组合优化整数规划不确定规划多目标规划目标规划动态规划连续优化 离散优化 从其他角度分类
应用广泛,生产和运作管理、经济与金融、图论和网络优化、目标规划问题、对策论、排队论、存储论，
以及更加综合、更加复杂的决策问题等
实际问题规模往往较大，用软件求解比较方便优 化 建 模
3,LINDO/LINGO软件简介优 化 建 模常用优化软件
1,LINDO/LINGO软件
2,MATLAB优化工具箱 / Mathematic的优化功能
3,SAS(统计分析 )软件的优化功能
4,EXCEL软件的优化功能
5,其他（如 CPLEX等）
优 化 建 模
MATLAB优化工具箱能求解的优化模型优化工具箱 3.0 (MATLAB 7.0 R14)
连续优化 离散优化无约束优化非线性极小
fminunc
非光滑 (不可微 )优化
fminsearch
非线性方程 (组 )
fzero
fsolve
全局优化暂缺非线性最小二乘
lsqnonlin
lsqcurvefit
线性规划
linprog
纯 0-1规划 bintprog
一般 IP(暂缺 )
非线性规划
fmincon
fminimax
fgoalattain
fseminf
上下界约束
fminbnd
fmincon
lsqnonlin
lsqcurvefit
约束线性最小二乘
lsqnonneg
lsqlin
约束优化二次规划
quadprog
优 化 建 模
LINDO 公司软件产品简要介绍美国芝加哥 (Chicago)大学的 Linus Schrage教授于 1980
年前后开发,后来成立 LINDO系统公司（ LINDO
Systems Inc.）,网址,http://www.lindo.com
LINDO,Linear INteractive and Discrete Optimizer (V6.1)
LINDO API,LINDO Application Programming Interface (V4.1)
LINGO,Linear INteractive General Optimizer (V10.0)
What’s Best!,(SpreadSheet e.g,EXCEL) (V8.0)
演 示 (试用 )版、高级版、超级版、工业版、扩展版 …
（求解 问题规模 和 选件 不同）
优 化 建 模
LINDO/LINGO软件能求解的模型优化线性规划 非线性规划二次规划连续优化 整数规划
LINDO LINGO
优 化 建 模
LINGO软件的功能与特点
LINGO模型的优点
集成了线性 (非线性 ) / 连续 (整数 ) 优化功能
具有多点搜索 / 全局优化功能
提供了灵活的编程语言 (矩阵生成器 )，可方便地输入模型
提供与其他数据文件的接口
提供与其他编程语言的接口
LINDO API 可用于自主开发
运行速度较快优 化 建 模
LP QP NLP IP 全局优化 (选 )
ILP IQP INLP
LINGO软件的求解过程
LINGO预处理程序线性优化求解程序 非线性优化求解程序分枝定界管理程序
1,确定常数
2,识别类型
1,单纯形算法
2,内点算法 (选 )
1、顺序线性规划法 (SLP)
2、广义既约梯度法 (GRG) (选 )
3、多点搜索 (Multistart) (选 )
优 化 建 模建模时需要注意的几个基本问题
1,尽量使用实数优化，减少整数约束和整数变量
2,尽量使用光滑优化，减少非光滑约束的个数如：尽量少使用绝对值、符号函数、多个变量求最大 /最小值、四舍五入、取整函数等
3,尽量使用线性模型，减少非线性约束和非线性变量的个数 （如 x/y <5 改为 x<5y）
4,合理设定变量上下界，尽可能给出变量初始值
5,模型中使用的参数数量级要适当 (如小于 103)
优 化 建 模自己练习，或课上布置布置作业内容
Thank you very much!
