多目标最优化数学模型

第六章 最优化数学模型

§1 最优化问题

1．1 最优化问题概念 1．2 最优化问题分类 1．3 最优化问题数学模型 §2 经典最优化方法 2．1 无约束条件极值 2．2 等式约束条件极值 2．3 不等式约束条件极值 §3 线性规划 3．1 线性规划 3．2 整数规划

§4 最优化问题数值算法 4．1 直接搜索法 4．2 梯度法 4．3 罚函数法

§5 多目标优化问题 5．1 多目标优化问题 5．2 单目标化解法 5．3 多重优化解法 5．4 目标关联函数解法 5．5 投资收益风险问题

第六章 最优化问题数学模型 §1 最优化问题

1．1 最优化问题概念 （1）最优化问题

在工业、农业、交通运输、商业、国防、建筑、通信、政府机关等各部门各领域的实际工作中，我们经常会遇到求函数的极值或最大值最小值问题，这一类问题我们称之为最优化问题。而求解最优化问题的数学方法被称为最优化方法。它主要解决最优生产计划、最优分配、最佳设计、最优决策、最优管理等求函数最大值最小值问题。

最优化问题的目的有两个：①求出满足一定条件下，函数的极值或最大值最小值；②求出取得极值时变量的取值。

最优化问题所涉及的内容种类繁多，有的十分复杂，但是它们都有共同的关键因素：变量，约束条件和目标函数。 （2）变量

变量是指最优化问题中所涉及的与约束条件和目标函数有关的待确定的量。一般来说，它们都有一些限制条件（约束条件），与目标函数紧密关联。

设问题中涉及的变量为x1,x2,,xn；我们常常也用X(x1,x2,,xn)表示。 （3）约束条件

在最优化问题中，求目标函数的极值时，变量必须满足的限制称为约束条件。 例如，许多实际问题变量要求必须非负，这是一种限制；在研究电路优化设计问题时，变量必须服从电路基本定律，这也是一种限制等等。在研究问题时，这些限制我们必须用数学表达式准确地描述它们。 用数学语言描述约束条件一般来说有两种： 等式约束条件 gi(X)0,不等式约束条件 hi(X)0,

或 hi(X)0,

i1,2,,m i1,2,,r i1,2,,r

注：在最优化问题研究中，由于解的存在性十分复杂，一般来说，我们不考虑不等式约束条件h(X)0或h(X)0。这两种约束条件最优化问题最优解的存在性较复杂。

（4）目标函数

在最优化问题中，与变量有关的待求其极值（或最大值最小值）的函数称为目标函数。

目标函数常用f(X)f(x1,x2,,xn)表示。当目标函数为某问题的效益函数时，问题即为求极大值；当目标函数为某问题的费用函数时，问题即为求极小值等等。

求极大值和极小值问题实际上没有原则上的区别，因为求f(X)的极小值，也就是要求f(X)的极大值，两者的最优值在同一点取到。

1．2 最优化问题分类

最优化问题种类繁多，因而分类的方法也有许多。可以按变量的性质分类，按有无约束条件分类，按目标函数的个数分类等等。

一般来说，变量可以分为确定性变量，随机变量和系统变量等等，相对应的最优化问题分别称为：普通最优化问题，统计最优化问题和系统最优化问题。 按有无约束条件分类：无约束最优化问题，有约束最优化问题。

按目标函数的个数分类：单目标最优化问题，多目标最优化问题。

按约束条件和目标函数是否是线性函数分类：线性最优化问题（线性规划），非线性最优化问题（非线性规划）。

按约束条件和目标函数是否是时间的函数分类：静态最优化问题和动态最优化问题（动态规划）。

按最优化问题求解方法分类：

古典微分法无约束古典变分法①解析法（间接法）

极大值原理有约束库恩图克定理

斐波那西法

一维搜索法黄金分割法

插值法

坐标轮换法

②数值算法（直接法） 

步长加速法多维搜索法方向加速法

单纯形法随机搜索法

最速下降法

无约束梯度法拟牛顿法



共轭梯度法

变尺度法

可行方向法

③数值算法（梯度法）有约束梯度法

梯度投影法

SUMT法化有约束为无约束SWIFT法

复形法





单目标化方法

④多目标优化方法多重目标化方法

目标关联函数法

⑤网络优化方法

1．3 最优化问题的求解步骤和数学模型 （1）最优化问题的求解步骤

最优化问题的求解涉及到应用数学，计算机科学以及各专业领域等等，是一个十分复杂的问题，然而它却是需要我们重点关心的问题之一。怎样研究分析求解这类问题呢？其中最关键的是建立数学模型和求解数学模型。一般来说，应用最优化方法解决实际问题可分为四个步骤进行： 步骤1：建立模型

提出最优化问题，变量是什么？约束条件有那些？目标函数是什么？建立最优化问题数学模型：确定变量，建立目标函数，列出约束条件——建立模型。 步骤2：确定求解方法

分析模型，根据数学模型的性质，选择优化求解方法——确定求解方法。 步骤3：计算机求解

编程序（或使用数学计算软件），应用计算机求最优解——计算机求解。 步骤4：结果分析

对算法的可行性、收敛性、通用性、时效性、稳定性、灵敏性和误差等等作出评价——结果分析。

（2）最优化问题数学模型

最优化问题的求解与其数学模型的类型密切相关，因而我们有必要对最优化问题的数学模型有所掌握。一般来说，最优化问题的常见数学模型有以下几种： ①无约束最优化问题数学模型

由某实际问题设立变量，建立一个目标函数且无约束条件，这样的求函数极值或最大值最小值问题，我们称为无约束最优化问题。其数学模型为： minf(x1,x2,,xn)——目标函数

例如：求一元函数yf(x)和二元函数zf(x,y)的极值。

22又例如：求函数f(x1,x2,x3)3x124x26x32x1x24x1x32x2x3的极值和取

得极值的点。

②有约束最优化问题数学模型

由某实际问题设立变量，建立一个目标函数和若干个约束条件（等式或不等式），这样的求函数极值或最大值最小值问题，我们称为有约束最优化问题。其数学模型为：

minf(x1,x2,,xn) ——目标函数 gi(x1,x2,,xn)0

i1,2,,m ——约束条件

有约束最优化问题的例子：求函数f(x1,x2,x3)x1x3xn在约束条件条件

x1x3xn2008,xi0,i1,2,,n下的最大值和取得最大值的点。

③线性规划问题数学模型

由某实际问题设立变量，建立一个目标函数和若干个约束条件，目标函数 和约束条件都是变量的线性函数，而且变量是非负的，这样的求函数最大值最小

值问题，我们称为线性最优化问题，简称为线性规划问题。其标准数学模型为： minf(x1,x2,,xn)c1x1c2x2cnxn ——目标函数

ai1x1ai2x2aimxnbi

xi0

i1,2,,m

——约束条件

矩阵形式： minf(X)CTX ——目标函数

AXB

——约束条件

X0

其中 X(x1,x2,,xn)T，C(c1,c2,,cn)T，B(b1,b2,,bm)T

a11a21

A

am1

a12a22am2

a1n



a2n



amn

在线性规划问题中，关于约束条件我们必须注意以下几个问题。

注1：非负约束条件xi0(i1,2,,n)，一般来说这是实际问题要求的需要。

如果约束条件为xidi，我们作变量替换zixidi0；如果约束条件为

xidi，我们作变量替换zidixi0。

注2：在线性规划的标准数学模型中，约束条件为等式。

如果约束条件不是等式，我们引入松驰变量，化不等式约束条件为等式约束条件。

情况1：若约束条件为ai1x1ai2x2aimxnbi，引入松驰变量

ziai1x1ai2x2aimxnbi0

原约束条件变为 ai1x1ai2x2aimxnzibi。

情况2：若约束条件为ai1x1ai2x2aimxnbi，引入松驰变量

zibi(ai1x1ai2x2aimxn)0

原约束条件变为 ai1x1ai2x2aimxnzibi

在其它最优化问题中，我们也常常采取上述方法化不等式约束条件为等式约束条件。

