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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第二讲 线性规划模型,统计与应用数学系,张耀峰,The model of linear programming,9/3/2024,1,第二讲 线性规划模型统计与应用数学系The model o,第,二,讲 线性规划模型,1.1 优化的思想,1.2 什么是线性规划模型,1.3 如何使用Lingo软件求解,线性规划问题,1.4 案例解析,9/3/2024,2,第二讲 线性规划模型1.1 优化的思想9/8/2023,1.1,优化的思想,9/3/2024,3,1.1 优化的思想9/8/20233,烧水,小明同学，烧一壶水要8分钟，灌开水要1分钟，取牛奶和报纸要5分钟（不能间断），整理书包要6分钟（可间断），为了尽快做完这些事，怎样安排才能使时间最少？最少需要几分钟？,例1、如何安排早上的时间？,取牛奶和报纸,收拾书包,灌水,收拾书包,5,8,9,12,0,9/3/2024,4,烧水 小明同学，烧一壶水要8分钟，灌开水要1分,例2、怎么排队才合理呢？,码头上现在同时有3艘货船需要卸货，但是只能一条一条地卸货，并且每艘船卸货所需的时间各不相同，分别为4小时、8小时和1小时。按照怎样的顺序卸货能使3艘货船等候的总时间最少呢？,9/3/2024,5,例2、怎么排队才合理呢？ 码头上现在同时有3艘,方案,卸货顺序,船1的等候时间,船2的等候时间,船3的等候时间,总的等候时间,1,船1船2船3,8,8+4,8+4+1,33,2,船1船3船2,8,8+1+4,8+1,30,3,船2船1船3,4+8,4,4+8+1,29,4,船2船3船1,4+1+8,4,4+1,22,5,船3船1船2,1+8,1+8+4,1,23,6,船3船2船1,1+4+8,1+4,1,19,9/3/2024,6,方案卸货顺序船1的等候时间船2的等候时间船3的等候时间总的等,1.2 什么是线性规划模型,9/3/2024,7,1.2 什么是线性规划模型9/8/20237,例3 运输问题,9/3/2024,8,例3 运输问题9/8/20238,解：设A,1,A,2,调运到三个粮站的大米分别为,x,11,，,x,12,，,x,13,，,x,21,，,x,22,，,x,23,吨。,题设量可总到下表：,8,4,库,存,量,x,23,x,22,x,21,A,2,5,4,2,需要量,x,13,x,12,x,11,A,1,B,3,B,2,B,1,粮库,粮站,距离及运量,12,12,24,30,8,24,9/3/2024,9,解：设A1,A2调运到三个粮站的大米分别为x11，题设量可总,结合存量限制和需量限制得数学模型,：,目标函数,约束条件,决策变量,9/3/2024,10,结合存量限制和需量限制得数学模型：目标函数约束条件决策变量9,1.3如何使用Lingo软件求解线性规划问题,9/3/2024,11,1.3如何使用Lingo软件求解线性规划问题9/8/2023,程序编写,model:,min,=12*x11+24*x12+8*x13+30*x21+12*x22+24*x23 ;,x11+x12+x134 ;,x21+x22+x232 ;,x12+x224 ;,x13+x235 ;,end,9/3/2024,12,程序编写9/8/202312,运行结果,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,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,9/3/2024,13,运行结果9/8/202313,例4,生产计划问题,某工厂计划安排生产，两种产品，已知每种单位产品的利润，生产单位产品所需设备台时及A,B两种原材料的消耗，现有原材料和设备台时的定额如表所示，问：,）怎么安排生产使得工厂获利最大？,）产品的单位利润降低到1.8万元，要不要改变生产计划，如果降低到1万元呢？,）产品的单位利润增大到5万，要不要改变生产计划,）如果产品，的单位利润同时降低了1万元，要不要改变生产计划？,产品,产品,最大资源量,设备,1,2,8台时,原材料A,4,0,16kg,原材料B,0,4,12kg,单位产品利润,2,3,9/3/2024,14,例4 生产计划问题某工厂计划安排生产，两种产品，已,9/3/2024,15,9/8/202315,程序编写,model:,title 生产计划问题;,maxfmax=2*x1+3*x2;,Ax1+2*x28;,B4*x116;,TIME4*x212;,END,9/3/2024,16,程序编写9/8/202316,运行结果,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.1250000,TIME 4.000000 0.000000,对问题,1,，安排是生产产品4单位，产品2单位，最大盈利为14万元,。,9/3/2024,17,运行结果对问题1，安排是生产产品4单位，产品2单位，最大,线性模型,敏感性分析,要使用敏感性分析,必须要在这里选择,Prices & Ranges,然后,保存,退出,路径：,LINGOOptionsGeneral Solver,(通用求解程序)选项卡,9/3/2024,18,线性模型敏感性分析要使用敏感性分析路径：9/8/202,要调出敏感性分析的结果，必须,先求解,后再,在程序窗口下,点击,LINGO,Range,，,9/3/2024,19,要调出敏感性分析的结果，必须先求解后再在程序窗口下点击9/8,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 4.000000,B 16.00000 16.00000 8.000000,TIME 12.00000 INFINITY 4.000000,当前变量系数,允许增加量,允许减少量,9/3/2024,20,对问题4，因为两个系数同时改变了，所以只有更 改程序的数据，重新运行得：不改变生产计划，但是最大利润降低到6万元.,对问题2，产品的单位利润降低到1.8万元，在（1.5，）之间，所以不改变生产计划。如果降低到1万元，不在（1.5，）内，要改变生产计划。在程序中将目标函数的系数“2”改为“1”，可得新的计划为安排是生产产品2单位，产品3单位，最大盈利为11万元.,对问题3，要改变生产计划，更改程序得新计划为生产产品2单位，产品3单位，最大盈利为19万元.,9/3/2024,21,对问题4，因为两个系数同时改变了，所以只有更 改程序的数,例5 加工奶制品的生产计划,1桶牛奶,3公斤A,1,12小时,8小时,4公斤A,2,或,获利24元/公斤,获利16元/公斤,50桶牛奶,时间480小时,至多加工100公斤A,1,制订生产计划，使每天获利最大,35元可买到1桶牛奶，买吗？若买，每天最多买多少?,可聘用临时工人，付出的工资最多是每小时几元?,A,1,的获利增加到 30元/公斤，应否改变生产计划？,每天：,9/3/2024,22,例5 加工奶制品的生产计划1桶牛奶 3公斤A1 12小,1桶牛奶,3公斤A,1,12小时,8小时,4公斤A,2,或,获利24元/公斤,获利16元/公斤,x,1,桶牛奶生产A,1,x,2,桶牛奶生产A,2,获利 243,x,1,获利 164,x,2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型(LP),时间480小时,至多加工100公斤A,1,50桶牛奶,每天,9/3/2024,23,1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利2,模型求解,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= 2,20桶牛奶生产A,1, 30桶生产A,2,，利润3360元。,max=72*x1+64*x2;,x1+x250;,12*x1+8*x2480;,3*x1100;,9/3/2024,24,模型求解 OBJECTIVE FUNCTION,模型求解,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 SURPLUS DUAL PRICES,2) 0.000000 48.000000,3) 0.000000 2.000000,4) 40.000000 0.000000,NO. ITERATIONS= 2,9/3/2024,25,模型求解 reduced cost值表示当该非基变量增加一个,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,原料无剩余,时间无剩余,加工能力剩余40,max 72x1+64x2,st,2）x1+x250,3）12x1+8x2480,4）3x1100,end,三种资源,结果解释,9/3/2024,26,OBJECTIVE FUNCTION VALUE原料,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,结果解释,最优解下“资源”增加1单位时“效益”的增量,原料增1单位, 利润增48,时间加1单位, 利润增2,能力增减不影响利润,影子价格,35元可买到1桶牛奶，要买吗？,35 ,sum,(yuefen(i)|i#le#j:d);,sum,(yuefen:x)=,sum,(yuefen:d);,for,(yuefen:xa);,end,9/3/2024,33,9/8/202333,露天矿里铲位已分成矿石和岩石: 平均铁含量不低于25%的为矿石，否则为岩石。每个铲位的矿石、岩石数量，以及矿石的平均铁含量（称为品位）都是已知的。每个铲位至多安置一台电铲，电铲平均装车时间5分钟,卡车在等待时所耗费的能量也是相当可观的，原则上在安排时不应发生卡车等待的情况。,例7、 露天矿生产的车辆安排,(CUMCM-2003B),矿石卸点需要的铁含量要求都为29.5%,1%(品位限制），搭配量在一个班次（8小时）内满足品位限制即可。卸点在一个班次内不变。卡车载重量为154吨，平均时速28km,平均卸车时间为3分钟。,问题：出动几台电铲，分别在哪些铲位上；出动几辆卡车，分别在哪些路线上各运输多少次 ?,9/3/2024,34,露天矿里铲位已分成矿石和岩石: 平均铁含量不低于25%的为矿,平面示意图,9/3/2024,35,平面示意图9/8/202335,问题数据,距离,铲位1,铲位,2,铲位3,铲位4,铲位5,铲位6,铲位7,铲位,8,铲位9,铲位10,矿石漏,5.26,5.19,4.21,4.00,2.95,2.74,2.46,1.90,0.64,1.27,倒装,1.90,0.99,1.90,1.13,1.27,2.25,1.48,2.04,3.09,3.51,岩场,5.89,5.61,5.61,4.56,3.51,3.65,2.46,2.46,1.06,0.57,岩石漏,0.64,1.76,1.27,1.83,2.74,2.60,4.21,3.72,5.05,6.10,倒装,4.42,3.86,3.72,3.16,2.25,2.81,0.78,1.62,1.27,0.50,铲位1,铲位2,铲位3,铲位4,铲位5,铲位6,铲位7,铲位,8,铲位9,铲位10,矿石量,095,105,100,105,110,125,105,130,135,125,岩石量,125,110,135,105,115,135,105,115,135,125,铁含量,30%,28%,29%,32%,31%,33%,32%,31%,33%,31%,9/3/2024,36,问题数据 距离铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位,问题分析,与典型的运输问题明显有以下不同：,这是运输矿石与岩石两种物资的问题；,属于产量大于销量的不平衡运输问题；,为了完成品位约束，矿石要搭配运输；,产地、销地均有单位时间的流量限制；,运输车辆只有一种，每次满载运输，154吨/车次；,铲位数多于铲车数意味着要最优的选择不多于7个产地作为最后结果中的产地；,最后求出各条路线上的派出车辆数及安排。,近似处理：,先求出产位、卸点每条线路上的运输量(MIP模型),然后求出各条路线上的派出车辆数及安排,9/3/2024,37,问题分析 与典型的运输问题明显有以下不同：近似处理：9/8/,模型假设,卡车在一个班次中不应发生等待或熄火后再启动的情况；,在铲位或卸点处由两条路线以上造成的冲突问题面前，我们认为只要平均时间能完成任务，就认为不冲突。我们不排时地进行讨论；,空载与重载的速度都是28km/h，耗油相差很大；,卡车可提前退出系统，等等。,如理解为严格不等待，难以用数学规划模型来解,个别参数队找到了可行解 （略）,9/3/2024,38,模型假设卡车在一个班次中不应发生等待或熄火后再启动的情况；如,符号,x,ij,：从i铲位到j号卸点的石料运量 （车） 单位： 吨；,c,ij,：从i号铲位到j号卸点的距离 公里；,T,ij,:从i号铲位到号j卸点路线上运行一个周期平均时间 分；,A,ij,：从号铲位到号卸点最多能同时运行的卡车数 辆；,B,ij,：从号铲位到号卸点路线上一辆车最多可运行的次数 次；,p,i,：i号铲位的矿石铁含量 p=(30,28,29,32,31,33,32,31,33,31) %,q,j,: j号卸点任务需求，q=(1.2,1.3,1.3,1.9,1.3)*10000 吨,ck,i,：i号铲位的铁矿石储量 万吨,cy,i,：i号铲位的岩石储量 万吨,f,i,:描述第i号铲位是否使用的0-1变量，取1为使用；0为关闭。,(近似),9/3/2024,39,符号xij ：从i铲位到j号卸点的石料运量 （车）,优化模型,（1）道路能力(卡车数)约束,（2）电铲能力约束,（3）卸点能力约束,（4）铲位储量约束,（5）产量任务约束,（6）铁含量约束,（7）电铲数量约束,（8）整数约束,.,x,ij,为非负整数,f,i,为0-1整数,9/3/2024,40,优化模型（1）道路能力(卡车数)约束.xij为非负整数9/8,计算结果（LINGO软件）,铲位1,铲位2,铲位3,铲位4,铲位5,铲位6,铲位7,铲位8,铲位9,铲位10,矿漏,13,54,11,倒,42,43,岩场,70,15,岩漏,81,43,倒,13,2,70,铲位1,铲位2,铲位3,铲位4,铲位5,铲位6,铲位7,铲位8,铲位9,铲位,10,矿石漏,0.867,1.862,0.314,倒场,1.077,1.162,岩场,1.892,0.326,岩石漏,1.841,1.229,倒场,0.684,0.1,1.489,cumcm2003b1.lg4,注: LINGO8.0本来是可以得到最优解的，但有些,LINGO8.0可能出现系统错误, 可能是系统BUG,9/3/2024,41,计算结果（LINGO软件）铲位1铲位2铲位3铲位4铲位5铲位,计算结果（派车）,铲位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辆联合派车（方案略）,9/3/2024,42,计算结果（派车）铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲,