数学规划模型精.ppt

《数学规划模型精.ppt》由会员分享，可在线阅读，更多相关《数学规划模型精.ppt（29页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、数学规划模型第1页，本讲稿共29页第四章第四章 数学规划模型数学规划模型 4.1奶制品的生产与销售奶制品的生产与销售4.2 自来水输送与货机装运自来水输送与货机装运4.3 汽车生产与原油采购汽车生产与原油采购4.4 接力队选拔和选课策略接力队选拔和选课策略4.5 饮料厂的生产与检修饮料厂的生产与检修4.6钢管和易拉罐下料钢管和易拉罐下料y第2页，本讲稿共29页数学规划模型数学规划模型 实际问题中实际问题中的优化模型的优化模型x决策变量决策变量f(x)目标函数目标函数gi(x)0约束条件约束条件多元函数多元函数条件极值条件极值决策变量个数决策变量个数n和和约束条件个数约束条件个数m较大较大最优解

2、在可行域最优解在可行域的边界上取得的边界上取得数数学学规规划划线性规划线性规划非线性规划非线性规划整数规划整数规划重点在模型的建立和结果的分析重点在模型的建立和结果的分析第3页，本讲稿共29页企业生产计划企业生产计划4.1奶制品的生产与销售奶制品的生产与销售 空间层次空间层次工厂级：根据外部需求和内部设备、人力、原料等条件，以工厂级：根据外部需求和内部设备、人力、原料等条件，以最大利润为目标制订产品生产计划；最大利润为目标制订产品生产计划；车间级：根据生产计划、工艺流程、资源约束及费用参车间级：根据生产计划、工艺流程、资源约束及费用参数等，以最小成本为目标制订生产批量计划。数等，以最小成本为目

3、标制订生产批量计划。时间层次时间层次若短时间内外部需求和内部资源等不随时间变化，可制订若短时间内外部需求和内部资源等不随时间变化，可制订单阶段生产计划单阶段生产计划，否则应制订多阶段生产计划。，否则应制订多阶段生产计划。本节课题本节课题第4页，本讲稿共29页例例1加工奶制品的生产计划加工奶制品的生产计划1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶桶牛奶时间时间480小时小时至多加工至多加工100公斤公斤A1制订生产计划，使每天获利最大制订生产计划，使每天获利最大 35元可买到元可买到1桶牛奶，买吗？若买，每天最多买多少桶牛奶，买吗？若买，

4、每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到的获利增加到30元元/公斤，应否改变生产计划？公斤，应否改变生产计划？每天：每天：第5页，本讲稿共29页1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 x1桶牛奶生产桶牛奶生产A1x2桶牛奶生产桶牛奶生产A2获利获利243x1获利获利164 x2原料供应原料供应 劳动时间劳动时间 加工能力加工能力 决策变量决策变量 目标函数目标函数 每天获利每天获利约束条件约束条件非负约束非负约束 线性线性规划规划模型模型(LP)时间时间480小时小时

5、至多加工至多加工100公斤公斤A150桶牛奶桶牛奶每天每天第6页，本讲稿共29页模型分析与假设模型分析与假设 比比例例性性可可加加性性连续性连续性xi对目标函数的对目标函数的“贡献贡献”与与xi取值成取值成正比正比xi对约束条件的对约束条件的“贡贡献献”与与xi取值成正比取值成正比xi对目标函数的对目标函数的“贡贡献献”与与xj取值无关取值无关xi对约束条件的对约束条件的“贡贡献献”与与xj取值无关取值无关xi取值连续取值连续A1,A2每公斤的获利是与各自每公斤的获利是与各自产量无关的常数产量无关的常数每桶牛奶加工出每桶牛奶加工出A1,A2的数量和时的数量和时间是与各自产量无关的常数间是与各自

6、产量无关的常数A1,A2每公斤的获利是与相互产每公斤的获利是与相互产量无关的常数量无关的常数每桶牛奶加工出每桶牛奶加工出A1,A2的数量和时的数量和时间是与相互产量无关的常数间是与相互产量无关的常数加工加工A1,A2的牛奶桶数是实数的牛奶桶数是实数线性规划模型线性规划模型第7页，本讲稿共29页模型求解模型求解 图解法图解法 x1x20ABCDl1l2l3l4l5约约束束条条件件目标目标函数函数 Z=0Z=2400Z=3360z=c(常数常数)等值线等值线c在在B(20,30)点得到最优解点得到最优解目标函数和约束条件是线性函数目标函数和约束条件是线性函数可行域为直线段围成的凸多边形可行域为直线

