线性规划

出处：按学科分类—经济 经济科学出版社《企业管理学大辞典》第549页（867字）

若干个线性等式(或不等式)的约束下求一个线性函数极值的问题。

线性规划模型的标准形式为：

其中各b_i(i=1…m)均非负。对于任意一个线性目标函数，无论是求其极大还是极小，也无论各约束条件是等式还是不等式，各b_i是否非负，各变量是否要求非负，都可以通过一定的变换使其变为标准形，标准形也可简记为：

其中C^T=(C₁…C_n)(向量)为目标函数的系数，Am×n(矩阵)为约束方程的系数。

将线性规划模型的一般形式化为标准形式是为了便于运用单纯形法来求解，单纯形法的基本思想是：由线性约束方程在空间中围起的形体一定是一个多边形，而使目标函数达到极值的点(即最优解所代表的点)一定可以在多边形的顶点上找到，因此，我们只需先找到任意一个顶点，然后从这个顶点开始按一定的顺序寻找目标函数值比这个顶点小的下一个顶点。

由于多边形的顶点是有限的，因此在经过了有限步的递推之后一定可以找到最优解。单纯形法的每一步操作都是固定而机械的，因此可以通过计算机来求解。在问题比较简单时，也可采用图解法，见图11－5。

图11－5

例：用图解法求解线性规划问题。

maxZ=x₁+2x₂

图中两条实线分别是x₁+3x₂=3和3x₁+x₂=3，可以看出原问题的可行区域是由这两条直线及坐标轴围成的部分。

虚线是令Z取常数时的目标直线，图中画了三条，分别是当Z=1，Z=9／4，Z=4时的直线，可以看到通过两条直线交点的目标函数直线既经过了可行域，又没有比它更高的直线了，因此Z=9／4就是最优值，而交点(3／4，3／4)是最优解。