一、最优化问题与预备知识

1. 预备知识

范数

向量范数满足如下性质:

常见向量范数:

这些向量范数之间的关系:.

向量范数的等价性:设是定义在上的两种向量范数,那么总存在两个正数使得对任意都有.

矩阵范数满足如下性质:

常见矩阵范数:

范数的相容性:

常用范数不等式:

函数可微性

连续:若给定函数,函数上连续在每一点连续;记作.

连续可微:若为开集且在每一点处,上连续可微每一个偏导数)存在且连续;记作.

二次连续可微:若在每一点处,上二次连续可微每一个二阶偏导数)存在且连续;记作.

梯度、海塞阵(Hesse)、Jacobi阵

梯度:设是一阶连续可微的,则处的一阶偏导数(即处的梯度)为.

海塞阵(Hesse):设是二阶连续可微的,则处的二阶导数(即处的Hesse阵)为.(由于二阶连续可微,所以混合偏导与顺序无关,该矩阵是对称的)

比如:设对称,二次函数,其中,则.

多变量向量值函数的Jacobi阵:设多变量向量值函数处连续可微,则处的一阶导数为,称为处的Jacobi阵。

比如:设多变量向量值函数,其中,则Jacobi阵为.

例1:求函数的梯度与Hesse阵

解:方法一,直接求导写在对应位置上:.

方法二:.

例2:求向量值函数的Jacobi阵

解:.

多变量实值函数的中值定理、泰勒公式

定理:设,且,如果是一阶连续可微的,则

(1)存在使得,其中.

(2)处有一阶Taylor公式:.

如果上是二阶连续可微的,则

(3)存在使得,其中.

(4)处有二阶Taylor公式:.

2. 凸集

凸集:给定非空集合,如果,都有,那么称中的一个凸集,如果凸集为开集,则称为开凸集;若凸集为闭集,则称为闭凸集。并且我们规定,空集为凸集。

如果给定,那么就是一条线,因此有凸集的另外一种定义:为凸集中任意两点的连线段仍然属于

易证,若,下面的集合都是凸集

  1. 单点集、.
  2. 超平面:.
  3. 闭半空间:.
  4. 开半空间:.
  5. 超球:,其中.

命题:假设为凸集、),则下列集合均为凸集

定理:非空集合为凸集及任意满足的非负实数为正整数)都有.

证明:根据凸集定义可得定理的充分性,下面用归纳法证明必要性

时由定义知结论成立;假设当时结论成立,下面证明时结论也成立:

,则,由知,归纳假设,于是上式可看作,根据时结论成立知,,即,由归纳原理知结论成立。

集合的(严格)分离:设为两个非空凸集,如果存在非零向量和实数,使得

(1)对任意都有,则称超平面分离集合.

(2)对任意都有,则称超平面严格分离集合.

点与凸集分离定理:设中的非空闭凸集,,则存在中的超平面严格分离集合.

3. 凸函数

Farkas引理:设,则不等式组有且仅有一组有解(即(1)和(2)不能同时有解)。

证明:假设(2)有解,即使得,若(1)也有解则使得,此时

假设(2)无解,记,则为非空闭凸集,且,根据点与凸集分离定理知,存在使得对所有,并且由,由的任意性知,,从而为(1)的解。

定理:设是两个非负整数,,则等式与不等式组无解存在实数)和非负实数)使得.

凸函数

凸函数的定义:设为非空凸集,给定函数

(1)若对任意的及任意的,有,则称函数为凸集上的凸函数

凸组合的函数小于等于的函数的凸组合叫凸函数。

(2)若对任意的,及任意的,有,则称函数为凸集上的严格凸函数

(3)若存在常数,使得对任意的及任意的,有,则称函数为凸集上的强凸函数(或一致凸函数)。

对应凹函数的定义:

(1)-凹函数。

(2)-严格凹函数。

(3)-强凹函数。

例如,给定向量,则线性函数既是凸函数又是凹函数,因为此时.

凸函数的性质(设是凸集):

一阶判别定理(凸函数的判别准则1):设函数在凸集上可微,则:

(1)上为凸函数对任意的,有.

(2)上为严格凸函数对任意不同的,有.

第一条的证明:

必要性:由于上的凸函数,则,有,整理得,由一阶泰勒展开得,所以,令.

充分性,有,于是,两式分别乘以再相加,得,即,因此上的凸函数。

第二条的证明:

必要性,令此时,根据第一条的必要性证明可以得到,并且根据凸函数定义有,所以,整理得.

充分性:证明和第一条类似。

二阶判别定理(凸函数的判别准则2):设在开凸集内函数二阶可微,则:

(1)内为凸函数对任意的半正定.

(2)若正定,则内为严格凸函数。

第一条的证明:

必要性,由是开集知,存在使得,由一阶判别定理有,由Taylor展开式得,所以,令,由的任意性得半正定。

充分性对称半正定,对做代拉格朗日余项的Taylor展开,并由于,其中,因此上的凸函数。

强凸函数的判别定理:设二次连续可微,则:是强凸函数一致正定。(注:一致正定即存在对所有都有,也就是的最小特征值是以为下界的)

4. 凸规划

凸规划问题:设为凸集,为凸函数,则称为凸规划问题。

凸规划的性质

第一点的证明(反证法):假设是凸规划问题的局部最优解但非全局最优解,则至少存在一个使得,由函数为凸函数、为凸集得,对任意,当时,,因此在充分接近时,,这与是局部最优解矛盾。

第二点的证明:由空集与单元素集为凸集,不妨设凸规划问题的最优解集至少含两个元素,假设,则(因为都是最优解,所以),由于是最优值,根据定义它是最小值,因此小于等于只能取等于号,即.

第三点的证明(反证法):假设全局最优解不唯一,则,显然,这与是全局最优解矛盾,所以凸规划问题有唯一最优解。

5. 线搜索迭代算法

线搜索算法的一般框架

基本思路:从某个点出发,按照某种规则产生一个迭代点序列,直到算法终止。

算法分类:

(1)按照迭代点是否可行,分为 ①可行算法-所有迭代点都是可行点 ②不可行算法-迭代点中至少存在一个不可行点

(2)按照目标函数值是否下降分为 ①单调下降算法 ②非单调下降算法

一般框架:

步1:选择一个初始点,令.

步2:判断当前的迭代点是否满足终止条件.

步3:从当前点出发,选择沿什么方向进行迭代(记迭代方向为)以及沿该方向走多远(记迭代步长为),确定下一个迭代点.

步4:令,转步2.

注1:关于终止规则

最理想的终止规则:.

常用的终止规则

(1) (2) (3) (4) (5)

注2:迭代方向

迭代方向定义:在点处,对于向量,若存在使得对任意都有,则称为函数处的一个下降方向。

命题:假设函数一阶连续可微,那么处的下降方向当且仅当.

证明:由Taylor展开式得,所以,从而结论成立。

注3:可行方向

可行方向定义:给定非空集合和点,对于向量,若存在使得对任意都有,则称处关于的一个可行方向。

可行下降方向定义:如果为点处的可行下降方向,那么存在使得,且.

注4:迭代步长的选取

1、精确一维线搜索:选取.

2、非精确一维线搜索

(1)Goldstein型线搜索(1965):选取使得,其中.

(2)Armijo型线搜索(1966):选取使得为满足下式的最小非负整数:,其中.

(3)Wolfe型线搜索:选取使得,其中.

3、非单调一维线搜索

(1)Grippo-Lampariello-Lucidi非单调线搜索(1986):寻找步长使得是满足下式的最小非负整数:,其中是一个正整数且为某一正整数),是一个给定的小实数,.

注:当时,即为单调的Armijo型线搜索。

(2)Zhang-Hager非单调线搜索(2004):寻找步长使得,其中按如下方式选取:,这里,且.

注:的凸组合,含有步迭代之前所有迭代点函数值的信息;的选取控制着”非单调性”的度,如果,则即为单调的Wolfe搜索。

(3)Hu-Huang-Lu非单调线搜索(2010):寻找步长使得,其中按如下方式选取:,且,其中,这里,若是Lipschitz连续的,则令,其中为Lipschitz常数;否则,令.

注一个特例:若,则;否则,选择。因此,每一步要么使用单调线搜索,要么使用非单调线搜索,是一种混合线搜索方法。

算法收敛性

1、适定性(well-defined):如果算法的每一步是适定的,则这个算法是适定的。

2、算法是收敛的:如果算法是有限终止的或所产生迭代点列的每个聚点是优化问题的最优解,则称该算法是收敛的。

3、全局收敛(globally convergent):局部收敛(locally convergent):如果对于任意的初始点算法是收敛的,则称该算法是全局收敛的;如果只有初始点充分靠近最优解时,算法是收敛的,则称该算法是局部收敛的。

4、收敛率(rate of convergence):假设算法生产无穷点列,且算法收敛到最优解,不妨设收敛到,即,则:

(1)全局Q-线性收敛:如果算法初始迭代点的选取无关于最优解的信息,且存在使得,则称该算法是全局Q-线性收敛的。

(2)局部Q-收敛率:如果存在使得,则称该算法是局部Q-阶收敛的。

注:特别地,

二、线性规划问题

1. 线性规划问题的数学模型

例1:某制药厂生产甲、乙两种药品,生产这两种药品都有消耗某种原料,生产每吨药品所需的原料量及所占设备时间见下表

项目消耗量 每吨产品的消耗 每周资源总量
原料/kg 30 20 160
设备/台班 5 1 15

该厂每周所能得到的原料量为160kg,每周设备最多能开15个台班,且根据市场需求,甲种产品每周产量不应超过4t。已知该厂生产每吨甲、乙两种产品的利润分别为5万元和2万元,问该厂应如何安排两种产品的产量才能使每周获得的利润最大?

解:设该厂每周安排生产甲、乙两种药品的产量分别为,则需要满足不等式条件,并且该问题变为.

例2:某铁器加工厂需要制作100套钢架,每套要用长分别为2.9m、2.1m和1.5m的圆钢各一根,已知原料长为7.4m。问应如何下料,可使用材料最省?

解:通过分析,可知有如下几种切割方式

长度(数量)方案编号
2.9m 1 2 0 1 0
2.1m 0 0 2 2 1
1.5m 3 1 2 0 3
料头/m 0 0.1 0.2 0.3 0.8

