数学建模规划问题的案例.pptx

《数学建模规划问题的案例.pptx》由会员分享，可在线阅读，更多相关《数学建模规划问题的案例.pptx（115页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、假设：1、两种产品的销量不受限制2、原材料供应不受限制约束条件：装配线1的工时限制装配线2的工时限制变量约束建立模型第1页/共115页模型求解：第2页/共115页1243657例2：最短路线问题的数学建模实例1415121013209128810第3页/共115页12436579810例3：最短路线问题算例1001502001751254002503002002751752752003501501009-101008-101506-9-103005-8-104007-8-102752-6-106004-6-105003-5-106001-4-10650最短路线为:1-4-6-9-10，长度：6

2、50第4页/共115页12436571415121013209128810例4：最小费用流问题第5页/共115页例5：最大流量问题12436571415121013209128810第6页/共115页第7页/共115页工厂定期订购原料，存入仓库供生产之用；车间一次加工出一批零件，供装配线每天生产之用；商店成批购进各种商品，放在货柜里以备零售；水库在雨季蓄水，用于旱季的灌溉和发电。存贮模型存贮量多少合适？存贮量过大，存贮费用太高；存贮量太小，会导致一次性订购费用增加，或不能及时满足需求。第8页/共115页问题1 不允许缺货的存贮模型配件厂为装配线生产若干种部件，轮换生产不同的部件时因更换设备要付

3、生产准备费（与生产数量无关），同一部件的产量大于需求时因积压资金、占用仓库要付存贮费。今已知某一部件的日需求量100件，生产准备费5000元，存贮费每日每件1元。如果生产能力远大于需求，并且不允许出现缺货，试安排该产品的生产计划，即多少天生产一次（称为生产周期），每次产量多少，可使总费用最小。第9页/共115页问题分析若每天生产一次，每次100件，无存贮费，生产准备费5000元，每天费用5000元；若10天生产一次，每次1000件，存贮费900+800+100=4500元，生产准备费5000元，总计9500元，平均每天费用950元；若50天生产一次，每次5000件，存贮费4900+4800+1

4、00=122500元，生产准备费5000元，总计127500元，平均每天费用2550元；寻找生产周期、产量、需求量、生产准备费和存贮费之间的关系，使每天的费用最少。第10页/共115页模型假设1连续化，即设生产周期T和产量Q均为连续量；2产品每日的需求量为常数r；3每次生产准备费C1，每日每件产品存贮费C2；4生产能力为无限大（相对于需求量），当存贮量降到零时，Q件产品立即生产出来供给需求，即不允许缺货。第11页/共115页模型建立总费用与变量的关系总费用=生产准备费+存贮费存贮费=存贮单价*存贮量存贮量=？第12页/共115页设t时刻的存贮量为q(t)，t=0时生产Q件，存贮量q(0)=Q,

5、q(t)以需求速率r线性递减，直至q(T)=0，如图。q(t)=Q-r t，Q=r T。otqQTrA不允许缺货模型的存贮量q(t)存贮量的计算第13页/共115页一个周期内存贮量一个周期内存贮费(A的面积)一个周期的总费用每天平均费用第14页/共115页模型求解用微分法每天平均最小费用第15页/共115页思考1建模中未考虑生产费用（这应是最大一笔费 用），在什么情况下才可以不考虑它？2建模时作了“生产能力无限大”的简化假设，如 果生产能力有限，是大于需求量的一个常数，如何建模？第16页/共115页结果解释当准备费c1增加时，生产周期和产量都变大；当存贮费c2增加时，生产周期和产量都变小；当日

6、需求费r增加时，生产周期变小而产量变大。这些定性结果符合常识，而定量关系（平方根，系数2等）凭常识是无法得出的，只能由数学建模得到。第17页/共115页这里得到的费用C与前面计算得950元有微小差别，你能解释吗？在本例中第18页/共115页敏感性分析讨论参数有微小变化时对生产周期T影响。由相对变化量衡量对参数的敏感程度。T对c1的敏感程度记为第19页/共115页意义是当准备费增加1%时，生产周期增加0.5%；而存贮费增加1%时，生产周期减少0.5%；日需求量增加1%时，生产周期减少0.5%。当有微小变化对生产周期影响不太大。第20页/共115页模型假设1连续化，即设生产周期T和产量Q均为连续量

