最优化方法_理工大学内部课件汇总

格式：ppt
大小：3.82 MB
文档页数：38

下载文档原格式

最优化方法课程PPT

x
∞
表示
= max { xi }
x 1 = ∑ xi
x 2 = (∑ x
1 2 2 i
)
7
二、数学预备知识
范数的内积范数不等式
x y = ∑ xi yi
T i =1 n
x+ y ≤ x + y
三角不等式柯西不等式
x0 = ( x1 ( 0 ) , x2 ( 0 ) ,..., xn ( 0 ) )
() () ()
4
一、最优化方法的基本概念
(2) 非线性规划非线性规划(Nonlinear Programming, NLP)
f(x)，Ci(x) ( i ∈ E U I )，其中之一均为线性函数，
(3) 无约束最优化问题 Unconstraint Optimization Problem) 无约束最优化问题(
λ)x(2)
x(2)
x
17
二、数学预备知识
(3) 凸函数的判定准则一阶判定条件：在凸集S上具有一阶连续偏导数一阶判定条件： f(x)在凸集上具有一阶连续偏导数，则在凸集上具有一阶连续偏导数， f(x)为S上凸函数的充要条件是为上凸函数的充要条件是
f x
f(x)
( ) ≥ f ( x ) + ∇f ( x ) ( x ( ) − x ( ) )
x
2 21 1
没有约束条件C 没有约束条件 i(x)
5
一、最优化方法的基本概念
4 数学规划模型的分类主要是针对决策变量x 来进行分类：主要是针对决策变量 1, x2,…xn来进行分类：
连续型离散型
线性规划 LP (有、无约束有无约束)
非线性规划NLP 非线性规划 (有、无约束有无约束)

《最优化方法》课件

7பைடு நூலகம்
5
2. 学习本课程所需的数学知识
向量、向量的模（范数）、向量的运算、线性相关与无关、基. 矩阵的运算及性质、矩阵的秩、特征值、正定性。向量函数、连续性、可微性、梯度、海森矩阵、向量函数（多元函数）的Taylor定理
6
3. 学习要求
掌握主要的优化模型的数学计算方法. 了解优化方法的数学原理. 了解现代优化方法. 熟练掌握应用数学软件计算优化问题.
3
二次大战以后，在军事运筹小组中工作过的一部分科学家开始转入民用部门，他们把对军事系统最优化的研究成果拓展到各种民用系统的研究上。
1947年美国数学家G.B.Dantzig在研究美国空军资源配置时,提出了求解线性规划的有效方法—单纯形法。二十世纪五十年代初，应用计算机求解线性规划获得成功。
2
运筹学这一名词最早出现于1938年。当时英，美等国盟军在与德国的战争中遇到了许多错综复杂的战略和战术问题难以解决，比如
(１)防空雷达的布置问题：
(２)护航舰队的编队问题：
为了应付上述各种复杂问题，英美等国逐批召集不同专业背景的科学家，在三军组织了各种研究小组，研究的问题都是军事性质的，在英国称为“Operational Research”，其他英语国家称为“Operations Research”，意思是军事行动研究。这些研究小组运用系统优化的思想，应用数学技术分析军事问题，取得了非常理想的效果。
至五十年代末，一些工业先进国家的大型企业已经较普遍地使用运筹学方法解决在生产经营管理中遇到的实际问题，并取得了良好的效果，至六十年代中期，运筹学开始应用于一些服务性行业和公用事业。
4
我国运筹学的研究始于五十年代中期，当时由钱学森教授将运筹学从西方国家引入我国，以华罗庚教授为首的一大批科学家在有关企事业单位积极推广和普及运筹学方法，在建筑，纺织，交通运输，水利建设和邮电等行业都有不少应用。关于邮递员投递的最佳路线问题就是由我国年轻的数学家管梅谷于1962年首先提出的，在国际上统称为中国邮递员问题。我国运筹学的理论和应用研究在较短时间内赶上了世界水平。

最优化方法PPT

