运筹学4 目标规划.ppt

1、,运筹学 Operations Research,1. 目标规划数学模型 Mathematical Model of GP 2. 目标规划的图解法 The graphical method of GP 3. 单纯形法 Simplex Method,Chapter 4 目标规划 Goal Programming,本章您将学到以下内容： 什么是目标规划，目标规划与线性规划有哪些联系和区别 目标规划数学模型的构成及其特征 目标规划的图解法、单纯形法 目标规划的应用,2020年9月2日星期三,在现实经济生活中，没有最优（max,min）只有满意。,从亚当斯密斯开始,资产阶级经济学家的一个基本假设就是认

2、为企业的决策者是“ 经济人”,他们的行为只受“ 最大化”的行为准则所支配，只以追求最大经济利益（利润）为唯一目标。,社会的发展已经证明，“ 经济人”的假设根本不适应现代管理的需要。,H.A.西蒙(H.A.Simon-美国卡内基-梅隆大学,1916-)教授着眼于现代企业的管理职能,否定了“ 经济人”概念和“ 最大化”行为准则，提出了“ 管理人”的概念和“ 令人满意”的行为准则。,最优和满意,2020年9月2日星期三,由于西蒙教授对现代经济管理的决策科学进行了开创性的研究，荣获了1978年诺贝尔经济学奖。,他提出满意行为模型要比最大化行为模型丰富得多。从而现代管理决策所追求的不是绝对意义下的最优解

3、，而是相对意义下的满意解。,目标规划的有关概念和模型最早在年由美国学者.查恩斯和.库伯在他们合著的管理模型和线性规划的工业应用一书中提出，以后这种模型又先后经尤吉艾吉里、杰斯基莱恩和桑.李不断完善改进。年伊格尼齐奥发表了目标规划及其扩展一书，系统归纳总结了目标规划的理论和方法。 下面通过例子来具体说明什么是目标规划以及它和线性规划的区别。,2020年9月2日星期三,【例4.】某企业计划生产I、II两种产品，这些产品分别 要在A、B、C、D四种不同设备上加工。工艺资料如表41所示。,问该企业应如何安排计划，使在计划期内的总利润收入为最大?,表41,2020年9月2日星期三,【解】设、II 产品的

4、产量分别为x1、x2，可以建立这个问题的线规划模型如下：,并可求出最优解为x8，x9，Z280元。,2020年9月2日星期三,现在企业的经营目标不仅仅是利润，而是考虑多个方面，如： (1)力求使利润指标不低于250元； (2)考虑到市场需求，、II两种产品的生产量需保持：2的比 (3)和为贵重设备，严格禁止超时使用； (4)设备A既要求充分利用，又尽可能不加班。 (5) 设备B必要时可以加班，但加班时间要控制；,1. 设置偏差变量，用来表明实际值同目标之间的差异。偏差变量用下列符号表示：,d1 ：超出利润目标的差值，称正偏差变量 d1 ： 未达到利润目标的差值，称负偏差变量,力求使利润指标不低

5、于250元，可表为：,2020年9月2日星期三,2. 设 d2 ：超出产品比例目标的差值 d2 ： 未达到产品比例目标的差值,要求I、II两种产品保持1：2的比例，当作一个约束，可以写为：,x1/x2=2 或x12x2=0,这是系统约束或称刚性约束。由于对这个比例允许有偏差 ，但希望正负偏差最小，因此有,3. 设 d3 ：超出设备A的加工能力的差值 d3 ： 未达到设备A的加工能力的差值，根据要求有,2020年9月2日星期三,4. 设 d4 ：超出设备B的加工能力的差值 d4 ： 未达到设备B的加工能力的差值，根据要求有,设备C、D的加工时间不允许超过现有加工能力，则有,2020年9月2日星期

6、三,5.目标的优先级与权系数。在一个目标规划的模型中，如果两个不同目标重要程度相差悬殊，为达到某一目标可牺牲其它一些目标，称这些目标是属于不同层次的优先级。优先级层次的高低可分别通过优先因子P1，P2表示，并规定PkPk+1即不同优先级之间的差别无法用数字大小衡量。对属于同一层次优先级的不同目标，按其重要程度可分别乘以不同的权系数。权系数是一个具体数字，乘上的权系数越大，表明该目标越重要。,现假定例4.1中企业的最重要目标是利润，列为第一优先级；其次目标是I、II产品的产量尽可能保持1：2的比例，列为第二优先级；再次是设备A、B尽量不超负荷工作，列为第三、第四优化先级。,2020年9月2日星期

