线性规划模型的应用与灵敏度分析(20)

变量则是与原问题模型的约束相对应。原问题是最小化，则可将对偶问题看做原问题

[12]

。

3.2线性规划的对偶理论

定理2-1(对称性定理) 对偶问题的对偶是原问题。

定理2-2(弱对偶定理) 设X和Y分别是原问题P和对偶问题D的可行解，则有

CX Yb[13]。

定理2-3(对偶原理)

定理2-4(互补松弛定理) 如果X和Y分别为P和D的可行解，它们分别为P和D的最优解的充要条件是(C YA)X 0和Y(b AX) 0. 3.3对偶单纯形法的步骤

对偶单纯形法是用对偶理论求解原问题的一种方法，而不是求解对偶问题解的单纯形法。与对偶单纯形法相对应，已有的单纯形法称原始单纯形法[14]。

（1）建立初始单纯形表，计算检验数行

（2）先确定换出变量--解答列中的负元素一般选最小的负元素对应的基变量出基；

（3）将主元素进行换基迭代（旋转运算、枢运算)，将主元素变成1，主元列变成单位向量，得到新的单纯形表。

继续以上步骤，直至求出最优解[15]。

4. 单纯形表

表2-2 单纯形表也可以反映线性规划在现实生活中的运用

中国石油大学胜利学院本科毕业设计(论文)

CB

XB

b

实际 x1

活动 x2 0 2 0 4 0 3 活动 x2 0 2 0 1 0 3

松弛 x3 1 1 0 0 0 0 松弛 x3 1 0 0 0 0 0

活动 x4 0 0 1 0 0 0 活动 x4 -2 1 -4 0 -2 2 x5 0 0 1 0 0 0 x5 0 0 0 1 0 0

比值 R 3 2 4 -

0

x3 x4 x5 x2j

6 2 16 3

2 1 4 0 2

第 二 单 纯 形 表

0 0 3

检验数行

Zj

9

0 实际 x1

第 三 单 纯 形 表

CB

XB

b

比值 R 4 4 12

0 2 0 3

x3 x1 x5 x2j

2 2 8 3

0 1 0 0 0

检验数行

Zj

13

2

16