系统工程---第五章 目标规划.ppt

第五章 目标规划,5.1 目标规划数学模型的建立 5.2 目标规划的图解法 5.3 目标规划的分层单纯形法 5.4 目标规划应用案例 5.4 目标规划应用案例,5.1 目标规划数学模型的建立,5.1.1 多目标规划简介 5.1.2 以多目标规划模型建立目标规划模型 5.1.3 以单目标规划模型建立目标规划数学模型 小结 作业,5.1 目标规划数学模型的建立,5.1.1 多目标规划简介,多目标问题最早是由Franklin在1772年提出来的，最早的多目标问题的经济模型是Cournot于1838年提出的。1896年，Pareto首次从数学的角度提出多目标最优化问题，后来，Von Neumann，Koopmans及Kohntucker，Charnes，Karlin，Polak等人又做了许多较有影响的工作。今天，多目标规划受到了人们的普遍重视。,5.1 目标规划数学模型的建立,5.1.1 多目标规划简介,（1）问题的提出及数学模型的建立,在实际问题中，常常需要研究在某些限制条件下，同时考虑多个目标的最优化问题。例如，人们购买一件物品，既要求价廉又要求物美，这就包含了两个目标。再把购买物品具体到购买一件衣服，可能要考虑质量、颜色、式样、大小、价格这五个目标。又如选择一个新厂址，除了考虑运费、造价、燃料供应费等经济指标外，还要考虑对环境的影响等社会因素。,我们可以通过下面几个实例来具体了解多目标规划问题的提出及数学模型的建立：,5.1 目标规划数学模型的建立,5.1.1 多目标规划简介,（1）问题的提出及数学模型的建立,5.1 目标规划数学模型的建立,5.1 目标规划数学模型的建立,5.1 目标规划数学模型的建立,当然，生产时间应为非负，故还有,综合上面的讨论，所考虑的生产计划问题可归纳为下面具有三个目标的最优化问题：,5.1 目标规划数学模型的建立,Vector Optimization,5.1 目标规划数学模型的建立,为使投资所用的资金尽可能地少，应使,5.1 目标规划数学模型的建立,为使获得的收益最大，又应要求,由于该公司的总资金为A万元，故要有限制条件,与前面的假设： xi=0或1的关系？,5.1 目标规划数学模型的建立,综上所述，所考虑的投资决策问题可归为对两个目标中的一个极小化，对另一个极大化的如下问题：,5.1 目标规划数学模型的建立,类似上述要考虑的多目标最优化问题的例子还可以举出很多。例如: 为制定国家的经济发展规划，在一定条件下就需要考虑以生产、消费、就业、投资回收率等项目的多个目标的最优化问题； 设计货船，人们通常要考虑选取使船舶的试航速率最大，年货运量最多和运输成本最低等多个目标都尽可能好的方案； 为了编制人才培养计划，在某些限制条件下亦需同时考虑以各级人员数额、升调面比率和工资总额等多个目标的最优化问题； 为合理地使用医院的血库，也会遇到以血液库存量、血液平均寿命以及血液收集费用等为目标的多个目标的最优化问题；等等。 这些例子说明，在实际应用中，具有多个目标的最优化问题是广泛的和大量存在的。,5.1 目标规划数学模型的建立,在把实际问题建立成多目标规划模型时，我们应注意以下三点： （1）决策变量。选择并确定所考虑的问题的供选方案，并把它们用一组变量表示出来。这些变量取不同的一组值对应着问题的一个不同方案。 （2）目标函数。按照决策者的意图，对问题提出期望要极小化或极大化若干个目标（指标），它们是决策变量的函数，并且一起组成一个向量目标函数。 （3）约束条件。寻找并建立决策变量必需满足的所有限制条件，并用含有决策变量的不等式或等式表示之。,5.1 目标规划数学模型的建立,（2）基本概念,考虑如下的向量函数：,5.1 目标规划数学模型的建立,（2）基本概念,5.1 目标规划数学模型的建立,单目标规划与多目标规划的区别,5.1 目标规划数学模型的建立,5.1.2 以多目标规划模型建立目标规划模型,5.1 目标规划数学模型的建立,5.1 目标规划数学模型的建立,5.1 目标规划数学模型的建立,5.1 目标规划数学模型的建立,5.1 目标规划数学模型的建立,对目标函数来说，由于决策者偏爱程度的不同，导致对不同目标函数逼近于其目标值的要求程度也不同。若要在模型中将决策者的这一偏爱关系体现出来，有两种方法可以利用，即权系数法和优先层次法。,5.1 目标规划数学模型的建立,5.1 目标规划数学模型的建立,5.1 目标规划数学模型的建立,5.1 目标规划数学模型的建立,5.1 目标规划数学模型的建立,5.1.3 以单目标规划模型建立目标规划数学模型,下面，通过一个例子来说明利用单目标规划模型建立目标规划模型的过程。,5.1 目标规划数学模型的建立,5.1 目标规划数学模型的建立,5.1 目标规划数学模型的建立,建立目标规划的数学模型时，需要确定目标值、优先层次、权系数等，它都具有一定的主观性和模糊性，可以通过组织专家进行评估给以量化。,5.1 目标规划数学模型的建立,小结 目标规划数学模型中的基本要素：,负偏差变量d -: 表示决策值不足目标值部分。 d - 0,变量约束：xj 0 j=1,2,n d + 0 , d - 0,1、变量：,决策变量x1, x2, xn:表示决策问题的计划产品产量或计划生产 时间。,正偏差变量d +: 表示决策值超过目标值部分。 d + 0,2、约束条件：,绝对约束(硬约束)：必须严格满足的等式约束或不等式约束。,目标约束(软约束)：含有d -, d +的约束。通常用等式来描述。,5.1 目标规划数学模型的建立,小结 目标规划数学模型中的基本要素：,3、目标函数：,(3) 要求不超过目标：,目标优先级（优先因子）： P1 P2 PL 同一级中可以有若干个目标：f21 , f22 , f23 其重要程度用权重系数w21 ,w22 ,w23 表示,(1) 要求恰好达到目标：,min f = d -+d+,(2) 要求超过目标：,min f= d -,min f= d +,5.1 目标规划数学模型的建立,小结,目标规划：求一组决策变量的满意值，使决策结果与给定目标 总偏差最小。, f = 0：各级目标均已达到 f 0：部分目标未达到。, 目标函数中只有偏差变量、优先因子、权系数。, 目标函数总是求偏差变量最小。,5.1 目标规划数学模型的建立,作业 什么叫非劣解（满意解）？说明非劣解与最优解的区别。 说明目标规划模型中的正、负偏差变量与松弛变量（剩余变量）、人工变量的区别。,5.2 目标规划的图解法,目标规划的图解法 作业,5.2 目标规划的图解法,Step2. 根据目标函数中的优先因子来分析求解： 1.先考虑P1优先因子的目标的实现; 2.再考虑P2优先因子的目标的实现; 3.最后考虑P3优先因子的目标的实现。, 图解法的主要步骤：,Step1在平面直角坐标系内，作各约束条件：,1.先画出绝对约束条件（画法同线性规划图解法）；,2.再画出目标约束条件：,先令 di- = di+ =0，作相应直线；,在直线旁标上di- 、 di+ ，表明目标约束可沿di- 、 di+所示方向平移（平移方向是使di- 或 di+ 增加的方向）。,对只具有二个决策变量的目标规划的数学模型，可以用图解法来分析求解。我们用例5-3来说明具体求解过程。, 有效解为GD线段： G=(2,4) 利润=56 D=(10/3,10/3)利润=60,5.2 目标规划的图解法,例5-4 用图解法求解例5-3。,d3+,5,x2,11,10,10,5,7,x1,A,B,C,D,E,G,d2+,d1-,x1+2x2 = 10,x1 -x2=0,8x1+10x2=56,2x1+x2 =11,O,d1+,d2-,d3-,解：1在平面直角坐标系内，做约束条件。,2根据目标函数中的优先因子来分析求解：, 可行域OAB, 目标1： OBC,目标2：ED线段,目标3：GD线段, min f =0,5.2 目标规划的图解法,5.2 目标规划的图解法,用图解法求解，见下图：,1. 满足目标、的满意域为ABCD,2. 先考虑的满意域为ABEF,3. 在满足目标、 、 的基础上，使得 d4- 最小的是E点(24,26)，获利2960。,4. min f =d4- = 4,再考虑，无公共满意域。,min f=P1d1-+P2d2+P3(2d3-+d4-)(目标函数),因此，该厂每周应装配彩色电视机24台，黑白电视机26台。,5.2 目标规划的图解法,作业 用图解法找出以下目标规划问题的有效解。,5.3 目标规划的分层单纯形法,目标规划的分层单纯形法 作业,5.3 目标规划的分层单纯形法,伊杰尼（YIjiri）1965年在提出目标的优先等级和优先权因子的概念的基础上，给出了改进的“目标规划”的分层单纯形算法。 目标规划模型的数学模型结构与线性规划的数学模型结构没有本质的区别，所以其计算方法与单纯形法类似。但要考虑目标规划数学模型的一些特点，作以下规定：,5.3 目标规划的分层单纯形法,解目标规划问题的分层单纯形法的计算步骤：,5.3 目标规划的分层单纯形法,例5-6 试用分层单纯形法求解例5-3。,5.3 目标规划的分层单纯形法,5.3 目标规划的分层单纯形法,依此类推，直至得到最终单纯形表为止（见表5-5）。,5.3 目标规划的分层单纯形法,作业 用分层单纯性法求解以下目标规划问题的有效解:,5.4 目标规划应用案例,案例1 目标规划在升级调资中的应用 案例2 产品分销决策的目标规划法 案例3 优化布雷兵力任务区分的目标规划方法,5.4 目标规划应用案例,案例1 目标规划在升级调资中的应用,某单位领导在考虑本单位职工的升级调资方案时，依次遵循以下规定： 1）尽量不超过月工资总额60000元。 2）每级的人数尽量不超过定编规定的人数。 3），级的升级面尽可能达到现有人数的20%。 4）级不足编制的人数可录用新职工，又级的职工中有10%要退休。 有关资料汇总于下表中，问：单位领导应如何拟定一个满意方案？,5.4 目标规划应用案例,案例分析： 设x1，x2， x3分别表示提升到、级和录用到级的新职工人数。,先对各目标确定的优先因子为：,再分别建立各目标约束 ：,（1）年工资总额不超过60000元：,并要求,5.4 目标规划应用案例,（2）每级的人数不超过定编规定的人数：,对级有,对级有,对级有,（3）、的升级面尽可能达到现有人数的20% ：,对级有,对级有,（4）目标函数,并要求,并要求,5.4 目标规划应用案例,综上，可得该单位职工的升级调资问题的目标规划的数学模型如下：,5.4 目标规划应用案例,以上目标规划模型可用分层单纯形法求解，得到多重解。现将这些解汇总下表，这个单位负责人再按具体情况，从下表中选一个执行方案。,5.4 目标规划应用案例,案例2 产品分销决策的目标规划法,1基本假设,案例分析：,5.4 目标规划应用案例,5.4 目标规划应用案例,（4）建立模型,根据上述假设，可构建企业产品分销的目标规划模型的一般形式如下：,5.4 目标规划应用案例,2企业产品分销的目标规划模型的建立,为了应用前面建立的一般线性目标规划模型建立该企业自身的产品分销模型，下面根据该企业的总体经营目标确定出各个目标的相对重要程度，进而拟定该企业各目标的优先级。,5.4 目标规划应用案例,5.4 目标规划应用案例,目标要求：尽量达到目标分销水平的要求。,5.4 目标规划应用案例,第二优先级(P2)分析：,由以上分析，在第一优先级里面有目标分销量小于现实的已经达到的分销量的情况，企业为了不降低市场占有率，在保证第一优先级的前提下确定出第二优先级（即尽量保持目标分销量不小于现实的分销量），因此由表5-8可以得到第二优先级的约束条件如下：,目标要求：尽量不低于现实分销水平的要求。,5.4 目标规划应用案例,第三优先级(P3)分析：,由于分销水平与市场占有率呈正方向变化，所以根据消费者偏好调整之后的产品分销结构，将提高产品的分销水平，同时也会提高企业产品的市场占有率。 因此，企业目标之一是在这些市场上每种酒的市场占有率都能提高，在此把它作为第三优先级。,于是可以利用该企业历年的市场占有率和分销水平之间的统计数据，得出该企业的3种酒的市场占有率与分销水平的回归方程如下：,5.4 目标规划应用案例,由上面分析可以得出该优先级的约束条件如下：,类似可以得到,目标要求：每种酒的市场占有率都能获得有效提高（不低于现实市场占有率的103%）,5.4 目标规划应用案例,第四优先级（P4）分析：,由于产品分销水平和市场占有率提高，这将促使企业的销售利润提高。因此企业的利润目标是在每个市场上都增加利润，为了得出相应的目标约束，根据市场调研得到的数据进行整理，并分别对各类市场同类产品下年度的销售量做出预测，如表5-9所示。,根据表5-9和三种酒的市场占有率与分销水平的回归方程，可以得到该优先层次的约束条件如下：,5.4 目标规划应用案例,类似可以得到 ：,目标要求：企业在三个市场上分别获得的利润不低于目标利润。,5.4 目标规划应用案例,经过以上分析，可以得到企业产品分销的目标规划模型如下：,5.4 目标规划应用案例,3计算结果及相关问题讨论,由表5-10可以看出： （1）决策变量最优解完全等于执行第一、二优先级期望的目标； （2）第三优先级的目标是在每一个市场的市场占有率平均增加3， 这可以将最优的分销水平代入前述的市场占有率与分销水平的回 归方程，算出最优分销水平下的市场占有率。,5.4 目标规划应用案例,现将其与现在的、目标的市场占有率列入表5-11。,5.4 目标规划应用案例,综上分析，在前述的优先层次情况下得到的最优解将使企业预订的利润目标在成都和重庆二个市场不能达到，使企业的市场占有率目标在重庆市场不能达到。 如果企业的决策者认为这种结构虽然满足了消费者的需求，但是无法达到自己的利润和市场目标，这不符合企业的追求利润最大化的宗旨,，那么此时只要调整优先层次顺序，可以把利润目标作为第一优先层次考虑，然后依次考虑相应的优先层次，建立新的模型，求解模型便可以得到新的产品分销结构。因此，改变目标优先层次结构可以产生不同的分销计划方案和方案的不同执行结果。 类似的方法可以产生若干个可供选择的方案提供给企业决策者，由决策者综合考虑、权衡利弊后做出选择。,5.4 目标规划应用案例,案例3 优化布雷兵力任务区分的目标规划方法,海上封锁战役是海军未来面临的主要作战样式之一。其中，水雷封锁因其代价小、威力大和容易使用，在封锁作战中占有重要地位。特别是双方存在技术差的情况下，水雷更是一种对付高技术对手的有效武器。在未来海洋方向的军事斗争中，大规模的水雷封锁能产生全局性的影响，从而具有巨大的实际效力和威慑力。 水雷封锁作战的关键是布雷行动。大规模布雷行动参战兵力多、限制条件多、组织复杂，行动方案是否科学合理对行动效果和代价影响极大。因此，对行动方案进行定量分析和优化十分必要。,5.4 目标规划应用案例,1基本假设,5.4 目标规划应用案例,由表5-13可见，X型水雷的总投放能力（1350枚）小于计划投放数量（1600枚），而Y型水雷的总投放能力（850枚）则大于计划投放数量（800枚）。,5.4 目标规划应用案例,目标约束1（仅适用于X型水雷）： 由于雷区D4距离远，对此雷区的布雷任务只能使用潜艇或作战半径较大的中型轰炸机，但机场A3没有中型轰炸机，因此机场A3无法对雷区D4布雷。,5.4 目标规划应用案例,目标约束2（仅适用于X型水雷）： 由于雷区D4的水文地质条件只适合于布设X型水雷，为了保证该雷区有足够的杀伤概率，要求在该雷区实际布设的X型水雷的数量力争不小于200枚。,目标约束3（仅适用于X型水雷）： 鉴于X型水雷的布雷能力不足，因此必须重点保证主要雷区的需要。由于雷区D2和D3位于敌主要港口附近，因此这两个雷区的X型水雷实际布雷数量不得小于计划布雷数量的90以保证该雷区的杀伤概率不至于降低过多。,5.4 目标规划应用案例,目标约束4（仅适用于X型水雷）： 在重点保证主要雷区需要的前提下，应将剩余的水雷比较平均地用于雷区D1和D5，使雷区D1和D5的实际布雷数量不小于计划布雷数量的75，以避免任一个雷区的杀伤概率降低过多。,目标约束5： 由于雷区D2和D3所在海区内敌方防空力量较强，因此最好由潜艇执行在这些雷区的布雷任务，以降低受敌威胁程度。,5.4 目标规划应用案例,目标约束6（仅适用于X型水雷）： 为了缩短整个布雷行动所消耗的时问，应尽量对距离较远的雷区D4采用空中布雷方式。鉴于约束1的限制，即应尽量使用机场A1和A2的中型轰炸机对该雷区布雷。,5.4 目标规划应用案例,目标约束6（仅适用于X型水雷）： 为了缩短整个布雷行动所消耗的时问，应尽量对距离较远的雷区D4采用空中布雷方式。鉴于约束1的限制，即应尽量使用机场A1和A2的中型轰炸机对该雷区布雷。,目标约束7（仅适用于Y型水雷）： 由于Y型水雷的布雷能力超出计划布雷数量，考虑到潜艇航速慢，为了缩短整个布雷行动所消耗的时问，应优先使用空中布雷兵力。 目标约束8： 为了尽可能缩短整个布雷行动的完成时间和降低消耗，应尽量让各机场和各基地的兵