共117页第8页
同时太阳系这个"整体"又是它所属的"更大整体"--银河系的一个组成部分。世界上的具体系统是纷繁复杂的，必须按照一定的标准，将千差万别的系统分门别类，以便分析、研究和管理，如：教育系统、医疗卫生系统、宇航系统、通讯系统等等。如果系统与外界或它所处的外部环境有物质、能量和信息的交流，那么这个系统就是一个开放系统，否则就是一个封闭系统。开放系统具有很强的生命力，它可能促进经济实力的迅速增长，使落后地区尽早走上现代化。如改革开放以来已大大增强了我们的综合国力。而我国的许多边远山区农村，由于交通不便，相对封闭，还处于比较落后的状态。
会科学和思维科学的相互渗透与交融汇流，产生了具有高度抽象性和广泛综合性的系统论、控制论和信息论。
系统论是研究系统的模式、性能、行为和规律的一门科学。它为人们认识各种系统的组成、结构、性能、行为和发展规律提供了一般方法论的指导。系统论的创始人是美籍奥地利理论生物学家和哲学家路德维格·贝塔朗菲。系统是由若干相互联系的基本要素构成的，它是具有确定的特性和功能的有机整体。如太阳系是由太阳及其围绕它运转的行星（金星、地球、火星、木星等等）和卫星构成的。
从数学上比较一般的观点来看，所谓最优化问题可以概括为这样一种数学模型：给定一个“函数”，F(X)，以及“自变量”X应满足的一定条件，求X为怎样的值时， F(X)取得其最大值或最小值。这里在函数和自变量两个词上之所以打上引号，是想强调它们的含意比中学数学和大学微积分中函数的定义要广泛得多。通常，称F(X) 为“目标函数”，X应满足的条件为“约束条件”。约束条件一般用一个集合D表示为：X∈D。求目标函数 F(X)在约束条件X∈D下的最小值或最大值问题，就是一般最优问题的数学模型，它还可以利用数学符号更简洁地表示成：Min F(X)或Max F(X)。

最优化方法及其应用[优质ppt]

一最优化问题总论
解设四间车房长为 x 1 ，宽为 x 2．由题意可知面积为 f(x1, x2)x1x2 且变量 x 1 ，x 2 ，应满足
2x15x240 x10，x2 0
即求 mfa(x1x ,x2)x1x2，
2x1x10， 5xx22
40， 0．
一最优化问题总论
一最优化问题总论
概括地说，凡是追求最优目标的数学问题都属于最优化问题作为最优化问题，一般要有三个要素：第一是目标；第二是方案；第三是限制条件．而且目标应是方案的“函数”．如果方案与时间无关，则该问题属于
静态最优化问题；否则称为动态最优化问题
本书只讨论静态最优化问题．
一最优化问பைடு நூலகம்总论
最简单的最优化问题实际上在高等数学中已遇到，这就是所谓函数极值，我们习惯上又称之为经典极值问题．
例1.1 对边长为a的正方形铁板，在四
个角处剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？
一最优化问题总论
解设剪去的正方形边长为x，由题意易知，与
此相应的水槽容积为
f(x)(a2x)2x
一最优化问题总论二一维搜索法三常用无约束最优化方法四常用约束最优化方法五程序设计及其他优化方法
一最优化问题总论
无论做任何一件事，人们总希望以最少的代价取得最大的效益，也就是力求最好，这就是优化问题．最优化就是在一切可能的方案中选择一个最好的方案以达到最优目标的学科．例如，从甲地到乙地有公路、水路、铁路、航空四种走法，如果我们追求的目标是省钱，那么只要比较一下这四种走法的票价，从中选择最便宜的那一种走法就达到目标．这是最简单的最优化问题，实际优化问题一般都比较复杂．

最优化方法课件01.3

值,所以一元凸函数表示连接函数图形上任意两点的线段总是位于曲线弧的上方.
13
对于一元凸函数f(x),可以发现,位于函数曲线上方的图形是凸集.事实上这一结论对于多元函数也是成立的,而且是充要条件,即有下面的定理.
定理:设f(x)是定义在凸集D Rn上的函数,则 f(x)是凸函数的充要条件是其上图epi(f)为凸集,其中epi(f)={(x,y)|x∈ D,y ∈ R,y≥f(x)}. 证明:作业
14
凸函数的性质
(i)设f(x)是凸集D Rn上的凸函数,实数k≥0,则 kf(x)也是D上的凸函数.
(ii)设f1(x), f2(x)是凸集D Rn上的凸函数,实数
m 0,则f1(x)+m f2(x)也是D上的凸函数. (iii)设f(x)是凸集D Rn上的凸函数,b为实数,
则水平集S(f,b)={x|x∈D,f(x)≤b }是凸集.
不等式取等号,必须||y||=||z||=a,且（ y,z ） =||y||||z||, 容易证明y=z=x,根据定义可知,x为极点.
9
凸函数
定义1.7.4 设函数f (x)定义在凸集D Rn上,若
对任意的x,y ∈ D,及任意的a ∈ [0,1]都有 f (a x+(1-a)y) ≤ a f(x)+(1-a) f (y)
28
例:证明集合 S {X | AX b} 是凸集。其中，A 为 mn矩阵，b为m维向量。
证明：任取 X 1, X 2 S
A，X 1 则 b, AX 2 b
A[a X 1 + (1-a )X 2] a AX 1 + (1-a )AX 2 ab + (1-a )b b
所以，a X 1 + (1-a ) X 2 S