7、段围成的凸多边形目标函数的等值线为直线目标函数的等值线为直线最优解一定在凸多边形最优解一定在凸多边形的某个顶点取得。的某个顶点取得。第8页，本讲稿共29页模型求解模型求解 软件实现软件实现 LINDO6.1max72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100endOBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.000000

8、2.0000004)40.0000000.000000NO.ITERATIONS=2DORANGE(SENSITIVITY)ANALYSIS?No20桶牛奶生产桶牛奶生产A1,30桶生产桶生产A2，利润，利润3360元。元。第9页，本讲稿共29页结果解释结果解释 OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.00000

9、00.000000NO.ITERATIONS=2原料无剩余原料无剩余时间无剩余时间无剩余加工能力剩余加工能力剩余40max72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三三种种资资源源“资源资源”剩余为零的约束为紧约束（有效约束）剩余为零的约束为紧约束（有效约束）第10页，本讲稿共29页结果解释结果解释 OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.0

10、0000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2最优解下最优解下“资源资源”增加增加1单单位时位时“效益效益”的增量的增量原料增加原料增加1单位单位,利润增长利润增长48时间增加时间增加1单位单位,利润增长利润增长2加工能力增长不影响利润加工能力增长不影响利润影子价格影子价格35元可买到元可买到1桶牛奶，要买吗？桶牛奶，要买吗？3548,应该买！应该买！聘用临时工人付出的工资最多每小时几元？聘用临时工人付出的工资最多每小时几元？2元！元！第11页，本讲稿共29页RANGESINWHICHTHEBASISISUN

11、CHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000最优解不变时目标函数最优解

12、不变时目标函数系数允许变化范围系数允许变化范围DORANGE(SENSITIVITY)ANALYSIS?Yesx1系数范围系数范围(64,96)x2系数范围系数范围(48,72)A1获利增加到获利增加到30元元/千克，应否改变生产计划千克，应否改变生产计划x1系数由系数由24 3=72增增加加为为30 3=90，在，在允允许范围内许范围内不变！不变！(约束条件不变约束条件不变)第12页，本讲稿共29页结果解释结果解释 RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOE

13、FINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000影子价格有意义时约束右端的允许变化范围影子价格有意义时约束右端的允许变化范围原料最多增加原料最多增加10时间最多增加时间最多增加5335元可买到元可买到1

14、桶牛奶，每天最多买多少？桶牛奶，每天最多买多少？最多买最多买10桶桶!(目标函数不变目标函数不变)第13页，本讲稿共29页例例2奶制品的生产销售计划奶制品的生产销售计划 在例在例1基础上深加工基础上深加工1桶桶牛奶牛奶3千克千克A112小时小时8小时小时4公斤公斤A2或或获利获利24元元/公斤公斤获利获利16元元/公斤公斤0.8千克千克B12小时小时,3元元1千克千克获利获利44元元/千克千克0.75千克千克B22小时小时,3元元1千克千克获利获利32元元/千克千克制订生产计划，使每天净利润最大制订生产计划，使每天净利润最大 30元可增加元可增加1桶牛奶，桶牛奶，3元可增加元可增加1小时时间，

15、应否投资？现小时时间，应否投资？现投资投资150元，可赚回多少？元，可赚回多少？50桶牛奶桶牛奶,480小时小时至多至多100公斤公斤A1B1，B2的获利经常有的获利经常有10%的波动，对计划有无影响？的波动，对计划有无影响？第14页，本讲稿共29页1桶桶牛奶牛奶3千克千克A112小时小时8小时小时4千克千克A2或或获利获利24元元/千克千克获利获利16元元/kg0.8千克千克 B12小时小时,3元元1千克千克获利获利44元元/千克千克0.75千克千克B22小时小时,3元元1千克千克获利获利32元元/千克千克出售出售x1千克千克A1,x2千克千克A2，X3千克千克B1,x4千克千克B2原料原料

16、供应供应 劳动劳动时间时间 加工能力加工能力 决策决策变量变量 目标目标函数函数 利润利润约束约束条件条件非负约束非负约束 x5千克千克A1加工加工B1，x6千克千克A2加工加工B2附加约束附加约束 第15页，本讲稿共29页模型求解模型求解 软件实现软件实现 LINDO6.1OBJECTIVEFUNCTIONVALUE1)3460.800VARIABLEVALUEREDUCEDCOSTX10.0000001.680000X2168.0000000.000000X319.2000010.000000X40.0000000.000000X524.0000000.000000X60.0000001.

