第二讲线性规划模型教材课件

第二讲线性规划模型统计与应用数学系张耀峰Themodeloflinearprogramming6/7/20231第二讲线性规划模型1.1优化的思想1.2什么是线性规划模型1.3如何使用Lingo软件求解线性规划问题1.4案例解析6/7/202321.1

优化的思想6/7/20233烧水小明同学，烧一壶水要8分钟，灌开水要1分钟，取牛奶和报纸要5分钟（不能间断），整理书包要6分钟（可间断），为了尽快做完这些事，怎样安排才能使时间最少？最少需要几分钟？

例1、如何安排早上的时间？取牛奶和报纸收拾书包灌水收拾书包5891206/7/20234例2、怎么排队才合理呢？

码头上现在同时有3艘货船需要卸货，但是只能一条一条地卸货，并且每艘船卸货所需的时间各不相同，分别为4小时、8小时和1小时。按照怎样的顺序卸货能使3艘货船等候的总时间最少呢？

6/7/20235方案卸货顺序船1的等候时间船2的等候时间船3的等候时间总的等候时间1船1—船2—船388+48+4+1332船1—船3—船288+1+48+1303船2—船1—船34+844+8+1294船2—船3—船14+1+844+1225船3—船1—船21+81+8+41236船3—船2—船11+4+81+41196/7/202361.2什么是线性规划模型6/7/20237例3运输问题6/7/20238解：设A1,A2调运到三个粮站的大米分别为x11，x12，

x13，

x21，

x22，

x23吨。题设量可总到下表：84库存量x23x22x21A2542需要量x13x12x11A1B3B2B1粮库粮站距离及运量121224308246/7/20239结合存量限制和需量限制得数学模型：目标函数约束条件决策变量6/7/2023101.3如何使用Lingo软件求解线性规划问题6/7/202311程序编写１model:min=12*x11+24*x12+8*x13+30*x21+12*x22+24*x23;x11+x12+x13<4;x21+x22+x23<8;x11+x21>2;x12+x22>4;x13+x23>5;end6/7/202312运行结果

Globaloptimalsolutionfound.Objectivevalue:160.0000Totalsolveriterations:5VariableValueReducedCostX112.0000000.000000X120.00000028.00000X132.0000000.000000X210.0000002.000000X224.0000000.000000X233.0000000.000000RowSlackorSurplusDualPrice1160.0000-1.00000020.00000016.0000031.0000000.00000040.000000-28.0000050.000000-12.0000060.000000-24.000006/7/202313

例4生产计划问题某工厂计划安排生产Ⅰ，Ⅱ两种产品，已知每种单位产品的利润，生产单位产品所需设备台时及A,B两种原材料的消耗，现有原材料和设备台时的定额如表所示，问：１）怎么安排生产使得工厂获利最大？２）产品Ⅰ的单位利润降低到1.8万元，要不要改变生产计划，如果降低到1万元呢？３）产品Ⅱ的单位利润增大到5万，要不要改变生产计划４）如果产品Ⅰ，Ⅱ的单位利润同时降低了1万元，要不要改变生产计划？

产品Ⅰ产品Ⅱ最大资源量设备128台时原材料A4016kg原材料B0412kg单位产品利润236/7/2023146/7/202315程序编写model:title生产计划问题;[maxf]max=2*x1+3*x2;[A]x1+2*x2<8;[B]4*x1<16;[TIME]4*x2<12;END6/7/202316运行结果

ModelTitle:生产计划问题

VariableValueReducedCostX14.0000000.000000X22.0000000.000000RowSlackorSurplusDualPriceMAXF14.000001.000000A0.0000001.500000B0.0000000.1250000TIME4.0000000.000000

对问题1，安排是生产产品Ⅰ4单位，产品Ⅱ2单位，最大盈利为14万元。6/7/202317线性模型－敏感性分析要使用敏感性分析必须要在这里选择Prices&Ranges然后保存退出路径：LINGO︱Options︱GeneralSolver(通用求解程序)选项卡6/7/202318要调出敏感性分析的结果，必须先求解后再在程序窗口下点击LINGO｜Range，

6/7/202319Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRanges

CurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX12.000000INFINITY0.5000000X23.0000001.0000003.000000

RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecreaseA8.0000002.0000004.000000B16.0000016.000008.000000TIME12.00000INFINITY4.000000

当前变量系数允许增加量允许减少量6/7/202320对问题4，因为两个系数同时改变了，所以只有更改程序的数据，重新运行得：不改变生产计划，但是最大利润降低到6万元.

对问题2，产品Ⅰ的单位利润降低到1.8万元，在（1.5，∞）之间，所以不改变生产计划。如果降低到1万元，不在（1.5，∞）内，要改变生产计划。在程序中将目标函数的系数“2”改为“1”，可得新的计划为安排是生产产品Ⅰ2单位，产品Ⅱ3单位，最大盈利为11万元.对问题3，要改变生产计划，更改程序得新计划为生产产品Ⅰ2单位，产品Ⅱ3单位，最大盈利为19万元.6/7/202321例5

加工奶制品的生产计划1桶牛奶3公斤A1

12小时8小时4公斤A2

或获利24元/公斤获利16元/公斤50桶牛奶时间480小时至多加工100公斤A1

制订生产计划，使每天获利最大

35元可买到1桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元?

A1的获利增加到30元/公斤，应否改变生产计划？每天：6/7/2023221桶牛奶3公斤A1