实际问题中，我们经常遇到两类特殊的线性规划问题。一类是：所求变量要求是非负整数，称为整数规划问题；另一类是所求变量要求只取0或1，称为0-1

规划问题。

例如：整数规划问题

minzx13x2

x23.13



s.t.22x134x2285。

x0,x0且为整数

21

又例如：0-1规划问题 maxz3x12x25x3

x12x2x32

x4xx4123

s.t.

x1x234x2x36

x1,x2,x30或1。

④非线性规划问题数学模型

由某实际问题设立变量，建立一个目标函数和若干个约束条件，如果目标函数或约束条件表达式中有变量的非线性函数，那么，这样的求函数最大值最小值问题，我们称为非线性规划最优化问题，简称为非线性规划问题。其数学模型为： minf(x1,x2,,xn) ——目标函数 gi(x1,x2,,xn)0

i1,2,,m ——约束条件

其中目标函数或约束条件中有变量的非线性函数。 例如：非线性规划问题 minf(x,y)(x1)2y

g1(x,y)xy20 。

g(x,y)y02

上述最优化问题中，目标函数是非线性函数，故称为非线性规划问题。

前面介绍的四种最优化数学模型都只有一个目标函数，称为单目标最优化问题，简称为最优化问题。

⑤多目标最优化问题数学模型

由某实际问题设立变量，建立两个或多个目标函数和若干个约束条件，且目标函数或约束条件是变量的函数，这样的求函数最大值最小值问题，我们称为多目标最优化问题。其数学模型为： minfi(x1,x2,,xn) gi(x1,x2,,xn)0

i1,2,,s ——目标函数 i1,2,,m ——约束条件

上述模型中有s个目标函数，m个等式约束条件。 例如：“生产商如何使得产值最大而且消耗资源最少问题”“投资商如何使得投资收益最大而且风险最小问题”等都是多目标最优化问题。

§2 经典最优化方法

经典最优化方法包括无约束条件极值问题和等式约束条件极值问题两种，不等式约束条件极值问题可以化为等式约束条件极值问题。

经典的极值理论：首先，根据可微函数取极值的必要条件确定可能极值点；其次，根据函数取极值的充分条件判断是否取极值？是极大值？还是极小值？这种方法已经几百年的历史了。 2．1 无约束条件极值

设n元函数f(X)f(x1,x2,,xn)，求f(X)的极值和取得极值的点。这是一个无约束条件极值问题，经典的极值理论如下。

定理1（极值必要条件）：设n元函数f(X)f(x1,x2,,xn)具有偏导数，则f(X)在XX*处取得极值的必要条件为：

f

|*0xiXX

i1,2,,n。

定理在此不给出证明，读者可自己参看有关资料。

注1：对于一元函数上述定理当然成立，只是偏导数应为导数；

注2：定理只是在偏导数存在的前提下的必要条件。如果函数在某一点偏导数不存在，那在这一点处仍然可能取得极值；

注3：如果函数在某一点偏导数存在，且偏导数都等于零，那么函数在这一点处也不一定取得极值。

例如，函数f(x,y)x2y2在点(0,0)处偏导数不存在，但在这一点处函数仍然取得极小值零。函数f(x,y)x3y5在点(0,0)处偏导数存在，且偏导数都等于零，但在这一点处函数不取极值。

定理1的作用在于，求出函数的可能极值点，然后，我们再研究这些点是否取得极值。

对于许多实际问题来说，函数一定能够取得极大值或极小值，而函数的可能极值点（满足必要条件的点）又只有一点，则这一点当然是函数取得极大值或极小值的点。

对于一般函数而言，我们怎样判定函数在某点是否取极值？是极大值？还是极小值？我们有下面的极值的充分条件定理。

定理2（极值充分条件）：设n元函数f(X)f(x1,x2,,xn)具有二阶偏导数，则

f(X)在XX*处取得极值的充分条件为：

（1）

f

|XX*0xi

i2,3,,n；

2f2x12f

（2）黑塞矩阵xx

212fxxn1

2fx1x22f2x22fxxx2



2fx1xn2fx2xn2f2xn



在XX*处正定或负定； 

（3）黑塞矩阵在XX*处正定时，函数取极小值；负定时，函数取极大值。 本章内容简要讲解理论，注重实际应用，对于许多经典的定理都不进行证明，读者可自己参看有关资料。

22

例1：求函数f(x1,x2,x3)2x126x24x32x1x22x2x3的极值。

解：（1）根据极值存在的必要条件，确定可能取得极值的点：

fff

4x12x2，12x22x12x3，8x32x2

x2x3x1

令

fff

0，解得 (x1,x2,x3)(0,0,0)。 x1x2x3

（2) 根据极值存在的充分条件，确定(x1,x2,x3)(0,0,0)是否是极值点：

2f2f2f计算 4，212，28； 2

x1x2x32f2f2f 0，2； 2，

x1x3x2x3x1x2

204

2

函数的黑塞矩阵为 f(0,0,0)2122

028

420

42

因为 40，440，21223200；

212

028

所以黑塞矩阵负定，

故函数在(x1,x2,x3)(0,0,0)处取得极大值f(0,0,0)0。

2．2 等式约束条件极值

下面我们研究的是有若干个等式约束条件下，一个目标函数的极值问题，其数学模型为：

minf(x1,x2,,xn) ——目标函数

s.t.

gi(x1,x2,,xn)0

i1,2,,m ——约束条件

拉格朗日（Lagrange)乘数法：

（1）令 Lf(x1,x2,,xn)igi(x1,x2,,xn)

i1m

称为上述问题的拉格朗日乘数函数，称i为拉格朗日乘数。 （2）设f(x1,x2,,xn)和gi(x1,x2,,xn)均可微，则得到方程组

m

gifL

i0xjxji1xj



Lgi(x1,x2,,xn)0i

j1,2,,n

i1,2,,n

（3）若(x1,x2,,xn,1,2,,m)是上述方程组的解，则点(x1,x2,,xn)可能为该问题的最优点。 拉格朗日（Lagrange)乘数法的本质是：将求有约束条件极值问题转化为求无条件极值问题；所求得的点，即是取得极值的必要条件点。

拉格朗日乘数法没有解决极值的存在性问题，但是，如果拉格朗日乘数函数具有二阶连续偏导数，我们也可以应用黑塞矩阵来判定函数是否取得极值。 在具体问题中，点(x1,x2,,xn)是否为最优点通常可由问题的实际意义决定。 例2：求表面积为定值a2，而体积为最大的长方体的体积。 解：设长方体的三棱长为x,y,z，体积为V； 建立数学模型如下： maxVxyz

2xy2xz2yza2

s.t.

x0,y0,z0

构造拉格朗日乘数函数L(x,y,z)xyz(2xy2yz2xza2)，则有

L

xyz2(yz)0L

xz2(xz)0 y

Lxy2(xy)0z

解得 xyz

663

a，maxVa 为所求。 636

2．3 不等式约束条件极值

对于不等式约束条件极值问题：

minf(x1,x2,,xn) ——目标函数 s.t.

gi(x1,x2,,xn)0

i1,2,,m ——约束条件

我们有与拉格朗日乘数法密切相关的方法库恩—图克定理。

定理3（库恩—图克定理）：对于上述不等式约束条件极值问题，设f(x1,x2,,xn)和gi(x1,x2,,xn)均可微，令 Lf(x1,x2,,xn)igi(x1,x2,,xn)

i1m

假设i存在，则在最优点XX*(x1,x2,,xn)处，必满足下述条件：

m

gLf

（1）ii0

xjxji1xj

j1,2,,n； i1,2,,m； i1,2,,m；

（2）gi(x1,x2,,xn)0（3）igi(x1,x2,,xn)0（4）i0。

根据库恩—图克定理我们可以求解许多不等式约束条件极值问题，值得注意的是应用库恩—图克定理求解不等式约束条件极值问题，定理并没有解决最优解的存在性问题，因此，我们必须另行判断。 例3：求解最优化问题（最优解存在） minf(x,y)(x1)2y

g(x,y)xy20 1

g2(x,y)y0

解：构造函数 L(x,y,z)(x1)2y1(xy2)2(y)，

L

x2(x1)10Ly1120

