第2章线性规划建模及其单纯形法.ppt

第二章 线性规划建模及单纯形法 1.线性规划的概念 例2.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? 这是一个典型的利润最大化的生产计划问题。 其中，“Max”是英文单词“Maximize”的缩写，含义为“最大化”； “s.t.”是“subject to”的缩写，表示“满足于…”。因此，上述模型的含义是：在给定条件限制下，求使目标函数z达到最大的x1 ,x2的取值 以上两个例子的共同特点： (1)每个问题都有一组未知变量， 表示所求方案，这组未知变量称为决策变量，通常这些变量取值是非负且连续。 (2)存在一组约束条件，指决策变量取值时受到的各种可用资源的限制，表示为决策变量的线性等式或不等式 (3)都有一个要求的目标，并且这个目标可表示为一组决策变量的线性函数，称为目标函数，目标函数可以是求最大，也可以求最小。 具有上述特征的数学模型就称为线性规划模型。 目标函数： Max(Min)z =c1x1+c2x2+…+cnxn 有两种形式： Max，Min 约束条件： 三种情况，大于等于，小于等于，等于 非负约束条件 线性规划的简洁形式 2. c-目标函数系数向量 b - 右端项 A - 约束系数矩阵 2.线性规划的图解法 线性规划的图解法(解的几何表示)： 对于只有两个决策变量的线性规划问题，可以在二维直角坐标平面上作图表示线性规划问题的有关概念，并求解。 图解法求解线性规划问题的步骤如下： (1)建立直角坐标系： 分别取决策变量x1 ,x2为坐标向量。 (2)绘制可行域： 对每个约束(包括非负约束)条件，作出其约束半平面(不等式)或约束直线(等式)。 各半平面与直线交出来的区域若存在，其中的点为此线性规划的可行解。 称这个区域为可行集或可行域。 然后进行下步。 否则若交为空，那么该线性规划问题无可行解。 (3) 绘制目标函数等值线，并移动求解： 目标函数随着取值不同，为一族相互平行的直线。 首先，任意给定目标函数一个值，可作出一条目标函数的等值线(直线)； 然后，确定该直线平移使函数值增加的方向； 最后，依照目标的要求平移此直线。 结果 若目标函数等值线能够移动到既与可行域有交点又达到最优的位置，此目标函数等值线与可行域的交点即最优解(一个或多个)，此目标函数的值即最优值。 否则，目标函数等值线与可行域将交于无穷远处，此时称无有限最优解。 例2.4:某工厂拥有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) 按照图解法的步骤： （1）以决策变量x1, x2为坐标向量作平面直角坐标系； (2)对每个约束(包括非负约束)条件作出直线(A、B、C、D、E)，并通过判断确定不等式所决定的半平面。 各约束半平面交出来的区域即可行集或可行域如下图阴影所示。