《《数学规划模型》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《数学规划模型》PPT课件.ppt（33页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数学规划模型数学规划模型 实际问题中实际问题中的优化模型的优化模型x决策变量决策变量f(x)目标函数目标函数gi(x)0约束条约束条件件决策变量个数决策变量个数n和和约束条件个数约束条件个数m较大较大最优解在可行域最优解在可行域的边界上取得的边界上取得数数学学规规划划线性规划线性规划非线性规划非线性规划整数规划整数规划重点在模型的建立和结果的分析重点在模型的建立和结果的分析优化模型的优化模型的简单分类简单分类线性规划线性规划(LP)目标和约束均为线性函数目标和约束均为线性函数非线性规划非线性规划(NLP)目标或约束中存在非线性函数目标或约束中存在非线性函数二次规划二次规划(QP)目标为二次函数
2、、约束为线性目标为二次函数、约束为线性整数规划整数规划(IP)决策变量决策变量(全部或部分全部或部分)为整数为整数整数整数线性线性规划规划(ILP)，整数，整数非线性非线性规划规划(INLP)一般整数规划，一般整数规划，0-1（整数）规划（整数）规划连连续续优优化化离离散散优优化化数学规划数学规划例例1加工奶制品的生产计划加工奶制品的生产计划获利24元/公斤 1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利16元/公斤 50桶牛奶桶牛奶 时间时间480小时小时甲设备至多加工甲设备至多加工100公斤公斤A1制订生产计划，使每天获利最大制订生产计划，使每天获利最大 每天：每天：线性规划模
3、型线性规划模型1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 x1桶牛奶生产桶牛奶生产A1x2桶牛奶生产桶牛奶生产A2获利获利243x1获利获利164 x2原料供应原料供应 劳动时间劳动时间 加工能力加工能力 决策变量决策变量 目标函数目标函数 每天获利每天获利约束条件约束条件非负约束非负约束 线性线性规划规划模型模型(LP)时间时间480小时小时 至多加工至多加工100公斤公斤A150桶牛奶桶牛奶每天每天模型求解模型求解 软件实现软件实现 LINGOmodel:max=72*x1+64*x2;milkx1+x250;time12*x1+8*x2480
4、;cpct3*x1100;end Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCost X120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.000000 20桶牛奶生产桶牛奶生产A1,30桶生产桶生产A2，利润，利润3360元元.如何如何装运，
5、装运，使本次飞行使本次飞行获利最大？获利最大？三个货舱三个货舱最大最大载载重重(t),(t),最大容积最大容积(m(m3 3)例例2 货机装运货机装运重量重量（t）体积体积(m3/t）利润利润（元（元/t）货物货物1184803100货物货物2156503800货物货物3235803500货物货物4123902850三个货舱中实际载重必须与其最大三个货舱中实际载重必须与其最大载载重成比例重成比例.前仓：前仓：10；6800中仓：中仓：16；8700后仓：后仓：8；5300飞机平衡飞机平衡WET=(10,16,8),VOL=(6800,8700,5300);w=(18,15,23,12),v=(
6、480,650,580,390),p=(3100,3800,3500,2850).已知参数已知参数 i=1,2,3,4（货物）（货物）j=1,2,3(分别代表前、中、后仓分别代表前、中、后仓)货舱货舱j的重量限制的重量限制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
8、xij-第第i 种货物装入第种货物装入第j 个货舱的重量个货舱的重量j,k=1,2,3;jk!定义集合及变量定义集合及变量;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
9、)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(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:12VariableValueReducedC
10、ostX(1,1)0.000000400.0000X(1,2)0.00000057.89474X(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,中仓
11、中仓1 13；货物货物4:中仓中仓3.货机装运货机装运模型求解模型求解 最大利润约最大利润约121516元元 如果生产某一类型汽车，则至少要生产如果生产某一类型汽车，则至少要生产8080辆，辆，那么最优的生产计划应作何改变？那么最优的生产计划应作何改变？例例1 汽车厂生产计划汽车厂生产计划 汽车厂生产三种类型的汽车，已知各类型每辆车对汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量钢材、劳动时间的需求，利润及工厂每月的现有量.小型小型中型中型大型大型现有量现有量钢材（钢材（t）1.535600劳动时间（劳动时间（h）28025040060000利润（万元
12、）利润（万元）234制订月生产计划，使工厂的利润最大制订月生产计划，使工厂的利润最大.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.0000Ex
13、tendedsolversteps:0Totalsolveriterations: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=610LINGO中中对对0-1变量的限定：变量的限定：bin(y1);bin(y2);bin(y3);方法方法2：引入引入0-1变量，化为整数规划变量，化为整数规划M为大的正数为大的正数,本例可取本例可取1000ObjectiveValue:610.0000VariableValueReducedCostX180.000000-2.000000X2150.000000-3.000000X30.000000-4.000000Y11.
15、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-LinearProgramming，简记简
16、记NLP）若生产某类汽车，则至少生产若生产某类汽车，则至少生产8080辆，求生产计划辆，求生产计划.x1=0 或 80 x2=0 或 80 x3=0 或 80最优解同前最优解同前.一般地，整数规划和非一般地，整数规划和非线性规划的求解比线性线性规划的求解比线性规划困难得多，特别是规划困难得多，特别是问题规模较大或者要求问题规模较大或者要求得到全局最优解时得到全局最优解时.汽车厂生产计划汽车厂生产计划 决策变量为整数决策变量为整数,建立建立整数规划模型整数规划模型.求解整数规划和非线性规划比线性规划求解整数规划和非线性规划比线性规划困难得多困难得多(即便用数学软件即便用数学软件).当整数变量取值
17、很大时当整数变量取值很大时,可作为连续变量可作为连续变量处理处理,问题问题简化为线性规划简化为线性规划.对于类似于对于类似于“x=0或或 80”这样的条件，通常这样的条件，通常引入引入0-1变量变量处理，尽量不用非线性规划（特处理，尽量不用非线性规划（特别是引入的整数变量个数较少时）别是引入的整数变量个数较少时）.应如何安排原油的采购和加工应如何安排原油的采购和加工？例例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%)决策决策变量变量 目标目标函数函数问题问题分析分析 利润：销售汽油的收入利润：销售汽油的收入 购买原油购买原油A的支出的支出.难点：原油难点：原油A的购价与购买量的关系较复杂的购价与购买量的关系较复杂.甲甲(A 50%)AB乙乙(A 60%)购买购买xx11x12x
19、21x224.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千千元元/t./t.目标目标函数函数购买购买x ABx11x12x21x22库存库存500t库存库存1000t目标函数中目标函数中c(x)不是线性函数，是非
20、线性规划；不是线性函数，是非线性规划；对于用分段函数定义的对于用分段函数定义的c(x)，一般的非线性规划软，一般的非线性规划软件也难以输入和求解；件也难以输入和求解；想办法将模型化简，用现成的软件求解想办法将模型化简，用现成的软件求解.汽油含原油汽油含原油A的比例限制的比例限制约束约束条件条件甲甲(A 50%)AB乙乙(A 60%)x11x12x21x22x1,x2,x3以价格以价格10,8,6(千元千元/t)t)采购采购A的吨数的吨数目标目标函数函数 只有当以只有当以10千元千元/t t的价格购买的价格购买x1=500(t)(t)时，才能以时，才能以8千千元元/t t的价格购买的价格购买x2
21、方法方法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=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
22、)*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)x1200090005000O50010001500b2 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).直接处理分段线性函数
23、直接处理分段线性函数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(x)x1200090005000O50010001500b1b2b3b4对于对于k=1,2,3方法方法3:直接处理分段线性函数，方法更具一般性直接处理分段线性函数，方法更具一般性.分段函数分段函数无法直接用非线性规划方法或软件求无法直接用非线性规划方法或软件求解解.原油采购与加工原油采
24、购与加工 方法方法1:增加约束化为增加约束化为非线性规划非线性规划,可以用可以用LINGO求解求解,但可能但可能得到的是局部最优解得到的是局部最优解.方法方法2:引入引入0-1变量变量,化为化为线性规划模型线性规划模型,可用可用LINGO求解求解.如何选拔队员组成如何选拔队员组成4 4 100100m混合泳接力队混合泳接力队?例例1 混合泳接力队的选拔混合泳接力队的选拔 5名候选人的名候选人的百米成绩百米成绩甲甲乙乙丙丙丁丁戊戊蝶泳蝶泳仰泳仰泳蛙泳蛙泳自由泳自由泳目标目标函数函数若选择队员若选择队员i参加泳姿参加泳姿j 的比赛，记的比赛，记xij=1,否则记否则记xij=0 0-1规划模型规划
25、模型 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人人 模型求解模型求解 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,5
26、3,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;);for(link:bin(x);END 混合泳接力队的选拔混合泳接力队的选拔指派指派(Assignment)问题问题：有若干项任务有若干项任务,每项任务必每项任务必有且只能有一人承担，每人只能承担一项有且只能有一人承担，每人只能承担一项，不同人员，不同人员承担不同任务的效益承担不同任务的效益(或成本或成本)不同，怎样分派各项任不同，怎样分派各项任务使总效益最大务使总效益最大(或总成本最小或总成本最小)?人员数量与任务数量相等人员数量与任务数量相等人员数量大于任务数量人员数量大于任务数量(本例本例)人员数量小于任务数量人员数量小于任务数量?建立建立0-1规划模型是常用方法规划模型是常用方法