第2章线性规划模型ppt课件.ppt

《第2章线性规划模型ppt课件.ppt》由会员分享，可在线阅读，更多相关《第2章线性规划模型ppt课件.ppt（59页珍藏版）》请在三一办公上搜索。

1、,线 性 规 划,Linear Programming,第一篇 运筹学模型,第2章 线性规划模型,2.1 拟订生产计划问题2.2 运输问题2.3 食谱问题2.4 作物布局问题2.5 配料问题2.6 LP模型的一般形式与标准形式2.7 LP模型的几何解释和图解法2.8 一些实例,实例1,某化工厂生产四种化工产品,每种产品生产1吨消耗的工时、能源和获得的利润如表2-1所示 表2-1 生产1t产品的消耗和收益,问 题,模型假设,四种产品的每吨获利是与它们各自的生产数量无关的常数；每种产品生产一吨消耗的工时，能耗是与各种产品的产量无关的常数。四种产品每吨的获利是与它们相互间产量无关的常数。每种产品所消

2、耗的工时，能耗是与它们相互间产量无关的常数。生产产品的数量可以是任意实数。,问题分析,决策变量：四种产品明年的生产数量目标：该厂明年的总利润最大 利润函数：约束条件：工时限制 能耗限制 蕴含约束：四种产品产量非负,模型建立,由于目标函数 是变量 的线性函数，约束条件是的线性不等式，所以该问题为线性规划问题，简写为LP.,线性规划问题的特征,实例2一般的拟定生产计划问题,例2 设有m种资源：,，拟生产n种产品：,.用,表示生产1个单位第j种产品,所需要的第i种资源的数量，用 表示第i种资源,的使用限额，用 表示销售一个单位的第j种产品,获得的利润，用 表示第j种产品的生产数量，则,就代表一个生产

3、计划，我们的,问题是：要设法安排一个生产计划，使该厂获得的,总利润最高。,问题分析,决策变量:n种产品的生产数量目标：该厂获得的总利润最大 利润函数：约束条件：资源 的使用限额 蕴含约束：n种产品产量非负,模型建立,实例1 化肥的供应与销售,问题分析,总产量为10+80+15=105，总销量为75+20+50=145因为总产量总销量，故该问题为产销不平衡的运输问题。目标函数：总运费与经济损失费之和决策变量：从产地运往销地的化肥量约束条件：必须保证A区的需求量，即A区无损失费；B,C有损失费；三个厂生产的化肥全部运出无剩余。,设从甲、乙、丙三个工厂向A,B,C三个地区运送的化肥量为 总运费与经济

4、损失费之和为.三个工厂到三地的运费之和记为 销地A必须满足需要量，无损失费 销地B损失费为 销地C损失费为,1,Z,模型建立,实例2 一般的运输问题,什么是吨公里数呢？吨公里数=运载量*运载公里数,模型建立,用 表示产地i供给产地j的物资数量，设s为运输的总吨公里数，则上述问题的数学模型为,一般食谱问题,假定有n种食品，每种食品中含有m种营养成分.其中：,问：应该怎样选配食品，才能保证在满足m种营养成分需要的条件下，使食品总成本y最低？,模型建立,例 红星农场要在n块土地 上，种植m 种作物，各块土地的面积、各种作物计划种植面积和在各块地上的每平方米产量如下表，问 应如何合理安排种植计划，才能

5、使总产量最高.这里假设计划播种的种面积等于土地的总面积，即,2.4 作物布局问题,土地,每平产量/kg,作物,问题分析,模型建立,一 般 形 式,目标函数,约束条件,注 释,规 范 形 式,标 准 形 式,概 念,模 型 转 换,约束转换实例,目标转换,变量转换,约 束 转 换,不等式变等式不等式变不等式,等式变不等式,不 等 式 变 等 式,松弛变量,剩余变量,不等式变不等式,例2.1.3 把问题转化为标准形式,图 解 法,例 解线性规划,注 释,可能出现的情况：可行域是空集 可行域无界无最优解 最优解存在且唯一，则一定在顶点上达到 最优解存在且不唯一，一定存在顶点是最优解,其他费用:450

