西安建筑科技大学精品课程：《运筹学》电子教案_第二章对偶线性规划

一般来说，对于一个线性规划问题，一定存在与此互为对偶关系的另一个线性规划问题。

团购合买资源类别：文库，文档格式：PDF，文档页数：19，文件大小：783.05KB

(1)从行看是原问题（Ⅰ），从列看是对偶问题（Ⅱ），两个问题的变量系数矩阵互为转置矩阵。（2）原问题（Ⅰ）的常数项是对偶问题（Ⅱ）的目标系数，反之，原问题（Ⅰ）的目标系数是对偶问题（Ⅱ）的常数项。（3）原问题（Ⅰ）有 n 个决策变量，对偶问题（Ⅱ）有 n 个约束方程：原问题有 m 个约束方程，对偶问题就有 m 个决策变量。（4）原问题的约束是“≤”型，对偶问题的约束是“≥”型。（5）原问题的目标函数是求极大，对偶问题的目标是求极小。例 2.2 在例 2.1 中引出的两规则：        ≥ + ≤ + ≤ + ≤ ⋅ = + , 0 45 2 80 3 90 max 5 4 1 2 1 2 1 2 1 2 1 2 x x x x x x x x s t Z x x      ≥ + + ≥ + + ≥ ⋅ = + + , , 0 3 4 2 5 min 90 80 45 1 2 3 1 2 3 1 2 3 1 2 3 w w w w w w w w w s t G w w w 的对偶关系表如表 2-3。从以上对偶表的关系知，只要我们得到定义中的原线性规划就可得到对偶规划，这样不要再像例 1 那样通过分析建模，但对于一个普通线性规划的对偶规划的寻找方法还需要进一步探讨。 2.1.2 对偶问题的性质对偶问题的性质比较多，在这里我们仅介绍几个较常用的性质，至于别的性质，请同学参阅其他的有关运筹学的书籍。表 2-3 x1 x2 5 4 W1 1 3 90 W2 2 1 80 Wm 1 1 45 ≤ ≤ minG maxZ ∧ ∧ ≤ 定理 1 如果线性规划（Ⅰ）中的第个约束条件是等式，则它的对偶规划（Ⅱ）中的第个变量W 无非负限制（W 为自由变量）。 k k k k 反之，若原线性规划（Ⅰ）中的第个变量无非负性要求，则对偶规划（Ⅱ）中的第个约束为等式。 k k 证：设线性规划（Ⅰ）的第k 个约束条件为等式，即 1 1 2 2 11 1 12 2 1 1 21 1 22 2 2 2 1 1 2 2 1 1 2 2 1 2 max , , , 0 n n n n n n k k kn n m m mn n n Z C x C x C x a x a x a x b a x a x a x b s t a x a x a x b a x a x a x b x x x = + + +  + + + ≤  + + + ≤   ⋅ +  + + =   + + + ≤   ≥ " … … ……………………………… … ……………………………… … … k m (Ⅰ)

