Differences

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

--- keynote:lesson13 [2010/06/24 22:04]
10921075
+++ keynote:lesson13 [2010/07/01 07:28]
10921064
@@ Line 180: / Line 180: @@
 若${\bar {\mathbf b}}\geq{\mathbf 0}$，则式$(2)$就对应着基本可行解${\bar {\mathbf x}}=
 \begin{pmatrix}
-{\bar {\mathbf b}}\\
+{\bar {\mathbf b}}\newline
 {\mathbf 0}\\
 \end{pmatrix}
@@ Line 316: / Line 316: @@
 =====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 442: / Line 449: @@
 ===== 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（称为单纯形算子）为对偶问题的可行解。所谓满足对偶可行性，即指其检验数满足最优性条件。因此在保持对偶可行性的前提下，一当基解成为可行解时，便也就是最优解。
 ===== 3.4原始-对偶单纯形法 =====

Applied Mathematics for Computer Science

User Tools

Site Tools

Differences

Page Tools