第三讲数学规划模型优秀课件.ppt

《第三讲数学规划模型优秀课件.ppt》由会员分享，可在线阅读，更多相关《第三讲数学规划模型优秀课件.ppt（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三讲数学规划模型第1页，本讲稿共33页优化模型的优化模型的简单分类简单分类线性规划线性规划(LP)目标和约束均为线性函数目标和约束均为线性函数非线性规划非线性规划(NLP)目标或约束中存在非线性函数目标或约束中存在非线性函数二次规划二次规划(QP)目标为二次函数、约束为线性目标为二次函数、约束为线性整数规划整数规划(IP)决策变量决策变量(全部或部分全部或部分)为整数为整数整数整数线性线性规划规划(ILP)，整数，整数非线性非线性规划规划(INLP)一般整数规划，一般整数规划，0-1（整数）规划（整数）规划连连续续优优化化离离散散优优化化数学规划数学规划第2页，本讲稿共33页例例1加工奶制品

2、的生产计划加工奶制品的生产计划获利24元/公斤 1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利16元/公斤 50桶牛奶桶牛奶时间时间480小时小时甲设备至多加工甲设备至多加工100公斤公斤A1制制订生生产计划，使每天划，使每天获利最大利最大 每天：每天：线性规划模型线性规划模型第3页，本讲稿共33页1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 x1桶牛奶生产桶牛奶生产A1x2桶牛奶生产桶牛奶生产A2获利获利243x1获利获利164 x2原料供应原料供应 劳动时间劳动时间 加工能力加工能力 决策决策变量量 目目标函数函数 每天获利每天获利约

3、束条件束条件非负约束非负约束 线性线性规划规划模型模型(LP)时间时间480小时小时至多加工至多加工100公斤公斤A150桶牛奶桶牛奶每天每天第4页，本讲稿共33页模型求解模型求解 软件件实现 LINGOmodel:max=72*x1+64*x2;milkx1+x250;time12*x1+8*x2480;cpct3*x1100;end Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCost X120.000000.000000X230.000000.00

