最优化问题的提出
在所有可行的方案中选出最合理的，达到规 定要求最优目标方案的实际问题称之为最优化问 题。
其它的最优化问题： 田忌赛马
本课程名为：运筹与优化 更合适
优化问题的数学描述，包括：
（１）优化的目标 追求的目的，路程最短，花费最少… （２）寻求的决策 众多可选的方案中寻找一个使目标达到最优的决策 （３）限制条件 方案需满足特定的规则约束，如背包容量有限
最优化方法
2013.2
:
1.1 问题提出
1 何为优化问题? 2 优化问题如何描述? (即如何进行数学建模?) 3 如何求解?
最优化问题
• 现实世界中普遍存在着优化问题
如：（1）电影院的座位设计问题 （2）组合投资问题 （3）背包问题/贪婪问题 （4）旅行售货问题
优化问 题
（1）电影院的座位设计问题
根据处理思想方法的不同，分为数学规划、组合优 化、图论与网络流、动态规划…
数学规划
一般线性规划
线性规划
运输问题
(Linear
整数规划（Integer Programming）
Programming)
无约束非线性规划
非线性规划 (Non-Linear Programming)
约束非线性规划
例1 加工奶制品的生产计划
优化问 题
（2）组合投资问题
（3）背包问题(贪婪问题)
一个小偷打劫一个保险箱，发现柜子里有3类不 同大小与价值的物品，但小偷只有一个容积为20的 背包来装东西，背包问题就是要找出一个小偷选择 所偷物品的组合，以使偷走的物品总价值最大。
（4）旅行售货问题
有一个推销员，要到各个城市去推销产品，他希 望能找到一个最短的旅遊途径，访问每一个城市，而 且每个城市只拜訪一次，然后回到最初出发的城市。
x1+x2≤50
劳动时间
生产A1、A2的总加工时间不超过每天正式工人
总的劳动时间480小时，即
12x1+8x2≤480
设备能力
A1的产量不得超过设备甲每天的加工能力100小
时，即
3x1≤100
非负约束
x1、x2均不能为负值，即x1≥0，x2≥0
综上所述可得如下优化模型：
Max z 72 x1 64 x2
优化问题的数学描述，包括： 优化的目标——目标函数
寻求的决策——决策变量 限制条件 ——约束不等式
优化问题的一般表述（优化问题的数学模型）：
X表示决策变量，X=(x1,x2,…xn)’
Max f(X)
( 或 Min )目标函数
S.T g(X)>=0
约束条件
X∈D
1.2 优化问题分类
根据决策变量取值情况不同，分为连续型和离散型。
问题：一奶制品加工厂用牛奶生产A1、A2两种奶制 品，1桶牛奶可以在设备甲上用12小时加工成3公斤 A1，或者在设备乙上用8小时加工成4公斤A2。根据 市场需求，生产的A1、A2能全部售出，且每公斤A1 获利24元，每公斤A2获利16元。现在加工厂每天能 得到50桶牛奶的供应，每天正式工人总的劳动时间 为480小时，并且设备甲每天至多能加工100公斤A1， 设备乙的加工能力没有限制。
若选择队员i参加泳姿j 的比赛，记xij=1, 否则记xij=0
目标 函数
约束 每人最多入选泳姿之一 每种泳姿有且只有1人 条件
非线性规划：使用临时料场的情形
使用两个临时料场A(5,1)，B(2,7).求从料场j向工地i 的运送量为Xij，在各工地用量必须满足和各料场运送 量不超过日储量的条件下， 改建两个新料场，要同时 确定料场的位置(xj,yj)和运送量Xij，在同样条件下 使总吨千米数最小。
组合优化（Combinatorial Optimization）
组合最优化问题是通过对数学方法的研究去寻 找离散事件的最优编排、分组、次序或筛选等。
例：旅行商问题（TSP,traveling saleman problem）
一个商人欲到 n 个城市推销商品，每两个城市 i 和 j 之间的距离为 d ij ,如何选择一条道路使得商 人每个城市走一遍后回到起点且所走路径最短。
x1 x2 50
st
12
x1 8x2 480 3x1 100
x1, x2 0
线性 规划 模型 (LP)
目标函数和约束条件都是线性的，这种优化
模型称为是线性规划（linear programming,LP） 模型。
整数线性规划模型的实例
例1 某厂拟用集装箱托运甲乙两种货物，每箱的体 积、重量、可获利润以及托运所受限制如表5－1：
模型建立：
决策变量
设每天用x1桶牛奶生产A1 ，用x2桶牛奶生产A2
目标函数
设每天获利为z元。 x1桶牛奶可生产3x1公斤A1，获利24*3x1; x2桶牛奶可生产4x2公斤A2，获利16*4x2; 故z=72x1+64x2
约束条件
原料供应
生产A1、A2的原料（牛奶）总量不超过每天的
供应50桶，即
货物
甲 乙 托运限制
体积
重量
利润
每箱（米3） 每箱（百斤）每箱（百元）
5
2
20
4
5
10
24
13
问两种货物各托运多少箱，可使获得的利润为最大？
解：设托运甲、乙两种货物x1，x2箱，用数学式 可表示为：
例：游泳队员的选拔问题
蝶泳 仰泳 蛙泳 自由泳
5名候选人的百米成绩
甲
乙
丙
丁
1’06”8
57”2
1’18”
1’10”
1’15”6
1’06”
1’07”8
1’14”2
1’27”
1’06”4
1’24”6
1’09”6
58”6
53”
59”4
57ቤተ መጻሕፍቲ ባይዱ2
戊 1’07”4 1’11” 1’23”8 1’02”4
如何选拔队员组成4100米混合泳接力队?
如果丁的蛙泳成绩退步到1’15”2；戊的自由泳成 绩进步到57”5, 组成接力队的方案是否应该调整？
试为该厂制定一个生产计划，使每天获利最大.
问题分析：
1桶 牛奶 或
12小时 3公斤A1 8小时 4公斤A2
获利24元/公斤 获利16元/公斤
每天： 50桶牛奶 时间480小时 至多加工100公斤 制订生产计划，使每天获A1利最大
生产计划是什么? 每天的牛奶：安排多少生产A1，多少生产A2 ?
有决策变量（生产计划），有目标，肯定就是 一个优化问题！考虑建立优化模型~
穷举法：组成接力队的方案共有5!=120种。
0-1规划模型
cij
i=1
j=1
66.8
j=2
75.6
j=3
87
j=4
58.6
cij(秒)~队员i 第j 种泳姿的百米成绩
i=2
i=3
i=4
i=5
57.2
78
70
67.4
66
67.8
74.2
71
66.4
84.6
69.6
83.8
53
59.4
57.2
62.4