根据库恩—图克定理则有 

1(xy2)0y0210,20

解得： x1,y0,10,21；所求最优解为(x,y)(1,0)，最优值为0。

§3 线性规划

3．1 线性规划

设线性规划标准数学模型为：

minf(x1,x2,,xn)c1x1c2x2cnxn ——目标函数

ai1x1ai2x2aimxnbi s.t.xi0i1,2,,mi1,2,,n ——约束条件

矩阵形式： minf(X)CTX ——目标函数 AXB ——约束条件 X0

其中 X(x1,x2,,xn)T，C(c1,c2,,cn)T，B(b1,b2,,bm)T

线性规划问题的求解有一整套理论体系，一般来说，应用单纯形法求解。此方法尽管比较复杂，然而在计算机上实现并不困难。解线性规划问题的单纯形法已在许多数学计算软件中实现，我们求解线性规划问题可根据需要，应用数学计算软件求解即可。在此，我们不系统研究其理论，只是简单介绍线性规划的穷举法和单纯形法的基本思想。

3.2 线性规划的穷举法

（1）穷举法基本原理和步骤

步骤1：将线性规划问题化成矩阵的标准形式，设系数矩阵的秩R(A)m，则对应线性方程组的基础解系自由变量的个数为nm个。

步骤2：穷举法求解：令xi1xi2xi(nm)0，解得对应线性方程组一组解为 (1,2,,n)；对应目标函数值为f(x1,x2,,xn)fi。

mnm 从n个变量x中选nm个作为自由变量，令它们的值为0，可得到CnCn

组解。

mnm步骤3：确定最优解：如果最优解存在，则上述求解得到的对应Cn个目标Cn

函数值中，最小者（或最大者）即为所求最小（或最大）最优值，对应的解为最优解。

步骤4：证明解为最优解：

①将最优解对应的自由变量看成参数t1,t2,,t(nm)；解对应线性方程组得

xibi0bi1t1bi2t2bi(nm)t(nm),i1,2,,n。

i1,2,,n ②将对应线性方程组解xibi0bi1t1bi2t2bi(nm)t(nm),

代入目标函数得：ff0d1t1d2t2d(nm)t(nm)。

如果di0,i1,2,,n，则所求为最小值最优解；否则，线性规划问题无最小值最优解。

如果di0,i1,2,,n，则所求为最大值最优解；否则，线性规划问题无最大值最优解。

例1：目标函数：maxf(X)2x13x2x3

x1x35x2xx1024s.t.1 xx452

xi0,i1,2,3,4,5

解：约束条件的增广矩阵为：

10100 A12010，R(A)3；

01001

令x1x20，解得X(0,0,5,10,4),f(X)5；

令x1x30，无解；

令x1x40，解得X(0,5,5,0,1)，不满足非负条件，舍去；

令x1x50，解得X(0,4,5,2,0),f(X)17；

令x2x30，解得X(5,0,0,5,4),f(X)10；

令x2x40，解得X(10,0,5,0,4)，不满足非负条件，舍去；

令x2x50，无解；

5335令x3x40，解得X(5,,0,0,),f(X)； 222

令x3x50，解得X(5,4,0,3,0)，不满足非负条件，舍去；

令x4x50，解得X(2,4,3,0,0),f(X)19；

所以maxf(X)19，最优解为X(2,4,3,0,0)。

证明：令x4t,x5s解得

x12t2sx4s2 x33t2s

xi0,i1,,5目标函数f(X)19ts；

因为x4t,x5s非负，所以maxf(X)19，故最优解存在。

（2）单纯形法基本原理和步骤

①将线性规划问题化成矩阵的标准形式，设系数矩阵的秩R(A)m，则对应线性方程组的基础解系的个数为nm个，即有nm个自由参数变量。 ②选取nm个非基变量（自由参数变量）,不妨假设为xj,jm1,,n； 解得线性规划问题的典式

nxiiijxj(i1,2,,m)

jm1n  0minffjxj(i1,2,,m)

jm1j1,2,,nxj0

定理1：如果线性规划问题的上述典式中所有j0,jm1,,n；

则X(1,2,,m,0,,0)为最优解。

定理2：如果线性规划问题的上述典式中存在某个mk0，且对应

i(mk)0,i1,2,,m；则线性规划问题无最优解。

由定理1和定理2知，如果我们选择适当的nm个非基变量，就可以根据所求得的典式判断最优解的存在与否，从而求解该线性规划问题。

单纯形法的思想是：选择适当的基变换（进基和退基），不断地变换典式，使得典式中目标函数值不断下降，从而求得最优解。其核心为如何选择进基和退基。

③进基规则和退基规则

进基规则——正检验数最小下标规则，即选取smin{j|j0}，由此确定xs为进基。

退基规则：选取这样的下标Jr（Ji表示第i个基变量的下标）

ii|is0} JrminJ{|,is0} iisis

由此确定xJr离基。

④单纯形法的基本步骤：

步骤1：化线性规划问题为标准形式。

步骤2：确定基变量，求得基本可行解和典式；

是否满足最优解定理或最优解不存在定理的条件？判断最优解的情况。 步骤3：根据进基规则和退基规则，选择进基和退基，进行基变换，求得对应典

式。重复进行基变换，直到求出最优解或判断出无最优解为止。

例2：解线性规划问题

minf2x1x2

x1x2x35xxx0124s.t. 6x2xx21251

xi0,i1,2,3,4,5

解：（1）约束条件的增广矩阵为：

11100 A11010，R(A)3；

62001

所以非基变量个数为两个。

（2）选取x1,x2作为非基变量，x3,x4,x5作为基变量，解得典式为

x35x1x2xxx124

x5216x12x2

minf2xx12xi0,i1,,5

不满足最优解定理和最优解不存在定理的条件，故必须进行基变换。

（3）进行基变换

选取进基： 120,210，

根据smin{j|j0}得x1为进基。 52121选取退基：min{,， 166

根据i|is0}，Jrmin{Ji|i,is0}得x5为离基。 isis

进行基变换，求新基的典式：

321xx32326x5

741x4x2x5236 x71x1x 12523611minf7x2x533xi0,i1,,5

判断：不满足最优解定理和最优解不存在定理的条件，故继续进行基变换。

（4）继续进行基变换

1选取进基： 20，根据smin{j|j0}得x2为进基。 3

921219选取退基：min{,,}， 4824

根据i|is0}，Jrmin{Ji|i,is0}得x3为离基。 isis

进行基变换，求新基的典式：

931xxx52342411x42x3x522 x111x1x 1354243111minfx3x5424xi0,i1,,5

满足最优解定理的条件，根据定理最优解为

119131 X(,,0,,0),minf。 4424

3．2 整数规划

设纯整数线性规划数学模型为：

minf(x1,x2,,xn)c1x1c2x2cnxn ——目标函数

axai2x2aimxnbi s.t.i11

xi0,xi为整数i1,2,,mi1,2,,n ——约束条件

这一类问题与一般线性规划比较起来，似乎是变简单了，但实际上恰恰相反，由于解集是一些离散的整数点集，使得单纯形法失去了应用的基础，求解变得困难而复杂。整数线性规划目前还缺乏统一的解法，这里只介绍分枝定界法，它是目前求解纯整数线性规划和混合整数线性规划最常用的方法，计算机求解整数线性规划的大多数程序也是以它为基础的。

分枝定界法：考虑上述纯整数线性规划问题，

（1）解对应线性规划问题

minf(x1,x2,,xn)c1x1c2x2cnxn ——目标函数

axai2x2aimxnbi s.t.i11

xi0i1,2,,mi1,2,,n ——约束条件

若无最优解，则原纯整数线性规划问题无最优解； 若有最优解，最优点(x1,x2,,xn)，目标函数最优值z0f(x1,x2,,xn)。 若最优点(x1,x2,,xn)全为整数，则为原纯整数线性规划问题的最优解； 若最优点(x1,x2,,xn)不全为整数，则进行下一步。

（2）定界和分枝

定界：M0minf(x1,x2,,xn)z0m0

其中M0取原纯整数线性规划问题中，满足约束条件的某一整数可行解所对应的目标函数值。原纯整数线性规划问题的最优解必须满足定界条件。