假设按第种方案下料的原料根数为),则求.

线性规划问题的数学模型:像上面那样,每个问题都有一组决策变量,每个问题都有这些决策变量需要满足的一组约束条件(一般为线性等式或不等式),每个问题都有一个关于决策变量的线性目标函数并且该函数要在满足约束条件的条件下实现最大化或最小化,那么我们将约束条件和目标函数都是决策变量的线性函数的规划问题称为线性规划

2. 图解法(两个决策变量)

对于只有两个决策变量的线性规划问题,一般采用图解法

例:求解.

解:以为坐标轴建立直角坐标系,分别作出约束条件所对应的半平面(图中的蓝色区域就是可行域

两个决策变量的线性规划问题-例

求出的梯度,将任一等值线沿的方向平移,直到将离开还未离开可行域时的一根等值线为,即为过图中点的等值线,故为唯一的最优解。

关于可行域与解的一些结论

3. 线性规划问题的标准化

标准的线性规划问题要求满足:

线性规划问题的矩阵形式,其中.

线性规划问题的向量形式,其中同矩阵形式,而,即.

如何将线性规划问题改写为标准形式

(1)若目标函数为最小化,则作函数,对实现最大化,即.

(2)若约束条件是小于等于型,则在该约束不等式左边加上一个松弛变量,将不等式改为等式.

比如:.

(3)若约束条件是大于等于型,则在该约束不等式左边减去一个剩余变量,将不等式改为等式。

比如:.

(4)若某个约束方程右端项,则在约束方程两端乘以,不等式改变方向,然后再将不等式转化为等式.

(5)若决策变量无非负要求,则可令两个新变量,作,在原有的数学模型中,均用来替代,而在非负约束中,增加.

即一般的线性规划问题都要求决策变量,如果实际问题中可以小于零,就要转化为两个非负的新的变量相减。

例:将下列线性规划问题化为标准形式:

解:令,再令,并在第一个约束条件中加入松弛变量,在第二个约束条件左边减去剩余变量,第三个约束条件两边同乘,得.

4.线性规划问题的解

可行解、最优解:若数学模型为,其中,我们把凡是满足的解称为线性规划问题的可行解,同时满足的可行解为最优解

基矩阵、基向量:设线性规划问题约束方程组的系数矩阵的秩为,则中某列组成的任一阶可逆阵称为该规划问题的基矩阵,简称,若把基记为,则称为基中的一个基向量,而中其余个列向量称为非基向量

基变量:当确定了的一个基后,与基向量相对应的决策变量称为关于基的一个基变量,而与非基向量对应的决策变量称为非基变量

基本解、基本可行解:若确定了基及其对应的基变量,我们称非基变量取值均为零且满足约束条件的一个解,为关于基的一个基本解;如果该基本解同时满足非负条件,则称基本解为基本可行解

基本解的确定:设为一个基矩阵,为对应的基变量,为非基矩阵,为对应的非基变量,那么可以改写为,因此,如果令非基变量,则基变量,故就是关于基的一个基本解。

例:求的基本解和基本可行解

解:化为标准形式,于是,设是一个基,且是相应的基变量,而是非基变量,令,算出基本解为,又因为,那么也是基本可行解。

另外,如果选取,得到,此时也是基本可行解。其他选法类似。

5. 线性规划问题基本理论

引入:通过两个变量的线性规划问题的图解法,可以得到如下结论:

下面考虑对于多变量线性规划问题,讨论以上结论是否仍然成立。

凸集:设集合,若对及每一个数,都有成立,则称为凸集。

从直观上看,没有凹入部分,或没有空洞的是凸集。若集合中任意两点连线上的每一点仍在中,则为凸集。

凸组合:设维欧式空间中的个点,若存在实数,其中,有,则称的一个凸组合。

严格凸组合:若存在实数,其中,有,则称的一个严格凸组合。

极点:设是凸集,,若不能表示为中任意两个不同点的一个严格凸组合,则称的一个极点。

中的一个极点,且有,则必有.

五边形的每个顶点都是极点,而圆域边界上任意一点都是极点。

定理:若线性规划问题存在可行域,则可行域为一凸集。

定理:线性规划问题的可行解为基本可行解当且仅当中正分量所对应的系数列向量线性无关。

定理:线性规划问题的每个基本可行解对应于可行域的一个极点。

证明:设基本可行解的前个分量为基变量,即,如果不是可行域中的极点,则一定可以表示为可行域中两个不同的点的一个严格凸组合,即,若记,则有,故),根据基本可行解的非负条件知,,因为是可行解,有,两式相减得,由于,所以至少有一个,其中,也就是说线性相关,这与是基本可行解矛盾,故假设不成立。

定理:有界凸集上任一点都可以表示为的极点的凸组合。

定理:对线性规划问题的标准形式,若可行域有界,且存在最优解,则目标函数必可在其可行域的某个顶点达到最优值。

定理:对于线性规划问题的标准形式,若存在可行解,则必存在基本可行解。其中约束矩阵为秩是型矩阵

通过以上分析,可得到以下结论:

于是,我们就可以用代数方法寻找最优解:求最优解先找基本可行解,而基本可行解的个数不会超过基本解的个数

6.单纯形法

单纯形法概述

引入:前面我们已经知道了要求线性规划问题的最优解可以先找基本可行解再逐个比较,但是往往基本可行解的个数会随着增大而迅速增大,所以这种方法往往行不通。于是我们设想如果可以从某一基本可行解(初始基本可行解)出发,每次寻求比上次更“好”的基本可行解,这样就大大减少了计算量。

要使用这种逐步改善的求解方法,要解决如下几个问题:(1)如何得到一个初始基本解 (2)如何判别是否达到了最优解 (3)若当前不是最优解,如何寻找一个更好的基本可行解

下面利用例题来说明单纯性法的思路:

例:.

解: 将问题标准化得,,写出约束矩阵为

步骤一:选取一个可逆的子阵作为初始基矩阵,比如,则相应的基变量为,于是初始基本可行解,带入计算得初始基本可行解为,相应的目标函数值为

步骤二:判断当前解是否为最优解。将基变量用非基变量表示,用非基变量表示目标函数,从数学角度看,目标函数中非基变量的系数为正数,故若让非基变量(或)的取值从零增加,相应的目标函数值也将增加,因此就有可能找到一个新的基本可行解,使目标函数值比的更“好”。因此,这个不是最优解。

步骤三:解的改进。在中,前的系数必比前的系数大,即每增加一个单位对的贡献比大,故让的取值从零变成正值。这样,从非基变量转为基变量,我们称之为进基变量。但对于本例,任意一个基本可行解中只能有3个基变量,因此必须从原有的基变量中选择一个离开基变量,我们称之为离基变量(或出基变量),为了选取合适的离基变量,观察,此时我们已经选取了为进基变量,而仍为非基变量取值仍为0,我们选取在从零增加直到使的取值减少到零时停止,第一个变为零的基变量为离基变量。显然,因此为离基变量(即令),将代入前面等式,可得到新的基本可行解

经过以上三步,我们得到了一个新的基本可行解,然后再重复上述步骤。(1)算出新的基本可行解后再重新写出基矩阵、基变量和目标函数:相应的基矩阵为,基变量为,非基变量为,对应的目标函数值是。(2)判断当前解是否为最优解:将基变量用非基变量表示,用非基变量表示目标函数,此时目标函数中的系数仍为正数,于是选为进基变量,迭代到一个新的基本可行解,就有可能使目标函数值再增加,因此仍不时最优解。(3)解的改进:在基变量用非基变量表示的式子中,仍为非基变量取值为0,在从零增加的过程中,首先到达零,故取,则

经过两次迭代,可得到新的基本可行解,再次判断此解是否为最优解:将基变量用非基变量表示,用非基变量表示目标函数,这时中任意一个从零开始增加,都会使减少,因此当前解就是最优解了,此时最优值为

通过上面例子,总结出单纯性法的求解步骤:

(1)在线性规划问题的标准形式中,设法在约束矩阵中构造出一个阶单位矩阵作为初始可行基,获得一个初始基本可行解;

(2)判断当前基本可行解是否为最优解。判断方法为:求出用非基变量表示基变量及目标函数的表示式,称为线性规划问题的典式(或称为规范式),在目标函数的典式中,若至少有一个非基变量前的系数为正数,则当前解不是最优解;而如果所有非基变量的系数均为非正数,则当前解就是最优解。因此我们把目标函数的典式中非基变量前的系数称为检验数,对于最大化问题,当所有的检验数时,当前解为最优解;对于最小化问题,当所有的检验数时,当前解为最优解;

个人理解:随着学习的深入,最优解的意义不同。比如学到对偶单纯形法之后,最大化问题的所有检验数只能叫做正则解,而不能再叫做最优解,因为后面的最优解还要求,这样才能利用互补松弛性定理写出对偶问题的解,但是如果不考虑对偶问题的话,这里管检验数的解叫最优解也没错,只是学的越后面,对最优解的要求变得越多。

(3)若当前解不是最优解,则要进行基变换迭代到下一个基本可行解。变换方式为:首先从当前解的非基变量中选一个作进基变量(选择的原则一般为目标函数的典式中,最大的正检验数所属的非基变量作为进基变量);再从当前解的基变量中选一个作为离基变量(选择的方法是在用非基变量表示基变量的典式中,除进基变量外,让其余非基变量取值为零,再按最小比值准则确定离基变量)。选好后再继续重复上面步骤,直至找到最优解。

单纯形法的矩阵描述

考虑线性规划问题的标准模型,其中,在下面的讨论中,假设:(1)此线性规划问题的可行域非空 (2)所有的基本可行解不退化。

步骤一:将分解为,其中为基矩阵,为非基矩阵,相应地,为基变量,为非基变量,那么解向量可写为,根据前面的结论知,当前的基本可行解,相应地,将价值系数向量也分为两块

步骤二:判断当前解是否为最优解,即求检验数。①先用非基变量表示基变量,由,又因为可逆,则有。②再用非基变量表示目标函数,,故对于每个非基变量,其对应的检验数为,其中在约束矩阵中对应的列向量,而基变量的检验数都为零;

