运筹学 010性规划.doc

第1章 线性规划 第一节 线性规划问题及数学模型 一、引例 例1：生产计划问题 工厂可生产A、B两种产品。每生产一吨A产品需用煤9吨，耗电4千瓦，用工时3个；每生产一吨B产品需用煤4吨，耗电5千瓦，用工时10个。每生产一吨A产品工厂可获得利润700元，一吨B产品可获利润1200元。工厂的煤、电力和工人均为有限，分别为煤：360吨，电：200千瓦时，工时：300个。在这种情况下，问：为获得最大利润，工厂应分别生产A、B两种产品各多少吨？ 该问题中的数据可归纳为下表： 产品 A B 资源限制 煤 9 4 360 电 4 5 200 工时 3 10 300 利润 700 1200 下面列出该问题的数学模型。 首先设变量，为产品A的生产量，为产品B的生产量。 可列出问题中煤、电、工时三种资源的消耗和限制情况： 煤： 电： 工时： 再列出获得最大利润这一目标： 最后列出变量的有效取值范围： 上面这些表达式用数学形式反映出了问题中的各种因素，即称为该问题的数学模型，整理如下： 该数学模型即是一个线性规划模型。 二、问题的特征 引例中的问题可表示为一个线性规划模型，该问题也就相应地称为是一个线性规划问题。下面结合该例题明确线性规划问题所具有的几个特征： (1) 目标性。问题中存在一个趋向性的目标，要求某个指标尽可能大或尽可能小。如要求利润尽可能大。 (2) 约束性。问题中存在一定的限制条件，如煤、电、工时的消耗量不能超过一定的限量。 (3) 矛盾性。是指不论如何调整解决问题的方案，都会对问题的目标同时产生有利和不利两方面的影响。或者说，对模型中所设定的每个变量，不论是增大还是减小变量的取值，都会从不同的方面导致目标值的增大和减小。如增加产品A的产量，会增大A的利润，但同时会增大A消耗的资源，从而减少B可用的资源，导致B的产量及利润减少。 矛盾性决定了一个问题无法通过简单的计算得到结果，而需要采用最优化方法来求解。 (4) 比例性与可加性。比例性指问题中各变量所产生的效应与变量的取值成正比。如资源的消耗量、利润均与产量成正比；可加性指各变量所产生的效应之和等于总效应，如两种产品所产生的利润相加即等于总利润。 三、线性规划模型的一般形式 线性规划模型的一般形式可表示如下： （目标函数） （约束条件） 第二节 图解法 一、求解方法 例： 解： (1) 建立一个二维坐标系，将对应于横轴，对应于纵轴。 (2) 画出约束条件 在坐标系中画出各约束条件及变量约束，得到能满足全部约束的区域，如图中阴影部分所示。该区域称为可行域。 (3) 画出目标函数线，确定目标线的移动方向。 取不同的z值，画出对应的目标线，并根据趋向性要求确定目标线的移动方向。 (4) 在图上确定最优解的位置 根据目标线的移动方向，将目标线移动到能与可行域存在相交的极限位置，此时目标线与可行域相交的部分即为最优解。 (5) 求得最优解 根据最优解的图上位置可知其处于约束线与的相交处。联立这两条直线方程求解，可得最优解： 将解代入目标函数可得最优目标值：z*=15 二、线性规划解的情况 结合上例，可明确线性规划模型的解存在如下四种情况： (1) 无穷多最优解 如果将上例中的目标函数改为： 则可行域右上角斜边线上的所有点均为最优解，其由无穷多个。 (2) 无界解 如去掉上例中第1和第3个约束条件，则目标线可一直向右上方推，z值可达到无穷大。在实际问题中若出现此种情况，通常是列模型错误，漏列了某些约束条件。 (3) 无可行解 如果将第2、第3个约束条件均改为≥，则不能存在可同时满足所有约束的区域，即不存在可行域，此时模型无可行解。如实际问题中出现此种情况，通常应调整模型，放宽某些约束条件。 (4) 唯一最优解 例题中所求得的解即为唯一最优解。唯一解与无求多解在实际问题中均为正常情况。 第三节 线性规划的Excel求解 一、Execl规划求解功能的加载 执行Excel菜单项“工具——加载宏”；勾选“规划求解”；确定。 该项操作只需进行一次。 二、Excel求解步骤 （1）规划单元格布局，填写数据； （2）填写目标函数及约束函数； （3）设定规划求解目标、变量及约束（菜单：工具——规划求解）； （4）求解，获取结果。 三、举例 例1：用Excel求解如下线性规划模型。 解：(1)规划单元格布局，填写数据 (2)填写函数 目标函数D4：=SUMPRODUCT($B$3:$C$3,B4:C4) 约束函数D5：=SUMPRODUCT($B$3:$C$3,B