分枝：选取(x1,x2,,xn)中一个不为整数所对应的xk分枝，

xk[xk]R1 axaxaxbi11i22imnix0i

xk[xk]R2 axaxaxbi11i22imnix0ii1,2,,m i1,2,,ni1,2,,m i1,2,,n

R1和R2称为对应线性规划问题的两枝，也是两个新线性规划问题的约束条件。显然，原纯整数线性规划问题的最优解满足R1或R2。

（3）对R1和R2进行剪枝和分枝

解R1对应的线性规划问题，对其进行剪枝和分枝：

若无最优解，则原纯整数线性规划问题在R1内无最优解。不需要对该区域继续讨论——剪枝。 若有最优解，最优点(x1,x2,,xn)，目标函数的最优值z1f(x1,x2,,xn)。 若z1f(x1,x2,,xn)M0，则原纯整数线性规划问题在R1内无最优解。不

需要对该区域继续讨论——剪枝。 若最优点(x1,x2,,xn)全为整数，则可能为原纯整数线性规划问题的最优解，定界：记M1f(x1,x2,,xn)M0，则M1minf(x1,x2,,xn)m0，本分枝求解结束。 若最优点(x1,x2,,xn)不全为整数，对R1继续进行分枝。

完全类似，解R2对应线性规划问题，对其进行剪枝和分枝。

依此类推，对所有分枝进行求解，剪枝，分枝，定界；直至求得最优解。

（4）最优解的确定

若某Mkm0，则为最优解，求解结束。

若所有分枝求解结束，则最后的上界Mk即为最优解。

例3：应用分枝定界法，求解整数线性规划问题

minzx13x2

x23.13 s.t.22x134x2285

x0,x0且为整数21

解：设原整数线性规划问题目标函数的最优值为z*，

（1）求解线性规划问题：minzx13x2

x23.13 s.t.22x134x2285

x0,x012

得最优解为 x18.12,x23.13；minz17.51。

x23.13记约束区域22x134x2285为R。

x0,x021

（2）对R进行分枝：选取最优解中不是整数的变量，例如x1，将R分成两个子

x19x18x23.13x23.13R:R:区域R1,R2。1， 2 22x34x28522x34x2852211

x10,x20x10,x20

（3）定界：确定最优值z*的上下界。由（1）中求得的最优值知z*17.51；而z*

的上界可由R内的任意一个可行解确定，例如，x17,

故z*19。从而，17.51z*19。

（4）在R1内求最优解，得 x19,

（5）在R2内求最优解，得 x18,x24即为一个可行解。x23.13；minz18.39。 x23.21；minz17.62。

（6）因为R1内最优解不全是整数，因而必须继续对R1分枝：

x24x23x9x191R11:x23.13x23.13 R12:

22x34x28522x34x2851221

x10,x20x10,x20

（7）显然R12内无解，剪枝。

在R11内求最优解，得 x19,x24；minz21；为整数可行解。 但因17.51z*19，而2119，故剪枝。

（8）因为R2内最优解不全是整数，因而必须继续对R2分枝：

x24x23x8x181R21:x23.13x23.13 R22:

22x34x28522x34x2851221

x10,x20x10,x20

（9）显然R22内无解，剪枝。

在R21内求最优解，得 x16.77,x24；minz18.77。

（10）因为R21内最优解不全是整数，因而必须继续对R21分枝：

x17x16x4x242x18x18R211: R212: x3.13x3.132222x134x228522x134x2285x0,x021x10,x20

（11）在R212内求最优解，得 x16,x24.5；minz19.5。

因minz19.5大于z*的上界，故剪枝。

（12）在R211内求最优解，得 x17,x24；minz19。

x24；minz19。 所求原整数规划问题的最优解为：x17,

§4 最优化问题数值算法

最优化问题的数值算法很多，常用的算法多为搜索法，本节只介绍搜索法的基本思想、无约束最优化问题的最速下降法（梯度法）和有约束最优化问题的罚函数法。

4．1 搜索算法

考虑无约束最优化问题： minf(x1,x2,,xn)

我们已经讨论了这类问题的最优解条件，这必须用到函数的解析性质。我们的方法是，先利用必要条件求出平稳点，再应用充分条件判断是否是极值点。但是，我们必须求解一个n个变量n个方程的方程组，并且常常是非线性的。这只有在特殊的情况下，才能求出它的精确解。在一般情况下，都不能用解析法求得精确解。更何况许多实际问题中，函数的解析表达式很难得到。因此，我们必须寻求一些切合实际问题的行之有效的数值解法。搜索算法就是我们常用的方法。

（1）搜索算法的基本思想：假定目标函数f(X)极小值问题。首先，确定目标函数f(X)的初始点X0；然后，按照一定规则产生一个点列{Xk}，这种规则称为算法；规则必须满足（1）点列{Xk}收敛；（2）点列{Xk}收敛到目标函数f(X)的极小值点。

（2）搜索算法的基本步骤：

①选定初始点X0（越接近最优点越好），允许误差0，令k0。 ②假定已得非最优点Xk，则选取一个搜索方向Sk，满足：

目标函数f(X)下降，或gradf(Xk)Sk0。

③选定搜索步长k0，Xk1XkkSk，满足：

f(Xk1)f(XkkSk)f(Xk)。 

④判断Xk1是否是最优点或是满足要求的近似解。

假定给定精度要求为0，常用确定求近似解搜索结束的方法有：

|gradf(Xk1)| ——梯度模确定法；

|f(Xk1)f(Xk)| ——目标函数差值绝对误差法；

|Xk1Xk| ——相邻搜索点绝对误差法。

如果Xk1满足给定精度要求，则搜索完成，近似最优点为X*Xk1； 如果Xk1不满足给定精度要求，令kk1返回（2）继续搜索。

注意1：我们的搜索算法一般得到的都是局部最优解。

注意2：确定求近似解搜索结束的方法还有

|f(Xk1)f(Xk)| ——目标函数差值相对误差法； |f(Xk)|

|Xk1Xk| ——相邻搜索点相对误差法。 |Xk|

（3）搜索算法的关键因素：从搜索算法的基本步骤中，我们知道，搜索算法的关键因素为：一是搜索方向，二是搜索步长。

搜索方向的选择，一般考虑既要使它尽可能的指向极小值点，又要不至于花费太多的计算量。

搜索步长的选择，既要确保目标函数的下降性质，又要考虑近似解的精度要求，还要考虑算法的计算量，问题十分复杂。常用方法有，固定步长法，最优步长法和变步长法。

固定步长法（简单算法）是选取k0为固定值。方法简单，但是有时不能保证目标函数的下降性质。

最优步长法（一维搜索算法）是选取k使得，

f(XkSk) f(XkkSk)min

这是一个关于单变量的函数求极小值问题，这样确定的步长称为最优步长。

变步长法（可接受点算法）是任意选取k，只要使得f(Xk1)f(Xk)即可。 这种选取步长的方法，确保了目标函数的下降性质，尽管每次选取的步长不是最 优的，但实践证明，方法能达到更好的数值效果。

总之，当搜索方向确定以后，步长就是决定最优化算法好坏的重要因素，因此，我们必须特别注重步长的选取问题。

（4）搜索算法的收敛性：搜索算法的收敛性是指，由某算法得到的点列{Xk}能够在有限步骤内收敛到目标函数f(X)的最优点或能够在有限步骤内达到满足

精度要求的目标函数f(X)的最优点的近似值。显然，只有具有收敛性质的算法才有意义。

搜索算法的收敛速度：作为一个好的算法，还必须要求它以较快的速度收敛于最优解。

阶收敛定义：对于收敛于最优解X*的序列{Xk}，若存在与k无关的数

0和1，当k从某个k0开始时，有

|Xk1X*||XkX*| 成立，

则称序列{Xk}收敛的阶为，或称阶收敛。

当1时，称迭代序列{Xk}为线性收敛；当12时，称迭代序列{Xk}为超线性收敛；当2时，称迭代序列{Xk}为二阶收敛。

