第2章 线性规划模型

,线性规划,LinearProgramming,第一篇运筹学模型,第2章线性规划模型,2.1拟订生产计划问题2.2运输问题2.3食谱问题2.4作物布局问题2.5配料问题2.6LP模型的一般形式与标准形式2.7LP模型的几何解释和图解法2.8一些实例,实例1,某化工厂生产四种化工产品,每种产品生产1吨消耗的工时、能源和获得的利润如表2-1所示表2-1生产1t产品的消耗和收益,问题,模型假设,四种产品的每吨获利是与它们各自的生产数量无关的常数；每种产品生产一吨消耗的工时，能耗是与各种产品的产量无关的常数。四种产品每吨的获利是与它们相互间产量无关的常数。每种产品所消耗的工时，能耗是与它们相互间产量无关的常数。生产产品的数量可以是任意实数。,问题分析,决策变量：四种产品明年的生产数量目标：该厂明年的总利润最大利润函数：约束条件：工时限制能耗限制蕴含约束：四种产品产量非负,模型建立,由于目标函数是变量的线性函数，约束条件是的线性不等式，所以该问题为线性规划问题，简写为LP.,线性规划问题的特征,实例2一般的拟定生产计划问题,例2设有m种资源：,，拟生产n种产品：,.用,表示生产1个单位第j种产品,所需要的第i种资源的数量，用表示第i种资源,的使用限额，用表示销售一个单位的第j种产品,获得的利润，用表示第j种产品的生产数量，则,就代表一个生产计划，我们的,问题是：要设法安排一个生产计划，使该厂获得的,总利润最高。,问题分析,决策变量:n种产品的生产数量目标：该厂获得的总利润最大利润函数：约束条件：资源的使用限额蕴含约束：n种产品产量非负,模型建立,实例1化肥的供应与销售,问题分析,总产量为10+80+15=105，总销量为75+20+50=145因为总产量总销量，故该问题为产销不平衡的运输问题。目标函数：总运费与经济损失费之和决策变量：从产地运往销地的化肥量约束条件：必须保证A区的需求量，即A区无损失费；B,C有损失费；三个厂生产的化肥全部运出无剩余。,设从甲、乙、丙三个工厂向A,B,C三个地区运送的化肥量为总运费与经济损失费之和为.三个工厂到三地的运费之和记为销地A必须满足需要量，无损失费销地B损失费为销地C损失费为,1,Z,模型建立,实例2一般的运输问题,什么是吨公里数呢？吨公里数=运载量*运载公里数,模型建立,用表示产地i供给产地j的物资数量，设s为运输的总吨公里数，则上述问题的数学模型为,一般食谱问题,假定有n种食品，每种食品中含有m种营养成分.其中：,问：应该怎样选配食品，才能保证在满足m种营养成分需要的条件下，使食品总成本y最低？,模型建立,例红星农场要在n块土地上，种植m种作物，各块土地的面积、各种作物计划种植面积和在各块地上的每平方米产量如下表，问应如何合理安排种植计划，才能使总产量最高.这里假设计划播种的种面积等于土地的总面积，即,2.4作物布局问题,土地,每平产量/kg,作物,问题分析,模型建立,一般形式,目标函数,约束条件,注释,规范形式,标准形式,概念,模型转换,约束转换实例,目标转换,变量转换,约束转换,不等式变等式不等式变不等式,等式变不等式,不等式变等式,松弛变量,剩余变量,不等式变不等式,例2.1.3把问题转化为标准形式,图解法,例解线性规划,注释,可能出现的情况：可行域是空集可行域无界无最优解最优解存在且唯一，则一定在顶点上达到最优解存在且不唯一，一定存在顶点是最优解,其他费用:450元/千吨,应如何分配水库供水量，公司才能获利最多？,若水库供水量都提高一倍，公司利润可增加到多少？,例1自来水输送,收入：900元/千吨,支出,总供水量：160,确定送水方案使利润最大,问题分析,总需求量(300),每个水库最大供水量都提高一倍,利润=收入(900)其它费用(450)引水管理费,供应限制,B,C类似处理,问题讨论,确定送水方案使利润最大,需求约束可以不变,求解,OBJECTIVEFUNCTIONVALUE1)88700.00VARIABLEVALUEREDUCEDCOSTX110.00000020.000000X12100.0000000.000000X130.00000040.000000X140.00000020.000000X2130.0000000.000000X2240.0000000.000000X230.00000010.000000X2450.0000000.000000X3150.0000000.000000X320.00000020.000000X3330.0000000.000000,这类问题一般称为“运输问题”(TransportationProblem),总利润88700（元）,例2加工奶制品的生产计划,50桶牛奶,时间480小时,至多加工100公斤A1,制订生产计划，使每天获利最大,35元可买到1桶牛奶，买吗？若买，每天最多买多少?,可聘用临时工人，付出的工资最多是每小时几元?,A1的获利增加到30元/公斤，应否改变生产计划？,每天：,x1桶牛奶生产A1,x2桶牛奶生产A2,获利243x1,获利164x2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型(LP),时间480小时,至多加工100公斤A1,模型分析与假设,比例性,可加性,连续性,xi对目标函数的“贡献”与xi取值成正比,xi对约束条件的“贡献”与xi取值成正比,xi对目标函数的“贡献”与xj取值无关,xi对约束条件的“贡献”与xj取值无关,xi取值连续,A1,A2每公斤的获利是与各自产量无关的常数,每桶牛奶加工出A1,A2的数量和时间是与各自产量无关的常数,A1,A2每公斤的获利是与相互产量无关的常数,每桶牛奶加工出A1,A2的数量和时间是与相互产量无关的常数,加工A1,A2的牛奶桶数是实数,线性规划模型,模型求解,图解法,约束条件,目标函数,z=c(常数)等值线,在B(20,30)点得到最优解,目标函数和约束条件是线性函数,可行域为直线段围成的凸多边形,目标函数的等值线为直线,最优解一定在凸多边形的某个顶点取得。,模型求解,软件实现,LINDO6.1,max72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end,OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2,DORANGE(SENSITIVITY)ANALYSIS?,No,20桶牛奶生产A1,30桶生产A2，利润3360元。,结果解释,OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2,原料无剩余,时间无剩余,加工能力剩余40,max72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end,三种资源,“资源”剩余为零的约束为紧约束（有效约束）,结果解释,OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2,最优解下“资源”增加1单位时“效益”的增量,原料增加1单位,利润增长48,时间增加1单位,利润增长2,加工能力增长不影响利润,影子价格,35元可买到1桶牛奶，要买吗？,3548,应该买！,聘用临时工人付出的工资最多每小时几元？,2元！,RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000,最优解不变时目标函数系数允许变化范围,DORANGE(SENSITIVITY)ANALYSIS?,Yes,x1系数范围(64,96),x2系数范围(48,72),A1获利增加到30元/千克，应否改变生产计划,x1系数由243=72增加为303=90，在允许范围内,不变！,(约束条件不变),结果解释,RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000,影子价格有意义时约束右端的允许变化范围,原料最多增加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千克A2加工B2,附加约束,模型求解,软件实现,LINDO6.1,OBJECTIVEFUNCTIONVALUE1)3460.800VARIABLEVALUEREDUCEDCOSTX10.0000001.680000X2168.0000000.000000X319.2000010.000000X40.0000000.000000X524.0000000.000000X60.0000001.520000ROWSLACKORSURPLUSDUALPRICES2)0.0000003.1600003)0.0000003.2600004)76.0000000.0000005)0.00000044.0000006)0.00000032.000000NO.ITERATIONS=2,OBJECTIVEFUNCTIONVALUE1)3460.800VARIABLEVALUEREDUCEDCOSTX10.0000001.680000X2168.0000000.000000X319.2000010.000000X40.0000000.000000X524.0000000.000000X60.0000001.520000ROWSLACKORSURPLUSDUALPRICES2)0.0000003.1600003)0.0000003.2600004)76.0000000.0000005)0.00000044.0000006)0.00000032.000000NO.ITERATIONS=2,结果解释,每天销售168千克A2和19.2千克B1，利润3460.8（元）,8桶牛奶加工成A1，42桶牛奶加工成A2，将得到的24千克A1全部加工成B1,除加工能力外均为紧约束,结果解释,OBJECTIVEFUNCTIONVALUE1)3460.800VARIABLEVALUEREDUCEDCOSTX10.0000001.680000X2168.0000000.000000X319.2000010.000000X40.0000000.000000X524.0000000.000000X60.0000001.520000ROWSLACKORSURPLUSDUALPRIC