第一讲目标规划模型

1、第一讲 目标规划模型 目标规划是由线性规划发展演变而来的。线性规划考虑的是只有可以个目标函数的问题，而实际问题中往往需要考虑多个目标函数，这些目标不仅有主次关系，而且有的还互相矛盾。这些问题用线性规划求解就比较困难，因而提出了目标规划。这里所讨论的目标规划实质上是线性目标规划。1.1线性规划与目标规划为了进一步了解目标规划的特点和性质，下面对同一问题分别考虑线性规划建模和目标规划建模。1.1.1线性规划建模与目标规划建模例1.1（生产安排问题） 某企业生产甲、乙两种产品，需要用到A、B、C三种设备，关于产品的盈利与使用设备的工时及限制如表1-1所示。问：该企业应如何安排生产，使得在计划期内总利

2、润最大？表1-1 生产产品使用设备的工时、限制和产品的盈利甲乙设备的生产能力/hA/（h/件）2212B/（h/件）4016C/（h/件）0515盈利/（元/件）2003001. 线性规划建模例8.1是一个线性规划问题，直接考虑它的线性规划模型。设甲、乙产品的产量分别为，建立线性规划模型：用LINDO或LINGO软件求解，得到最优解。2. 目标规划建模企业的经营目标不仅仅是利润，还要考虑多个方面。例如在例8.1中，增加下列因素（目标）：（1） 力求使利润指标不低于1500元；（2） 考虑到市场需求，甲、乙两种产品的产量比应尽量保持1：2；（3） 设备A为贵重设备，严格禁止超时使用；（4） 设备

3、C可以适当加班，但要控制；设备B既要求充分利用，又尽可能不加班，在重要性上，设备B是设备C的3倍。从上述问题可以看出，仅用线性规划方法是不够的，需要借助于目标规划的方法进行建模求解。1.1.2 线性规划建模的局限性例1.2（汽车广告费问题） 某汽车销售公司委托一个广告公司在电视上为其做广告。汽车销售公司提出三个目标：第一个目标，至少有40万高收入的男性公民（记为HIM）看到这个广告；第二个目标，至少有60万一般收入的公民（记为LIP）看到这个广告；第三个目标，至少有35万高收入的女性公民（记为HIW）看到这个广告。广告公司可以从电视台购买两种类型的广告展播：足球赛中插播广告和电视系列剧中插播广

4、告。广告公司最多花费60万元的电视广告费。每一类广告展播每分钟的花费及潜在的观众人数如表1-2所示。广告公司必须决定为汽车销售公司购买两种类型的电视广告展播各多少分钟？表1-2 广告展播的花费及潜在的观众人数HIMLIPHIW费用/（万元/min）足球赛中插播/（万人/min）710510系列剧中插播/（万人/min）35461. 线性规划建模对于例1.2考虑建立线性规划模型。设分别是足球赛和系列剧中插播的分钟数，按照要求，列出相应的线性规划问题。用LINDO或LINGO软件求解，会发现该问题不可行。2. 线性规划建模的局限性通过上述两个例子可以看出，在求解问题中，线性规划模型存在很大的局限性

5、。（1） 线性规划要求所解决的问题必须满足全部的约束，而实际问题中并非所有约束都需要严格的满足；（2） 线性规划只能处理单目标的优化问题，而对一些次目标只能转化为约束处理，而在实际问题中，目标和约束是可以相互转化的，处理时不一定要严格区分；（3） 线性规划在处理问题时，将各个约束（也可看做目标）的地位看成同等重要，而在实际问题中，各目标的重要性即有层次上的差别，也有在同一层次上不同权重的差别；（4） 线性规划寻找最优解，而许多实际问题只需要找到满意解就可以了。1.2目标规划的数学模型1.2.1 目标规划的基本概念为了克服线性规划的局限性，目标规划采用如下手段。1. 设置偏差变量用偏差变量来表示