一般来说，线性收敛是比较慢的，而二阶收敛则是很快的，超线性收敛介于二者之间。如果一个算法具有超线性以上的收敛速度，我们就认为是一个好的算法了。

4．2 无约束最优化问题的梯度法

无约束最优化问题

minf(x1,x2,,xn)

的计算方法很多。无约束最优化问题的计算方法分为两大类：一类是解析法，包括经典最优化方法，最速下降法（梯度法），共轭梯度法，牛顿法和变尺度法等。另一类是直接法，包括坐标轮换法，步长加速法，方向加速法和单纯形法等。 所谓解析法就是在方法的计算过程中，应用到了函数的解析性质（可导性质等）；所谓直接法就是在方法的计算过程中，仅仅涉及目标函数值的计算，而不涉及函数导数等解析性质。我们在这里只介绍最速下降法（梯度法）。

最速下降法理论根据：早在1847年，法国著名数学家Cauchy就曾提出，从任意给定点出发，函数沿哪个方向下降最快的问题。这个问题已从理论上解决了，即沿着函数在该点的负梯度方向前进时，函数下降最快。这就是最速下降法的理论根据。

最速下降法的搜索步骤：

步骤1：选定初始点X0（越接近最优点越好），允许误差0，令k0。 步骤2：假定已得非最优点Xk，计算梯度gradf(Xk)，

(Xfk) 选取搜索方向 Skgrad



步骤3：选定搜索步长k0，Xk1XkkSk，满足：



f(XkkSk)minf(XkSk)。

0



步骤4：判断Xk1是否是最优点或是满足要求的近似解。

根据精度要求，检验是否满足收敛性判断准则：

|gradf(Xk1)|或|f(Xk1)f(Xk)|或|Xk1Xk| 如果Xk1满足给定精度要求，则搜索完成，近似最优点为X*Xk1； 如果Xk1不满足给定精度要求，令kk1返回（2）继续搜索。

2

例1：应用最速下降法求解minf(X)x1225x2。

解：（1）选定初始点X0(2,2)，允许误差0.2，置k:0

收敛判断准则 |f(Xk1)f(Xk)|。