4、0000RowSlackorSurplusDualPrice13360.0001.000000MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.000000 20桶牛奶生产桶牛奶生产A1,30桶生产桶生产A2，利润，利润3360元元.第5页，本讲稿共33页如何如何装运，装运，使本次飞行使本次飞行获利最大？获利最大？三个货舱三个货舱最大最大载载重重(t),(t),最大容积最大容积(m(m3 3)例例2 货机装运货机装运重量重量（t）体积体积(m3/t）利润利润（元（元/t）货物货物1184803100货物货物2156503800货物货物3

5、235803500货物货物4123902850三个货舱中实际载重必须与其最大三个货舱中实际载重必须与其最大载载重成比例重成比例.前仓：前仓：10；6800中仓：中仓：16；8700后仓：后仓：8；5300飞机平衡飞机平衡第6页，本讲稿共33页WET=(10,16,8),VOL=(6800,8700,5300);w=(18,15,23,12),v=(480,650,580,390),p=(3100,3800,3500,2850).已知参数已知参数 i=1,2,3,4（货物）（货物）j=1,2,3(分别代表前、中、后仓分别代表前、中、后仓)货舱货舱j的重量限制的重量限制WETj体积限制体积限制VO

6、Lj第第i种货物的重量种货物的重量wi，单位重量的体积，单位重量的体积vi，利润，利润pi货机装运机装运第7页，本讲稿共33页决策决策变量量 xij-第第i 种货物装入第种货物装入第j 个货舱的重量个货舱的重量(t(t）i=1,2,3,4,j=1,2,3(分别代表前、中、后仓分别代表前、中、后仓)模型假模型假设 每种货物可以分割到任意小；每种货物可以分割到任意小；货机装运机装运每种货物可以在一个或多个货舱中任意分布；每种货物可以在一个或多个货舱中任意分布；多种货物可以混装，并保证不留空隙；多种货物可以混装，并保证不留空隙；所给出的数据都是精确的，没有误差所给出的数据都是精确的，没有误差.模型建

7、立模型建立 第8页，本讲稿共33页货舱货舱容积容积 目目标函函数数(利利润润)约束束条件条件货机装运机装运模型建立模型建立 货舱货舱重量重量 10；680016；87008；5300 xij-第第i 种货物装入第种货物装入第j 个货舱的重量个货舱的重量第9页，本讲稿共33页约束束条件条件平衡平衡要求要求 货物货物供应供应 货机装运机装运模型建立模型建立 10；680016；87008；5300 xij-第第i 种货物装入第种货物装入第j 个货舱的重量个货舱的重量j,k=1,2,3;jk 第10页，本讲稿共33页!定义集合及变量定义集合及变量;sets:cang/1.3/:WET,VOL;wu/

8、1.4/:w,v,p;link(wu,cang):x;endsets!对已知变量赋值对已知变量赋值;data:WET=10,16,8;VOL=6800,8700,5300;w=18,15,23,12;v=480,650,580,390;p=3100,3800,3500,2850;enddatamax=sum(wu(i):p(i)*sum(cang(j):x(i,j);for(wu(i):sum(cang(j):x(i,j)w(i);for(cang(j):sum(wu(i):x(i,j)WET(j);for(cang(j):sum(wu(i):v(i)*x(i,j)VOL(j);for(can

9、g(j):for(cang(k)|k#GT#j:!#GT#是大于等于的含义是大于等于的含义;sum(wu(i):x(i,j)/WET(j)=sum(wu(i):x(i,k)/WET(k););END货机装运机装运LINGO程序程序第11页，本讲稿共33页 Globaloptimalsolutionfound.Objectivevalue:121515.8Totalsolveriterations:12VariableValueReducedCostX(1,1)0.000000400.0000X(1,2)0.00000057.89474X(1,3)0.000000400.0000X(2,1)7.

10、0000000.000000X(2,2)0.000000239.4737X(2,3)8.0000000.000000X(3,1)3.0000000.000000X(3,2)12.947370.000000X(3,3)0.0000000.000000X(4,1)0.000000650.0000X(4,2)3.0526320.000000X(4,3)0.000000650.0000货物货物2：前仓：前仓7,后仓后仓8；货货物物3:前仓前仓3,中仓中仓1 13；货物货物4:中仓中仓3.货机装运机装运模型求解模型求解 最大利润约最大利润约121516元元第12页，本讲稿共33页 如果生产某一类型汽车，

11、则至少要生产如果生产某一类型汽车，则至少要生产8080辆，辆，那么最那么最优的生产计划应作何改变？优的生产计划应作何改变？例例1 汽车厂生产计划汽车厂生产计划 汽车厂生产三种类型的汽车，已知各类型每辆车对钢汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量材、劳动时间的需求，利润及工厂每月的现有量.小型小型中型中型大型大型现有量现有量钢材（钢材（t）1.535600劳动时间（劳动时间（h）28025040060000利润（万元）利润（万元）234制订月生产计划，使工厂的利润最大制订月生产计划，使工厂的利润最大.4.3汽车生产与原油采购汽车生产与原油采购第1

12、3页，本讲稿共33页IP可用可用LINGO直接求解直接求解整数规划整数规划(IntegerProgramming,简记简记IP)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.0000Extendedsolversteps:0Totalsolveriterations:3VariableValue

13、ReducedCostX164.00000-2.000000X2168.0000-3.000000X30.000000-4.000000IP结果输出结果输出设每月生产小、中、大型汽设每月生产小、中、大型汽车的数量分别为车的数量分别为x1,x2,x3第14页，本讲稿共33页其中其中3个个子模型应子模型应去掉，然后逐一去掉，然后逐一求解，比较目标函数值，再加上求解，比较目标函数值，再加上整数约束，得最优解：整数约束，得最优解：方法方法1：分解为：分解为8个个LP子模型子模型汽汽车厂生厂生产计划划 若生产某类汽车，则至少生产若生产某类汽车，则至少生产8080辆，求生产计划辆，求生产计划.x1,x2,

14、x3=0或或 80 x1=80，x2=150，x3=0，最优值，最优值z=610第15页，本讲稿共33页LINGO中中 对对 0-1变变量的限定：量的限定：bin(y1);bin(y2);bin(y3);方法方法2：引入引入0-1变量，化为整数规划变量，化为整数规划M为大的正数为大的正数,本例可取本例可取1000ObjectiveValue:610.0000VariableValueReducedCostX180.000000-2.000000X2150.000000-3.000000X30.000000-4.000000Y11.0000000.000000Y21.0000000.000000

15、Y30.0000000.000000 若生产某类汽车，则至少生产若生产某类汽车，则至少生产8080辆，求生产计划辆，求生产计划.x1=0 或 80 x2=0 或 80 x3=0 或 80最优解同前最优解同前第16页，本讲稿共33页max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3600;280*x1+250*x2+400*x30;x2*(x2-80)0;x3*(x3-80)0;gin(x1);gin(x2);gin(x3);方法方法3：化为非线性规划化为非线性规划非线性规划（非线性规划（Non-LinearProgramming，简记简记NLP）若生产某类汽车，则至少生产若

16、生产某类汽车，则至少生产8080辆，求生产计划辆，求生产计划.x1=0 或 80 x2=0 或 80 x3=0 或 80最优解同前最优解同前.一般地，整数规划和非线性一般地，整数规划和非线性规划的求解比线性规划困难规划的求解比线性规划困难得多，特别是问题规模较大得多，特别是问题规模较大或者要求得到全局最优解时或者要求得到全局最优解时.第17页，本讲稿共33页汽汽车厂生厂生产计划划 决策变量为整数决策变量为整数,建立建立整数规划模型整数规划模型.求解整数规划和非线性规划比线性规划困求解整数规划和非线性规划比线性规划困难得多难得多(即便用数学软件即便用数学软件).当整数变量取值很大时当整数变量取值

17、很大时,可作为连续变量处理可作为连续变量处理,问题问题简化为线性规划简化为线性规划.对于类似于对于类似于“x=0或或 80”这样的条件，通常这样的条件，通常引入引入0-1变量变量处理，尽量不用非线性规划（特别是引处理，尽量不用非线性规划（特别是引入的整数变量个数较少时）入的整数变量个数较少时）.第18页，本讲稿共33页应如何安排原油的采购和加工应如何安排原油的采购和加工？例例2 原油采购与加工原油采购与加工 市场上可买到不超过市场上可买到不超过1500t t的原油的原油A：购买量不超过购买量不超过500t t时的单价为时的单价为10000元元/t/t；购买量超过购买量超过500t t但不超过但

18、不超过1000t t时，超过时，超过500t t的的 部部分分8000元元/t/t；购买量超过购买量超过1000t t时，超过时，超过1000t t的部分的部分6000元元/t./t.售价售价4800元元/t售价售价5600元元/t库存库存500t库存库存1000t汽油甲汽油甲(A 50%)原油原油A原油原油B汽油乙汽油乙(A 60%)第19页，本讲稿共33页决策决策变量量 目目标函数函数问题分析分析 利润：销售汽油的收入利润：销售汽油的收入 购买原油购买原油A的支出的支出.难点：原油难点：原油A的购价与购买量的关系较复杂的购价与购买量的关系较复杂.甲甲(A 50%)AB乙乙(A 60%)购买

19、购买xx11x12x21x224.8千元千元/t5.6千元千元/t原油原油A的购买量的购买量,原油原油A,B生产生产汽油汽油甲甲,乙的数量乙的数量c(x)购买原油购买原油A的支出的支出利润利润(千元千元)c(x)如何表述？如何表述？第20页，本讲稿共33页原油供应原油供应 约束束条件条件 x 500t t单价为单价为10千千元元/t/t；500t t x 1000t t，超过，超过500t t的的8千千元元/t/t；1000t t x 1500t t，超过，超过1000t t的的6千千元元/t./t.目目标函数函数购买购买x ABx11x12x21x22库存库存500t库存库存1000t第21

20、页，本讲稿共33页目标函数中目标函数中c(x)不是线性函数，是非线性规划；不是线性函数，是非线性规划；对于用分段函数定义的对于用分段函数定义的c(x)，一般的非线性规划软件也难，一般的非线性规划软件也难以输入和求解；以输入和求解；想办法将模型化简，用现成的软件求解想办法将模型化简，用现成的软件求解.汽油含原油汽油含原油A的比例限制的比例限制约束束条件条件甲甲(A 50%)AB乙乙(A 60%)x11x12x21x22第22页，本讲稿共33页x1,x2,x3以价格以价格10,8,6(千元千元/t)t)采购采购A的吨数的吨数目目标函数函数 只有当以只有当以10千元千元/t t的价格购买的价格购买x

21、1=500(t)(t)时，才能以时，才能以8千元千元/t t的价格购买的价格购买x2方法方法1 非线性规划模型非线性规划模型，可以用，可以用LINGO求解求解模型求解模型求解x=x1+x2+x3,c(x)=10 x1+8x2+6x3 500t t x 1000t t，超过，超过500t t的的8千千元元/t/t增加约束增加约束x=x1+x2+x3,c(x)=10 x1+8x2+6x3 类似地有类似地有第23页，本讲稿共33页方法方法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;

22、x21+x220;2*x12-3*x220;x=x1+x2+x3;(x1-500)*x2=0;(x2-500)*x3=0;x1500;x2500;x30y=1与方法与方法1（全局最优解）的结果相同（全局最优解）的结果相同引入引入0-1变量变量模型求解模型求解第26页，本讲稿共33页b1b2b3b4方法方法3 b1 x b2，x=z1b1+z2b2，z1+z2=1，z1,z2 0,c(x)=z1c(b1)+z2c(b2).c(x)x1200090005000O50010001500b2 x b3，x=z2b2+z3b3，z2+z3=1，z2,z3 0,c(x)=z2c(b2)+z3c(b3).b

23、3 x b4，x=z3b3+z4b4，z3+z4=1，z3,z4 0,c(x)=z3c(b3)+z4c(b4).直接处理分段线性函数直接处理分段线性函数c(x)第27页，本讲稿共33页IP模型，模型，LINGO求求解，得到的结果与解，得到的结果与方法方法2相同相同.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)x1200090005000O50010001500b1b2b3b4对于对于k=1,2,3第28页，本讲稿共33页方法方法3:

24、直接处理分段线性函数，方法更具一般性直接处理分段线性函数，方法更具一般性.分段函数分段函数无法直接用非线性规划方法或软件求解无法直接用非线性规划方法或软件求解.原油采购与加工原油采购与加工 方法方法1:增加约束化为增加约束化为非线性规划非线性规划,可以用可以用LINGO求解求解,但可能但可能得到的是局部最优解得到的是局部最优解.方法方法2:引入引入0-1变量变量,化为化为线性规划模型线性规划模型,可用可用LINGO求解求解.第29页，本讲稿共33页如何选拔队员组成如何选拔队员组成4 4 100100m混合泳接力队混合泳接力队?例例1 混合泳接力队的选拔混合泳接力队的选拔 5名候选人的名候选人的

25、百米成绩百米成绩甲甲乙乙丙丙丁丁戊戊蝶泳蝶泳仰泳仰泳蛙泳蛙泳自由泳自由泳第30页，本讲稿共33页目标目标函数函数若选择队员若选择队员i参加泳姿参加泳姿j 的比赛，记的比赛，记xij=1,否则记否则记xij=0 0-1规划模型划模型 cij(s)队员队员i第第j 种泳姿的百米成绩种泳姿的百米成绩约束约束条件条件每人最多入选泳姿之一每人最多入选泳姿之一ciji=1i=2i=3i=4i=5j=166.857.2787067.4j=275.66667.874.271j=38766.484.669.683.8j=458.65359.457.262.4每种泳姿有且只有每种泳姿有且只有1 1人人 第31页，

26、本讲稿共33页模型求解模型求解 MODEL:sets:person/1.5/;position/1.4/;link(person,position):c,x;endsetsdata:c=66.8,75.6,87,58.6,57.2,66,66.4,53,78,67.8,84.6,59.4,70,74.2,69.6,57.2,67.4,71,83.8,62.4;enddata输入输入LINGO求解求解 min=sum(link:c*x);for(person(i):sum(position(j):x(i,j)=1;);for(position(i):sum(person(j):x(j,i)=1;

27、);for(link:bin(x);END 第32页，本讲稿共33页混合泳接力队的选拔混合泳接力队的选拔指派指派(Assignment)问题问题：有若干项任务有若干项任务,每项任务必有且只每项任务必有且只能有一人承担，每人只能承担一项能有一人承担，每人只能承担一项，不同人员承担不同任，不同人员承担不同任务的效益务的效益(或成本或成本)不同，怎样分派各项任务使总效益最不同，怎样分派各项任务使总效益最大大(或总成本最小或总成本最小)?人员数量与任务数量相等人员数量与任务数量相等人员数量大于任务数量人员数量大于任务数量(本例本例)人员数量小于任务数量人员数量小于任务数量?建立建立0-1规划模型是常用方法规划模型是常用方法第33页，本讲稿共33页