最优化方法教案(1)

第一章 最优化问题与数学预备知识

最优化分支：线性规划，整数规划，几何规划，非线性规划，动态规划。又称规划论。

应用最优化方法解决问题时一般有以下几个特点： 1. 实用性强

2. 采用定量分析的科学手段 3. 计算量大，必须借助于计算机 4. 理论涉及面广

应用领域：工业，农业，交通运输，能源开发，经济计划，企业 管理，军事作战 。

§1.1 最优化问题实例

最优化问题：追求最优目标的数学问题。 经典最优化理论：

（1） 无约束极值问题：opt f(x1,x2, ,xn)

（min f(x1,x2, ,xn)或max f(x1,x2, ,xn)）

其中，f(x1,x2, ,xn)是定义在n维空间上的可微函数。

解法（求极值点）：求驻点，即满足

fx 1(x1, ,xn) 0

fx 2(x1, ,xn) 0

f (x, ,x) 0

n xn1

并验证这些驻点是否极值点。

（2） 约束极值问题：opt f(x1,x2, ,xn)

s.t. hj(x1,x2, ,xn) 0,j 1,2, ,l(l n)

解法：采用Lagrange乘子法，即将问题转化为求Lagrange函数

L(x1,x2, ,xn; 1, , l) f(x1,x2, ,xn) jhj(x1, ,xn)

j 1

l

的无约束极值问题。

近代最优化理论的实例：

例1 (生产计划问题) 设某工厂有3种资源B1，B2，B3，数量各为b1，b2，b3，要生产10种产品A1， ，A10 。每生产一个单位的Aj需要消耗Bi的量为aij，根据合同规定，产品Aj的量不少于dj，再

设Aj的单价为cj 。问如何安排生产计划，才能既完成合同，又使总收入最多？（线性规划问题）

数学模型：设Aj的计划产量为xj ，z为总收入。 目标函数：maxz

cx

jj

j 1

10

10

aijxj bi,i 1,2,3

约束条件： j 1

x d,j 1,2, ,10

j j

线性规划问题通常采用单纯形法来求解。

例2 (工厂设址问题) 要在m个不同地点计划修建m个规模不完全相同的工厂，他们的生产能力分别是a1,a2 ,am（为简便起见，假设生产同一种产品），第i个工厂的建设费用fi,i 1,2, ,m。又有n个零售商店销售这种产品，对这种产品的需求量分别为

b1,b2 ,bn，从第i个工厂运送一个单位产品到第j个零售商店的运

费为cij。试决定应修建哪个工厂，使得既满足零售商店的需求，又使建设工厂和运输的总费用最小。（混合整数规划问题）

数学模型： 设第i个工厂运往第j个零售商店的产品数量为xij

（i=1， ，m；j=1， ，n），且

1, 如果修建第i个工厂

yi ,i 1, ,m

0, 否则

n

目标函数：minz fiyi cijxij

i 1 j 1

m

n

xij aiyi, i 1, ,m j 1m

xij bj, j 1, ,n

约束条件： i 1

yi 0 或 1, i 1, ,m xij 0, i 1, ,m;j 1, ,n

整数规划问题通常可用分枝定界法或割平面法来求解。

例3 (投资计划问题) 假设某一个生产部门在一段时间内可用于投资的总金额为a亿元，可供选择的项目总共有n个，分别记为1，2， n。并且已知对第j个项目的投资总数为aj亿元，而收益额总数为cj亿元。问如何使用资金a亿元，才能使单位投资获得的收益最大。（非线性规划问题）

1, 对第j个项目投资

, j 1, ,n 数学模型：设xj

0, 否则

cx

j

n

j

目标函数：

maxz

ax

jj 1

j 1n

j

n

ajxj aj 1

约束条件：

x 0 或 1, j 1, ,n j

非线性规划问题的求解方法很多，是本课的重点。

动态规划是解决“多阶段决策过程”的最优化问题的一种方法，基于“Bellman最优性原理”，例如：资源分配问题，生产与存储问

题。

例4 (多参数曲线拟合问题)已知热敏电阻R依赖于温度T的函数关系为

R x1e

x2T x3

（*）

其中，x1,x2,x3是待定的参数，通过实验测得T和R的15组数据列表如下，如何确定参数x1,x2,x3？

建立数学模型：测量点(Ti,Ri)与曲线R(T)对应的点产生“偏差”，即

S [Ri x1e

i 1

15

x2

Ti x32

]

得如下无约束最优化问题：

minf(x) [Ri x1e

i 1

15

x2

Ti x32

]

通常采用最小二乘法。

§1.2 最优化问题的数学模型

一、 最优化问题的数学模型

1. 定义1：设向量 [a1,a2, ,am], [b1,b2, ,bm]. 若ai bi (i 1,2, ,m)，则记 或 ； 若ai bi (i 1,2, ,m)，则记 或

n

TT

。

2．一般模型： opt f(x)(或min或max)，x R （1）

(2) Si(x) 0, i 1, ,m

s.t.

h(x) 0, j 1, ,l (3) j

T

x [x,x, ,x]其中，； f(x)，Si(x)，hj(x)是关于变量12n

x1,x2, ,xn的实值连续函数，一般可假定它们具有二阶连续偏导数。

3．向量模型： opt f(x)(或min或max)，x R （1）

n

(2) S(x) 0

s.t.

h(x) 0 (3)

其中，f(x)称为目标函数；

Si(x)， hj(x)称为约束函数；

满足约束条件（2），（3）的点称为容许解或容许点（或可行解）； 容许解的全体称为容许域（或可行域），记为R；

满足（1）的容许点称为最优点或最优解（或极小（大）点），记

*

为x；f(x)称为最优值；

不带约束的问题称为无约束问题，带约束的问题称为约束问题； 若目标函数f(x)，约束函数 Si(x)， hj(x)都是线性函数，则

称为线性规划；若其中存在非线性函数，则称为非线性规划；

若变量只取整数，称为整数规划； 若变量只取0，1，称为0—1规划。

注：因 h(x) 0 h(x) 0，-h(x) 0，则最优化问题一般可 写成

opt f(x) s.t. S(x) 0

二、 最优化问题的分类

一维问题 无约束问题

n维问题 静态规划

线性规划最优化问题 约束问题 非线性规划

动态规划

§1.3 二维问题的图解法

例1. maxz 2x1 3x2

x1 2x2 8

s.t. 4x1 16

x,x 0 12

解：1. 由全部约束条件作图，求出可行域R：凸多边形OABC 2. 作出一条目标函数的等值线：设2x1 3x2 6 ，作该直线即为一条目标函数的等值线，并确定在可行域内，这条等值线向哪个方

向平移可使z值增大。

3. 平移目标函数等值线，做图求解最优点，再算出最优值。顶

T

点B(4,2)是最优点，即最优解x [42]，最优值z 14。

分析： 线性规划问题解的几种情况 （1） 有唯一最优解（上例）；

（2） 有无穷多组最优解：目标函数改为maxz 2x1 4x2 （3） 无可行解：增加约束x2 5，则R 。 （4） 无有限最优解（无界解）：例 maxz x1 x2

x1 2x2 4

s.t. - x1 x2 2

x,x 0 12

结论：（1）线性规划问题的可行域为凸集，特殊情况下为无界域或空集。（2）线性规划问题若有最优解，一定可在其可行域的顶点上得到。

22

例2. min(x1 …… 此处隐藏：5013字，全部文档内容请下载后查看。喜欢就下载吧 ……