12小时8小时4公斤A2

或获利24元/公斤获利16元/公斤x1桶牛奶生产A1

x2桶牛奶生产A2

获利24×3x1

获利16×4x2

原料供应

劳动时间

加工能力

决策变量

目标函数

每天获利约束条件非负约束

线性规划模型(LP)时间480小时至多加工100公斤A1

50桶牛奶每天6/7/202323模型求解

OBJECTIVEFUNCTIONVALUE

1)3360.000

VARIABLEVALUEREDUCEDCOST

X120.0000000.000000

X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=220桶牛奶生产A1,30桶生产A2，利润3360元。max=72*x1+64*x2;x1+x2<50;12*x1+8*x2<480;3*x1<100;6/7/202324模型求解

reducedcost值表示当该非基变量增加一个单位时（其他非基变量保持不变）目标函数减少的量(对max型问题)

OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=26/7/202325OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000

ROW

SLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.0000004)40.0000000.000000原料无剩余时间无剩余加工能力剩余40max72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100end三种资源结果解释

6/7/202326OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.000000

4)40.0000000.000000结果解释

最优解下“资源”增加1单位时“效益”的增量原料增1单位,利润增48时间加1单位,利润增2能力增减不影响利润影子价格

35元可买到1桶牛奶，要买吗？35<48,应该买！聘用临时工人付出的工资最多每小时几元？2元！6/7/202327RANGESINWHICHTHEBASISISUNCHANGED:

OBJCOEFFICIENTRANGES

VARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASE

X172.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系数由243=72增加为303=90，在允许范围内不变！(约束条件不变)结果解释

6/7/202328结果解释

RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000

RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000影子价格有意义时约束右端的允许变化范围原料最多增加10时间最多增加53

35元可买到1桶牛奶，每天最多买多少？最多买10桶？(目标函数不变)6/7/2023291.4案例分析6/7/202330例6阶段生产问题某公司生产某产品,最大生产能力为10000单位,每单位存储费2元,预定的销售量与单位成本如下:月份单位成本(元)销售量1234

706000

71

70008012000766000求一生产计划,使1)满足需求;2)不超过生产能力;3)成本(生产成本与存储费之和)最低.6/7/202331解:假定1月初无库存,4月底卖完,当月生产的不库存,库存量无限制.第j+1个月的库存量第j+1个月的库存费共3个月的库存费到本月总生产量大于等于销售量4个月总生产量等于总销售量4个月总生产成本6/7/202332model:title

生产计划程序1;Sets:yuefen/1..4/:c,x,e,d;endsetsdata:c=70718076;d=60007000120006000;e=2222;a=10000;enddatamin=@sum(yuefen:c*x)+

@sum(yuefen(j)|j#lt#4:

@sum(yuefen(i)|i#le#j:x-d)*e(j+1));@for(yuefen(j)|j#lt#4:

@sum(yuefen(i)|i#le#j:x)>@sum(yuefen(i)|i#le#j:d));@sum(yuefen:x)=@sum(yuefen:d);@for(yuefen:x<a);end

6/7/202333露天矿里铲位已分成矿石和岩石:平均铁含量不低于25%的为矿石，否则为岩石。每个铲位的矿石、岩石数量，以及矿石的平均铁含量（称为品位）都是已知的。每个铲位至多安置一台电铲，电铲平均装车时间5分钟卡车在等待时所耗费的能量也是相当可观的，原则上在安排时不应发生卡车等待的情况。例7、露天矿生产的车辆安排(CUMCM-2003B)

矿石卸点需要的铁含量要求都为29.5%1%(品位限制），搭配量在一个班次（8小时）内满足品位限制即可。卸点在一个班次内不变。卡车载重量为154吨，平均时速28km,平均卸车时间为3分钟。问题：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次?6/7/202334平面示意图6/7/202335问题数据距离铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏5.265.194.214.002.952.742.461.900.641.27倒装Ⅰ1.900.991.901.131.272.251.482.043.093.51岩场5.895.615.614.563.513.652.462.461.060.57岩石漏0.641.761.271.832.742.604.213.725.056.10倒装Ⅱ4.423.863.723.162.252.810.781.621.270.50铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石量0．951．051．001．051．101．251．051．301．351．25岩石量1．251．101．351．051．151．351．051．151．351．25铁含量30%28%29%32%31%33%32%31%33%31%6/7/202336问题分析与典型的运输问题明显有以下不同：这是运输矿石与岩石两种物资的问题；属于产量大于销量的不平衡运输问题；为了完成品位约束，矿石要搭配运输；产地、销地均有单位时间的流量限制；运输车辆只有一种，每次满载运输，154吨/车次；铲位数多于铲车数意味着要最优的选择不多于7个产地作为最后结果中的产地；最后求出各条路线上的派出车辆数及安排。近似处理：先求出产位、卸点每条线路上的运输量(MIP模型)然后求出各条路线上的派出车辆数及安排6/7/202337模型假设卡车在一个班次中不应发生等待或熄火后再启动的情况；在铲位或卸点处由两条路线以上造成的冲突问题面前，我们认为只要平均时间能完成任务，就认为不冲突。我们不排时地进行讨论；空载与重载的速度都是28km/h，耗油相差很大；卡车可提前退出系统，等等。如理解为严格不等待，难以用数学规划模型来解个别参数队找到了可行解（略）6/7/202338符号xij

：从i铲位到j号卸点的石料运量（车）