第九讲多目标规划

目标规划与多目标规划一、目标规划问题及其数学模型例1某工厂生产两种产品，受到原材料和设备工时的限制，在单位利润等有关数据已知的条件下，要求制订一个获利最大的生产计划。具体数据见表4-1产品III限量原材料(kg)51060设备工时(h)4440利润($/件)68表4-1解设产品I和II产量分别为x1和x2，建立线性规划模型，李容单纯形法求解得到x1=8,x2=2，最大获利为64元。

作为线性规划的例1，看起来已经圆满解决。但是，作为实际问题，就有几个方面值得进一步考虑：（1）目标函数的选择的单一化：一般来说，作为一个生产计划，需要满足多方面的要求。例如，财务部门希望利润最大化；行政部门希望规模最大化；物资部门则希望物资消耗最小化；销售部门希望产品多样化以适应市场销售，降低销售风险；计划部门产品批量尽可能大，便于安排生产等等。而这些目标有些是一致的，有些则是相互矛盾的，不可调和的。需要用数学模型来解决问题，怎么办呢？

这时，有两种方法可用，一是从总多矛盾的目标中，找出主要目标，忽略与之矛盾的其它目标。这样考虑的决策者，就是要建立单目标模型。二是协调众多目标，通过相互妥协达成可行的多目标规规划。（2）在实际问题中，各类约束不一定相容。也就是说，建立的线性规划模型不一定有可行解(或者说可行域可能是空集)。（3）在用数学方法解决实际问题时，只是强调数学模型与实际问题的相似性。而并非完全一致，一旦实际问题发生变化，则模型得到的可行解或最优解就面临着不能实施的可能。

