目标规划及图解法--运筹学.ppt

清华大学出版社,运筹学教程（第三版）,运筹学基础,胡运权 主编,教材,第四章 目标规划,例1,求利润最大的生产方案,利润 max z= 80 x1 + 100x2,例2,由于各种原因，对例1的提出一些要求： 1、B产品不超过10单位 2、利润不低于1600元 3、充分利用2车间的生产能力，尽量不加班。,目标的含义,本题三个目标依次表示为： 1、B产品不超过10单位 x2 =1600 3、充分利用2车间的生产能力，尽量不加班。 x1 + 2x2 = 40,?,问题分析,1）问题中有些限制是必须满足的，不能有丝毫妥协余地的，如对资源的约束： 2x1 + 1.5x2 50 (1) x1 + 2x2 40 (2) 这些约束条件是一种刚性约束，称之为 系统约束or绝对约束,问题分析,2）除了前面提到的刚性约束外，例2中还提出一些的希望达到的目标。这些要求实际上也是约束条件，当然这些目标能到达最好，实在无法达到也是可以接受的，我们称之为 目标约束,如：1、B产品不超过10单位 2、利润不低于1600元 3、充分利用2车间的生产能力，尽量不加班。,问题分析,3）目标约束的目标一定要明确，给出确切的量值， 即目标期望值,B产品不超过10单位 利润不低于1600元 充分利用2车间的生产能力，尽量不加班,如：,问题分析,4）目标约束不是刚性的，而是弹性的，允许在一定范围内有偏差，这更接近于实际。为表达这种灵活性，便引入了偏差变量的概念，偏差变量有正负之分，表示为：d+和d-， d+表示超过目标值的部分； d-表示不足目标值的部分.显然有d- d+=0,问题分析,本题三个目标约束依次表示为： 1、B产品不超过10单位 x2 + d1- - d1+=10 2、利润不低于1600元 80x1 + 100x2 + d2- - d2+ =1600 3、充分利用2车间的生产能力，尽量不加班。 x1 + 2x2 + d3- - d3+ =40,问题分析,4）目标的重要程度不同，因此目标的满足有先有后，即有优先级别。设最重要的为P1级，次之者为P2级优先因子 P看成实数 P1P2,问题分析,5） 有时同级别的目标中，其重要程度又 有差别，则设置不同的权重（系数W） 。,6) x1 + 2x2 40 (系统约束) x1 + 2x2 + d3- - d3+ =40 (目标约束),当对某个资源约束既是系统约束，又是目标约束时，则不再表示为系统约束,问题分析,1、B产品不超过10单位 d1+ 越小越好 0最佳 2、利润不低于1600元 d2- 越小越好 0最好 3、充分利用2车间的生产能力，尽量不加班 d3- 和 d3+ 越小越好,7）目标规划的目标,问题分析,7）目标规划的目标函数： 目标规划有多个目标，我们已经把它转化为目标约束，整个问题的目标就是使得实施结果与目标期望值的偏差最小 于是本题目标函数表示为： minZ=P1d1+ , P2d2- , P3( d3- + d3+) ,问题分析,2x1 + 1.5x2 50 x2 + d1- - d1+ = 10 80x1 + 100x2 + d2- - d2+ = 1600 x1 + 2x2 + d3- - d3+ = 40 x1 ，x2 ，di-，di+ 0 ,i=1,2,3,综上所述，本题的数学模型为：,目标函数：min Z=P1d1+ , P2d2- , P3( d3- + d3+) ,约束条件,目标规划的概念及数学模型,数学模型为：,目标函数,min Z = Pl (k(Wlk- dk-+Wlk+ dk+) )， l=1,2,L,约束条件,jckjxj+ dk- - dk+ =bk, k=1,2,K jaijxj (= ) bi, i=1,2,m xj ，dk-，dk+ 0 ,j=1,n;k=1,2,K,目标约束,系统约束,目标规划的图解法,例2,2x1 + 1.5x2 50 x2 + d1- - d1+ = 10 80x1 + 100x2 + d2- - d2+ = 1600 x1 + 2x2 + d3- - d3+ = 40 x1 ，x2 ，di-，di+ 0 ,i=1,2,3,目标函数 min Z=P1 d1+ , P2 d2- , P3( d3- +d3+),约束条件,d1-,d1+,图解法,4.3 解目标规划的单纯形法,4.3 解目标规划的单纯形法,目标规划的数学模型结构与线性规划的数学模型结构没有本质的区别，所以可用单纯形法进行求解。但要考虑目标规划数学模型的一些特点：,(1) 因目标规划问题的目标函数都是求最小化，所以检验数的最优准则与我们前面讲到的线性规划检验准则是相反的，即以所有的j0为最优准则；,(2) 因为非基变量的检验数中含有不同等级的优先因子，且 Pi Pi+1，i = 1,2,L-1. 所以在判断各检验数大小时得小心；,解目标规划的单纯形法计算步骤,(1) 建立初始单纯形表，在表中将检验数行按优先因子个数分别列成L行，置k=1。 (2) 检查该行中是否存在负数，且对应的前k-1行的系数是0。若有，则取其中最小者对应的变量为换入变量，转(3)；否则，转(5)。 (3) 按最小比值规则确定换出变量，当存在两个或两个以上相同的最小比值时，选取具有较高优先级别的变量为换出变量。 (4) 按单纯形法进行基变换运算，建立新的单纯形表。 (5) 当k=L时，计算结束，表中解即为满意解。否则置k=k+1，返回(2) 。,例5 用单纯形法来解例2 引入松弛变量x3 ，将例2的目标规划中约束条件转换成线性规划标准形式，如下： Min P1d1-，P2 d2+，P3 d3- s.t. 5x1 + 10x2 + x3 = 60 x1 - 2x2 + d1- - d1+ = 0 4x1 + 4x2 + d2- -d2+ = 36 6x1 + 8x2 + d3- -d3+ = 48 x1 , x2 , x3 , di- ,di+ 0 , i = 1,2,3., Min z = P1d1- + P2 d2+ + P3 d3- s.t. 5x1 + 10x2 + x3 = 60 x1 - 2x2 + d1- - d1+ = 0 4x1 + 4x2 + d2- -d2+ = 36 6x1 + 8x2 + d3- -d3+ = 48 x1 , x2 , x3 , di- ,di+ 0 , i = 1,2,3.,该目标规划和下面线性规划问题等价,建立初始单纯形表,最终单纯形表,最优解 X1 = （24/5，12/5）,分别得到剩下的三个最优解： X2 = （8，0）； X3 = （6，3）； X4 = （9，0）,X1,X2,X3,X4,目标规划应用举例之一,要求：P1:充分利用工时 P2：A、B、C分别达到5、5、8件，并按 工时利润确定权重 P3：加班时间不要超过16小时 P4：A、B、C月销售量10、12、10件 P5：尽量减少加班时间,例1.,目标规划应用举例之一,min Z = P1d1-+P2(40d2- +35d3- +42d4-)+P3 d5+ +P4(d6-+ d7-+ d8-)+P5 d1+,5x1+8x2+12x3 +d1- - d1+ =120 x1+ d2- -d2+= 5 x2+ d3- -d3+=