（2）计算梯度gradf(Xk)，选取搜索方向Skgradf(Xk) grad(Xfk){2x1,50x2}|XXk，Sk{2x1,50x2}|XXk 第一点搜索计算：gradf(X0){4,100} }，S0{4,100（3）选定搜索步长k0，Xk1XkkSk，满足：







f(XkkSk)minf(XkSk)

0



第一点搜索计算：求最优步长

minf(X0S0)(24)225(2100)2

0



解得00.02。

（4）判断Xk1是否是最优点或是满足要求的近似解。 第一点搜索计算：X1(1.92,0)

验证收敛判断准则 |f(X1)f(X0)|100.310.02，不满足，继续搜索。 依次类推，直到搜索到最优解或满足精度要求为止。

4．3 罚函数法

对于约束最优化问题也有许多种方法，本段只介绍把约束最优化问题转化为无约束最优化问题的一种求解方法——罚函数法。分为等式约束最优化问题和不等式约束最优化问题两种情况讨论。

（1） 等式约束最优化问题的罚函数法

首先，考虑等式约束最优化问题

minf(X)

s.t.

gi(X)0

i1,2,,m

假定上述等式约束最优化问题的最优解存在。 若记 D{X|gi(X)0,i1,2,,m,XRn}， 构造辅助函数 T(X,M)f(X)M[gi(X)]2——罚函数

i1m

其中M0（罚因子）是一个充分大的正数。

定理1：若对于某确定数M0，无约束最优化问题 minT(X,M)f(X)M[gi(X)]2

i1m

的最优解X*D，则X*必为原等式约束最优化问题的最优解。 证明：设无约束最优化问题 minT(X,M)f(X)M[gi(X)]2

i1m

的最优解X*D，则有： gi(X)0而当XD时，T(X,M)f(X)

所以minf(X)minT(X,M)T(X*,M)f(X*)

i1,2,,m

即X*为原等式约束最优化问题的最优解。

定理2：设f(X)和gi(X)0,i1,2,,m均为连续函数， 若对于任意正数M0，无约束最优化问题 minT(X,M)f(X)M[gi(X)]2

i1m

的最优解X*(M)D，且limX*(M)X*，

M

则limX*(M)X*为原等式约束最优化问题的最优解。

M

定理2的证明请参看有关参考资料。

根据定理1和定理2，我们就可以将通过构造罚函数的方法化为无约束最优化问题求解，这种方法称为罚函数法。 罚函数法的步骤：（等式约束最优化问题罚函数法） 步骤1：构造罚函数 T(X,M)f(X)M[gi(X)]2，

i1m

选定M10，允许误差0，令k:1；

*步骤2：求无约束问题 min； T(X,Mk) 的最优解Xk*步骤3：判断Xk是否是最优点或是满足要求的近似解。

根据精度要求，检验是否满足收敛性判断准则：

* |gi(Xk)|,

m

i1,2,,m

或

[g(X

i

i1

*

k

)]2

*

如果满足收敛性判断准则，则X*Xk，结束搜索；

否则，令k:k1，取Mk1Mk0，返回（2），继续搜索。

下面我们通过一个简单的例子来说明等式约束最优化问题的罚函数法。 例2：应用罚函数法求解非线性规划问题

2 minf(X)x12x2

s.t.x210

2

解：构造罚函数：T(X,Mk)x12x2Mk(x21)2

求罚函数的最优解：应用解析法

TT

2x1， 2x22Mk(x21) x1x2

令上述两式等于零，解得 x10,x2

Mk

1Mk

令Mk得 x10,x21 为所求最优解。 （2） 不等式约束最优化问题的罚函数法 对于，不等式约束最优化问题

minf(X)

s.t.

gi(X)0

i1,2,,m

假定上述不等式约束最优化问题的最优解存在。

由于不等式约束条件gi(X)0,i1,2,,m等价于等式约束条件

min(0,gi(X))0,

i1,2,,m

因而，上述不等式约束最优化问题可以转化为问题

minf(X)

s.t.min(0,gi(X))0类似问题（1）构造罚函数

i1,2,,m

T(X,M)f(X)M[mi0n,(gi(X))2]

i1

m

则将上述等式约束最优化问题的求解转化为下面无约束最优化问题的求解： minT(X,M)f(X)M[min(0,gi(X))]2

i1m

定理3：若对于某确定数M0，无约束最优化问题 minT(X,M)f(X)M[min(0,gi(X))]2

i1m

的最优解X*D，则X*必为原不等式约束最优化问题的最优解， 其中D{X|gi(X)0,i1,2,,m,XRn}。

定理4：设（1）f(X)和gi(X)0,i1,2,,m均为连续函数； （2）原不等式约束最优化问题的最优解X*存在；

（3）数列{Mk}满足0M1M2Mk且limMk；

k

（4）对任意Mk0，问题minT(X,M)的最优解XkX(Mk)都存在，且有界；

（5）点列{Xk}存在极限点；

则：点列{Xk}的极限点是原不等式约束最优化问题的最优解。 罚函数法的步骤：（不等式约束最优化问题罚函数法）

步骤1：构造罚函数 T(X,M)f(X)M[mi0n,(gi(X))2]，

i1m

选定M10，允许误差0，令k:1；

*步骤2：求无约束问题 min； T(X,Mk) 的最优解Xk*步骤3：判断Xk是否是最优点或是满足要求的近似解。

根据精度要求，检验是否满足收敛性判断准则：

* |gi(Xk)|,

m

i1,2,,m

或

[g(X

i

i1

*

k

)]2

*

如果满足收敛性判断准则，则X*Xk，结束搜索；

否则，令k:k1，取Mk1Mk0，返回（2），继续搜索。 例3：应用罚函数法求解非线性规划问题 minf(X)x1x2

g1(X)x12x20

s.t.

g(X)x012

解：构造罚函数 T(X,M)f(X)M[mi0n,(gi(X))2]

i1

m

T(X,Mk)x1x2Mk{[min(0,x12x2)]2[min(0,x1)]2}

求T(X,Mk)的极小值点

T

12Mk[min(0,2x132x1x2)min(0,x1)] x1

T

12Mk[min(0,x12x2)] x2

当x12x20,或x10时，显然上两式不能同时等于零， 所以，此时T(X,Mk)不存在极小值点。

当x12x20,x10时，有

T

12Mk(2x132x1x2)2Mkx1 x1

T

12Mk(x12x2) x2

TT0，0； x1x2

令上面两式等于零：

解得T(X,Mk)的极小值点为 Xk(

111

,)

22Mk(22Mk)22Mk

当Mk取不同值时，可得到相应的Xk值，计算如下表

根据定理得，原问题的极小值点为X*(0,0)，极小值为f(X*)0。

§5 多目标优化问题

在许多实际的最优化问题中，常常遇到目标函数是几个的情况，这一类问题我们称之为多目标优化问题。

例如，投资方向选择问题，我们不仅要求投资的收益最大，而且要求投资的风险最小。

再例如，购买商品问题，我们既要考虑商品的价格，又要考虑商品的质量，甚至还要考虑商品的性能等等。

所谓多目标优化问题是指：目标函数是两个或两个以上的最优化问题。其数学模型为：

minfi(x1,x2,,xn) gi(x1,x2,,xn)0例1：求解多目标优化问题 minx2和miny

i1,2,,s ——目标函数 i1,2,,m ——约束条件

x1 s.t.

y1

解：易求x0,y1时，minx20，miny1。 例2：求解多目标优化问题 max2和miny

x1

s.t.

y1

解：显然，无最优解。

5．1 多目标优化问题的解

多目标优化问题解的存在性极其复杂，这是由多目标优化问题的目标函数多个性和目标函数相互之间的复杂性质决定的。由于目标函数在很多情况下不可能同时达到最大值或最小值，因而，多目标最优化问题很少有最优解，而实际问题又要求我们做出决择，求得一个比较好的解。什么样的解才是我们需要的解呢？对于同一个问题不同的要求导致不同的求解标准，从而就会得到不同的求解结果。为此，我们给出多目标最优化问题的条件最优解概念。

最优解：满足约束条件且使所有目标函数达到要求的最大值或最小值的点称为多目标优化问题的最优解。

可行解：满足多目标优化问题的约束条件的点称为可行解。 条件最优解：满足多目标优化问题的约束条件且满足根据需要设定条件的可

行解称为条件最优解。

对于一个多目标优化问题，即使最优解存在，要求解它也是十分困难的，特殊情况下，我们也只好用搜索法求解。更何况它常常还不存在最优解，因而我们必须寻求其求解条件最优解的方法。

为了求得满足我们要求的解，常常不得不设定一些新的条件，从而求得条件最优解。设定新条件的方法是我们求解多目标优化问题的基本方法。下面的“单目标化方法、多重目标函数方法和目标关联函数方法”都是针对目标函数设定新条件的方法。

5．2 单目标化解法

将原多目标优化问题多个目标函数转化成为只有一个目标函数的单目标优化问题求解的方法称为单目标化方法。 （1）单目标化解法的基本思想

步骤1：构造一个新的目标函数 ff(f1,f2,,fs)

满足性质：在约束条件的区域内f(f1,f2,,fs)是f1,f2,,fs的单调增函数。 特别注意：构造新目标函数也可以根据实际问题，将f(f1,f2,,fs)定义为

f1,f2,,fs的不减函数。

步骤2：建立单目标优化数学模型

minff(f1,f2,,fs) ——目标函数 gi(x1,x2,,xn)0

i1,2,,m ——约束条件

步骤3：求解上述单目标优化数学模型得到：单目标优化问题的最优解，从而可得到原多目标优化问题的最优解或条件最优解。 （2） 单目标优化问题最优解的性质

单目标优化问题的最优解与原多目标最优化问题的最优解有着密切的内在关系。下面的定理揭示了两者之间最重要的一种关系。

定理1：设f(f1,f2,,fs)是f1,f2,,fs的单调增函数，原多目标最优化问题的最优解存在，则单目标优化问题

minff(f1,f2,,fs) gi(x1,x2,,xn)0

i1,2,,m

的最优解存在，且为原多目标最优化问题的最优解。 证明：显然，单目标优化问题的最优解存在。

设原多目标最优化问题的最优解为X*， 则在该点处，目标函数f1,f2,,fs都取得最小值。

设单目标最优化问题的最优解为Y*，

则在该点处，目标函数f(f1,f2,,fs)取得最小值f(Y*)。

显然，1） fi(X*)fi(Y*) 2） f(X*)f(Y*)

i1,2,,s

又因为，f(f1,f2,,fs)是f1,f2,,fs的单调增函数， 根据1）有：f(X*)f(Y*) 所以， f(X*)f(Y*)， 故必有 fi(X*)fi(Y*)

i1,2,,s

即Y*为原多目标最优化问题的最优解。

定理告诉我们：如果多目标最优化问题的最优解存在，则只需求解一个单目标最优化问题就可以得到。

但是，如果多目标最优化问题的最优解不存在呢？则单目标最优化问题的最优解可能存在，也可能不存在。

当原多目标最优化问题的最优解不存在，而单目标最优化问题的最优解存在时，我们称解为单目标条件最优解。这种解在一定程度上反应了原多目标最优化问题的性质，因此，在实践中常常被选用。 （3） 单目标化的常用目标函数

当多目标最优化问题的最优解不存在时，应用单目标化求解方法寻求条件最优解，构造目标函数是关键。新的目标函数反应了原多目标之间的复杂关系，因而，必须根据实际问题构造目标函数，以比较准确地反应实际问题的性质。下面是几种常用的目标函数。

①均衡优化函数 f(f1,f2,,fs)f1f2fs ②权重优化函数 f(f1,f2,,fs)1f12f2sfs 其中1,2,,s为大于零的权重系数 ③平方和优化函数 f(f1,f2,,fs)fi2

i1s

④平方和均衡优化函数 f(f1,f2,,fs)ifi2

i1

s

其中1,2,,s为大于零的权重系数 例2：求解多目标优化问题

x(2y)和max(yx) max

xy1

s.t.

x0,y0

解：问题涉及两个目标函数，可应用单目标化方法求解。

（1）构造单目标函数 f(x,y)(x2y)(yx)3y

f(x,y)3y （2）求解模型 max

xy1

s.t.

x0,y0

得最优解为x0,y1，此时maxf3。

（3）易知原问题最优解存在（可通过作图验证），所以最优解为x0,y1，

x(2y)2，max(yx)1。 此时 max

5．3 多重优化解法

根据实际问题的性质，将原多目标优化问题转化成为多重单目标优化问题的方法称为多重优化法。 （1）多重优化方法的基本思想

①根据多目标优化问题目标函数的性质，确定目标函数优化对象和优化次序。

②建立多重优化数学模型 第一重优化：

minfi1(x1,x2,,xn) 其中fi1为f1,f2,,fs中的某一函数 gi(x1,x2,,xn)0 求解得解集为D1 第二重优化：

minfi2(x1,x2,,xn) 其中fi2为f1,f2,,fs中的某一函数 (x1,x2,,xn)D1 求解得解集为D2 依次类推，进行s重优化 第s重优化：

minfi(x1,x2,,xn) 其中fis为f1,f2,,fs中的某一函数 (x1,x2,,xn)Ds1

求解得解集为Ds，即为多重优化问题的最优解集。 ③原多目标优化问题的最优解集或条件最优解集为Ds。

i1,2,,m

值得特别注意的是，我们不一定对所有目标函数进行多重优化，也可以根据需要只选取某几个目标函数进行多重优化，甚至只选取某一个目标函数进行优化。

（2）多重优化问题最优解的性质

多重优化问题的最优解与原多目标最优化问题的最优解也有着密切的内在关系。下面的定理揭示了两者之间的相互关系。

定理2：设原多目标最优化问题的最优解存在，则多重优化问题 第一重优化：

minfi1(x1,x2,,xn) 其中fi1为f1,f2,,fs中的某一函数 gi(x1,x2,,xn)0 解集为D1 第二重优化：

minfi2(x1,x2,,xn) 其中fi2为f1,f2,,fs中的某一函数 (x1,x2,,xn)D1 解集为D2 依次类推 第s重优化：

minfi(x1,x2,,xn) 其中fis为f1,f2,,fs中的某一函数 (x1,x2,,xn)Ds1 解集为Ds

的最优解必存在，且为原多目标最优化问题的最优解。

定理的证明留给读者自己练习。 例3：求解多目标优化问题

x(y)和max(y2x) max

i1,2,,m

xy1

s.t.

x0,y0

解：问题涉及两个目标函数，可应用多重优化方法求解。 （1）求解第一重优化：max(xy)

xy1

s.t.

x0,y0

的解集为D{(x,y)|xy1,x0,y0}，此时max(xy)1

（2）求解第二重优化：max(y2x)

xy1

s.t.

x0,y0

得解为x0,y1，此时max(y2x)1。

（3）易知原问题最优解存在（可以通过作图验证），所以最优解为x0,y1， 此时max(xy)1，max(y2x)1。

5．4 目标关联函数方法

在多目标最优化问题数学模型中，如果我们只是选定某一个目标函数（称为主目标）做为目标，而固定其余目标函数（称为次目标）在允许取值范围内为常数，则得到下列单目标优化数学模型：

minfi1(x1,x2,,xn) 其中fi1为f1,f2,,fs中的某一函数 fik(x1,x2,,xn)aik

gi(x1,x2,,xn)0

k2,3,,s，其中i1,i2,,is为1,2,,s的某排列 i1,2,,m

如果上述问题有解，则minfi1(x1,x2,,xn)与其余目标函数的取值有关。 目标关联函数方法的基本思想就是：固定某些目标函数的取值，求关于另一部分目标函数的最优解的方法。 为了讨论方便，我们以双目标优化问题为例来说明目标关联函数方法的基本思想。

双目标优化数学模型：

minf1(x1,x2,,xn) minf2(x1,x2,,xn)

gi(x1,x2,,xn)0（1）目标关联函数定义

目标关联函数定义：选取目标函数minf1(x1,x2,,xn)作为主目标，

i1,2,,m

minf2(x1,x2,,xn)作为次目标，固定f2(x1,x2,,xn)t，则得到单目标优化数学模型：

minf1(x1,x2,,xn) f2(x1,x2,,xn)t

gi(x1,x2,,xn)0

i1,2,,m

记最优值minf1(x1,x2,,xn)为F，则F为t的函数，即FF(t)，称此函数为第一个目标关于第二个目标的目标关联函数。也称为主目标关于次目标的目标关联函数。

类似地，我们可以定义第二个目标关于第一个目标的目标关联函数。 （2）目标关联函数的求解

对不同的t值，解数学模型：

minf1(x1,x2,,xn) f2(x1,x2,,xn)t

gi(x1,x2,,xn)0

i1,2,,m

得到目标关联函数FF(t)，为第一目标关于第二目标的关联函数。

注：关于t的取值范围，在可行解集上minf2(x1,x2,,xn)tmaxf2(x1,x2,,xn) （3）目标关联函数的性质

性质1：设第一目标关于第二目标的关联函数为FF(t)，如果原双目标优化问

题最优解存在，则必在tminf2(x1,x2,,xn)所对应的点取得。

性质2：如果目标关联函数FF(t)在tminf2(x1,x2,,xn)处不取得最小值，

则原双目标优化问题不存在最优解。

性质3：对于固定的t值，目标关联函数FF(t)所对应取值点为原双目标优化 问题在固定第二目标的条件下的条件最优解。

上述三条性质比较简单，证明都不难，读者自己练习完成。 （4）优劣解的概念

目标关联函数还具有许多很好的性质，譬如单调函数的性质等等。当原双目标优化问题不存在最优解时，应用目标关联函数选取条件最优解最有效。为了对条件最优解有更深入的了解，下面我们引入优劣解的概念。

优劣解的概念：设X*和Y*为可行解，如果满足下列条件之一

1）f1(X*)f1(Y*)，f2(X*)f2(Y*)； 2）f1(X*)f1(Y*)，f2(X*)f2(Y*)； 3）f1(X*)f1(Y*)，f2(X*)f2(Y*)；

则称X*是比Y*优的解。

性质4：任意可行解，要么对应目标关联函数一取值点对应的可行解；要么总存

在某目标关联函数一取值点的可行解优于该可行解。

证明：以双目标最优化问题为例证明。

设X*为任意一可行解，记f2(X*)t，目标函数f1关于目标函数f2的目标关联函数为FF(t)；

根据目标关联函数的定义 f1(X*)F(t)。 设目标关联函数在点t处对应的可行解为Y*， 则f1(X*)f1(Y*)，f2(X*)f2(Y*)

所以，要么X*是比Y*劣的解，

要么X*对应目标关联函数一取值点对应的可行解。

根据性质4，我们求双目标优化问题的最优解或条件最优解，只需要求出它的两个目标关联函数，再根据目标关联函数求解即可。 （5） 条件最优解的确定

一般来说，如果多目标优化问题存在最优解，我们就没有必要应用目标关联函数法求解，只需要应用单目标优化法或多重目标优化法。如果多目标优化问题不存在最优解，那末我们就可以应用目标关联函数法求其条件最优解。

为什么要求条件最优解呢？这是因为多目标优化问题现实生活中大量存在，需要解决，而它们往往又都不存在最优解，因而寻求在一定条件下的最优解。例如，“企业如何确定生产方案，使得资源消耗最少，而效益最大”问题、“投资公司如何确定投资方案，使得风险最少，而效益最大”问题、“公交公司如何确定公交车运营方案，使得乘客满意度最大，而效益最好”问题等等，都是多目标优化问题。显然，这些问题都没有最优解。因此，我们只能够寻求它们的条件最优解。由目标关联函数确定条件最优解的方法分为直接法和分析法。

①直接法：给定次目标函数的取值，直接求解关于主目标的对应单目标最优化问题，得到条件最优解。

②分析法：首先求出目标关联函数；然后通过分析目标关联函数的性质或图形，选取条件最优解。

5．5 投资风险问题

某投资公司有一定数量的资金进行投资，现有投资方向S1,S2,,Sn可供选择。投资选择和资金分配的原则为：总体收益尽可能大，总体风险尽可能小。 已知：投资收益率ri

Ri

，其中Ri为投资Si的收益，Xi为投资资金；投资风险Xi

nn

Qi

率qi，其中Qi为投资Si的风险；定义投资总体风险QQiqiXi。

Xii1i1

投资效益与风险问题建模

一、问题分析 （—）问题的性质

本问题是一个投资“关于效益与风险的双目标”最优化决策问题。必须在“总体收益尽可能大，总体风险尽可能小”的原则下确定投资方向，即确定每个投资方向的投资资金。 （二）问题的主要因素

（1）每个投资方向Si的投资资金Xi；

（2）每个投资方向Si投资的收益率ri与收益Ri； （3）每个投资方向Si投资的风险率qi与风险Qi； （4）投资总收益R； （5）投资总体风险Q。

关键因素为投资总收益与投资总体风险。 （三）解决问题的难点

从本实际问题出发，投资的收益与风险是一对矛盾。一般来说，投资的收益越大，风险就会越大。因此，根本不存在投资的收益最大，同时风险又最小的投资方案。

怎样协调收益与风险之间的矛盾？这是解决该问题的难点。 （四）目标函数的确定 根据“总体收益尽可能大，总体风险尽可能小”的原则，建立数学模型时，我们的目标函数必须以总体收益和总体风险为基础。 （1）总体收益函数RRiriXi

i1n

i1n

n

n

（2）总体风险函数QQiqiXi

i1

i1

（五）数学建模的思路

（1）思路1——建立双目标优化模型

以“总体收益函数最大，总体风险函数最小”为目标函数，建立双目标最优化模型。

由于题目所给数据反应的“收益最大和风险最小”是矛盾的，因此，此模型无最优解。但模型反应了投资的追求，是建立其他模型的基础。 （2）思路2——建立单目标优化模型

引入新的函数，从一定程度上反应“收益最大和风险最小”的目标，将此函数做为目标函数，建立单目标优化模型。 新的目标函数应该满足：收益越大，函数值越大；风险越小，函数值越大。 （3）思路3——建立多重优化模型

对于投资者来说，有的重视的是收益，而将风险做为第二考虑；有的则重视的是风险，而将收益做为第二考虑。

根据这种投资者的两种特点，我们可以分别建立两种模型。一是建立“先优化收益，再优化风险”的重视收益二重优化模型；二是建立“先优化风险，再优化收益”的重视风险二重优化模型。

（4）思路4——建立目标关联函数模型 对于有些投资者来说，选择投资方案的原则是：在固定总体风险的前提下，选择收益最大的投资方案。此时，最大收益实际上是总体风险的函数，求得该函数和该函数每一点处的投资方案，即为在固定总体风险的条件下，最佳的投资方案。

同理，对于有些投资者来说，选择投资方案的原则如果是：在固定总体收益的前提下，选择风险最小的投资方案。此时，最小风险实际上是总体收益的函数，求得该函数和该函数每一点处的投资方案，即为在固定总体收益的条件下，最佳的投资方案。

上述两函数揭示了收益和风险的内在关系，我们分别称为收益关于风险的目标关联函数和风险关于收益的目标关联函数，统称为目标关联函数。 二、模型建立 （一）建模准备

（1）总体收益函数和总体风险函数 总体收益函数RRiriXi

i1n

i1n

n

n

总体风险函数QQiqiXi

i1

i1

（2）约束条件

设总投资资金为1个单位，投资Si的投资资金为Xi个单位， 则有：

n



RriXi



i1

nQqiXi

 i1

n

Xi1i1

Xi0,i1,2,,n

（二）双目标优化模型

根据题意，我们以“总体收益函数最大，总体风险函数最小”为目标函数，建立双目标最优化模型。

模型1——双目标最优化模型：

maxR

minQ

n



RriXi



i1

nQqiXi

i1

n

Xi1i1

Xi0,i1,2,,n

定理：对于题目所给数据，上述模型无最优解。

证明：显然，投资方案X1X2X3X4X50,X61的收益最大，R0.6；

此时，投资风险也是最大，Q0.6。

所以，模型无最优解。

由于模型无最优解，如何根据不同投资者的需要选择投资方案？成为解决问题的关键。

（三）单目标优化模型

为了满足不同投资者的需要，我们来建立一个调和收益和风险矛盾的模型。为此，引入新的函数，反应“收益最大和风险最小”的目标，将此函数做为目标函数，建立单目标优化模型。

（1）收益风险权重函数 新的目标函数应该满足：收益越大，函数值越大；风险越小，函数值越大。我们定义一个常用的线性函数作为新的目标函数。 定义1：收益风险权重函数 WR(1)Q

其中0为权重系数，它表示了投资者对收益和风险的重视程度。越大越重视收益，越小越重视风险。

(2)模型2——线性优化模型：

maxWR(1)Q

n



RriXi



i1

nQqiXi

i1

n

Xi1i1

Xi0,i1,2,,n

该模型可以根据投资者的不同类型，确定需要的投资方案。下面我们对投资者进行简单的分类。

注重收益忽略风险型：只注重收益，不考虑风险，此时，1。

1

收益风险注重均衡型：均衡注重收益和风险，此时，。

2

注重风险忽略收益型：只注重风险，不考虑收益。此时，0。

当然，我们可以将投资者分成更多种类型，并确定权重系数，再求解模型，从而得到该类型投资者的最佳投资方案。 （四）多重优化模型

（1）由问题分析中我们知道，有的投资者，首先重视的是收益，其次再是风险；还有些投资者则首先重视的是风险，而将收益做为第二考虑。

根据投资者的两种特点，我们可以分别建立两种模型。一是建立“先优化收益，再优化风险”的重视收益二重优化模型；二是建立“先优化风险，再优化收益”的重视风险二重优化模型。

（2）模型3——收益第一风险第二模型： 第一重优化 maxR

n



RriXi



i1

nQqiXi

i1

n

Xi1i1

Xi0,i1,2,,n

设解集为D1 第二重优化

Q min

XD1

（3）模型4——风险第一收益第二模型：

minQ

n

RriXi



i1

nQqiXi

i1

n

Xi1i1

Xi0,i1,2,,n

设解集为D1

第二重优化

R max

XD1

上述二重优化模型，提供了两类投资者的最优投资方案。

（五）目标关联函数模型

（1）根据投资选择方案的原则“在固定总体风险的前提下，选择收益最大的投资方案”；建立收益关于风险的关联函数模型；求出该函数每一点处的最佳投资方案。

模型5——固定风险模型 maxR

n



RriXi



i1

nQqiXit

其中minQtmaxQ i1

n

Xi1i1

Xi0,i1,2,,n

maxRR(t)

（2）根据投资选择方案的原则“在固定总体收益的前提下，选择风险最小的投资方案”；建立风险关于收益的关联函数模型；求出该函数每一点处的最佳投资方案。

模型6——固定收益模型

minQ

n



RriXit

i1

nQqiXi

其中minRtmaxR i1

n

Xi1i1

Xi0,i1,2,,n

minQQ(t)

模型5和模型6从理论上讲提供了任意类型投资者的最佳投资方案。 三、模型求解和结果 （一）模型1无最优解。

第一重优化结果

R0.6,Q0.60.1t,X(0,0,0,0,t,1t)，其中0t1。 第二重优化结果

R0.6,Q0.5,X(0,0,0,0,1,0)。

（四）模型4：模型为线性规划模型，可以直接求解。

第一重优化结果

minQ0.3,R0.30.1t,X(t,1t,0,0,0,0)，其中0t1。 第二重优化结果

Q0.3,R0.3,X(0,1,0,0,0,0)。

（五）模型5：模型为线性规划模型，可以直接求解或应用数学计算软件求解。

对于0.3t0.6分别求解得 收益关于风险的目标关联函数

1.5t0.150.3t0.5

R(t)

0.60.5t0.6

固定风险的条件下，相应的最佳相应的投资方案为

(0,2.55t,0,0,5t1.5,0)0.3t0.5

X

(0,0,0,0,610t,10t5)0.5t0.6

（六）模型6：模型为线性规划模型

对于0.2t0.6分别求解得 风险关于收益的目标关联函数

0.320.2t0.3

Q(t)

0.1t0.3t0.63

固定收益的条件下，相应的最佳投资方案为

(310t,10t2,0,0,0,0)0.2t0.3

X1010

(0,2t,0,0,t1,0)0.3t0.633

练 习 题

22

（1）求函数f(x1,x2,x3)3x124x2x32x1x23x2x34x15x22的极值。

（2）将2008拆成若干个正整数的和，使得它们的乘积最大。 （3）证明周长一定的平面曲线围成面积最大的是圆周曲线。 （4）用穷举法求解

minfx12x23x3x4

x12x23x3152xx5x20123s.t.

x2xxx102341xi0,i1,2,3,4

（5）应用单纯形法求解线性规划问题 maxfx1x2x33x5

x2x3x42x56x2x2x524s.t.1

2xx3xx84562xi0,i1,2,3,4,5,6

（6）应用分枝定界法，求解整数线性规划问题

maxz3x14x2

2x15x215

s.t.2x12x25。

x0,x0为整数

21

（7）投资风险问题

某投资公司有一定数量的资金进行投资，现有投资方向S1,S2,,Sn可供选择。投资选择和资金分配的原则为：总体收益尽可能大，总体风险尽可能小。 已知：投资收益率ri

Ri

，其中Ri为投资Si的收益，Xi为投资资金；投资风险Xi

nn

Qi

率qi，其中Qi为投资Si的风险；定义投资总体风险QQiqiXi。

Xii1i1

（8）在上题中将投资总体风险定义为Qmax{q1X1,,qnXn}，试建立投资风险问题的数学模型，并根据上题数据计算选择投资方向。

参考资料

1. 运筹学基础 何坚勇 编著 清华大学出版社 2000年7月 2. 数学规划的原理何方法3. 最优化与最优化控制 俞玉森 蔡宣三 主编 华中理工大学出版社 编著 清华大学出版社 年10月 年1月

1993 1983