运筹学01_线性规划和单纯形法.ppt

运筹学 第一章线性规划及单纯形法Linear Programming and Simplex Method §1. 线性规划问题及数学模型 如何合理地利用 有限的人、财、物 等资源，得到最 好的经济效果? 　 例1.1：某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示： 问题：工厂应如何安排生产可获得最大的总利润？ 对设备C，两种产品生产所占用的机时数不能超过75，于是我们可以得到不等式：3x2 ≤75 ；另外，产品数不可能为负，即 x1 ,x2 ≥0。 同时，我们有一个追求目标，即获取最大利润。于是可写出目标函数z为相应的生产计划可以获得的总利润：z =1500x1+2500x2 。 综合上述讨论，在加工时间以及利润与产品产量成线性关系的假设下，把目标函数和约束条件放在一起，可以建立如下的线性规划模型： 目标函数 max z =1500x1+2500x2? 约束条件 s.t. 3x1+2x2≤65 2x1+x2≤40 3x2≤75 x1 ,x2 ≥0? §2. 线性规划的求解 (1) 图解法——只适用两个变量 （2）单纯型法——适用多个变量 线性规划的图解法 对于只有两个变量的线性规划问题，可以二维直角坐标平面上作图表示线性规划问题的有关概念，并求解。图解法求解线性规划问题的步骤如下： (1)分别取决策变量x1，x2为坐标向量建立直角坐标系。 （2）找可行域。对每个约束条件（包括非负约束），先取其等式在坐标系中作出直线，并判断确定不等式所决定的半平面。各约束半平面交集形成一个区域(也有可能是空集），就是线性规划的可行集（可行域）；其中的点就是线性规划的可行解。如果可行集是空集，则该线性规划问题无可行解。 （3）确定最优解。任意给定目标函数一个值作一条目标函数的等值线，并确定该等值线平行移动后值增加的方向。平移此目标函数的等值线，使其达到既与可行域有交点又不可能使值再增加的位置(有时交于无穷远处，此时称无有限最优解）。若有交点时，此目标函数等值线与可行域的交点即最优解（一个或多个），此目标函数的值即最优值。 例1.3（续例1.1）：某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示： 问题：工厂应如何安排生产可获得最大的总利润？用图解法求解。 解：设变量xi为第i种（甲、乙）产品的生产件数（i＝1, 2）。根据前面分析，可以建立如下的线性规划模型： max z = 1500 x1 + 2500 x2 s.t. 3x1+2x2 ≤ 65 (A) 2x1+ x2 ≤ 40 (B) 3x2 ≤ 75 (C) x1, x2 ≥ 0 (D, E) 按照图解法的步骤在以决策变量x1, x2为坐标向量的平面直角坐标系上对每个约束（包括非负约束）条件作出直线，并通过判断确定不等式所决定的半平面。各约束半平面交出来的区域即可行集或可行域如下图阴影所示。 例1.4：在例1.3的线性规划模型中，如果目标函数变为： max z = 1500 x1 + 1000 x2 那么，最优情况下目标函数的等值线与直线（A）重合。这时，最优解有无穷多个，是从点 (5,25)T到点 (15,10)T 线段上的所有点，最优值为32500。如下图所示： ? 线性规划的可行域和最优解有以下几种可能的情况 1.可行域为封闭的有界区域 (a)有唯一的最优解； (b)有无穷多个最优解； 2.可行域为无界区域 (c)有唯一的最优解； (d)有无穷多个最优解； (e)目标函数无界(即虽有可行解， 但在可行域中，目标函数可以无 限增大或无限减少)，因而没有 有限最优解。 3.可行域为空集 (f)没有可行解，原问题无最优解 以上几种情况的图示如