线性规划求解的图解法

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

线性规划常用的求解方法有图解法和单纯形法两种。图解法是用几何图形来求解两个变量问题的基本方法。

1．线性规划问题的求解术语

(1)可行解，是指满足所有约束条件的解，

(2)可行域，是包括所有可行解的区域，又称为可行解的集合。

(3)最优解，是使目标函数最优的可行解，

(4)最优值，是最优解所确定的目标值。

2．图解法的求解过程可归纳为4个步骤

第一步，用约束条件的等式方程在以变量构成的直角坐标中分别画出相应的直线,

第二步，确定可行域，一般是所有直线共同包围的凸多边形，包括这些直线构成的边界，

第三步，用目标函数方程画出目标函数等值线束(一族平行线)；

第四步，确定最优解，即极大或极小解，此解是目标函数等值线最后离开可行域的点，在图中总是在凸集的边界角点上(极点)。

将最优解的点对应的变量值代入目标函数方程，即可算出最优解的目标值。

图解法应用举例：

某车间生产甲、乙两种产品，需经过加工与装配两个工段完成，产品的工时定额、利润及工段可用工时如下表所示。用图解法求利润最大时产品的生产搭配计划。

解：(1)假设产品甲的产量为x1，产品乙的产量x2,利润为p

(2)建立线性规划模型目标函数是最大利润，即

MaxP=6x1+8x2

约束条件为

5x1+10x2≤60

4x1+4x2≤40

变量非负约束为

xl≥0，x 2≥0

(3)按图解法步骤得可行域的边界为ABCO四边形，如图2—23中的阴影范围。

图2—23

(4)作P的等值线(虚线)向增大方向平移，最后离开可行域的B点，则B点是可行最优解。

B点坐标为xl=8，x 2=2，则最优目标值为P=6*8+8*2=64

(5)结论

最优产品生产的搭配计划方案应为甲产品；乙产品=8：2，可获得的最大单位利润为64元。