17、520000ROWSLACKORSURPLUSDUALPRICES2)0.0000003.1600003)0.0000003.2600004)76.0000000.0000005)0.00000044.0000006)0.00000032.000000NO.ITERATIONS=2DORANGE(SENSITIVITY)ANALYSIS?No第16页，本讲稿共29页OBJECTIVEFUNCTIONVALUE1)3460.800VARIABLEVALUEREDUCEDCOSTX10.0000001.680000X2168.0000000.000000X319.2000010.000000X40

18、.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全部加工全部加工成成

19、B1除加工能力外均除加工能力外均为紧约束为紧约束第17页，本讲稿共29页结果解释结果解释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.00

20、000044.0000006)0.00000032.000000增加增加1桶牛奶使利润增长桶牛奶使利润增长3.1612=37.92增加增加1小时时间使利润小时时间使利润增长增长3.2630元可增加元可增加1桶牛奶，桶牛奶，3元可增加元可增加1小时时间，应否小时时间，应否投资？现投资投资？现投资150元，可赚回多少？元，可赚回多少？投资投资150元增加元增加5桶牛奶，可桶牛奶，可赚回赚回189.6元。（大于增加元。（大于增加时间的利润增长）时间的利润增长）第18页，本讲稿共29页结果解释结果解释B1,B2的获利有的获利有10%的波动，对计划有无影响的波动，对计划有无影响RANGESINWHICH

21、THEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX124.0000001.680000INFINITYX216.0000008.1500002.100000X344.00000019.7500023.166667X432.0000002.026667INFINITYX5-3.00000015.8000002.533334X6-3.0000001.520000INFINITYDORANGE(SENSITIVITY)ANALYSIS?YesB1获利下降获利下降1

22、0%，超出，超出X3系数允许范围系数允许范围B2获利上升获利上升10%，超出，超出X4系数允许范围系数允许范围波动对计划有影响波动对计划有影响生产计划应重新制订：如将生产计划应重新制订：如将x3的系数改为的系数改为39.6计算，计算，会发现结果有很大变化。会发现结果有很大变化。第19页，本讲稿共29页生产中通过切割、剪裁、冲压等手段，生产中通过切割、剪裁、冲压等手段，将原材料加工成所需大小将原材料加工成所需大小6钢管和易拉罐下料钢管和易拉罐下料原料下料问题原料下料问题按照工艺要求，确定下料方案，使所按照工艺要求，确定下料方案，使所用材料最省，或利润最大用材料最省，或利润最大第20页，本讲稿共2

23、9页问题问题1.如何下料最节省如何下料最节省?例例1 钢管下料钢管下料 问题问题2.客户增加需求：客户增加需求：原料钢管原料钢管:每根每根19米米 4米米50根根 6米米20根根 8米米15根根 客户需求客户需求节省的标准是什么？节省的标准是什么？由于采用不同切割模式太多，会增加生产和管理成本，规定由于采用不同切割模式太多，会增加生产和管理成本，规定切割模式不能超过切割模式不能超过3种。如何下料最节省？种。如何下料最节省？5米米10根根 第21页，本讲稿共29页按照客户需要在一根原料钢管上安排切割的一种组合。按照客户需要在一根原料钢管上安排切割的一种组合。切割模式切割模式余料余料1 1米米 4

24、米米1根根 6米米1根根 8米米1根根余料余料3米米4米米1根根6米米1根根6米米1根根合理切割模式合理切割模式的余料应小于客户需要钢管的最小尺寸的余料应小于客户需要钢管的最小尺寸余料余料3米米8米米1根根8米米1根根钢管下料钢管下料 第22页，本讲稿共29页为满足客户需要，按照哪些种合理模式，每种模式切为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？割多少根原料钢管，最为节省？合理切割模式合理切割模式2.所用原料钢管总根数最少所用原料钢管总根数最少模式模式4米钢管根数米钢管根数6米钢管根数米钢管根数8米钢管根数米钢管根数余料余料(米米)140032310132013