最优化 PPT课件

• 另外也可用学术味更浓的名称：“运筹学”。由于最优化问题背景十分广泛，涉及的知识不尽相同，学科分枝很多，因此这个学科名下到底包含哪些分枝，其说法也不一致。
• 比较公认的是：“规划论”（包括线性和
非线性规划、整数规划、动态规划、多目
标规划和随机规划等），“组合最优化”，
“对策论”及“最优控制”等等。
j
1, 2,L
,n
(5)
14
nn
min
cij xij
i 1 j 1
n
xij 1, i 1, 2,L
,n
s.t.
j 1 n
(5)
xij 1, j 1, 2,L , n
i1
xij
0
或 1 ,i,
j
1, 2,L
,n
(5)的可行解既可以用一个矩阵(称为解矩阵)表示，其每行每列均有且只
mn
min
cij xij
i 1 j 1
n
xij ai ,
i 1, , m
j 1
s.t.
m xij bj ,
j 1,2, , n
i 1
xij
0
11
对产销平衡的运输问题，由于有以下关系式存在：
n
bj
j1
m
i1
n xij
j1
n m
j1 i1
xij
费的总时间最少？
引入变量 xij ，若分配 i 干 j 工作，则取 xij 1，否则取 xij 0 。上
述指派问题的数学模型为
nn
min
cij xij
i 1 j 1
n
xij 1,i 1, 2,L
,n
j1

最优化方法课件01.1

2
二、包含的内容
按照优化思想分为经典方法与现代方法。经典方法主要包括：线性规划、非线性规划、整数规划、动态规划等现代方法主要包括：随机规划、模糊规划、模拟退火算法、遗传算法、禁忌搜索和人工神经网络等。我们学习的内容主要是经典的最优化方法。内容包括线性规划及其对偶规划，无约束最优化方法、约束最优化方法等主要内容。
i 1 j 1
9
m k
数学模型:
注:平衡条件出现在约束条件中.
作为已知条件并不
10
例1.1.2 生产计划问题
设某工厂有m种资源B1,B2, …,Bm,数量分别为: b1,b2, …, bm,用这些资源产n种产品A1,A2, …, An.每生产一个单位的Aj产品需要消耗资源Bi 的量为aij,根据合同规定,产品Aj的量不少于dj. 再设Aj的单价为cj. 问如何安排生产计划,才能既完成合同,又使该厂总收入最多?
f x 2x1 2x2 , 2x2 2x1 2x3 3, 2x3 2x2
T
35
例：求目标函数的梯度和Hesse矩阵。
f ( x) x x x 2 x1 x2 2 x2 x3 3x2
2 1 2 2 2 3
2 2 2 f f f 又因为： 2, 2, 0 2 x1 x1x2 x1x3
因此,数据拟合问题得数学模型为
其中xi,yi(i=1,2,…,m)及jj(x)(j=0,1,…,n)为已知.
18
§1.2最优化问题的基本概念
19
最优化问题的一般形式为:
P:
(1.1)(目标函数) (1.2)(等式约束) (1.3)(不等式约束)
其中x是n维向量. 在实际应用中,可以将求最大值的目标函数取相反数后统一成公式中求最小值的形式. 我们总是讨论

最优化方法复习大纲PPT课件

