ch01_第五节 单纯形法的进一步讨论.pdf

第一章 线性规划及其单纯形法 26-1 第一章 线性规划与单纯形法 §1 线性规划问题及其数学模型 §1 线性规划问题及其数学模型 §2 线性规划问题的几何意义 §3 单纯形法 单纯形法 §4 单纯形法的计算步骤 单纯形法的计算步骤 §5 单纯形法的进一步讨论 单纯形法的进一步讨论 §6 应用举例 第一章§5 单纯形法的进一步讨论 26-2 §5 单纯形法的进一步讨论 单纯形法的进一步讨论 一、人工变量法 n ∑P x b 设线性规划问题的约束条件 j j j 1 其中没有可作为初始基的单位矩阵，则分别给每一个 约束方程加入人工变量 xn+1 , … , xn+m ，得到 a x +a x + +a x +x b ⎧ 11 1 12 2 1n n n+1 1 ⎪ a x +a x + +a x +x b ⎪⎪ 21 1 22 2 2n n n+2 2 ⎨ ⎪ a x +a x ++a x +x b ⎪ m 1 1 m 2 2 mn n n+m m x , , x 0; x , , x 0 ⎪ ≥ ≥ ⎩ 1 n m +1 n+m (0) T 令x (i=1,2 ,…,m)为基变量，得X =(0,0, …,0 ,b , b , … , b ) . n+i 1 2 m 第一章§5 单纯形法的进一步讨论 26-3 注： 1°因人工变量是后加入到原约束条件中的虚拟变量， 无任何物理意义，它们的取值最终必须为零，才能 保证约束方程不发生变化。 2 °必须把人工变量从基变量中替换出去而变成非基变量， 则LP 问题有解，即 i) 基变量中不再含有非零的人工变量，这表示原问题有解； ii) 若在最终表中当所有c −z ≤0 ，而在其中还有某个非零人工