运筹学第9讲目标规划.

目标规划目标规划举例：例9.1企业生产不同企业的生产目标是不同的。多数企业追求最大的经济效益。但随着环境问题的日益突出，可持续发展已经成为全社会所必须考虑的问题。因此，企业生产就不能再如以往那样只考虑企业利润，必须承担起社会责任，要考虑环境污染、社会效益、公众形象等多个方面。兼顾好这几者关系，企业才可能保持长期的发展。目标规划目标规划举例：例9.2商务活动企业在进行盈亏平衡预算时，不能只集中在一种产品上，因为某一种产品的投入和产出仅仅是企业所有投入和产出的一部分。因此，需要用多产品的盈亏分析来解决具有多个盈亏平衡点的决策问题（多产品的盈亏平衡点往往是不一致的）。目标规划目标规划举例：例9.3投资企业投资时不仅仅要考虑收益率，还要考虑风险。一般地，风险大的投资其收益率更高。因此，企业管理者只有在对收益率和风险承受水平有明确的期望值时，才能得到满意的决策。例9.4裁员同样的，企业裁员时要考虑很多可能彼此矛盾的因素。裁员的首要目的是压缩人员开支，但在人人自危的同时员工的忠诚度就很难保证，此外，员工的心理压力、工作压力等都会增加，可能产生负面影响。目标规划目标规划举例：例9.5营销营销方案的策划和执行存在多个目标。既希望能达到立竿见影的效果，又希望营销的成本控制在某一个范围内。此外，营销活动的深入程度也决定了营销效果的好坏和持续时间。目标规划例9.6金融投资一位投资商有一笔资金准备购买股票。资金总额为90000元，目前可选的股票有A和B两种（可以同时投资于两种股票）。其价格以及年收益率和风险系数如下表：股票价格(元)年收益(元)/年风险系数A2030.5B5040.2从上表可知，A股票的收益率为（3／20）×100％＝15％，股票B的收益率为4／50×100％＝8％，A的收益率比B大，但同时A的风险也比B大。这也符合高风险高收益的规律。试求一种投资方案，使得一年的总投资风险不高于700，且投资收益不低于10000元。目标规划的数学模型1.目标规划问题的提出应用线性规划，可以处理很多线性系统的最优化问题，但是，线性规划作为一种决策工具，在解决实际问题时，存在着一定的局限性。例9.7某工厂生产两种产品，受原材料和设备工时的限制，在单位利润等数据已知的条件下，要求制定一个获利最大的生产方案。III限量原材料2111设备工时1210利润810目标规划的数学模型解设x1,x2为产品I和II的产量，建立线性规划模型如下：12121212max810211210,0zxxxxxxxx用图解法得到最优解为(4,3)T,最优值为62元。从线性规划的角度来看，问题似乎已经得到圆满的解决，但是，如果站在工厂计划人员的立场进行评价的话，问题就不是这么简单了。目标规划的数学模型第一，这是一个单目标的最优化问题。而在实际决策中，一个计划问题需要满足多方面的要求。例如，财务部门要求尽可能大的利润；物资部门可能希望有尽可能小的物资消耗，以节约储备资金；销售部门可能希望产品品种多样，适销对路；计划部门可能希望有尽可能大的产品批量，以便于安排生产等等。即，一个计划问题实际上是一个多目标决策问题，这个针对单一目标的优化结果违背了某些部门的愿望，使生产计划的实施受到影响。目标规划的数学模型第二，线性规划有最优解的必要条件是可行集非空，即各约束条件彼此相容，但是实际问题有时不能满足这样的要求。例如，在生产计划中，由于储备资金的限制，原材料的最大供应量不能满足计划产量的需要时，从供给和需求两方面产生的约束条件彼此就是互不相容的；或者，由于设备维修、能源供应、其它产品生产需要等原因，计划期内可以提供的设备工时不能满足计划产量工时需要时，也会产生彼此互不相容的情况。目标规划的数学模型第三，线性规划解的可行性和最优性具有十分明确的意义，但那都是针对特定数学模型而言的。在实际问题中，决策者在作决策时，往往还会对它作某种调整和修改，其原因可能是由于数学模型相对于实际问题的近似性。这种近似性一方面来自建模时对实际问题的抽象过程。因此，决策者需要计划人员提供的不是严格的数学上的最优解，而是可以帮助做出最优决策的参考性的计划，或是提供多种计划方案，供最终决策时选择。目标规划的数学模型上述分析表明，同任何其它决策工具一样，线性规划并不是完美无缺的。在处理实际问题时，线性规划存在着由其“刚性”本质所决定的某些固有的局限性。现代决策强调定量分析和定性分析相结合，强调硬技术和软技术相结合，强调矛盾和冲突的合理性，强调妥协和让步的必要性。线性规划无法胜任这些要求。目标规划的数学模型1961年，ACharnes和WCooper提出目标规划(goalprogramming)，得到广泛的重视和较快发展。目标规划在处理实际决策问题时，承认各项决策要求(即使是冲突的)的存在有合理性；在作最终决策时，不强调其绝对意义上的最优性。由于目标规划一定程度上弥补了线性规划的上述局限性，因此，目标规划被认为是一种较之线性规划更接近于实际决策过程的决策工具。目标规划的数学模型2.目标规划模型的构建例9.8计划人员还被要求考虑以下意见：(1)由于II销售疲软，故希望产品II的产量不超过产品I的一半；(2)原材料严重短缺，生产中应避免过量消耗；(3)最好能节约4小时设备工时；(4)计划利润不低于48元。面对这些意见，计划人员需要会同有关各方作进一步的协调，最后达成了一致的意见：原材料试用限额不得突破；产品II产量要求必须优先考虑；设备工时问题其次考虑；最后考虑计划利润的要求。类似这样的多目标决策问题是典型的目标规划问题。目标规划的数学模型要构建目标规划的数学模型，先建立如下的基本概念：(1)偏差变量对一个决策目标，引入正、负偏差变量，分别表示决策值超过或不足目标值的部分，按定义应有dd,0,0dddd0,(2)绝对约束和目标约束绝对约束是目标必须严格满足的约束条件，如线性规划中的约束条件都是绝对约束。绝对约束是硬约束，对它的满足与否，决定了解的可行性。目标约束是目标规划特有的概念，是一种软约束，目标约束中的决策值和目标值之间的差异用偏差变量表示。目标规划的数学模型(3)优先因子和权系数不同目标的主次轻重有两种差别，一种差别是绝对的，可用优先因子Pl来表示，只有在高级优先因子对应的目标已满足的基础上，才能考虑低级优先因子对应的目标；在考虑低级优先因子对应的目标时，绝不允许违背已满足的高级优先因子对应的目标。优先因子之间的关系为，即Pl对应的目标比Pl+1对应的目标有绝对的优先性。另一种差别是相对的，这些目标具有相同的优先因子，它们的重要程度可用权系数的不同来表示。1llPP目标规划的数学模型4.目标规划的目标函数目标规划的目标函数(又称为准则函数或达成函数)由各目标约束的偏差变量及相应的优先因子和权系数构成，由于目标规划追求的是尽可能接近各既定目标值，也就是使各有关偏差变量尽可能小，所以其目标函数只能是极小化。应用时，有三种基本表达式：(1)要求恰好达到目标值。这时，决策值超过或不足目标值都是不希望的，因此取min{f(d++d-)}(2)要求不超过目标值，但允许不足目标值。这时，不希望决策值超过目标值，因此有min{f(d+)}目标规划的数学模型(3)要求不低于目标值，但允许超过目标值。这时，不希望决策值低于目标值，因此有min{f(d-)}根据上述概念，上面的例子的目标规划数学模型如下：1122331212111222123312,min{,,}510602044366848,,0,1,2,3iiPdPdPdxxxxddxxddxxddxxddi在左式的约束中，第一个约束为绝对约束，后面三个为目标约束，根据题意，P1为两种产量产量以前的优先因子；P2为节约工时要求的优先因子；P3为计划利润要求的优先因子，它们满足。123PPP目标规划的数学模型目标规划数学模型的一般形式为：在建立目标规划数学模型时，需要确定预期目标值、优先等级和权系数，应当综合运用各种决策技术，尽可能减少主观盲目性。111min{(()),1,2,,},1,2,,(,),1,2,,0,1,2,,,0,1,2,,KllkklkkknkjjkkkjnijjijjkkklklklPwdwdlLcxddgkKaxbimxjnddkKgkwwP为第个目标约束的预期目标值，和为优先因子对应各目标的权系数。目标规划的图解法对于只含有两个决策变量的目标规划问题，可以用图解法来求解。在用图解法解目标规划时，首先必须满足所有绝对约束。在此基础上，再按优先级从高到低的顺序，逐个地考虑各个目标约束。一般的，若优先因子为、Pj对应的解空间为Rj，则优先因子Pj+1对应的解空间只能在Rj中考虑，即。若，而，则Rj中的解为目标规划的第j级满意解，也只能得到满意解，它只能保证满足P1，P2，……Pj级目标，而不能保证满足其后的各级目标。1jjRRjR1jR目标规划的图解法例9.9利用图解法解例9.8中得到的目标规划模型。解解题过程如右图所示：在上图中，三角形OAB区域是满足绝对约束和非负条件的解空间，对于所有目标约束，去掉偏差变量，划去相应直线，然后标出偏差变量变化时直线平移方向。按优先级高低，首先考虑P1，此时求mind1—，因而解空间R1为三角形OAC区域；再考虑P2级，此时求mind2+，因而解空间R2为三角形ODC区域；目标规划的图解法最后考虑P3，此时要求mind3_，因而解空间R3为四边形EDCF区域。容易求得EDCF四点的坐标为(8,0),(9,0),(6,3),(4.8,2.4)，故此问题的解可表示为a1(8,0)+a2(9,0)+a3(6,3)+a4(4.8,2.4)=(8a1+9a2+6a3+4.8a4,3a3+2.4a4)其中，a1,a2,a3,a4≥0,a1+a2+a3+a4=1.本题解能满足所有目标的要求，即能够使minz=0，这种情况并不总是出现，即很多多目标规划问题只能满足前面Pj级目标的要求。目标规划的图解法例9.8用图解法求解下面的目标规划。11223344112111222123324412,min{,,(53),}2629242,,0,1,2,3,4iiPdPdPddPdxxddxxddxxddxddxxddi目标规划的图解法解解题过程如下图由图可见，在考虑P1和P2的目标后，解空间R2为四边形ABCD区域，在考虑P3的目标时，因为d3-的权系数比d4-的大，所以先考虑mind3-。此时，x1和x2的范围所谓四边形ABEF区域，然后考虑mind4-。但在四边形ABEF区域内无法满足d4-=0，所以退一步，要求在四边形ABEF中找一点，使d4-尽可能小，这一点就是点E(6.5,1.25)，所以问题的满意解为E(6.5,1.25)。用图解法求解下面的目标规划。目标规划的图解法总结：在用图解法解目标规划时，可能会遇到以下两种情况：最后一级目标的解空间非空，这时得到的解能满足所有目标的要求。当解不唯一时，决策者在作实际决策时究竟选择哪一个解，完全取决于决策者自身的考虑。得到的解不能满足所有的目标，这时寻找问题的满意解，使它尽可能满足高级别的目标，同时，又使它对那些不满足的较低级别目标的偏离程度尽可能小。必须注意的是，在考虑低级别目标时，不能破坏已经满足的高级别目标，这是目标规划的基本原则。目标规划的单纯形法目标规划的数学模型实际上是最小化型的线性规划，可以用单纯形法求解。在用单纯形法解目标规划时，检验数时各优先因子的线性组合。因此，在判别各自检验数的正负及大小时，必须注意。当所有检验数都已满足最优性条件时，从最优单纯形表上就可以得到目标规划的解。123PPP目标规划的单纯形法例9.9用单纯形法解前面的例9.7。解引入松弛