7、；2产品每日的需求量为常数r；3每次生产准备费C1，每日每件产品存贮费C2；4生产能力为无限大（相对于需求量），允许缺货，每天每件产品缺货损失费C3，但缺货数量需在下次生产（订货）时补足。问题2允许缺货的存贮模型第21页/共115页模型建立总费用=生产准备费+存贮费+缺货损失费存贮费=存贮单价*存贮量缺货损失费=缺货单价*缺货量存贮量=？，缺货量=？第22页/共115页因存贮量不足造成缺货，因此q(t)可取负值，q(t)以需求速率r 线性递减，直至q(T1)=0，如图。q(t)=Q-r t，Q=rT1。otqQTrA允许缺货模型的存贮量q(t)RT1B第23页/共115页一个周期内缺货损失费一

8、个周期内存贮费一个周期的总费用每天平均费用第24页/共115页模型求解用微分法令每天平均最小费用第25页/共115页每个周期的供货量与不允许缺货模型相比较，有第26页/共115页结果解释即允许缺货时，周期和供货量增加，周期初的存贮量减少。2）缺货损失费愈大，愈小，愈接近，愈接近。1）3）不允许缺货模型可视为允许缺货模型的特例。第27页/共115页企业生产计划奶制品的生产与销售 空间层次工厂级：根据外部需求和内部设备、人力、原料等条件，以最大利润为目标制订产品生产计划；车间级：根据生产计划、工艺流程、资源约束及费用参数等，以最小成本为目标制订生产批量计划。时间层次若短时间内外部需求和内部资源等不

9、随时间变化，可制订单阶段生产计划，否则应制订多阶段生产计划。本节课题第28页/共115页一奶制品加工厂用牛奶生产A1、A2两种奶制品，一桶牛奶可以在甲类设备上用12小时加工成3公斤A1，或者在乙类设备上用8个小时加工成4公斤A2。根据市场需求，生产的A1，A2全部都能售出，且每公斤A1获利24元，每公斤A2获利16元。现在加工厂每天能得到50桶牛奶的供应，每天正式工人总的劳动时间为480小时，并且甲类设备每天之多能加工100公斤A1，乙类设备没有加工能力限制。试为该厂制订一个生产计划，使每天获利最大，并进一步讨论一以下3个附加问题：例1加工奶制品的生产计划35元可买到1桶牛奶，买吗？若买，每天

10、最多买多少?可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到30元/公斤，应否改变生产计划？第29页/共115页例1加工奶制品的生产计划1桶牛奶3公斤A112小时8小时4公斤A2或获利24元/公斤获利16元/公斤50桶牛奶 时间480小时 至多加工100公斤A1制订生产计划，使每天获利最大35元可买到1桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到30元/公斤，应否改变生产计划？每天：第30页/共115页1桶牛奶3公斤A112小时8小时4公斤A2或获利24元/公斤获利16元/公斤x1桶牛奶生产A1x2桶牛奶生产A2获利243x1获利

11、164 x2原料供应劳动时间加工能力决策变量目标函数每天获利约束条件非负约束线性规划模型(LP)时间480小时 至多加工100公斤A150桶牛奶每天第31页/共115页模型分析与假设比例性可加性连续性xi对目标函数的“贡献”与xi取值成正比xi对约束条件的“贡献”与xi取值成正比xi对目标函数的“贡献”与xj取值无关xi对约束条件的“贡献”与xj取值无关xi取值连续A1,A2每公斤的获利是与各自产量无关的常数每桶牛奶加工出A1,A2的数量和时间是与各自产量无关的常数A1,A2每公斤的获利是与相互产量无关的常数每桶牛奶加工出A1,A2的数量和时间是与相互产量无关的常数加工A1,A2的牛奶桶数是实

12、数线性规划模型第32页/共115页模型求解 图解法 x1x20ABCDl1l2l3l4l5约束条件目标函数Z=0Z=2400Z=3600z=c(常数)等值线c在B(20,30)点得到最优解目标函数和约束条件是线性函数可行域为直线段围成的凸多边形目标函数的等值线为直线最优解一定在凸多边形的某个顶点取得。第33页/共115页OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.00000

13、03)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2模型求解 软件实现 LINDO6.1max72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100endDORANGE(SENSITIVITY)ANALYSIS?No20桶牛奶生产A1,30桶生产A2，利润3360元。第34页/共115页OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUAL

