第3章节线性规划的图解法与基准化.ppt

第三章　线性规划的图解法和标准化 §1　图解法 §2　线性规划的标准化 例1.目标函数： Max z = 50 x1 + 100 x2 约束条件： s.t. x1 + x2 ≤ 300 (A) 2 x1 + x2 ≤ 400 (B) x2 ≤ 250 (C) x1 ≥ 0 (D) x2 ≥ 0 (E) 得到最优解： x1 = 50， x2 = 250 最优目标值 z = 27500 §1　图 解 法 (1)分别取决策变量X1和X2为横轴和纵轴，建立直角坐标系。在直角坐标系中，图上任意一点的坐标代表了决策变量的一组取值，例1的每个约束条件都代表一个半平面。 §1　图 解 法 （2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。 §1　图 解 法 （3）把五个图合并成一个图，取各约束条件的公共部分，如图3-1所示。 §1　图 解 法 （4）目标函数Z=50x1+100x2，当Z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，Z在可行域内实现了最大化。A，B，C，D，E是可行域的顶点，对有限个约束条件，则其可行域的顶点也是有限的。 §1　图 解 法 例2 max z=x1+3x2 s.t. x1+ x2≤6 -x1+2x2≤8 x1 ≥0, x2≥0 进 一 步 讨 论 例3 某公司由于生产需要，共需要A、B两种原料至少350 吨（A，B两种材料有一定替代性），其中A原料至少购进125 吨。但由于A，B两种原料的规格不同，各自所需的加工时间 也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需 要1小时，而公司总共有600个加工小时。又知道每吨A原料的 价格为2万元，每吨B原料的价格为3万元，试问在满足生产需 要的前提下，在公司加工能力的范围内，如何购买A、B两种 原料，使得购进成本最低？ 进 一 步 讨 论 解：目标函数： Min Z = 2x1 + 3 x2 约束条件： s.t. x1 + x2 ≥ 350 x1 ≥ 125 2 x1 + x2 ≤ 600 x1 , x2 ≥ 0 采用图解法，如左图：得Q点坐标（250，100）为最优解。 §1　图 解 法 重要结论1： 线性规划的可行域是凸集 可行域的顶点为有限个 线性规划的最优解一定可以在某个顶点上实现 §1　图 解 法 重要结论2： 如果线性规划有唯一最优解（例1、2、3），则一定有一个可行域的顶点对应最优解； 无穷多个最优解。若将例1中的目标函数变为max z=50x1+50x2，则线段BC上的所有点都代表最优解； 无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。一般来说，这说明模型有错，忽略了一些必要的约束条件； 无可行解。若在例1的数学模型中再增加一个约束条件4x1+3x2≥1200，则可行域为空域，不存在满足约束条件的解，当然也就不存在最优解。 §2　线性规划的标准化 一般形式 目标函数： Max （Min） Z = c1 x1 + c2 x2 + … + cn xn 约束条件：s.t. a11 x1 + a12 x2 + … + a1n xn ≤ （ =, ≥ ）b1 a21 x1 + a22 x2 + … + a2n xn ≤ （ =, ≥ ）b2 …… …… am1 x1 + am2 x2 + … + amn xn ≤ （ =, ≥ ）bm x1 ，x2 ，… ，xn ≥ 0 标准形式 目标函数：Max Z = c1 x1 + c2 x2 + … + cn xn 约束条件：s.t. a11 x1 + a12 x2 + … + a1n xn = b1