严格意义上讲，数学模型相对于实际问题，都是实际问题“刚性”的本质的抽象。线性规划也一样，由其“刚性”注定了其局限性。现代决策者强调定性和定量分析相结合，强调硬技术和软技术的结合，强调矛盾和冲突的合理性，强调妥协和让步的必要性。所以线性规划就不具备这样的分析能力。1961年，查恩斯(A.Charnes)和库伯(W.W.Cooper)提出目标规划(goalprogramming)，就是弥补了上述线性规划局限性。目标规划在处理实际问题时，承认各决策要求(即变冲突的）的合理性；在作最终决策时，不强调绝对意义上的最优性。因此目标规划是更接近于实际决策过程的决策工具。2目标规划的模型例2在上述例1的基础上，计划人员还要求考虑如下意见：（1）由于产品II销售疲软，故希望产品II的产量不超过产品I产量的一半；（2）原材料严重短缺，生产中应避免过量消耗；（3）最好能够节约4小时设备工时；（4）计划利润不少于48元。分析：把这四条意见分别看成营销部门、材料部门、设备管理部门、财务部门四个部门的目标愿望。那么在决策的时候，如何协调者四个部门的意愿呢。同等对待每个目标意愿，势必陷于矛盾中。故当务之急是确定四个目标的重要程度或轻重缓急。然后根据重要程度逐一协调。下面引入一些新的变量来解决问题。1优先因子和权系数不同目标的主次轻重有两种差别：一种差别是绝对的，可用优先因子PL来表示，只有在高级优先因子对应的目标已满足的基础上，才能考虑较低级优先因子所对应的目标；在考虑低级优先因子对应的目标时，绝不允许违背已满足的高级优先因子对应的目标。因此，优先因子的关系为PL>>PL+1,即PL对应的目标比PL+1对应的目标有绝对的优先性。另外一种差别是相对的，这些目标具有相同的优先因子，它们的重要程度可用权系数的不同来表示。

在给出点四个部门的目标中，计划人员根据部门提出目标的口气以及在生产中的实际地位来确定，决策者必须让不同部门都参与确定优先因子，达成一致后方可做下一步。例2的协调结果是：P1原材料使用限量不得突破；P2产品II产量优先考虑；P3设备工时其次考虑；P4最后考虑计划利润的要求。

P1>>P2>>P3>>P4.2

列出每个部门的目标愿望分为决策值和目标值。决策值依赖于问题的决策变量，使决策变量的表达式，目标值是该决策值的一个愿望参考值。比如，设决策者决定生产产品Ix1件，产品IIx2件。则四个部门的目标决策值和目标值分别为部门目标决策值f目标值f*优先级别P营销部门X2-x1/20P2材料部门5x1+10x260P1设备管理4x1+4x240-4=36P3财务部门6x1+8x248P43偏差变量

对每一个决策目标，引入正负偏差变量d+和d-，分别表示决策值与目标值的偏差，d+表示决策值超过目标值部分，d-表示决策值不足目标值部分。显然，根据定义，有那么，例2的四个目标的决策值和目标值的偏差表达为4各个目标的欲望表达

任何一个部门在表达自己的意见时，总是用某种语气表达目标决策值和目标值之间的某种比较欲望。归纳起来，不外乎下面三种：（1）要求决策值不超过目标值min{d+}

或min{f(d+)}（2）要求决策值不低于目标值min{d-}或min{f(d-)}（3）要求决策值恰好达到目标值min{d-+d+}或min{f(d-+d+)}根据上面的定义，例2的四个部门的欲望可以表达为材料部门：mind1+

营销部门：mind2+设备部门：mind3+财务部门：mind4-

对于材料部门，基于语气的强硬，也可以把材料部门的欲望改为d1+=0。这样的话这个约束就由可以商量（称为软约束）转化为没有商量的余地（称为硬约束），并不改变问题的性质。根据上面引入的概念和分析，例2的规划模型为

在建立目标规划模型时，尽可能利用各种决策技术，尽量减少主观性和片面性。目标规划的一般形式硬约束软约束例2多目标供给问题

已知三个工厂生产的产品供应给四个用户，各工厂生产量、用户需求量及从各个工厂到用户的单位产品的运输费用如表4-2所示。由于总生产量小于总需求量，上级部门经研究决定，制定了调配方案的8项指标，并规定了重要性的次序。表4-2用户1234生产量工厂1工厂2工厂3需求量534200255100642450763250300200400第一目标：用户4为重要部门，需求量必须全部满足；第二目标：供应用户1的产品中，工厂3的产品不少于100个单位；第三目标：每个用户的满足率不低于80%；第四目标：应尽量满足个用户的要求；第五目标：新方案的总运费不超过原运输问题的总运费的10%；第六目标：因道路问题，工厂2到用户4的路线尽量避免运输；第七目标：用户1和用户3的满足率应尽量保持平衡；第八目标：力求减少总运费；请列出相应的目标规划模型，并用Lingo求解。解设从工厂i向用户j调运产品量为xij,i=1,2,3;j=1,2,3,4;Cij表示从工厂i向用户j调运的单位产品的费用；ai表示工厂i的产量；i=1,2,3;bj表示用户j的需求量，j=1,2,3,4;

由于目标5中需要用到不考虑任何目标的调运方案下的最小费用，故需要先求解如下线性规划模型s.t.上述模型的求解程序及结果为sets:gch/1..3/:a;yhu/1..4/:b;link(gch,yhu):x,c;endsetsmin=@sum(link:c*x);@for(gch(i):@sum(yhu(j):x(i,j))=a(i));@for(yhu(j):@sum(gch(i):x(i,j))<=b(j));data:a=300,200,400;b=200,100,450,250;c=526735464523;enddata计算得到最小运费为2950元.建立目标规划引入p1,…,p8表示各个目标的优先顺序；di+，di-表示各个决策目标与参考目标的正偏差和负偏差;i=1,2,3,…下面写出各个约束硬约束（供应约束）系列软约束（1）用户4必须全部满足（2）供应用户1的产品中，工厂3的产品不少于100单位（3）每个用户的满足率不低于80%；四个用户的80%需求量分别为160,80,360,200，即（4）应尽量满足个用户的要求（5）新运费尽量不超过不考虑各个目标费用的10%：（6）因道路限制，工厂2到用户4的路线的运输任务应尽量避免：（7）用户1和用户3的满足率尽量平衡：（8）力求减少总费用：变量要求按照优先级别写出目标函数s.t.硬约束（供应约束）软约束二、利用lingo计算目标规划

多目标规划实质是一个多个目标的线性规划问题，仍可以用Lingo求解，下面以例1和例题2为计算例子。5*x1+10*x2-d11+d12=60;x2-x1/2-d21+d22=0;4*x1+4*x2-d31+d32=36;6*x1+8*x2-d41+d42=48;d12=0;d22=0;d32=0;min=d42;Globaloptimalsolutionfoundatiteration:4Objectivevalue:0.000000VariableValueReducedCostX16.0000000.000000X23.0000000.000000D110.0000000.000000D120.0000000.000000D210.0000000.000000D220.0000000.000000D310.0000000.000000D320.0000000.000000D4112.000000.000000D420.0000001.000000sets:chandi/1..3/:a;xiaodi/1..4/:b;link(chandi,xiaodi):c,x;endsets@for(chandi(i):@sum(xiaodi(j):x(i,j))<=a(i));@sum(chandi(i):x(i,4))+d11-d12=250;x(3,1)+d21-d22=100;@sum(chandi(i):x(i,1))+d31-d32=160;@sum(chandi(i):x(i,2))+d41-d42=80;@sum(chandi(i):x(i,3))+d51-d52=360;@sum(chandi(i):x(i,4))+d61-d62=200;@sum(chandi(i):x(i,1))+d71-d72=200;@sum(chandi(i):x(i,2))+d81-d82=100;@sum(chandi(i):x(i,3))+d91-d92=450;@sum(chandi(i):x(i,4))+d101-d102=250;@sum(link:c*x)+d111-d112=1.1*2950;x(2,4)+d121-d122=0;@sum(chandi(i):x(i,1))/200-@sum(chandi(i):x(i,3))/450+d131-d132=0;@sum(link:c*x)+d141-d142=2950;data:a=300,200,400;b=200,100,450,250;c=526735464523;enddatad11=0;d21=0;d31=0;d41=0;d51=0;d61=0;d71+d81+d91+d101=100;d112=115;d122=0;d132+d131=0.15;min=d142;VariableValueReducedCostD3230.000000.000000D4220.000000.000000D6250.000000.000000D7110.000000.000000D9190.000000.000000D112115.00000.000000D1320.15000000.000000D142410.00000.