③据表 2-5 得对偶规划 1 2 3 1 2 3 1 2 1 2 3 1 3 1 3 2 min 5 ( 4) 2 2 1 3 1 1 , 0, G W W W W W W W W s t W W W W W W W W = + − −  + − ≥  − =  ⋅ +  + ≥  − =   ≥ 无非负性要求定理 2 若 X ,W分别为互为对偶规划（Ⅰ）与（Ⅱ）的可行解，则min G ≥ max z 证：因为G 所以，。 b W AX W X A W X A W X C CX CX z T T T T T T T T T = ≥ ( ) = = ( ) ≥ = ( ) = = min G ≥ max z 定理 3 若（Ⅰ）与（Ⅱ）的可行解，并且CX ，则 X ∗ ,W ∗ 分别为互为对偶规划 ∗ ∗ = b W T ∗ ∗ X 与W 分别为（Ⅰ）与（Ⅱ）的最优解。因为，由定理 2 知，对（Ⅰ）与（Ⅱ）的任一可行解 X ,W 都有，所以，特别的对可行解 G Z(CX b W ) T ≥ ≤ X ∗ 也有bT W ≥ CX ∗ 成立。又因为，，故对任何可行解W 从而由极小值的最优解的定义知，W 是（Ⅱ）的最优解。同理可证， ∗ ∗ CX = b W T ∗ ,都有 ∗ ∗ b W ≥ CX = b W T T ∗ X 是规划（Ⅰ）的最优解。定理 4 对偶问题的对偶是问题证：设原问题是max f (X ) = CX; AX ≤ b; X ≥ 0 W; A W ≥ C ,W ≥ 0 T T max( G), max( G) b W, T − 所以 − = − 0 根据对偶问题的标准形式可找到它的对偶问题 min 对上式的目标函数两边取负号又因为给约束条件两边取负号，得，W 合起来有线性规划 G = bT − min G = T −C ≥ G b W T − min = − − A W ≤    ≥ − ≤ − ⋅ − = − 0 max( ) W A W C s t G b W T T T 根据标准形式的对偶关系，上式的对偶问题是 min(−C′) = −CX; − AX ≥ −b; X ≥ 0 又因为min( −G ′) = − max W ′ 所以，− maxW′ = −CX; − AX ≥ −b; X ≥ 0 即max f (X ) = CX; AX ≤ b; X ≥ 0即是原问题。定理 5 设 ∗ X 为线性规划（L,p）的基本最优解，对应基阵为 B，并且其检验数全部非正，则W ∗ = CB B−1是对偶规划（D,p）的最优解。证明：由线性代数的知识知（L,P）对应于 ∗ X 的典型式为 B B N N B N X N X = X − B NX = B b − BNX f = f − C B N − CN X = f − λ ∗ −1 −1 0 −1 0 ( )

应的检验数（-1，-3，0，0，0）全部非正，容易验证对应的C 是对偶问题的可行解（此时称 −1 B B 0 X 具有对偶可行性），一般地，如果 0 X 是（L,p）的基本解且对应检验数全部非正，则对应的C 必为对偶问题（D,p）的可行解。如果在迭代过程中，保持基本解的对偶可行性，而使其对原问题的非可行性逐步消失，一旦基本解达到可行，则此解必是原问题的最优解。这就是对偶单纯形法的基本思想，为表达方便起见，先引进下面概念。 −1 B B 0 X ,", 0 } l < 0 = b * +  0 4 3 2 x x 3 1 , 0, , 2 2 , 0 定义：对于（L,p），其检验数全部非正的基本解称为（L,p）的正则解，对应的基称为正则基。从而可知，如果既是（L,p）的正则解，又是它的可行解，则 0 X 也是（L,p）的最优解。所谓对偶单纯形法就是以这一事实为依据。即从（L,p）的正则解开始迭代，在迭代过程中保持正则性，而使其不可行逐步消失，最后达到可行解，从而得到最优解。 2.3.3 对偶单纯形方法步骤第一步：建立线性规划的单纯形表第二步：判别，若单纯形表中的bi ≥ 0(i =1,2 m),且λ j ≤ ，则 X 是最优解。若某负常数项，对应行中的变量系数无负数，则该规划无最优解，否则进行第三步。第三步：确定出基变量，选常数列中最小负数对应的行中的基变量出基，即 min{ i i b b 所对应行的基变量出基。第四步：确定入基变量 0, 0 j s j i j i j a a λ θ λ ∗     = <      < 对应的变量入基。第五步：确定主元，将主元变 1，主元所在列上的其他元素变为零。 2.3.4 方法应用举例例 2.5 利用对偶单纯形法求解线性规划        ≥ + ≥ + ≥ − − = − ⋅ = − − , , 2 1 3 2 2 3 max 3 1 2 3 1 2 1 2 1 2 1 x x x x x x x x x s t Z x 解：求解过程如表 2-6 所示。由对偶单纯形表 2-6 可知 ( ) * T x = 1 2 ， 3 max 2 Z = −

点击进入文档下载页（PDF格式）

共19页，试读已结束，阅读完整版请下载

点击下载（PDF格式）

浏览记录

西安建筑科技大学精品课程：《运筹学》电子教案_第二章对偶线性规划

西安建筑科技大学精品课程：《运筹学》电子教案_第二章 对偶线性规划

西安建筑科技大学精品课程：《运筹学》电子教案_第二章对偶线性规划