第九讲多目标规划

1、目标规划与多目标规划一、 目标规划问题及其数学模型例1 某工厂生产两种产品，受到原材料和设备工时的限制，在 单位利润等有关数据已知的条件下，要求制订一个获利最大的生产计划。具体数据见表4-1产品III限量原材料(kg)51060设备工时(h)4440利润($/件)68表4-1解 设产品I和II产量分别为x1和x2，建立线性规划模型，李容单纯形法求解得到x1=8,x2=2，最大获利为64元。12121212maxz6x8x5x10 x604x4x40 x , x0 作为线性规划的例1，看起来已经圆满解决。但是，作为实际问题，就有几个方面值得进一步考虑：（1）目标函数的选择的单一化：一般来说，作为

2、一个生产计划，需要满足多方面的要求。例如，财务部门希望利润最大化；行政部门希望规模最大化；物资部门则希望物资消耗最小化；销售部门希望产品多样化以适应市场销售，降低销售风险；计划部门产品批量尽可能大，便于安排生产等等。而这些目标有些是一致的，有些则是相互矛盾的，不可调和的。需要用数学模型来解决问题，怎么办呢？ 这时，有两种方法可用，一是从总多矛盾的目标中，找出主要目标，忽略与之矛盾的其它目标。这样考虑的决策者，就是要建立单目标模型。二是协调众多目标，通过相互妥协达成可行的多目标规规划。（2）在实际问题中，各类约束不一定相容。也就是说，建立的线性规划模型不一定有可行解(或者说可行域可能是空集)。（

3、3）在用数学方法解决实际问题时，只是强调数学模型与实际问题的相似性。而并非完全一致，一旦实际问题发生变化，则模型得到的可行解或最优解就面临着不能实施的可能。 严格意义上讲，数学模型相对于实际问题，都是实际问题“刚性”的本质的抽象。线性规划也一样，由其“刚性”注定了其局限性。现代决策者强调定性和定量分析相结合，强调硬技术和软技术的结合，强调矛盾和冲突的合理性，强调妥协和让步的必要性。所以线性规划就不具备这样的分析能力。 1961年，查恩斯(A.Charnes)和库伯(W.W.Cooper)提出目标规划(goal programming)，就是弥补了上述线性规划局限性。目标规划在处理实际问题时，承