6、实际值与目标值之间的差异，令d+为超出目标的差值，称为正偏差变量；d-为未达到目标的差值，称为负偏差变量。其中d+与d-至少有一个为0。当实际值超过目标值时，有d-=0，d+0;当实际值未达到目标值时，有d+=0，d-0；当实际值与目标值一致时，有d+=d-=0。2. 统一处理目标与约束在目标规划中，约束有两类，一类是对资源有严格限制的，同线性规划的处理相同，用严格的等式或不等式约束来处理，例如，用目标规划求解例8.1，设备A禁止超时使用，则有刚性约束：另一类约束是可以不严格控制的，连同原线性规划的目标，构成柔性约束。例如，在求解例8.1中，我们希望利润不低于1500元，则目标可表示为甲，乙两

7、种产品的产量尽量保持1：2的比例，则目标可表示为设备C可以适当加班，但要控制，则目标可表示为设备B既要求充分利用，又尽可能不加班，则目标可表示为从上面的分析可以看到，如果希望不等式保持大于等于，则极小化负偏差；如果希望不等式保持小于等于，则极小化正偏差；如果希望保持等式，则同时极小化正、负偏差。3. 目标的优先级与权系数在目标规划模型中，目标的优先分为两个层次。第一个层次是目标分成不同的优先级，在计算目标规划时，必须先优化高优先级的目标，然后再优化低优先级的目标。通常以P1，P2，表示不同的因子，并规定。第二个层次是目标处于同一优先级，但两个目标的权重不一样，因此两目标同时优化，但用权系数的大

8、小来表示目标重要性的差别。1.2.2 目标规划模型的建立总的来讲，目标规划在建模中，除刚性约束必须严格满足外，对所有目标约束均允许有偏差。其求解过程要从高到低逐层优化，在不增加高层次目标的偏差值的情况下，逐次使低层次的偏差达到极小。例1.3 用目标规划方法求解例1.1，建立相应的目标规划模型。解 ：在例1.1中设备A是刚性约束，其余是线性约束。首先，最重要的指标是企业的利润，因此，将它的优先级列为第一级；其次，甲、乙两种产品的产量尽量保持1：2的比例，列为第二级；再次，设备C，B的工作时间要有所控制，列为第三级。在第三级中，设备B的重要性是设备C的三倍，因此，它们的权重不一样，设备B前的系数是

9、设备C前系数的3倍。由此得到相应的目标规划模型。通过上述实例，可以给出目标规划的一般数学表达式。1.2.3 目标规划的一般模型设是目标规划的决策变量，共有m个约束是刚性约束，可能是等式约束，也可能是不等式约束。设有l个柔性目标约束，其目标规划约束的偏差为，设有q个优先级别，分别为在同一个优先级中，有不同的权重，分别记为因此目标规划模型的一般数学表达式为：1.2.4 求解目标规划的序贯式算法序贯式算法是求解目标规划的一种早期算法，其核心是根据优先级的先后次序，将目标规划问题分解成一系列的单目标规划问题，然后再依次求解。算法1.1（求解目标规划的序贯式算法）对于k=1,2,q, 求解单目标规划问题

10、 其最优目标值为，当k=1时，第三个约束为空约束。当k=q时，所对应的解为目标规划的最优解。例1.4 用算法1.1求解例1.3。 相关LINDO程序为： MIN DMINUS1 SUBJECT TO 2X1 + 2X2 = 12 200X1 + 300X2 - DPLUS1 + DMINUS1 = 1500 2X1 - X2 - DPLUS2 + DMINUS2 = 0 4X1 - DPLUS3 + DMINUS3 = 16 5X2 - DPLUS4 + DMINUS4 = 15 END 计算结果如下： LP OPTIMUM FOUND AT STEP 5 OBJECTIVE FUNCTION