步骤三:若当前解不是最优解,则要进行基变换迭代到下一个基本可行解。①若某个非基变量的检验数,则当前解不是最优解,而且越大,目标函数值增加越多,选择进基变量使。②选择离基变量,因为,除以外,其他的非基变量取值仍为零,所以,其中都为维向量,于是,由最小比值准则知,,故当前的第个基标量为离基变量。于是新的基矩阵为

定理:根据上面分析,可以看出,对于最大化线性规划问题,若存在一个检验数,且,即,则线性规划问题有无界解(无最优解)。

定理:对于最大化线性规划问题,若所有非基变量的检验数,则当前解为最优解;对于最小化线性规划问题,若所有非基变量的检验数,则当前解为最优解。

例:用单纯形法求解.

解:将问题化为标准型得,写出系数矩阵

第一次迭代:步骤一:选择初始可行基,则,故基本可行解为,相应的目标函数值。步骤二:计算非基变量的检验数,对于非基变量,其检验数,同理,的检验数为。步骤三:由于都大于0,选取,其对应的非基变量为进基变量;为选取离基变量,先求出,利用最小比值准则,找出,其中,,故中的第三个分量为离基变量,相应的新的基矩阵为

第二次迭代:步骤一:新可行基的逆,则基变量,非基变量为,于是初始基本可行解为,相应的目标函数值。步骤二:计算非基变量的检验数,公式为,算出,同理。步骤三:,故对应的为进基变量;此时,找出,其中,故中的第二个分量为离基变量,相应的新的基矩阵为

第三次迭代:新可行基的逆为,则,故初始基本可行解为,目标函数值为。计算非基变量的检验数,同理,由前面定理知,所有非基变量的检验数,则当前解为最优解。

综上,最优解,最优值

单纯形表

考虑线性规划问题的标准模型,其中,假设为初始的可行基,为基变量,为非基变量,则,于是上述线性规划问题可以写成如下等价形式,,进一步化为(其中第二条用到了),该约束方程可以看作是以为变量的方程组,把其系数列成表格,得到单纯形表:

右端项
0 (单位阵)
-1 0

若假设为基变量,可设计如下单纯形表:

1 0 0
0 1 0
0 0 1
0 0 0
原表格

若按行看,为价值系数,为决策变量,中间的矩阵包含着一个阶方阵,该方阵对应着个基变量,而是检验行(其中基变量的检验数都是零);若按列看,是基变量的价值系数,是基变量,是基变量取值(因为),而最右边的这一列是最小比值列。

根据单纯形表,可以:

(1)检验当前基本可行解是否为最优解:若检验行所有的,则已获得最优解,停止计算,否则要进行下一次步计算。

(2)检验是否为无界解:在)中,若有一个,而在单纯形表中所在列的所有元素都,则该问题无最优解,停止计算,否则进行下一步计算。

(3)选择进基变量:由进基变量选择准则)(即在所有检验数为正的当中选取最大的检验数),选择进基变量,相应的列为进基向量,称表中所在列为主列

(4)选择离基变量:由离基变量的最小比值准则,则称第行为主行,与主行对应的基变量为离基变量。

(5)基变换:将可行基由,且将主列化为单位列向量,即

例:用单纯形表解下列问题,.

解:系数矩阵为

第一次迭代:步骤一,选取初始可行基,其中,故初始基本可行解为。步骤二,计算检验数,建立初始单纯形表

线性规划问题-单纯形法-单纯形表-例题-01

步骤三,选取检验数最大的5所在列的作为进基变量,此时所在列称为主列,再用列对应元素除以主列对应元素(根据最小比值准则知,主列为负的不用除),即可得到列(最小比值列),最小比值3所在的行对应,于是选取为离基变量,这时检验数5所在列与最小比值3所在行交叉处的元素5(用中括号括起来),称这个5为主元素

更新单纯形表:我们要将主元素5变为1,再把主元素所在列其他的元素变为0,这样主列才能变成单位向量。于是把主元素所在行所有元素都乘以(中间的大矩阵及列),把主元素变为1,同时把主元素适当倍数加到除主元素所在行以外的其他行(中间的大矩阵及列),就能把主元素所在列其他的元素变为0。按顺序写出新的基变量及其价值函数系数,再次计算、检验数和最小比值,于是得到了新的单纯形表如下

线性规划问题-单纯形法-单纯形表-例题-02

此时检验数仍然有大于零的数,所以当前解还不是最优解,再次重复上面步骤,得到新的单纯形表

线性规划问题-单纯形法-单纯形表-例题-03

此时所有检验数都,即当前解是最优解,

这种方法的好处是,每一次都令是单位阵,在计算检验数的过程中就不用反复计算,并且也不需要计算,直接用除以主列对应元素即可得到

线性规划问题解的数目

定理:在最大化问题中,若当前基本可行解的非基变量的检验数满足最优准则),且其中有一个非基变量的检验数,则该线性规划问题有无穷多个最优解。

证明:设为当前的基本可行解,),满足最优准则,故此时。不妨设为非基变量,且检验数,选为进基变量,则对应的数列有以下两种情况:

(1)若中至少有一个分量,则按最小比值准则选择离基变量,可由当前解迭代到下一个基本可行解,而对应的目标函数值为(因为其中的就是的检验数),因此也是最优解,由凸集的性质可知,连线上的任一点都是方程的可行解,且,因此有无穷多个最优解。

(2)若中所有分量,则不能运用最小比值准则,但仍然可以构造其他不同的最优解。把写成,令,其余,不难发现,必为一个可行解(但不是基本可行解),由于可取任意正值,则相应的目标函数值,故也是最优解,也就是说该问题有无穷多个最优解。

定理:对线性规划问题的某一个基本可行解,若第个非基变量的检验数,而对应的系数列向量(即单纯形表中所在列的各元素都小于等于零),则该线性规划问题没有最优解。

例:求下列问题的最优解,.

解:把问题标准为,列出初始单纯形表

线性规划问题-单纯形法-线性规划问题解的数目-01

这时当前解还不是最优解,经过计算,得到最优单纯形表为:

线性规划问题-单纯形法-线性规划问题解的数目-02

由于有一个非基变量的检验数为零(蓝色那一列),根据定理,该问题一定有无穷多个最优解。验证:选为进基变量,为离基变量,得到第二个最优单纯形表:

线性规划问题-单纯形法-线性规划问题解的数目-03

根据凸集的性质,这两个最优解连线上的任意一点都是最优解,即该问题有无穷多个最优解。

7. 大M法与两阶段法

人工变量及其处理方法:前面的单纯形法告诉我们,选取单位阵作为初始可行基可以很大程度地简化计算。为了便于计算及寻找计算方法上的规律性,希望在化线性规划为标准形式时,约束矩阵中含有一个阶单位阵作为初始可行基,这有以下几种情况:

比如,考虑线性规划,在每个约束方程左边加上一个人工变量)有,这样就让其中含有了一个阶单位矩阵,以为基变量,得初始基本可行解

加入人工变量后的数学模型与未加人工变量的数学模型一般不是等价的。因此,人工变量与松弛变量或剩余变量是不同的,松弛变量或剩余变量只是将不等式改写为等式,而改写前后,两个约束是等价的。虽然加入人工变量后的新问题与原问题不等价,但它们有如下关系:

当以新问题的作为初始基本可行解进行迭代时,要怎样才能将所有的人工变量从基变量中“赶”出去,通常有大M法两阶段法两种。

大M法

对于最大化问题,当以下式作为约束方程组(每个方程加一个人工变量),若将目标函数修改为,其中是一个很大的正数,因为是对目标函数实现最大化,因此人工变量必须从基变量中迅速换出去,否则目标函数不可能实现最大化。

注:如果是最小化问题要用大M法,则把最小化目标函数化为

例:求解线性规划问题.

解:将问题化为,写出初始单纯形表

线性规划问题-大M法-例题-01

这里的M看作是一个很大的正数即可(因此选取所在列为主列),第一次迭代:

线性规划问题-大M法-例题-02

第二次迭代:

线性规划问题-大M法-例题-03

第三次迭代:

线性规划问题-大M法-例题-04

对于最大化问题,检验数全部时取得最优解,于是当前解为新问题的最优解。此时基变量中不含人工变量,且人工变量取值为零,所以当前解去掉的部分就是原问题的最优解,即原问题的最优解为

两阶段法

当线性规划问题添加人工变量后,将问题拆成两个线性规划问题:

(1)第一阶段:求解第1个线性规划,即第1个线性规划的目标函数是对所有人工变量之和求最小,分以下情况进行讨论:

(2)第二阶段:得出原问题的一个基本可行解后,通过单纯形法对原问题进行计算。

例:考虑线性规划问题.

解:建立第一阶段的线性规划问题,令作初始可行基,作初始单纯形表:

线性规划问题-两阶段法-例题-01

由于这里是最小化问题,当所有检验数都时才取得最优解,选取第三列为主列,进行第一次迭代:

线性规划问题-两阶段法-例题-02

第二次迭代:

线性规划问题-两阶段法-例题-03

此时已达到最优值,因此第一阶段的最优解为,将该表中人工变量列划去,即可得到第二阶段的初始单纯形表(由于第二阶段目标函数不同,涉及目标函数的部分需重新计算),且为第二阶段的初始基本可行解。

建立第二阶段的线性规划问题,写出初始单纯形表:

线性规划问题-两阶段法-例题-04

第一次迭代:

线性规划问题-两阶段法-例题-05

因此原问题的最优解

8. 对偶问题

对偶问题概述

引入:一个线性规划问题往往伴随着与之配对的,两者有密切联系的另一个线性规划问题,我们将其中一个称为原问题,另一个称为对偶问题。对偶问题在经济学上有重要意义,下面通过一个问题来说明。

问题:某家具长木器车间生产木门和木窗两种产品,加工木门收入为56元/扇,加工木窗收入为30元/扇,生产一扇木门需要木工4小时、油漆工2小时,生产一扇木窗需要木工3小时、油漆工1小时。该车间每日可用木工总工时为120小时,油漆工总工时为50小时,问该车间应如何安排生产才能使每日收入最大?

解:令该车间每日安排生产木门扇、木窗扇,则数学模型为,用图解法或单纯形法,可求得最优解元。

