LP(Linear Programming) 线性规划，指目标函数和约束条件解为线性的最优化问题。 约束 Constraint 数学中，约束是一个最最优化问题的解需要符合的条件。分为等式约束（束缚拘束）和不等式约束（非束缚拘束）。 符合所有约束的解的集合称为可行集（feasible set）或是候选解（candidate solution） 线性 数学函数 L ( x ) L(x) L(x

对于simplex算法，如果每进行一次pivot变换，目标函数所得到的结果都会有可能出现增加的情况，所以得到的结论中，可以肯定它的值是一定不会出现减少的情况的，每次从目标函数中找到一个系数大于0的变量，然后再在约束条件中选取能够让它的增值最少的那个来继续进行pivot变换。 当目标函数中不存在变量系数大于0的变量的时候，就是算法结束了，因此只要进行了多少次的pivot变换就能够使得目标函数不存在

对于任何线性规划系统，并不是都存在最优解，如果在约束条件中，每个常量都是大于等于0的，那么线性规划系统肯定是有最优解的，此时将每个变量选取为0就可以了。而只有当约束条件中的常量有小于0的情况的时候，才需要验证系统是否存在最优解，给出一个反例，进行最优解的存在性的证明： 添加图片注释，不超过 140 字（可选） 对于如上的例子，引入一个新的变量x0，同时将线性规划系统修改为如下：