25、41203511116030170023钢管下料问题钢管下料问题1 1 两种两种标准标准1.原料钢管剩余总余量最小原料钢管剩余总余量最小第23页，本讲稿共29页xi 按第按第i 种模式切割的原料钢管根数种模式切割的原料钢管根数(i=1,2,7)约束约束满足需求满足需求 决策决策变量变量 目标目标1（总余量）（总余量）按模式按模式2切割切割12根根,按模式按模式5切割切割15根，余料根，余料27米米模模式式4米米根数根数6米米根数根数8米米根数根数余余料料14003231013201341203511116030170023需需求求502015最优解：最优解：x2=12,x5=15,其余为其余为

26、0；最优值：最优值：27。整数约束：整数约束：xi 为整数为整数第24页，本讲稿共29页当余料没有用处时，当余料没有用处时，通常以总根数最少为目标通常以总根数最少为目标 目标目标2（总根数）（总根数）钢管下料问题钢管下料问题1 1 约束条约束条件不变件不变 最优解：最优解：x2=15,x5=5,x7=5,其余为其余为0；最优值：最优值：25。xi 为整数按模式按模式2切割切割15根，根，按模式按模式5切割切割5根，按根，按模式模式7切割切割5根，共根，共25根，余料根，余料35米米虽余料增加虽余料增加8米，但减少了米，但减少了2根根与与目标目标1的结果的结果“共切割共切割27根，余料根，余料2

27、7米米”相比相比第25页，本讲稿共29页钢管下料问题钢管下料问题2对大规模问题，用模型的约束条件界定合理模式对大规模问题，用模型的约束条件界定合理模式增加一种需求：增加一种需求：5米米10根；切割根；切割模式不超过模式不超过3种。种。现有现有4种种需求：需求：4米米50根，根，5米米10根，根，6米米20根，根，8米米15根，根，用枚举法确定合理切割模式，过于复杂。用枚举法确定合理切割模式，过于复杂。决策变量决策变量 xi 按第按第i 种模式切割的原料钢管根数种模式切割的原料钢管根数(i=1,2,3)r1i,r2i,r3i,r4i 第第i 种切割模式下，每根原料钢管生种切割模式下，每根原料钢管

28、生产产4米、米、5米、米、6米和米和8米长的钢管的数量米长的钢管的数量第26页，本讲稿共29页满足需求满足需求模式合理：每根余模式合理：每根余料不超过料不超过3米米整数非线性规划模型整数非线性规划模型钢管下料问题钢管下料问题2目标函数（目标函数（总根数）总根数）约束约束条件条件整数约束：整数约束：xi,r1i,r2i,r3i,r4i(i=1,2,3)为整数为整数第27页，本讲稿共29页增加约束，缩小可行域，便于求解增加约束，缩小可行域，便于求解原料钢管总根数下界：原料钢管总根数下界：特殊生产计划：对每根原料钢管特殊生产计划：对每根原料钢管模式模式1：切割成：切割成4根根4米钢管，需米钢管，需1

29、3根；根；模式模式2：切割成：切割成1根根5米和米和2根根6米钢管，需米钢管，需10根；根；模式模式3：切割成：切割成2根根8米钢管，需米钢管，需8根。根。原料钢管总根数上界：原料钢管总根数上界：13+10+8=31模式排列顺序可任定模式排列顺序可任定钢管下料问题钢管下料问题2需求：需求：4米米50根，根，5米米10根，根，6米米20根，根，8米米15根根每根原料钢管长每根原料钢管长19米米第28页，本讲稿共29页LINGO求解整数非线性规划模型求解整数非线性规划模型Localoptimalsolutionfoundatiteration:12211Objectivevalue:28.0000

30、0VariableValueReducedCostX110.000000.000000X210.000002.000000X38.0000001.000000R113.0000000.000000R122.0000000.000000R130.0000000.000000R210.0000000.000000R221.0000000.000000R230.0000000.000000R311.0000000.000000R321.0000000.000000R330.0000000.000000R410.0000000.000000R420.0000000.000000R432.0000000.000000模式模式1：每根原料钢管切割成：每根原料钢管切割成3根根4米和米和1根根6米钢管，共米钢管，共10根；根；模式模式2：每根原料钢管切割成：每根原料钢管切割成2根根4米、米、1根根5米和米和1根根6米钢管，共米钢管，共10根；根；模式模式3：每根原料钢管切割成：每根原料钢管切割成2根根8米米钢管，共钢管，共8根。根。原料钢管总根数为原料钢管总根数为28根。根。第29页，本讲稿共29页