《第二讲线性规划模型教材课件.ppt》由会员分享，可在线阅读，更多相关《第二讲线性规划模型教材课件.ppt（42页珍藏版）》请在三一办公上搜索。
1、2022/12/3,1,第二讲 线性规划模型,统计与应用数学系张耀峰,The model of linear programming,2022/12/3,2,第二讲 线性规划模型,1.1 优化的思想1.2 什么是线性规划模型1.3 如何使用Lingo软件求解 线性规划问题1.4 案例解析,2022/12/3,3,1.1 优化的思想,2022/12/3,4,烧水,小明同学，烧一壶水要8分钟，灌开水要1分钟，取牛奶和报纸要5分钟（不能间断），整理书包要6分钟（可间断），为了尽快做完这些事，怎样安排才能使时间最少？最少需要几分钟？,例1、如何安排早上的时间？,取牛奶和报纸,收拾书包,灌水,收拾书包,
2、5,8,9,12,0,2022/12/3,5,例2、怎么排队才合理呢？,码头上现在同时有3艘货船需要卸货，但是只能一条一条地卸货，并且每艘船卸货所需的时间各不相同，分别为4小时、8小时和1小时。按照怎样的顺序卸货能使3艘货船等候的总时间最少呢？,2022/12/3,6,2022/12/3,7,1.2 什么是线性规划模型,2022/12/3,8,例3 运输问题,2022/12/3,9,解：设A1,A2调运到三个粮站的大米分别为x11，x12， x13， x21， x22， x23吨。,题设量可总到下表：,2022/12/3,10,结合存量限制和需量限制得数学模型：,目标函数,约束条件,决策变量,
3、2022/12/3,11,1.3如何使用Lingo软件求解线性规划问题,2022/12/3,12,程序编写model:min=12*x11+24*x12+8*x13+30*x21+12*x22+24*x23 ;x11+x12+x132 ;x12+x224 ;x13+x235 ;end,2022/12/3,13,运行结果 Global optimal solution found. Objective value: 160.0000 Total solver iterations: 5 Variable Value Reduced Cost X11 2.000000 0.000000 X12 0
4、.000000 28.00000 X13 2.000000 0.000000 X21 0.000000 2.000000 X22 4.000000 0.000000 X23 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.00000,2022/12/3,14,例4 生产计划问题某工厂计划安排生产，两种产品，已知
5、每种单位产品的利润，生产单位产品所需设备台时及A,B两种原材料的消耗，现有原材料和设备台时的定额如表所示，问：）怎么安排生产使得工厂获利最大？）产品的单位利润降低到1.8万元，要不要改变生产计划，如果降低到1万元呢？）产品的单位利润增大到5万，要不要改变生产计划）如果产品，的单位利润同时降低了1万元，要不要改变生产计划？,2022/12/3,15,2022/12/3,16,程序编写model:title 生产计划问题;maxfmax=2*x1+3*x2;Ax1+2*x28;B4*x116;TIME4*x212;END,2022/12/3,17,运行结果 Model Title: 生产计划问题
6、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.1250000 TIME 4.000000 0.000000,对问题1，安排是生产产品4单位，产品2单位，最大盈利为14万元 。,2022/12/3,18,线性模型敏感性分析,要使用敏感性分析必须要在这里选择Prices & Ranges然后保存退出,路径：LINGOOptionsG
7、eneral Solver(通用求解程序)选项卡,2022/12/3,19,要调出敏感性分析的结果，必须先求解后再在程序窗口下点击LINGORange，,2022/12/3,20,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 Sid
8、e Ranges Row Current Allowable Allowable RHS Increase Decrease A 8.000000 2.000000 4.000000 B 16.00000 16.00000 8.000000 TIME 12.00000 INFINITY 4.000000,当前变量系数,允许增加量,允许减少量,2022/12/3,21,对问题4，因为两个系数同时改变了，所以只有更 改程序的数据，重新运行得：不改变生产计划，但是最大利润降低到6万元.,对问题2，产品的单位利润降低到1.8万元，在（1.5，）之间，所以不改变生产计划。如果降低到1万元，不在（1.5，
9、）内，要改变生产计划。在程序中将目标函数的系数“2”改为“1”，可得新的计划为安排是生产产品2单位，产品3单位，最大盈利为11万元.,对问题3，要改变生产计划，更改程序得新计划为生产产品2单位，产品3单位，最大盈利为19万元.,2022/12/3,22,例5 加工奶制品的生产计划,50桶牛奶,时间480小时,至多加工100公斤A1,制订生产计划，使每天获利最大,35元可买到1桶牛奶，买吗？若买，每天最多买多少?,可聘用临时工人，付出的工资最多是每小时几元?,A1的获利增加到 30元/公斤，应否改变生产计划？,每天：,2022/12/3,23,x1桶牛奶生产A1,x2桶牛奶生产A2,获利 243
10、x1,获利 164 x2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型(LP),时间480小时,至多加工100公斤A1,2022/12/3,24,模型求解,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
11、0.000000 NO. ITERATIONS= 2,20桶牛奶生产A1, 30桶生产A2，利润3360元。,max=72*x1+64*x2;x1+x250;12*x1+8*x2480;3*x1100;,2022/12/3,25,模型求解,reduced cost值表示当该非基变量增加一个单位时（其他非基变量保持不变）目标函数减少的量(对max型问题),OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR
12、SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2,2022/12/3,26,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
13、 4) 40.000000 0.000000,原料无剩余,时间无剩余,加工能力剩余40,max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end,三种资源,结果解释,2022/12/3,27,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
14、 4) 40.000000 0.000000,结果解释,最优解下“资源”增加1单位时“效益”的增量,原料增1单位, 利润增48,时间加1单位, 利润增2,能力增减不影响利润,影子价格,35元可买到1桶牛奶，要买吗？,35 48, 应该买！,聘用临时工人付出的工资最多每小时几元？,2元！,2022/12/3,28,RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.0000
15、00 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000,最优解不变时目标系数允许变化范围,DO RANGE(SENSITIVITY) ANALYSIS?,Yes,x1系数范围(64,96),x2系数范围(48,72),A1获
16、利增加到 30元/千克，应否改变生产计划,x1系数由243= 72 增加为303= 90，在允许范围内,不变！,(约束条件不变),结果解释,2022/12/3,29,结果解释,RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW
17、 CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000,影子价格有意义时约束右端的允许变化范围,原料最多增加10,时间最多增加53,35元可买到1桶牛奶，每天最多买多少？,最多买10桶？,(目标函数不变),2022/12/3,30,1.4 案例分析,2022/12/3,31,例6 阶段生产问题,某公司生产某产品,最大生产能力为10000单位,每单位存储费2元,
18、预定的销售量与单位成本如下:,求一生产计划,使 1)满足需求; 2)不超过生产能力;3)成本(生产成本与存储费之和)最低.,2022/12/3,32,解:假定1月初无库存,4月底卖完,当月生产的不库存,库存量无限制.,第j+1个月的库存量,第j+1个月的库存费,共3个月的库存费,到本月总生产量大于等于销售量,4个月总生产量等于总销售量,4个月总生产成本,2022/12/3,33,model:title 生产计划程序1;Sets:yuefen/1.4/:c,x,e,d;endsetsdata:c=70 71 80 76;d=6000 7000 12000 6000;e=2 2 2 2 ;a=10
19、000;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:xa);end,2022/12/3,34,露天矿里铲位已分成矿石和岩石: 平均铁含量不低于25%的为矿石，否则为岩石。每个铲位的矿石、岩石数量，以及矿石的平均铁含量（称为品位）都是已知的。每个铲位至多安置一
20、台电铲，电铲平均装车时间5分钟,卡车在等待时所耗费的能量也是相当可观的，原则上在安排时不应发生卡车等待的情况。,例7、 露天矿生产的车辆安排(CUMCM-2003B),矿石卸点需要的铁含量要求都为29.5%1%(品位限制），搭配量在一个班次（8小时）内满足品位限制即可。卸点在一个班次内不变。卡车载重量为154吨，平均时速28km,平均卸车时间为3分钟。,问题：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次 ?,2022/12/3,35,平面示意图,2022/12/3,36,问题数据,2022/12/3,37,问题分析,与典型的运输问题明显有以下不同：这是运输矿石与岩
21、石两种物资的问题；属于产量大于销量的不平衡运输问题；为了完成品位约束，矿石要搭配运输；产地、销地均有单位时间的流量限制；运输车辆只有一种，每次满载运输，154吨/车次；铲位数多于铲车数意味着要最优的选择不多于7个产地作为最后结果中的产地；最后求出各条路线上的派出车辆数及安排。,近似处理：先求出产位、卸点每条线路上的运输量(MIP模型)然后求出各条路线上的派出车辆数及安排,2022/12/3,38,模型假设,卡车在一个班次中不应发生等待或熄火后再启动的情况；在铲位或卸点处由两条路线以上造成的冲突问题面前，我们认为只要平均时间能完成任务，就认为不冲突。我们不排时地进行讨论；空载与重载的速度都是28
22、km/h，耗油相差很大；卡车可提前退出系统，等等。,如理解为严格不等待，难以用数学规划模型来解 个别参数队找到了可行解 （略）,2022/12/3,39,符号,xij ：从i铲位到j号卸点的石料运量 （车） 单位： 吨；cij ：从i号铲位到j号卸点的距离 公里；Tij :从i号铲位到号j卸点路线上运行一个周期平均时间 分；Aij ：从号铲位到号卸点最多能同时运行的卡车数 辆；Bij ：从号铲位到号卸点路线上一辆车最多可运行的次数 次；pi：i号铲位的矿石铁含量 p=(30,28,29,32,31,33,32,31,33,31) %qj : j号卸点任务需求，q=(1.2,1.3,1.3,1.
23、9,1.3)*10000 吨cki ：i号铲位的铁矿石储量 万吨cyi ：i号铲位的岩石储量 万吨fi :描述第i号铲位是否使用的0-1变量，取1为使用；0为关闭。,(近似),2022/12/3,40,优化模型,（1）道路能力(卡车数)约束（2）电铲能力约束（3）卸点能力约束（4）铲位储量约束（5）产量任务约束（6）铁含量约束（7）电铲数量约束（8）整数约束,.,xij为非负整数fi 为0-1整数,2022/12/3,41,计算结果（LINGO软件）,注: LINGO8.0本来是可以得到最优解的，但有些 LINGO8.0可能出现系统错误, 可能是系统BUG,2022/12/3,42,计算结果（派车）,结论：铲位1、2、3、4、8、9、10处各放置一台电铲。一共使用了13辆卡车；总运量为85628.62吨公里；岩石产量为32186吨；矿石产量为38192吨。,此外：6辆联合派车（方案略）,
