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:45] 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 307: | Line 307: | ||
---- | ---- | ||
**Bland规则** | **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修改单纯形法===== | =====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 434: | 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原始-对偶单纯形法 ===== |