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

1、2023-5-221第二讲第二讲 线性规划模型线性规划模型统计与应用数学系统计与应用数学系张耀峰张耀峰The modelThe model of linear programming of linear programming2023-5-222第第二二讲讲 线性规划模型线性规划模型1.1 优化的思想优化的思想1.2 什么是线性规划模型什么是线性规划模型1.3 如何使用如何使用Lingo软件求解软件求解 线性规划问题线性规划问题1.4 案例解析案例解析2023-5-2231.1 优化的思想优化的思想2023-5-224烧水烧水 小明同学，烧一壶水要小明同学，烧一壶水要8分钟，灌开水要分钟，灌开

2、水要1分钟，分钟，取牛奶和报纸要取牛奶和报纸要5分钟（不能间断），整理书包要分钟（不能间断），整理书包要6分钟（可间断），为了尽快做完这些事，怎样安排才分钟（可间断），为了尽快做完这些事，怎样安排才能使时间最少？最少需要几分钟？能使时间最少？最少需要几分钟？例例1、如何安排早上的时间？、如何安排早上的时间？取牛奶和报纸取牛奶和报纸收拾书包收拾书包灌水灌水收拾书包收拾书包5891202023-5-225例例2、怎么排队才合理呢？、怎么排队才合理呢？码头上现在同时有码头上现在同时有3艘货船需要卸货，但是只艘货船需要卸货，但是只能一条一条地卸货，并且每艘船卸货所需的时间能一条一条地卸货，并且每艘船卸

3、货所需的时间各不相同，分别为各不相同，分别为4小时、小时、8小时和小时和1小时。按照怎小时。按照怎样的顺序卸货能使样的顺序卸货能使3艘货船等候的总时间最少呢？艘货船等候的总时间最少呢？2023-5-226方案卸货顺序船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+41192023-5-2271.2 什么是线性规划模型什么是线性规划模型2023-5-228例例3 3 运输问题运输问题。

