第1章最优化问题总论

第一章 最优化问题总论

无论做任何一件事，人们总希望以最少的代价取得最大的效益，也就是力求最好，这就是优化问题．最优化就是在一切可能的方案中选择一个最好的方案以达到最优目标的学科．例如，从甲地到乙地有公路、水路、铁路、航空四种走法，如果我们追求的目标是省钱，那么只要比较一下这四种走法的票价，从中选择最便宜的那一种走法就达到目标．这是最简单的最优化问题，实际优化问题一般都比较复杂．

概括地说，凡是追求最优目标的数学问题都属于最优化问题．作为最优化问题，一般要有三个要素：第一是目标；第二是方案；第三是限制条件．而且目标应是方案的“函数”．如果方案与时间无关，则该问题属于静态最优化问题；否则称为动态最优化问题．

§1.1 最优化问题数学模型

最简单的最优化问题实际上在高等数学中已遇到，这就是所谓函数极值，我们习惯上又称之为经典极值问题．

例1.1 对边长为a的正方形铁板，在四个角处剪去相等的正方形以制成方形无盖水槽，问如何剪法使水槽的容积最大？

解 设剪去的正方形边长为x，由题意易知，与此相应的水槽容积为

f(x)?(a?2x)2x．

令

f'(x)?2(a?2x)(?2)x?(a?2x)2?(a?2x)(a?6x)?0，

得两个驻点：

x?11a，x?a26．

a第一个驻点不合实际，这是因为剪去4个边长为2的正方形相当于将铁板全部剪去．现

在来判断第二个驻点是否为极大点．

af''()??4a?06∵ f''(x)?24?8a， ，

ax?6 是极大点． ∴

a因此，每个角剪去边长为6的正方形可使所制成的水槽容积最大．

例1.2 求侧面积为常数6a(a?0)，体积最大的长方体体积．

2y，z体积为v，则依题意知体积为 解 设长方体的长、宽、高分别为x，v?f(x，y，z)?xyz，

条件为

?(x，y，z)?2(yz?xz?xy)?6a2?0．

由拉格朗日乘数法，考虑函数

F(x，y，z)?xyz??(2yz?2xz?2xy?6a2)，

Fx??yz?2?(y?z)?0，Fy??xz?2?(z?x)?0，y，z应是正数，由此??0，将上面三个等式分别乘以x，y，z并利用条件由题意可知x，Fz??xy?2?(x?y)?0，

yz?zx?xy?3a2，得到

?xyz?2?(3a2?yz)?0，?2?xyz?2?(3a?zx)?0，?2xyz?2?(3a?xy)?0．?比较以上三式可得

3a2?yz?3a2?zx?3a2?xy，

从而x?y?z?a．又侧面积固定的长方体的最大体积客观存在，因此侧面积固定的长方体中以正方体体积最大，其最大值为a．

例1.3 某单位拟建一排四间的停车房，平面位置如图1.1所示．由于资金及材料的限制，围墙和隔墙的总长度不能超过40m，为使车房面积最大，应如何选择长、宽尺寸？

解 设四间停车房长为x1，宽为x2．由题意可知面积为

3f(x1，x2)?x1x2，

且变量x1，x2应满足

2x1?5x2?40， x1?0，x2?0．

x1 x2 图1.1

maxf(x1,x2)?x1x2，

?2x1?5x2?40，??x1?0，x2?0．

即求

以上三个例子，虽然简单，但是它代表了三种类型的最优化问题．

第一个例子代表无约束极值问题：

f(x1,x2,?,xn)或maxf(x1,x2,?,xn)．这里，一般可表示为minf(x1,x2,?,xn)是定义在Rn上的可微函数．

求极值的方法是从如下含有n个未知数x1,x2,?,xn的非线性方程组

中解出驻点，然后判定或验证这些驻点是不是极值点．

第二个例子代表具有等式约束的极值问题： 一般可表示为

?f'x1(x1，x2?xn)?0，??f'x2(x1，x2?xn)?0，???????f'(x，x?x)?0n?xn12

