最优化方法
例:某计算机公司提供大型计算机系统,有A, B, C三个技术团队
-高端系统
-中端系统
2009年度,A队可工作10个月,B队8个月、C队7个月
问:怎样的销售策略能使总利润最大?
可设销售x_1个中端系统,x_2个高端系统
目标函数
从实际中总结出来的LP形式不完全一样:
标准LP问题形式:
min z=cx
s.t. Ax=b, x≥0
将LP问题标准化:
目标函数的转换 \max\ z→\min\ (-z)
约束条件的转换(引入松弛变量)
定义:可行区域是所有满足约束条件的可行点的集合,记为D
D={x| Ax=b, x≥0}
若dim(D)= n-m, D’为D的界面,且dim(D’)=n-m-k,则|Q|≥k.
如果一个方向d不能表成两个方向的正线性组合,就成d是C的极方向(extreme direction)。
— 刘迎春 2010/06/16 15:09
假定rank(A)=m,则A中必有m个线性无关的列向量——构成满秩方阵B,A中其余各列组成子阵N,即A=(B, N)。相应的x=(xB, xN),则Ax=b可改写成
BxB+NxN=b. 因为B为满秩,则B-1存在,那么 xB=B-1b-B-1NxN
任给一组值xN,则可得到相应的xB,
(xB, xN)
为Ax=b的一个解。 令xN=0, 则xB=B-1b, x=(B-1b, 0)称为约束方程组的基本解。
基本解不一定满足非负条件,故不一定是可行解。对于非负的基本解,称为基本可行解。
基本可行解x,若它所有的基变量都取正值,则x为非退化的(non-degenerated); 反之,为退化的。 对应一个LP问题,如果它的所有基本可行解都是非退化,就说该问题是非退化的,否则为退化的。 (
— 刘迎春 2010/06/16 15:10
(老师PPT中阐述很清楚)
若LP问题
minz= cx s.t.Ax= b x≥ 0
存在有限最优值(即有最优解),则最优值必在可行区域D的某个极点上达到。并且,目标函数存在有限最优值的充要条件是对D的所有极方向dj,均有cdj≥0. (这可以从老师前面讲的例题中理解)
— 刘迎春 2010/06/13 09:14
假定rank(A)=m<n,且假定已找到一个非退化基本可行解,即找到一个基B。则A{\mathbf x}={\mathbf b}可写成
下面将证明{\hat {\mathbf x}}是可行解。带入式(5)并注意到{\hat {\mathbf x}}_N=(0,\dots,θ,0,\dots,0),得
下面再证明{\hat {\mathbf x}}是基本解。{\hat {\mathbf x}}的各分量为
现在即证明{\mathbf a}_1,\dots,{\mathbf a}_{r-1},{\mathbf a}_k,{\mathbf a}_{r+1},\dots,{\mathbf a}_m线性无关。
反证法。因为\{{\mathbf a}_1, \dots, {\mathbf a}_m\}是线性无关的,所以{\mathbf a}_k必然是其余的m-1个向量的线性组合。即{\mathbf a}_k=\sum_{i=1,i\neq r}^my_i{\mathbf a}_i
又\bar {\mathbf a}_k=B^{-1}{\mathbf a}_k,故{\mathbf a}_k=B{\bar {\mathbf a}}_k=\sum_{i=1}^m{\bar a}_{ik}{\mathbf a}_i。
两式相减,得
这里,\mathbf ζ称之为检验向量。在迭代过程中,如果\mathbf ζ有不止一个正分量,则为了使目标函数下降得较快,一般取最大的分量ζ_k所对应的列向量{\mathbf a}_k进入基。
根据θ和\hat {\mathbf x}的构造方式可知,得到改进的基本可行解。即使原来的非基变量x_k变成取正值的基本变量,同时使原来的基本变量x_r值为零(变成非基变量)。等价地,基B=[{\mathbf a}_1,\dots,{\mathbf a}_m]变成另一个基\hat B=[{\mathbf a}_1,\dots,{\mathbf a}_{r-1},{\mathbf a}_k,{\mathbf a}_{r+1},\dots,{\mathbf a}_m]。
换基变换
x_k称为进基变量,x_r称为离基变量。
在基B下,典式的系数增广矩阵为
x_r和x_k的地位互换。第k列通过初等变换变成单位向量{\mathbf e}_r。
最后一行正式基\hat B所对应的基本可行解。
设原问题为
设原问题为
若单纯形表中右端向量存在分量为0,即出现退化解的情况下,可能出现循环。为了避免循环,需要再补充一些旋转规则。
字典序方法
非零向量{\mathbf x},并且第一个非零分量是非负的,称为按字典序非负,记为{\mathbf x}\succeq {\mathbf 0}。对向量{\mathbf x},{\mathbf y},若{\mathbf x} - {\mathbf y}\succeq {\mathbf 0},则称{\mathbf x}按字典序大于等于{\mathbf y}。
若一组{\mathbf x}^i,有{\mathbf x}^t,使对所有{\mathbf x}^i,均有{\mathbf x}^i\succeq {\mathbf x}^t,则称{\mathbf x}^t为该组向量中按字典序最小的。记为:{\mathbf x}^t = lex \min {\mathbf x}^i。
字典序法就是在选定了进基变量{\mathbf x}_k后,令\frac{ {\mathbf P}_r }{ {\bar a}_{rk} } = lex\min\{ \frac{{\mathbf P}_i}{{\bar a}_{ik}}|{\bar a}_{ik}>0,i=1,\dots,m \},其中{\mathbf P}_i为({\bar {\mathbf b}}, B^{-1})的第i行。
Bland规则
* Bland规则的优点是简单易行,但缺点是只考虑最小下标,而不考虑目标函数值下降的快慢。故其效率比字典序或原来单纯形法低。 * 在实际中,退化是常见的,但退化不一定产生循环。事实上,产生循环是较罕见的。
当LP问题的规模很大时,如何减少存储量和计算时间,就是一个必须加以考虑的问题。在实际中,大多采用修改单纯形法。
逆矩阵法
一般单纯形表为
逆矩阵法对每一张单纯形表,仅存贮下列数据
上表称为修改单纯形表。
根据这张表和原始数据进行迭代计算。由ζ_k = \max\{ {\mathbf w}{\mathbf a}_j - c_j|x_j非基变量 \}确定x_k为进基变量,再求{\bar {\mathbf a}}_k = B^{-1} {\mathbf a}_k,用最小比确定离基变量x_r,得到新的基\hat B,最后构造对应于\hat B的修改单纯形表。如果每一次迭代都必须重构造B^{-1},则计算量显然难以令人满意。
定理:对应基B的修改单纯形表的右边添加一列\begin{pmatrix} ζ_k \newline {\bar {\mathbf a}}_k \end{pmatrix},以{\bar {\mathbf a}}_{rk}为转轴元旋转,就得到了对应于基\hat B的修改单纯形表。
对偶性
设A为m×n阶矩阵,{\mathbf b}∈E^{m},{\mathbf c}∈E^{m},{\mathbf x}∈E^{m},则{\mathbf x}^{*}为LP问题
对于标准形式的LP问题的K-L条件,只要将A{\mathbf x}={\mathbf b}改写成
一个基本可行解
(Dual Simplex Method)1954年美国数学家C.莱姆基提出对偶单纯形法。单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解,直到检验数满足最优性条件为止。对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解。在迭代过程中始终保持基解的对偶可行性,而使不可行性逐步消失。设原始问题为min{cx|Ax=b,x≥0},则其对偶问题(Dual Problem)为 max{yb|yA≤c}。当原始问题的一个基解满足最优性条件时,其检验数cBB-1A-c≤0。即知y=cBB-1(称为单纯形算子)为对偶问题的可行解。所谓满足对偶可行性,即指其检验数满足最优性条件。因此在保持对偶可行性的前提下,一当基解成为可行解时,便也就是最优解。