优化方法

优化方法

概述：

在一系列的条件下，寻求最优方案使得目标达到最优的问题统称为优化问题。解决这类问题的方法，自然就称之为优化方法。又称为数学规划。是运筹学的一个重要分支。

分类：

优化问题可以归结为优化模型，按照优化模型的求解方法不同，可以分为以下类型：

（1）按照有无约束条件，无约束和约束优化问题 （2）按照决策变量是否连续分为：

A.数学规划或连续规划LP、NLP、QP B.离散规划或组合优化IP （3）单目标规划和组合规划 （4）确定性规划和不确定性规划

（5）目标规划、动态规划、非线性规划、多目标规划 注：

1、约束优化问题可以转化为无约束优化问题来解决

2、多目标规划可以通过适当的方法转化为单目标规划来解决 3、非线性规划在一定条件下，可以近似为线性规划

4、不确定规划可以通过适当的技巧转化为确定性方法来解决

优化方法：在优化方法中，决策变量、目标函数（尽量简单、光滑）、约束条件、求解方法是四个关键因素。其中包括无约束规则（用fminserch、fminbnd）线性规划（用lingo实现）、非线性规划（用fmincon实现）、多目标规划（效用函数）、动态规划（倒向、正向）整数规划。

目录：

动态规划..................................................................................................2 目标规划..................................................................................................4

1

动态规划

动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。 虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题， 但是一些与时间无关的静态规划（如线性规划、非线性规划） ，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。

应指出，动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种特殊算法（如线性规划是一种算法） 。因而，它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。因此，在学习时，除了要对基本概念和方法正确理解外，应以丰富的想象力去建立模型，用创造性的技巧去求解。

动态规划的数学模型：

（i）将过程划分成恰当的阶段。

（ii）正确选择状态变量xk，使它既能描述过程的状态，又满足无后效性，同时确定允许状态集合Xk。

（iii）选择决策变量uk，确定允许决策集合Uk(xk)。 （iv）写出状态转移方程。

（v）确定阶段指标vk(xk,uk)及指标函数Vkn的形式（阶段指标之和，阶段指标之积，阶段指标之极大或极小等） 。

（vi）写出基本方程即最优值函数满足的递归方程，以及端点条件。

动态规划与静态规划的关系 动态规划与静态规划（线性和非线性规划等）研究的对象本质上都是在若干约束条件下的函数极值问题。两种规划在很多情况下原则上可以相互转换。

动态规划可以看作求决策u1,u2,un使指标函数V1n(x1,u1,u2,,un)达到最优 （最大或最小）的极值问题，状态转移方程、端点条件以及允许状态集、允许决策集等是约束条件，原则上可以用非线性规划方法求解。

一些静态规划只要适当引入阶段变量、状态、决策等就可以用动态规划方法求解。

与静态规划相比，动态规划的优越性在于：

（i）能够得到全局最优解。由于约束条件确定的约束集合往往很复杂，即使指标函数较简单，用非线性规划方法也很难求出全局最优解。而动态规划方法把全过程化为一系列结构相似的子问题，每个子问题的变量个数大大减少，约束集合也简单得多，易于得到全局最优解。特别是对于约束集合、状态转移和指标函数不能用分析形式给出的优化问题，可以对每个子过程用枚举法求解，而约束条件越多，决策的搜索范围越小，求解也越容易。对于这类问题，动态规划通常是求

2

全局最优解的唯一方法。

（ii）可以得到一族最优解。与非线性规划只能得到全过程的一个最优解不同，动态规划得到的是全过程及所有后部子过程的各个状态的一族最优解。 有些实际问题需要这样的解族，即使不需要，它们在分析最优策略和最优值对于状态的稳定性时也是很有用的。当最优策略由于某些原因不能实现时，这样的解族可以用来寻找次优策略。

（iii）能够利用经验提高求解效率。如果实际问题本身就是动态的，由于动态规划方法反映了过程逐段演变的前后联系和动态特征， 在计算中可以利用实际知识和经验提高求解效率。如在策略迭代法中，实际经验能够帮助选择较好的初始策略，提高收敛速度。

动态规划的主要缺点是：

（i）没有统一的标准模型，也没有构造模型的通用方法，甚至还没有判断一个问题能否构造动态规划模型的准则。这样就只能对每类问题进行具体分析，构造具体的模型。对于较复杂的问题在选择状态、决策、确定状态转移规律等方面需要丰富的想象力和灵活的技巧性，这就带来了应用上的局限性。

（ii） 用数值方法求解时存在维数灾 （curse of dimensionality） 。 若一维状态变量有m个取值，那么对于n维问题，状态xk就有mn个值，对于每个状态值都要计算、存储函数fk(xk)对于n稍大的实际问题的计算往往是不现实的。目前还没有克服维数灾的有效的一般方法。

3

目标规划 一、引言

1．线性规划的局限性

