keynote:lesson13
Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
keynote:lesson13 [2010/06/24 21:14] 10921075 |
keynote:lesson13 [2023/08/19 21:02] (current) |
||
|---|---|---|---|
| Line 180: | Line 180: | ||
| 若${\bar {\mathbf b}}\geq{\mathbf 0}$，则式$(2)$就对应着基本可行解${\bar {\mathbf x}}= | 若${\bar {\mathbf b}}\geq{\mathbf 0}$，则式$(2)$就对应着基本可行解${\bar {\mathbf x}}= | ||
| \begin{pmatrix} | \begin{pmatrix} | ||
| - | {\bar {\mathbf b}}\\ | + | {\bar {\mathbf b}}\newline |
| {\mathbf 0}\\ | {\mathbf 0}\\ | ||
| \end{pmatrix} | \end{pmatrix} | ||
| Line 282: | Line 282: | ||
| * 若此时所有人工变量都是非基变量，则解为基本可行解。 | * 若此时所有人工变量都是非基变量，则解为基本可行解。 | ||
| * 否则，进行旋转变换消去基本量中的人工变量。设基变量$x_r$为人工变量， | * 否则，进行旋转变换消去基本量中的人工变量。设基变量$x_r$为人工变量， | ||
| - | * * 取第$r$行的前$n$个元素中不为零的元素${\bar a}_{rs}$为转轴元进行变换，则非人工变量$x_5$进入基变量，同时从基本量消除了人工变量$x_r$。 | + | * 取第$r$行的前$n$个元素中不为零的元素${\bar a}_{rs}$为转轴元进行变换，则非人工变量$x_5$进入基变量，同时从基本量消除了人工变量$x_r$。 |
| - | * * 若第$r$行的前$n$个元素都为零，则直接去掉该行以及对应的人工变量。 | + | * 若第$r$行的前$n$个元素都为零，则直接去掉该行以及对应的人工变量。 |
| + | <note important> --- //[[1@1|高海东]] 2010/06/24 21:15//</note> | ||
| =====2.4初识解：大M法===== | =====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退化与防止循环===== | =====2.5退化与防止循环===== | ||
| - | =====2.6修改单纯形法===== | + | 若单纯形表中右端向量存在分量为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问题的规模很大时，如何减少存储量和计算时间，就是一个必须加以考虑的问题。在实际中，大多采用修改单纯形法。** | ||
| - | <note important>高海东 2010/06/17</note> | + | ---- |
| + | **逆矩阵法** | ||
| + | 一般单纯形表为\\ | ||
| + | {{: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> | ||
| Line 414: | Line 449: | ||
| ===== 3.3对偶单纯形法 ===== | ===== 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（称为单纯形算子）为对偶问题的可行解。所谓满足对偶可行性，即指其检验数满足最优性条件。因此在保持对偶可行性的前提下，一当基解成为可行解时，便也就是最优解。 | ||
| + | <note important> --- //[[1@1|王益文]] //</note> | ||
| ===== 3.4原始-对偶单纯形法 ===== | ===== 3.4原始-对偶单纯形法 ===== | ||
keynote/lesson13.1277385270.txt.gz · Last modified: 2023/08/19 21:01 (external edit)
Page Tools
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Noncommercial-Share Alike 4.0 International
