《第三讲数学规划模型精选文档.ppt》由会员分享，可在线阅读，更多相关《第三讲数学规划模型精选文档.ppt（33页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三讲数学规划模型本讲稿第一页，共三十三页优化模型的优化模型的简单分类简单分类线性规划线性规划(LP)目标和约束均为线性函数目标和约束均为线性函数非线性规划非线性规划(NLP)目标或约束中存在非线性函数目标或约束中存在非线性函数二次规划二次规划(QP)目标为二次函数、约束为线性目标为二次函数、约束为线性整数规划整数规划(IP)决策变量决策变量(全部或部分全部或部分)为整数为整数整数整数线性线性规划规划(ILP)，整数，整数非线性非线性规划规划(INLP)一般整数规划，一般整数规划，0-1（整数）规划（整数）规划连连续续优优化化离离散散优优化化数学规划数学规划本讲稿第二页，共三十三页例例1加工奶
2、制品的生产计划加工奶制品的生产计划获利24元/公斤 1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利16元/公斤 50桶牛奶桶牛奶时间时间480小时小时甲设备至多加工甲设备至多加工100公斤公斤A1制订生产计划，使每天获利最大制订生产计划，使每天获利最大 每天：每天：线性规划模型线性规划模型本讲稿第三页，共三十三页1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 x1桶牛奶生产桶牛奶生产A1x2桶牛奶生产桶牛奶生产A2获利获利243x1获利获利164 x2原料供应原料供应 劳动时间劳动时间 加工能力加工能力 决策变量决策变量 目标函数目标函数
3、每天获利每天获利约束条件约束条件非负约束非负约束 线性线性规划规划模型模型(LP)时间时间480小时小时至多加工至多加工100公斤公斤A150桶牛奶桶牛奶每天每天本讲稿第四页，共三十三页模型求解模型求解 软件实现软件实现 LINGOmodel:max=72*x1+64*x2;milkx1+x250;time12*x1+8*x2480;cpct3*x1100;end Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCost X120.000000.000000
4、X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.000000 20桶牛奶生产桶牛奶生产A1,30桶生产桶生产A2，利润，利润3360元元.本讲稿第五页，共三十三页如何如何装运，装运，使本次飞行使本次飞行获利最大？获利最大？三个货舱三个货舱最大最大载载重重(t),(t),最大容积最大容积(m(m3 3)例例2 货机装运货机装运重量重量（t）体积体积(m3/t）利润利润（元（元/t）货物货物1184803100货物货物
5、2156503800货物货物3235803500货物货物4123902850三个货舱中实际载重必须与其最大三个货舱中实际载重必须与其最大载载重成比例重成比例.前仓：前仓：10；6800中仓：中仓：16；8700后仓：后仓：8；5300飞机平衡飞机平衡本讲稿第六页，共三十三页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的重量限制的重量
6、限制WETj体积限制体积限制VOLj第第i种货物的重量种货物的重量wi，单位重量的体积，单位重量的体积vi，利润，利润pi货机装运货机装运本讲稿第七页，共三十三页决策决策变量变量 xij-第第i 种货物装入第种货物装入第j 个货舱的重量个货舱的重量(t(t）i=1,2,3,4,j=1,2,3(分别代表前、中、后仓分别代表前、中、后仓)模型假设模型假设 每种货物可以分割到任意小；每种货物可以分割到任意小；货机装运货机装运每种货物可以在一个或多个货舱中任意分布；每种货物可以在一个或多个货舱中任意分布；多种货物可以混装，并保证不留空隙；多种货物可以混装，并保证不留空隙；所给出的数据都是精确的，没有误
7、差所给出的数据都是精确的，没有误差.模型建立模型建立 本讲稿第八页，共三十三页货舱货舱容积容积 目标函目标函数数(利利润润)约束约束条件条件货机装运货机装运模型建立模型建立 货舱货舱重量重量 10；680016；87008；5300 xij-第第i 种货物装入第种货物装入第j 个货舱的重量个货舱的重量本讲稿第九页，共三十三页约束约束条件条件平衡平衡要求要求 货物货物供应供应 货机装运货机装运模型建立模型建立 10；680016；87008；5300 xij-第第i 种货物装入第种货物装入第j 个货舱的重量个货舱的重量j,k=1,2,3;jk 本讲稿第十页，共三十三页!定义集合及变量定义集合及变
8、量;sets:cang/1.3/:WET,VOL;wu/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(
9、i):v(i)*x(i,j)VOL(j);for(cang(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程序程序本讲稿第十一页，共三十三页 Globaloptimalsolutionfound.Objectivevalue:121515.8Totalsolveriterations:12VariableValueReducedCostX(1,1)0.000000400.0000X(1,2)0.00000057.89474
10、X(1,3)0.000000400.0000X(2,1)7.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.货机装运货机装运模型求解模型求解 最大利润约最大利润约1
11、21516元元本讲稿第十二页，共三十三页 如果生产某一类型汽车，则至少要生产如果生产某一类型汽车，则至少要生产8080辆，辆，那么最优的生产计划应作何改变？那么最优的生产计划应作何改变？例例1 汽车厂生产计划汽车厂生产计划 汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量劳动时间的需求，利润及工厂每月的现有量.小型小型中型中型大型大型现有量现有量钢材（钢材（t）1.535600劳动时间（劳动时间（h）28025040060000利润（万元）利润（万元）234制订月生产计划，使工厂的利润最大制订月生产计划，
12、使工厂的利润最大.4.3 汽车生产与原油采购汽车生产与原油采购本讲稿第十三页，共三十三页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:0To
13、talsolveriterations:3VariableValueReducedCostX164.00000-2.000000X2168.0000-3.000000X30.000000-4.000000IP结果输出结果输出设每月生产小、中、大型汽设每月生产小、中、大型汽车的数量分别为车的数量分别为x1,x2,x3本讲稿第十四页，共三十三页其中其中3个个子模型应子模型应去掉，然后逐一去掉，然后逐一求解，比较目标函数值，再加上整求解，比较目标函数值，再加上整数约束，得最优解：数约束，得最优解：方法方法1：分解为：分解为8个个LP子模型子模型汽车厂生产计划汽车厂生产计划 若生产某类汽车，则至少生产
14、若生产某类汽车，则至少生产8080辆，求生产计划辆，求生产计划.x1,x2,x3=0或或 80 x1=80，x2=150，x3=0，最优值，最优值z=610本讲稿第十五页，共三十三页LINGO中中 对对 0-1变量的限定：变量的限定：bin(y1);bin(y2);bin(y3);方法方法2：引入引入0-1变量，化为整数规划变量，化为整数规划M为大的正数为大的正数,本例可取本例可取1000ObjectiveValue:610.0000VariableValueReducedCostX180.000000-2.000000X2150.000000-3.000000X30.000000-4.000
15、000Y11.0000000.000000Y21.0000000.000000Y30.0000000.000000 若生产某类汽车，则至少生产若生产某类汽车，则至少生产8080辆，求生产计划辆，求生产计划.x1=0 或 80 x2=0 或 80 x3=0 或 80最优解同前最优解同前本讲稿第十六页，共三十三页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-L
16、inearProgramming，简，简记记NLP）若生产某类汽车，则至少生产若生产某类汽车，则至少生产8080辆，求生产计划辆，求生产计划.x1=0 或 80 x2=0 或 80 x3=0 或 80最优解同前最优解同前.一般地，整数规划和非线性一般地，整数规划和非线性规划的求解比线性规划困难规划的求解比线性规划困难得多，特别是问题规模较大得多，特别是问题规模较大或者要求得到全局最优解时或者要求得到全局最优解时.本讲稿第十七页，共三十三页汽车厂生产计划汽车厂生产计划 决策变量为整数决策变量为整数,建立建立整数规划模型整数规划模型.求解整数规划和非线性规划比线性规划困求解整数规划和非线性规划比线
17、性规划困难得多难得多(即便用数学软件即便用数学软件).当整数变量取值很大时当整数变量取值很大时,可作为连续变量可作为连续变量处理处理,问题问题简化为线性规划简化为线性规划.对于类似于对于类似于“x=0或或 80”这样的条件，通常这样的条件，通常引入引入0-1变量变量处理，尽量不用非线性规划（特别是引入处理，尽量不用非线性规划（特别是引入的整数变量个数较少时）的整数变量个数较少时）.本讲稿第十八页，共三十三页应如何安排原油的采购和加工应如何安排原油的采购和加工？例例2 原油采购与加工原油采购与加工 市场上可买到不超过市场上可买到不超过1500t t的原油的原油A：购买量不超过购买量不超过500t
18、 t时的单价为时的单价为10000元元/t/t；购买量超过购买量超过500t t但不超过但不超过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%)本讲稿第十九页，共三十三页决策决策变量变量 目标目标函数函数问题问题分析分析 利润：销售汽油的收入利润：销售汽油的收入 购买原油购买原油A的支出的支出.难点：原油难点：原油
19、A的购价与购买量的关系较复杂的购价与购买量的关系较复杂.甲甲(A 50%)AB乙乙(A 60%)购买购买xx11x12x21x224.8千元千元/t5.6千元千元/t原油原油A的购买量的购买量,原油原油A,B生产生产汽油汽油甲甲,乙的数量乙的数量c(x)购买原油购买原油A的支出的支出利润利润(千元千元)c(x)如何表述？如何表述？本讲稿第二十页，共三十三页原油供应原油供应 约束约束条件条件 x 500t t单价为单价为10千千元元/t/t；500t t x 1000t t，超过，超过500t t的的8千千元元/t/t；1000t t x 1500t t，超过，超过1000t t的的6千千元元/
20、t./t.目标目标函数函数购买购买x ABx11x12x21x22库存库存500t库存库存1000t本讲稿第二十一页，共三十三页目标函数中目标函数中c(x)不是线性函数，是非线性规划；不是线性函数，是非线性规划；对于用分段函数定义的对于用分段函数定义的c(x)，一般的非线性规划软件也难，一般的非线性规划软件也难以输入和求解；以输入和求解；想办法将模型化简，用现成的软件求解想办法将模型化简，用现成的软件求解.汽油含原油汽油含原油A的比例限制的比例限制约束约束条件条件甲甲(A 50%)AB乙乙(A 60%)x11x12x21x22本讲稿第二十二页，共三十三页x1,x2,x3以价格以价格10,8,6
21、(千元千元/t)t)采购采购A的吨数的吨数目标目标函数函数 只有当以只有当以10千元千元/t t的价格购买的价格购买x1=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 类似地有类似地有本讲稿第二十三页，共三十三页方法方法1：LINGO求解求解Model:Max=
22、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;x30y=1与方法与方法1（全局最优解）的结果相同（全局最优解）的结果相同引入引入0-1变量变量模型求解模型求解本讲稿第二十六页，共三十三页b1b2b3b4方法方法3 b1 x b2，x=z1b1+z2b2，z1+z2=1，z1,z2 0,c(x)=z1c(b1)+z2c(b2).c(x)x1200090005000O500100
23、01500b2 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)本讲稿第二十七页，共三十三页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(
24、x)x1200090005000O50010001500b1b2b3b4对于对于k=1,2,3本讲稿第二十八页，共三十三页方法方法3:直接处理分段线性函数，方法更具一般性直接处理分段线性函数，方法更具一般性.分段函数分段函数无法直接用非线性规划方法或软件求解无法直接用非线性规划方法或软件求解.原油采购与加工原油采购与加工 方法方法1:增加约束化为增加约束化为非线性规划非线性规划,可以用可以用LINGO求解求解,但可能但可能得到的是局部最优解得到的是局部最优解.方法方法2:引入引入0-1变量变量,化为化为线性规划模型线性规划模型,可用可用LINGO求解求解.本讲稿第二十九页，共三十三页如何选拔队
25、员组成如何选拔队员组成4 4 100100m混合泳接力队混合泳接力队?例例1 混合泳接力队的选拔混合泳接力队的选拔 5名候选人的名候选人的百米成绩百米成绩甲甲乙乙丙丙丁丁戊戊蝶泳蝶泳仰泳仰泳蛙泳蛙泳自由泳自由泳本讲稿第三十页，共三十三页目标目标函数函数若选择队员若选择队员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.2
26、71j=38766.484.669.683.8j=458.65359.457.262.4每种泳姿有且只有每种泳姿有且只有1 1人人 本讲稿第三十一页，共三十三页模型求解模型求解 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(per
27、son(i):sum(position(j):x(i,j)=1;);for(position(i):sum(person(j):x(j,i)=1;);for(link:bin(x);END 本讲稿第三十二页，共三十三页混合泳接力队的选拔混合泳接力队的选拔指派指派(Assignment)问题问题：有若干项任务有若干项任务,每项任务必有且每项任务必有且只能有一人承担，每人只能承担一项只能有一人承担，每人只能承担一项，不同人员承担不同，不同人员承担不同任务的效益任务的效益(或成本或成本)不同，怎样分派各项任务使总效益最不同，怎样分派各项任务使总效益最大大(或总成本最小或总成本最小)?人员数量与任务数量相等人员数量与任务数量相等人员数量大于任务数量人员数量大于任务数量(本例本例)人员数量小于任务数量人员数量小于任务数量?建立建立0-1规划模型是常用方法规划模型是常用方法本讲稿第三十三页，共三十三页