最优化方法

• 线性规划
• 非线性优化

• 线性规划，张建中，许绍吉，科学出版社
• 最优化理论与方法，袁亚湘，孙文瑜，科学出版社

例：某计算机公司提供大型计算机系统，有A, B, C三个技术团队
-高端系统

• 每套售后的利润400万元
• 需用A、B两个技术团队协作实施
• A团队2个月，B团队1个月；

-中端系统

• 每套售后的利润300万元
• 需用A, B, C三个技术团队协作实施
• 每个团队各需1个月

2009年度，A队可工作10个月，B队8个月、C队7个月
问：怎样的销售策略能使总利润最大？
可设销售x_1个中端系统，x_2个高端系统
目标函数

约束条件 附加条件：x_1和x_2为整数
在一组线性的等式或不等式约束下，求一个线性函数的最小值或最大值。
形式化的定义：
即：
min c^Tx
s.t. Ax≤b, x≥0
其中，c为价值向量，A为约束矩阵，b为右端向量
x满足约束条件成为可行解或可行点
D所有可行点的集合称为可行区域
LP问题：
D=∅，无解或不可行
D≠∅，但目标函数在D上无上界：无界
D≠∅，且目标函数有限的最优解：有最优解
线性规划的图解法：
线性规划可用下图来解：

线性规划在Matlab中的实现方法
基本函数形式为
linprog(c, A, b) 返回值是向量x的值
调用举例：
[x,fval]=linprog(c, A, b, Aeq, beq, LB, UB, X0, OPTIONS)
fval返回目标函数的值，
Aeq、beq对应等式约束，AeqX = beq
LB、UB分别是变量X的下界和上界，X0是X的初始值
OPTIONS是控制参数。
例： 约束条件： Matlab代码： c=[2,3,-5];
a=[-2,5,-1];
b=-10;
aeq=[1,1,1];
beq=7;
x=linprog(-c,a,b,aeq,beq,zeros(3,1))
value=c'*x

从实际中总结出来的LP形式不完全一样：

• 目标函数是最大值或最小值，
• 约束条件是等式约束或不等式约束，
• 变量有上界或下界或无界

标准LP问题形式：
min z=cx
s.t. Ax=b, x≥0 将LP问题标准化： 目标函数的转换 \max\ z→\min\ (-z)
约束条件的转换（引入松弛变量）

变量的非负约束：

定义：可行区域是所有满足约束条件的可行点的集合，记为D

D={x| Ax=b, x≥0}

• 仿射集：对于集合S⊆En，如果对任意x, y∈S, λ∈E1, 都有λx+(1-λ)y∈S,则S为仿射集。
• 凸集：对任意的x, y∈C,λ∈(0,1)，有 λx＋(1-λ)y∈C，则C为凸集。
• 界面：可行区域D的子集D’为D的一个界面当且仅当存在指标集合Q⊆{1,…,n},使得D’={x|Ax=b,x≥0,且xj=0当j∈Q}

若dim(D)= n-m, D’为D的界面，且dim(D’)=n-m-k，则|Q|≥k.

• 极点：凸集C的1维界面称为边（edge）, 0维界面称为极点(extreme point)。若两个极点在同一条边上，称它们是相邻的。
• 极方向：设C≠Ø为En中的一个凸集，d∈En,d≠0。若对任一x∈C及λ>0，均有x+λd∈C，则称d为C的一个方向。

如果一个方向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

• 基本定理1（表示定理）

（老师PPT中阐述很清楚）

• 基本定理2

若LP问题

  minz= cx
 s.t.Ax= b
 x≥ 0

存在有限最优值（即有最优解），则最优值必在可行区域D的某个极点上达到。并且，目标函数存在有限最优值的充要条件是对D的所有极方向dj,均有cdj≥0. （这可以从老师前面讲的例题中理解）

— 刘迎春 2010/06/13 09:14

• 主要思想：先找一个可行解，判断它是否是最优解。若不是，就找一个更好的基本可行解，再进行检验。如此迭代，直至最后找到最优解，或判定无界。
• 两个主要问题：
  • 寻找初始解
  • 如何判别和迭代（先考虑）

— 高海东 2010/06/24 08:24

假定rank(A)=m<n，且假定已找到一个非退化基本可行解，即找到一个基B。则A{\mathbf x}={\mathbf b}可写成

