单纯形法 -- 求解线性规划

本文主要是介绍单纯形法 -- 求解线性规划，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目前，运用最广的线性规划方法就是著名的单纯形方法。这种方法是G.B.Dantzig在1947年提出的。几十年的实践证明，单纯形方法的确是一种使用方便、行之有效的重要算法。如今，它已经成为线性规划的中心内容。
单纯形法的基本思路是有选择地取（而不是枚举所有的）基本可行解，即是从可行域的一个顶点出发，沿着可行域的边界移到另一个相邻的顶点，要求新顶点的目标函数值不比原目标函数值差，如此迭代，直至找到最优解，或判定问题无界。

线性规划问题及其表示

线性规划问题可表示为如下形式：

变量满足约束条件(8.2)-(8.5)式的一组值称为线性规划问题的一个可行解。
所有可行解构成的集合称为线性规划问题的 可行区域。
使目标函数取得极值的可行解称为 最优解。
在最优解处目标函数的值称为 最优值。
有些情况下可能不存在最优解。
通常有两种情况：
(1)根本没有可行解，即给定的约束条件之间是相互排斥的，可行区域为空集；
(2)目标函数没有极值，也就是说在n 维空间中的某个方向上，目标函数值可以无限增大，而仍满足约束条件，此时目标函数值无界。

例：

这个问题的解为 $(x_1,x_2,x_3,x_4) = (0,3.5,4.5,1)$ 最优值为 $16$ 。

线性规划基本定理

约束条件(8.2)-(8.5)中 $n$ 个约束以等号满足的可行解称为线性规划问题的基本可行解。
若 $n>m$ ，则基本可行解中至少有 $n-m$ 个分量为0，也就是说，基本可行解中最多有m个分量非零。
线性规划基本定理：如果线性规划问题有最优解，则必有一基本可行最优解。
上述定理的重要意义在于，它把一个最优化问题转化为一个组合问题，即在(8.2) -(8.5)式的 $m+n$ 个约束条件中，确定最优解应满足其中哪n个约束条件的问题。
由此可知，只要对各种不同的组合进行测试，并比较每种情况下的目标函数值，直到找到最优解。
Dantzig于1948年提出了线性规划问题的单纯形算法。
单纯形算法的特点是：
（1）只对约束条件的若干组合进行测试，测试的每一步都使目标函数的值增加；
（2）一般经过不大于 $m$ 或 $n$ 次迭代就可求得最优解。