11、 VALUE 1) 0.E+00 VARIABLE VALUE REDUCED COST DMINUS1 0. 1. X1 3. 0. X2 3. 0. DPLUS1 0. 0. DPLUS2 3. 0. DMINUS2 0. 0. DPLUS3 0. 0. DMINUS3 4. 0. DPLUS4 0. 0. DMINUS4 0. 0. ROW SLACK OR SURPLUS DUAL PRICES 2) 0. 0. 3) 0. 0. 4) 0. 0. 5) 0. 0. 6) 0. 0. NO. ITERATIONS= 5 目标函数的最优值为0，即第一级偏差为0。 求第二级偏差，列出LIN

12、GO程序如下： MIN DPLUS2 + DMINUS2 SUBJECT TO 2X1 + 2X2 = 12 200X1 + 300X2 - DPLUS1 + DMINUS1 = 1500 2X1 - X2 - DPLUS2 + DMINUS2 = 0 4X1 - DPLUS3 + DMINUS3 = 16 5X2 - DPLUS4 + DMINUS4 = 15 DMINUS1 = 0 END 计算结果如下： LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) 0.E+00 VARIABLE VALUE REDUCED COST DPL

13、US2 0. 1. DMINUS2 0. 1. X1 1. 0. X2 3. 0. DPLUS1 0. 0. DMINUS1 0. 0. DPLUS3 0. 0. DMINUS3 8. 0. DPLUS4 3. 0. DMINUS4 0. 0. ROW SLACK OR SURPLUS DUAL PRICES 2) 0. 0. 3) 0. 0. 4) 0. 0. 5) 0. 0. 6) 0. 0. 7) 0. 0. NO. ITERATIONS= 2 目标函数最优值还是0，即二级偏差仍为0。 求第三级偏差，列出LINGO程序： MIN 3DPLUS3 + 3DMINUS3 + DPLUS4 S

14、UBJECT TO 2X1 + 2X2 = 12 200X1 + 300X2 - DPLUS1 + DMINUS1 = 1500 2X1 - X2 - DPLUS2 + DMINUS2 = 0 4X1 - DPLUS3 + DMINUS3 = 16 5X2 - DPLUS4 + DMINUS4 = 15 DMINUS1 = 0 DPLUS2 + DMINUS2 = 0 END计算结果如下： LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) 29.00000 VARIABLE VALUE REDUCED COST DPLUS3 0. 6

15、. DMINUS3 8. 0. DPLUS4 5. 0. X1 2. 0. X2 4. 0. DPLUS1 100. 0. DMINUS1 0. 0. DPLUS2 0. 0. DMINUS2 0. 11. DMINUS4 0. 1. ROW SLACK OR SURPLUS DUAL PRICES 2) 0. 0. 3) 0. 0. 4) 0. 5. 5) 0. -3. 6) 0. 1. 7) 0. 0. 8) 0. 5. NO. ITERATIONS= 2目标函数最优值为29，即第三级偏差为29。 分析结果知，X1为2，X2为4，DPLUS1为100，因此目标规划的最优解为（2，4），最优

16、利润为1600。例1.5按照算法1.1编写求解例1.3的LINGO程序，给出相应的计算结果，并将计算结果与LINDO软件的计算结果相比较。 按照算法1.1编写LINGO程序： sets: Level/1.3/: P, z, Goal; Variable/1.2/: x; H_Con_Num/1.1/: b; S_Con_Num/1.4/: g, dplus, dminus; H_Cons(H_Con_Num, Variable): A; S_Cons(S_Con_Num, Variable): C; Obj(Level, S_Con_Num): Wplus, Wminus;endsetsdat