14、PRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2：结果解释 OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2原料无剩余时间无剩余加工能力剩余40max72x1

15、+64x2st2）x1+x2503）12x1+8x24804）3x1100end三种资源“资源”剩余为零的约束为紧约束（有效约束）第35页/共115页结果解释OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2最优解下“资源”增加1单位时“效益”的增量原料增加1单位,

16、利润增长48时间增加1单位,利润增长2加工能力增长不影响利润影子价格35元可买到1桶牛奶，要买吗？3548,应该买！聘用临时工人付出的工资最多每小时几元？2元！第36页/共115页RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEF INCREASE DECREASEX1 72.000000 24.000000 8.000000X2 64.000000 8.000000 16.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEAL

17、LOWABLERHS INCREASE DECREASE2 50.000000 10.000000 6.6666673 480.000000 53.333332 80.0000004100.000000INFINITY40.000000最优解不变时目标函数系数允许变化范围DORANGE(SENSITIVITY)ANALYSIS?Yesx1系数范围(64,96)x2系数范围(48,72)A1获利增加到30元/千克，应否改变生产计划x1系数由243=72增加为303=90，在允许范围内不变！(约束条件不变)第37页/共115页结果解释 RANGESINWHICHTHEBASISISUNCHANGE

18、D:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000影子价格有意义时约束右端的允许变化范围

19、原料最多增加10时间最多增加5335元可买到1桶牛奶，每天最多买多少？最多买10桶!(目标函数不变)第38页/共115页例2奶制品的生产销售计划例1给出的A1、A2两种奶制品的生产条件、利润、及工厂的“资源”限制都不变，为增加工厂的获利，开发了奶制品的深加工技术：用2小时和3元加工费可将1公斤A1加工成0.8公斤的高级奶制品B1，也可将1公斤A2加工成0.75公斤的高级奶制品B2，每公斤B1能获利44元，每公斤B2能获利32元。试为该厂制定一个生产销售计划，使每天的净利润最大，并讨论以下问题：若投资30元可增加1桶牛奶，投资3元可增加1小时劳动时间，应否应做这些投资？现每天投资150元，可赚回

20、多少？B1，B2的获利经常有10%的波动，对定制的计划有无影响？若每公斤B1的获利下降10，计划应该变化吗？第39页/共115页例2奶制品的生产销售计划在例1基础上深加工1桶牛奶3千克A112小时8小时4公斤A2或获利24元/公斤获利16元/公斤0.8千克B12小时,3元1千克获利44元/千克0.75千克B22小时,3元1千克获利32元/千克制订生产计划，使每天净利润最大50桶牛奶,480小时至多100公斤A1若投资30元可增加1桶牛奶，投资3元可增加1小时劳动时间，应否应做这些投资？现每天投资150元，可赚回多少？B1，B2的获利经常有10%的波动，对定制的计划有无影响？若每公斤B1的获利下

21、降10，计划应该变化吗？第40页/共115页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附加约束第41页/共115页模型求解 软件实现 LINDO6.1OBJECTIVEFUNCTIONVALUE1)3460.800VARIABLEVALUEREDUCEDCOSTX10.0000001.680000X216

22、8.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=2DORANGE(SENSITIVITY)ANALYSIS?No第42页/共115页OBJECTIVEFUNCTIONVALUE1)3460.800VA

23、RIABLEVALUEREDUCEDCOSTX10.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

24、.8（元）8桶牛奶加工成A1，42桶牛奶加工成A2，将得到的24千克A1全部加工成B1除加工能力外均为紧约束第43页/共115页结果解释OBJECTIVEFUNCTIONVALUE1)3460.800VARIABLEVALUEREDUCEDCOSTX10.0000001.680000X2168.0000000.000000X319.2000010.000000X40.0000000.000000X524.0000000.000000X60.0000001.520000ROWSLACKORSURPLUSDUALPRICES2)0.0000003.1600003)0.0000003.2600004

25、)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元。（大于增加时间的利润增长）第44页/共115页结果解释B1,B2的获利有10%的波动，对计划有无影响RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFI

26、NCREASEDECREASEX124.0000001.680000INFINITYX216.0000008.1500002.100000X344.00000019.7500023.166667X432.0000002.026667INFINITYX5-3.00000015.8000002.533334X6-3.0000001.520000INFINITYDORANGE(SENSITIVITY)ANALYSIS?YesB1获利下降10%，超出X3系数允许范围B2获利上升10%，超出X4系数允许范围波动对计划有影响生产计划应重新制订：如将x3的系数改为39.6计算，会发现结果有很大变化。第45页

27、/共115页自来水输送与货机装运生产、生活物资从若干供应点运送到一些需求点，怎样安排输送方案使运费最小，或利润最大；运输问题各种类型的货物装箱，由于受体积、重量等限制，如何搭配装载，使获利最高，或装箱数量最少。第46页/共115页其他费用:450元/千吨应如何分配水库供水量，公司才能获利最多？若水库供水量都提高一倍，公司利润可增加到多少？元/千吨甲乙丙丁A160130220170B140130190150C190200230/引水管理费例例1 自来水输自来水输送送收入：900元/千吨支出A：50B：60C：50甲：30；50乙：70；70丙：10；20丁：10；40水库供水量(千吨)小区基本用

28、水量(千吨)小区额外用水量(千吨)（以天计）第47页/共115页总供水量：160确定送水方案使利润最大问题分析A：50B：60C：50甲：30；50乙：70；70丙：10；20丁：10；40总需求量(300)每个水库最大供水量都提高一倍利润=收入(900)其它费用(450)引水管理费利润(元/千吨)甲乙丙丁A290320230280B310320260300C260250220/供应限制B,C类似处理问题讨论 确定送水方案使利润最大需求约束可以不变第51页/共115页求解OBJECTIVEFUNCTIONVALUE1)88700.00VARIABLEVALUEREDUCEDCOSTX110.0

29、0000020.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)丙(1

30、0;20)丁(10;40)4010050305030第52页/共115页如何装运，使本次飞行获利最大？三个货舱最大载重(吨),最大容积(米3)例例2 货机装货机装运运重量（吨）空间(米3/吨）利润（元/吨）货物1184803100货物2156503800货物3235803500货物4123902850三个货舱中实际载重必须与其最大载重成比例前仓：10；6800中仓：16；8700后仓：8；5300飞机平衡第53页/共115页决策变量xij-第i 种货物装入第j 个货舱的重量(吨）i=1,2,3,4,j=1,2,3(分别代表前、中、后仓)模型假设每种货物可以分割到任意小；货机装运每种货物可以在一

31、个或多个货舱中任意分布；多种货物可以混装，并保证不留空隙；模型建立第54页/共115页货舱容积目标函数(利润)约束条件货机装运模型建立 货舱重量10；680016；87008；5300 xij-第i 种货物装入第j 个货舱的重量第55页/共115页约束条件平衡要求货物供应货机装运模型建立 10；680016；87008；5300 xij-第i 种货物装入第j 个货舱的重量第56页/共115页OBJECTIVEFUNCTIONVALUE1)121515.8VARIABLEVALUEREDUCEDCOSTX110.000000400.000000X120.00000057.894737X130.0

32、00000400.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元货物供应点货舱需求点平衡要求运输问题运输问题的扩展第57页/共115页设每月生产小、中、大型汽车的数量

33、分别为x1,x2,x3汽车厂生产计划 模型建立小型中型大型现有量钢材1.535600时间28025040060000利润234线性规划模型(LP)第58页/共115页模型求解 3）模型中增加条件：x1,x2,x3均为整数，重新求解。OBJECTIVEFUNCTIONVALUE1)632.2581VARIABLEVALUEREDUCEDCOSTX164.5161290.000000X2167.7419280.000000X30.0000000.946237ROWSLACKORSURPLUSDUALPRICES2)0.0000000.7311833)0.0000000.003226结果为小数，怎么

34、办？1）舍去小数：取x1=64，x2=167，算出目标函数值z=629，与LP最优值632.2581相差不大。2）试探：如取x1=65，x2=167；x1=64，x2=168等，计算函数值z，通过比较可能得到更优的解。但必须检验它们是否满足约束条件。为什么？第59页/共115页IP可用LINDO直接求解整数规划(IntegerProgramming,简记IP)“gin3”表示“前3个变量为整数”，等价于：ginx1ginx2ginx3IP的最优解x1=64，x2=168，x3=0，最优值z=632max2x1+3x2+4x3st1.5x1+3x2+5x3600280 x1+250 x2+400