该问题的求解通常采用拉格朗日乘数法，即把这个问题转化为求

mx2，?，xn)或maxf(x1，x2，?，xn)，??minf(x1，?x2，?，xn)?0，j?1，2，3，?，m(m?n)．??hj(x1，

L(x1，x2，?，xn；?1，?2，?，?m)?f(x1，x2，?，xn)???jhj(x1，x2，?，xn)j?1的无约束极值问题．

第三个例子代表具有不等式约束的极值问题．

下面具体分析上述三种类型的最优化问题中按经典极值问题解法可能出现不能解决的情况：

（1）当变量个数增加且方程组又是非线性，求解此方程组只有在相当特殊情况下才能人工解出．正因为如此，通常高等数学中的求极值问题的变量个数一般不超过三个．

（2）当限制条件出现不等式，无论变量数多少，按经典极值方法求解根本无法解决． 直到本世纪50年代，最优化理论的建立以及电子计算机的迅速发展，才为求解各种最优化问题提供了雄厚的基础和有效手段．不过最优化方法作为一门崭新的应用学科，有关理论和方法还没有完善，有许多问题还有待解决，目前正处于迅速发展之中．

最优化问题的数学模型包含三个要素：变量（又称设计变量）、目标函数、约束条件． 一、变量

一个优化设计方案是用一组设计参数的最优组合来表示的．这些设计参数可概括地划分为两类：一类是可以根据客观规律、具体条件、已有数据等预先给定的参数，统称为常量；另一类是在优化过程中经过逐步调整，最后达到最优值的独立参数，称为变量．优化问题的目的就是使各变量达到最优组合．变量的个数称为优化问题的维数．例如有n个变量

x1，x2，?，xn的优化问题就是在n维空间Rn中寻优．n维空间Rn中的点X?[x1，x2，?，xn]T就代表优化问题中的一个方案．当变量为连续量时，称为连续变量；

若变量只能在离散量中取值，称为离散变量．

二、目标函数

反映变量间相互关系的数学表达式称为目标函数．其值的大小可以用来评价优化方案的好坏．按照规范化的形式，一般把优化问题归结为求目标函数的极小化问题，换句话说，目标函数值越小，优化方案越好．对于某些追求目标函数极大的问题，可以转化成求其负值最小的问题，即

maxf(X)?maxf(x1，x2，?，xn)??min[?f(X)]．

因此在本书的叙述中，一律把优化问题描述为目标函数的极小化问题，其一般形式为

minf(X)?minf(x1，x2，?，xn)． 如果优化问题只有一个目标函数，称为单目标函数，如果优化问题同时追求多个目标，则该问题的目标函数称为多目标函数．

多目标优化问题的目标函数通常表示为

V?minF(X)?[f1(X)，f2(X)，?，fm(X)]T，

TX?[x，x，?，x]12n其中．这时的目标函数在目标空间中是一个m维矢量，所以又称之为

矢量优化问题（一般用min加一个前缀“V?”来表示矢量极小化）． 三、约束条件

变量间本身应该遵循的限制条件的数学表达式称为约束条件或约束函数． 约束条件按其表达式可分为不等式约束和等式约束两种，即

2?，l，??gi(X)?0，i?1，，s.t.?2?，m．??hj(X)?0，j?1，，

上式中“s. t.”为Subject to的缩写，意即“满足于”或“受限于”．按约束条件的作用还可将约束条件划分为起作用的约束（紧约束、有效约束）和不起作用的约束（松约束、消极约束）．等式约束相当于空间里一条曲线（曲面或超曲面），点X必须为该曲线（曲面或超曲面）上的一点，因而总是紧约束．有一个独立的等式约束，就可用代入法消去一个变量，使优化问题降低一维．因此，数学模型中独立的等式约束个数应小于变量个数；如果相等，就不是一个待定优化系统，而是一个没有优化余地的既定系统．不等式约束通常是以其边界

g(X)?0(或g(X)?0)表现出约束作用的，它只限制点X必须落在允许的区域内（包括边

界上），因而不等式约束的个数与变量个数无关．不带约束条件的优化问题称为无约束最优化问题；带约束条件的优化问题称为约束最优化问题．

四、带约束条件的优化问题数学模型表示形式

综上所述，全书所要讨论的问题是如下的（静态）最优化问题，其表示形式有三种： 第一种最优化问题表示形式为

[x1，x2，?，xn]T??minf(x1，x2，?，xn)，第二种最优化问题表示形式为

x2，?，xn)?0，i?1，，2?，l，??gi(x1，s.t.?x2，?，xn)?0，j?1，，2?，m(m?n)．??hj(x1， minfX(，)X??第三种最优化问题表示形式为

minf(X)，X??0i?，，1?2，l，??gi(X)?，s.t.?2?，m(m?n)．??hj(X)?0，j?1，，

?G(X)?0，s.t.??H(X)?0，

TT?，gl(X)]，H(X)?[h1(X)，?，hm(X)]． 其中G(X)?[g1(X)，n （1.1）

上述三种表示形式中，X??称为集约束．在所讨论的最优化问题中，集约束是无关紧要的．这是因为一般??R，不然的话，?通常也可用不等式约束表达出来．因此今后一般不再考虑集约束．

满足所有约束的点X称为容许点或可行点．容许点的集合称为容许集或可行域．可用 D?{X|gi(X)?0，i?1，，2?，l；hj(X)?0，j?1，，2?，m(m?n)} 表示．

*一般地，对于最优化问题（1.1）的求解，是指在可行域内找一点X，使得目标函数f(X)在该点取得极小值，即

f(X*)?minf(X)，?G(X*)?0，s.t.?*?H(X)?0．

**f(X)称为最优X这样的称为问题（1.1）的最优点，也称极小点，而相应的目标函数值

*值；合起来，(X，f(X))称为最优解，但习惯上常把X本身称为最优解．最优点的各分

**量和最优值必须是有限数．

§1.2 最优化问题的算法

一、二维最优化问题的图解法

二维最优化问题具有鲜明的几何解释，这对于理解有关理论和掌握所述的方法是很有益处的．下面讨论的二维最优化问题为

minf(x1，x2)s.t.2，?，l，?gi(x1，x2)?0i?1，?x2)?0.?h(x1，

（一）约束集合

x2的坐标平面上为一条直线；不等式约束在当约束函数为线性时，等式约束在x1，x1，x2的坐标平面上为一半平面．当约束函数（例如h(x1，x2)）为非线性时，则等式约束条

x2)?0在x1，x2的坐标平面上为一条曲线（如图1.2所示）件h(x1，．当约束函数（例如

g1(x1，x2)）为非线性时，则不等式约束g1(x1，x2)?0在x1，x2的坐标平面上为曲线g1(x1，x2)?0把坐标平面分成两部分当中的一部分（如图1.3所示）．

图1.2

图1.3

综上所述，当把约束条件中的每一个等式所确定的曲线，以及每一个不等式所确定的部

x2坐标平面上画出之后，它们相交的公共部分即为约束集合D． 分在x1，x2坐标平面上画出约束集合 例1.4 在x1，2D?{[x1,x2]T|x12?x2?1，x1?0，x2?0}．

x2?0的解 满足x1?x2?1的区域为以原点为圆心，半径为1的圆盘；满足x1?0，区域为第一象限中的扇形（如图1.4所示）．

22（二）等高线

我们知道

TS等．

（4）基于系统动态演化的算法．将优化过程转化为系统动态的演化过程，基于系统动态的演化来实现优化，如神经网络和混沌搜索等．

（5）混合型算法．指上述各算法从结构或操作上相混合而产生的各类算法． 优化算法当然还可以从别的角度进行分类，如确定性算法和不确定性算法，局部优化算法和全局优化算法等．

§1.4 组合优化问题简介

一、组合优化问题建模

优化问题涉及的工程领域很广，问题种类与性质繁多，归纳而言，最优化问题可分为函数优化问题和组合优化问题两大类，上一节介绍的最优化数学模型属于函数优化问题，该函数优化的对象是一定区间内的连续变量，而组合优化的对象则是解空间中的离散状态．本节重点介绍组合优化问题．

组合优化问题是通过对数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等，所研究的问题涉及信息技术、经济管理、工业工程、交通运输、通信网络等诸多领域，该问题数学模型可表示为

minf(X)X???G(X)?0，s.t.??H(X)?0，

其中f(X)为目标函数，G(X)和H(X)为约束函数，X为决策变量，?表示有限个点组

成的集合．

一个组合优化问题可用3个参数(?，D，f)表示，其中?表示决策变量的定义域，D表示可行解区域D?{X|X??，G(X)?0，H(X)?0}，D中的任何一个元素称为该问题的

*可行解，f表示目标函数，满足f(X)?min{f(X)|X?D}的可行解X称为该问题的

*最优解．组合最优化问题的特点是可行解集合为有限集．由直观可知，只要将?中有限个点逐一判别是否满足约束条件G(X)?0，H(X)?0和比较目标函数值的大小，该问题的最优解一定存在并可以求得，下面是三个典型的组合优化问题．

例1.9 0-1背包问题（knapsack problem）

设有一个容积为b的背包，n个体积分别为ai(i?1,2,?,n)，价值分别为

ci(i?1,2,?,n)的物品，如何以最大的价值装包?这个问题称为0-1背包问题．用数学模型

表示为

max?cixii?1n， （1.3）

?n??aixi?b，s.t.?i?1?x?{0，1}，i?1，2，?，n．?i(1.4)(1.5)

其中目标（1.3）欲使包内所装物品的价值最大，式（1.4）为包的能力限制，式（1.5）表示

xi为二进制变量，xi?1表示装第i个物品，xi?0则表示不装．

例1.10 旅行商问题（TSP，traveling salesman problem）

d如何选择一条道

一个商人欲到n个城市推销商品，每两个城市i和j之间的距离为ij，

路使得商人每个城市走一遍后回到起点且所走路径最短．TSP还可以细分为对称和非对称距离两大类问题．当对任意的i，j时都有

dij?dji，则称该TSP为对称距离TSP，否则称为

非对称距离TSP．对一般的TSP，它的一种数学模型描述为

min?dijxiji?j， （1.6）

?n2?，n，??xij?1，i?1，，?j?1?n?xij?1，j?1，，2?，n，s..t??i?1?2?|S|?n?2，S?{1，，2?，n}，??xij?|S|?1，?i,j?S?xij?{0，1}，i，j?1，2，?，，ni?j．?以上是基于图论的数学模型．其中式（1.10）中的决策变量

(1.7)(1.8)(1.9)(1.10)

xij=1表示商人行走的路线包含

x?0表示商人没有选择走这条路．i?j的约束可以减少变量

从城市i到城市j的路径，ij的个数，使得共有n?(n?1)个决策变量．目标（1.6）要求距离之和最小．式（1.7）要求商人从城市i出来一次，式（1.8）要求商人走入城市j只有一次．式（1.7）和式（1.8）表示每个城市经过一次．仅有式（1.7）和式（1.8）的约束无法避免回路的产生，一条回路是由k(1?k?n)个城市和k条弧组成，因此，式（1.9）约束旅行商在任何一个城市子集中不形成回路，其中|S|表示集合S中元素个数．

例1.11 聚类问题

，2，?，n}要求聚类成k类，使得各类本身内的点最相m维空间上的n个模式{Xi|i?11(p)R?min?||Xi?Rp||pnpRpi?0近，即，其中p为第类的中心，

n?Xi?1np(p)i，2，?，k，，p?1np为第p类中的点数．

二、算法复杂性

前面给大家介绍的三个组合优化问题例子，模型建立都比较简单，但要求它们的最优解却很困难，而解模型的困难主要原因是所谓的“组合爆炸”，如聚类问题的可能划分方式有

kn/k!个，TSP问题有n!个．显然状态数量随问题规模呈超指数增长，若计算机每秒处理1

亿种排列，则列举20个城市问题的20！种排列约需几百年．如此巨大的计算量是无法承受的，更不用谈更大规模问题的求解，因此解决这些问题的关键在于寻求有效的优化算法，也正是由于组合优化问题算法的复杂性，激起了人们对它的理论与算法研究的兴趣．

算法的复杂性是指算法对时间复杂性和对空间复杂性．按照算法复杂性求解的难易程度，可把组合优化问题分为P类，NP类和NP完全类．

算法或问题的复杂性一般表示为问题规模n（如TSP问题中的城市数）的函数，时间的复杂性记为T(n)，空间的复杂性记为S(n)．在算法分析和设计中，沿用实用性的复杂性概念，即把求解问题的关键操作，如加、减、乘，比较等运算指定为基本操作，算法执行基本操作的次数则定义的算法的时间复杂性，算法执行期间占用的存储单元则定义为算法的空

间复杂性．P类问题指具有多项式时间求解算法的问题类．许多优化问题仍没有找到求得最优解的多项式时间算法，称这种比P类问题更广泛的问题为非确定型多项式算法的问题类，即NP问题．

三、NP完全问题

离散问题的求解常常要从有限个方案中选出一个满意的结果来 ，也许有人认为，从有限个方案中挑选一个，总是比较容易的．然而，事实并非如此，关键在于问题的规模．由于计算机的出现，人们对问题的求解在观念上发生了改变，一个在理论上可解的问题如果在求解时需要花费相当多，以至于不合理的时间（如几百年甚至更长时间），我们不能认为它已解决，而应当努力寻找更好的算法．

如何比较算法的好坏呢？从不同的角度出发可以有不同的回答．这里，仅就算法的计算速度作一个十分粗略的比较．

设有一台每小时能进行M次运算的计算机．并设问题已有两种不同的算法，算法A对规模为n的问题约需作n次运算，算法B则约需作2次运算．运用算法A在一个小时内大

n2约可解一个规模为M的问题，而算法B则大约可解一个规模为log2M的问题．

现在假设计算机有了改进，例如计算速度提高了100倍．此时，利用算法A能求解的问题规模增大了10倍，利用算法B可解的问题规模只增加了log2100?7．前者得到了成倍的增加，而后者则几乎没有什么改变，今天无法求解的问题，将来也很少有希望解决．由于这一原因，对算法作如下分类．

定义1.2（多项式算法） 设A是求解某类问题D的一个算法，n为问题D的规模，用

fA(D，n)表示用算法A在计算机上求解这一问题时需作的初等运算的次数．若存在一个多

项式P(n)和正整数N，当n?N时，总有fA(D,n)?P(n)（不论求解的D是怎样的具体实例），则称算法A是求解问题D的一个多项式算法．

定义1.3（指数算法） 设算法B是求解某类问题D的一个算法，若存在一个常数k?0，对任意n，总可以找到问题D的一个规模为n的实例，用算法B求解时，所需的计算量约为

fB(D，n)?o(2kn)，则称B为求解问题D的一个指数算法．

多项式算法被称为是“好”算法（或有效算法），而指数算法则一般认为是“坏”算法，因为它只能用来求解规模很小的问题．

这样看来，对一个问题只有在找到求解它的多项式算法后才能较为放心．然而十分可惜的是，对于许多具有广泛应用价值的离散模型，人们至今仍未找到多项式算法．现在的任何算法在最坏的情况下计算量均可达到或接近2．

1971年和1972年，S. Cook和R. Karp分别发表了相关论文，奠定了NP完全理论基础．Cook指出，NP完全类问题，具有两个性质：

（1）这类问题中的任何一个问题至今均未发现有多项式算法．

（2）只要其中任一个问题找到了多项式算法，那么其他所有问题也就有了多项式算法． 现在，NP完全类中的问题已被扩充到了四千多个，其中包括前面讨论的旅行商问题．对它们的研究使人们越来越相信这样一个猜测：对这类问题也许根本不存在多项式算法．

n

本文来源：https://www.bwwdw.com/article/8gfo.html