2 0 2 0 0 12
问：（1）确定当前单纯型表中的基变量，基本可行解，
目标函数值。
（2）判断其是否为最优单纯型表，是则给出理由；不是，则继续求解该问题的最优解。
10
解：
（1）基变量为 x2 , x4 , x5 ，基本可行解为 x1 (0,4,0,2,6)T 。目标函数值为12。
（2）因为变量 x1 的检验数 1 2 0 ，所以不是最优单纯
题的最优解计算. 6. 模式搜索法：计算。
7. 最优性条件：积极约束判断，K-T条件， K-T点判别。
8. 惩罚函数法：外点法惩罚函数的构造，内点法障碍函数的构造，外点法、内点法计算。
2
9. 线性规划：建立线性规划模型，化标准型，基本可行解的计算，单纯型表上的单纯型算法.
3
例1. 试用梯度法解下述问题 min f ( x) x12 4 x22
min z 2 x1 x2 3 x3
x1 x2 2 x3 4
s.t .
2 x1 x3 2 2x2 x3 5
x1 , x2 0, x3无约束
解：令 x3 x4 x5 .
max z 2 x1 x2 3 x4 3 x5
x1 x2 2 x4 2 x5 x6 4
已知初始点 x1 (1,1)T ,求迭代点x2。
解： f ( x) [ 2x1 ,8x2 ]T d1 f ( x1) [ 2, 8]T
x x1 d1 [1 2,1 8]T
记 ( ) f ( x1 d1) (1 2 )2 4(1 8 )2
令 '( ) 4(1 2 ) 64(1 8 ) 0
最优化方法复习提纲
一、概念
最优化问题，凸集，凸函数，局部极小点，全局极小点，下降方向，最优步长，共轭方向，可行方向，积极约束，线性规划问题，基本解。

华理最优化方法课件-3-2

注:根据线性规划问题本身的形式,可以引进一些人工变量.
构造单纯性表
CB 0 M M XB x4 x6 x7 b 11 3 1 -3 x1 1 -4 -2 1 x2 -2 1 0 1 x3 1 2 1 0 x4 1 0 0 0 x5 0 -1 0 M x6 0 1 0 M x7 0 0 1
qi
11 3/2 1
min f ( X )=-3x1 x2 x3 min x6 x7 11 x1 2 x2 x3 x4 x1 2 x2 x3 11 4 x x 2 x x x 4 x x 2 x 3 3 1 2 3 5 6 1 2 3 2 x1 +x3 x7 1 2 x + x 1 1 3 x , x , x , x , x , x , x 0 x , x , x 0 1 2 3 4 5 6 7 1 2 3
在实际问题中可以取M为适当大的一个数,比如比问题中的系数大一个数量级.
两阶段法的数学模型
对于线性规划问题
n n aij x j bi(bi 0),i 1,2, min f ( X ) c j x j s. t. j 1 j 1 x 0, j 1,2, , n j
f ( X ) 2
*
§3.5 对偶问题的基本原理
例 3.8 生产问题
某工厂计划在下一生产周期生产3种产品A1,A2,A3 这些产品都要在甲、乙、丙、丁4种设备上加工，根据设备性能和以往的生产情况知道单位产品的加工工时，各种设备的最大加工工时限制，以及每种产品的单位利润（单位：千元），如表3.1所示，问如何安排生产计划，才能使工厂得到最大利润？
大M法的理论依据

最优化及最优化方法讲稿

最优化及最优化方法讲稿ppt xx年xx月xx日CATALOGUE目录•最优化问题概述•线性规划问题及其求解方法•非线性规划问题及其求解方法•动态规划问题及其求解方法•最优化算法的收敛性分析•最优化算法的鲁棒性分析•最优化算法的应用举例 - 解决生产调度问题01最优化问题概述最优化问题是一个寻找某个或多个函数的特定输入，以使该函数的输出达到最小或最大的问题。

定义根据不同的分类标准，可以将最优化问题分为线性规划、非线性规划、多目标规划、约束规划等。

分类最优化问题的定义与分类描述所追求的最小或最大值的函数。

目标函数约束条件数学模型限制搜索范围的约束条件。

目标函数和约束条件的数学表达。

03最优化问题的数学模型0201最优化问题的求解方法牛顿法利用目标函数的Hessian矩阵（二阶导数矩阵）进行搜索。

梯度下降法迭代搜索，逐步逼近最优解。

混合整数规划将整数变量引入优化模型中，求解整数规划问题。

模拟退火算法以概率接受劣质解，避免陷入局部最优解。

进化算法模拟生物进化过程的启发式搜索算法。

02线性规划问题及其求解方法线性规划问题定义：在一组线性约束条件下，求解一组线性函数的最大值或最小值的问题。

数学模型：将实际问题转化为线性规划模型，包括决策变量、目标函数和约束条件。

线性规划问题的求解方法 - 单纯形法基本概念：介绍单纯形法的相关概念，如基、可行解、最优解等。

单纯形法步骤：阐述单纯形法的基本步骤和算法流程，包括初始基可行解的求解、最优解的迭代搜索和最终最优解的确定。

