Matlab学习系列27多目标规划

27.多目标规划一、线性规划的局限性1.线性规划要求所求解问题必须满足全部的约束，而实际问题中并非所有约束都需要严格的满足；2.线性规划只能处理单目标的优化问题，从而对一些次目标只能转化为约束处理，而实际问题中，目标和约束是可以相互转化的，处理时不一定要严格区分；3.线性规划在处理问题时，将各个约束（也可看成目标）的地位看成同等重要，实际问题中，各个目标的重要性有层次上的差别，在同一层次也可能有不同权重；4.线性规划寻找最优解，而许多实际问题只要找到满意解就可以了。例1(线性规划——生产安排问题)某企业生产甲、乙两种产品，需要用到A,B,C三种设备，每天产品盈利与设备使用工时及限制如下表：甲乙设备生产能力/hA/(h/件)2212B/(h/件)4016C/(h/件)0515盈利/(元/件)200300问：该企业应如何安排生产，能使总利润最大？解：设甲乙产品的产量分别为x1,x2，建立线性规划模型：12121212max200300s.t.2212416515,0zxxxxxxxx用Lingo可求得最优解：x1=3,x2=3,z*=1500.但实际上，企业的经营目标不仅仅是利润，还需要考虑多个方面，比如：增加下列因素（目标）（1）力求使利润不低于1500元；（2）考虑市场需求，甲乙两种产品的产量比应尽量保持1:2；（3）设备A位贵重设备，严格禁止超时使用；（4）设备C可以适当加班，但要控制，设备B既要求充分利用，又尽可能不加班，在重要性上，设备B是设备C的3倍。这就需要用目标规划。二、目标规划的基本概念1.设置偏差变量偏差变量——表示实际值与目标值之间的差异；d+——表示超出目标的差值，称为正偏差变量；当实际值超过目标值时，有d-=0，d+0;d-——表示未达到目标的差值，称为负偏差变量；当实际值未达到目标值时，有d+=0，d-0.注：若实际值与目标值一致，有d-=d+=0.2.统一处理目标与约束目标规划中，约束有两类，一类是对资源有严格限制的，用严格的等式或不等式约束来处理（同线性规划），例如，例1中设备A禁止超时使用，则有刚性约束：122212xx另一类约束是可以不严格限制的，连同原线性规划的目标，构成柔性约束，例如，例1中希望利润不低于1500元，则目标可表示为12min{}2003001500dxxdd甲乙两种产品产量尽量保持1:2的比例，则目标可表示为12min{}20ddxxdd设备C可以适当加班，但要控制，则目标可表示为2min{}515dxdd设备B要求充分利用，又尽可能不加班，则目标可表示为1min{}416ddxdd结论：若希望不等式保持大于等于，则极小化负偏差；若希望不等式保持小于等于，则极小化正偏差；若希望保持等式，则同时极小化正负偏差。3.目标的优先级与权系数目标规划中，目标的优先分为两个层面，第一个层面是目标分成不同的优先级，在求解目标规划时，必须先优化优先级高的目标，再优化优先级低的目标；通常用P1,P2,…表示不同的因子，并规定PkPk+1.第二个层面是目标处于同一优先级，但两个目标的权重不同，此时应两目标同时优化，但用权重系数的大小来表示目标重要性的差别。目标规划建模中，除刚性约束必须严格满足外，对所有目标约束均允许有偏差。其求解过程要从高到低逐层优化，中不增加高层次目标的偏差值的情况下，逐次使低层次的偏差达到极小。例1按目标规划的方法可建立如下目标规划模型：设备A是刚性约束，其余是柔性约束；首先，最重要的指标是企业的利润，故将其优先级列为第一级；其次，甲乙两种产品的产量保持1:2的比例，列为第二级；再次，设备C，B的工作时间要有所控制，列为第三级。中第三级中，设备B的重要性是设备C的3倍，因此其权重不一样，设备B前的系数是C前系数的3倍，于是得到：1122233341212111222133244min()(33)s.t.2212200300150020416515zPdPddPdddxxxxddxxddxddxdd12,,,0,1,2,3,4iixxddi三、目标规划模型的一般形式：设,1,,jxjn是目标规划的决策变量，共有m个刚性约束（等式或不等式约束），有l个柔性目标约束，其目标规划约束的偏差为,,1,,jjddjl，有个q优先级别，分别为1,,qPP，在同一个优先级kP中有不同的权重，分别记为,,1,...,kjkjwwjl，则目标规划模型的一般形式为：1111min()s.t.(,),1,,(),1,,()0,qlkkjjkjjkjnijjijnijjiiijjzPwdwdaxbimcxddgilx刚性约束柔性约束1,,,0,1,,iijnddil注：建立目标规划模型时，需要确定目标值、优先等级、权系数等，这些具有一定的主观性和模糊性，可以用专家评定法予以量化。序贯式算法是求解目标规划的一种早期算法，其核心是根据优先级的先后次序，将目标规划问题分解成一系列的单目标规划问题，然后再依次求解。~jxie/lindo例1模型的求解：Lingo代码：附录：Lingo语法（二）以料场选址问题为例：建筑工地的位置用平面坐标a,b表示（距离单位km）；水泥日用量（单位t）由下表给出：表工地的位置(a,b)及水泥日用量123456a1.258.750.55.7537.25b1.250.754.7556.57.75d3547611目前想设置两个临时料场,日储量各有20t，问两个料场选址在何处，分别向各工地运送多少吨水泥，能使总的吨公里数最小？求解：记工地的位置为(ai,bi),水泥的日用量为di,i=1,…,6;料场位置为(xi,yi),日储量为ej,j=1,2;从料场j向工地i的运送量为cij,则该问题的数学规划模型为：2622112161min()()s.t.,1,,6,1,2ijjijijiijijijjifcxaybcdicejLingo代码：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;enddatainit:!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));!demandconstrains(需求约束);@for(demand(i):[DEMAND_CON]@sum(supply(j):c(i,j))=d(i););!supplyconstrains(供应约束);@for(supply(j):[SUPPLY_CON]@sum(demand(i):c(i,j))=e(j););@for(supply:@free(x);@free(y););ENDLingo程序的一般结构：程序是以MODEL:开始，以END结束。主体通常分为5个部分：(1)集合段；(2)数据段；(3)初始段；(4)计算段；(5)目标与约束段。一、集合段以“SET:”开始，以“ENDSET”结束；用来定义必要的集合变量及元素、属性，相当于数组。sets:demand/1..6/:a,b,d;supply/1,2/:x,y,e;link(demand,supply):c;endsets表示集合1名称为demand，元素为1…6，即demand={1,2,3,4,5,6}，该集合的属性有a,b,d“集合的属性相当于以集合的元素为下标的数组”即相当于demand定义了如下数组的：a(1),a(2),a(3),a(4),a(5),a(6)b(1),b(2),b(3),b(4),b(5),b(6)d(1),d(2),d(3),d(4),d(5),d(6)类似地，supply定义了如下数组x(1),x(2),y(1),y(2),e(1),e(2)注1：1,2,3,4可简写为1..4；注2：若无属性列表，则该集合往往是作为循环变量来使用，或用来构造派生集合；注3：若无元素列表，则必须在程序的数据段以赋值语句方式给出元素列表。派生集合：为了处理有两个下标的数组，引入派生集合：link(demand,supply):c;表示link={(s,t):s∈demand,t∈supply}，即笛卡尔积；其属性c则为6×2矩阵（二维数组）：c(1,1),c(1,2)c(2,1),c(2,2)c(3,1),c(3,2)c(4,1),c(4,2)c(5,1),c(5,2)c(6,1),c(6,2)注：demand和supply称为link的父集合。二、数据段以“DATA:”开始，以“ENDDATA”结束；用来对集合的属性（数组）输入必要的常数数据。data:a=1.25,8.75,0.5,5.75,3,7.25;b=1.25,0.75,4.75,5,6.5,7.75;d=3,5,4,7,6,11;e=20,20;enddata对集合的属性输入必要的常数数据，赋值结果为：a(1)=1.25,a(2)=8.75,……,a(6)=7.25b(1)=1.25,b(2)=0.75,……,b(6)=7.75d(1)=3,d(2)=5,……,d(6)=11e(1)=20,e(2)=20若需要在运行时才对单变量（不能是属性变量，数组）参数赋值，可以在数据段使用输入语句：例如A=?;在求解时，Lingo将给出提示界面，等待用户输入变量A的数值。三、初始段以“INIT:”开始，以“ENDINIT”结束；用来对集合的属性（数组）定义初始值，一般作为迭代用。init:x,y=5,1,2,7;endinit这里与数据段的赋值一样。注意：变量x,y一起赋值时的赋值顺序，相当于x(1)=5,y(1)=1,x(2)=2,y(2)=7同“x=5,2;y=1,7;”四、计算段以“CALC:”开始，以“ENDCALC”结束；用来对原始数据进行计算处理。例如，CALC:T_d=@SUM(demand:d);!总日用量;A_d=T_d/@size(demand);!平均日用量;ENDCALC其中，函数@size(demand)返回demand的元素个数。五、目标和约束段除上述四段之外的部分，无开始、结束标志；是模型的主体，用来定义目标函数和约束条件。1.目标函数：262211min()()ijjijijifcxayb[OBJ]min=sum(link(i,j):c(i,j)*((x(j)-a(i))^2+(y(j)-b(i))^2)^(1/2));@sum函数，派生集合（二维数组）link关于索引i，j对表达式求和；2.约束条件1：21,1,,6ijijcdi@for(demand(i):[DEMAND_CON]@sum(supply(j):c(i,j))=d(i););@for函数，对集合demand的每个索引i，应用求和表达式，集合supply关于索引j对表达式求和；约束条件2：61,1,2ijjicej@for(supply(j):[SUPPLY_CON]@sum(demand(i):c(i,j))