文档介绍：最优化方法
:
1 何为优化问题?
2 优化问题如何描述? (即如何进行数学建模?)
3 如何求解?
问题提出
现实世界中普遍存在着优化问题
最优化问题
如：（1）电影院的座位设计问题
（2）组合两种货物，每箱的体积、重量、可获利润以及托运所受限制如表5－1：
问两种货物各托运多少箱，可使获得的利润为最大？
解：设托运甲、乙两种货物x1，x2箱，用数学式
可表示为：
如果丁的蛙泳成绩退步到1’15”2；戊的自由泳成绩进步到57”5, 组成接力队的方案是否应该调整？
如何选拔队员组成4100米混合泳接力队?
例：游泳队员的选拔问题
甲
乙
丙
丁
戊
蝶泳
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

78
70

j=2

66

71
j=3
87

j=4

53

每种泳姿有且只有1人
非线性规划：使用临时料场的情形
使用两个临时料场A(5,1)，B(2,7).求从料场j向工地i的运送量为Xij，在各工地用量必须满足和各料场运送量不超过日储量的条件下，改建两个新料场，要同时确定料场的位置(xj,yj)和运送量Xij，在同样条件下使总吨千米数最小。
组合优化（Combinatorial Optimization）
组合最优化问题是通过对数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等。
例：旅行商问题（TSP,traveling saleman problem）
一个商人欲到 n 个城市推销商品，每两个城市 i 和 j 之间的距离为 d ij ,如何选择一条道路使得商人每个城市走一遍后回到起点且所走路径最短。
图论与网络流
最短路问题
最小生成树问题
最大流问题
匹配问题
最小费用流问题
（4）旅行售货问题
有一个推销员，要到各个城市去推销产品，他希望能找到一个最短的旅遊途径，访问每一个城市，而且每个城市只拜訪一次，然后回到最初出发的城市。
其它优化
目标规划(多目标规划)
动态规划
对策论、决策论
模糊优化
随机规划
随机规划：报童的诀窍
问题
报童售报： a (零售价) > b(购进价) > c(退回价)
售出一份赚 a-b；退回一份赔 b-c
每天购进多少份可使收入最大？
每天需求量是随机的
优化问题的目标函数应是长期的日平均收入
每天收入是随机的
建模
设每天购进 n 份，日平均收入为 G(n)
调查需求量的随机规律——每天需求量为 r 的概率 f(r), r=0,1,2…
准备
求 n 使 G(n) 最大
已知售出一份赚 a-b；退回一份赔 b-c
一般地，对于最优化问题（）的求解，是指
在可行域内找一点，使得目标函数在该点取得极小
值，即
这样的称为问题（）的最优点，也称极
小点，而相应的目标函数值　　称为最优值；
合起来，称为最优解，但习惯上，把　
本身称为最优解．
优化问题的求解
满足所有约束的点（解）称为可行点．可行点的集合称为可行域．
优化问题的求解方法（最优化方法）：
（１）图解法
（２）函数极值法：　目标函数求导数
（3 ）数值解法，
　　　初始值x0，迭代的方法，搜索最优解
以下为例：
线性规划模型(LP)
１、图解法
x1
x2
0
A
B
C
D