7运筹学之目标规划(胡运权版)

1第七章目标规划§1目标规划的提出线性规划问题是讨论一个给定的线性目标函数在一组线性约束条件下的最大值或最小值问题。对于一个实际问题，管理科学者根据管理层决策目标的要求，首先确定一个目标函数以衡量不同决策的优劣，且根据实际问题中的资源、资金和环境等因素对决策的限制提出相应的约束条件以建立线性规划模型；然后用计算机软件求出最优方案并作灵敏度分析以供管理层决策之用。而在一些问题中，决策目标往往不只一个，且模型中有可能存在一些互相矛盾的约束条件的情况，用已有的线性规划的理论和方法无法解决这些问题。因此，1961年美国学者查恩斯（A.Charnes）和库柏（W.W.Coopor）提出了目标规划的概念与数学模型，以解决经济管理中的多目标决策问题。我们将通过几个例子来说明在实际应用中线性规划存在一系列的局限性。例1某厂生产A、B两种产品每件所需的劳动力分别为4个人工和6个人工，所需设备的单位台时均为1。已知该厂有10个单位机器台时提供制造这两种产品，并且至少能提供70个人工。又，A、B产品的利润，每件分别为300元和500元。试问：该厂各应生产多少件A、B产品，才能使其利润值最大？解设该厂能生产A、B产品的数量分别为12,xx件，则有2121212max30050010..46700,1,2.jzxxxxstxxxj图解法求解如下：由上图可得，满足约束条件的可行解集为，即机时约束和人工约束之间产生矛盾，因而该问题无解。但在实际中，该厂要增加利润，不可能不生产A、B两种产品，而由线性规划模型无法为其找到一个合适的方案。例2某厂为进行生产需采购A、B两种原材料，单价分别为70元/公斤和50元/公斤。现要求购买资金不超过5000元，总购买量不少于80公斤，而A原材料不少于20公斤。问如何确定最好的采购方案（即花掉的资金最少，购买的总量最大）？解这是一个含有两个目标的数学规划问题。设12,xx分别为购买两种原材料的公斤数，112,fxx为花掉的资金，212,fxx为购买的总量。建立该问题的数学模型形式如下：311212212121212112min,7050max,7050500080..20,0fxxxxfxxxxxxxxstxxx对于这样的多目标问题，线性规划很难为其找到最优方案。极可能的结果是，第一个方案使第一目标的结果值优于第二方案，同时第二方案使第二目标的结果值优于第一方案。也就是说很难找到一个最优方案，使两个目标的函数值同时达到最优。另外，对于多目标问题，还存在有多个目标存在有不同重要程度的因素，而这也是线性规划所无法解决的。在线性规划的基础上，建立了一种新的数学规划方法——目标规划法，用于弥补线性规划的上述局限性。总的来说，目标规划和线性规划的不同之处可以从以下几点反映出来：1、线性规划只能处理一个目标，而现实问题往往存在多个目标。目标规划能统筹兼顾地处理多个目标的关系，求得切合实际需求的解。2、线性规划是求满足所有约束条件的最优解。而在实际问题中，可能存在相互矛盾的约束条件而导致无可行解，但此时生产还得继续进行。即使存在可行解，实际问题中也未必一定需要求出最优解。目标规划是要找一个满意解，即使在相互矛盾的约束条件下也找到尽量满足约束的满意解，即满意方案。43、线性规划的约束条件是不分主次地等同对待，这也并不都符合实际情况。而目标规划可根据实际需要给予轻重缓急的考虑。§2目标规划的基本概念与数学模型§2.1基本概念在这一小节里介绍与目标规划有关的基本概念。1．偏差变量对于例1，造成无解的关键在于约束条件太死板。设想把约束条件“放松”，比如占用的人力可以少于70人的话，机时约束和人工约束就可以不再发生矛盾。在此基础上，引入了正负偏差的概念，来表示决策值与目标值之间的差异。id——正偏差变量，表示决策值超出目标值的部分，目标规划里规定0id；id——负偏差变量，表示决策值未达到目标值的部分，目标规划里规定0id。实际操作中，当目标值（也就是计划的利润值）确定时，所作的决策可能出现以下三种情况之一：（1）决策值超过了目标值（即完成或超额完成计划利润值），表示为0id，0id；5（2）决策值未达到目标值（即未完成计划利润值），表示为0id，0id；（3）决策值恰好等于目标值（即恰好完成计划利润指标），表示为0id，0id。以上三种情况，无论哪种情况发生，均有id•id=0。2．绝对约束与目标约束绝对约束也称系统约束，是指必须严格满足的等式约束和不等式约束，它对应于线性规划模型中的约束条件。目标约束是目标规划所特有的。当确定了目标值，进行决策时，允许与目标值存在正或负的偏差。因而目标约束中加入了正、负偏差变量。如，例1中假定该企业计划利润值为5000元，那么对于目标函数12max300500zxx，可变换为123005005000iixxdd。该式表示决策值与目标值5000之间可能存在正或负的偏差（请读者分别按照上面所讲的三种情况来理解）。绝对约束也可根据问题的需要变换为目标约束。此时将约束右端项看作所追求的目标值。如，例1中绝对约束1210xx，可变换为目标约束1210iixxdd。3．目标规划的目标函数6对于满足绝对约束与目标约束的所有解，从决策者的角度来看，判断其优劣的依据是决策值与目标值的偏差越小越好。因此目标规划的目标函数是与正、负偏差变量密切相关的函数，我们表示为min,iizfdd。它有如下三种基本形式：（1）要求恰好达到目标值，即正、负偏差变量都尽可能地小。此时，构造目标函数为：miniizdd（2）要求不超过目标值，即允许达不到目标值，正偏差变量尽可能地小。此时构造目标函数为：minizd（3）求超过目标值，即超过量不限，负偏差变量尽可能地小。此时构造目标函数为：minizd4．优先次序系数与权系数一个规划问题往往有多个目标。决策者在实现这些目标时，存在有主次与轻重缓急的不同。对于有K级目标的问题，按照优先次序分别赋予不同大小的大M系数：1M，2M，，KM。1M，2M，，KM为无穷大的正数，并且，1M2MKM（“”符号表示“远大于”），这样，只有当某一级目标实现以后（即目标值为0），才能忽略大M的影响，否则目标偏离量会因为大M的原因而无穷放大。并且由于1kkMM，所以只有先考虑忽略kM影响（实现第k级目标）后，才能考虑第1k级目标。实际上这里的大M是对偏离目标值的惩罚系数，优先级别越高，惩罚系数越大。权系数i用来区别具有相同优先级别的若干目标。在同一优先级7别中，可能包含有两个或多个目标，它们的正负偏差变量的重要程度有差别，此时可以给正负偏差变量赋予不同的权系数i和i。各级目标的优先次序及权系数的确定由决策者按具体情况给出。§2.2目标规划的数学模型综上所述，目标规划模型由目标函数、目标约束、绝对约束以及变量非负约束等几部分构成。目标规划的一般数学模型为：目标函数11minKLkkllkllklZMdd目标约束11,2,nijjllljcxddglL绝对约束1,1,2,nijjijaxbim非负约束01,2,jxjn,01,2,,kkddkK例3在例1中，假定目标利润不少于15000元，为第一目标；占用的人力可以少于70人，为第二目标。求决策方案。解按决策者的要求分别赋予两个目标大M系数12,MM。列出模型如下：81122121112221212min300500150004670..10,,,01,2,3.iizMdMdxxddxxddstxxxxddi例4某纺织厂生产A、B两种布料，平均生产能力均为1千米/小时，工厂正常生产能力是80小时/周。又A布料每千米获利2500元，B布料每千米获利1500元。已知A、B两种布料每周的市场需求量分别是70千米和45千米。现该厂确定一周内的目标为：第一优先级：避免生产开工不足；第二优先级：加班时间不超过10小时；第三优先级：根据市场需求达到最大销售量；第四优先级：尽可能减少加班时间。试求该问题的最优方案。解设12,xx分别为生产甲、乙布料的小时数。对于第三优先级目标，根据A、B布料利润的比值2500:15005:3，取二者达到最大销量的权系数分别为5和3。该问题的目标规划模型为：1122334411211122213324412min538090..7045,,,01,,4.iizMdMdMddMdxxddxxddstxddxddxxddi9综上所述，目标规划建立模型的步骤为：1、根据问题所提出的各目标与条件，确定目标值，列出目标约束与绝对约束；2、根据决策者的需要将某些或全部绝对约束转换为目标约束，方法是绝对约束的左式加上负偏差变量和减去正偏差变量；3、给各级目标赋予相应的惩罚系数kM（1,2,kK），kM为无穷大的正数，且1M2MKM；4、对同一优先级的各目标，再按其重要程度不同，赋予相应的权系数kl；5、根据决策者的要求，各目标按三种情况取值：①恰好达到目标值，取iidd②允许超过目标值，取id③不允许超过目标值，取id；然后构造一个由惩罚系数、权系数和偏差变量组成的、要求实现极小化的目标函数。§3目标规划的求解3.1图解法只有两个决策变量的目标规划数学模型，可以使用简单直观的图解法求解。其方法与线性规划图解法类似，先在平面直角坐标系第一象限内作出各约束等式或不等式的图象，然后由绝对约束确定了可行域，由目标约束和目标函数确定最优解或满意解。10对于绝对约束，与线性规划中的约束条件画法完全相同。对于目标约束方程，除作出直线外，还要在直线上要标出正负偏差变量的方向，其可行域方向取决于目标函数中对应目标。另外，目标规划是在前一级目标满足的情况下再来考虑下一级目标，很有可能尽可能满足目标的解不是可行解（即非可行解），而是权衡以后得出的最优解——满意解。因而在目标规划里称求得的解为满意解。注意在求解的时候，把绝对约束作最高级别考虑。例5用图解法求解目标规划问题11122331211122212331212min03515..43247,,,01,2,3.iizMddMdMdxxddxxddstxxddxxxxddi解在平面直角坐标系第一象限内作出各约束条件的图像，目标约束要在直线旁标上id和di+。11首先，绝对约束127xx确定了可行解范围在三角形OEF内；根据第一级目标，要求实现11mindd（恰好），因而可行解范围缩小到线段OC上；根据第二级目标，要求实现2mind（不少于），在线段OC上，取20d的点A，此时可行解范围缩小到线段AC上；根据第三级目标，要求实现3mind，在线段AC上，取30d的点B，此时解的范围缩小到线段AB上。所以，线段AB上的所有点为满意解。可求得A(15/8,15/8)，B(24/7,24/7)。2.winQSB求解目标规划[例]求解目标规划：1122331211222133121212min1078..62603460,,,0,1,2,3jjzPdPdPdxxddxddxddstxxxxxxddj第1步：生成表格选择“程序winQSBGaolProgrammingFileNewProgram”，弹出对话框：12输入：目标约束数（NumberofGoals）“3”决策变量数（NumberofVariables）“2”系统约束数（NumberofConstraints）“2”目标要求（DefaultGo