运筹学

线性规划问题的可性解的集合是凸集

线性规划问题的基础可行解一般都对应于凸集的极点

凸集的极点的个数是有限的

最优解只可能在凸集的极点上，而不可能发生在凸集的内部

1.2 线性规划问题的单纯型解法

1.2.1 线性规划问题的标准形式

为了使线性规划问题的解法标准，就要把一般形式化为标准形式

目标函数为min型，价值系数一律反号。令 f?(x) = -f(x) = -CX,　有 min f(x) = - max [- f(x)] = - max　f ?(x)

第i 个约束的bi 为负值，则该行左右两端系数同时反号，同时不等号也要反向

第i 个约束为 ? 型，在不等式左边增加一个非负的变量xn+i ，称为松弛变量；同时令 cn+i = 0

第i 个约束为 ? 型，在不等式左边减去一个非负的变量xn+i ，称为剩余变量；同时令 cn+i = 0

若xj ?0，令 xj= -xj? ，代入非标准型，则有xj? ? 0

若xj ?不限，令 xj= xj? - xj?， xj? ? 0，xj? ? 0，代入非标准型