数学规划公开课一等奖优质课大赛微课获奖课件.pptx

第四章第四章 数学规划模型数学规划模型 4.1奶制品生产与销售奶制品生产与销售4.2 自来水输送与货机装运自来水输送与货机装运4.3 汽车生产与原油采购汽车生产与原油采购4.4 接力队选拔和选课策略接力队选拔和选课策略4.5 饮料厂生产与检修饮料厂生产与检修4.6钢管和易拉罐下料钢管和易拉罐下料y第1页第1页数学规划模型数学规划模型 实际问题中实际问题中优化模型优化模型x决议变量决议变量f(x)目的函数目的函数gi(x)0约束条约束条件件多元函数多元函数条件极值条件极值决议变量个数决议变量个数n和和约束条件个数约束条件个数m较大较大最优解在可行域最优解在可行域边界上取得边界上取得数数学学规规划划线性规划线性规划非线性规划非线性规划整数规划整数规划重点在模型建立和结果分析重点在模型建立和结果分析第2页第2页公司生产计划公司生产计划4.1奶制品生产与销售奶制品生产与销售 空间层次空间层次工厂级：依据外部需求和内部设备、人力、原料等工厂级：依据外部需求和内部设备、人力、原料等条件，以最大利润为目的制定产品生产计划；条件，以最大利润为目的制定产品生产计划；车间级：依据生产计划、工艺流程、资源约束及费车间级：依据生产计划、工艺流程、资源约束及费用参数等，以最小成本为目的制定生产批量计划。用参数等，以最小成本为目的制定生产批量计划。时间层次时间层次若短时间内外部需求和内部资源等不随时间改变，可若短时间内外部需求和内部资源等不随时间改变，可制定制定单阶段生产计划单阶段生产计划，不然应制定多阶段生产计划。，不然应制定多阶段生产计划。本节课题本节课题第3页第3页例例1加工奶制品生产计划加工奶制品生产计划1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或赢利24元/公斤 赢利16元/公斤 50桶牛奶桶牛奶时间时间480小时小时 至多加工至多加工100公斤公斤A1制定生产计划，使天天赢利最大制定生产计划，使天天赢利最大 35元可买到元可买到1桶牛奶，买吗？若买，天天最多买多少桶牛奶，买吗？若买，天天最多买多少?可聘用暂时工人，付出工资最多是每小时几元可聘用暂时工人，付出工资最多是每小时几元?A1赢利增长到赢利增长到30元元/公斤，应否改变生产计划？公斤，应否改变生产计划？天天：天天：第4页第4页1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或赢利24元/公斤 赢利16元/公斤 x1桶牛奶生产桶牛奶生产A1x2桶牛奶生产桶牛奶生产A2赢利赢利243x1赢利赢利164 x2原料供应原料供应 劳动时间劳动时间 加工能力加工能力 决议变量决议变量 目的函数目的函数 天天赢利天天赢利约束条件约束条件非负约束非负约束 线性线性规划规划模型模型(LP)时间时间480小时小时 至多加工至多加工100公斤公斤A150桶牛奶桶牛奶天天天天第5页第5页模型分析与假设模型分析与假设 百百分分比比性性可可加加性性连续性连续性xi对目的函数对目的函数“奉奉献献”与与xi取值成正取值成正比比xi对约束条件对约束条件“奉奉献献”与与xi取值成正取值成正比比xi对目的函数对目的函数“奉奉献献”与与xj取值无关取值无关xi对约束条件对约束条件“奉奉献献”与与xj取值无关取值无关xi取值连续取值连续A1,A2每公斤赢利是与各自每公斤赢利是与各自产量无关常数产量无关常数每桶牛奶加工出每桶牛奶加工出A1,A2数量和时数量和时间是与各自产量无关常数间是与各自产量无关常数A1,A2每公斤赢利是与互相每公斤赢利是与互相产量无关常数产量无关常数每桶牛奶加工出每桶牛奶加工出A1,A2数量和时数量和时间是与互相产量无关常数间是与互相产量无关常数加工加工A1,A2牛奶桶数是实数牛奶桶数是实数线性规划模型线性规划模型第6页第6页模型求解模型求解 图解法图解法 x1x20ABCDl1l2l3l4l5约约束束条条件件目的目的函数函数 Z=0Z=2400Z=3600z=c(常数常数)等值线等值线c在在B(20,30)点得到最优解点得到最优解目的函数和约束条件是线性函数目的函数和约束条件是线性函数可行域为直线段围成凸多边形可行域为直线段围成凸多边形目的函数等值线为直线目的函数等值线为直线最优解一定在凸多边最优解一定在凸多边形某个顶点取得。形某个顶点取得。第7页第7页模型求解模型求解 软件实现软件实现 LINDO6.1max72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100endOBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2DORANGE(SENSITIVITY)ANALYSIS?No20桶牛奶生产桶牛奶生产A1,30桶生产桶生产A2，利润，利润3360元。元。第8页第8页结果解释结果解释 OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2原料无剩余原料无剩余时间无剩余时间无剩余加工能力剩余加工能力剩余40max72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三三种种资资源源“资源资源”剩余为零约束为紧约束（有效约束）剩余为零约束为紧约束（有效约束）第9页第9页结果解释结果解释 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元！元！第10页第10页RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000最优解不变时目的函最优解不变时目的函数系数允许改变范围数系数允许改变范围DORANGE(SENSITIVITY)ANALYSIS?Yesx1系数范围系数范围(64,96)x2系数范围系数范围(48,72)A1赢利增长到赢利增长到30元元/公斤，应否改变生产计划公斤，应否改变生产计划x1系数由系数由24 3=72增长增长为为30 3=90，在在允许范围内允许范围内不变！不变！(约束条件不变约束条件不变)第11页第11页结果解释结果解释 RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000影子价格故意义时约束右端允许改变范围影子价格故意义时约束右端允许改变范围原料最多增长原料最多增长10时间最多增长时间最多增长5335元可买到元可买到1桶牛奶，天天最多买多少桶牛奶，天天最多买多少？最多买最多买10桶桶!(目的函数不变目的函数不变)第12页第12页例例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小时时间，应否投小时时间，应否投资？现投资资？现投资150元，可赚回多少？元，可赚回多少？50桶牛奶桶牛奶,480小时小时至多至多100公斤公斤A1B1，B2赢利经常有赢利经常有10%波动，对计划有无影响？波动，对计划有无影响？第13页第13页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原料原料供应供应 劳动劳动时间时间 加工能力加工能力 决议决议变量变量 目的目的函数函数 利润利润约束约束条件条件非负约束非负约束 x5公斤公斤A1加工加工B1，x6公斤公斤A2加工加工B2附加约束附加约束 第14页第14页模型求解模型求解 软件实现软件实现 LINDO6.1OBJECTIVEFUNCTIONVALUE1)3460.800VARIABLEVALUEREDUCEDCOSTX10.0000001.680000X2168.0000000.000000X319.010.000000X40.0000000.000000X524.0000000.000000X60.0000001.50ROWSLACKORSURPLUSDUALPRICES2)0.0000003.1600003)0.0000003.2600004)76.0000000.0000005)0.00000044.0000006)0.00000032.000000NO.ITERATIONS=2DORANGE(SENSITIVITY)ANALYSIS?No第15页第15页OBJECTIVEFUNCTIONVALUE1)3460.800VARIABLEVALUEREDUCEDCOSTX10.0000001.680000X2168.0000000.000000X319.010.000000X40.0000000.000000X524.0000000.000000X60.0000001.50ROWSLACKORSURPLUSDUALPRICES2)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除加工能力外均除加工能力外均为紧约束为紧约束第16页第16页结果解释结果解释OBJECTIVEFUNCTIONVALUE1)3460.800VARIABLEVALUEREDUCEDCOSTX10.0000001.680000X2168.0000000.000000X319.010.000000X40.0000000.000000X524.0000000.000000X60.0000001.50ROWSLACKORSURPLUSDUALPRICES2)0.0000003.1600003)0.0000003.2600004)76.0000000.0000005)0.00000044.0000006)0.00000032.000000增长增长1桶牛奶使利润增桶牛奶使利润增长长3.1612=37.92增长增长1小时时间使利小时时间使利润增长润增长3.2630元可增长元可增长1桶牛奶，桶牛奶，3元可增长元可增长1小时时间，小时时间，应否投资？现投资应否投资？现投资150元，可赚回多少？元，可赚回多少？投资投资150元增长元增长5桶牛奶，桶牛奶，可赚回可赚回189.6元。（不小元。（不小于增长时间利润增长）于增长时间利润增长）第17页第17页结果解释结果解释B1,B2赢利有赢利有10%波动，对计划有无影响波动，对计划有无影响RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX124.0000001.680000INFINITYX216.0000008.1500002.100000X344.00000019.7500023.166667X432.0000002.026667INFINITYX5-3.00000015.8000002.533334X6-3.0000001.50INFINITYDORANGE(SENSITIVITY)ANALYSIS?YesB1赢利下降赢利下降10%，超，超出出X3系数允许范围系数允许范围B2赢利上升赢利上升10%，超，超出出X4系数允许范围系数允许范围波动对计划有影响波动对计划有影响生产计划应重新制定：如将生产计划应重新制定：如将x3系数改为系数改为39.6计计算，会发觉结果有很大改变。算，会发觉结果有很大改变。第18页第18页4.2 自来水输送与货机装运自来水输送与货机装运生产、生活物资从若干供应点运送到一些需求点，生产、生活物资从若干供应点运送到一些需求点，如何安排输送方案使运费最小，或利润最大；如何安排输送方案使运费最小，或利润最大；运送问题运送问题各种类型货品装箱，由于受体积、重量等限制，如各种类型货品装箱，由于受体积、重量等限制，如何搭配装载，使赢利最高，或装箱数量至少。何搭配装载，使赢利最高，或装箱数量至少。第19页第19页其它费用其它费用:450元元/千吨千吨 应如何分派水库供水量，公司才干赢利最多？应如何分派水库供水量，公司才干赢利最多？若水库供水量都提升一倍，公司利润可增长到多少？若水库供水量都提升一倍，公司利润可增长到多少？元元/千吨千吨甲甲乙乙丙丙丁丁A160130220170B140130190150C190200230/引水管理费引水管理费例例1 自来水输送自来水输送收入：收入：900元元/千吨千吨支出支出A：50B：60C：50甲：甲：30；50乙：乙：70；70丙：丙：10；20丁：丁：10；40水库供水量水库供水量(千吨千吨)小小区区基基本本用用水水量量(千千吨吨)小区额外用水量小区额外用水量(千吨千吨)（以天计）（以天计）第20页第20页总供水量：总供水量：160拟定送水方案拟定送水方案使利润最大使利润最大问题问题分析分析A：50B：60C：50甲：甲：30；50乙：乙：70；70丙：丙：10；20丁：丁：10；40总需求量总需求量(300)每个水库最大供水量都提升一倍每个水库最大供水量都提升一倍利润利润=收入收入(900)其它费用其它费用(450)引水管引水管理费理费利润利润(元元/千吨千吨)甲甲乙乙丙丙丁丁A290320230280B310320260300C260250220/供应供应限制限制B,C类似处理类似处理问题讨论问题讨论 拟定送水方案拟定送水方案使利润最大使利润最大需求约束能够不变需求约束能够不变第24页第24页求解求解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（元）（元）A(100)B(120)C(100)甲甲(30;50)乙乙(70;70)丙丙(10;20)丁丁(10;40)4010050305030第25页第25页如何如何装运，装运，使本次飞行使本次飞行赢利最大？赢利最大？三个货舱三个货舱最大最大载载重重(吨吨),),最大容积最大容积(米米3 3)例例2货机装运货机装运重量（吨）重量（吨）空间空间(米米3/吨）吨）利润（元利润（元/吨）吨）货品货品1184803100货品货品2156503800货品货品3235803500货品货品4123902850三个货舱中实际载重必须与其最大三个货舱中实际载重必须与其最大载载重成百分重成百分比比前仓：前仓：10；6800中仓：中仓：16；8700后仓：后仓：8；5300飞机平衡飞机平衡第26页第26页决议决议变量变量 xij-第第i 种货品装入第种货品装入第j 个货舱重量个货舱重量(吨）吨）i=1,2,3,4,j=1,2,3(分别代表前、中、后仓分别代表前、中、后仓)模型假设模型假设 每种货品能够分割到任意小；每种货品能够分割到任意小；货机装运货机装运每种货品能够在一个或多个货舱中任意分布；每种货品能够在一个或多个货舱中任意分布；各种货品能够混装，并确保不留空隙；各种货品能够混装，并确保不留空隙；模型建立模型建立 第27页第27页货舱货舱容积容积 目的目的函数函数(利润利润)约束约束条件条件货机装运货机装运模型建立模型建立 货舱货舱重量重量 10；680016；87008；5300 xij-第第i 种货品装入第种货品装入第j 个货舱重量个货舱重量第28页第28页约束约束条件条件平衡平衡要求要求 货品货品供应供应 货机装运货机装运模型建立模型建立 10；680016；87008；5300 xij-第第i 种货品装入第种货品装入第j 个货舱重量个货舱重量第29页第29页OBJECTIVEFUNCTIONVALUE1)121515.8VARIABLEVALUEREDUCEDCOSTX110.000000400.000000X120.00000057.894737X130.000000400.000000X2110.0000000.000000X220.000000239.473679X235.0000000.000000X310.0000000.000000X3212.9473690.000000X333.0000000.000000X410.000000650.000000X423.0526320.000000X430.000000650.000000货品货品2：前仓：前仓10,后仓后仓5；货品货品3:中仓中仓13,后仓后仓3；货品货品4:中仓中仓3。货机装运货机装运模型求解模型求解 最大利润约最大利润约121516元元货品货品供应点供应点货舱货舱需求点需求点平衡要求平衡要求运送运送问题问题运送问题扩展运送问题扩展第30页第30页 假如生产某一类型汽车，则至少要生产假如生产某一类型汽车，则至少要生产8080辆，辆，那么最优生产计划应作何改变？那么最优生产计划应作何改变？例例1汽车厂生产计划汽车厂生产计划汽车厂生产三种类型汽车，已知各类型每辆车对钢材、汽车厂生产三种类型汽车，已知各类型每辆车对钢材、劳动时间需求，利润及工厂每月既有量。劳动时间需求，利润及工厂每月既有量。小型小型中型中型大型大型既有量既有量钢材（吨）钢材（吨）1.535600劳动时间（小时）劳动时间（小时）28025040060000利润（万元）利润（万元）234制定月生产计划，使工厂利润最大。制定月生产计划，使工厂利润最大。4.3 汽车生产与原油采购汽车生产与原油采购第31页第31页设每月生产小、中、大型设每月生产小、中、大型汽车数量分别为汽车数量分别为x1,x2,x3汽车厂生产计划汽车厂生产计划 模型建立模型建立 小型小型中型中型大型大型既有量既有量钢材钢材1.535600时间时间28025040060000利润利润234线性线性规划规划模型模型(LP)第32页第32页模型模型求解求解 3）模型中增长条件：模型中增长条件：x1,x2,x3均为整数，重新求解。均为整数，重新求解。OBJECTIVEFUNCTIONVALUE1)632.2581VARIABLEVALUEREDUCEDCOSTX164.5161290.000000X2167.7419280.000000X30.0000000.946237ROWSLACKORSURPLUSDUALPRICES2)0.0000000.7311833)0.0000000.003226结果为小数，结果为小数，怎么办？怎么办？1）舍去小数：取）舍去小数：取x1=64，x2=167，算出目的函数值，算出目的函数值z=629，与，与LP最优值最优值632.2581相差不大。相差不大。2）试试探探：如如取取x1=65，x2=167；x1=64，x2=168等等，计计算算函函数数值值z，通过比较也许得到更优解。，通过比较也许得到更优解。但必须检查它们是否满足约束条件。为何？但必须检查它们是否满足约束条件。为何？第33页第33页IP可用可用LINDO直接求解直接求解整数规划整数规划(IntegerProgramming,简记简记IP)“gin3”表示表示“前前3个变量个变量为整数为整数”，等价于：，等价于：ginx1ginx2ginx3IP最优解最优解x1=64，x2=168，x3=0，最优值，最优值z=632max2x1+3x2+4x3st1.5x1+3x2+5x3600280 x1+250 x2+400 x360000endgin3OBJECTIVEFUNCTIONVALUE1)632.0000VARIABLEVALUEREDUCEDCOSTX164.000000-2.000000X2168.000000-3.000000X30.000000-4.000000模型求解模型求解 IP结果输出结果输出第34页第34页其中其中3个个子模型应子模型应去掉，然后去掉，然后逐一求解，比较目的函数值，逐一求解，比较目的函数值，再加上整数约束，得最优解：再加上整数约束，得最优解：办法办法1：分解为：分解为8个个LP子模型子模型汽车厂生产计划汽车厂生产计划 若生产某类汽车，则至少生产若生产某类汽车，则至少生产8080辆，求生产计划。辆，求生产计划。x1,x2,x3=0或或 80 x1=80，x2=150，x3=0，最优值，最优值z=610第35页第35页LINDO中中 对对 0-1变量限定：变量限定：inty1inty2inty3办法办法2：引入引入0-1变量，化为整数规划变量，化为整数规划M为大正数，为大正数，可取可取1000OBJECTIVEFUNCTIONVALUE1)610.0000VARIABLEVALUEREDUCEDCOSTX180.000000-2.000000X2150.000000-3.000000X30.000000-4.000000Y11.0000000.000000Y21.0000000.000000Y30.0000000.000000 若生产某类汽车，则至少生产若生产某类汽车，则至少生产8080辆，求生产计划。辆，求生产计划。x1=0 或 80 x2=0 或 80 x3=0 或 80最优解同前最优解同前第36页第36页NLP即即 使使 可可 用用 现现 成成 数数 学学 软软 件件 求求 解解(如如 LINGO,MATLAB)，但是其结果常依赖于初值选择。，但是其结果常依赖于初值选择。办法办法3：化为非线性规划化为非线性规划非线性规划（非线性规划（Non-LinearProgramming，简记，简记NLP）实实践践表表明明，本本例例仅仅当当初初值值非非常常靠靠近近上上面面办办法法算算出出最优解时，才干得到正确结果。最优解时，才干得到正确结果。若生产某类汽车，则至少生产若生产某类汽车，则至少生产8080辆，求生产计划。辆，求生产计划。x1=0 或 80 x2=0 或 80 x3=0 或 80第37页第37页应如何安排原油采购和加工应如何安排原油采购和加工？例例2原油采购与加工原油采购与加工市场上可买到不超出市场上可买到不超出1500吨原油吨原油A：购买量不超出购买量不超出500吨时单价为吨时单价为10000元元/吨；吨；购买量超出购买量超出500吨但不超出吨但不超出1000吨时，超出吨时，超出500吨吨 部分部分8000元元/吨；吨；购买量超出购买量超出1000吨时，超出吨时，超出1000吨部分吨部分6000元元/吨。吨。售价售价4800元元/吨吨售价售价5600元元/吨吨库存库存500吨吨库存库存1000吨吨汽油甲汽油甲(A 50%)原油原油A原油原油B汽油乙汽油乙(A 60%)第38页第38页决议决议变量变量 目的目的函数函数问题问题分析分析 利润：销售汽油收入利润：销售汽油收入-购买原油购买原油A支出支出 难点：原油难点：原油A购价与购买量关系较复杂购价与购买量关系较复杂甲甲(A 50%)AB乙乙(A 60%)购买购买xx11x12x21x224.8千元千元/吨吨5.6千元千元/吨吨原油原油A购买量购买量,原油原油A,B生产生产汽油汽油甲甲,乙数量乙数量c(x)购买原油购买原油A支出支出利润利润(千元千元)c(x)如何表述？如何表述？第39页第39页原油供应原油供应 约束约束条件条件 x 500吨单价为吨单价为10千千元元/吨；吨；500吨吨 x 1000吨，超出吨，超出500吨吨8千千元元/吨；吨；1000吨吨 x 1500吨，超出吨，超出1000吨吨6千千元元/吨。吨。目的目的函数函数购买购买x ABx11x12x21x22库存库存500吨吨库存库存1000吨吨第40页第40页目的函数中目的函数中c(x)不是线性函数，是非线性规划；不是线性函数，是非线性规划；对于用分段函数定义对于用分段函数定义c(x)，普通非线性规划软件也，普通非线性规划软件也难以输入和求解；难以输入和求解；想办法将模型化简，用现成软件求解。想办法将模型化简，用现成软件求解。汽油含原油汽油含原油A百分比限制百分比限制约束约束条件条件甲甲(A 50%)AB乙乙(A 60%)x11x12x21x22第41页第41页x1,x2,x3以价格以价格10,8,6(千元千元/吨吨)采购采购A吨数吨数目的目的函数函数 只有当以只有当以10千元千元/吨价格购买吨价格购买x1=500(吨吨)时，才干以时，才干以8千元千元/吨价格购买吨价格购买x2办法办法1 非线性规划模型非线性规划模型，能够用，能够用LINGO求解求解模型求解模型求解x=x1+x2+x3,c(x)=10 x1+8x2+6x3 500吨吨 x 1000吨，超出吨，超出500吨吨8千千元元/吨吨增长约束增长约束x=x1+x2+x3,c(x)=10 x1+8x2+6x3 第42页第42页办法办法1：LINGO求解求解Model:Max=4.8*x11+4.8*x21+5.6*x12+5.6*x22-10*x1-8*x2-6*x3;x11+x12x+500;x21+x220;2*x12-3*x220;x=x1+x2+x3;(x1-500)*x2=0;(x2-500)*x3=0;x1500;x2500;x30;x110;x120;x210;x220;x10;x20;x30;endObjectivevalue:4800.000VariableValueReducedCostX11500.00000.0000000E+00X21500.00000.0000000E+00X120.0000000E+000.0000000E+00X220.0000000E+000.0000000E+00X10.1021405E-1310.00000X20.0000000E+008.000000X30.0000000E+006.000000X0.0000000E+000.0000000E+00LINGO得到是局部最优解，还能得到是局部最优解，还能得到更加好解吗？得到更加好解吗？用库存用库存500吨原油吨原油A、500吨原油吨原油B生生产汽油甲，不购买新原油产汽油甲，不购买新原油A，利润，利润为为4,800千千元。元。第43页第43页y1,y2,y3=1以价格以价格10,8,6(千元千元/吨吨)采购采购A增增长长约约束束办法办法2 0-1线性规划模型线性规划模型，可用，可用LINDO求解求解y1,y2,y3=0或或1OBJECTIVEFUNCTIONVALUE1)5000.000VARIABLE VALUE REDUCEDCOSTY11.0000000.000000Y21.0000002200.000000Y31.0000001200.000000X110.0000000.800000X210.0000000.800000X121500.0000000.000000X221000.0000000.000000X1500.0000000.000000X2500.0000000.000000X30.0000000.400000X1000.0000000.000000购买购买1000吨原油吨原油A，与，与库存库存500吨原油吨原油A和和1000吨原油吨原油B一起，生产汽一起，生产汽油乙，利润为油乙，利润为5,000千元千元。x1,x2,x3以价格以价格10,8,6(千元千元/吨吨)采购采购A吨数吨数y=0 x=0 x0y=1优于办法优于办法1结果结果第44页第44页b1b2b3b4办法办法3 b1 x b2，x=z1b1+z2b2，z1+z2=1，z1,z2 0,c(x)=z1c(b1)+z2c(b2).c(x)x190005000050010001500b2 x b3，x=z2b2+z3b3，z2+z3=1，z2,z3 0,c(x)=z2c(b2)+z3c(b3).b3 x b4，x=z3b3+z4b4，z3+z4=1，z3,z4 0,c(x)=z3c(b3)+z4c(b4).直接处理处理分段线性函数直接处理处理分段线性函数c(x)第45页第45页IP模型，模型，LINDO求求解，得到结果与办解，得到结果与办法法2相同相同.处理分段线性函数，办法处理分段线性函数，办法3更具普通性更具普通性bk x bk+1yk=1,不然不然,yk=0办法办法3 bk x bk+1,x=zkbk+z k+1bk+1zk+zk+1=1，zk,zk+1 0,c(x)=zkc(bk)+zk+1c(bk+1).c(x)x190005000050010001500b1b2b3b4对于对于k=1,2,3第46页第46页分派问题分派问题4.4 接力队选拔和选课策略接力队选拔和选课策略若干项任务分给一些候选人来完成，每人专长不同，完成每项任务取得效益或需要资源就不同，怎样分派任务使取得总效益最大，或付出总资源最少。若干种策略供选择，不同策略得到收益或付出成本不同，各个策略之间有相互制约关系，怎样在满足一定条件下作出决择，使得收益最大或成本最小。第47页第47页丁蛙泳成绩退步到丁蛙泳成绩退步到115”2；戊自由泳成绩进步到；戊自由泳成绩进步到57”5,构成接力队方案是否应当调整构成接力队方案是否应当调整？如何选拔队员构成如何选拔队员构成4 4 100100米混合泳接力队米混合泳接力队?例例1混合泳接力队选拔混合泳接力队选拔甲甲乙乙丙丙丁丁戊戊蝶泳蝶泳106”857”2118”110”107”4仰泳仰泳115”6106”107”8114”2111”蛙泳蛙泳127”106”4124”6109”6123”8自由泳自由泳58”653”59”457”2102”45名候选人名候选人百米成绩百米成绩穷举法穷举法：构成接力队方案共有构成接力队方案共有5!=120种种。第48页第48页目的目的函数函数若选择队员若选择队员i参与泳姿参与泳姿j 比赛，记比赛，记xij=1,不然记不然记xij=0 0-1规划模型规划模型 cij(秒秒)队员队员i 第第j 种泳姿百米成绩种泳姿百米成绩约束约束条件条件每人最多入选泳姿之一每人最多入选泳姿之一ciji=1i=2i=3i=4i=5j=166.857.2787067.4j=275.66667.874.271j=38766.484.669.683.8j=458.65359.457.262.4每种泳姿有且只有每种泳姿有且只有1 1人人 第49页第49页模型求解模型求解 最最优优解解：x14=x21=x32=x43=1,其它变量为其它变量为0;成成绩绩为为253.2(秒秒)=413”2MIN66.8x11+75.6x12+87x13+58.6x14+67.4x51+71x52+83.8x53+62.4x54SUBJECTTOx11+x12+x13+x14=1x41+x42+x43+x44=1x11+x21+x31+x41+x51=1x14+x24+x34+x44+x54=1ENDINT20输入输入LINDO求解求解 甲甲乙乙丙丙丁丁戊戊蝶泳蝶泳106”857”2118”110”107”4仰泳仰泳115”6106”107”8114”2111”蛙泳蛙泳127”106”4124”6109”6123”8自由泳自由泳58”653”59”457”2102”4甲甲自由泳、乙自由泳、乙蝶泳、蝶泳、丙丙仰泳、丁仰泳、丁蛙泳蛙泳.第50页第50页丁蛙泳丁蛙泳c43=69.675.2，戊自由泳，戊自由泳c54=62.457.5,方案是否调整？方案是否调整？敏感性分析？敏感性分析？乙乙蝶泳、丙蝶泳、丙仰泳、仰泳、丁丁蛙泳、戊蛙泳、戊自由泳自由泳IP规划普通没有与规划普通没有与LP规划相类似理论，规划相类似理论，LINDO输输出敏感性分析结果通常是没故意义。出敏感性分析结果通常是没故意义。最优解：最优解：x21=x32=x43=x51=1,成绩为成绩为417”7c43,c54 新数据重新输入模型，用新数据重新输入模型，用LINDO求解求解 指派(Assignment)问题：每项任务有且只有一人承担，每人只能承担一项，效益不同，怎样分派使总效益最大.讨论讨论甲甲自由泳、乙自由泳、乙蝶泳、蝶泳、丙丙仰泳、丁仰泳、丁蛙泳蛙泳.原原方方案