单纯形法求解线性规划问题

参考资料

先在可行域中找到一个极点，然后检查一下是不是在邻接极点除可以让目标函数取值更佳。如果不是，当前顶点就是最优点，然后算法停止；如果是，转而处理那个能让目标函数取值更佳的邻接顶点。有限步以后，该算法要么发现了一个取到最优解的极点，要么证明了最优解不存在。

要求
- 它必须是一个最大化问题。
- 所有的约束都必须用线性方程的形式表示(除了非负约束)。
- 所有的变量都必须要求是非负的。
由此，具有m个约束和n个变量(n\gem)的标准形式的通用线性规划问题是：
$\begin{align}根据约束 \quad a_{i1}x_1 &+ ...+a_{in}x_n = b_i , \quad i = 1,2,...,m \\ &x_1 \ge ,...,x_n \ge0 \tag{} \\ &使c_1 x_1 +...+c_nx_n最大化 \end{align}$
也可写成紧凑矩阵形式
$\begin{align}根据约束 \quad Ax &= b \\ x &\ge 0 \\使cx最大化\end{align}$ $\begin{align} 其中， c = [c_1c_2...c_n],\quad x=\left[ \begin{matrix}x_1\\x_2 \\ ...\\x_n \end{matrix} \right] , A = \left[\begin{matrix} a_{11}& a_{12} & ... & a_{1n}\\...& & & ...\\a_{m1} & a_{m2} & ... &a_{mn} \end{matrix}\right],b=\left[ \begin{matrix}b_1\\b_2 \\ ...\\b_m \end{matrix} \right]\end{align}$

过程过于复杂，而且有一些概念不方便简单介绍，主要参考的是书籍，找到书后找P271页即可。

待更新…