3
2
限额
34 36 40
在一定的条件下，问生产数量xi =？使利润达到最大？
规划模型
m ax Z 4 x1 3 x2 2 x3
利润
2 x1 3 x2 x3 34
s
.t
.
3 3
x1 x1
2 2
x2 x2
1.5 x3 5x3
36 40
材料
工时 人力
x1 , x 2 , x 3 0
优化(Optimization), 规划(Programming)
4
优化问题的一般形式
优化问题三要素：决策变量；目标函数；约束条件
min f ( x)
目标函数
s.t. hi ( x) 0, i 1,..., m 约
g j ( x) 0, j 1,..., l
束 条
决策变量
x D n
件
• 可行解（满足约束）与可行域（可行解的集合） • 最优解（取到最小／大值的可行解）
5
无约束优化:最优解的分类和条件
给定一个函数 f(x),寻找 x* 使得 f(x*)最小，即
Minf (x) x
其中
x(x1,x2, ,xn)T n
局部最优解
全局最优解
ox
必要条件 充分条件
f(x*)(fx1, ,fxn)T02 f
2 f
f(x*)0, 2f(x*)0
7
最优化问题简介
1、生产计划问题； 2、运输问题；
特点：从若干可能的计划（方案）中寻求某种意
义下的最优方案，数学上将这种问题称为最优化问 题（optimization). 静态问题(没有考虑时间t的变化)
8
生产计划问题
单耗
数据表
甲乙
丙
材料 工时 工人
x1
x2
x3
2
3
1
3
2 1.5
3
2
5
利润(元/件) 4
优化模型
1
主要内容
最优化问题简介 引例 常用优化软件
范例1: 加工奶制品的生产计划 范例2:自来水输送与货机装运 范例3:汽车厂生产计划
2
优化模型及软件的重要意义
(最)优化:在一定条件下,寻求使目标最大(小)的决策
最优化是工程技术、经济管理、科学研究、 社会生活中经常遇到的问题, 如: 结构设计 资源分配 生产计划 运输方案 解决优化问题的手段 • 经验积累，主观判断 • 作试验，比优劣 • 建立数学模型(优化模型)，求最优策略(决策)
9
运输问题
网络图
S2
1200
S3
690 720
S4
690
160
170
520
88
320 70
1100
195 306
1150
5
450
3 104
600
80 2 750
A3
301
A2
10 194
606 A5 A4
A1
202
S1
20
12
31
10
201
462 S5 10
70
42
10 220
480
A10 300
s.t. hi ( x) 0, i 1,..., m g j ( x) 0, j 1,..., l
决策变量
x D n
目标函数
约 束 条 件
• 可行解（满足约束）与可行域（可行解的集合） • 最优解（取到最小／大值的可行解）
15
数学规划中的几个概念
1、可行解（可行点） 2、可行域 3、最优解
图解: 起作用约束：L2，L3 最优解（4，1） 最优值 zmax = 13
例：Max z = 3x1+x2 s.t. -x1+x2≤2 L1
x1-2x2≤2 L2 3x1+2x2≤14 L3 x1，x2≥0
线性规划(LP)
整数规划(IP)
运 输 问 题
配 料 问 题
投 资 计 划
综 合 生 产
中 转 调 用
生 产 率 比 较
投生 指 下 资产 派 料 选计 问 问 择划 题 题
50个决策变量以上的优化问题称为大规模的.
返回
14
优化问题的一般形式
优化问题三要素：决策变量；目标函数；约束条件
min f ( x)
CUMCM赛题：约一半以上与优化有关，需用软件求解
3
最优化问题简介 (最)优化理论是运筹学的基本内容
OR/ 运筹学(OR: Operations/Operational Research) MS/ 管理科学(MS: Management Science) DS 决策科学 (DS: Decision Science)
工地的需求量为bj，单位产品的运费cij已知，那么如
何安排运输方案可以使总运费最低？
状 态
数学模型：
变
量 cij —单位运费；
xij —运输量；
MN
min
cij xij
i1 j1
N
s.t.
xij ai ,
j 1
i 1, 2, ..., M
ai —第i 地产量； bj —第j 地需要量；
M
xij b j
A11
A9
680
A8
A6 205 A7
目标：运费达到最小
290 30 S7
160
70 30
20 20
S6
110
62 420
A15
500
A14
A13
210
A12
S1~S7 钢管厂 铁路
火车站 公路 管道
450 里程（km）
10
运输问题
某种原材料有M个产地，现在需要将原材料从
产地运往N个工地，假定M个产地的产量为ai和N个
xixj nn
Hessian阵
最优解在可行域边界上取得时不能用无约束优化方法求解
6
约束优化的
min f ( x)
简单分类
s.t. hi ( x) 0, i 1,..., m
数学规划
g j ( x) 0, j 1,..., l x D n
连 • 线性规划(LP) 目标和约束均为线性函数
续 优
• 非线性规划(NLP) 目标或约束中存在非线性函数
化 ✓ 二次规划(QP) 目标为二次函数、约束为线性
• 整数规划(IP) 决策变量(全部或部分)为整数
离 散
✓ 整数线性规划(ILP)，整数非线性规划(INLP)
优 ✓ 纯整数规划(PIP), 混合整数规划(MIP)
化 ✓ 一般整数规划，0-1（整数）规划
返回
12
优化，规划的类型
• 无约束优化
• 线性规划(LP) 目标和约束均为线性函数
• 非线性规划(NLP) 目标和约束均为非线性函数
• 整数规划(IP) 决策变量为整数
• 组合优化
• 不确定规划
• 多目标规划
目标函数至少两个以上
• 网络优化
• 动态规划
研究随时间变化的决策问题
返回
13
典型的工程应用问题
i 1
j 1, 2, ..., N
返回
11
建立最优化的数学模型应具备三个基本要素
1、决策变量（decision variables); 2、约束条件（constraints); 3、目标函数（objective function)
最优化问题分类： ① 线性、非线性 ② 静态、动态 ③ 整数、非整数 ④ 随机、非随机等