只能解决一组线性约束条件下，某一目标只能是一个目标的最大或最小值的问题。

2．实际决策中，衡量方案优劣考虑多个目标。这些目标中，有主要的，也有次要的；有最大值的，也有最小值的；有定量的，也有定性的；有相互补充的，也有相互对立的，LP则无能为力。 3．目标规划（Goal Programming） 美国经济学家查恩斯（A. Charnes）和库柏（W. W. Cooper）在1961 年出版的《管 理模型及线性规划的工业应用》一书中，首先提出的。 4．求解思路

（1）加权系数法

为每一目标赋一个权系数，把多目标模型转化成单一目标的模型。但困难是要确 定合理的权系数，以反映不同目标之间的重要程度。 （2）优先等级法

将各目标按其重要程度不同的优先等级，转化为单目标模型。 （3）有效解法

寻求能够照顾到各个目标，并使决策者感到满意的解。由决策者来确定选取哪一个解，即得到一个满意解。但有效解的数目太多而难以将其一一求出。

二、与目标规划数学模型有关的概念 1. 正、负偏差变量

设d 为决策变量的函数，正偏差变量dmaxdd0,0表示决策值超过目标值 的部分， 负偏差变量dmindd0,0表示决策值未达到目标值的部分， 这里d0表示d的目标值。因决策值不可能既超过目标值同时又未达到目标值，即恒有dd0

2. 绝对（刚性）约束和目标约束

绝对约束是指必须严格满足的等式约束和不等式约束； 如线性规划问题的所有约束条件，不能满足这些约束条件的解称为非可行解，所以它们是硬约束。目标约束是目标规划特有的，可把约束右端项看作要追求的目标值。在达到此目标值时允许发生正或负偏差，因此在这些约束中加入正、负偏差变量，它们是软约束。线性规划问题的目标函数，在给定目标值和加入正、负偏差变量后可变换为目标约束。也可根据问题的需要将绝对约束变换为目标约束。 3. 优先因子（优先等级）与权系数 一个规划问题常常有若干目标。但决策者在要求达到这些目标时，是有主次或轻重缓急的不同。凡要求第一位达到的目标赋于优先因子P1，次位的目标赋于优先因子P2，并规定PkPk1,k1,2,q，表示Pk比Pk1有更大的优先权。以此

4

类推，若要区别具有相同优先因子的两个目标的差别， 这时可分别赋于它们不同的权系数wj，这些都由决策者按具体情况而定。

4. 目标规划的目标函数

目标规划的目标函数（准则函数）是按各目标约束的正、负偏差变量和赋于相应的优先因子而构造的。当每一目标值确定后，决策者的要求是尽可能缩小偏离目标值。因此目标规划的目标函数只能是minzf(d,d)，其基本形式有三种： （1）要求恰好达到目标值，即正、负偏差变量都要尽可能地小，这时 minzf(dd)

（2）要求不超过目标值，即允许达不到目标值，就是正偏差变量要尽可能地小， 这时

minzf(d)

（3）要求超过目标值，即超过量不限，但必须是负偏差变量要尽可能地小，这时

minzf(d)

对每一个具体目标规划问题， 可根据决策者的要求和赋于各目标的优先因子来构造目标函数。

5. 目标规划的一般数学模型

设xj(j1,2,n)是目标规划的决策变量，共有m个约束是刚性约束，可能是等式约束，也可能是不等式约束。设有l个柔性目标约束，其目标规划约束的偏差为di,di(i1,2,,l)。设有q个优先级别，分别为P1,P2,,Pq。在同一个优先

级Pk中，有不同的权重，分别记为wkj,wkj(j1,2,,l)。因此目标规划的一般数

学表达式为

minzPk(wkjdjwkjdj)

k1j1qlnaijxj(,)bi,i1,,mnj1cijxjdidigi,i1,2,,m j1xj0,j1,2,ndi,di0,i1,2,,l建立目标规划的数学模型时，需要确定目标值、优先等级、权系数等，它都具有一定的主观性和模糊性，可以用专家评定法给以量化。

5

三、求解目标规划的序贯式算法

序贯式算法是求解目标规划的一种早期算法，其核心是根据优先级的先后次序， 将目标规划问题分解成一系列的单目标规划问题，然后再依次求解。 求解目标规划的序贯算法 对于k1,2,q求解单目标规划

 minzPk(wkjdjwkjdj)

k1j1qlaj1nnijxj(,)bi,i1,,m

cj1ijxjdidigi,i1,2,,l

sjj*wsjdj)Zs,s1,2,,k1

(wdj1lxj0,j1,2,n

di,di0,i1,2,,l

**其最优目标值为Zk，当k1时，约束（4）为空约束。当kq时，Zq所对应的

解x*为目标规划的最优解。

注：

1、此时最优解的概念与线性规划最优解的概念已有所不同，但为方便起见，仍称为最优解。

2、目标规划可用Matlab或lingo求解。

6