线性规划2-6.pdf

线性规划 第二章 §2.6 单纯形方法中的检验数的处 理形式 1 极小化问题检验数的处理 讲2项内容： 1) 最优解的判别 2) 单纯形表的放置形式 1) 最优解的判别 考虑极小化问题标准型 min CX AX b  s.t  X 0 最优解的判别： 基本可行解  x B  X    0  1 是最优解  C CB B A 0 证： 方程 AX b 两端左乘 B1 B 1 AX B 1 b ……① 两端左乘 CB 1 1 CB B AX CB B b ……② 令 Z CX …… ③ ② + ③ 1 1 Z CB B AX CX CB B b …④ 整理 1 Z 1b ( C C B A ) X …… ⑤ CB B   B 注意到，基本可行解  x B  X  0  对应的目标函数值是 C X  CB B1 b 而对任意的可行解X ，对应的目标函数值是 Z CX 因此，基本可行解  x B  X  0  是最优解  Z CB B1 b 1 由⑤  (C CB B A)X 0