§4 条件极值问题解法
本节讨论目标函数
在一组不等式
(或
)
或等式
约束条件下的极值问题解法.这种问题称为条件极值问题,当目标函数和约束条件关于自变量都是线性时,称为线性规划问题,否则称为非线性规划问题.
条件极值问题就是要求在维欧氏空间
的一个由不等式约束条件所限定的区域:
上求一点,使得目标函数
达到极小值(或极大值)
,即
其中,
是定义在
的某一开集
上的具有一阶连续偏导数的实值函数.
因为在同样的约束条件下,极小和极大只是目标函数相差一符号,以后限于讨论极小的情况.
若某一,有
则称为
的内点,若
,存在一个
使
则称为
的边界点.
[线性规划问题的可行解与极小可行解] 线性规划问题就是求目标函数
(1)
在约束条件
(
)
(
)
(
)
(
)
(
)
(
)
(
)
下的极小值,其中有个等式约束条件,其余是不等式约束条件.假定
.
对形如()的约束条件,则引进松驰变量
,把它变为等式
对形如()的约束条件,则引进松驰变量
,把它变为等式
(
)
松驰变量并不出现在目标函数(1)中,它的引进并不影响问题的最优解,它把所有约束条件(除了外)化成统一的等式形式
(3)
式中是
维矢量,它包含所有原来的变量和松驰变量,
是
维常数矢量,而
是
矩阵,因此(3)表示
个未知量的
个方程的线性方程组.
所以线性规划问题可以表述为如下三种等价形式:
求目标函数
(
)
在约束条件
(
)
(
) (
)
下的极小值,假定 (
).
求目标函数
(4b)
在约束条件
(5b)
(6b)
下的极小值,其中是一行矢量,
是一列矢量,
为
矩阵(
),
是一列矢量,假定
.
求目标函数
(4c)
在约束条件
(5c)
(6c)
下的极小值,其中是矩阵A的第
列矢量
,假定
称为目标函数(4)的价格系数.
定义1 满足条件(5)和(6)的矢量称为线性规划问题的可行解.
定义2 若可行解的分量中至多有
个
,则称
为基本可行解.
定义3 若一个基本可行解恰有
个分量
,则称
为非退化的基本可行解.
定义4 使目标函数(4)达到极小值的可行解称为极小可行解(简称极小解).
集合
是一凸集,它有有限个顶点,若线性规划中目标函数(4)有极小值,则必可在其凸集上某一顶点达到.
假设线性规划问题是可行的,每一基本可行解都是非退化的,并且给定一基本可行解和与它关联的一组线性无关矢量
则有
式是所有,
为目标函数的价格系数,
为目标函数相应于给定解
的数值.由于
是线性无关的,存在
满足
(
)
并且定义
(
)
式中为相应于
的价格系数.
定
理 1 如果对任一固定的,条件
成立,那末可以构造一组可行解使得对组中的任一可行解都有
,其中
的下限或者是有限的或者是无限的(
是目标函数相应于可行解组中某一可行解的数值.)
定理2 如果对任一基本可行解,条件
对所有
成立,那末
是一极小可行解.
[单纯形法] 根据以上两个定理解线性规划问题的单纯形法就是从已知的某一基本可行解(它是满足约束条件的一切点即可行解所组成的凸集的一个顶点)出发,确定这点是否使目标函数达到极小值.如果不是,依次构造新的基本可行解(它们是凸集
的相邻顶点),其相应的目标函数值小于或等于前面的数值.经过有限步(通常在
和
之间)就可得到极小解.所以单纯形法实际是凸集顶点的一个迭代方法.下面分两种情形叙述.
假设矩阵
的
个列矢量
包含
个单位矢量并集中在一起组成一个
阶单位矩阵,不妨设这些列矢量
,命
(
为
阶单位矩阵)
称为容许基底.由于,而且
的所有元素都是非负的,因此有初始基本可行解
式中
列表如下:
表 1
i |
基底 |
|
|
|
|
… |
|
… |
|
|
… |
|
… |
|
… |
|
|
|
|
|
|
|
… |
|
… |
|
|
… |
|
… |
|
… |
|
1 |
|
|
|
1 |
0 |
… |
0 |
… |
0 |
|
… |
|
… |
|
… |
|
2 |
|
|
|
0 |
1 |
… |
0 |
… |
0 |
|
… |
|
… |
|
… |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
… |
1 |
… |
0 |
|
… |
|
… |
|
… |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
… |
0 |
… |
1 |
|
… |
|
… |
|
… |
|
|
|
|
|
0 |
0 |
… |
0 |
… |
0 |
|
… |
|
… |
|
… |
|
由于,因此表中
.表中
元素和
在它们所在列的第
行出现.对基底矢量
总是等于零.有了表1后就可对它进行如下的单纯形法迭代:
(1) 检验是否所有的.如果所有
,那末
是极小解,相应的目标函数值为
.
(2) 如果某个,则选择对应于
的矢量进入基底.
(3) 把对应于
的矢量从基底中消去.如果所有的
,那末目标函数值无界.
(4) 为了得到新解,新矢量
和相应的
,对表1中行
和列
的每一元素用下面的主元素(
)消去法公式进行变换
其中
每迭代一次就得到一新的基本可行解,重复步骤(1)~(4)直到求得极小解或者确定一无界解.
对表1进行上述迭代一次后就得到下表:
表 2
|
基底 |
|
|
|
|
… |
|
… |
|
|
… |
|
… |
|
… |
|
|
|
|
|
|
|
… |
|
… |
|
|
… |
|
… |
|
… |
|
1 |
|
|
|
1 |
0 |
… |
… |
… |
0 |
|
… |
|
… |
0 |
… |
|
2 |
|
|
|
0 |
1 |
… |
|
… |
0 |
|
… |
|
… |
0 |
… |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
… |
|
… |
0 |
|
… |
|
… |
1 |
… |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
… |
|
… |
1 |
|
… |
|
… |
0 |
… |
|
|
|
|
|
0 |
0 |
… |
|
… |
0 |
|
… |
|
… |
0 |
… |
|
假设矩阵A不包含一个
阶单位矩阵.这时可采用下面的人工基底法:
引进人工变量(
)将线性规划问题的系统扩大为:
极小化
满足条件
和,其中
为一未定的大的正数(不必指定
的数值).矢量
形成扩大系统的一个基底(人工基底).
对扩大了的问题,第一个可行解为
相应的目标函数值为.由于基底组成一个单位矩阵,所以
(
)
列表如下:
表
3
|
基底 |
|
|
|
|
… |
|
… |
|
|
… |
|
… |
|
|
|
|
|
|
|
… |
|
… |
|
|
… |
|
… |
|
1 |
|
|
|
|
|
… |
|
… |
|
1 |
… |
0 |
… |
0 |
2 |
|
|
|
|
|
… |
|
… |
|
0 |
… |
0 |
… |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
… |
|
… |
|
0 |
… |
1 |
… |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
… |
|
… |
|
0 |
… |
0 |
… |
1 |
|
|
|
0 |
|
|
… … |
|
|
|
0 0 |
… … |
0 0 |
… … |
0 0 |