====== 第十三课 ======
**最优化方法**
====== 内容 ======
* 线性规划
* 非线性优化
====== 主要参考书： ======
* 线性规划，张建中，许绍吉，科学出版社
* 最优化理论与方法，袁亚湘，孙文瑜，科学出版社
====== 基本理论 ======
===== 问题定义 =====
例：某计算机公司提供大型计算机系统，有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$个高端系统\\
目标函数\max\ z=4x_1+3x_2
约束条件
2x_1+x_2\le10
x_1+x_2\le8
x_2\le7
x_1,x_2\ge0
附加条件：$x_1$和$x_2$为整数\\
在一组线性的等式或不等式约束下，求一个线性函数的最小值或最大值。\\
形式化的定义：\\
\min\ c_1x_1+...+c_nx_n
s.t.
a_{11}x_1+...+a_{1n}x_n\le b_1
...
a_{m1}x_1+...+a_{mn}x_n\le b_m
x_1,...,x_n \ge 0
即：\\
min **cTx**\\
s.t. A**x**≤**b**, **x**≥**0**\\
其中，**c**为价值向量，**A**为约束矩阵，**b**为右端向量\\
**x**满足约束条件成为可行解或可行点\\
D所有可行点的集合称为可行区域\\
LP问题：\\
D=∅，无解或不可行\\
D≠∅，但目标函数在D上无上界：无界\\
D≠∅，且目标函数有限的最优解：有最优解\\
线性规划的图解法：\\
线性规划可用下图来解：\\
{{:keynote:capture.png|}}\\
线性规划在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是控制参数。\\
例：\max\ z=2x_1+3x_2-5x_3
约束条件：x_1+x_2+x_3=7
2x_1-5x_2+x_3\ge10
x_1,x_2,x_3\ge0
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\\
--- //[[1@1|梁中岩]] 2010/06/12 21:10//
===== 标准LP问题 =====
从实际中总结出来的LP形式不完全一样：\\
* 目标函数是最大值或最小值，
* 约束条件是等式约束或不等式约束，
* 变量有上界或下界或无界
标准LP问题形式：\\
min z=**cx**\\
s.t. A**x**=**b**, **x**≥**0**
将LP问题标准化：
目标函数的转换 $\max\ z->\min\ (-z)$\\
约束条件的转换（引入松弛变量）
\sum_{j=1}^{n}{a_{ij}x_j\le b_{i}}
<=>
\sum_{j=1}^{n}{a_{ij}x_j+x_{n+i}}=b_i, x_{n+i}\ge 0
变量的非负约束：
x_j\ge l_j
<=>
y_j\ge0, y_j=x_j-l_j
x_j自由变量
<=>u_j\ge0, v_j\ge0, x_j=u_j-v_j
--- //[[1@1|梁中岩]] 2010/06/12 21:10//
====== 可行区域 ======
定义：可行区域是所有满足约束条件的可行点的集合，记为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）。
--- //[[1@1|刘迎春]] 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问题，如果它的所有基本可行解都是非退化，就说该问题是非退化的，否则为退化的。
(tip退化将在后续的单纯形方法中用到。)
--- //[[1@1|刘迎春]] 2010/06/16 15:10//
====== 线性规划基本定理 ======
* 基本定理1（表示定理）
（老师PPT中阐述很清楚）
* 基本定理2
若LP问题
minz= cx
s.t.Ax= b
x≥ 0
存在有限最优值（即有最优解），则最优值必在可行区域D的某个极点上达到。并且，目标函数存在有限最优值的充要条件是对D的所有极方向dj,均有cdj≥0.
（这可以从老师前面讲的例题中理解）
--- //[[1@1|刘迎春]] 2010/06/13 09:14//
======2.单纯形方法======
=====2.1基本单纯形方法=====
* **主要思想**：先找一个可行解，判断它是否是最优解。若不是，就找一个更好的基本可行解，再进行检验。如此迭代，直至最后找到最优解，或判定无界。
* 两个主要问题：
* 寻找初始解
* 如何判别和迭代（先考虑）
--- //[[1@1|高海东]] 2010/06/18 00:00//
--- //[[1@1|高海东]] 2010/06/24 08:24//
=====判别和迭代=====
假定$rank(A)=m
{\mathbf x}_B + B^{-1}N{\mathbf x}_N=B^{-1}{\mathbf b}~~~~(1)
记
\[B=(a_1,\dots,a_m)\]
\[{\bar {\mathbf a}}_j=B^{-1}{\mathbf a}_j=({\bar a}_{1j},\dots,{\bar a}_{mj})^T,j=1,\dots,n\]
\[{\bar {\mathbf b}}=B^{-1}{\mathbf b}=({\bar a}_1,\dots,{\bar b}_m)^T\]
\[{\bar N}=B^{-1}N\]
则上式$(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={\mathbf c}{\mathbf x}={\mathbf c}_B{\bar {\mathbf b}} - ({\mathbf c}_B{\bar N} - {\mathbf c}_N){\mathbf x}_N={\mathbf c}_B{\bar {\mathbf b}} - \sum_{j=m+1}^{n}{ ({\mathbf c}_B{\bar {\mathbf a}}_j - c_j)x_j}~~~~(3)\]
用$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问题可叙述成 \\
\[ \min z = z_0 - {\mathbf ζ}{\mathbf x}~~~~(4)\]
\[ s.t.~~~~{\mathbf x}_B + B^{-1}N{\mathbf x}_N = \bar{\mathbf b},{\mathbf x}\geq {\mathbf 0}.~~~~(5)\]
**定理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}$。令\\
\[ θ=\min\{ \frac{{\bar b}_i}{{\bar a}_{ik}}|{\bar a}_{ik}>0,i=1,2,\dots,m \} = \frac{{\bar b}_r}{{\bar a}_{rk}} > 0 \]
\hat {\mathbf x}
=
\bar {\mathbf x}
+ θ
\begin{pmatrix}
\begin{pmatrix}
-{\bar {\mathbf a}}_k \newline
{\mathbf 0} \\
\end{pmatrix}
+{\mathbf e}_k
\end{pmatrix}
=
\begin{pmatrix}
{\bar {\mathbf b}} - θ{\mathbf {\bar a}}_k \newline
{\mathbf 0}
\end{pmatrix}
+θ{\mathbf e}_k
.
\\
----
下面将证明${\hat {\mathbf x}}$是可行解。带入式（5）并注意到${\hat {\mathbf x}}_N=(0,\dots,θ,0,\dots,0)$，得
\[ {\hat {\mathbf x}}_B + {\bar N}{\hat {\mathbf x}}_N = {\bar {\mathbf b}} - θ{\mathbf {\bar a}}_k + \sum_{j=m+1}^n{ {\hat x}_j{\bar {\mathbf a}}_j }
= {\bar {\mathbf b}} - θ{\mathbf {\bar a}}_k + θ{\mathbf {\bar a}}_k = \bar {\mathbf b}. \]
根据θ的构造，显然可知${\hat {\mathbf x}}\geq {\mathbf 0}$，故其是可行解。
----
下面再证明${\hat {\mathbf x}}$是基本解。${\hat {\mathbf x}}$的各分量为
\[ {\hat x}_i = {\bar b}_i - ({\bar b}_r / {\bar a}_{rk}){\bar a}_{ik},i=1,\dots,m \]
\[ {\hat x}_k = {\bar b}_k / {\bar a}_{rk} \]
\[ {\hat x}_i = 0,j=m+1,\dots,n, j \neq k. \]
由于这里${\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}{\mathbf a}_r + \sum_{i=1,i\neq r}^m({\bar a}_{ik} - y_i){\mathbf a}_i = {\mathbf 0} \]
因为${\bar a}_{rk} \neq 0$，故$\{{\mathbf a}_1, \dots, {\mathbf a}_m\}$线性有关，引出矛盾。\\
最后 \\
\[ z(\hat {\mathbf x}) = z_0 - {\mathbf ζ}{\hat {\mathbf x}} = z_0 - ζ_kθ < z_0. \]
--- //[[1@1|高海东]] 2010/06/18 01:55// //&& 2010/06/24 08:25//
=====单纯形法的计算步骤=====
- 找初始的可行基
- 求出对应的典式
- 求$ζ_k=\max\{ ζ_j|j=1,\dots,n \}$
- 若$ζ_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}}$
- 若${\bar {\mathbf a}}_k\leq {\mathbf 0}$，停止，原问题无解
- 求最小比$\frac{ {\bar b}_r }{ {\bar a}_{rk} }=\min\{ \frac{{\bar b}_i}{{\bar a}_{ik}} | {\bar a}_{ik}>0 \}$
- 以${\mathbf a}_k$代替${\mathbf a}_{Br}$得到新的基，回到2.
**这里，$\mathbf ζ$称之为检验向量。在迭代过程中，如果$\mathbf ζ$有不止一个正分量，则为了使目标函数下降得较快，一般取最大的分量$ζ_k$所对应的列向量${\mathbf a}_k$进入基。**
--- //[[1@1|高海东]] 2010/06/24 08:44//
=====2.2单纯形表=====
根据θ和$\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$下，典式的系数增广矩阵为 \\
{{:keynote:增广矩阵.jpg|}} \\
$x_r$和$x_k$的地位互换。第$k$列通过初等变换变成单位向量${\mathbf e}_r$。
- 第$r$行${\bar {\mathbf a}}_r^T$除以${\bar a}_{rk}$，${\hat {\mathbf a}}_r^T = {\bar {\mathbf a}}_r^T / {\bar a}_{rk}$
- 对第$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$所对应的基本可行解。
\[ {\hat b}_r={\bar b}_r / {\bar a}_{rk}, {\hat b}_i={\bar b}_i - ({\bar b}_r / {\bar a}_{rk}){\bar a}_{ik}, i\neq r \]
换基时，目标函数$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 $ \\
看成一个方程，放在典式中一同进行初等变换。\\
{{:keynote:单纯性的旋转变换.jpg|}} \\
上述变换又称为旋转（Pivot），类似于解线性方程组的主元消元法。单纯形表可简记为 \\
{{:keynote:单纯形表.jpg|}} \\
--- //[[1@1|高海东]] 2010/06/24 09:24//
=====2.3初识解：两阶段法=====
设原问题为 \\
\[ \min{\mathbf c}{\mathbf x}~~~~s.t.{\mathbf A}{\mathbf x} = {\mathbf b}({\mathbf b} \geq {\mathbf 0}), {\mathbf x}\geq {\mathbf 0} \]
引入$m$个人工变量${\mathbf x}_a=(x_{n+1},\dots,x_{n+m})^T$，考虑如下辅助问题 \\
\[ \min g = {\mathbf 1}{\mathbf x}_a~~~~s.t.{\mathbf A}{\mathbf x} + {\mathbf x}_a = {\mathbf b}, {\mathbf x}, {\mathbf x}_a\geq {\mathbf 0} \]
其中${\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$个元素都为零，则直接去掉该行以及对应的人工变量。
--- //[[1@1|高海东]] 2010/06/24 21:15//
=====2.4初识解：大M法=====
设原问题为\\
\[ \min {\mathbf c}{\mathbf x}~~~~s.t.{\mathbf A}{\mathbf x} = {\mathbf b},{\mathbf b},{\mathbf x}\geq {\mathbf 0} \]
引入${\mathbf x}_a \in {\mathbb R}^m$及足够大的整数$M$，得到新问题如下\\
\[ \min {\mathbf c}{\mathbf x} + M{\mathbf 1}{\mathbf x}_a~~~~s.t.{\mathbf A}{\mathbf x} + {\mathbf x}_a = {\mathbf b},{\mathbf x}, {\mathbf x}_a\geq {\mathbf 0} \]
其中${\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}$，因此总可以用单纯形法求解。
--- //[[1@1|高海东]] 2010/06/24 21:27//
=====2.5退化与防止循环=====
若单纯形表中右端向量存在分量为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}}$达到最小，就选其中下标最小的那个基变量作为离基变量。即
\[ l = \min\{ r|\frac{b_r}{{\bar a}_{rk}}=\min\{ \frac{b_i}{{\bar a}_{ik}}|{\bar a}_{ik}>0 \} \} \]
* Bland规则的优点是简单易行，但缺点是只考虑最小下标，而不考虑目标函数值下降的快慢。故其效率比字典序或原来单纯形法低。
* 在实际中，退化是常见的，但退化不一定产生循环。事实上，产生循环是较罕见的。
--- //[[1@1|高海东]] 2010/06/24 22:03//
=====2.6修改单纯形法=====
**当LP问题的规模很大时，如何减少存储量和计算时间，就是一个必须加以考虑的问题。在实际中，大多采用修改单纯形法。**
----
**逆矩阵法**
一般单纯形表为\\
{{:keynote:一般单纯形表.jpg|}} \\
逆矩阵法对每一张单纯形表，仅存贮下列数据 \\
{{:keynote:修改单纯形表.jpg|}} \\
上表称为修改单纯形表。 \\
根据这张表和原始数据进行迭代计算。由$ζ_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$的修改单纯形表。
--- //[[1@1|高海东]] 2010/06/24 22:07//
====== 3.最优性条件和对偶理论 ======
对偶性
* 对于每一个线性规划$P$，总存在着另一个线性规划$D$，两者之间存在着密切的联系，人们可以通过求解对偶规划$D$来获得原规划$P$的最优解。
===== 3.1 Kuhn Tucker条件 =====
* 定理
设$A$为$m×n$阶矩阵，${\mathbf b}∈E^{m}$，${\mathbf c}∈E^{m}$，${\mathbf x}∈E^{m}$，则${\mathbf x}^{*}$为$LP$问题\\
\min \ {\mathbf c}{\mathbf x}
s.t. \ A{\mathbf x}≥{\mathbf b}
{\mathbf x}≥{\mathbf 0}
的最优解的充要条件是存在${\mathbf w}∈E^{m}$，${\mathbf v}∈E^{n}$，使得下列$K-T$条件得到满足
A{\mathbf x}^{*}≥{\mathbf b},{\mathbf x}^{*}≥{\mathbf 0}
{\mathbf c}-{\mathbf w}A-{\mathbf v}=0,{\mathbf w}≥{\mathbf 0},{\mathbf v}≥{\mathbf 0}
{\mathbf w}(A{\mathbf x}^{*}-{\mathbf b})=0,{\mathbf v}{\mathbf x}^{*}=0
若将${\mathbf v}$消去（利用${\mathbf c}-{\mathbf w}A - {\mathbf v}={\mathbf 0}$），可得到$K-T$条件的另外一种形式
A{\mathbf x}^{*}≥{\mathbf b},{\mathbf x}^{*}≥{\mathbf 0}
{\mathbf w}A≤{\mathbf c},{\mathbf w}≥{\mathbf 0}
{\mathbf w}(A{\mathbf x}^{*}-{\mathbf b})=0,({\mathbf w}A-{\mathbf c}){\mathbf x}^{*}=0
对于标准形式的$LP$问题的$K-L$条件，只要将$A{\mathbf x}={\mathbf b}$改写成
\[
\left(
\begin{array} {clr}
A \newline
-A
\end{array}
\right)
{\mathbf x}≥
\left(
\begin{array}{clr}
{\mathbf b}\newline
-{\mathbf b}
\end{array}
\right)
\],
可推出相应的$K-T$条件
A{\mathbf x}={\mathbf b},{\mathbf x}≥{\mathbf 0}
{\mathbf c}-{\mathbf w}A - {\mathbf v}=0,{\mathbf v}≥{\mathbf 0}
{\mathbf v}{\mathbf x}=0
或等价的
A{\mathbf x}={\mathbf b},{\mathbf x}≥{\mathbf 0}
{\mathbf w}A≤{\mathbf c}
({\mathbf w}A-{\mathbf c}){\mathbf x}=0
一个基本可行解
\[
\left(
\begin{array}{clr}
{\mathbf x}_B \newline
{\mathbf x}_N
\end{array}
\right)
=
\left(
\begin{array}{clr}
{\bar {\mathbf b}} \newline
{\mathbf 0}
\end{array}
\right)
({\bar {\mathbf b}} )>{\mathbf 0})
\]为最优的充要条件是检验向量$ζ≤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})$，于是有
\[
\left\{
\begin{array}{ll}
{\mathbf c}_B-{\mathbf w}B =0 \newline
{\mathbf c}_N-{\mathbf w}N-{\mathbf v}_N={\mathbf 0}
\end{array}
\right.
\]⇒
\[
\left\{
\begin{array}{ll}
{\mathbf w}={\mathbf c}_{B}B^{-1} \newline
{\mathbf v}_N = {\mathbf c}_N-{\mathbf w}N={\mathbf c}_N-{\mathbf c}_{B}B^{-1}N
\end{array}
\right.
\]
这就是说，若给一个基本可行解$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}$.
--- //[[1@1|冯银付]] 2010/06/19 23:21//
--- //[[1@1|李传煌]] 2010/06/21 21:44 minor changes//
===== 3.2对偶理论 =====
* 对偶问题可被看做是原始问题的“行列转置”
\min {\mathbf c}^{T}{\mathbf x} \ \ \ s.t. \ \ {\mathbf A}{\mathbf x}={\mathbf b},{\mathbf x}≥0
\[ \min {\mathbf c}^{T}{\mathbf x} \ s.t. \ \ \
\begin{bmatrix}
A \newline
-A
\end{bmatrix}
x≥
\begin{bmatrix}
b \newline
-b
\end{bmatrix},x≥0
\]
* 对偶问题是
* 其中
===== 3.3对偶单纯形法 =====
（Dual Simplex Method）1954年美国数学家C.莱姆基提出对偶单纯形法。单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解，直到检验数满足最优性条件为止。对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解。在迭代过程中始终保持基解的对偶可行性，而使不可行性逐步消失。设原始问题为min{cx|Ax=b，x≥0}，则其对偶问题（Dual Problem）为 max{yb|yA≤c}。当原始问题的一个基解满足最优性条件时,其检验数cBB-1A-c≤0。即知y＝cBB-1（称为单纯形算子）为对偶问题的可行解。所谓满足对偶可行性，即指其检验数满足最优性条件。因此在保持对偶可行性的前提下，一当基解成为可行解时，便也就是最优解。
--- //[[1@1|王益文]] //
===== 3.4原始-对偶单纯形法 =====
===== 3.5对偶初始解 =====
====== 二、非线性最优化 ======
===== 引言 =====
===== 1、无约束非线性最优化 =====
==== 1.1无约束问题的最优条件 ====
--- //[[1@1|冯银付]] 2010/06/19 20:50//