《数学规划模型》PPT课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,数学规划模型,实际问题中,的优化模型,x,决策变量,f,(,x,)目标函数,g,i,(,x,),0,约束条件,决策变量个数,n,和,约束条件个数,m,较大,最优解在可行域,的边界上取得,数学规划,线性规划,非线性规划,整数规划,重点在模型的建立和结果的分析,优化模型的,简单分类,线性规划,(LP),目标和约束均为线性函数,非线性规划,(NLP),目标或约束中存在非线性函数,二次规划,(QP),目标为二次函数、约束为线性,整数规划,(IP),决策变量,(,全部或部分,),为整数,整数,线性,规划,(ILP),，整数,非线性,规划,(INLP),一般整数规划，,0-1,（整数）规划,连续优化,离散优化,数学规划,例1 加工奶制品的生产计划,获利24元/公斤,1桶牛奶,3公斤A,1,12小时,8小时,4公斤A,2,或,获利16元/公斤,50桶牛奶,时间480小时,甲设备至多加工100公斤A,1,制订生产计划，使每天获利最大,每天：,线性规划模型,1桶牛奶,3公斤A,1,12小时,8小时,4公斤A,2,或,获利24元/公斤,获利16元/公斤,x,1,桶牛奶生产A,1,x,2,桶牛奶生产A,2,获利 243,x,1,获利 164,x,2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型(LP),时间480小时,至多加工100公斤A,1,50桶牛奶,每天,模型求解,软件实现,LINGO,model:,max=72*x1+64*x2;,milk x1+x250;,time,12*x1+8*x2480;,cpct 3*x1100;,end,Global optimal solution found.,Objective value:3360.000,Total solver iterations:2,Variable Value,Reduced Cost,X1 20.00000,0.000000,X2 30.00000,0.000000,Row Slack or Surplus Dual Price,1 3360.000 1.000000,MILK 0.000000 48.00000,TIME 0.000000 2.000000,CPCT 40.00000 0.000000,20桶牛奶生产A,1,30桶生产A,2,，利润3360元.,如何,装运，使本次飞行获利最大？,三个货舱,最大,载,重(t),最大容积(m,3,),例2 货机装运,重量,（t）,体积,(m,3,/t）,利润,（元/t）,货物1,18,480,3100,货物2,15,650,3800,货物3,23,580,3500,货物4,12,390,2850,三个货舱中实际载重必须与其最大,载,重成比例.,前仓：,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,的重量限制,WET,j,体积限制,VOL,j,第,i,种货物的重量,w,i,，单位重量的体积,v,i,，利润,p,i,货机装运,决策变量,x,ij,-第,i,种货物装入第,j,个货舱的重量(t）,i,=1,2,3,4,j,=1,2,3(分别代表前、中、后仓),模型假设,每种货物可以分割到任意小；,货机装运,每种货物可以在一个或多个货舱中任意分布；,多种货物可以混装，并保证不留空隙；,所给出的数据都是精确的，没有误差.,模型建立,货舱容积,目标函数(,利润),约束条件,货机装运,模型建立,货舱重量,10；,6800,16；,8700,8；,5300,x,ij,-第,i,种货物装入第,j,个货舱的重量,约束条件,平衡要求,货物供应,货机装运,模型建立,10；,6800,16；,8700,8；,5300,x,ij,-第,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;,enddata,max=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(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程序,Global optimal solution found.,Objective value:121515.8,Total solver iterations:12,Variable Value Reduced Cost,X(1,1)0.000000 400.0000,X(1,2)0.000000 57.89474,X(1,3)0.000000 400.0000,X(2,1)7.000000 0.000000,X(2,2)0.000000 239.4737,X(2,3)8.000000 0.000000,X(3,1)3.000000 0.000000,X(3,2)12.94737 0.000000,X(3,3)0.000000 0.000000,X(4,1)0.000000 650.0000,X(4,2)3.052632 0.000000,X(4,3)0.000000 650.0000,货物,2,：前仓,7,后仓,8,；,货物,3,:前仓,3,中仓1,3,；,货物,4,:中仓,3,.,货机装运,模型求解,最大利润约,121516,元,如果生产某一类型汽车，则至少要生产,80,辆，那么最优的生产计划应作何改变？,例1 汽车厂生产计划,汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量.,小型 中型 大型 现有量,钢材（t）1.5 3 5 600,劳动时间（h）280 250 400 60000,利润（万元）2 3 4,制订月生产计划，使工厂的利润最大,.,4.3,汽车生产与原油采购,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*x3,60000;,gin(x1);gin(x2);gin(x3);,Global optimal solution found.,Objective value:632.0000,Extended solver steps:0,Total solver iterations:3,Variable Value Reduced Cost,X1 64.00000,-2.000000,X2 168.0000,-3.000000,X3 0.000000,-4.000000,IP 结果输出,设每月生产小、中、大型汽车的数量分别为,x,1,x,2,x,3,其中,3,个,子模型应,去掉，然后逐一求解，比较目标函数值，再加上整数约束，得最优解：,方法1：分解为8个LP子模型,汽车厂生产计划,若生产某类汽车，则至少生产,80,辆，求生产计划,.,x,1,x,2,x,3,=0 或,80,x,1,=80,，,x,2,=150,，,x,3,=0,，最优值,z,=610,LINGO中对0-1变量的限定：,bin(y1);bin(y2);bin(y3);,方法2：,引入,0-1,变量，化为整数规划,M,为大的正数,本例可取,1000,Objective Value: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,最优解同前,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-Linear Programming,，简记,NLP,）,若生产某类汽车，则至少生产,80,辆，求生产计划,.,x,1,=0,或,80,x,2,=0,或,80,x,3,=0,或,80,最优解同前.,一般地，整数规划和非线性规划的求解比线性规划困难得多，特别是问题规模较大或者要求得到全局最优解时.,汽车厂生产计划,决策变量为整数,建立,整数规划模型,.,求解整数规划和非线性规划比线性规划困难得多,(,即便用数学软件,).,当整数变量取值很大时,可作为连续变量处理,问题,简化为线性规划,.,对于类似于“,x,=0,或,80”,这样的条件，通常,引入,0-1,变量,处理，尽量不用非线性规划（特别是引入的整数变量个数较少时）,.,应如何安排原油的采购和加工,？,例2 原油采购与加工,市场上可买到不超过,1500,t的原油,A,：,购买量不超过,500,t,时的单价为,10000,元,/t,；,购买量超过,500,t,但不超过,1000,t,时，超过,500,t,的 部分,8000,元,/t,；,购买量超过,1000,t,时，超过,1000,t,的部分,6000,元,/t.,售价4800元/t,售价5600元/t,库存500t,库存1000t,汽油甲(A,50%),原油A,原油B,汽油乙(A,60%),决策变量,目标函数,问题分析,利润：销售汽油的收入,购买原油,A,的支出,.,难点：原油,A,的购价与购买量的关系较复杂,.,甲(A,50%),A,B,乙(A,60%),购买,x,x,11,x,12,x,21,x,22,4.8千元/t,5.6千元/t,原油,A,的购买量,原油,A,B生产,汽油,甲,乙的数量,c,(,x,),购买原油,A,的支出,利润(千元),c,(,x,)如何表述？,原油供应,约束条件,x,500,t,单价为,10,千,元,/t,；,500,t,x,1000,t,，超过,500,t,的,8,千,元,/t,；,1000,t,x,1500,t,，超过,1000,t,的,6,千,元,/t.,目标函数,购买,x,A,B,x,11,x,12,x,21,x,22,库存500t,库存1000t,目标函数中,c,(,x,),不是线性函数，是非线性规划；,对于用分段函数定义的,c,(,x,),，一般的非线性规划软件也难以输入和求解；,想办法将模型化简，用现成的软件求解,.,汽油含原油A的比例限制,约束条