7、三,上述问题的目标规划模型可以写为：,2020年9月2日星期三,【例4.2】(教材P109) （） 不超过年工资总额60000元； （） 每级人数不超过定编人数； （） 、级的升级面到达或超过现有人数的20； （） 级不足人数可录用新职工，级职工有10退休，退休工资由社会发放。,2020年9月2日星期三,P1不超过年工资总额60000元,偏差变量为,2000(9x1)1500(12x1x2)1000(15x2x3) 60000,【解】设x1由级升到级的人数 x2由级升到级的人数 x3录用的新职工人数,500 x1500 x21000 x3 9000,2020年9月2日星期三,P3、级的升级面到

8、达或超过现有人数的20,级偏差变量为,级偏差变量为,2020年9月2日星期三,2020年9月2日星期三,目标规划的一般数学模型可表为：,式中: Pk为第k级优先因子，k=1,K; 为分别赋予第l个目标约束的正负偏差变量的权系数； gl为目标的预期目标值，l=1,L。 （4.2c）为目标约束，(4.2b)为系统约束。,2020年9月2日星期三,本节介绍了如何建立目标规划的数学模型。,您学完本节后，应深刻领会下列概念：,1.目标规划由哪些要素构成，与线性规划有哪些不同之处；,2.偏差变量的含义及其作用；,3.目标函数的表达方法；,4.优先级别的含义。,1正偏差变量大于等于零，负偏差变量小于等于零.

9、 2系统约束中没有偏差变量. 3目标约束含有偏差变量. 4一对正负偏差变量至少一个大于零.,试一试，判断下列各结论是否正确：,2020年9月2日星期三,5一对正负偏差变量至少一个等于零.,8目标规划没有系统约束时，一定存在满意解.,9超出目标的差值称为正偏差.,10未到达目标的差值称为负偏差.,6要求至少到达目标值的目标函数是,7要求不超过目标值的目标函数是,图解法,作业: 教材P112 4.1 4.2 补充作业,Exit,2020年9月2日星期三,对模型中只含两个变量（偏差变量不计入）的目标规划问题，可以用图解分析的方法找出满意解。【例4.3】,(a),(b),(c),(d ),x2,x1,

10、(e),(f),d1-,d1+,d2+,d2-,d3-,d3+,d4-,d4+,满意解(3,3),0,4,6,8,3,4,6,2,2,【例4.3】,x1,x2,(a),(b),d1+,d1-,(c),d2-,d2+,(d),d3-,d3+,G,D,满意解是线段GD上任意点,其中G点X(2,4),D点X(10/3,10/3),0,5.5,10,5,5.6,11,2,4,10/3,10/3,5,10,7,【例4.4】教材P106,O,x1,x2,20,40,60,50,20,40,60,50,a,b,d1-,d1+,d2-,d2+,c,d,d3-,d3+,d4-,d4+,(24,26),满意解X=

11、(24，26),【例4.5】教材P104例3,2020年9月2日星期三,作业：教材P112 T4.1 4.2,单纯形法,Exit,2020年9月2日星期三,目标规划的数学模型与线性规划基本相同，所以用单纯形法求解时的方法步骤也基本相同。但由于目标规划中目标函数分不同的优先级，因此应首先寻求使最高优先级的目标优化，然后转向下一级，当下一级目标优化后再转更低一级，等等。下面用例子具体说明。,【例1】用单纯形法求解下述目标规划问题：,2020年9月2日星期三,【解】用单纯形法求解目标规划问题的具体步骤如下：,第步：列出初始单纯形表。由于目标规划中的目标函数一定是求极小，为方便起见不转换成求极大。又由

12、于各目标约束中的负偏差变量其系数均为单位向量，全部负偏差变量的系数列向量构成一个基。因此本例中以d1、d2、d3作为基变量，列出初始单纯形表见表41。,因为目标函数中各偏差变量分别乘以不同的优先因子，因此表中检验数（cjzj）按优先因子1、2分成两行，分别计算。,第步：确定换入变量。在表4中按优先级顺序依次检查1,P2,3,，k行的（cjzj）值是否有负的。因表中1行存在负检验数，说明目标函数中第一优先级可进一步优化，选取1行中最小检验数，其对应变量x1即为换入变量。 第步：确定换出变量，将表4中b列数字同x1列中的正数相比，其最小比值对应的变量d1 即为换出变量。 第步：用换入变量替换基变量中的换出变量，进行迭代运算，得表4。,2020年9月2日星期三,表1,表2,2020年9月2日星期三,表3,表4,2020年9月2日星期三,这里需要说明两点： 1对目标函数的优化是先按优先顺序逐步进行的。当P1行的所有检验数均为非负时，说明第一级已得到优化，可转入下一级，再考察P2行的检验数是否存在负值，依此类推。,2从考察P2行以下的检验数时，注意应包括更高级别的优先因子在内，例如表3最下面P2行有两个负值，其对应的变量d1的检验数为（P1P2）0，变量d2的检验数为(P12P2) 0。因此判断迭