线性规划求解的单纯形法

出处：按学科分类—经济 南京大学出版社《新编经济师实用手册工业企业分册》第61页（919字）

单纯形法是解3个以上变量线性规划的基本方法。它利用代数知识把各种线性规划问题的模型都变成一种标准的形式;然后先求得一个基础解，再不断调整、换基迭代而找到最优解，但一般计算量较大，宜用电子计算机求解。因此，人工处理的主要工作是将模型进行标准化处理，使其成为如式3-28所示的标准型。

1．线性规划标准型的特点

①目标函数都以极大值表示；②约束条件都用等式;⑧方程的个数m<未知量个数n,④变量非负约束，即x1≥o;⑤b1≥o。

2．线性规划…般型标准化的方法如下；

目标函数

(1)当约束条件为“≤”时，在式的左方加一个非负的变量x_n+k，使“≤”变成“=”，代入目标函数时，这些变量的系数为0。

(2)当约束条件为“≥”时，在式的左方减一个非负变数x_n+k，使“≥”变成“=”。

(3)当变量无非负要求时，将其分解为x′_k=x_k－x″_k，使x′_k和x″_k为两个非负变量，即都“≥0”。

(4)当目标函为极小时，等式两端乘“－1”，即变成极大的形式。

3．单纯形法求解过程的要点

根据标准型求得的基础解，即可行域原点(x₁=0，x₂=0)的解→将基础解换基迭代到可行域的另一个顶点上→若经判断还不是最优解时，再换基迭代到另一顶点→直到使目标函数最好时，从单纯形表中得到最优解。

这样即将多变量线性规划求解要从包括无限多解的可行域中优化的复杂问题，变成只在有限个顶点上优化的简单问题，使求解工作变得容易且可行。