管理运筹学讲义A-1.doc

PAGE 1 PAGE 44 ` 线性规划与单纯形法 (liner program and simplex algorithm) 线性规划问题及其数学模型 问题的提出 线性规划问题有两大类型，各举例如下： 某工厂在计划期内要安排生产Ⅰ和Ⅱ两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如下表所示，该厂每生产一件产品Ⅰ可获利2元，每生产一件产品Ⅱ可获利3元，问应如何安排计划使该厂获利最多？ ⅠⅡ设备128台时原材料A4016 Kg原材料B0412 Kg解：对这样的问题用数学的语言来描述，就称为建立数学模型，简称建模。数学模型指用数学方法(字母、符号、数字等)对研究对象的数量关系所进行的定量描述。 该问题是要求如何安排生产方案，即生产多少Ⅰ和Ⅱ两种产品，才能使所获得的利润最大，为此，设Ⅰ和??两种产品的产量分别为x1和x2，x1和x2称为决策变量，显然，x1和x2的产量越大，所获得利润也越大，但x1和x2的产量要受到材料设备等资源的约束。如对于设备资源，生产Ⅰ和Ⅱ两种产品消耗的总台时数为x1＋2 x2不能超过设备的有效台时数，即必须要满足下列条件： 同样地，对于原材料A、B，也需满足下列条件： 由于x1和x2是产品的产量，所以，x1和x2的取值自然限制在： 在满足上述各个条件后，再考虑如何使得总利润最大(总利润为产品Ⅰ和Ⅱ的利润之和)，即，这里，max表示要求最大值。所以，该生产计划问题的数学模型可表示为： 用数学语言描述，就是求一组的值，使之在满足下列约束条件条件下： 使目标函数的值尽量大。 这里，s.t.是subject to的缩写，表示受约束于┅。 靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m3,在两个工厂之间有一条流量为每天200万支流，第一化工厂每天排放含有某种有害物质的工业污水2万m3，第二化工厂每天排放含有这种有害物质的工业污水1.4万m3。从第一化工厂排出的工业污水流到第二化工厂之前，有20％可自然净化，根据环保要求，河流中工业污水的含量应不大于0.2%，这两个工厂都需要各自处理一部分工业污水，第一化工厂处理工业污水的成本是1000元/万m3，第二化工厂处理工业污水的成本是800元/万m3，现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂总的处理工业污水费用最小？ 200万m3 500万m3 工厂2 工厂1 解：该问题是问两个工厂各应处理多少污水，使得污水处理费用最小。设第一化工厂每天处理污水为x1万m3，第二化工厂每天处理污水为x2万m3，显然，两个工厂处理污水越少，费用就越小，但处理污水量，必须要满足环保要求，受环保标准的限制，环保要求两个工厂附近河流的污水含量都不得大于0 .2％,所以，对第一化工厂处理污水量x1必须满足下列要求： 同样，对第二化工厂，处理污水量x2也必须满足： 由于两个工厂每天处理污水量不会大于各自的排放量，所以有， 两个工厂处理污水量又自然限制于： 在这些要求下，使得总费用最小，记为。所以，该环保问题的数学模型为： 线性规划所研究的两类问题，一类是所谓“增产”问题：现有的资源一定，如何安排使用，使得创造的利润、收益等最大，如例1；另一类是所谓“节约”问题：任务一定，如何统筹安排，以尽可能少的资源去完成，如例2。所有的线性规划问题，尽管各个问题的具体内容不同，但都可归结为这两类问题。 例3 （房地产开发）某房屋开发公司拟根据市场的需求修建二居室、三居室和四居室住宅。公司要求其规划部门确定各类住宅的户数，以获得最大利润。约束如下： 工程造价不超过900万元； 总户数不能少于350户； 基于市场分析，各类住宅在总户数中所占比例为：二居室不大于20％，三居室不大于60％，四居室不大于40％； 各类住宅造价（户）：二居室 2万元，三居室 2.5万元，4居室 3万元 各类住宅利润（户）：二居室 2000元，三居室 3000元，4居室 4000元。 分析：这是一个在资源一定的情况下的求收益最大的问题，即“增产”问题。 决策变量：设拟修建的二居室、三居室和四居室的户数分别为 约束： 目标函数： 要求寻找使得公司预计利润最大的开发方案，此问题的数学模型为： s.t. 从上面例子看到，线性规划问题是求极值问题,而且是求条件极值的问题,但这与多元函数微积分中求条件极值问题不同, 多元函数微积分中求条件极值的限制条件必须是等式的,而且自变量的个数要比限制条件个数多,才能用拉格朗日方法求解,所以,不能用微积分的方法求解上面的问题,属于线性规划研究的内容。 线性规划问题的数学模型 — 一般形式 从上面建立的线性规划模型来看，这些模型都包括三部分： 都有一组决策变量，是问