现在从另一个角度来考虑车间的生产问题。假设有一个个体经营者,手中有一批木器家去生产订单,他想利用该木器生产车间的木工与油漆工来完成他的订单,他就要实现考虑付给该车间每个工时的价格。他可以构造一个数学模型来研究如何定价才能:(1)木器生产车间觉得有利可图从而愿意替他加工这批订单(2)他自己所付的工时费用总数最小。设为付给木工每个工时的价格,为付给油漆工每个工时的价格,则该个体经营者的目标函数为每日所付工时总费用最小,即,但该个体经营者所付的价格不能太低,至少不能低于该车间生产木门、木窗时所得到的收入,否则车间觉得无利可图就不会替他加工这批订单,因此应满足,解出

对比两个问题,,他们有某些共同点:原问题的价值系数是对偶问题约束条件的右端项,对偶问题价值系数是原问题约束条件右端项,原问题约束不等式系数的行是对偶问题约束不等式系数的列,原问题约束不等式系数的列是对偶问题约束不等式系数的行,…

原问题与对偶问题:原问题与对偶问题一般表示为,其中,两个问题之间的对应关系总结如下表(如果原问题是最小化问题,则从右侧对应左侧):

线性规划问题-对偶问题-原问题与对偶问题的关系-01

比如:写出下列问题的对偶问题:.

对偶理论

对于,其中,有如下定理:

弱对偶性定理:设分别是LP和DP的任一可行解,则恒有

证明:.

该定理说明了,最大化问题的任一可行解的目标函数值都是其对偶最小化问题目标函数的下界。最小化问题的任一可行解的目标函数值都是其对偶最大化问题目标函数值的上界。

定理:设分别是LP及DP问题的可行解,则当时,必分别是各自问题的最优解。

证明:设是LP问题的任意一个可行解,则由弱对偶性定理知,必有,说明是LP问题的最优解;同理可证是DP问题的最优解。

定理:若原问题LP与对偶问题DP同时有可行解,则它们必都有最优解。

定理:若原问题的目标函数无界,则其对偶问题必无可行解。

强对偶定理:设LP与DP中有一个最优解,则另一个问题也必存在最优解,且两个问题最优解的目标函数值必相等。

证明:将原问题标准化为,其中为松弛变量,为松弛变量的系数(显然),为单位矩阵,设其相应的最优基为,则所有变量的检验数。考虑变量的检验数,可以写成,若记,代入上式得,因此满足对偶问题的约束条件;再考虑的检验数,可以写成,那么,因此是对偶问题的可行解,此时原问题与对偶问题的目标函数值有,故为对偶问题的最优解(前面的定理,目标函数值相等即为各自最优解)。

对称形式的互补松弛性定理:设分别是对称形式的原问题及其对偶问题的两个可行解,则分别是各自问题的最优解的充分必要条件为:对所有的,下列各式都成立:

(1)若,必有

(2)若,必有

(3)若,必有

(4)若,必有

其中为原问题约束矩阵的第行,的第列,是对偶变量,是原问题的决策变量,是原问题的价值系数,是原问题约束方程右端项。

例:若已知的最优解为,求其对偶问题的最优解

解:对偶问题为,根据互补松弛定理的第(1)条,因为所有的,列出的方程得,此时方程还无法求解,于是再根据互补松弛定理的第(4)条,再将代入原问题的约束条件中,得,所以,最后解得对偶问题最优解为.

对偶单纯形法

引入:单纯形法从一个基本可行解迭代到下一个基本可行解时,总是保持解的可行性不变,变化的只是检验数向量,对于最大化问题,当时最优解诞生,此时由知,是对偶问题的可行解。因此,我们可以这样来描述单纯形法的过程:从基本解向最优解迭代时,是始终保持原问题可行性的条件下,其对偶问题由不可行()向可行()转化,一旦其对偶问题也成为可行解时,根据前面定理,原问题的可行解即成为最优解。而对偶单纯形法是把上面的过程反过来,在迭代的过程中,始终保持对偶问题解的可行性,而使原问题的解由不可行逐渐向可行转化,一旦原问题的解满足了可行性,对偶问题也就达到了最优解。

正则解与正则基的定义:设是原问题的一个基本解,对应的基是,若它所对应的检验数向量成立,则称是原问题的一个正则解,对应的基矩阵称为正则基

正则解对原问题而言只是一个基本解,并不要求是可行解,而其成立,即满足了对偶问题的可行性,称之为正则。因此用正则性语言来描述对偶单纯形法的思路是:在保持正则解的正则性不变的条件下,在迭代过程中,使原问题的不可行性逐步消失,一旦迭代到可行解时,即达到了最优解。

对偶单纯形法计算步骤

(1)给定一个初始正则解,对应的正则基为

(2)计算,若时,则停止计算,当前的正则解便是最优解,否则继续进入到下一步;

(3)确定离基变量:令,则为离基变量(此时称第行称为主行);

(4)检查单纯形表中第行的系数:,若所有的,则原问题无可行解,否则转下一步(理由如下:对于第个约束方程,因为所有的,因此不论)改为怎样的正值,都无法使的值转化为正数,故本问题无可行解);

(5)确定进基变量:取,则是进基变量,是主列;

(6)迭代:以为主元素进行消元变换,迭代到下一个正则解。

对偶单纯形法与单纯形法的不同之处在于,先根据确定离基变量得到主行,再用检验数除以主行中的负元素得到比值确定进基变量。

例:用对偶单纯形法求解.

解:将问题标准化为,为了利用作为初始基,将两个约束方程左右两端各乘,得,写出初始单纯形表:

线性规划问题-对偶问题-对偶单纯形法-例题-01

第一次迭代:

线性规划问题-对偶问题-对偶单纯形法-例题-02

第二次迭代:

线性规划问题-对偶问题-对偶单纯形法-例题-03

此时达到了最优解。

9. 单纯形法的灵敏度分析

引入:之前的计算中,总是把(价值系数)、(约束矩阵)、(约束方程右端项)视作常数,而灵敏度分析是讨论他们如果变化,会对解产生什么影响。

灵敏度分析通常有两类问题:

设考虑的问题为,相应的最优单纯形表为:

线性规划问题-灵敏度分析-01

下面分情况讨论(注意计算时由于题目数据发生了改变,大部分情况下都要用题目的数据进行重算,而不能用单纯形表中的数据计算):

价值系数c发生改变

时,最优表会发生改变的只是最后一行(检验行)。设,则,则检验数应修改为,而目标函数值应修改为。此时:

例1:已知标准形式的线性规划问题,其最优单纯形表如下

线性规划问题-灵敏度分析-例题1-01

问:(1)当变为时,求新问题的最优解(2)讨论在什么范围内变化时,原有的最优解仍是最优解

解:(1)因为只有非基变量的系数发生了改变,只需重新计算,可见最优性准则已不满足,修改上表后重新迭代可得问题的最优解:

线性规划问题-灵敏度分析-例题1-02

(2)要使原最优解仍为最优解,须在新条件下仍满足,记,由于为基变量,发生了改变全部检验数都要重算,于是,即当或写成时,原最优解仍为最优解。

右端项b发生改变

当右端列向量,改变的只是表中第三列(右端列),即基变量的取值由,而目标函数值由。此时:

例2:已知线性规划问题,若右端列向量从,求新问题的最优解。

解:原问题的最优单纯形表如下:线性规划问题-灵敏度分析-例题2-01

改变为时,,当前解只是一个正则解,还要用对偶单纯形法进行迭代:

线性规划问题-灵敏度分析-例题2-02

第一次迭代:

线性规划问题-灵敏度分析-例题2-03

故新问题的最优解是,最优值为

约束系数列向量发生改变

设系数列向量由。此时:

例3:已知线性规划问题,若由原来的,最优解将如何变化?

解:原问题的最优单纯形表如下

线性规划问题-灵敏度分析-例题3-01

发生改变,此时,最优准则已不满足,修改最优单纯形表中的第三列为,选出主元素再进行迭代

线性规划问题-灵敏度分析-例题3-02

第一次迭代:

线性规划问题-灵敏度分析-例题3-03

故新问题的最优解是

增加一个新变量

考虑线性规划问题,设该问题已经得到了最优解,最优基为,现追加一个新变量,其价值系数为,系数列向量为,得到新问题,这时原问题的最优基是新问题的可行基,原由变量的检验数都保持不变,而。此时:

例4:已知线性规划问题,现增加新变量,且,求新问题的最优解。

解:原问题的最优单纯形表如下

线性规划问题-灵敏度分析-例题4-01

计算决策变量的检验数,说明新增加的对总的结果有利,目标函数肯定有所增加。在原最优单纯形表加入列,然后以作为进基变量进行迭代

线性规划问题-灵敏度分析-例题4-02

第一次迭代:

线性规划问题-灵敏度分析-例题4-03

故新问题的最优解是

10. 运输问题

运输问题的数学模型

运输问题是一种典型的线性规划问题,所以它可以用单纯形法求解,但是其数学模型有特殊的结构,存在一种比单纯形法更简便的计算方法–表上作业法(表上作业法本质上仍是单纯形法)。下面通过例子来了解运输问题:

问题:设有个生产点可供应某种物质,其生产量分别为,另有销售点,其销售量分别为。如果从运输单位物质的运价为,那么在产销平衡的条件下(),如何设计调运方案才使得运费最小?

解:将问题通过表格来描述,其中表示从的发运量:

于是可以得到数学模型:,把前两个约束展开,得到,其系数矩阵为,观察可知:

定理(运输问题解的存在性):产销平衡问题存在最优基本可行解。

证明:记,若构造),将代入约束方程得,因为,所以是产销平衡问题的可行解,故原问题有基本可行解。

再由的定义知,,即产销问题的任意可行解是有限的,故其可行域是有界的,因此原问题必有最优解。

(补充)产销不平衡问题的数学模型:当产量大于销量时,有,相应的数学模型为

表上作业法:要求解产销平衡时的运输问题,可以用西北角法最小元素法确定初始可行解,然后用位势法求检验数,再用闭合回路法调整基本可行解,由于以上都在表(价格表或调运表)中进行,所以它们都是表上作业法

首先了解几个相关的定义:将变量在调运表中对应的空格记作,称为格点,将的系数列向量称为格点所对应的系数列向量。若为基变量,则称为基格,否则称为非基格

西北角法

下面通过例题了解西北角法如何确定初始可行解:

例:某公司生产糖果,它有3个加工厂,每月产量分别为,该公司把产品分别运往4个销售店,每月销量分别为。已知从第个加工厂到第个销售店的每吨糖果的运价见下表,试设计在满足销售店需求量的前提下,个加工厂到每个销售店的调运方案,使该公司所花总的运费最小。