记 则上式(1)可写成{\mathbf x}_B + {\bar N}{\mathbf x}_N={\bar b}~~~~(2)。
显然，不同的基对应的方程表达式也不同。式（2）称为基B的典则方程组，简称典式。 若{\bar {\mathbf b}}\geq{\mathbf 0}，则式(2)就对应着基本可行解{\bar {\mathbf x}}= \begin{pmatrix} {\bar {\mathbf b}}\newline {\mathbf 0}
\end{pmatrix} 。 将目标函数也做相应的变换， 用z_0表示在基本可行解{\bar {\mathbf x}}处的目标函数值，则有z_0={\mathbf c}{\bar {\mathbf x}}={\mathbf c}_B{\bar {\mathbf b}}（即上式的常数项） 因为{\bar {\mathbf a}}_1,\dots,{\bar {\mathbf a}}_m是线性无关向量，故当j=1,\dots,m时，{\mathbf c}_B{\bar {\mathbf a}}_j - c_j=0。 引入记号ζ_j={\mathbf c}_B{\bar {\mathbf a}}_j - c_j,h=1,\dots,n或用向量形式ζ={\mathbf c}_BB^{-1}A - {\mathbf c}=({\mathbf ζ}_B,{\mathbf ζ}_N)=({\mathbf 0},{\mathbf c}_BB^{-1}N - {\mathbf c}_N)则式（3）改写成z={\mathbf c}_B{\bar {\mathbf b}} - {\mathbf ζ}{\mathbf x}。其中{\mathbf ζ}={\mathbf c}_BB^{-1}A - {\mathbf c}=({\mathbf ζ}_B,{\mathbf ζ}_N)=({\mathbf 0}, {\mathbf c}_BB^{-1}N-{\mathbf c}_N)。
经过变量变换后，LP问题可叙述成
定理2.1：若（4）中\mathbf ζ \leq {\mathbf 0}，则\bar {\mathbf x}为最优解。
定理2.2：若（4）中\mathbf ζ存在某一分量ζ_k>0且\bar {\mathbf a}_k \leq {\mathbf 0}，则原问题无解。
定理2.3：若（4）中有ζ_k>0且\bar {\mathbf a}_k至少存在一个正分量，则能找到基本可行解\hat {\mathbf x}，使得{\mathbf c}{\hat {\mathbf x}} < {\mathbf c}{\bar {\mathbf x}}。
那现在我们就来构造（更好的基本可行解）\hat {\mathbf x}。令

---

下面将证明{\hat {\mathbf x}}是可行解。带入式（5）并注意到{\hat {\mathbf x}}_N=(0,\dots,θ,0,\dots,0)，得

根据θ的构造，显然可知{\hat {\mathbf x}}\geq {\mathbf 0}，故其是可行解。

---

下面再证明{\hat {\mathbf x}}是基本解。{\hat {\mathbf x}}的各分量为

由于这里{\hat x}_r = 0而{\hat x}_k > 0，只需证明{\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}_{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。
两式相减，得

因为{\bar a}_{rk} \neq 0，故\{{\mathbf a}_1, \dots, {\mathbf a}_m\}线性有关，引出矛盾。
最后

1. 找初始的可行基
2. 求出对应的典式
3. 求ζ_k=\max\{ ζ_j|j=1,\dots,n \}
4. 若ζ_k\leq 0，停止。已找到最优解\mathbf x = \begin{pmatrix} {\mathbf x}_B \newline {\mathbf x}_N \end{pmatrix} = \begin{pmatrix} {\bar {\mathbf b}} \newline {\mathbf 0} \end{pmatrix}及最优值z={\mathbf c}_B{\bar {\mathbf b}}
5. 若{\bar {\mathbf a}}_k\leq {\mathbf 0}，停止，原问题无解
6. 求最小比\frac{ {\bar b}_r }{ {\bar a}_{rk} }=\min\{ \frac{{\bar b}_i}{{\bar a}_{ik}} | {\bar a}_{ik}>0 \}
7. 以{\mathbf a}_k代替{\mathbf a}_{Br}得到新的基，回到2.

这里，\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。

1. 第r行{\bar {\mathbf a}}_r^T除以{\bar a}_{rk}，{\hat {\mathbf a}}_r^T = {\bar {\mathbf a}}_r^T / {\bar a}_{rk}
2. 对第i,i\neq r行{\bar {\mathbf a}}_i^T，{\hat {\mathbf a}}_r^T = {\bar {\mathbf a}}_i^T - {\bar {\mathbf a}}_r^T {\bar a}_{ik}，即第i行减去新的第r行{\bar {\mathbf a}}_r^T乘以{\bar a}_{rk}

最后一行正式基\hat B所对应的基本可行解。

换基时，目标函数z={\mathbf c}_B{\bar {\mathbf b}} - ( {\mathbf c}_B{\bar N} - {\mathbf c}_N ){\mathbf x}_N也要做想应的调整，即将B换成\hat B。将上式的等价形式
z + ( {\mathbf c}_B{\bar N} - {\mathbf c}_N ){\mathbf x}_N ={\mathbf c}_B{\bar {\mathbf b}}，或者 z + {\mathbf ζ}_N{\mathbf x}_N = z_0
看成一个方程，放在典式中一同进行初等变换。

上述变换又称为旋转（Pivot），类似于解线性方程组的主元消元法。单纯形表可简记为

设原问题为

引入m个人工变量{\mathbf x}_a=(x_{n+1},\dots,x_{n+m})^T，考虑如下辅助问题
其中{\mathbf 1}=(1,\dots,1)。设原问题的可行域为D，辅助问题的可行域为D^'，显然{\mathbf x}\in D⇔\begin{pmatrix}{\mathbf x}\newline {\mathbf 0}\end{pmatrix}\in D^'。而\begin{pmatrix}{\mathbf x}\newline {\mathbf 0}\end{pmatrix}\in D^' ⇔ \min g = 0。
对于辅助问题来说，一个基本可行解是\begin{pmatrix}{\mathbf x}\newline {\mathbf x}_a\end{pmatrix} = \begin{pmatrix}{\mathbf 0}\newline {\mathbf b}\end{pmatrix}，于是可进行单纯形迭代求解，其结果有两种可能：
1)\min g>0，说明D=\emptyset。
2)\min g=0，这是自然有{\mathbf x}_a=0，把它除去后记得到原问题的一个可行解。