6、元/千吨,应如何分配水库供水量，公司才能获利最多？,若水库供水量都提高一倍，公司利润可增加到多少？,例1 自来水输送,收入：900元/千吨,支出,总供水量：160,确定送水方案使利润最大,问题分析,总需求量：120+180=300,总收入900160=144,000(元),收入：900元/千吨,其他费用:450元/千吨,支出,引水管理费,其他支出450160=72,000(元),供应限制,约束条件,需求限制,线性规划模型(LP),目标函数,水库i 向j 区的日供水量为 xij（x34=0）,决策变量,模型建立,确定3个水库向4个小区的供水量,模型求解,OBJECTIVE FUNCTION VA

7、LUE 1)24400.00 VARIABLE VALUE REDUCED COST X11 0.000000 30.000000 X12 50.000000 0.000000 X13 0.000000 50.000000 X14 0.000000 20.000000 X21 0.000000 10.000000 X22 50.000000 0.000000 X23 0.000000 20.000000 X24 10.000000 0.000000 X31 40.000000 0.000000 X32 0.000000 10.000000 X33 10.000000 0.000000,利润=总

8、收入-其它费用-引水管理费=144000-72000-24400=47600（元）,引水管理费 24400(元),目标函数,总供水量(320)总需求量(300),每个水库最大供水量都提高一倍,利润=收入(900)其它费用(450)引水管理费,供应限制,B,C 类似处理,问题讨论,确定送水方案使利润最大,需求约束可以不变,求解,OBJECTIVE FUNCTION VALUE 1)88700.00 VARIABLE VALUE REDUCED COST X11 0.000000 20.000000 X12 100.000000 0.000000 X13 0.000000 40.000000 X1

9、4 0.000000 20.000000 X21 30.000000 0.000000 X22 40.000000 0.000000 X23 0.000000 10.000000 X24 50.000000 0.000000 X31 50.000000 0.000000 X32 0.000000 20.000000 X33 30.000000 0.000000,这类问题一般称为“运输问题”(Transportation Problem),总利润 88700（元）,例2 加工奶制品的生产计划,50桶牛奶,时间480小时,至多加工100公斤A1,制订生产计划，使每天获利最大,35元可买到1桶牛奶，

10、买吗？若买，每天最多买多少?,可聘用临时工人，付出的工资最多是每小时几元?,A1的获利增加到 30元/公斤，应否改变生产计划？,每天：,x1桶牛奶生产A1,x2桶牛奶生产A2,获利 243x1,获利 164 x2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型(LP),时间480小时,至多加工100公斤A1,模型分析与假设,比例性,可加性,连续性,xi对目标函数的“贡献”与xi取值成正比,xi对约束条件的“贡献”与xi取值成正比,xi对目标函数的“贡献”与xj取值无关,xi对约束条件的“贡献”与xj取值无关,xi取值连续,A1,A2每公斤的获利是与

11、各自产量无关的常数,每桶牛奶加工出A1,A2的数量和时间是与各自产量无关的常数,A1,A2每公斤的获利是与相互产量无关的常数,每桶牛奶加工出A1,A2的数量和时间是与相互产量无关的常数,加工A1,A2的牛奶桶数是实数,线性规划模型,模型求解,图解法,约束条件,目标函数,z=c(常数)等值线,在B(20,30)点得到最优解,目标函数和约束条件是线性函数,可行域为直线段围成的凸多边形,目标函数的等值线为直线,最优解一定在凸多边形的某个顶点取得。,模型求解,软件实现,LINDO 6.1,max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end,OBJECTIV

12、E FUNCTION VALUE 1)3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 48.000000 3)0.000000 2.000000 4)40.000000 0.000000 NO.ITERATIONS=2,DO RANGE(SENSITIVITY)ANALYSIS?,No,20桶牛奶生产A1,30桶生产A2，利润3360元。,结果解释,OBJECTIVE FUNCTION VALU

13、E 1)3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 48.000000 3)0.000000 2.000000 4)40.000000 0.000000 NO.ITERATIONS=2,原料无剩余,时间无剩余,加工能力剩余40,max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end,三种资源,“资源”剩余为零的约束为紧约束（有效约束）,结果解释,OB