价格表

3 11 3 10
1 9 2 8
7 4 10 5

解:画出调运表如下:

发量
7
4
9
收量 3 6 5 6

要填写该表,可以用西北角法,观察最西北角处的格子(行与列交界处),此时发量(即产量)为7,而收量(即需求量)为3,因此可以满足,不再需要来自的货物,画斜线,于是填写如下

发量
3 7-3
/ 4
/ 9
收量 3-3 6 5 6

那么剩下的格子的西北角是交界处位置,此时收量为6,而发量只剩下4,于是剩下的不可能再接收来自的货物,划斜线,而剩下的收量2需要来自,于是填写如下

发量
3 4 / / 7-3-4
/ 2 4-2
/ / 9
收量 3-3 6-4-2 5 6

以此类推,最后填写如下

发量
3 4 / / 7-3-4
/ 2 2 / 4-2-2
/ / 3 6 9-3-6
收量 3-3 6-4-2 5 6

故原问题的一个初始可行解,相应的总费用为1330元。

最小元素法

下面通过例题了解最小元素法如何确定初始可行解:

例题同西北角法,但是这次使用最小元素法确定初始可行解,价格表如下:

3 11 3 10
1 9 2 8
7 4 10 5

解:画出调运表如下

发量
7
4
9
收量 3 6 5 6

要填写该表,根据最小元素法,从价格表中找出运费最低的是1,即从运往,于是在调运表对应位置尽可能发更多的货,对应位置发货量为3可以满足,于是此时达到饱和,不需要再来自的货物,画斜线

发量
/ 7
3 4-3
/ 9
收量 3-3 6 5 6

再找下一个最小的元素,是从运往的2,发完1的货物后,已经不可能再给发货了,于是填写如下

发量
/ 7
3 / 1 / 4-3-1
/ 9
收量 3-3 6 5-1 6

再找下一个最小的元素,是从运往的3,以此类推,最后填写如下

发量
/ / 4 3 7-4-3
3 / 1 / 4-3-1
/ 6 / 3 9-6-3
收量 3-3 6-6 5-1-4 6

故原问题的一个初始可行解

位势法

位势法的原理是利用基变量检验数为零,得到公式是其对偶问题的决策变量),依此得到方程组解出,再利用非基变量检验数公式算出非基变量的检验数。

推导:在原来检验数公式的基础上修改,得到双下标形式的检验数公式,若记,则就是对偶问题的决策变量,设,则运输问题的对偶问题为,决策变量的检验数为,因为基变量的检验数,故当,这是一个含有个方程、个未知量的线性方程组,为求解方程组,我们人为规定令,这样就可以求出所有的,以及所有非基变量的检验数。

下面通过例题了解位势法如何求检验数(注意位势法是在价格表上进行的):

同样是前面的问题,用西北角法求出的可行解为例,下面是其对应的调运表

发量
3 4 / / 7-3-4
/ 2 2 / 4-2-2
/ / 3 6 9-3-6
收量 3-3 6-4-2 5 6

在例题的价格表上加上一行一列,其中是其对偶问题的决策变量,在对应的调运表中非零元素的位置作加粗标识(其对应的是基变量),非基变量用中括号括住,如下表

[3] [10]
[1] [8]
[7] [4]

由于检验数公式为,所以我们应将确定下来,首先根据前面的分析,人为规定为0,于是填写如下

[3] [10]
[1] [8]
[7] [4]
0

以某个基格为标准,结合公式(仅当时成立)计算运输问题的对偶问题的基变量,比如,(注意只看基变量对应的格子,即加粗元素的位置),最后填写如下

[3] [10] -1
[1] [8] -3
[7] [4] 5
4 12 5 0

对于非基变量的检验数,通过计算,比如,把检验数写在价格表上,如下表(原非基变量的用中括号括住,而基变量的检验数一定为0就不填写了)

[3]-1 [10]11 -1
[1]0 [8]11 -3
[7]-2 [4]-13 5
4 12 5 0

由于问题是最小化问题,当所有检验数都时得到最优解,显然当前解还不是最优解,还要再用闭合回路法对基本可行解进行调整。

闭合回路法

定义:若一组格点经过适当的排序后,能写成以下形式:,则称这组格点构成了闭合回路

比如以下格点:

线性规划问题-运输问题-闭合回路法-01

由梨花组成的就构成了闭合回路;再比如心形组成的也构成了闭合回路,…

下面通过例题了解闭合回路法如何调整基本可行解:

前面通过位势法得到了下面价格表

[3]-1 [10]11 -1
[1]0 [8]11 -3
[7]-2 [4]-13 5
4 12 5 0

同单纯形法选择进基变量的准则,对于最小化问题,找出最小检验数对应变量作为进基变量,,即为进基变量,也就是说进基格,为确定离基变量,以进基格为起点作一个闭合回路,要求除起始格为进基格外,该闭合回路的其余顶点均为基格

我们在调运表中进行操作(进基格用标注):

发量
3 4 7
2 2 4
3 6 9
收量 3 6 5 6

找出任意一个闭合回路,比如,考虑(闭合回路用标注):

发量
3 4 7
4
6 9
收量 3 6 5 6

其中。因为根据产销平衡原则,进基变量要增大(从0变为正数),所以销售点进更多的货(吨)就要从少进同等数量的货(吨),同时闭合回路上的也从进了货,由于的发量是固定的,所以销售点要从少进吨货,同时从吨货以保持收量;而的取值准则是尽可能大,由于最多只能减到零,所以找(也就是符号为负)中的最小值。

此时显然易见,选择变为了零,于是就是离基变量。因此改善后的基本可行解为

发量
3 4 7
4 4
2 1 6 9
收量 3 6 5 6

此时再通过位势法检验是否为最优解,若不是,再重复前面的步骤直至得到最优解。

后续过程

第二次迭代

用位势法得到的价格表:

[3]-14 [10]-2 12
[1]13 [9]13 [8]11 -3
[7]11 5
-9 -1 5 0

检验数还有小于零的部分,继续迭代,对应的调运表:

发量
3 7
4 4
6 9
收量 3 6 5 6

用闭合回路法得到的调运表:

发量
3 3 1 7
4 4
3 6 9
收量 3 6 5 6

第三次迭代

再用位势法检验是否为最优解,得到的价格表为:

[10]-2 12
[1]-1 [9]-1 [8]-3 11
[7]11 [10]14 5
-9 -1 -9 0

检验数还有小于零的部分,继续迭代,对应的调运表:

发量
3 7
4
9
收量 3 6 5 6

经过有限次运算得到最优解,且最优解有无穷多个

发量
2 5 7
1 3 4
6 3 9
收量 3 6 5 6

相应的最优值为.

三、整数规划问题

1. 整数规划问题的数学模型

在许多线性规划问题中,决策变量具有不可分割的性质,如人数、设备的台数、车辆船只数、项目的个数等

例1:设有一背包的最大容量,现有种物品可供选择装入背包,每种物品数量不限,设第种物品的体积为),相应的价值为,问每种物品各取多少件装入,可使背包中价值最大?

解:设第种物品有件装入背包,则,这是一个纯整数规划问题。

通常情况下,整数规划无法通过单纯形法求解然后对结果舍零取整得到解,因为取整后的解不一定仍然是可行解,即使是可行解也不一定是最优解。我们把整数规划问题中的整数要求去掉后的问题称为原问题的伴随规划

例2:某厂计划用集装箱托运甲乙两种货物,每箱的体积、重量、可获利润及托运所受限制见下表,如何设计装运方案可使所获利润最大?

货物/箱 体积/ 重量/百斤 利润/百元
5 2 20
4 5 10
托运限制/集装箱 24 13

解:数学模型为,这是一个纯整数规划问题,其伴随规划为,伴随规划的最优解为,易知舍零取整后的解不是原问题的整数规划的可行解;而是可行解,但不是整数规划的最优解。

2. 分枝定界法

分枝定界法既可以用来求解整数规划,也可以用来求解混合整数规划。分枝定界法的主要思路是:首先求解整数规划的伴随规划,如果求得的最优解不符合整数条件,则增加新约束条件以便缩小可行域,将原整数规划问题分枝为两个子规划,再解子规划的伴随规划,通过求解一系列子规划的伴随规划问题,从而不断地定界,最后得到原整数规划问题的整数最优解。

原问题与伴随规划问题的解的关系如下:

分枝定界法的步骤如下(一般将原问题(整数规划问题)称为问题,将它的伴随问题称为):

步骤一:计算原问题目标函数的初始上界。因为问题的可行域问题的可行域,故一般用伴随问题的作为初始上界;

步骤二:计算原问题目标函数的初始下界。若能从问题的约束条件观察到一个整数可行解,则可将其目标函数值作为问题目标函数的初始下界,否则可以令初始下界为

步骤三:增加约束条件将原问题分枝。一般是分别采用向上、向下取整将伴随问题的小数部分去掉,从而分为两枝。

步骤四:分别求解每一分枝。对某分枝的伴随问题求解,可能出现以下情形:

步骤五:修改上界与下界。修改的时机和原则如下:

步骤六:结束准则:当所有分枝均已查明,且此时,则已得到了原问题的整数最优解,即目标函数值为下界的那个整数解。

下面通过例题了解分枝定界法

例:求解下列整数规划问题.

解:为方便表示,这里将原问题称为问题,将它的伴随问题称为。通过之前的方法可以求出的最优解为,最优值为,下面开始使用分枝定界法:

步骤一:计算原问题目标函数的初始上界。因为问题的最优解不满足整数条件,故不为的最优解,又因为的可行域问题的可行域,故有,于是的初始上界为

步骤二:计算原问题目标函数的初始下界。对于本例,一个显然的可行解为零,故

步骤三:分枝。由于的最优解为,可以将问题分枝为

步骤四、五、六:分别求解这一对分枝的伴随问题,并更新上、下界,一直进行分枝,直至上界与下界相等时得到整数最优解。

整数规划问题-分枝定界法-例题-01

3. 割平面法

割平面法主要用于求解纯整数规划。割平面法的主要思路是:不断切割原问题伴随规划的可行域,使它在不断缩小的过程中,将原问题的整数最优解逐渐暴露,且趋于可行域极点。