17、a: P= ? ? ?; Goal = ? ? 0; b = 12; g= 1500 0 16 15; A = 2 2; C = 200 300 2 -1 4 0 0 5; Wplus = 0 0 0 0 0 1 0 0 0 0 3 1; Wminus = 1 0 0 0 0 1 0 0 0 0 3 0;enddatamin=sum(Level: P * z);for(Level(i): z(i)=sum(S_Con_Num(j): Wplus(i,j)*dplus(j) +sum(S_Con_Num(j): Wminus(i,j)*dminus(j);for(H_Con_Num(i): su

18、m(Variable(j): A(i,j) * x(j) = b(i);for(S_Con_Num(i): sum(Variable(j): C(i,j)*x(j) + dminus(i) - dplus(i) = g(i););for(Level(i) | i #lt# size(Level): bnd(0, z(i), Goal(i););END根据此程序可进行调试。1.3 目标规划模型的实例前面介绍了目标规划的求解方法，这里再介绍几个目标规划模型的实例，帮助我们进一步了解目标规划模型的建立和求解过程。由于选用LINGO软件求解目标规划较为方便，因此在下面的求解过程中，所用的软件均是LIN

19、GO软件。如果读者对LINDO软件的编程方法感兴趣，可按照1.2节介绍的方法编写LINDO程序。例1.6 某音像商店有5名全职售货员和4名兼职售货员，全职售货员每月工作160h，兼职售货员每月工作80h,根据过去的工作记录，全职售货员每小时销售CD25张，平均每小时工资15元，加班工资每小时22.5员，兼职售货员每小时销售CD10张，平均工资每小时10元，加班工资每小时10元，现在预测下月CD销售量为27500张，商店每周开门营业6天，所以可能要加班，每出售一张CD赢利1.5元。商店经理认为，保持稳定的就业水平加上必要的加班，比不加班但就业水平不稳定要好，但全职收获员，如果加班过多，就会因为疲

20、劳过度而造成效率下降，因而不允许每月加班超过100h，建立相关的目标规划模型，并运用LINGO软件求解。解：首先，建立目标规划的优先级。：下月的CD销售量达到27500张。：限制全职售货员加班时间不超过100h。：保持全体售货员充分就业，因为充分工作是良好劳资关系的重要因素，但对全职售货员要比兼职售货员优先考虑。：尽量减少加班时间，但对两种售货员区别对待，优先权因子由他们对利润的贡献而定。第二，建立目标约束。（1） 销售目标约束。设：全体全职售货员下月的工作时间；：全体兼职售货员下月的工作时间；：大不到销售目标的偏差；：超过销售目标的偏差。希望下月的销售量超过27500张CD片，因此销售目标为

21、 （25）（2） 正常工作时间约束。设：全体全职售货员下月的停工时间；：全体全职售货员下月的加班时间；：全体兼职售货员下月的停工时间；：全体兼职售货员下月的加班时间。由于希望保持全体售货员充分就业，同时加倍优先考虑全职售货员，因此工作目标约束为 （26）（3） 加班时间的限制。设 ：全体全职售货员下月加班不足100h的偏差； ：全体全职售货员下月加班超过100h的偏差限制全体售货员加班时间不超过100h，将加班约束看成正常班的约束，不同的是右端加上100h，因此加班目标约束为 （27）另外，全职售货员加班1h，商店得到的利润为15元（25*1.5-22.5=15），兼职售货员加班1h，商店得到

22、的利润为5元，（10*1.5-10=5），因此加班1h全职售货员获得的利润是兼职售货员的3倍，故权因子之比为 ，所以，另一个加班目标约束为 （28）第三，按目标的优先级，写出相应的目标规划模型： （29）S.T （30） （31） （32） （33） （34）第四，写出LINGO程序： sets: Level/1.4/: P, z, Goal; Variable/1.2/: x; S_Con_Num/1.4/: g, dplus, dminus; S_Cons(S_Con_Num, Variable): C; Obj(Level, S_Con_Num): Wplus, Wminus;endse

23、tsdata: P= ? ? ? ?; Goal = ?, ?, ?, 0; g= 27500 800 320 900; C = 25 10 1 0 0 1 1 0; Wplus = 0 0 0 0 0 0 0 1 0 0 0 0 0 1 3 0; Wminus = 1 0 0 0 0 0 0 0 0 2 1 0 0 0 0 0;enddatamin=sum(Level: P * z);for(Level(i): z(i)=sum(S_Con_Num(j): Wplus(i,j)*dplus(j) +sum(S_Con_Num(j): Wminus(i,j)*dminus(j);for(S_C

24、on_Num(i): sum(Variable(j): C(i,j)*x(j) + dminus(i) - dplus(i) = g(i););for(Level(i) | i #lt# size(Level): bnd(0, z(i), Goal(i););END 然后进行调试。最后得出，全职售货员总工作时间为900h（加班100h）,兼职售货员总工作时间500h（加班时间180h），下月共销售CD盘27500张，商店获得利润 （元）。例 1.7 某计算机公司生产三种型号的笔记本电脑A，B，C。这3种笔记本电脑需要在复杂的装配线上生产，生产一台A，B，C型号的笔记本电脑分别需要5，8，12（

25、h）.公司装配线正常的生产时间是每月1700h，公司营业部门估计A,B,C三种笔记本电脑的利润分别是每台1000，1440，2520（元），而公司预测这个月生产的笔记本电脑能够全部售出。公司经理考虑以下目标：第一目标：充分利用正常的生产能力，避免开工不足；第二目标：优先满足老客户的需求，A，B，C三种型号的电脑50，50，80（台），同时根据三种电脑的纯利润分配不同的权因子；第三目标：限制装配线加班时间，不允许超过200h；第四目标：满足各种型号电脑的销售目标，A，B，C型号分别为100，120，100（台），再根据三种电脑的纯利润分配不同的权因子；第五目标：装配线的加班时间尽可能少。请列出相

26、应的目标规划模型，并用LINGO软件求解。解 建立目标约束：（1）装配线正常生产 设生产A，B，C型号的电脑为(台)，为装配线正常生产时间未利用数，为装配线加班时间，希望装配线正常生产，避免开工不足，因此装配线目标约束为 （35）（2）销售目标优先满足老客户的需求。并根据三种电脑的纯利润分配不同的权因子，S，B，C三种型号的电脑，每小时的利润是1000/5，1440/8，2520/12，因此，根据老客户的销售目标建立约束。再考虑一般销售，类似上面的讨论，可得到约束。（3） 加班限制 首先是限制装配线加班时间，不允许超过200h。再次装配线的加班时间尽可能少。写出目标规划的数学模型。参考LING

27、O程序：sets: Level/1.5/: P, z, Goal; Variable/1.3/: x; S_Con_Num/1.8/: g, dplus, dminus; S_Cons(S_Con_Num, Variable): C; Obj(Level, S_Con_Num): Wplus, Wminus;endsetsdata: P= ? ? ? ? ?; Goal = ?, ?, ?, ?, 0; g= 1700 50 50 80 100 120 100 1900; C = 5 8 12 1 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 1 5 8 12; Wplus

28、= 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0; Wminus = 1 0 0 0 0 0 0 0 0 20 18 21 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 18 21 0 0 0 0 0 0 0 0 0;enddatamin=sum(Level: P * z);for(Level(i): z(i)=sum(S_Con_Num(j): Wplus(i,j)*dplus(j) +sum(S_Con_Num(j): Wminus(i,j)*dminu

29、s(j);for(S_Con_Num(i): sum(Variable(j): C(i,j)*x(j) + dminus(i) - dplus(i) = g(i););for(Level(i) | i #lt# size(Level): bnd(0, z(i), Goal(i););经5次计算得到：=100，。装配线生产时间为1900h，满足装配线加班不超过200h，能够满足老客户的需求，但未能达到销售目标。销售总利润为（元）。例1.8 已知3个工厂生产的产品供应给4个客户，各工厂生产量，用户需求量及从工厂到用户的单位产品的运输费用如表1-3所示。由于总生产量小于小于总需求量，上级部门研究后，

30、制定了调配方案的8项指标，并规定了重要性的秩序。表1.3 工厂生产量，用户需求量及运费单价用户1234生产量工厂15267300工厂23546200工厂34523200需求量200100450250第一目标：用户4为重要部门，需求量必须全部满足；第二目标：供应用户1的产品中，工厂3的产品不少于100个单位；第三目标：每个用户的满足率不低于80%；第四目标：应尽量满足各用户的需求，第五目标：新方案的总运费不超过原运输问题的调度方案的10%；第六目标：因道路限制，工厂2到用户4的路线应尽量避免运输任务；第七目标：用户1和用户3的满足率应尽量保持平衡；第八目标：力求减少运输费。请列出相应的目标规划模

31、型，并用LINGO求解。解： 求解原运输问题：由于总生产量小于总需求量，虚设工厂4，生产量为100个单位，到各个用户间的运费单价为0.利用第七章介绍的运输问题的求解方法，用LINGO软件求解，得到总运费是2950元，运输方案如表1-4所示：表1-4 作为运输问题的最优方案用户1234生产量工厂1100200300工厂2200200工厂3250150400工厂4100100需求量200100450250可看出上述方案中，第一个目标就不能满足，用户4的需求量也得不到满足，下面按照目标性的等级列出目标规划的约束和目标函数。 设为工厂i调配给用户j的运量。 建模过程略。参考程序：sets: Level

32、/1.8/: P, z, Goal; S_Con_Num/1.13/: dplus, dminus; Plant /1.3/: a; Customer /1.4/: b; Routes(Plant, Customer): c, x;endsetsdata: P= ? ? ? ? ? ? ? ?; Goal = ? ? ? ? ? ? ? 0; a = 300 200 400; b = 200 100 450 250; c = 5 2 6 7 3 5 4 6 4 5 2 3;enddatamin=sum(Level: P * z);z(1) = dminus(9);z(2) = dminus(1

33、);z(3) = dminus(2)+dminus(3)+dminus(4)+dminus(5);z(4) = dminus(6)+dminus(7)+dminus(8)+dminus(9);z(5) = dplus(10);z(6) = dplus(11);z(7) = dminus(12)+dplus(12);z(8) = dplus(13);for(Plant(i): sum(Customer(j): x(i,j) 0,vi(i=1,2,m)表示第j个决策单元对第r种输出的参出量，并且满足yrj0，vi(i=1,2,m)表示第i种输入的一种度量（或称为权），ur（r=1，2，s）表示第r

34、种输出的一种度量（或称为权）。将表1-7中的元素写成向量的形式，如表1-8所示。表1-8 决策单元的矩阵形式 1 2 j n vX1 x2 xj xnY1 y2 yj yn u在表1-8中，Xj，Yj（j=1，2，n）分别为决策单元j的输入，输出向量，v，u分别为输入，输出的权重。1.4.2 模型1、引例考查某种燃烧置的燃烧比。设YR是给定X个单位煤产生热量的理想值，设是某种燃烧装置燃烧X个单位煤所产生热量的实际值，则燃烧装置的燃烧比（相对评价指标数）为，为.（50）显然有，YR即01。现在用模型的方法推导出式（50）。考虑优化问题Max ,（51）s.t （52）（53）u0，v0，.（54）其中u，v是权重，其目的是使约束（52）（53）成立。设（，）是优化问题（51）（54）的最优解，由于YR，以及，得到。因此，优化问题（51）（54）的最优解（，）满足，其最优目标值为，即燃烧装置的燃烧评价指数。2、模型类似上面的讨论，对于表8-8所给出的数据，设，j=1，2，n，为第j个决策单元的评价指数。总可以选择适当的权系数u，v，使得，j=1，2，n，第j个决策单元的评价指数的意义是：在权系数