数学建模讲义线性规划模型2运输问题等课件

,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,数学建模讲义,第4章 线性规划模型,-运输问题等,数学建模讲义第4章 线性规划模型-运输问题等,1,其他费用:,450,元,/,千吨,应如何分配水库供水量，公司才能获利最多？,若水库供水量都提高一倍，公司利润可增加到多少？,元/千吨,甲,乙,丙,丁,A,160,130,220,170,B,140,130,190,150,C,190,200,230,/,引水管理费,1 运输问题：自来水输送(,4.2,),收入：900,元,/,千吨,支出,A：50,B：60,C：50,甲：30；,50,乙：70；,70,丙：10；,20,丁：10；,40,水库供水量,(,千吨,),小区基本用水量,(,千吨,),小区额外用水量,(,千吨,),（以天计）,其他费用:450元/千吨 应如何分配水库供水量，公司才能获,2,总供水量：160,确定送水方案,使利润最大,问题分析,A：50,B：60,C：50,甲：30；,50,乙：70；,70,丙：10；,20,丁：10；,40,总需求量：120+,180,=300,总收入900,160,=144,000(元),收入：900,元,/,千吨,其他费用:,450,元,/,千吨,支出,引水管理费,其他,支出,450,160,=72,000(元),使引水管理费最小,总供水量：160确定送水方案使利润最大问题分析A：50B：6,3,供应限制,约束条件,需求限制,线性规划模型(LP),目标函数,水库,i,向,j,区的日供水量为,x,ij,（,x,34,=0）,决策变量,模型建立,确定3个水库向4个小区的供水量,供应限制约束条件需求限制 线性规划模型(LP)目标函数 水库,4,模型求解,OBJECTIVE FUNCTION VALUE,1)24400.00,VARIABLE VALUE REDUCED COST,X11 0.000000 30.000000,X12 50.000000 0.000000,X13 0.000000 50.000000,X14 0.000000 20.000000,X21 0.000000 10.000000,X22,50.000000,0.000000,X23 0.000000 20.000000,X24,10.000000,0.000000,X31,40.000000,0.000000,X32 0.000000 10.000000,X33,10.000000,0.000000,利润=总收入-其它费用-引水管理费,=144000-72000-24400=47600,（元）,A(50),B(,60,),C(,50,),甲(30;,50),乙(70;,70),丙(10;,20),丁(10;,40),50,50,40,10,10,引水管理费,24400(,元,),模型求解 OBJECTIVE FUNCTION VALUE利,5,设每月生产小、中、大型汽车的数量分别为,x,1,x,2,x,3,2 0-1规划：汽车厂生产计划,(,4.3,),模型建立,小型 中型 大型 现有量,钢材 1.5 3 5 600,时间 280 250 400 60000,利润 2 3 4,线性规划模型(LP),设每月生产小、中、大型汽车的数量分别为x1,x2,x32,6,模型求解,3）,模型中增加条件：,x,1,x,2,x,3,均为整数，重新求解。,OBJECTIVE FUNCTION VALUE,1)632.2581,VARIABLE VALUE REDUCED COST,X1 64.516129,0.000000,X2 167.741928,0.000000,X3 0.000000 0.946237,ROW SLACK OR SURPLUS DUAL PRICES,2)0.000000 0.731183,3)0.000000 0.003226,结果为小数，怎么办？,1）舍去小数：取,x,1,=64，,x,2,=167，算出目标函数值,z,=629，与LP最优值632.2581相差不大。,2）试探：如取,x,1,=65，,x,2,=167；,x,1,=64，,x,2,=168等，计算函数值,z,，通过比较可能得到更优的解。,但必须检验它们是否满足约束条件。为什么？,模型求解 3）模型中增加条件：x1,x2,x3 均为,7,IP,可用,LINGO,直接求解,整数规划(,Integer Programming,简记,IP,),IP,的最优解,x,1,=64,，,x,2,=168,，,x,3,=0,，最优值,z,=632,Max=2*x1+3*x2+4*x3;,1.5*x1+3*x2+5*x3600;,280*x1+250*x2+400*x360000;,gin(x1);,gin(x2);,gin(x3);,OBJECTIVE FUNCTION VALUE,1)632.0000,VARIABLE VALUE REDUCED COST,X1 64.000000 -2.000000,X2 168.000000 -3.000000,X3 0.000000 -4.000000,模型求解,IP,结果输出,IP可用LINGO直接求解整数规划(Integer Prog,8,其中,3,个,子模型应,去掉，然后逐一求解，比较目标函数值，再加上整数约束，得最优解：,方法1：分解为8个LP子模型,汽车厂生产计划,若生产某类汽车，则至少生产80辆，求生产计划。,x,1,x,2,x,3,=0 或,80,x,1,=80,，,x,2,=150,，,x,3,=0,，最优值,z,=610,其中3个子模型应去掉，然后逐一求解，比较目标函数值，再加上整,9,LINGO中对0-1变量的限定：,bin(y1);,bin(y2);,bin(y3);,方法2：,引入,0-1,变量，化为整数规划,M,为大的正数，可取,1000,OBJECTIVE FUNCTION VALUE,1)610.0000,VARIABLE VALUE REDUCED COST,X1 80.000000,-2.000000,X2 150.000000,-3.000000,X3 0.000000,-4.000000,Y1 1.000000 0.000000,Y2 1.000000 0.000000,Y3 0.000000 0.000000,若生产某类汽车，则至少生产80辆，求生产计划。,x,1,=0,或,80,x,2,=0,或,80,x,3,=0,或,80,最优解同前,LINGO中对0-1变量的限定：方法2：引入0-1变量，化为,10,NLP,虽然可用现成的数学软件求解(如,LINGO,MATLAB,)，但是其结果常依赖于初值的选择。,方法3：,化为非线性规划,非线性规划（,Non-Linear Programming,，简记,NLP,）,实践表明，本例仅当初值非常接近上面方法算出的最优解时，才能得到正确的结果。,若生产某类汽车，则至少生产80辆，求生产计划。,x,1,=0,或,80,x,2,=0,或,80,x,3,=0,或,80,NLP虽然可用现成的数学软件求解(如LINGO,MATLA,11,丁的蛙泳成绩退步到,115”2,；戊的自由泳成绩进步到,57”5,组成接力队的方案是否应该调整,？,如何选拔队员组成4,100米混合泳接力队?,3 分配问题：混合泳接力队的选拔,(,4.4,),甲,乙,丙,丁,戊,蝶泳,106”8,57”2,118”,110”,107”4,仰泳,115”6,106”,107”8,114”2,111”,蛙泳,127”,106”4,124”6,109”6,123”8,自由泳,58”6,53”,59”4,57”2,102”4,5名候选人的,百米成绩,穷举法,：,组成接力队的方案共有,5!=120,种,。,丁的蛙泳成绩退步到115”2；戊的自由泳成绩进步到57”5,12,目标函数,若选择队员,i,参加泳姿,j,的比赛，记,x,ij,=1,否则记,x,ij,=0,0-1,规划模型,c,ij,(秒),队员,i,第,j,种泳姿的百米成绩,约束条件,每人最多入选泳姿之一,c,ij,i,=1,i,=2,i,=3,i,=4,i,=5,j,=1,66.8,57.2,78,70,67.4,j,=2,75.6,66,67.8,74.2,71,j,=3,87,66.4,84.6,69.6,83.8,j,=4,58.6,53,59.4,57.2,62.4,每种泳姿有且只有1人,目标函数若选择队员i参加泳姿j 的比赛，记xij=1,否则,13,模型求解,最优解：,x,14,=,x,21,=,x,32,=,x,43,=1,其它变量为,0;,成绩为,253.2,(秒),=413”2,MIN=66.8*x11+75.6*x12+87*x13,+58.6*x14+62.4*x54;,x11+x12+x13+x14=1;,x41+x42+x43+x44=1;,x11+x21+x31+x41+x51=1;,x14+x24+x34+x44+x54=1;,bin(x11);.;bin(x54);,输入,LINGO,求解,甲,乙,丙,丁,戊,蝶泳,106”8,57”2,118”,110”,107”4,仰泳,115”6,106”,107”8,114”2,111”,蛙泳,127”,106”4,124”6,109”6,123”8,自由泳,58”6,53”,59”4,57”2,102”4,甲,自由泳、乙,蝶泳、丙,仰泳、丁,蛙泳.,模型求解 最优解：x14=x21=x32=x43,14,丁蛙泳,c,43,=,69.6,75.2,，戊自由泳,c,54,=,62.4,57.5,方案是否调整？,敏感性分析？,乙,蝶泳、丙,仰泳、丁,蛙泳、戊,自由泳,IP,规划一般没有与,LP,规划相类似的理论，,LINDO,输出的敏感性分析结果通常是没有意义的。,最优解：,x,21,=,x,32,=,x,43,=,x,51,=1,成绩为,417”7,c,43,c,54,的新数据重新输入模型，用,LINDO,求解,指派(,Assignment,)问题,：,每项任务有且只有一人承担，每人只能承担一项,，效益不同，怎样分派使总效益最大.,讨论,甲,自由泳、乙,蝶泳、丙,仰泳、丁,蛙泳.,原方案,丁蛙泳c43=69.675.2，戊自由泳c54=62.4,15,为了选修课程门数最少，应学习哪些课程？,4 多目标规划：选课策略,(,4.4,),要求至少选两门数学课、三门运筹学课和两门计算机课,课号,课名,学分,所属类别,先修课要求,1,微积分,5,数学,2,线性代数,4,数学,3,最优化方法,4,数学；运筹学,微积分；线性代数,4,数据结构,3,数学；计算机,计算机编程,5,应用统计,4,数学；运筹学,微积分；线性代数,6,计算机模拟,3,计算机；运筹学,计算机编程,7,计算机编程,2,计算机,8,预测理论,2,运筹学,应用统计,9,数学实验,3,运筹学；计算机,微积分；线性代数,选修课程最少，且学分尽量多，应学习哪些课程？,为了选修课程门数最少，应学习哪些课程？4 多目标规划：,16,0-1,规划模型,决策变量,目标函数,x,i,=1,选修课号,i,的课程（,x,i,=0,不选）,选修课程总数最少,约束条件,最少,2,门数学课，,3,门运筹学课，,2,门计算机课。,课号,课名,所属类别,1,微积分,数学,2,线性代数,数学,3,最优化方法,数学；运筹学,4,数据结构,数学；计算机,5,应用统计,数学；运筹学,6,计算机模拟,计算机；运筹学,7,计算机编程,计算机,8,预测理论,运筹学,9,数学实验,运筹学；计算机,0-1规划模型 决策变量 目标函数 xi=1 选修课号i,17,先修课程要求,最优解：,x,1,=,x,2,=,x,3,=,x,6,=,x,7,=,x,9,=1,其它为,0；6,门课程，总学分,21,0-1,规划模型,约束条件,x,3,=1必有,x,1,=,x,2,=1,模型求解（LINGO）,课号,课名,先修课要求,1,微积分,2,线性代数,3,最优化方法,微积分；线性代数,4,数据结构,计算机编程,5,应用统计,微积分；线性代数,6,计算机模拟,计算机编程,7,计算机编程,8,预测理论,应用统计,9,数学实验,微积分；线性代数,先修课程要求最优解：x1=x2=x3=x6=,18,学分最多,多目标优化的处理方法：化成单目标优化。,两目标(多目标)规划,讨论：选修课程最少，学分尽量多，应学习哪些课程？,课程最少,以,学分最多为目标，不管课程多少。,以课程最少,为目标，不管学分多少。,最优解如上，,6,门课程，总学分,21。,最优解显然是选修所有,9,门课程,。,学分最多多目标优化的处理方法：化成单目标优化。两目标(多目标,19,多目标规划,在,课程最少的前提下,以,学分最多为目标。,最优解：,x,1,=,x,2,=,x,3,=,x,5,=,x,7,=,x,9,=1,其它为,0；,总学分由,21增至22。,注意：最优解不唯一！,课号,课名,学分,1,微积分,5,2,线性代数,4,3,最优化方法,4,4,数据结构,3,5,应用统计,4,6,计算机模拟,3,7,计算机编程,2,8,预测理论,2,9,数学实验,3,LINGO无法告诉优化问题的解是否唯一。,可将,x,9,=1,易为,x,6,=1,增加约束 ，,以学分最多为目标求解。,多目标规划 在课程最少的前提下以学分最多为目标。最优解：,20,多目标规划,对学分数和课程数加权形成一个目标，如三七开。,最优解：,x,1,=,x,2,=,x,3,=,x,4,=,x,5,=,x,6,=,x,7,=,x,9,=1,，,其它为,0；,总学分,28。,课号,课名,学分,1,微积分,5,2,线性代数,4,3,最优化方法,4,4,数据结构,3,5,应用统计,4,6,计算机模拟,3,7,计算机编程,2,8,预测理论,2,9,数学实验,3,多目标规划 对学分数和课程数加权形成一个目标，如三七开。,21,讨论与思考,最优解,与,1,=0，,2,=1,的结果相同学分最多,多目标规划,最优解,与,1,=1，,2,=0,的结果相同课程最少,讨论与思考最优解与1=0，2=1的结果相同学分最多多,22,问题1.如何下料最节省?,5 下料问题：钢管下料(,4.6,),问题2.客户增加需求：,原料钢管:每根,19,米,4,米,50,根,6,米,20,根,8,米,15,根,客户需求,节省的标准是什么？,由于采用不同切割模式太多，会增加生产和管理成本，规定切割模式不能超过3种。如何下料最节省？,5,米,10,根,问题1.如何下料最节省?5 下料问题：钢管下料(4,23,按照客户需要在一根原料钢管上安排切割的一种组合。,切割模式,余料1米,4,米,1,根,6,米,1,根,8米1根,余料3米,4米1根,6米1根,6米1根,合理切割模式,的余料应小于客户需要钢管的最小尺寸,余料3米,8米1根,8米1根,钢管下料,按照客户需要在一根原料钢管上安排切割的一种组合。切割模式余,24,为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？,合理切割模式,2.所用原料钢管总根数最少,模式,4米钢管根数,6米钢管根数,8米钢管根数,余料(米),1,4,0,0,3,2,3,1,0,1,3,2,0,1,3,4,1,2,0,3,5,1,1,1,1,6,0,3,0,1,7,0,0,2,3,钢管下料问题1,两种标准,1.原料钢管剩余总余量最小,为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢,25,x,i,按第,i,种模式切割的原料钢管根数(,i,=,1,2,7,),约束,满足需求,决策变量,目标1（总余量）,按模式,2,切割,12,根,按模式,5,切割,15,根，余料,27,米,模,式,4米,根数,6米,根数,8米,根数,余,料,1,4,0,0,3,2,3,1,0,1,3,2,0,1,3,4,1,2,0,3,5,1,1,1,1,6,0,3,0,1,7,0,0,2,3,需,求,50,20,15,最优解：,x,2,=12,x,5,=15,其余为0；,最优值：,27。,整数约束：,x,i,为整数,xi 按第i 种模式切割的原料钢管根数(i=1,2,7),26,当余料没有用处时，,通常以总根数最少为目标,目标,2（总根数）,钢管下料问题1,约束条件不变,最优解：,x,2,=15,x,5,=5,x,7,=5,其余为0；,最优值：,25。,x,i,为整数,按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35米,虽余料增加8米，但减少了2根,与,目标,1的结果“共切割27根，余料27米”相比,当余料没有用处时，通常以总根数最少为目标 目标2（总根数）钢,27,钢管下料问题,2,对大规模问题，用模型的约束条件界定合理模式,增加一种需求：,5,米,10,根；切割,模式不超过3种。,现有4种,需求：,4,米,50,根，,5,米,10,根，,6,米,20,根，,8,米,15,根，用枚举法确定合理切割模式，过于复杂。,决策变量,x,i,按第,i,种模式切割的原料钢管根数(,i,=,1,2,3,),r,1,i,r,2,i,r,3,i,r,4,i,第,i,种切割模式下，每根原料钢管生产4米、5米、6米和8米长的钢管的数量,钢管下料问题2对大规模问题，用模型的约束条件界定合理模式增加,28,满足需求,模式合理：每根余料不超过3米,整数非线性规划模型,钢管下料问题,2,目标函数（,总根数）,约束条件,整数约束：,x,i,r,1,i,r,2,i,r,3,i,r,4,i,(,i,=,1,2,3,),为整数,满足需求模式合理：每根余料不超过3米整数非线性规划模型钢管下,29,增加约束，缩小可行域，便于求解,原料钢管总根数下界：,特殊生产计划：对每根原料钢管,模式1：切割成4根4米钢管，需13根；,模式2：切割成1根5米和2根6米钢管，需10根；,模式3：切割成2根8米钢管，需8根。,原料钢管总根数上界：13+10+8=31,模式排列顺序可任定,钢管下料问题,2,需求：,4,米,50,根，,5,米,10,根，,6,米,20,根，,8,米,15,根,每根原料钢管长19米,增加约束，缩小可行域，便于求解原料钢管总根数下界：特殊生产,30,LINGO,求解整数非线性规划模型（,代码见P125,）,Local optimal solution found at iteration:12211,Objective value:28.00000,Variable Value Reduced Cost,X1,10.00000,0.000000,X2,10.00000,2.000000,X3 8.000000 1.000000,R11,3.000000,0.000000,R12,2.000000,0.000000,R13 0.000000 0.000000,R21,0.000000,0.000000,R22,1.000000,0.000000 R23 0.000000 0.000000 R31,1.000000,0.000000 R32,1.000000,0.000000 R33 0.000000 0.000000 R41,0.000000,0.000000 R42,0.000000,0.000000 R43 2.000000 0.000000,模式1：每根原料钢管切割成3根4米和1根6米钢管，共10根；,模式2：每根原料钢管切割成2根4米、1根5米和1根6米钢管，共10根；,模式3：每根原料钢管切割成2根8米钢管，共8根。,原料钢管总根数为28根。,LINGO求解整数非线性规划模型（代码见P125）Loca,31,板材,规格2：,长方形，,32,28cm，,2万张。,例,易拉罐下料,每周工作40小时，每只易拉罐利润0.10元，原料余料损失0.001元/cm,2,（不能装配的罐身、,盖、,底也是余料）,模式1：1.5秒,模式2：2秒,模式3：1秒,模式4：3秒,上盖,下底,罐,身,罐身高,10cm,，上,盖,、下底直径均,5cm,。,板材规格,1：,正方形，边长,24cm，5,万张。,如何安排每周生产？,板材规格2：例 易拉罐下料每周工作40小时，每只易拉罐利润0,32,罐身个数,底、盖,个数,余料损失,（,cm,2,）,冲压时间（秒）,模式1,1,10,222.6,1.5,模式2,2,4,183.3,2,模式3,0,16,261.8,1,模式4,4,5,169.5,3,模式1:,正方形,边长,24cm,问题分析,计算各种模式下的余料损失,上、下底直径,d,=5cm，罐身高,h,=10cm。,模式1,余料损失 24,2,-10,d,2,/4,-dh,=222.6,cm,2,罐身个数底、盖余料损失冲压时间（秒）模式1110222.6,33,问题分析,目标:,易拉罐利润扣除原料余料损失后的净利润最大,约束：,每周工作时间不超过40小时；,原料数量：,规格,1（模式1 3）5,万张，,规格,2（模式4）2,万张；,罐身和底、盖的配套组装。,注意：不能装配的罐身、上下底也是余料,决策变量,x,i,按照第,i,种模式的生产张数(,i,=,1,2,3,4,)；,y,1,一周生产的易拉罐个数；,y,2,不配套的罐身个数；,y,3,不配套的底、盖个数。,模型建立,问题分析目标:易拉罐利润扣除原料余料损失后的净利润最大 约,34,目标,约束条件,时间约束,原料约束,产量,余料,时间,x,1,222.6,1.5,x,2,183.3,2,x,3,261.8,1,x,4,169.5,3,模型建立,y,1,易拉罐个数；,y,2,不配套的罐身；,y,3,不配套的底、盖。,每只易拉罐利润0.10元，余料损失0.001元/cm,2,罐身,面积,dh=,157.1,cm,2,底盖,面积,d,2,/4=19.6,cm,2,(40小时),目标 约束条件 时间约束 原料约束 产量余料时间x1222.,35,约束条件,配套约束,y,1,易拉罐个数；,y,2,不配套的罐身；,y,3,不配套的底、盖。,罐身,底、盖,1,10,2,4,0,16,4,5,产量,x,1,x,2,x,3,x,4,虽然,x,i,和,y,1,，,y,2,，,y,3,应是整数，但是因生产量很大，可以把它们看成实数，从而用线性规划模型处理。,约束条件 配套约束 y1 易拉罐个数；y2 不配套的,36,将所有决策变量扩大,10000,倍（,x,i,万张，,y,i,万件）,LINDO,发出警告信息：“数据之间的数量级差别太大，建议进行预处理，缩小数据之间的差别”,模式,2,生产,40125,张，,模式,3,生产,3750,张，,模式,4,生产,20000,张，,共产易拉罐,160250,个,(罐身和底、盖无剩余)，,净利润为,4298,元,模型求解,OBJECTIVE FUNCTION VALUE,1)0.4298337,VARIABLE VALUE REDUCED COST,Y1 16.025000 0.000000,X1 0.000000 0.000050,X2 4.012500 0.000000,X3 0.375000 0.000000,X4 2.000000 0.000000,Y2 0.000000 0.223331,Y3 0.000000 0.036484,将所有决策变量扩大10000倍（xi 万张，yi 万件）,37,下料问题的建模,确定下料模式,构造优化模型,规格不太多，可枚举下料模式，建立整数线性规划模型，否则要构造整数非线性规划模型，求解困难，可用,缩小可行域,的方法进行化简，但要保证最优解的存在。,一维问题（如钢管下料）,二维问题（如易拉罐下料）,具体问题具体分析（比较复杂）,下料问题的建模 确定下料模式 构造优化模型 规格不太多，,38,