单纯形法改进：介绍一些改进的单纯形法，如简化单纯形法、对偶单纯形法等。

线性规划问题的定义与数学模型通过一个具体的生产计划问题，说明如何建立线性规划模型并进行求解。

生产计划问题通过一个配货问题，说明如何运用线性规划模型解决实际问题。

配货问题通过一个投资组合优化问题，说明如何运用线性规划进行风险和收益的平衡。

投资组合优化问题线性规划问题的应用举例03非线性规划问题及其求解方法非线性规划问题定义：非线性规划问题是一类求最优解的问题，其中目标函数和约束条件均为非线性函数。

最优化方法全部ppt课件

解法：Lagrange乘子法
1.2 实例
数据拟合问题原料切割问题运输问题营养配餐问题分配问题
1.3 基本概念
1. 最优化问题的向量表示法
设 xvx1,x2,L,xnT 则
m i n fx 1 ,x 2 ,L ,x n m i n fx v （1）
以向量为变量的实值函数定义向量间的序关系(定义1.1)：
②取 c0,1,4,9,L并画出相应的曲线（称之为等值线）.
③确定极值点位置，并用以往所学方法求之。
易知本题的极小值点 xv* 2,1T。
再复杂点的情形见P13上的例1.7。虽然三维及以上的问题不便于在平面上画图，图解法失效，但仍有相应的等值面的概念，且等值面具有以下性质：
①有不同函数值的等值面互不相交（因目标函数是单值函数的缘故）；
其中
g1 xv0
x1
g2 xv0
x1
L
gv
xv0
g1 xv0
x2
g2 xv0
x2
L
M
g1 xv0
xn
M
g2 xv0
xn
称为向量值函数 gv xv 在点
L
xv 0
g
m xv0
x1
g
m
xv0
x2
g
M
m xv0
xn
处的导数，
而gv xv0 T 称为向量值函数 gv xv 在点 xv 0 处的Jacobi矩阵。
称为最优化方法。最优化方法是在第二次世界大战前后，
在军事领域中对导弹、雷达控制的研究中逐渐发展起来的。
最优化方法解决问题一般步骤：（1）提出需要进行最优化的问题，开始收集有关资料和数据；（2）建立求解最优化问题的有关数学模型，确定变量，列出目标函数和有关约束条件；（3）分析模型，选择合适的最优化方法；（4）求解方程。一般通过编制程序在电子计算机上求得最优解；（5）最优解的验证和实施。随着系统科学的发展和各个领域的需求，最优化方法不断地应用于经济、自然、军事和社会研究的各个领域。

最优化计算方法PPT课件

0.91
0.91
3 (x 5)2 ( y 3)2 18 (x 1)2 ( y 1)2
0.91
0.91
8 (x 3)2 ( y 1)2 6 (x 5)2 ( y 1)2 ] / 84
▪ 问题为在区域0=<x=<6, 0=<y=<6上求z=f(x,y)的最小值。
•15
绘制目标函数图形
xnew=a+(b-a)*rand(1); ynew=c+(d-c)*rand(1); znew=subs(z,[x,y],[xnew,ynew]); if znew<zmin
xmin=xnew; ymin=ynew; zmin=znew; fprintf('%4.0f %1.6f %1.6f %1.6f\n', n, xmin, ymin, zmin); end end
•16
16/5+...+17/140 (x2-10 x+26+y2-2 y)91/200
20
15
10
5
5 0
5 0
-5
-5
y
x
•17
绘制等值线图
ezcontourf(z,[0 6 0 6])
colorbar, grid on
16/5+...+17/140 (x2-10 x+26+y2-2 y)91/200 6
据的统计分析给出：对离救火站r英里打来
的求救电话，需要的响应时间估计
为
。下图给出了从消3.防21管.7r0员.91 处得到
的从城区不同区域打来的求救电话频率的
估计数据。求新的消防站的最佳位置。
•13

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

最优化问题的提出
在所有可行的方案中选出最合理的，达到规定要求最优目标方案的实际问题称之为最优化问题。
其它的最优化问题：田忌赛马
本课程名为：运筹与优化更合适
优化问题的数学描述，包括：
（１）优化的目标追求的目的，路程最短，花费最少… （２）寻求的决策众多可选的方案中寻找一个使目标达到最优的决策（３）限制条件方案需满足特定的规则约束，如背包容量有限
最优化方法
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