基于LINGO的多目标规划模型求解

I基于LINGO的多目标规划模型求解唐家德（楚雄师范学院数学与统计学院，云南楚雄675000）摘要建立实际问题的多目标规划数学模型并求解是运筹学中常遇到的问题,应用最优化软件LINGO可以快捷准确地求出该类问题的解，本文以实例的方式介绍了多目标规划数学模型的建立、LINGO求解程序的编写，为实际工作者解决这类优化问题提供了一种便捷的途径。关键词多目标规划；LINGO；偏差变量；优先级.中图分类号O221.6文献标识码A0引言多目标规划是运筹学的一个重要内容,它研究在一定约束条件下多个目标函数的极值问题,与传统的单目标函数问题不同,在多目标规划问题中,通常不存在能使得所有目标函数同时得到优化的最优解,往往只需要求出满意解.求解多目标规划的方法主要有两类：第一类是化多为少的方法,即把多目标化为较容易求解的单目标问题进行求解,第二类是分级序列法,即把目标按其重要性给出一个优先级,每次在上一优先级目标的最优解集内求下一优先目标的最优解,直到求出共同的最优解，本文主要介绍第二种方法。下面我们以一个实例来说明多目标规划的特点、采用分级序列法求解的步骤和LINGO程序的编写。1一个实例（运输问题模型）要把一种产品从产地运到客户处,发量、需求量及产地到客户的运输费单价如表1所示.表1运输费用单价表客户1客户2客户3发量产地1104123000产地281034000需求量200015005000-客户产地22线性规划建模求解设从产地i（1,2i）到客户(1,2,3)jj的运送量为ijx，单位运输费用为ijc，产地i的发量为ie，客户j的需求量为jd，则可建立如下的线性规划模型：min2311ijijijzcx(1)s.t.21,1,2,3ijjixdj(2)31,1,2ijijxei(3)使用LINGO软件求解，发现无可行解。无可行解的原因是客户总需求量（8500）大于产地的总发量（7000），客户需求量无法满足。由于该问题是一个供求不平衡问题,总需求量缺少1500个单位,因此按下列目标来考虑运输方案：第一目标,客户1为重要部门,需求量必须全部满足;第二目标,满足其他两个客户至少75%的需要量;第三目标,使运费尽量少;第四目标,从产地2到客户1的运量至少有1000个单位.3采用分级序列法对多目标规划求解[13]3．1确定目标的优先级与权系数首先确定目标的优先级与权系数，目标的优先分为两个层次,第一个层次是目标分成不同的优先级,在计算多目标规划时,必须先优化高优先级的目标,然后再优化低优先级的目标,通常以12,,,kPPP表示不同的优先级,并规定kkpp1,在上述实例中，有四个目标，按重要性分为第一至第四目标，我们分别记这四个目标的优先级为1234,,,PPPP。第二个层次是目标处于同一优先级,但两个目标的权重不一样,因此两目标同时优化,用权系数w的大小来表示目标重要性的差别.3．2统一处理目标与约束其次将原线性规划的目标函数和约束条件都统一视为约束条件，然后将约束分成两类，一类是严格要求满足的，用严格的等式或不等式约束来处理，例如，上述例子中，对各产地发量的约束是要求严格满足的，这类约束称为刚性约束：31,1,2ijijxei(刚性约束)另一类约束是可以不严格要求满足的,称为柔性约束,对于柔性约束,我们通过设置偏差变量的方法将其转化为等式约束.33.3偏差变量的设置方法用偏差变量来表示计算值()ifx与目标值^()ifx之间的差异,若)()(^xfxfii,则令)()(^xfxfdiii,0id,即id为)(xfi超过)(^xfi部分的数量,故称id为正偏差变量;若)()(^xfxfii时,令)()(^xfxfdiii,0id,即id为)(xfi没有达到)(^xfi部分的数量,故称id为负偏差变量.若^()()iifxfx,则0iidd在实际问题中,对于计算值)(xfi来说,如果希望)(xfi尽量超过目标值)(^xfi,则极小化负偏差变量,即minid;希望)(xfi尽量不超过)(^xfi,则极小化正偏差变量,即minid;希望)(xfi尽可能地接近)(^xfi,则同时极小化正、负偏差变量，即miniidd;在上述实例中，四个目标可视为四个柔性约束，分别写为：（1）客户1为重要部门需求量必须全部满足,即：1112111min{}2000dxxdd;（2）满足客户2和客户3至少75%的需要量,即：37501125}min{33231322221232ddxxddxxdd;（3）使运费尽量少,即：4234411min{}33000ijijijdcxdd（4）从产地2到客户1的运输量至少有1000个单位,即：52155min{}1000dxdd;根据上面的陈述,可以写出相应的目标函数为：min112233445()ZPdPddPdPd,其中4321,,,PPPP均为优先级.4LINGO软件求解将上述内容编写为以下LINGO程序：sets:Level/1..4/:P,z,Goal;!定义优先级集合及其属性;S_Con_Num/1..5/:dplus,dminus;!定义柔性约束集合及正负偏差变量;Plant/1,2/:e;!定义产地集合及发量;Customer/1..3/:d;!定义客户集合及需求量;4Routes(Plant,Customer):c,x;!生成产地与客户的派生集及单位运价和运输量;endsetsdata:P=????;!分级运算，等待用户输入;Goal=???0;!分级运算，用户根据上一级运算结果输入;e=30004000;!产地发量数据;d=200015005000;!客户需求量数据;c=104128103;!各产地到各客户单位运价数据;enddatamin=@sum(Level:P*z);!目标函数;z(1)=dminus(1);z(2)=dminus(2)+dminus(3);z(3)=dplus(4);z(4)=dminus(5);!各优先级优化的目标;@for(Plant(i):@sum(Customer(j):x(i,j))=e(i));!产量约束为刚性约束;x(1,1)+x(2,1)+dminus(1)-dplus(1)=2000;!第一目标约束为柔性约束;@for(Customer(j)|j#gt#1:@sum(Plant(i):x(i,j))+dminus(j)-dplus(j)=0.75*d(j););!第二目标约束;@sum(Routes:c*x)+dminus(4)-dplus(4)=33000;!第三目标约束;x(2,1)+dminus(5)-dplus(5)=1000;!第四目标约束;@for(Level(i)|i#lt#@size(Level):@bnd(0,z(i),Goal(i)););!人为增加上下界约束;现将上述程序分别执行四次,在做第一级目标计算时,4321,,,PPPP分别输入1,0,0,0;(1),(2),(3)GoalGoalGoal分别输入10000,10000,10000,执行solve得到0)1(Goal.在做第二级目标运算时,4321,,,PPPP分别输入0,1,0,0;(1),(2),(3)GoalGoalGoal分别输入0,10000,10000,执行solve得到0)2(Goal.在做第三级目标运算时,4321,,,PPPP分别输入0,0,1,0,5(1),(2),(3)GoalGoalGoal分别输入0,0,10000,执行solve得到2250)3(Goal.在做第四级目标运算时,4321,,,PPPP分别输入0,0,0,1;(1),(2),(3)GoalGoalGoal分别输入0,0,2250,执行solve得到750)4(Goal.通过四次运算我们得到上述问题的部分输出结果：X(1,1)1750.0000.000000X(1,2)1125.0000.000000X(1,3)0.0000000.000000X(2,1)250.00000.000000X(2,2)0.0000002.142857X(2,3)3750.0000.000000根据结果我们可以知道从产地1运往3个客户的运输量分别为：1750,1125,0,从产地2运往3个客户的运输量分别为：250,0,3750.此结果满足四个目标约束,则此运输方案为满意解,故最小运输费用为:元35250375030102508012112541750105小结采用分级序列法，多目标规划的一般数学表达式也可以记为：[46]1111min()(,),1,2,...,,1,2,...,..0,1,2,...,,0,1,2,...,qlkkjjkjjkjnijjijnijjjjijjiizPwdwdaxbippqcxddgiqstxjnddil目标函数刚性约束柔性约束（4）将所有柔性约束（等式或不等式）加上负偏差变量与正偏差变量的差后变为等式约束，如果希望约束保持小于，则极小化正偏差变量，如果希望约束保持大于，则极小化负偏差变量，如果希望约束保持等于，则极小化正、负偏差变量之和。采用分级序列法再结合LINGO软件，可以高效准确地求出多目标规划问题，这种求解方法具有普遍的实践意义,适合解决常规的多目标规划的数学模型.由于多目标规划还有很多方面的应用,如林产品的加工中各种原材料的最佳配比、木材最优运输路线的选择、造林的最佳投资方案选择、水资源的最优配置、抚育采伐的最优控制、产品生产的安6排、投资方案选择等,都可以用多目标数学规划的方法加以解决.目前,多目标数学规划的理论,求解方法都处于迅速发展阶段,并且在生产、经济、科学、工程等诸多领域中都处于重要的地位,例如设计一个导弹,既要其射程远,又要耗料少,还要命中率高等,只有对各因素的指标进行综合衡量后,才能做出合理的决策.相信,在不久的将来多多目标规划问题将会在实践中得到广泛地应用,理论也会随之不断地完善,计算技术也会更为简便,在理论与实践的结合上将会有广阔的发展前景.参考文献：[1]谢金星,薛毅.优化建模与LINGO软件[M].北京：清华大学出版社,2005.[2]徐玖平,李军.多目标决策的理论与方法[M].北京：清华大学出版社,2005.3.[3]徐玖平,胡智能,李军.运筹学（Ⅱ类）[M].北京：科学出版社,2004.[4]李华.预测与决策[M].西安：电子科技大学出版社,2005.3.1.[5]王丽颖,赵连丽,赵连忠.多目标规划模型的应用研究[J].白城师范学院学报,2010,24（6）：7-15.[6]刘淋.多目标线性规划的若干解法及Lingo实现[J].襄樊职业技术学院报,2011,10（6）：20-22.[7]郑漳华，艾芊，顾承红，蒋传文.考虑环境因素的分布式发电多目标优化配置[J].中国电机工程学报,2009,29（13）：23-29.[8]乔辰；张国立.几何加权法求解多目标规划问题[J].华北电力大学学报(自然科学版),2011,38（6）：107-110.[10]刘杨，云美萍，彭国雄.应急车辆出行前救援路径选择的多目标规划模型[J].公路交通科技,2009,26（8）：135-139.[11]何其超，胡列格，钱红波.基于多目标规划的低碳销售物流网络规划方法[J].系统工程,2013,31（7）：20-22.[12]刘淋.多目标线性规划的若干解法及Lingo实现[J].襄樊职业技术学院报,2011,10（6）：20-22.TheSolvingofTheMultiobjectiveProgrammingBasedonLINGOTangJia-de(DepartmentofMathema