01数学规划建模

数学建模华中农业大学数学建模基地系列课件最优化问题的数学模型的一般形式为：xfzoptskjiRDxnkxtmjxglixhts,,1,0,,1,0,,1,0..（1）（2）三个要素：决策变量decisionbariable，目标函数objectivefunction，约束条件constraints。（2）所确定的x的范围称为可行域feasibleregion，满足（2）的解x称为可行解feasiblesolution，同时满足（1）（2）的解x称为最优解Optimalsolution，整个可行域上的最优解称为全局最优解globaloptimalsolution，可行域中某个领域上的最优解称为局部最优解localoptimalsolution。最优解所对应的目标函数值称为最优值optimum。优化模型的分类（一）按有无约束条件（2）可分为：1.无约束优化unconstrainedoptimization。2.约束优化constrainedoptimization。大部分实际问题都是约束优化问题。（二）按决策变量取值是否连续可分为：1.数学规划或连续优化。可继续划分为线性规划(LP)Linearprogramming和非线性规划(NLP)Nonlinearprogramming。在非线性规划中有一种规划叫做二次规划(QP)Quadraticprogramming，目标为二次函数，约束为线性函数。2.离散优化或组合优化。包含：整数规划(IP)Integerprogramming，整数规划中又包含很重要的一类规划：0-1（整数）规划Zero-oneprogramming，这类规划问题的决策变量只取0或者1。（三）按目标的多少可分为：1.单目标规划。2.多目标规划。（四）按模型中参数和变量是否具有不确定性可分为：1.确定性规划。2.不确定性规划。（五）按问题求解的特性可分为：1.目标规划。2.动态规划。3.多层规划。4.网络优化。5.……等等。优化问题求解常用的软件LINGO软件和MATLAB软件。对于LINGO软件，线性优化求解程序通常使用单纯形法simplexmethod，单纯形法虽然在实际应用中是最好最有效的方法，但对某些问题具有指数阶的复杂性，为了能解大规模问题，也提供了内点算法interiorpointmethod备选（LINGO中一般称为障碍法，即barrier），非线性优化求解程序采用的是顺序线性规划法，也可用顺序二次规划法，广义既约梯度法，另外可以使用多初始点（LINGO中称multistart）找多个局部最优解增加找全局最优解的可能，还具有全局求解程序—分解原问题成一系列的凸规划。软件介绍例1帆船生产计划SAILCO公司需要决定下四个季度的帆船生产量。下四个季度的帆船需求量分别是40条，60条，75条，25条，这些需求必须按时满足。每个季度正常的生产能力是40条帆船，每条船的生产费用为400美元。如果加班生产，每条船的生产费用为450美元。每个季度末，每条船的库存费用为20美元。假定生产提前期为0，初始库存为10条船。如何安排生产可使总费用最小？分析:DEM－需求量，RP－正常生产的产量，OP－加班生产的产量，INV－库存量，则DEM,RP,OP,INV对每个季度都应该有一个对应的值，也就说他们都应该是一个由4个元素组成的数组，其中DEM是已知的，而RP,OP,INV是未知数。目标函数：正常生产费＋加班生产费＋储存费最小4,3,2,1)}(20)(450)(400{MINIIINVIOPIRP约束条件：1）能力限制：4,3,2,1,40)(RPII2）产品数量的平衡方程：4,3,2,1),()()()1()(IIDEMIOPIRPIINVIINV10)0(INV4）变量非负3）初始库存：－引例－模型建立记四个季度组成的集合QUARTERS={1，2，3，4}，它们就是上面数组的下标集合，而数组DEM,RP,OP,INV对集合QUARTERS中的每个元素1，2，3，4分别对应于一个值。LINGO正是充分利用了这种数组及其下标的关系，引入了“集合”及其“属性”的概念，把QUARTERS={1，2，3，4}称为集合，把DEM,RP,OP,INV称为该集合的属性(即定义在该集合上的属性)。－集合与属性－•QUARTERS集合的属性DEMRPOPINV•QUARTERS集合2341－集合与属性－集合元素及集合的属性确定的所有变量集合QUARTERS的元素1234定义在集合QUARTERS上的属性DEMDEM(1)DEM(2)DEM(3)DEM(4)RPRP(1)RP(2)RP(3)RP(4)OPOP(1)OP(2)OP(3)OP(4)INVINV(1)INV(2)INV(3)INV(4)－集合与属性－－程序编写－MODEL:!集合段：定义集合SET，元素member及其属性attribute；SETS:QUARTERS/1,2,3,4/:DEM,RP,OP,INV;ENDSETS!目标与约束段：没有开始和结束标记，顺序无关；MIN=@SUM(QUARTERS(I):400*RP(I)+450*OP(I)+20*INV(I));@FOR(QUARTERS(I):RP(I)40);@FOR(QUARTERS(I)|I#GT#1:INV(I)=INV(I-1)+RP(I)+OP(I)-DEM(I););INV(1)=10+RP(1)+OP(1)-DEM(1);!数据段：对集合的属性输入必要的常数数据；DATA:DEM=40,60,75,25;ENDDATAEND或1..4或用空格或回车隔开，“属性＝常数列表”对“：”前的每个元素求和或循环遍历下标元素，可省略下标“︱”后是过滤条件，逻辑关系式I1（greaterthan）－展开式－LINGO︱Generate︱DisplyModel(Ctrl+G)MIN=@SUM(QUARTERS(I):400*RP(I)+450*OP(I)+20*INV(I));@FOR(QUARTERS(I):RP(I)40);@FOR(QUARTERS(I)|I#GT#1:INV(I)=INV(I-1)+RP(I)+OP(I)-DEM(I););INV(1)=10+RP(1)+OP(1)-DEM(1);全局最优解RP=(40,40,40,25)OP=(0,10,35,0)最小成本=78450自动生成行号－结果报告－例2运输问题241230A282412A1B3B2B1粮库粮站距离。问如何调运使运费最低如下公里单位距离两个粮库到三个粮站的吨大米分别为三个粮站至少需要吨吨为两个粮库现存大米分别调运大米向三个粮站有两个粮库,):(,5,4,2,8,4,,,,32121BBBAA解：设A1,A2调运到三个粮站的大米分别为x11，x12，x13，x21，x22，x23吨。题设量可总到下表：84库存量x23x22x21A2542需要量x13x12x11A1B3B2B112122430824结合存量限制和需量限制得数学模型：23222113121124123082412xxxxxxfmin054284232221131211231322122111232221131211xxxxxxxxxxxxxxxxxxts,,,,,..程序编写推荐MODEL:TITLE调运大米的运输问题程序４;!定义集合段;SETS:LIANGKU/1..2/:A;!定义粮库的集合;LIANGZHAN/1..3/:B;!定义粮站的集合;YULIANG(LIANGKU,LIANGZHAN):X,C;!定义运量和距离;ENDSETSDATA:!粮库到粮站的距离;C=12248301224;!粮库的限量;A=48;!粮站的限量;B=245;ENDDATA[OBJ]MIN=@SUM(YULIANG:C*X);!粮库上限的约束;@FOR(LIANGKU(I):[LK]@SUM(LIANGZHAN(J):X(I,J))A(I));!粮站下限的约束;@FOR(LIANGZHAN(J):[LZ]@SUM(LIANGKU(I):X(I,J))B(J));END程序的调试1.直接点击运行，如果出错会弹出错误提示，根据提示做相应的修改；2.可以用“！”把约束变成说明语句，而把这条语句屏蔽掉，缩小寻找出错的范围；3.可以边写程序边运行，保证每行书写都是正确的程序；料场的建立与运输建筑工地的位置(用平面坐标a,b表示，距离单位：公里)及水泥日用量d(吨)下表给出。有两个临时料场位于P(5,1),Q(2,7),日储量各有20吨。(1)从A,B两料场分别向各工地运送多少吨水泥，使总的吨公里数最小。(2)两个新的料场应建在何处，节省的吨公里数有多大？１２３４５６a1.258.750.55.7537.25b1.250.754.7556.57.75d3547611非线性规划－引例－2622112161MIN1s.t.,1,2,,62,1,23ijjijijiijijijjifcxayacdicejb),(iiba已知为LP模型，未知为NLP模型－引例－模型建立料场向工地的运送量为：),(iiba6,1,idi),(jjyx2,1,jejijc工地：位置水泥日用量：料场：位置日储量：利用集合的概念，可以定义需求点DEMAND和供应点SUPPLY两个集合，分别有6个和2个元素(下标)。但决策变量(运送量)cij与集合DEMAND和集合SUPPLY都有关系的。该如何定义这样的属性？集合的属性相当于以集合的元素为下标的数组。这里的cij相当于二维数组。它的两个下标分别来自集合DEMAND和SUPPLY，因此可以定义一个由二元对组成的新的集合，然后将cij定义成这个新集合的属性，这个集合称为派生集合。－派生集合－－程序编写－MODEL:TitleLocationProblem;sets:demand/1..6/:a,b,d;supply/1..2/:x,y,e;link(demand,supply):c;endsetsdata:!locationsforthedemand(需求点的位置);a=1.25,8.75,0.5,5.75,3,7.25;b=1.25,0.75,4.75,5,6.5,7.75;!quantitiesofthedemandandsupply（供需量）;d=3,5,4,7,6,11;e=20,20;enddata……基本集合primaryset与派生集合derivedset（定义多维数组）－程序编写－……!初始段：对集合属性定义初值（迭代算法的迭代初值）;init:!initiallocationsforthesupply（初始点）;x,y=5,1,2,7;endinit!Objectivefunction（目标）;[OBJ]min=@sum(link(i,j):c(i,j)*((x(j)-a(i))^2+(y(j)-b(i))^2)^(1/2));!demandconstraints（需求约束）;@for(demand(i):[DEMAND_CON]@sum(supply(j):c(i,j))=d(i););!supplyconstraints（供应约束）;@for(supply(i):[SUPPLY_CON]@sum(demand(j):c(j,i))=e(i););@for(supply:@bnd(0.5,X,8.75);@bnd(0.75,Y,7.75););ENDLINGO对数值顺序按列赋值，即：x=5,2;y=1,7;标号自动在后加下标*_1,_2…比@free(x);@free(y);要好，可减少计算工作量－求解观察－激活全局最优解：LINGO︱Options→GlobalSolver︱UseGlobalSolver－结果报告－0