下面通过例题了解割平面法

例:求解下列整数规划问题.

解:求出伴随问题的最优单纯形表如下

整数规划问题-割平面法-例题-01

割平面法步骤如下:

(1)割平面方程可以由上述最优单纯形表上任一含有不满足整数条件的基变量的约束方程演变得到,比如上表中对应的行(第4行),有

(2)将所选的约束方程中非基变量的系数及常数项进行拆分处理,具体规则是:将上述系数和常数项均拆成一个整数加一个非负的真分数之和,即

(3)将上述方程重新组合,组合的原则是:将非基变量系数及常数项中的非负真分数移到等号左端,将其他部分移到等式右端,即

(4)求割平面方程,等式右端全部项为整数,并且松弛变量被认为是非负整数(当原问题的约束方程组中的系数或常数项中有非整数时,可以先将它们化为整数再标准化,所以这里只考虑整数的情况)。这里,故,否则非负的条件矛盾(反证法:由于都是整数,如果严格小于零,那么最大只能取,此时,而如果非负,不可能等于一个小于零的数),因此割平面条件为:

(5)把割平面条件化为,加入松弛变量得,将此方程加入到伴随规划的约束方程中,得到新问题

新问题的单纯形表可以由原来的单纯形表改写得到,直接添加一行一列如下

整数规划问题-割平面法-例题-02

此时还不是最优单纯形表,通过对偶单纯形法得到最优单纯形表如下

整数规划问题-割平面法-例题-03

可见此时已得到整数最优解,所以最优解为,且相应的目标函数值为

4. 指派问题与匈牙利算法

最小化的指派问题

指派问题:在实践中经常会遇到这样一种问题:有n项不同的工作或任务,需要n个人去完成,要求每人只完成一项工作,由于每人的知识、能力、经验等不同,故各人完成不同任务所需要的时间不同,问应指派何人完成何项工作,使完成n项工作总耗时最少,这种问题叫做指派问题,指派问题是一种整数规划问题,同时也是一类特殊的运输问题。

指派问题的数学模型,其中表示令第个人去完成第份工作,表示第个人做第份工作的时间(或资源浪费,匈牙利算法要求非负),约束条件表示一个人只能做一份工作,并且每份工作只由一个人来完成。将效率系数排成一个矩阵,称为效率矩阵价值系数矩阵,即

定理:设指派问题的效率矩阵为,若将该矩阵的某一行或列的各元素都减去同一个常数,得到新的效率矩阵,则以为效率矩阵的新指派问题与原指派问题的最优解相同,但其最优值比原最优值减少

证明:根据指派问题定义,假设第行减去了.

定理:若将指派问题的效率矩阵每一行(或每一列)分别减去各自的最小元素,则得到的新指派问题与原指派问题有相同的最优解。

将效率矩阵的每一行减去各行最小元素,所得矩阵的每一列再减去当前列中最小元素,最后的新效率矩阵中必然会出现一些零元素,显然,元素表示第个人去干第项工作效率最好,或表示第项工作由第个人来干效率最高。

定义:在效率矩阵中,有一组处在不同行不同列的零元素,称为独立零元素组,此时其中每个元素称为独立零元素。

例1:由效率矩阵的独立零元素组确定最优指派问题:,其中加粗的零就组成了一个独立零元素组,此时将独立零元素组所在的位置赋1,其他为零,就得到了一个解,即让第1个人去完成第2份工作、第2个人去完成第4份工作,…;独立零元素组并不唯一,比如

可见,当独立零元素组的个数和矩阵的阶数相等时,可以直接利用定理2及独立零元素组写出解。但是在有的问题中,效率矩阵的独立零元素的个数不到个,这样就无法求到最优指派方案,需要作进一步分析。

定理:效率矩阵中独立零元素的最多个数等于能覆盖所有零元素的最少直线数。

比如:是4个独立零元素,也是4个独立零元素。

圈零法:要找出矩阵的独立零元素,可以使用圈零法,具体步骤如下:

(1)进行行检验:对进行逐行检查,每行只有一个未标记的零元素时,用O记号将该元素圈起,然后将被圈起的零元素所在列的其他未标记的零元素用记号×划去; (2)进行列检验:与进行行检验类似;

(3)重复检验,直到每一行都没有未被标记的零元素或至少有两个未被标记的零元素为止。

根据圈零法标记的个数的不同,最后可能会有如下情况:

匈牙利算法的步骤

(1)根据定理2,将各行或各列都减去各自的最小元素,得到新效率矩阵,此时新效率矩阵对应的最优解仍与原问题相同;

(2)用圈零法找出新矩阵中的独立零元素;

(3)进行试指派,根据前面圈零法讨论的不同情况:①情况1可以直接令圈零位置的决策变量取值1,其他决策变量取值0,得到一个最优指派方案;②情况2经过任选一个作为独立零元素的处理,再次进行圈零法的检验,会转变为情况1或情况3;③情况3,需进行第四、五步。

(4)增加独立零元素的个数。首先要作最少直线覆盖当前所有零元素:①对中所有不含圈零元素的行打;②对打的行中所有零元素所在列打;③对所有打列中圈零元素所在行打;④重复上述第②、③步,直到不能进一步打为止;然后对所有没有打的行划横线、对已打的列划竖线,便能用最少直线覆盖所有零元素。然后再在未被直线覆盖的元素中找出最小元素,将打行的各元素减去这个最小元素,将打列的各元素加上这个最小元素,这样就能增加独立零元素的个数。

(5)对已增加独立零元素的矩阵,重复(2)、(3)、(4)步,直至出现圈零数等于矩阵阶数为止。

下面通过例题了解匈牙利算法的完整求解步骤

例2:现有一个的指派问题,其效率矩阵为,求该指派问题。

解:

步骤一:变换效率矩阵,根据定理2,将各行都减去各自的最小元素,得

步骤二:用圈零法求出新矩阵中独立零元素,最后得到,检查的过程为(这里用代替圈):先看第1、2行,都有多于一个的零,不作任何标记;到第3行时,只有一个零,对这个零作标记,此时同列的位置的零划掉;再到后面4、5行都不符合,不作标记;行检查完一次,开始对列进行检查,第1列的所有零都已经有标记了,不作检查;第2列只有一个零,对这个零作标记,此时同行的位置的零划掉;第3、4列都有多于一个的零,不作任何标记;第5列只有一个零,对这个零作标记,此时同行的位置的零划掉;第二次行检查可以看到,只剩下位置的零还没有被标记,任选一个画,另一个划即可。

步骤三:进行试指派。此时显然独立零元素的个数4小于矩阵阶数5,属于情况3,进入步骤四。

步骤四:先作最少直线覆盖当前所有零元素,根据规则对行、列打,然后对所有没有打的行划横线、对已打的列划竖线,最后得到,然后找出没有划线元素中最小元素为2,打行减去2、打列加上2,得到

步骤五:找出的独立零元素,用圈零法得,此时可以直接写出最优解为,其余

(补充)最大化的指派问题

对于最大化的指派问题,,不能使用将目标函数添加负号转化为最小化问题的方法,因为匈牙利算法要求每个元素都非负。

我们可以在效率矩阵中,找出一个最大元素,并令),这样就能转化为求解最小化问题

这两个问题等价的证明:,即负相关,的最小值就是的最大值。

四、非线性规划

1. 非线性规划的数学模型

非线性规划的概念:线性规划的一个明显的特点是其目标函数与约束条件都是决策变量的一次函数,如果在一个规划问题的目标函数和约束条件中,至少有一个方程是决策变量的非线性函数,则称这类规划问题为非线性规划

例1(选址问题):设有个市场,第个市场的位置为,它对某种货物的需求量为),现计划建立个仓库,第个仓库的存储容量为)。试确定仓库的位置使各仓库对各市场的运输量与路程乘积之和为最小。

解:设第个仓库的位置为,它到第个市场的货物供应量为,则数学模型为.

一般非线性规划的数学模型可表示为,其中,而都是的映射。

定义:我们称下列集合为非线性规划问题的可行域。当非线性规划问题的自变量没有任何约束,或说可行域是整个维向量空间,则称该非线性规划问题为无约束问题,记作,有约束问题与无约束问题在处理方法上有明显的不同。

在微积分中曾讨论过极值问题,它们都属于无约束极值问题,即使有约束,也是等式约束,这样可利用拉格朗日乘子法。将等式约束极值问题化为无约束极值问题来求解,这种极值问题统称为经典极值问题。

定义:若,且满足,即对都有,则称为非线性规划的全局最优解

定义:若,且存在一个,对于(这里的表示的一个邻域),使成立,即,都有,则称为非线性规划的局部最优解

若线性规划问题有最优解,则其最优解一定在可行域的极点上,但非线性规划的最优解却可能是可行域上的任何一点。

线性规划问题的最优解一定是全局最优解,而非线性规划问题有局部最优解与全局最优解之分,一般的非线性规划算法往往求出的是局部最优解。

2. 无约束问题-最优性条件

定义:设,若在处对于自变量的各分量的偏导数都存在,则称函数在点一阶可导,并称向量在点处的梯度一阶导数

定理(微分与梯度的关系):设,若在点可微,则在点处的梯度存在,并且有,其中处的增量。

定义:设,若处对于自变量的各分量的二阶偏导数)都存在,则称函数在在点二阶可导,且称矩阵在点处的二阶导数黑塞矩阵,记作

定义:设是一个多元函数,,若,且,则:

定义:设是一个多元函数,,若,则:

多元函数局部极小点(极大点)的判定条件

定理(一阶必要条件):设)在点处可微,若的局部极值点,则

注意只是函数取得极值点的必要条件;

我们将满足的点称为函数的平稳点;函数的平稳点或是其极小点,或是其极大点,或两者都不是。

定理(二阶必要条件):设)在点处二次可微,若的局部极小点,则,且半正定。

定理(二阶充分条件):设)在点处二次可微,若,且正定,则是函数的严格局部极小点。

定理(二阶充分条件):设)在点的一个邻域内二次可微,若在点处满足,且都有半正定,则是函数的局部极小点。

例1:求下列函数的极小点.

解:先找出平稳点,得出平稳点为,然后再判断黑塞阵的正定性,在平稳点的黑塞阵为,观察可知它是一个正定矩阵(因为特征值都大于零),根据前面的定理(二阶充分条件1)知,是严格局部极小点。

