第一讲目标规划模型

第一讲目标规划模型目标规划是由线性规划发展演变而来的。线性规划考虑的是只有可以个目标函数的问题，而实际问题中往往需要考虑多个目标函数，这些目标不仅有主次关系，而且有的还互相矛盾。这些问题用线性规划求解就比较困难，因而提出了目标规划。这里所讨论的目标规划实质上是线性目标规划。1.1线性规划与目标规划为了进一步了解目标规划的特点和性质，下面对同一问题分别考虑线性规划建模和目标规划建模。1.1.1线性规划建模与目标规划建模例1.1（生产安排问题）某企业生产甲、乙两种产品，需要用到A、B、C三种设备，关于产品的盈利与使用设备的工时及限制如表1-1所示。问：该企业应如何安排生产，使得在计划期内总利润最大？表1-1生产产品使用设备的工时、限制和产品的盈利甲乙设备的生产能力/hA/（h/件）2212B/（h/件）4016C/（h/件）0515盈利/（元/件）2003001.线性规划建模例8.1是一个线性规划问题，直接考虑它的线性规划模型。设甲、乙产品的产量分别为12,xx，建立线性规划模型：12121212max200300,..2212,416,515,,0.Zxxstxxxxxx用LINDO或LINGO软件求解，得到最优解*123,3,1500xxz。2.目标规划建模企业的经营目标不仅仅是利润，还要考虑多个方面。例如在例8.1中，增加下列因素（目标）：（1）力求使利润指标不低于1500元；（2）考虑到市场需求，甲、乙两种产品的产量比应尽量保持1：2；（3）设备A为贵重设备，严格禁止超时使用；（4）设备C可以适当加班，但要控制；设备B既要求充分利用，又尽可能不加班，在重要性上，设备B是设备C的3倍。从上述问题可以看出，仅用线性规划方法是不够的，需要借助于目标规划的方法进行建模求解。1.1.2线性规划建模的局限性例1.2（汽车广告费问题）某汽车销售公司委托一个广告公司在电视上为其做广告。汽车销售公司提出三个目标：第一个目标，至少有40万高收入的男性公民（记为HIM）看到这个广告；第二个目标，至少有60万一般收入的公民（记为LIP）看到这个广告；第三个目标，至少有35万高收入的女性公民（记为HIW）看到这个广告。广告公司可以从电视台购买两种类型的广告展播：足球赛中插播广告和电视系列剧中插播广告。广告公司最多花费60万元的电视广告费。每一类广告展播每分钟的花费及潜在的观众人数如表1-2所示。广告公司必须决定为汽车销售公司购买两种类型的电视广告展播各多少分钟？表1-2广告展播的花费及潜在的观众人数HIMLIPHIW费用/（万元/min）足球赛中插播/（万人/min）710510系列剧中插播/（万人/min）35461.线性规划建模对于例1.2考虑建立线性规划模型。设12,xx分别是足球赛和系列剧中插播的分钟数，按照要求，列出相应的线性规划问题。121212121212min00;()..10660,()7340,()10560,()5435,(),0.xxstxxxxHIMxxLIPxxHIWxx可以任意目标广告费约束约束约束约束用LINDO或LINGO软件求解，会发现该问题不可行。2.线性规划建模的局限性通过上述两个例子可以看出，在求解问题中，线性规划模型存在很大的局限性。（1）线性规划要求所解决的问题必须满足全部的约束，而实际问题中并非所有约束都需要严格的满足；（2）线性规划只能处理单目标的优化问题，而对一些次目标只能转化为约束处理，而在实际问题中，目标和约束是可以相互转化的，处理时不一定要严格区分；（3）线性规划在处理问题时，将各个约束（也可看做目标）的地位看成同等重要，而在实际问题中，各目标的重要性即有层次上的差别，也有在同一层次上不同权重的差别；（4）线性规划寻找最优解，而许多实际问题只需要找到满意解就可以了。1.2目标规划的数学模型1.2.1目标规划的基本概念为了克服线性规划的局限性，目标规划采用如下手段。1.设置偏差变量用偏差变量来表示实际值与目标值之间的差异，令d+为超出目标的差值，称为正偏差变量；d-为未达到目标的差值，称为负偏差变量。其中d+与d-至少有一个为0。当实际值超过目标值时，有d-=0，d+0;当实际值未达到目标值时，有d+=0，d-0；当实际值与目标值一致时，有d+=d-=0。2.统一处理目标与约束在目标规划中，约束有两类，一类是对资源有严格限制的，同线性规划的处理相同，用严格的等式或不等式约束来处理，例如，用目标规划求解例8.1，设备A禁止超时使用，则有刚性约束：122212.xx另一类约束是可以不严格控制的，连同原线性规划的目标，构成柔性约束。例如，在求解例8.1中，我们希望利润不低于1500元，则目标可表示为12min;2003001500.dxxdd甲，乙两种产品的产量尽量保持1：2的比例，则目标可表示为12min;20.ddxxdd设备C可以适当加班，但要控制，则目标可表示为2min;515.dxdd设备B既要求充分利用，又尽可能不加班，则目标可表示为1min;416.ddxdd从上面的分析可以看到，如果希望不等式保持大于等于，则极小化负偏差；如果希望不等式保持小于等于，则极小化正偏差；如果希望保持等式，则同时极小化正、负偏差。3.目标的优先级与权系数在目标规划模型中，目标的优先分为两个层次。第一个层次是目标分成不同的优先级，在计算目标规划时，必须先优化高优先级的目标，然后再优化低优先级的目标。通常以P1，P2，……表示不同的因子，并规定1kkPP。第二个层次是目标处于同一优先级，但两个目标的权重不一样，因此两目标同时优化，但用权系数的大小来表示目标重要性的差别。1.2.2目标规划模型的建立总的来讲，目标规划在建模中，除刚性约束必须严格满足外，对所有目标约束均允许有偏差。其求解过程要从高到低逐层优化，在不增加高层次目标的偏差值的情况下，逐次使低层次的偏差达到极小。例1.3用目标规划方法求解例1.1，建立相应的目标规划模型。解：在例1.1中设备A是刚性约束，其余是线性约束。首先，最重要的指标是企业的利润，因此，将它的优先级列为第一级；其次，甲、乙两种产品的产量尽量保持1：2的比例，列为第二级；再次，设备C，B的工作时间要有所控制，列为第三级。在第三级中，设备B的重要性是设备C的三倍，因此，它们的权重不一样，设备B前的系数是设备C前系数的3倍。由此得到相应的目标规划模型。112223334121211122213324412min()(33);..2212,2003001500,20,416,515,,,,0,1,2,3,4iizPdPddPdddstxxxxddxxddxddxddxxddi通过上述实例，可以给出目标规划的一般数学表达式。1.2.3目标规划的一般模型设(1,2,,)jxjn…是目标规划的决策变量，共有m个约束是刚性约束，可能是等式约束，也可能是不等式约束。设有l个柔性目标约束，其目标规划约束的偏差为,(1,2,)iidd…，l，设有q个优先级别，分别为12,,.qppp…在同一个优先级kP中，有不同的权重，分别记为,(1,2,kjkjwwj…，l).因此目标规划模型的一般数学表达式为：1111min();..(,),1,2,,1,2,0,1,2,,0,1,2,qlkkjjkjjkjnijjijijjiiijiizPwdwdstaxbicxddgijddinj?m,?l,x?n,?l.1.2.4求解目标规划的序贯式算法序贯式算法是求解目标规划的一种早期算法，其核心是根据优先级的先后次序，将目标规划问题分解成一系列的单目标规划问题，然后再依次求解。算法1.1（求解目标规划的序贯式算法）对于k=1,2,……,q,求解单目标规划问题111*1min();..(,),1,2,,1,2,(),1,2,0,1,2,,0,1,2,lkkjjkjjjnijjijijjiiijlsjjsjjsjiizwdwdstaxbicxddgiwdwdzsjddinj?m,?l,?k-1,x?m,?l.其最优目标值为*kz，当k=1时，第三个约束为空约束。当k=q时，*qz所对应的解*x为目标规划的最优解。例1.4用算法1.1求解例1.3。相关LINDO程序为：MINDMINUS1SUBJECTTO2X1+2X2=12200X1+300X2-DPLUS1+DMINUS1=15002X1-X2-DPLUS2+DMINUS2=04X1-DPLUS3+DMINUS3=165X2-DPLUS4+DMINUS4=15END计算结果如下：LPOPTIMUMFOUNDATSTEP5OBJECTIVEFUNCTIONVALUE1)0.0000000E+00VARIABLEVALUEREDUCEDCOSTDMINUS10.0000001.000000X13.0000000.000000X23.0000000.000000DPLUS10.0000000.000000DPLUS23.0000000.000000DMINUS20.0000000.000000DPLUS30.0000000.000000DMINUS34.0000000.000000DPLUS40.0000000.000000DMINUS40.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.0000000.0000003)0.0000000.0000004)0.0000000.0000005)0.0000000.0000006)0.0000000.000000NO.ITERATIONS=5目标函数的最优值为0，即第一级偏差为0。求第二级偏差，列出LINGO程序如下：MINDPLUS2+DMINUS2SUBJECTTO2X1+2X2=12200X1+300X2-DPLUS1+DMINUS1=15002X1-X2-DPLUS2+DMINUS2=04X1-DPLUS3+DMINUS3=165X2-DPLUS4+DMINUS4=15DMINUS1=0END计算结果如下：LPOPTIMUMFOUNDATSTEP2OBJECTIVEFUNCTIONVALUE1)0.0000000E+00VARIABLEVALUEREDUCEDCOSTDPLUS20.0000001.000000DMINUS20.0000001.000000X11.8750000.000000X23.7500000.000000DPLUS10.0000000.000000DMINUS10.0000000.000000DPLUS30.0000000.000000DMINUS38.5000000.000000DPLUS43.7500000.000000DMINUS40.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.7500000.0000003)0.0000000.0000004)0.0000000.0000005)0.0000000.0000006)0.0000000.0000007)0.0000000.000000NO.ITERATIONS=2目标函数最优值还是0，即二级偏差仍为0。求第三级偏差，列出LINGO程序：MIN3DPLUS3+3DMINUS3+DPLUS4SUBJECTTO2X1+2X2=12200X1+300X2-DPLUS1+DMINUS1=15002X1-X2-DPLUS2+DMINUS2=04X1-DPLUS3+DMINUS3=165X2-DPLUS4+DMINUS4=15DMINUS1=0DPLUS2+DMINUS2