35、 x360000endgin3OBJECTIVEFUNCTIONVALUE1)632.0000VARIABLEVALUEREDUCEDCOSTX164.000000-2.000000X2168.000000-3.000000X30.000000-4.000000模型求解 IP结果输出第60页/共115页其中3个子模型应去掉，然后逐一求解，比较目标函数值，再加上整数约束，得最优解：方法1：分解为8个LP子模型汽车厂生产计划 若生产某类汽车，则至少生产80辆，求生产计划。x1,x2,x3=0或80 x1=80，x2=150，x3=0，最优值z=610第61页/共115页LINDO中对0-1变量的限

36、定：inty1inty2inty3方法2：引入0-1变量，化为整数规划M为大的正数，可取1000OBJECTIVEFUNCTIONVALUE1)610.0000VARIABLEVALUEREDUCEDCOSTX180.000000-2.000000X2150.000000-3.000000X30.000000-4.000000Y11.0000000.000000Y21.0000000.000000Y30.0000000.000000若生产某类汽车，则至少生产80辆，求生产计划。x1=0或80 x2=0或80 x3=0或80最优解同前第62页/共115页NLP虽 然 可 用 现 成 的 数 学

37、软 件 求 解(如 LINGO,MATLAB)，但是其结果常依赖于初值的选择。方法3：化为非线性规划非线性规划（Non-LinearProgramming，简记NLP）实践表明，本例仅当初值非常接近上面方法算出的最优解时，才能得到正确的结果。若生产某类汽车，则至少生产80辆，求生产计划。x1=0或80 x2=0或80 x3=0或80第63页/共115页应如何安排原油的采购和加工？例例2 原油采购与加原油采购与加工工 市场上可买到不超过1500吨的原油A：购买量不超过500吨时的单价为10000元/吨；购买量超过500吨但不超过1000吨时，超过500吨的部分8000元/吨；购买量超过1000吨

38、时，超过1000吨的部分6000元/吨。售价4800元/吨售价5600元/吨库存500吨库存1000吨汽油甲(A50%)原油A原油B汽油乙(A60%)第64页/共115页决策变量目标函数问题分析利润：销售汽油的收入-购买原油A的支出难点：原油A的购价与购买量的关系较复杂甲(A50%)AB乙(A60%)购买xx11x12x21x224.8千元/吨5.6千元/吨原油A的购买量,原油A,B生产汽油甲,乙的数量c(x)购买原油A的支出利润(千元)c(x)如何表述？第65页/共115页原油供应约束条件 x 500吨单价为10千元/吨；500吨x1000吨，超过500吨的8千元/吨；1000吨x1500吨

39、，超过1000吨的6千元/吨。目标函数购买xABx11x12x21x22库存500吨库存1000吨第66页/共115页目标函数中c(x)不是线性函数，是非线性规划；对于用分段函数定义的c(x)，一般的非线性规划软件也难以输入和求解；想办法将模型化简，用现成的软件求解。汽油含原油A的比例限制约束条件甲(A50%)AB乙(A60%)x11x12x21x22第67页/共115页x1,x2,x3以价格10,8,6(千元/吨)采购A的吨数目标函数只有当以10千元/吨的价格购买x1=500(吨)时，才能以8千元/吨的价格购买x2方法1非线性规划模型，可以用LINGO求解模型求解x=x1+x2+x3,c(x

40、)=10 x1+8x2+6x3500吨 x1000吨，超过500吨的8千元/吨增加约束x=x1+x2+x3,c(x)=10 x1+8x2+6x3第68页/共115页方法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.000V

41、ariableValueReducedCostX11500.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千元。第69页/

42、共115页y1,y2,y3=1以价格10,8,6(千元/吨)采购A增加约束方法20-1线性规划模型，可用LINDO求解y1,y2,y3=0或1OBJECTIVEFUNCTIONVALUE1)5000.000VARIABLE VALUE REDUCEDCOSTY1 1.000000 0.000000Y2 1.000000 2200.000000Y3 1.000000 1200.000000X11 0.000000 0.800000X21 0.000000 0.800000X121500.0000000.000000X221000.0000000.000000X1 500.000000 0.000