例2:求下列函数的极小点.

解:先找出平稳点,得出平稳点为,黑塞阵为,在平稳点的黑塞阵为,该矩阵是半正定的(一阶顺序主子式大于零,而二阶顺序主子式等于零),考虑的邻域,则,易证上述矩阵是半正定的,故是局部极小点。

3. 解非线性规划的基本思路

引入:前面讨论了无约束问题的最优性条件,但是对大多数实际问题,要用最优性条件来求解非线性规划是很困难的:有的问题导数不存在,有的问题导数即使存在,计算也很麻烦;多数问题由条件得到的是一个非线性方程组,求解非常困难,甚至根本无法得到解析解。

求解非线性规划问题一般采用数值计算的选代方法。迭代就是从某个已知点出发,按照某种算法求出后继点,用代替,重复以上过程,得到一个点列。非线性规划选代方法的基本思想是:使得要求的送代算法(1)当是穷点列时,其最后一点是该问题的最优解;(2)当是无穷点列时,它的极限点是该问题的最优解。

定义:设是某种迭代算法的第轮和第轮迭代点,记为两者之差,即,故,令是向量方向上的单位向量,则有,进而有,其中是大于零的实数。这里的就是基本迭代格式,并且从该选代格式可知,求解非线性规划问题的关键在于:如何构造每一轮的搜索方向步长因子

根据基本选代格式,求解非线性规划问题的选代算法的关键在于构造搜索方向,构造不同的搜索方向,就是不同的算法。但这些不同的搜索方向有一个共同的要求:就是当算法从产生了搜索方向和步长,从而得到了,要求,也就是说,搜索方向应指向目标函数值减小的方向。

定义:设,点,向量),若存在一个数,使都有,则称向量在点处的下降方向

一般来说,在点处的下降方向不止一个,可能有无穷多个,那么如何在点处选择使函数下降最快的方向是一个重要的问题。并且对于有约束的非线性规划问题,算法不仅要保证搜索方向为下降方向,而且要保证仍在可行域内,因此对于有约束的非线性规划问题,要寻找可行下降方向

计算的终止条件:常用的计算终止条件有:

非线性规划迭代算法的一般步骤

(1)选取初始点,令

(2)构造搜索方向(下降方向或可行下降方向,构造的方向不同,就是不同的算法);

(3)确定步长因子,此时只是的一元函数,求步长就相当于求一元函数的极小点,即,称上述最优步长,并称求最优步长的过程为一维搜索

(4)求出下一个迭代点;若已满足规定的终止条件,停止迭代,否则令,转第二步。

4. 无约束问题-步长(一维搜索)

前面提到过,求解的过程称作一维搜索,因为的极小点,故在理论上应满足,但是对许多问题来说,求导计算并不容易,且不便于利用计算机来解决,因此一般不是用求导的方法来求的精确值,而是求它的近似值。求解近似值的方法主要分为区间收缩法函数逼近法

后面介绍的黄金分割法属于区间收缩法,而牛顿法抛物线法属于函数逼近法。

黄金分割法

黄金分割法也称0.618法,属于区间收缩法,其主要步骤为:①找出包含极小点的初始搜索区间;②按黄金分割点通过对函数值的比较不断缩小搜索区间(要保证极小点始终在搜索区间内);③当区间长度小到精度范围之内时,可以粗略地认为区间端点的平均值即为极小点的近似值。

定义:设函数,闭区间,若存在一点,使上严格递减,在上严格递增,则称单谷函数单谷区间

单谷函数及其性质::若是单谷区间上的单谷函数,极小点为,在中任取两点,且,则

非线性规划-一维搜索-黄金分割法-01

黄金分割法的步骤

(1)在单谷区间中找两个试点后,比较的大小,就可把搜索区域缩小至

(2)在区间中继续找试点,比较的大小,又可以把搜索区域从缩小至

(3)重复上述过程,直到的区间长度足够小,并达到事先规定的精度时,取

一般取黄金分割点及对称点。

非线性规划-一维搜索-黄金分割法-02

黄金分割点及对称点:若记,则,若希望,因此

取黄金分割点及对称点的优势:

  1. ,搜索区间被保留下来的是,则区间的黄金分割点;
  2. ,搜索区间被保留下来的是,则其中的区间的对称点。

黄金分割法的简化步骤

(1)选取初始数据:确定初始搜索区间,给出最后的区间精度

(2)计算初始的两个试点:在区间上黄金分割点用表示,其对称点用表示,计算,并计算相应试点的函数值,此时规定

(3)比较目标函数值:

例:用黄金分割法求的近似最优解,设初始的搜索区间为,精度.

解:初始数据题目已经给出;接下来计算初始的两个试点,计算,计算得,此时规定;显然,取,此时,精度不满足要求,故需继续寻找试点,计算得,算法在转至第三步。

显然,取,此时,精度不满足要求,故需继续寻找试点,计算得,算法在转至第三步。

显然,取,此时,精度满足要求,因此近似最优解为,相应的近似最优值为

牛顿法

牛顿法是一种函数通近法,它的基本思想是:在极小点附近用二阶泰勒多项式近似代替目标函数,从而求出极小点的估计值。

,现已有极小点的第级估计值,在点将作二阶泰勒展开:,记,则在附近可用来近似,即,因此可以用的极小点来近似的极小点(假定的极小点在附近)。

首先要找出的驻点,令,得驻点为,以的驻点作为附近的极小点的第级估计值。

牛顿法的步骤

(1)给定初始点,给定精度,令

(2)计算:若,则停止迭代,输出近似极小点,否则进行第三步;

(3)用迭代公式计算,令,返回第二步。

例:用牛顿法求函数的极小点,取.

解:

1 1 0.7854 2 0.7854 -0.5708
2 -0.5708 -0.5187 1.3258 0.5187 0.1169
3 0.1169 0.1164 1.0137 0.1164 -0.00106
4 -0.00106 0.0010

加步探索法

黄金分割法及其他一维搜索方法都要事先给定一个包含极小点的初始搜索区间,加步探索法能解决这个问题。

加步探索法本身是一种区间试探法,其主要思路就是从一点出发,按一定的步长,试图确定出函数值呈现“高-低-高”的三点。首先从一个方向去找,若不成功,就退回来,再沿相反方向寻找,若方向正确,则加大步长进行探索,最终找到三点,并满足

加步探索法的步骤

(1)给定初始点,初始步长

(2)用加倍步长的外推法找出初始区间,由初始点向某个方向,比如向增大方向走一步,步长为,得,计算并比较函数值的大小:

(3)再进一步缩小搜索区间,在上述三个点之间,步长是逐次加倍的,故有,若在之间再插入一点,令,得到等间距的四个点,比较,令函数值最小的点为,它的左、右邻点分为称为,则得到更小的搜索区间,这三点有,且

例:用加步探索法确定的搜索区间,要求选取,步长的倍数.

解:取,令,由于,说明方向正确,取,则,即对三点有,在间插入点,且,比较知,为最小值,故为初始搜索区间。

抛物线法

抛物线法的步骤

(1)在极小点附近,用二次三项式逼近目标函数,若这三个点。且满足,令二次三项式,设

(2)解出的表达式后,通过求得的驻点,用抛物线的极小点来近似的极小点,即

(3)然后从中选出三个点,选择的原则是以目标函数值最小的点作为新的点,其左右两个邻点分别作为新的点,将新得到的点及新的函数值代入公式,可求出极小点新的估计值,继续重复该过程,可以得到一个点列,这个点列可收敛于原问题的极小点。

注意:三个初始点的函数值须满足“高-低-高”的形式,这样才能保证二次三项式的二次项系数,且的极小点都在区间之内,而寻找初始的这三点,可以用加步探索法。

5.无约束问题-搜索方向

前面介绍了一维搜索的几种方法,本节介绍构造无约束问题搜索方向的方法:

后面要介绍的变量轮换法属于直接法,而最速下降法、牛顿法、共轭方向法等属于解析法。

变量轮换法

变量轮换法是把多变量函数的优化问题转化为一系列单变量函数的优化问题来求解。它的基本思路是:认为有利的搜索方向是各坐标轴的方向,因此它轮流按各坐标轴的方向搜索最优点。

从某一个给定点出发,按第个坐标轴的方向搜索时,在个变量中,只有单个变量在变化,其余个变量都取给定点的值保持不变。依次从次单变量的一维搜索,完成了变量轮换法的依次选代.

变量轮换法的步骤

(1)给定初始点

(2)从出发,先沿第1个坐标轴方向进行一维搜索,记求得的最优步长为,则可得到新点,即;再以为起点,沿第2个坐标轴方向进行一维搜索,求得的最优步长为,则可得到新点;依此类推直至个坐标轴方向全部搜索一遍,最后可得到点,此时完成了变量轮换法的一次迭代;

(3)令,返回第二步,即以点作为起点,再沿着各坐标轴方向依次进行一维搜索,一直到所有最新点满足给定的精度为止。

例:用变量轮换法求解,已知初始点,当时停止迭代.

解:第一次迭代:(1)先从初始点出发,沿轴方向进行一维搜索:,由求得步长,故;(2)然后从出发,沿轴方向进行一维搜索:,求得步长,故;(3)再从出发,沿轴方向进行一维搜索,,求得步长,故;因为,故令,再进行新一轮迭代。

第二次迭代:(1),由,求得步长,故;(2),由,求得步长,故;(3)同理,;因为,故为极小点。

变量轮换法的缺点是收敛速度较慢,搜索效率较低。只有对那些具有特殊结构的函数使用起来尚好,但变量轮换法的基本思路非常简单:沿各坐标轴的方向进行搜索。

此方法把一维搜索放到了确定搜索方向的前面,并没有按照前面非线性规划基本思路里的顺序来进行。

最速下降法

最速下降法又称梯度法,它是许多非线性规划算法的一个基础。

最速下降法的原理:考虑问题,假设式中有一阶连续偏导数,有极小点,若现已求得的第此近似值,欲求得度次近似值,需选定搜索方向。设,对点作一阶泰勒展开,其中是比高阶的无穷小量,而,故,由于要找极小点,所以小,所以左边一定是负数,而右边的步长,所以夹角的值一定小于零,因为,其中为向量与向量之间的夹角,显然只有当(即的方向与相反)时目标函数值下降最快,因为,故

