2第二章 线规划与单纯形法(1-4节).ppt

第二章 ;在生产管理和经营活动中经常提出以下两类问题： 1.如何利用有限的人力、物力、财力等资源安排生产，使产值最大或利润最高。 2.对给定的任务，如何统筹安排，以便用最少的人力、物力、财力等资源消耗去完成任务。;对于这种从生产的计划与组织中提出的达到最大收益或最小支付为目的的问题研究，构成了运筹学的一个重要分支——数学规划论。 ; 第一节 线性规划问题及其数学模型 第二节 线性规划问题的图解法 第三节 线性规划问题的标准型 第四节 线性规划问题的解 第五节 线性规划问题的几何意义 第六节 单纯形法的基本原理 第七节 单纯形法的应用 第八节 线性规划在管理方面的应用 第九节 数据包络分析;第一节 线性规划问题及其数学模型 ;又知道，每生产一件产品 I 可获利2元，每生产一件产品 II 可获得3元，问应如何安排生产计划才能够使得工厂获利最多？;对生产计划（即产品 I 和 II 的生产数量）造成影响的制约因素有三个，分别为： （1）设备台时数限制： x1 + 2x2 ≤ 8 （2）原材料A的数量限制：4x1 ≤ 16 （3）原材料B的数量限制： 4x2 ≤ 12;综上所述，建立问题的数学模型为： 目标函数： max z = 2x1 + 3x2;例2 河流旁建有两个化工厂，两条河流的流量分别为500万立方米/天、200万立方米/天。;根据环保要求，河流中污水含量不应大于0.2%。 为了达到环保要求，需要进行污水处理。处理方式有两种： （1）河流自然净化：工厂1排出的污水流到工厂2时，20%得到自然净化。 （2）工厂自己进行污水处理： 工厂I 污水处理成本：1000 元/万立方米 工厂II 污水处理成本：800 元/万立方米 问如何制定污水处理计划才能使工厂总污水处理成本最小。;解：污水处理计划就是要确定工厂 I 和工厂 II 各处理污水多少。 故问题的决策变量为工厂 I 处理的污水、工厂 II 处理的污水。 设工厂I 需处理的污水：x1 万立方米 设工厂II 需处理的污水：x2 万立方米;对污水处理计划（即工厂I和II的污水处理量）造成影响的制约因素有四个，分别为： （1）工厂I 污水处理量的上限：x1 ≤ 2 （2）工厂II 污水处理量的上限：x2 ≤ 1.4 （3）工厂I和II之间河流污水含量的0.2%限制： （2-x1 ）/ 500 ≤ 0.002;问题的目标是使得污水处理成本最小，用 z 表示污水处理成本，则可表示为： min z = 1000x1 + 800x2 ;综上所述，建立问题的数学模型为： 目标函数： min z = 1000x1 + 800x2;二、线性规划问题的特征 ;存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。 都有一个要求表达的目标，它可用决策变量的线性函数来表示（称为目标函数），按问题的不同，要求目标函数实现最大化或最小化。 ;三、线性规划问题的数学模型 ;四、线性规划问题数学模型的特点 ;第二节 线性规划问题的图解法 ;该公共取值范围中的每一点都满足所有约束条件，称为线性规划的可行域。 可行域边界上改变方向的点称为可行域的顶点。 可行域中的每一点都满足所有约束条件，称可行域中的每一点为线性规划的可行解。 可行域中使目标函数极大或极小的那个可行解称为最优解。 最优解必然在可行域的顶点上取得。 ;如目标函数为最大化：则把目标函数在直角坐标系中所代表的直线沿法线方向向右上方或左上方平移，直到同图中可行域（公共取值范围）的边界点相交为止，停止平移；;如目标函数为最小化：则把目标函数在直角坐标系中所代表的直线沿法线方向向右下方或左下方，直到同图中可行域（公共取值范围）的边界点相交为止，停止平移。;求出目标函数直线同可行域相交的边界点坐标值。 该边界值即为问题的最优解，并代入目标函数，求出问题的最优解。 ;例：目标函数： max z = 2x1 + 3x2;解：（1）绘制公共取值范围： x1 + 2x2 ≤ 8：直线 x1+ 2x2 = 8 的左下方 4x1 ≤ 16：直线 4x1 = 16 的左方 4x2 ≤ 12：直线 4x2 = 12 的下方 x1≥0、x2≥0：第1象限;（2）绘制等值线、并向右上方平移。;（3）求出交点坐标 Q（4,2）。;确定约束条件围成的区域； 求出该区域边界点，列表求出目标函数的最优值。 ;x1;三、求解结果分析 ;最优解是唯一的。;目标函数： max z = 2x1 + 4x2;x