14、JECTIVE FUNCTION VALUE 1)3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 48.000000 3)0.000000 2.000000 4)40.000000 0.000000 NO.ITERATIONS=2,最优解下“资源”增加1单位时“效益”的增量,原料增加1单位,利润增长48,时间增加1单位,利润增长2,加工能力增长不影响利润,影子价格,35元可买到1桶牛奶，要买吗？

15、,35 48,应该买！,聘用临时工人付出的工资最多每小时几元？,2元！,RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2

16、50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000,最优解不变时目标函数系数允许变化范围,DO RANGE(SENSITIVITY)ANALYSIS?,Yes,x1系数范围(64,96),x2系数范围(48,72),A1获利增加到 30元/千克，应否改变生产计划,x1系数由24 3=72增加为303=90，在允许范围内,不变！,(约束条件不变),结果解释,RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIEN

17、T RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.00

18、0000,影子价格有意义时约束右端的允许变化范围,原料最多增加10,时间最多增加53,35元可买到1桶牛奶，每天最多买多少？,最多买10桶!,(目标函数不变),例3 奶制品的生产销售计划,在例2基础上深加工,制订生产计划，使每天净利润最大,30元可增加1桶牛奶，3元可增加1小时时间，应否投资？现投资150元，可赚回多少？,50桶牛奶,480小时,至多100公斤A1,B1，B2的获利经常有10%的波动，对计划有无影响？,出售x1 千克 A1,x2 千克 A2，,X3千克 B1,x4千克 B2,原料供应,劳动时间,加工能力,决策变量,目标函数,利润,约束条件,非负约束,x5千克 A1加工B1，x6

19、千克 A2加工B2,附加约束,模型求解,软件实现,LINDO 6.1,OBJECTIVE FUNCTION VALUE 1)3460.800 VARIABLE VALUE REDUCED COST X1 0.000000 1.680000 X2 168.000000 0.000000 X3 19.200001 0.000000 X4 0.000000 0.000000 X5 24.000000 0.000000 X6 0.000000 1.520000ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 3.160000 3)0.000000 3.260000

20、 4)76.000000 0.000000 5)0.000000 44.000000 6)0.000000 32.000000 NO.ITERATIONS=2,OBJECTIVE FUNCTION VALUE 1)3460.800 VARIABLE VALUE REDUCED COST X1 0.000000 1.680000 X2 168.000000 0.000000 X3 19.200001 0.000000 X4 0.000000 0.000000 X5 24.000000 0.000000 X6 0.000000 1.520000ROW SLACK OR SURPLUS DUAL P

21、RICES 2)0.000000 3.160000 3)0.000000 3.260000 4)76.000000 0.000000 5)0.000000 44.000000 6)0.000000 32.000000 NO.ITERATIONS=2,结果解释,每天销售168 千克A2和19.2 千克B1，利润3460.8（元）,8桶牛奶加工成A1，42桶牛奶加工成A2，将得到的24千克A1全部加工成B1,除加工能力外均为紧约束,结果解释,OBJECTIVE FUNCTION VALUE 1)3460.800 VARIABLE VALUE REDUCED COST X1 0.000000 1.6

22、80000 X2 168.000000 0.000000 X3 19.200001 0.000000 X4 0.000000 0.000000 X5 24.000000 0.000000 X6 0.000000 1.520000ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 3.160000 3)0.000000 3.260000 4)76.000000 0.000000 5)0.000000 44.000000 6)0.000000 32.000000,增加1桶牛奶使利润增长3.1612=37.92,增加1小时时间使利润增长3.26,30元可增加1桶牛

23、奶，3元可增加1小时时间，应否投资？现投资150元，可赚回多少？,投资150元增加5桶牛奶，可赚回189.6元。（大于增加时间的利润增长）,结果解释,B1,B2的获利有10%的波动，对计划有无影响,RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 24.000000 1.680000 INFINITY X2 16.000000 8.150000 2.100000 X3 44.000000 19.750002 3.166667 X4 32.000000 2.026667 INFINITY X5-3.000000 15.800000 2.533334 X6-3.000000 1.520000 INFINITY,B1获利下降10%，超出X3 系数允许范围,B2获利上升10%，超出X4 系数允许范围,波动对计划有影响,生产计划应重新制订：如将x3的系数改为39.6计算，会发现结果有很大变化。,