最速下降法的步骤

(1)给定初始数据:起始点,给定终止误差,令

(2)求梯度向量模的值:①若,停止计算,此时就是极小点的近似值;②若,转下一步;

(3)构造负梯度方向:

(4)进行一维搜索:无论用哪种方法求得后,令,令,转第二步。

对于一些简单的函数,也可以通过直接求导获得最优步长因子;当搜索方向为最速下降方向(即)时,以为起点的最优步长公式为(其中是黑塞阵)。

最优步长的推导:设有二阶连续偏导数,将它在点作二阶泰勒展开:,将上式中的主要部分记为,即,函数的唯一极值点即为最优步长。

例:用最速下降法求下述函数的极小点,初始点.

解:梯度向量模的值,在,且,精度不满足要求,要进行搜索,先确定搜索方向,再确定步长,这里使用前面的公式计算,,故,因此下一个近四点为,此时,故的极小点为.

最速下降法对初始点的选择要求不高,每一轮选代工作量较少,它可以比较快地从初始点达到极小点附近。但在接近极小点时,最速下降法却会出现锯齿现象,选代产生的点列所循路径是之字形的,每次选代移动的步长很小,收敛速度很慢。因此常常将梯度法与其他方法结合起来使用(比如与牛顿法结合),前期用最速下降法,而当接近极小点时改用牛顿法。

牛顿法

牛顿法是一种函数通近法,它的基本思想是:在极小点附近用点的二阶泰勒多项式来近似目标函数,并用选代点处指向近似二次函数的极小点方向作为搜索方向

牛顿法的原理:设规划问题,其中在点处具有连续偏导数,黑塞阵正定,,记上式中的主要部分为,在附近可用来近似,故可用的极小点来近似的极小点,先求出的驻点:,由的平稳点,故(由指向的向量就是),(对比上式与基本迭代格式中的得出步长为1)。

牛顿法的步骤

(1)选取初始数据:起始点,终止条件,令

(2)求梯度向量,并计算:若,停止计算,此时为极小点;否则转下一步;

(3)构造牛顿方向:

(4)算法迭代:计算,以作为下一轮迭代点,令,转第二步。

例:用牛顿法求的极小点,其中初始点为.

解:求梯度和黑塞阵,于是,且是正定矩阵,故,牛顿方向为,于是,此时相应的梯度为,且,故是所求的极小点。

牛顿法在极小点附近收敛性很好、速度快,而最速下降法在极小点附近收敛速度很差。牛顿法要求初始点离最优解不远,若初始点选得离最优解太远时,牛顿法并不能保证其收敛,甚至也不是下降方向,因此经常是将牛顿法与最速下降法结合起来使用,前期用最速下降法,当选代到一定程度后改用牛顿法,可得到较好的效果。

修正牛顿法

为了克服牛顿法的缺点,人们保留了从牛顿法中选取牛顿方向作为搜索方向,摒弃其步长恒取1的做法,而用一维搜索确定最优步长来构造算法,这种方法通常称做修正牛顿法。

修正牛顿法的步骤

(1)选取初始数据:初始点,终止条件,令

(2)求梯度向量,若,停止计算,此时为极小点;否则转下一步;

(3)构造牛顿方向:

(4)进行一维搜索:求,使,令,令,转第二步。

例:用修正牛顿法求的极小点,初始点.

解:求梯度和黑塞阵,在初始点处有,牛顿方向为,然后沿牛顿方向作一维搜索:,令,得最优步长,然后计算在新迭代点处的梯度:易知,即为所求极小点。

修正牛顿法虽然比牛顿法有了改进,但也有不足之处:一是要计算黑塞阵及其逆矩阵,工作量较大;二是要求选代点处的黑塞阵正定,可是有些函数未必能满足,因而牛顿方向未必是下降方向,也有一些函数的黑塞阵不可逆,因此不能确定出后继点,这些都是修正牛顿法与牛顿法的局限性。

6. 约束极值问题-最优性条件

求解带有约束的极值问题常用的方法有:

考虑只含不等式约束条件下求极小值问题的数学模型:,其中可行域

定义:设,点,向量),若存在一个数,使,都有,则称向量在点处的下降方向

定理:设在点处可微,若存在向量使得,则存在数,使得对每个都有。若在点处可微,当向量满足,则就是在点处的下降方向。

定义:设,若有,则称不等式约束为点起作用的约束,且将下标集称为点起作用下标集。若有,则称不等式约束为点不起作用约束。(显然等式约束都是起作用约束)

是点处的一个可行方向,则存在实数,使得对任意的,都有,即,将处作泰勒展开,得

定义:对于非线性规划问题,如果可行点处,各起作用约束的梯度向量线性无关,则称是约束条件的一个正则点

定义:将既是点的下降方向又是点处的可行方向的向量称为点处的可行下降方向,即有

容易验证,点的可行下降方向与该点处的目标函数负梯度向量之间夹角成锐角,与该点处所有起作用约束的梯度向量之间夹角也都成锐角。

定理:设处可微,若是局部最优解,则点处必不存在可行下降方向。

库恩-塔克条件(Kuhn-Tucker条件)是确定某点为局部最优解的一阶必要条件,只要是最优点就必满足这个条件。但一般来说它不是充分条件,即满足这个条件的点并非最优点,但是对于凸规划,库恩-塔克条件是充要条件。

只含有不等式约束的库恩-塔克条件:设是极小点,那么可能在可行域的内部,也可能在可行域的边界上:

含等式和不等式约束的库恩-塔克条件:对于问题,其中,从而转化为只含不等式约束的问题,其库恩-塔克条件为

例:求下列非线性规划问题的点(库恩-塔克点):.

解:将约束改写为的形式,设所求的点为,则

写出库恩-塔克条件

①如果两个约束均是处不起作用约束,则由,代入库恩-塔克条件解出,但该点不满足,故该点不是可行点;

②若是起作用约束,是不起作用约束,则由,代入库恩-塔克条件解出,可知是可行点,且满足库恩-塔克条件,又是一个正则点,故它是一个点;又因为也成立,此时和第一张情形一样,该点也不是可行点;

③若是不起作用约束,是起作用约束,则由,代入库恩-塔克条件解出,当时不满足的条件,当时与第一种情形一样;

④若两个约束都是起作用的,此时,于是库恩-塔克条件化简为,但是得出的解不满足,故舍去;

综上,本题目的库恩-塔克点为

本题的目标函数是凸函数,而都是凹函数,故本题是凸规划,而对于凸规划而言,库恩-塔克条件也是充分的,因此也是本题的全局极小点。

7. 约束极值问题-可行方向法

可行方向法是用一个线性规划来确定搜索方向的方法,我们将约束条件分为线性和非线性的两种情形来讨论。

约束条件为线性

考虑,其中是可微函数,矩阵,矩阵,,即问题有个线性不等式约束,有个线性等式约束。

定理:设是问题的一个可行解,且,其中(即将的起作用约束部分的系数矩阵(不一定是方阵)作为、右端项作为,不起作用约束的系数矩阵作为、右端项作为),则下列结论成立:

可行方向法计算步骤(约束条件为线性函数时):

(1)给定初始可行点,允许误差,令

(2)在点处把分解成,使得

(3)判断是否为问题可行域的内点;

(4)求可行下降方向就是要求解问题,设得到的最优解为,若,则停止迭代,否则转第五步;

(5)先计算的上限,再作一维搜索,求得最优解,令

(6)令,返回第二步。

搜索方向和步长计算步骤的推导:

根据定理,要寻找问题可行点的一个可行下降方向,相当于求解如下的一个线性规划问题,问题一(其中把的各分量限制在之间是为了讨论方便,我们只关心它的方向而非大小),显然是其中一个可行解,故目标函数的最优值,当时,则为可行下降方向;当时,则为库恩-塔克点。

确定了搜索方向,然后就是步长的确定了。假定是第次迭代点的出发点,其可行下降方向为,则后继点,为使,且的值尽可能小,求解一维搜索问题,问题二,其中

考虑到线性约束,那么求解问题二时首先求解问题三,因为是可行方向,则,而是可行点,则,说明问题三中的第2个约束必定满足(因为),可不再考虑它。

在问题三的基础上,如果在点处将不等式约束分为起作用约束和不起作用约束,得问题四,其中,因为是可行方向,根据前面定理,再设,故问题四中的第1个条件自然满足,可不再考虑它。

根据问题三、四的讨论知,问题二可以被简化为问题五,要使步长尽可能大,就是要求的上界,的上界由下面的公式给出:,此时问题二再次被化简为问题六

综上,对于约束是线性函数的非线性规划问题,若已知一个迭代点后,可由求解问题一得到可行下降方向,再由问题六求解该方向上的步长

例:用可行方向法求解,取.

解:

第一次迭代:

代入约束条件,因此第1、2个约束为点的起作用约束,故

先确定搜索方向,令,求解线性规划,因为,故线性规划进一步简化为,用单纯形法解得,因此

再作一维搜索()来确定的上界,求出,故

为确定步长,还要求解下述规划,故最优解和最优值为,故,且,但是,还要进行下一次迭代;

第二次迭代:

寻找可行下降方向:,因此第2个约束是点的起作用约束,故

确定搜索方向:令,求解线性规划,解得,相应的目标函数值,因为,此时已经没有可行下降方向了,即已经达到极值点(由于,该点也是库恩塔克点),故即为所求。

约束条件非线性

考虑非线性规划,其中)均为可微函数。

定理:设是问题的一个可行解,是点处起作用约束下标集,若)均为可微函数,)在点处连续,如果,则是可行下降方向。

上述定理中的条件等价于用方程组求向量,满足这一条件的可行下降方向和数一般有很多个,我们希望求出能使目标函数值下降最多的方向

则求可行下降方向的问题可转化为求下列线性规划问题:

得到与可行下降方向后,沿方向进行一维搜索确定,其中

可行方向法计算步骤(约束条件为非线性函数时):

(1)给定初始可行点,允许误差,令

(2)确定点处的起作用下标集

(3)判断是否是问题可行域的内点:

(4)确定搜索方向,即求解线性规划问题,设得到的最优解为,若,停止迭代,得到极小点,否则以为搜索方向转第五步;

(5)先计算的上限,然后作一维搜索,求得最优解,令

(6)令,返回第二步。