§82对偶单纯形法 、对偶单纯形法的基本思路 设互为对偶的线性规划问题为 (Ⅱ) max z=CX min S=yb AX< 6 WA≌C s·t X20 Y≥0 引进松弛变量X,将(I)化为标准形式 minz CX AX+X=b X>0,X=0
§8.2 对偶单纯形法 一、对偶单纯形法的基本思路 设互为对偶的线性规划问题为 (Ⅰ) (Ⅱ) max z = CX minS =Yb AX ≤ b YA≥C X ≥0 Y ≥0 引进松弛变量Xs , 将(Ⅰ) 化为标准形式 (Ⅲ) minz′= - CX AX+ Xs = b X ≥0, Xs ≥0 st st st
若B为问题皿的一个基,约束方程组的系数矩阵可写 成分块形式(BN,则基B的单纯形矩阵为 T(B)=-ICBB(BND-C] - b B(BND B b 0 -(CBBN-CN)-CBB - b B B B b 在T(B)中 B-1b-问题(的基础解中基变量值,也为问题 (Ⅱ)中非基变量对应的检验数的相反数
若B为问题(Ⅲ)的一个基, 约束方程组的系数矩阵可写 成分块形式(BNI), 则基B 的单纯形矩阵为 在T(B)中 B-1b------问题(Ⅲ)的基础解中基变量值,也为问题 (Ⅱ)中非基变量对应的检验数的相反数. − − − − = − − − = − − − − − − − − − − I B N B B b C B N C C B C B b B BNI B b C B BNI C C B b T B B N B B B B 1 1 1 1 1 1 1 1 1 1 0 ( ) ( ) [ ( ) ] ( )
CB1-题中非基变量对应的检验数的 相反数,亦为(Ⅱ)的一个基础解. 若基B满足(1)B1b>0, (2)-(CB1N-CN)≤0,-CB1-0 则B为最优基 若B不满足(1)而满足(2,即有CB1NCN≌0 和CB1≥0.此时CB1是问题(Ⅱ)的基础可行解,这 时称B为对偶可行基
CBB-1 ------问题(Ⅲ)中非基变量对应的检验数的 相反数, 亦为(Ⅱ)的一个基础解. 若基 B 满足 (1) B-1b≥0, (2) -(CBB-1N -CN ) ≤0, -CBB-1 ≤0. 则 B 为最优基. 若 B 不满足(1)而满足(2), 即有 CBB-1N-CN ≥0 和 CBB-1 ≥0. 此时 CBB-1 是问题(Ⅱ)的基础可行解, 这 时称 B为对偶可行基
我们可以从对偶可行基出发通过换基迭代,在保 持对偶基础解可行的前提下,逐步使对偶可行基满足 条件(1)即B1b≌0,从而求得原始问题(I)的最优解
我们可以从对偶可行基出发通过换基迭代, 在保 持对偶基础解可行的前提下, 逐步使对偶可行基满足 条件(1)即 B-1b≥0, 从而求得原始问题(Ⅰ)的最优解
对偶单纯形法的计算步骤 第一步将给定的线性规划问题化为标准形式,再 作出一个对偶可行基B对应的单纯形矩阵. 第二步判别.若基变量值全部非负,B就是最优 基.若基变量值有负数,但其中某负数对应的行没有负 数,则问题无可行解;若基变量有负数,且所有负数对 应的行都有负数,则要换基迭代
二、对偶单纯形法的计算步骤 第一步 将给定的线性规划问题化为标准形式,再 作出一个对偶可行基 B 对应的单纯形矩阵. 第二步 判别. 若基变量值全部非负，B 就是最优 基. 若基变量值有负数, 但其中某负数对应的行没有负 数, 则问题无可行解；若基变量有负数, 且所有负数对 应的行都有负数, 则要换基迭代