第六讲多目标规划ppt课件

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对应的目的有绝对的优先性。 另外一种差别是相对的，这些目的具有一样的优先因子，它们的重要程度可用权系数的不同来表示。 在给出点四个部门的目的中，方案人员根据部门提出目的的口气以及在消费中的实践位置来确定，决策者必需让不同部门都参与确定优先因子，达成一致后方可做下一步。例2

6、的协调结果是：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偏向变量 对每一个决策目的，引入正负偏向变量d+和d-，分别表示决策值

7、与目的值的偏向，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 f(d-)3要求决策值恰好到达目的

8、值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 xxdd024x4xdd366x8xdd48x ,x0d ,d0,i1,2,3,

9、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项目的，并规定了重要性的次序。表4-2用 户 1 2 3 4 消费量工厂

10、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向

11、用户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):sum(yhu(j):x(i,j)=a(i);

12、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必需全部满足;250ddxxx113424141dmin2供应用户1的产品中，工厂3的产品不

13、少于100单位;100ddx2231-2dmin3每个用户的满足率不低于80%；四个用户的80%需求量分别为160,80,360,200，即,200ddxxx,360ddxxx,80ddxxx,160ddxxx66342414553323134432221233312111654-3ddddmin4应尽量满足个用户的要求,250ddxxx,450ddxxx,100ddxxx,200ddxxx10103424149933231388322212773121111098-7ddddmin5新运费尽量不超越不思索各个目的费用的10%：,324529501 .1ddxc111131i41jijij11

14、dmin6因道路限制，工厂2到用户4的道路的运输义务应尽量防止：, 0ddx12122412dmin7 用户1和用户3的满足率尽量平衡：, 0dd450 xxx200 xxx13133323133121111313ddmin8力求减少总费用：,2950ddxc141431i41jijij 14dmin变量要求14,2, 1i ,0d,d4, 3 ,2, 1j;3 ,2, 1i ,0 xiiij按照优先级别写出目的函数14813137126115109874654332211dp)dd(pdpdp)dddd(p)dddd(pdpdpmins.t.硬约束供应约束,400 xxxx,200 xxxx

15、,300 xxxx343332312423222114131211;250ddxxx11342414;100ddx2231软约束,200ddxxx,360ddxxx,80ddxxx,160ddxxx66342414553323134432221233312111,250ddxxx,450ddxxx,100ddxxx,200ddxxx1010342414993323138832221277312111,324529501 .1ddxc111131i41jijij, 0ddx121224, 0dd450 xxx200 xxx1313332313312111,2950ddxc141431i41jij

16、ij 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*x1+4*x2-d31+d32=36;6*x1+8*x2-d41+d42=48;d12=

17、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 D31 0.000000 0.000000 D32 0.000000 0.000000 D41

18、 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-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