• 若此时所有人工变量都是非基变量，则解为基本可行解。
• 否则，进行旋转变换消去基本量中的人工变量。设基变量x_r为人工变量，
  • 取第r行的前n个元素中不为零的元素{\bar a}_{rs}为转轴元进行变换，则非人工变量x_5进入基变量，同时从基本量消除了人工变量x_r。
  • 若第r行的前n个元素都为零，则直接去掉该行以及对应的人工变量。

设原问题为

引入{\mathbf x}_a \in {\mathbb R}^m及足够大的整数M，得到新问题如下
其中{\mathbf 1}=(1,\dots,1)。只要M取得足够大，那么可以说x是原问题的最优解⇔\begin{pmatrix}{\mathbf x}\newline {\mathbf 0}\end{pmatrix}是新问题的最优解。而新问题就初始解\begin{pmatrix}{\mathbf 0}\newline {\mathbf b}\end{pmatrix}，因此总可以用单纯形法求解。

若单纯形表中右端向量存在分量为0，即出现退化解的情况下，可能出现循环。为了避免循环，需要再补充一些旋转规则。

• 字典序方法
• Bland规则

---

字典序方法 非零向量{\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规则

• 选下标最小的整检验数ζ_k所对应的非基变量x_k作为进基变量。
• 离基变量x_l的确定：如果同时有几个\frac{b_r}{{\bar a}_{rk}}达到最小，就选其中下标最小的那个基变量作为离基变量。即

* 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的修改单纯形表。

对偶性

• 对于每一个线性规划P，总存在着另一个线性规划D，两者之间存在着密切的联系，人们可以通过求解对偶规划D来获得原规划P的最优解。

• 定理

设A为m×n阶矩阵，{\mathbf b}∈E^{m}，{\mathbf c}∈E^{m}，{\mathbf x}∈E^{m}，则{\mathbf x}^{*}为LP问题

的最优解的充要条件是存在{\mathbf w}∈E^{m}，{\mathbf v}∈E^{n}，使得下列K-T条件得到满足 若将{\mathbf v}消去（利用{\mathbf c}-{\mathbf w}A - {\mathbf v}={\mathbf 0}），可得到K-T条件的另外一种形式

对于标准形式的LP问题的K-L条件，只要将A{\mathbf x}={\mathbf b}改写成

, 可推出相应的K-T条件

一个基本可行解

为最优的充要条件是检验向量ζ≤0，和K-T是什么关系呢？
由{\mathbf v}{\mathbf x}={\mathbf v}_{B}{\mathbf x}_{B}+{\mathbf v}_{N}{\mathbf x}_{N}=0,且{\mathbf x}_{B} > 0，可知{\mathbf v}_{B} = 0。
条件{\mathbf c}-{\mathbf w}A-{\mathbf v}={\mathbf 0}可改写为({\mathbf c}_{B}，{\mathbf c}_{N})-{\mathbf w}({\mathbf B},N)-({\mathbf v}_{B},{\mathbf v}_{N})=({\mathbf 0},{\mathbf 0})，于是有 ⇒ 这就是说，若给一个基本可行解x，如果取{\mathbf v}_B=0,{\mathbf w}={\mathbf c}_{B}B^{-1},{\mathbf v}_N={\mathbf c}_N-{\mathbf w}N={\mathbf c}_N-{\mathbf c}_{B}B^{-1}N，的K-T条件除了{\mathbf v}≥{\mathbf 0}外，其余条件都已满足。而根据v的取法，易知v≥{\mathbf 0}⇔ζ≤{\mathbf 0}.

• 对偶问题可被看做是原始问题的“行列转置”

• 对偶问题是
• 其中

（Dual Simplex Method）1954年美国数学家C.莱姆基提出对偶单纯形法。单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解，直到检验数满足最优性条件为止。对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解。在迭代过程中始终保持基解的对偶可行性，而使不可行性逐步消失。设原始问题为min{cx|Ax=b，x≥0}，则其对偶问题（Dual Problem）为 max{yb|yA≤c}。当原始问题的一个基解满足最优性条件时,其检验数cBB-1A-c≤0。即知y＝cBB-1（称为单纯形算子）为对偶问题的可行解。所谓满足对偶可行性，即指其检验数满足最优性条件。因此在保持对偶可行性的前提下，一当基解成为可行解时，便也就是最优解。