数学规划模型讲义省公共课一等奖全国赛课获奖课件.pptx

第四章第四章 数学规划模型数学规划模型 y4.2自来水输送与货机装运自来水输送与货机装运（运输问题）（运输问题）4.3汽车生产与原油采购汽车生产与原油采购(整数规划整数规划)第1页4.2 自来水输送与货机装运自来水输送与货机装运生产、生活物资从若干供给点运输到一些需求点，生产、生活物资从若干供给点运输到一些需求点，怎样安排输送方案使运费最小，或利润最大；怎样安排输送方案使运费最小，或利润最大；运输问题运输问题各种类型货物装箱，因为受体积、重量等限制，怎各种类型货物装箱，因为受体积、重量等限制，怎样搭配装载，使赢利最高，或装箱数量最少。样搭配装载，使赢利最高，或装箱数量最少。第2页其它费用其它费用:450元元/千吨千吨 应怎样分配水库供水量，企业才能赢利最多？应怎样分配水库供水量，企业才能赢利最多？若水库供水量都提升一倍，企业利润可增加到多少？若水库供水量都提升一倍，企业利润可增加到多少？元元/千吨千吨甲甲乙乙丙丙丁丁A160130220170B140130190150C190200230/引水管理费引水管理费例例1 自来水输送自来水输送收入：收入：900元元/千吨千吨支出支出A：50B：60C：50甲：甲：30；+50乙：乙：70；+70丙：丙：10；+20丁：丁：10；+40水库供水量水库供水量(千吨千吨)小小区区基基本本用用水水量量(千千吨吨)小区额外用水量小区额外用水量(千吨千吨)（以天计）（以天计）第3页总供水量：总供水量：160确定送水方案确定送水方案使利润最大使利润最大问题问题分析分析A：50B：60C：50甲：甲：30；+50乙：乙：70；+70丙：丙：10；+20丁：丁：10；+40总需求量总需求量(300)每个水库最大供水量都提升一倍每个水库最大供水量都提升一倍利润利润=收入收入(900)其它费用其它费用(450)引水管引水管理费理费利润利润(元元/千吨千吨)甲甲乙乙丙丙丁丁A290320230280B310320260300C260250220/供给供给限制限制B,C类似处理类似处理问题讨论问题讨论 确定送水方案确定送水方案使利润最大使利润最大需求约束能够不变需求约束能够不变第7页求解求解这类问题普通称为这类问题普通称为“运输问题运输问题”(TransportationProblem)总利润总利润 88700（元）（元）A(100)B(120)C(100)甲甲(30;50)乙乙(70;70)丙丙(10;20)丁丁(10;40)4010050305030 Globaloptimalsolutionfound.Objectivevalue:88700.00Totalsolveriterations:7VariableValueReducedCostX110.00000020.00000X12100.00000.000000X130.00000040.00000X140.00000020.00000X2130.000000.000000X2240.000000.000000X230.00000010.00000X2450.000000.000000X3150.000000.000000X320.00000020.00000X3330.000000.000000第8页怎样怎样装运，装运，使此次飞行使此次飞行赢利最大？赢利最大？三个货舱三个货舱最大最大载载重重(吨吨),),最大容积最大容积(米米3 3)例例2货机装运货机装运重量（吨）重量（吨）空间空间(米米3/吨）吨）利润（元利润（元/吨）吨）货物货物1184803100货物货物2156503800货物货物3235803500货物货物4123902850三个货舱中实际载重必须与其最大三个货舱中实际载重必须与其最大载载重成百分重成百分比比前仓：前仓：10；6800中仓：中仓：16；8700后仓：后仓：8；5300飞机平衡飞机平衡第9页决议决议变量变量 xij-第第i 种货物装入第种货物装入第j 个货舱重量个货舱重量(吨）吨）i=1,2,3,4,j=1,2,3(分别代表前、中、后仓分别代表前、中、后仓)模型假设模型假设 每种货物能够分割到任意小；每种货物能够分割到任意小；货机装运货机装运每种货物能够在一个或多个货舱中任意分布；每种货物能够在一个或多个货舱中任意分布；各种货物能够混装，并确保不留空隙；各种货物能够混装，并确保不留空隙；模型建立模型建立 第10页货舱货舱容积容积 目标目标函数函数(利润利润)约束约束条件条件货机装运货机装运模型建立模型建立 货舱货舱重量重量 10；680016；87008；5300 xij-第第i 种货物装入第种货物装入第j 个货舱重量个货舱重量第11页约束约束条件条件平衡平衡要求要求 货物货物供给供给 货机装运货机装运模型建立模型建立 10；680016；87008；5300 xij-第第i 种货物装入第种货物装入第j 个货舱重量个货舱重量第12页 Globaloptimalsolutionfound.Objectivevalue:121515.8VariableValueReducedCostX110.000000400.000000X120.00000057.894737X130.000000400.000000X2110.0000000.000000X220.000000239.473679X235.0000000.000000X310.0000000.000000X3212.9473690.000000X333.0000000.000000X410.000000650.000000X423.0526320.000000X430.000000650.000000货物货物2：前仓：前仓10,后仓后仓5；货物货物3:中仓中仓13,后仓后仓3；货物货物4:中仓中仓3。货机装运货机装运模型求解模型求解 最大利润约最大利润约121516元元货物货物供给点供给点货舱货舱需求点需求点平衡要求平衡要求运输运输问题问题运输问题扩展运输问题扩展第13页第14页其它费用其它费用:450元元/千吨千吨 应怎样分配水库供水量，企业才能赢利最多？应怎样分配水库供水量，企业才能赢利最多？若水库供水量都提升一倍，企业利润可增加到多少？若水库供水量都提升一倍，企业利润可增加到多少？元元/千吨千吨甲甲乙乙丙丙丁丁A160130220170B140130190150C190200230/引水管理费引水管理费例例1 自来水输送自来水输送收入：收入：900元元/千吨千吨支出支出A：50B：60C：50甲：甲：30；+50乙：乙：70；+70丙：丙：10；+20丁：丁：10；+40水库供水量水库供水量(千吨千吨)小小区区基基本本用用水水量量(千千吨吨)小区额外用水量小区额外用水量(千吨千吨)（以天计）（以天计）第15页总供水量：总供水量：160确定送水方案确定送水方案使利润最大使利润最大问题问题分析分析A：50B：60C：50甲：甲：30；+50乙：乙：70；+70丙：丙：10；+20丁：丁：10；+40总需求量总需求量(300)每个水库最大供水量都提升一倍每个水库最大供水量都提升一倍利润利润=收入收入(900)其它费用其它费用(450)引水管引水管理费理费利润利润(元元/千吨千吨)甲甲乙乙丙丙丁丁A290320230280B310320260300C260250220/供给供给限制限制B,C类似处理类似处理问题讨论问题讨论 确定送水方案确定送水方案使利润最大使利润最大需求约束能够不变需求约束能够不变第19页求解求解这类问题普通称为这类问题普通称为“运输问题运输问题”(TransportationProblem)总利润总利润 88700（元）（元）A(100)B(120)C(100)甲甲(30;50)乙乙(70;70)丙丙(10;20)丁丁(10;40)4010050305030 Globaloptimalsolutionfound.Objectivevalue:88700.00Totalsolveriterations:7VariableValueReducedCostX110.00000020.00000X12100.00000.000000X130.00000040.00000X140.00000020.00000X2130.000000.000000X2240.000000.000000X230.00000010.00000X2450.000000.000000X3150.000000.000000X320.00000020.00000X3330.000000.000000第20页怎样怎样装运，装运，使此次飞行使此次飞行赢利最大？赢利最大？三个货舱三个货舱最大最大载载重重(吨吨),),最大容积最大容积(米米3 3)例例2货机装运货机装运重量（吨）重量（吨）空间空间(米米3/吨）吨）利润（元利润（元/吨）吨）货物货物1184803100货物货物2156503800货物货物3235803500货物货物4123902850三个货舱中实际载重必须与其最大三个货舱中实际载重必须与其最大载载重成百分重成百分比比前仓：前仓：10；6800中仓：中仓：16；8700后仓：后仓：8；5300飞机平衡飞机平衡第21页决议决议变量变量 xij-第第i 种货物装入第种货物装入第j 个货舱重量个货舱重量(吨）吨）i=1,2,3,4,j=1,2,3(分别代表前、中、后仓分别代表前、中、后仓)模型假设模型假设 每种货物能够分割到任意小；每种货物能够分割到任意小；货机装运货机装运每种货物能够在一个或多个货舱中任意分布；每种货物能够在一个或多个货舱中任意分布；各种货物能够混装，并确保不留空隙；各种货物能够混装，并确保不留空隙；模型建立模型建立 第22页货舱货舱容积容积 目标目标函数函数(利润利润)约束约束条件条件货机装运货机装运模型建立模型建立 货舱货舱重量重量 10；680016；87008；5300 xij-第第i 种货物装入第种货物装入第j 个货舱重量个货舱重量第23页约束约束条件条件平衡平衡要求要求 货物货物供给供给 货机装运货机装运模型建立模型建立 10；680016；87008；5300 xij-第第i 种货物装入第种货物装入第j 个货舱重量个货舱重量第24页 Globaloptimalsolutionfound.Objectivevalue:121515.8VariableValueReducedCostX110.000000400.000000X120.00000057.894737X130.000000400.000000X2110.0000000.000000X220.000000239.473679X235.0000000.000000X310.0000000.000000X3212.9473690.000000X333.0000000.000000X410.000000650.000000X423.0526320.000000X430.000000650.000000货物货物2：前仓：前仓10,后仓后仓5；货物货物3:中仓中仓13,后仓后仓3；货物货物4:中仓中仓3。货机装运货机装运模型求解模型求解 最大利润约最大利润约121516元元货物货物供给点供给点货舱货舱需求点需求点平衡要求平衡要求运输运输问题问题运输问题扩展运输问题扩展第25页4.3 汽车生产与原油采购汽车生产与原油采购整数规划整数规划第26页设每个月生产小、中、大设每个月生产小、中、大型汽车数量分别为型汽车数量分别为x1,x2,x3例例1 1 汽车厂生产计划汽车厂生产计划 模型建立模型建立 小型小型中型中型大型大型现有量现有量钢材钢材1.535600时间时间28025040060000利润利润234线性线性规划规划模型模型(LP)第27页模型模型求解求解 3）模型中增加条件：模型中增加条件：x1,x2,x3均为整数，重新求解。均为整数，重新求解。Globaloptimalsolutionfound.Objectivevalue:632.2581VariableValueReducedCostX164.5161290.000000X2167.7419280.000000X30.0000000.946237RowSlackorSurplusDualPriceST10.0000000.731183ST20.0000000.003226结果为小数，结果为小数，怎么办？怎么办？1）舍去小数：取）舍去小数：取x1=64，x2=167，算出目标函数值，算出目标函数值z=629，与，与LP最优值最优值632.2581相差不大。相差不大。2）试试探探：如如取取x1=65，x2=167；x1=64，x2=168等等，计计算算函函数数值值z，经过比较可能得到更优解。，经过比较可能得到更优解。可能找不到最优！可能找不到最优！但必须检验它们是否满足约束条件。但必须检验它们是否满足约束条件。可能不是可行解！可能不是可行解！第28页IP可用可用LINDO直接求解直接求解整数规划整数规划(IntegerProgramming,简记简记IP)“gin(x1);”表示表示“x1为为整数整数”.”.IP最优解最优解x1=64，x2=168，x3=0，最优值，最优值z=632max=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);Globaloptimalsolutionfound.Objectivevalue:632.0000VariableValueReducedCostX164.000000-2.000000X2168.000000-3.000000X30.000000-4.000000模型求解模型求解 IP结果输出结果输出第29页其中其中3个个子模型应子模型应去掉，然后去掉，然后逐一求解，比较目标函数值，逐一求解，比较目标函数值，再加上整数约束，得最优解：再加上整数约束，得最优解：方法方法1：分解为：分解为8个个LP子模型子模型汽车厂生产计划汽车厂生产计划 若生产某类汽车，则最少生产若生产某类汽车，则最少生产8080辆，求生产计划。辆，求生产计划。x1,x2,x3=0或或 80 x1=80，x2=150，x3=0，最优值，最优值z=610第30页方法方法2：引入引入0-1变量，化为整数规划变量，化为整数规划M为大正数，为大正数，可取可取1000 若生产某类汽车，则最少生产若生产某类汽车，则最少生产8080辆，求生产计划。辆，求生产计划。x1=0 或 80 x2=0 或 80 x3=0 或 80第31页max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3=600;280*x1+250*x2+400*x3=60000;x1=80*y1;x2=80*y2;x3=80*y3;gin(x1);gin(x2);gin(x3);bin(y1);bin(y2);bin(y3);方法方法2：引入引入0-1变量，化为整数规划变量，化为整数规划 Globaloptimalsolutionfound.Objectivevalue:610.0000Extendedsolversteps:0Totalsolveriterations:10VariableValueReducedCostX180.00000-2.000000X2150.0000-3.000000X30.000000-4.000000Y11.0000000.000000Y21.0000000.000000Y30.0000000.000000 若生产某类汽车，则最少生产若生产某类汽车，则最少生产8080辆，求生产计划。辆，求生产计划。最优解同前最优解同前第32页NLP即即 使使 可可 用用 现现 成成 数数 学学 软软 件件 求求 解解(如如 LINGO,MATLAB)，不过其结果常依赖于初值选择。，不过其结果常依赖于初值选择。方法方法3：化为非线性规划化为非线性规划非线性规划（非线性规划（Non-LinearProgramming，简记，简记NLP）实实践践表表明明，本本例例仅仅当当初初值值非非常常靠靠近近上上面面方方法法算算出出最优解时，才能得到正确结果。最优解时，才能得到正确结果。若生产某类汽车，则最少生产若生产某类汽车，则最少生产8080辆，求生产计划。辆，求生产计划。x1=0 或 80 x2=0 或 80 x3=0 或 80第33页max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3=600;280*x1+250*x2+400*x3=0;x2*(x2-80)=0;x3*(x3-80)=0;gin(x1);gin(x2);gin(x3);Global optimal solution found.Objective value:610.0000 Extended solver steps:2 Total solver iterations:171 Variable Value X1 80.00000 X2 150.0000 X3 0.000000第34页应怎样安排原油采购和加工应怎样安排原油采购和加工？例例2原油采购与加工原油采购与加工市场上可买到不超出市场上可买到不超出1500吨原油吨原油A：购置量不超出购置量不超出500吨时单价为吨时单价为10000元元/吨；吨；购置量超出购置量超出500吨但不超出吨但不超出1000吨时，超出吨时，超出500吨吨 部分部分8000元元/吨；吨；购置量超出购置量超出1000吨时，超出吨时，超出1000吨部分吨部分6000元元/吨。吨。售价售价4800元元/吨吨售价售价5600元元/吨吨库存库存500吨吨库存库存1000吨吨汽油甲汽油甲(A 50%)原油原油A原油原油B汽油乙汽油乙(A 60%)第35页决议决议变量变量 目标目标函数函数问题问题分析分析 利润：销售汽油收入利润：销售汽油收入-购置原油购置原油A支出支出 难点：原油难点：原油A购价与购置量关系较复杂购价与购置量关系较复杂甲甲(A 50%)AB乙乙(A 60%)购置购置xx11x12x21x224.8千元千元/吨吨5.6千元千元/吨吨原油原油A购置量购置量,原油原油A,B生产生产汽油汽油甲甲,乙数量乙数量c(x)购置原油购置原油A支出支出利润利润(千元千元)c(x)怎样表述？怎样表述？第36页原油供给原油供给 约束约束条件条件 x 500吨单价为吨单价为10千千元元/吨；吨；500吨吨 x 1000吨，超出吨，超出500吨吨8千千元元/吨；吨；1000吨吨 x 1500吨，超出吨，超出1000吨吨6千千元元/吨。吨。目标目标函数函数购置购置x ABx11x12x21x22库存库存500吨吨库存库存1000吨吨第37页目标函数中目标函数中c(x)不是线性函数，是非线性规划；不是线性函数，是非线性规划；对于用分段函数定义对于用分段函数定义c(x)，普通非线性规划软件也，普通非线性规划软件也难以输入和求解；难以输入和求解；想方法将模型化简，用现成软件求解。想方法将模型化简，用现成软件求解。汽油含原油汽油含原油A百分比限制百分比限制约束约束条件条件甲甲(A 50%)AB乙乙(A 60%)x11x12x21x22第38页x1,x2,x3以价格以价格10,8,6(千元千元/吨吨)采购采购A吨数吨数目标目标函数函数 只有当以只有当以10千元千元/吨价格购置吨价格购置x1=500(吨吨)时，才能以时，才能以8千元千元/吨价格购置吨价格购置x2方法方法1 非线性规划模型非线性规划模型，能够用，能够用LINGO求解求解模型求解模型求解x=x1+x2+x3,c(x)=10 x1+8x2+6x3 500吨吨 x 1000吨，超出吨，超出500吨吨8千千元元/吨吨增加约束增加约束x=x1+x2+x3,c(x)=10 x1+8x2+6x3 第39页方法方法1：LINGO求解求解Model:Max=4.8*x11+4.8*x21+5.6*x12+5.6*x22-10*x1-8*x2-6*x3;x11+x12x+500;x21+x220;2*x12-3*x220;x=x1+x2+x3;(x1-500)*x2=0;(x2-500)*x3=0;x1500;x2500;x30;x110;x120;x210;x220;x10;x20;x30;endObjectivevalue:4800.000VariableValueReducedCostX11500.00000.0000000E+00X21500.00000.0000000E+00X120.0000000E+000.0000000E+00X220.0000000E+000.0000000E+00X10.1021405E-1310.00000X20.0000000E+008.000000X30.0000000E+006.000000X0.0000000E+000.0000000E+00LINGO得到是局部最优解，得到是局部最优解，还能还能得到更加好解吗？得到更加好解吗？用库存用库存500吨原油吨原油A、500吨原油吨原油B生生产汽油甲，不购置新原油产汽油甲，不购置新原油A，利润，利润为为4,800千千元。元。第40页y1,y2,y3=1以价格以价格10,8,6(千元千元/吨吨)采购采购A增增加加约约束束方法方法2 0-1线性规划模型线性规划模型，可用，可用LINGO求解求解y1,y2,y3=0或或1Objectivevalue:5000.000VariableValueReducedCostY11.0000000.000000Y21.0000002200.000000Y31.0000001200.000000X110.0000000.800000X210.0000000.800000X121500.0000000.000000X221000.0000000.000000X1500.0000000.000000X2500.0000000.000000X30.0000000.400000X1000.0000000.000000购置购置1000吨原油吨原油A，与，与库存库存500吨原油吨原油A和和1000吨原油吨原油B一起，生产汽一起，生产汽油乙，利润为油乙，利润为5,000千元千元。x1,x2,x3以价格以价格10,8,6(千元千元/吨吨)采购采购A吨数吨数y=0 x=0 x0y=1优于方法优于方法1结果结果第41页b1b2b3b4方法方法3 b1 x b2，x=z1b1+z2b2，z1+z2=1，z1,z2 0,c(x)=z1c(b1)+z2c(b2).c(x)x190005000050010001500b2 x b3，x=z2b2+z3b3，z2+z3=1，z2,z3 0,c(x)=z2c(b2)+z3c(b3).b3 x b4，x=z3b3+z4b4，z3+z4=1，z3,z4 0,c(x)=z3c(b3)+z4c(b4).直接处理处理分段线性函数直接处理处理分段线性函数c(x)第42页IP模型，模型，LINGO求求解，得到结果与方解，得到结果与方法法2相同相同.处理分段线性函数，方法处理分段线性函数，方法3更具普通性更具普通性bk x bk+1yk=1,不然不然,yk=0方法方法3 bk x bk+1,x=zkbk+z k+1bk+1zk+zk+1=1，zk,zk+1 0,c(x)=zkc(bk)+zk+1c(bk+1).c(x)x190005000050010001500b1b2b3b4对于对于k=1,2,3第43页示性函数使用已知mx M,z=0 or 1,那么 若x0,则z=1 若z=0,则x=0 x Mz若x=0,则z=0 若z=1,则x 0 x mz条件约束 if,then若x1+x23,则x3+x4 6 x3+x4 6z,x1+x2-3Mz若x1+x2=3,则x3+x4 6 x3+x4 6(1-z),x1+x2-3 mz逻辑运算 or,andx1 3或x2 3 x1 3z1,x2 3z2,z1+z2 1 分段线性目标函数如例2 原油采购与加工原油采购与加工 第44页第45页