4、问问如如何何调调运运使使运运费费最最低低如如下下公公里里单单位位距距离离两两个个粮粮库库到到三三个个粮粮站站的的吨吨大大米米分分别别为为三三个个粮粮站站至至少少需需要要吨吨吨吨为为两两个个粮粮库库现现存存大大米米分分别别调调运运大大米米向向三三个个粮粮站站有有两两个个粮粮库库,):(,5,4,2,8,4,32121BBBAA2023-5-229解：设解：设A1,A2调运到三个粮站的大米分别为调运到三个粮站的大米分别为x11，x12，x13，x21，x22，x23吨。吨。题设量可总到下表：题设量可总到下表：84库库存存量量x23x22x21A2542需要量需要量x13x12x11A1B3B2B1

5、粮库粮库粮站粮站距离及运量距离及运量121224308242023-5-2210结合存量限制和需量限制得数学模型结合存量限制和需量限制得数学模型：23222113121124123082412xxxxxxf min 054284232221131211231322122111232221131211xxxxxxxxxxxxxxxxxxts,.目标目标函数函数约束约束条件条件决策决策变量变量2023-5-22111.3如何使用如何使用Lingo软件求解线性规划问题软件求解线性规划问题2023-5-2212程序编写程序编写model:min=12*x11+24*x12+8*x13+30*x21+1

6、2*x22+24*x23;x11+x12+x134;x21+x22+x232;x12+x224;x13+x235;end2023-5-2213运行结果运行结果 Global optimal solution found.Objective value:160.0000 Total solver iterations:5 Variable Value Reduced Cost X11 2.000000 0.000000 X12 0.000000 28.00000 X13 2.000000 0.000000 X21 0.000000 2.000000 X22 4.000000 0.000000 X

7、23 3.000000 0.000000 Row Slack or Surplus Dual Price 1 160.0000 -1.000000 2 0.000000 16.00000 3 1.000000 0.000000 4 0.000000 -28.00000 5 0.000000 -12.00000 6 0.000000 -24.000002023-5-2214 例例4 生产计划问题生产计划问题某工厂计划安排生产某工厂计划安排生产，两种产两种产品，已知每种单位产品的利润，生产单位产品所需设备品，已知每种单位产品的利润，生产单位产品所需设备台时及台时及A,B两种原材料的消耗，现有原材料

8、和设备台时的两种原材料的消耗，现有原材料和设备台时的定额如表所示，问：定额如表所示，问：）怎么安排生产使得工厂获利最大？）怎么安排生产使得工厂获利最大？）产品）产品的单位利润降低到的单位利润降低到1.8万元，要不要改变生产万元，要不要改变生产计划，如果降低到计划，如果降低到1万元呢？万元呢？）产品）产品的单位利润增大到的单位利润增大到5万，要不要改变生产计划万，要不要改变生产计划）如果产品）如果产品，的单位利润同时降低了的单位利润同时降低了1万元，要不万元，要不要改变生产计划？要改变生产计划？产品产品最大资源量设备128台时原材料A4016kg原材料B0412kg单位产品利润232023-5-

9、22152023-5-2216程序编写程序编写model:title 生产计划问题生产计划问题;maxfmax=2*x1+3*x2;Ax1+2*x28;B4*x116;TIME4*x212;END2023-5-2217运行结果运行结果 Model Title:生产计划问题生产计划问题 Variable Value Reduced Cost X1 4.000000 0.000000 X2 2.000000 0.000000 Row Slack or Surplus Dual Price MAXF 14.00000 1.000000 A 0.000000 1.500000 B 0.000000 0

10、.1250000 TIME 4.000000 0.000000 对问题对问题1，安排是生产产品，安排是生产产品4单位，产品单位，产品2单位，单位，最大盈利为最大盈利为14万元万元。2023-5-2218 线性模型敏感性分析要使用敏感性分析要使用敏感性分析必须要在这里选择必须要在这里选择Prices&Ranges然后然后保存保存退出退出路径：路径：LINGOOptionsGeneral Solver(通用求解程序通用求解程序)选项卡选项卡2023-5-2219要调出敏感性分析的结果，要调出敏感性分析的结果，必须必须先求解先求解后再后再在程序窗在程序窗口下口下点击点击LINGORange，2023

11、-5-2220 Ranges in which the basis is unchanged:Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease X1 2.000000 INFINITY 0.5000000 X2 3.000000 1.000000 3.000000 Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease A 8.000000 2.000000

12、4.000000 B 16.00000 16.00000 8.000000 TIME 12.00000 INFINITY 4.000000 当前变量系数允许增加量允许减少量2023-5-2221 对问题对问题4，因为两个系数同时改变了，所以只，因为两个系数同时改变了，所以只有更有更 改程序的数据，重新运行得：不改变生产计改程序的数据，重新运行得：不改变生产计划，但是最大利润降低到划，但是最大利润降低到6万元万元.对问题对问题2，产品，产品的单位利润降低到的单位利润降低到1.8万元，万元，在（在（1.5，）之间，所以不改变生产计划。如果降）之间，所以不改变生产计划。如果降低到低到1万元，不在（万

13、元，不在（1.5，）内，要改变生产计划。）内，要改变生产计划。在程序中将目标函数的系数在程序中将目标函数的系数“2”改为改为“1”，可得新，可得新的计划为安排是生产产品的计划为安排是生产产品2单位，产品单位，产品3单位，单位，最大盈利为最大盈利为11万元万元.对问题对问题3，要改变生产计划，更改程序得新，要改变生产计划，更改程序得新计划为生产产品计划为生产产品2单位，产品单位，产品3单位，最大盈单位，最大盈利为利为19万元万元.2023-5-2222例例5 加工奶制品的生产计划加工奶制品的生产计划1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛

14、奶桶牛奶 时间时间480小时小时 至多加工至多加工100公斤公斤A1 制订生产计划，使每天获利最大制订生产计划，使每天获利最大 35元可买到元可买到1桶牛奶，买吗？若买，每天最多买多少桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到的获利增加到 30元元/公斤，应否改变生产计划？公斤，应否改变生产计划？每天：每天：2023-5-22231桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 x1桶牛奶生产桶牛奶生产A1 x2桶牛奶生产桶牛奶生产A2 获利获利 243x1

15、获利获利 164 x2 原料供应原料供应 5021 xx劳动时间劳动时间 48081221 xx加工能力加工能力 10031x决策变量决策变量 目标函数目标函数 216472xxzMax每天获利每天获利约束条件约束条件非负约束非负约束 0,21xx线性线性规划规划模型模型(LP)时间时间480小时小时 至多加工至多加工100公斤公斤A1 50桶牛奶桶牛奶 每天每天2023-5-2224模型求解模型求解 OBJECTIVE FUNCTION VALUE 1)3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.00000

16、0 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 48.000000 3)0.000000 2.000000 4)40.000000 0.000000 NO.ITERATIONS=220桶牛奶生产桶牛奶生产A1,30桶生产桶生产A2，利润，利润3360元。元。max=72*x1+64*x2;x1+x250;12*x1+8*x2480;3*x1100;2023-5-2225模型求解模型求解 reduced cost值表值表示当该非基变量示当该非基变量增加一个单位时增加一个单位时（其他非基变量（其他非基变量保持不变）目标保持不变）目标函数

17、减少的量函数减少的量(对对max型问题型问题)OBJECTIVE FUNCTION VALUE 1)3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 48.000000 3)0.000000 2.000000 4)40.000000 0.000000 NO.ITERATIONS=22023-5-2226 OBJECTIVE FUNCTION VALUE 1)3360.000 VARIABLE VA

18、LUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 48.000000 3)0.000000 2.000000 4)40.000000 0.000000原料无剩余原料无剩余时间无剩余时间无剩余加工能力剩余加工能力剩余40max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三三种种资资源源结果解释结果解释 2023-5-2227 OBJECTIVE FUNCTION VALUE 1)3360.00

19、0 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 48.000000 3)0.000000 2.000000 4)40.000000 0.000000结果解释结果解释 最优解下最优解下“资源资源”增增加加1单位时单位时“效益效益”的的增量增量 原料增原料增1单位单位,利润增利润增48 时间加时间加1单位单位,利润增利润增2 能力增减不影响利润能力增减不影响利润影子价格影子价格 35元可买到元可买到1桶牛奶，要买

20、吗？桶牛奶，要买吗？35 sum(yuefen(i)|i#le#j:d);sum(yuefen:x)=sum(yuefen:d);for(yuefen:xa);end 2023-5-2234露天矿里铲位已分成矿石和岩石露天矿里铲位已分成矿石和岩石:平均铁含量不低于平均铁含量不低于25%的为矿石，否则为岩石。每个铲位的矿石、岩石数的为矿石，否则为岩石。每个铲位的矿石、岩石数量，以及矿石的平均铁含量（称为品位）都是已知的。量，以及矿石的平均铁含量（称为品位）都是已知的。每个铲位至多安置一台电铲，电铲平均装车时间每个铲位至多安置一台电铲，电铲平均装车时间5分钟分钟卡车在等待时所耗费的能量也是相当可观

21、的，原则上卡车在等待时所耗费的能量也是相当可观的，原则上在安排时不应发生卡车等待的情况。在安排时不应发生卡车等待的情况。例例7、露天矿生产的车辆安排露天矿生产的车辆安排(CUMCM-2003B)矿石卸点需要的铁含量要求都为矿石卸点需要的铁含量要求都为29.5%1%(品位限品位限制），搭配量在一个班次（制），搭配量在一个班次（8小时）内满足品位限制即小时）内满足品位限制即可。卸点在一个班次内不变。卡车载重量为可。卸点在一个班次内不变。卡车载重量为154吨，平吨，平均时速均时速28km,平均卸车时间为平均卸车时间为3分钟。分钟。问题：出动几台电铲，分别在哪些铲位上；出动几辆问题：出动几台电铲，分别

22、在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次卡车，分别在哪些路线上各运输多少次?2023-5-2235平面示意图2023-5-2236问题数据问题数据 距离铲位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

23、.162.252.810.781.621.270.50铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石量095105100105110125105130135125岩石量125110135105115135105115135125铁含量30%28%29%32%31%33%32%31%33%31%2023-5-2237问题分析问题分析 与典型的运输问题明显有以下不同：与典型的运输问题明显有以下不同：1.这是运输矿石与岩石两种物资的问题；这是运输矿石与岩石两种物资的问题；2.属于产量大于销量的不平衡运输问题；属于产量大于销量的不平衡运输问题；3.为了完成品位约束，矿石要搭配运输；

24、为了完成品位约束，矿石要搭配运输；4.产地、销地均有单位时间的流量限制；产地、销地均有单位时间的流量限制；5.运输车辆只有一种，每次满载运输，运输车辆只有一种，每次满载运输，154吨吨/车次；车次；6.铲位数多于铲车数意味着要最优的选择不多于铲位数多于铲车数意味着要最优的选择不多于7个个产地作为最后结果中的产地；产地作为最后结果中的产地；7.最后求出各条路线上的派出车辆数及安排。最后求出各条路线上的派出车辆数及安排。近似处理：近似处理：先求出产位、卸点每条线路上的运输量先求出产位、卸点每条线路上的运输量(MIP模型模型)然后求出各条路线上的派出车辆数及安排然后求出各条路线上的派出车辆数及安排2

25、023-5-2238模型假设模型假设v卡车在一个班次中不应发生等待或熄火后再启动卡车在一个班次中不应发生等待或熄火后再启动的情况；的情况；v在铲位或卸点处由两条路线以上造成的冲突问题在铲位或卸点处由两条路线以上造成的冲突问题面前，我们认为只要平均时间能完成任务，就认面前，我们认为只要平均时间能完成任务，就认为不冲突。我们不排时地进行讨论；为不冲突。我们不排时地进行讨论；v空载与重载的速度都是空载与重载的速度都是28km/h，耗油相差很大；，耗油相差很大；v卡车可提前退出系统，等等。卡车可提前退出系统，等等。如理解为严格不等待，难以用数学规划模型来解如理解为严格不等待，难以用数学规划模型来解 个

26、别参数队找到了可行解个别参数队找到了可行解（略）（略）2023-5-2239符号符号vxij：从：从i铲位到铲位到j号卸点的石料运量号卸点的石料运量（车）（车）单位：单位：吨；吨；vcij：从：从i号铲位到号铲位到j号卸点的距离号卸点的距离 公里；公里；vTij:从从i号铲位到号号铲位到号j卸点路线上运行一个周期平均时间卸点路线上运行一个周期平均时间 分；分；vAij：从号铲位到号卸点最多能同时运行的卡车数：从号铲位到号卸点最多能同时运行的卡车数 辆；辆；vBij：从号铲位到号卸点路线上一辆车最多可运行的次数：从号铲位到号卸点路线上一辆车最多可运行的次数 次；次；vpi：i号铲位的矿石铁含量号

27、铲位的矿石铁含量 p=(30,28,29,32,31,33,32,31,33,31)%vqj:j号卸点任务需求，号卸点任务需求，q=(1.2,1.3,1.3,1.9,1.3)*10000 吨吨vcki：i号铲位的铁矿石储量号铲位的铁矿石储量 万吨万吨vcyi：i号铲位的岩石储量号铲位的岩石储量 万吨万吨vfi:描述第描述第i号铲位是否使用的号铲位是否使用的0-1变量，取变量，取1为使用；为使用；0为关闭。为关闭。532平均速度距离到jiTij5ijijTAijijijTAB5)1(608(近似近似)2023-5-2240优化模型优化模型cxijijij10151min5,1,10,1,jiBA

28、xijijij10,1,5/60851ifxijij5,1,208101jiijx10,1,154/10000154/1000043521icyxxckxxxiiiiiii（1）道路能力）道路能力(卡车数卡车数)约束约束（2）电铲能力约束）电铲能力约束（3）卸点能力约束）卸点能力约束（4）铲位储量约束）铲位储量约束（5）产量任务约束）产量任务约束（6）铁含量约束）铁含量约束（7）电铲数量约束）电铲数量约束（8）整数约束）整数约束 5,1,154/101jqxjiij5,2,1,0)5.28(0)5.30(101101jpxpxiiijiiij.7101iifxij为非负整数为非负整数fi 为为

29、0-1整数整数2023-5-2241计算结果（计算结果（LINGOLINGO软件）软件）铲位铲位1 1铲位铲位2 2铲位铲位3 3铲位铲位4 4铲位铲位5 5铲位铲位6 6铲位铲位7 7铲位铲位8 8铲位铲位9 9铲位铲位1010矿漏矿漏131354541111倒倒42424343岩场岩场70701515岩漏岩漏81814343倒倒13132 27070铲位铲位1 1铲位铲位2 2铲位铲位3 3铲位铲位4 4铲位铲位5 5铲位铲位6 6铲位铲位7 7铲位铲位8 8铲位铲位9 9铲位铲位1010矿石漏矿石漏0.8671.8620.314倒场倒场1.0771.162岩场岩场1.8920.326岩石

30、漏岩石漏1.8411.229倒场倒场0.6840.11.489cumcm2003b1.lg4注注:LINGO8.0本来是可以得到最优解的，但有些本来是可以得到最优解的，但有些 LINGO8.0可能出现系统错误可能出现系统错误,可能是系统可能是系统BUG2023-5-2242计算结果（派车）计算结果（派车）铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏1(29)倒场1(39)1(37)岩场1(37)岩石漏1(44)1(35)倒场1(47)结论：结论：铲位铲位1、2、3、4、8、9、10处各放置一台电铲。处各放置一台电铲。一共使用了一共使用了13辆卡车；总运量为辆卡车；总运量为85628.62吨公里；吨公里；岩石产量为岩石产量为32186吨；矿石产量为吨；矿石产量为38192吨。吨。此外：此外：6辆联合派车（方案略）辆联合派车（方案略）