线性规划问题的图解法

1、 12max23Zxx12121228416412, 0 xxxxx x 例例1-19 8 7 6 5 4 3 2 1 0 |123456789x1x2x1 + 2x2 8(0, 4)(8, 0)4x1 164 x2 129 8 7 6 5 4 3 2 1 0 x2|123456789x1x1 + 2x2 84x1 164 x2 16可行域可行域9 8 7 6 5 4 3 2 1 0 |123456789x1x2x1 + 2x2 84x1 164 x2 16可行域可行域BCDEA9 8 7 6 5 4 3 2 1 0 x2|123456789x1x1 + 2x2 84x1 164 x2 16B

2、CDEA9 8 7 6 5 4 3 2 1 0 x2|123456789x1x1 + 2x2 84x1 164 x2 16BCDEAx1+ 2x2=8 4x1 =16对应坐标对应坐标x1=4, x2=2 是最佳的产品组合是最佳的产品组合, 4,2T就是线性规划模型的就是线性规划模型的使产品的总利润达到最大值使产品的总利润达到最大值maxZ=2 4+3 2=14就是目标函数就是目标函数 x1+2x2=8 4x1=16总结线性规划问题的有关概念总结线性规划问题的有关概念（1 1）可行解可行解：满足约束条件与非负：满足约束条件与非负限制的变量的值，称为可行解。限制的变量的值，称为可行解。（2 2）可

3、行域可行域：全部可行解的集合称：全部可行解的集合称 为可行域。为可行域。（3 3）最优解最优解：使目标函数取得：使目标函数取得 最优值最优值的可行解，称为最优解。的可行解，称为最优解。练习：某公司由于生产需要，共需要练习：某公司由于生产需要，共需要A，B两种原料至少两种原料至少350吨（吨（A，B两种材料有两种材料有一定替代性），其中一定替代性），其中A原料至少购进原料至少购进125吨。但由于吨。但由于A，B两种原料的规格不同，两种原料的规格不同，各自所需的加工时间也是不同的，加工每各自所需的加工时间也是不同的，加工每吨吨A原料需要原料需要2个小时，加工每吨个小时，加工每吨B原料需原料需要要1

4、小时，而公司总共有小时，而公司总共有600个加工小时。个加工小时。又知道每吨又知道每吨A原料的价格为原料的价格为2万元，每吨万元，每吨B原料的价格为原料的价格为3万元，试问在满足生产需万元，试问在满足生产需要的前提下，在公司加工能力的范围内，要的前提下，在公司加工能力的范围内，如何购买如何购买A，B两种原料，使得购进成本两种原料，使得购进成本最低？最低？解：目标函数： Min f = 2x1 + 3 x2 约束条件：s.t. x1 + x2 350 x1 125 2 x1 + x2 600 x1 , x2 0 采用图解法。如下图：得Q点坐标（250，100）为最优解。100200300 400

5、 500 600100200300400600500 x1 =125x1+x2 =3502x1+x2 =600 x1 x2 2x1+3x2 =1200100200300 400 500 600100200300400600500 x1 =125x1+x2 =3502x1+x2 =600 x1 x2 Q2x1+3x2 =12002x1+3x2 =9002x1+3x2 =800讨论：讨论：用图解法求解线性规划的各种可能用图解法求解线性规划的各种可能 的结果。的结果。线性规划问题求解的线性规划问题求解的 几种可能结果几种可能结果(1) 唯一唯一最优解最优解 x26 5 4 3 2 1 0 |1234

6、56789x1(2)无穷多无穷多最优解最优解6 5 4 3 2 1 0 x2|123456789x1 目标函数等值线与可行域的一条边界目标函数等值线与可行域的一条边界线段重合，说明线段重合，说明该线性规划问题有该线性规划问题有线段上的所有点都线段上的所有点都使 目 标 函 数 取 得 相 同 的 最 大 值使 目 标 函 数 取 得 相 同 的 最 大 值Zmax=14。 (3)无界解无界解 Max Z = x1 + x2s.t. -2x1 + x2 4 x1 - x2 2 x1、 x2 0 0 x2x142 如图中可行域是一个无界区域，如阴如图中可行域是一个无界区域，如阴影区所示。虚线为目标

7、函数等值线，沿着箭影区所示。虚线为目标函数等值线，沿着箭头指的方向平移可以使目标函数值无限制地头指的方向平移可以使目标函数值无限制地增大，但是找不到最优解。增大，但是找不到最优解。 如果一个实际问题抽象成像上面这样的线如果一个实际问题抽象成像上面这样的线性规划模型，比如是一个生产计划问题，其性规划模型，比如是一个生产计划问题，其经济含义就是某些资源是无限的，产品的产经济含义就是某些资源是无限的，产品的产量可以无限大量可以无限大，这说明模型忽略了一些必要，这说明模型忽略了一些必要的约束条件的约束条件。此时应重新检查和修改模型，。此时应重新检查和修改模型，否则就没有实际意义。否则就没有实际意义。(4)无可行解无可行解Max Z = 2x1 + 3x2s.t. x1 +2 x2 8 4 x1 16 4x2 12 -2x1 + x2 4 x1、 x2 0 085678221xxx13x24123102可行域是有界或无界的凸多边形。可行域是有界或无界的