4、认各决策要求(即变冲突的）的合理性；在作最终决策时，不强调绝对意义上的最优性。因此目标规划是更接近于实际决策过程的决策工具。2目标规划的模型例2 在上述例1的基础上，计划人员还要求考虑如下意见：（1）由于产品II销售疲软，故希望产品II的产量不超过产品I产量的一半；（2）原材料严重短缺，生产中应避免过量消耗；（3）最好能够节约4小时设备工时；（4）计划利润不少于48元。分析：把这四条意见分别看成营销部门、材料部门、设备管理部门、财务部门四个部门的目标愿望。那么在决策的时候，如何协调者四个部门的意愿呢。同等对待每个目标意愿，势必陷于矛盾中。故当务之急是确定四个目标的重要程度或轻重缓急。然后根据重

5、要程度逐一协调。下面引入一些新的变量来解决问题。1优先因子和权系数不同目标的主次轻重有两种差别： 一种差别是绝对的，可用优先因子PL来表示，只有在高级优先因子对应的目标已满足的基础上，才能考虑较低级优先因子所对应的目标；在考虑低级优先因子对应的目标时，绝不允许违背已满足的高级优先因子对应的目标。因此，优先因子的关系为PLPL+1,即PL对应的目标比PL+1对应的目标有绝对的优先性。 另外一种差别是相对的，这些目标具有相同的优先因子，它们的重要程度可用权系数的不同来表示。 在给出点四个部门的目标中，计划人员根据部门提出目标的口气以及在生产中的实际地位来确定，决策者必须让不同部门都参与确定优先因子

6、，达成一致后方可做下一步。例2的协调结果是：P1原材料使用限量不得突破；P2产品II产量优先考虑；P3设备工时其次考虑；P4最后考虑计划利润的要求。 P1P2P3P4.2 列出每个部门的目标愿望分为决策值和目标值。决策值依赖于问题的决策变量，使决策变量的表达式，目标值是该决策值的一个愿望参考值。比如，设决策者决定生产产品I x1件，产品II x2件。则四个部门的目标决策值和目标值分别为部门目标决策值f目标值f*优先级别P营销部门X2-x1/20P2材料部门5x1+10 x260P1设备管理4x1+4x240-4=36P3财务部门6x1+8x248P43偏差变量 对每一个决策目标，引入正负偏差变

7、量d+和d-，分别表示决策值与目标值的偏差，d+表示决策值超过目标值部分，d-表示决策值不足目标值部分。dff *, df *f显然，根据定义，有那么，例2的四个目标的决策值和目标值的偏差表达为121112221233124412ii5x10 xdd60 xxdd024x4xdd366x8xdd48x ,x0d ,d0,i1,2,3,40dd0d,d4各个目标的欲望表达 任何一个部门在表达自己的意见时，总是用某种语气表达目标决策值和目标值之间的某种比较欲望。归纳起来，不外乎下面三种：（1）要求决策值不超过目标值min d+ 或min f(d+)（2）要求决策值不低于目标值min d- 或min

8、 f(d-)（3）要求决策值恰好达到目标值min d-+d+ 或 min f(d-+d+)根据上面的定义，例2的四个部门的欲望可以表达为材料部门：min d1+ 营销部门：min d2+设备部门：min d3+财务部门：min d4- 对于材料部门，基于语气的强硬，也可以把材料部门的欲望改为d1+=0。这样的话这个约束就由可以商量（称为软约束）转化为没有商量的余地（称为硬约束），并不改变问题的性质。根据上面引入的概念和分析，例2的规划模型为11223344121112221233124412iimin p d ,p d ,p d ,p d 5x10 xdd60 xxdd024x4xdd366x

9、8xdd48x ,x0d ,d0,i1,2,3,4 在建立目标规划模型时，尽可能利用各种决策技术，尽量减少主观性和片面性。目标规划的一般形式L,.,2, 1i ,0d,dn,.,2, 1j,0 x,L,.2, 1i ,gddxc,m,.,2, 1i ,b),(xa. t . s)dwdw(pzminiijiiin1jjijin1jjijq1kL1jjkjjkjk硬约束软约束例2 多目标供给问题 已知三个工厂生产的产品供应给四个用户，各工厂生产量、用户需求量及从各个工厂到用户的单位产品的运输费用如表4-2所示。由于总生产量小于总需求量，上级部门经研究决定，制定了调配方案的8项指标，并规定了重要性

10、的次序。表4-2用 户 1 2 3 4 生产量工厂1工厂2工厂3需求量534200255100642450763250300200400第一目标：用户4为重要部门，需求量必须全部满足；第二目标：供应用户1的产品中，工厂3的产品不少于100个单位；第三目标：每个用户的满足率不低于80%；第四目标：应尽量满足个用户的要求；第五目标：新方案的总运费不超过原运输问题的总运费的10%；第六目标：因道路问题，工厂2到用户4的路线尽量避免运输；第七目标：用户1和用户3的满足率应尽量保持平衡；第八目标：力求减少总运费；请列出相应的目标规划模型，并用Lingo求解。解设从工厂i向用户j调运产品量为xij,i=1

11、,2,3;j=1,2,3,4;Cij表示从工厂i向用户j调运的单位产品的费用；ai表示工厂i的产量；i=1,2,3;bj表示用户j的需求量，j=1,2,3,4; 由于目标5中需要用到不考虑任何目标的调运方案下的最小费用，故需要先求解如下线性规划模型3i41jijijxczmin, 3 ,2, 1j; 3 ,2, 1i ,0 x4, 3 ,2, 1j,bx3 ,2, 1i ,axijj31iiji41jijs.t.上述模型的求解程序及结果为sets:gch/1.3/:a;yhu/1.4/:b;link(gch,yhu):x,c;endsetsmin=sum(link:c*x);for(gch(i

12、):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=5 2 6 73 5 4 64 5 2 3;enddata计算得到最小运费为2950元.建立目标规划引入p1,p8表示各个目标的优先顺序；di+，di-表示各个决策目标与参考目标的正偏差和负偏差;i=1,2,3,下面写出各个约束硬约束（供应约束）,400 xxxx,200 xxxx,300 xxxx343332312423222114131211系列软约束（1）用户4必须全部满足;250ddxxx11

13、3424141dmin（2）供应用户1的产品中，工厂3的产品不少于100单位;100ddx2231-2dmin（3）每个用户的满足率不低于80%；四个用户的80%需求量分别为160,80,360,200，即,200ddxxx,360ddxxx,80ddxxx,160ddxxx66342414553323134432221233312111654-3ddddmin（4）应尽量满足个用户的要求,250ddxxx,450ddxxx,100ddxxx,200ddxxx10103424149933231388322212773121111098-7ddddmin（5）新运费尽量不超过不考虑各个目标费用的

14、10%：,324529501 .1ddxc111131i41jijij11dmin（6）因道路限制，工厂2到用户4的路线的运输任务应尽量避免：, 0ddx12122412dmin（7） 用户1和用户3的满足率尽量平衡：, 0dd450 xxx200 xxx13133323133121111313ddmin（8）力求减少总费用：,2950ddxc141431i41jijij 14dmin变量要求14,2, 1i ,0d,d4, 3 ,2, 1j;3 ,2, 1i ,0 xiiij按照优先级别写出目标函数14813137126115109874654332211dp)dd(pdpdp)dddd(p

15、)dddd(pdpdpmins.t.硬约束（供应约束）,400 xxxx,200 xxxx,300 xxxx343332312423222114131211;250ddxxx11342414;100ddx2231软约束,200ddxxx,360ddxxx,80ddxxx,160ddxxx66342414553323134432221233312111,250ddxxx,450ddxxx,100ddxxx,200ddxxx1010342414993323138832221277312111,324529501 .1ddxc111131i41jijij, 0ddx121224, 0dd450 xx

16、x200 xxx1313332313312111,2950ddxc141431i41jijij 14,2, 1i ,0d,d4, 3 ,2, 1j;3 ,2, 1i ,0 xiiij二、利用lingo计算目标规划 多目标规划实质是一个多个目标的线性规划问题，仍可以用Lingo求解，下面以例1和例题2为计算例子。11223344121112221233124412iimin p d ,p d ,p d ,p d 5x10 xdd60 xxdd024x4xdd366x8xdd48x ,x0d ,d0,i1,2,3,45*x1+10*x2-d11+d12=60;x2-x1/2-d21+d22=0;4

17、*x1+4*x2-d31+d32=36;6*x1+8*x2-d41+d42=48;d12=0;d22=0;d32=0;min=d42; Global optimal solution found at iteration: 4 Objective value: 0.000000 Variable Value Reduced Cost X1 6.000000 0.000000 X2 3.000000 0.000000 D11 0.000000 0.000000 D12 0.000000 0.000000 D21 0.000000 0.000000 D22 0.000000 0.000000 D3

18、1 0.000000 0.000000 D32 0.000000 0.000000 D41 12.00000 0.000000 D42 0.000000 1.000000sets:chandi/1.3/:a;xiaodi/1.4/:b;link(chandi,xiaodi):c,x;endsetsfor(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-d

19、42=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=5 2 6 73 5 4 64 5 2 3;enddatad11=0;d21=0;d31=0;d41=0;d51=0;d61=0;d71+d81+d91+d101=1