43、000X2 500.000000 0.000000X3 0.000000 0.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的结果第70页/共115页b1b2b3b4方法3b1 xb2，x=z1b1+z2b2，z1+z2=1，z1,z20,c(x)=z1c(b1)+z2c(b2).c(x)x1200090005000050010001500b2 xb3，x=z2b2+z3b3，z2+z3=1，z

44、2,z30,c(x)=z2c(b2)+z3c(b3).b3 xb4，x=z3b3+z4b4，z3+z4=1，z3,z40,c(x)=z3c(b3)+z4c(b4).直接处理处理分段线性函数c(x)第71页/共115页IP模型，LINDO求解，得到的结果与方法2相同.处理分段线性函数，方法3更具一般性bkxbk+1yk=1,否则,yk=0方法3bkxbk+1,x=zkbk+z k+1bk+1zk+zk+1=1，zk,zk+10,c(x)=zkc(bk)+zk+1c(bk+1).c(x)x1200090005000050010001500b1b2b3b4对于k=1,2,3第72页/共115页分派问

45、题接力队选拔和选课策略若干项任务分给一些候选人来完成，每人的专长不同，完成每项任务取得的效益或需要的资源就不同，如何分派任务使获得的总效益最大，或付出的总资源最少。若干种策略供选择，不同的策略得到的收益或付出的成本不同，各个策略之间有相互制约关系，如何在满足一定条件下作出决择，使得收益最大或成本最小。第73页/共115页丁的蛙泳成绩退步到115”2；戊的自由泳成绩进步到57”5,组成接力队的方案是否应该调整？如何选拔队员组成4100米混合泳接力队?例例1 混合泳接力队的选拔混合泳接力队的选拔 甲乙丙丁戊蝶泳106”857”2118”110”107”4仰泳115”6106”107”8114”21

46、11”蛙泳127”106”4124”6109”6123”8自由泳58”653”59”457”2102”45名候选人的百米成绩穷举法：组成接力队的方案共有5!=120种。第74页/共115页目标函数若选择队员i参加泳姿j 的比赛，记xij=1,否则记xij=00-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人第75页/共115页模型求解最优解

47、：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”

48、457”2102”4甲自由泳、乙蝶泳、丙仰泳、丁蛙泳.第76页/共115页丁蛙泳c43=69.675.2，戊自由泳c54=62.457.5,方案是否调整？敏感性分析？乙蝶泳、丙仰泳、丁蛙泳、戊自由泳IP规划一般没有与LP规划相类似的理论，LINDO输出的敏感性分析结果通常是没有意义的。最优解：x21=x32=x43=x51=1,成绩为417”7c43,c54的新数据重新输入模型，用LINDO求解指派(Assignment)问题：每项任务有且只有一人承担，每人只能承担一项，效益不同，怎样分派使总效益最大.讨论甲自由泳、乙蝶泳、丙仰泳、丁蛙泳.原方案第77页/共115页为了选修课程门数最少，应学习

49、哪些课程？例例2 选课策略选课策略要求至少选两门数学课、三门运筹学课和两门计算机课课号课名学分所属类别先修课要求1微积分5数学2线性代数4数学3最优化方法4数学；运筹学微积分；线性代数4数据结构3数学；计算机计算机编程5应用统计4数学；运筹学微积分；线性代数6计算机模拟3计算机；运筹学计算机编程7计算机编程2计算机8预测理论2运筹学应用统计9数学实验3运筹学；计算机微积分；线性代数选修课程最少，且学分尽量多，应学习哪些课程？第78页/共115页0-1规划模型决策变量目标函数xi=1选修课号i 的课程（xi=0不选）选修课程总数最少约束条件最少2门数学课，3门运筹学课，2门计算机课。课号课名所属

50、类别1微积分数学2线性代数数学3最优化方法数学；运筹学4数据结构数学；计算机5应用统计数学；运筹学6计算机模拟计算机；运筹学7计算机编程计算机8预测理论运筹学9数学实验运筹学；计算机第79页/共115页先修课程要求最优解：x1=x2=x3=x6=x7=x9=1,其它为0；6门课程，总学分210-1规划模型约束条件x3=1必有x1=x2=1模型求解（LINDO）课号课名先修课要求1微积分2线性代数3最优化方法微积分；线性代数4数据结构计算机编程5应用统计微积分；线性代数6计算机模拟计算机编程7计算机编程8预测理论应用统计9数学实验微积分；线性代数第80页/共115页学分最多多目标优化的处理方法：