|
|
|
线性规划是研究在有限的资源条件下，如何有效地使用这些资源达到预定目标的数学方法。用数学的语言来说，也就是在一组约束条件下寻找目标函数的极值问题。
|
|
|
|
|
|
|
|
在上述条件下，求解x1，x2，…，xn，使满足下列表达式的Z取极大值（或极小值）：
|
|
|
|
|
|
解线性规划问题的方法有很多，最常用的有图解法和单纯形法。图解法简单直观，有助于了解线性规划问题求解的基本原理，下面，通过一个例子来说明图解法的应用。
|
|
|
|
例题1某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时及A、B两种原料的消耗，如下表所示。
|
|
|
|
|
|
|
|
该工厂每生产一件产品Ⅰ可获利2元，每生产一件产品Ⅱ可获利3元，问应该如何安排计划使该工厂获利最多？
|
|
|
|
该问题可用以下数学模型来描述，设x1、x2分别表示在计划期内产品Ⅰ、Ⅱ的产量，因为设备的有效台时是8，这是一个限制产量的条件，所以在确定产品Ⅰ、Ⅱ的产量时，要考虑不超过设备的有效台时数，即可用不等式表示为x1+2x2≤8
|
|
|
|
|
|
|
|
该工厂的目标是在不超过所有资源限制的条件下，确定产量x1、x2，以得到最大的利润。若用z表示利润，这时z=2x1+3x2。综上所述，该计划问题可用数学模型表示为：
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
在以x1、x2为坐标轴的直角坐标系中，非负条件x1，x2≥0是指第一象限。上述每个约束条件都代表一个半平面。如约束条件x1+2x2≤8是代表以直线x1+2x2=8为边界的左下方的半平面，若同时满足x1，x2≥0，x1+2x2≤8，4x1≤16和4x2≤12的约束条件的点，必然落在由这三个半平面交成的区域内。由例题1的所有约束条件为半平面交成的区域如下图中的阴影部分所示。阴影区域中的每一个点（包括边界点）都是这个线性规划问题的解（称可行解），因而此区域是例题1的线性规划问题的解的集合，称为可行域。
|
|
|
|
|
|
|
|
再分析目标函数z=x21+3x2，在坐标平面上，它可表示以z为参数，-2/3为斜率的一族平行线：
|
|
|
|
|
|
位于同一直线上的点，具有相同的目标函数值，因此称它为等值线。当z值由小变大时，直线沿其法线方向向右上方移动。当移动到Q2点时，使z值在可行域边界上实现最大化（如上图所示），这就得到了例题1的最优解Q2，Q2点的坐标为（4，2）。于是可计算出z=14。
|
|
|
|
这说明该厂的最优生产计划方案是：生产4件产品Ⅰ，2件产品Ⅱ，可得最大利润为14元。
|
|
|
|
例题1中求解得到的最优解是唯一的，但对一般线性规划问题，求解结果还可能出现以下几种情况：无穷多最优解（多重解）、无界解（无最优解）、无可行解。当求解结果出现后两种情况时，一般说明线性规划问题的数学模型有错误。无界解源于缺乏必要的约束条件，无可行解源于矛盾的约束条件。
|
|
|
|
从图解法中可以直观地看到，当线性规划问题的可行域非空时，它是有界或无界凸多边形。若线性规划问题存在最优解，它一定在可行域的某个顶点得到；若在两个顶点同时得到最优解，则它们连线上的任意一点都是最优解，即有无穷多最优解。
|
|
|
|
图解法虽然直观，但当变量数多于3个以上时，它就无能为力了，这时需要使用单纯形法。
|
|
|
|
单纯形法的基本思路是：根据问题的标准，从可行域中某个可行解（一个顶点）开始，转换到另一个可行解（顶点），并且使目标函数达到最大值时，问题就得到了最优解。限于篇幅，不再介绍单纯形法的详细求解过程。
|
|
|
