Differences

This shows you the differences between two versions of the page.

--- keynote:lesson13 [2010/06/24 22:23]
10921075
+++ keynote:lesson13 [2023/08/19 21:02]
@@ Line 1: / Line 1: @@
-====== 第十三课 ======
-**最优化方法**
-====== 内容 ======
-  * 线性规划
-  * 非线性优化
-====== 主要参考书： ======
-  * 线性规划，张建中，许绍吉，科学出版社
-  * 最优化理论与方法，袁亚湘，孙文瑜，科学出版社
-====== 基本理论 ======
-===== 问题定义 =====
-例：某计算机公司提供大型计算机系统，有A, B, C三个技术团队\\
--高端系统
-  * 每套售后的利润400万元
-  * 需用A、B两个技术团队协作实施
-  * A团队2个月，B团队1个月；
--中端系统
-  * 每套售后的利润300万元
-  * 需用A, B, C三个技术团队协作实施
-  * 每个团队各需1个月
-年度，A队可工作10个月，B队8个月、C队7个月\\
-问：怎样的销售策略能使总利润最大？\\
-可设销售$x_1$个中端系统，$x_2$个高端系统\\
-目标函数<jsmath>\max\  z=4x_1+3x_2</jsmath>
-约束条件
-<jsmath>2x_1+x_2\le10</jsmath>
-<jsmath>x_1+x_2\le8</jsmath>
-<jsmath>x_2\le7</jsmath>
-<jsmath>x_1,x_2\ge0</jsmath>
-附加条件：$x_1$和$x_2$为整数\\
-在一组线性的等式或不等式约束下，求一个线性函数的最小值或最大值。\\
-形式化的定义：\\
-<jsmath>\min\ c_1x_1+...+c_nx_n </jsmath>
-<jsmath> s.t.</jsmath>
-<jsmath>a_{11}x_1+...+a_{1n}x_n\le b_1</jsmath>
-<jsmath>...</jsmath>
-<jsmath>a_{m1}x_1+...+a_{mn}x_n\le b_m</jsmath>
-<jsmath>x_1,...,x_n \ge 0</jsmath>
-即：\\
-min **c<sup>T</sup>x**\\
-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是控制参数。\\
-例：<jsmath>\max\ z=2x_1+3x_2-5x_3</jsmath>
-约束条件：<jsmath>x_1+x_2+x_3=7</jsmath>
-<jsmath>2x_1-5x_2+x_3\ge10</jsmath>
-<jsmath>x_1,x_2,x_3\ge0</jsmath>
-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\\
-<note important> --- //[[1@1|梁中岩]] 2010/06/12 21:10//</note>
-===== 标准LP问题 =====
-从实际中总结出来的LP形式不完全一样：\\
-  * 目标函数是最大值或最小值，
-  * 约束条件是等式约束或不等式约束，
-  * 变量有上界或下界或无界
-标准LP问题形式：\\
-min z=**cx**\\
-s.t. A**x**=**b**, **x**≥**0**
-将LP问题标准化：
-目标函数的转换 $\max\ z->\min\ (-z)$\\
-约束条件的转换（引入松弛变量）
-<jsmath>\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</jsmath>
-变量的非负约束：
-<jsmath>x_j\ge l_j
-<=>
-y_j\ge0, y_j=x_j-l_j</jsmath>
-<jsmath>x_j自由变量
-<=>u_j\ge0, v_j\ge0, x_j=u_j-v_j</jsmath>
-<note important> --- //[[1@1|梁中岩]] 2010/06/12 21:10//</note>
-====== 可行区域 ======
-定义：可行区域是所有满足约束条件的可行点的集合，记为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问题，如果它的所有基本可行解都是非退化，就说该问题是非退化的，否则为退化的。
- (<note tip>tip</note>退化将在后续的单纯形方法中用到。)
- --- //[[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基本单纯形方法=====
-  * **主要思想**：先找一个可行解，判断它是否是最优解。若不是，就找一个更好的基本可行解，再进行检验。如此迭代，直至最后找到最优解，或判定无界。
-  * 两个主要问题：
-    * 寻找初始解
-    * 如何判别和迭代（先考虑）
-<note important> --- //[[1@1|高海东]] 2010/06/18 00:00//</note>
- --- //[[1@1|高海东]] 2010/06/24 08:24//
-=====判别和迭代=====
-假定$rank(A)=m<n$，且假定已找到一个非退化基本可行解，即找到一个基B。则$A{\mathbf x}={\mathbf b}$可写成
-<jsmath>
-{\mathbf x}_B + B^{-1}N{\mathbf x}_N=B^{-1}{\mathbf b}~~~~(1)
-</jsmath>
-记
-\[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 \]
-<jsmath>
-\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
-.
-</jsmath> \\
-----
-下面将证明${\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.  \]
-<note important> --- //[[1@1|高海东]] 2010/06/18 01:55// //&& 2010/06/24 08:25//</note>
-=====单纯形法的计算步骤=====
-  - 找初始的可行基
-  - 求出对应的典式
-  - 求$ζ_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$进入基。**
-<note important> --- //[[1@1|高海东]] 2010/06/24 08:44//</note>
-=====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|}} \\
-<note important> --- //[[1@1|高海东]] 2010/06/24 09:24//</note>
-=====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}$，于是可进行单纯形迭代求解，其结果有两种可能：\\
-)$\min g>0$，说明$D=\emptyset$。\\
-)$\min g=0$，这是自然有${\mathbf x}_a=0$，把它除去后记得到原问题的一个可行解。\\
-  * 若此时所有人工变量都是非基变量，则解为基本可行解。
-  * 否则，进行旋转变换消去基本量中的人工变量。设基变量$x_r$为人工变量，
-    * 取第$r$行的前$n$个元素中不为零的元素${\bar a}_{rs}$为转轴元进行变换，则非人工变量$x_5$进入基变量，同时从基本量消除了人工变量$x_r$。
-    * 若第$r$行的前$n$个元素都为零，则直接去掉该行以及对应的人工变量。
-<note important> --- //[[1@1|高海东]] 2010/06/24 21:15//</note>
-=====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}$，因此总可以用单纯形法求解。
-<note important> --- //[[1@1|高海东]] 2010/06/24 21:27//</note>
-=====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规则的优点是简单易行，但缺点是只考虑最小下标，而不考虑目标函数值下降的快慢。故其效率比字典序或原来单纯形法低。
-  * 在实际中，退化是常见的，但退化不一定产生循环。事实上，产生循环是较罕见的。
-<note important> --- //[[1@1|高海东]] 2010/06/24 22:03//</note>
-=====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$的修改单纯形表。
-<note important> --- //[[1@1|高海东]] 2010/06/24 22:07//</note>
-====== 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$问题\\
-<jsmath>\min \ {\mathbf c}{\mathbf x}</jsmath>
-<jsmath>s.t. \ A{\mathbf x}≥{\mathbf b} </jsmath>
-<jsmath>{\mathbf x}≥{\mathbf 0}</jsmath>
-的最优解的充要条件是存在${\mathbf w}∈E^{m}$，${\mathbf v}∈E^{n}$，使得下列$K-T$条件得到满足
-<jsmath>A{\mathbf x}^{*}≥{\mathbf b},{\mathbf x}^{*}≥{\mathbf 0}</jsmath>
-<jsmath>{\mathbf c}-{\mathbf w}A-{\mathbf v}=0,{\mathbf w}≥{\mathbf 0},{\mathbf v}≥{\mathbf 0}</jsmath>
-<jsmath>{\mathbf w}(A{\mathbf x}^{*}-{\mathbf b})=0,{\mathbf v}{\mathbf x}^{*}=0</jsmath>
-若将${\mathbf v}$消去（利用${\mathbf c}-{\mathbf w}A - {\mathbf v}={\mathbf 0}$），可得到$K-T$条件的另外一种形式
-<jsmath>A{\mathbf x}^{*}≥{\mathbf b},{\mathbf x}^{*}≥{\mathbf 0}</jsmath>
-<jsmath>{\mathbf w}A≤{\mathbf c},{\mathbf w}≥{\mathbf 0}</jsmath>
-<jsmath>{\mathbf w}(A{\mathbf x}^{*}-{\mathbf b})=0,({\mathbf w}A-{\mathbf c}){\mathbf x}^{*}=0</jsmath>
-对于标准形式的$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$条件
-<jsmath>A{\mathbf x}={\mathbf b},{\mathbf x}≥{\mathbf 0}</jsmath>
-<jsmath>{\mathbf c}-{\mathbf w}A - {\mathbf v}=0,{\mathbf v}≥{\mathbf 0}</jsmath>
-<jsmath>{\mathbf v}{\mathbf x}=0</jsmathbf>
-或等价的
-<jsmath>A{\mathbf x}={\mathbf b},{\mathbf x}≥{\mathbf 0}</jsmath>
-<jsmath>{\mathbf w}A≤{\mathbf c}</jsmath>
-<jsmath>({\mathbf w}A-{\mathbf c}){\mathbf x}=0</jsmath>
-一个基本可行解
-\[
-\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}$.
-<note important> --- //[[1@1|冯银付]] 2010/06/19 23:21//</note>
-<note important> --- //[[1@1|李传煌]] 2010/06/21 21:44 minor changes//</note>
-===== 3.2对偶理论 =====
-  * 对偶问题可被看做是原始问题的“行列转置”
-   <jsmath> \min {\mathbf c}^{T}{\mathbf x} \ \ \ s.t. \ \  {\mathbf A}{\mathbf x}={\mathbf b},{\mathbf x}≥0</jsmath>
-\[    \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对偶单纯形法 =====
-===== 3.4原始-对偶单纯形法 =====
-===== 3.5对偶初始解 =====
-====== 二、非线性最优化 ======
-===== 引言 =====
-===== 1、无约束非线性最优化 =====
-==== 1.1无约束问题的最优条件 ====
-<note important>--- //[[1@1|冯银付]] 2010/06/19 20:50//</note>

Applied Mathematics for Computer Science

User Tools

Site Tools

Differences

Page Tools