运筹学——目标规划

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,OR2,*,OPERATIONS RESEARCH,运筹学,徐 玲,1,第五章 目标规划,要求,1、理解概念,2、掌握建模,3、掌握图解法和单纯形解法,4、理解目标规划的灵敏度分析,2,5.1,目标规划的概念及数学模型,1,多目标问题,多目标线性规划,例1,产品,资源,A B,限量,原材料（,kg),设备（台时）,2 1,1 2,11,10,单位利润,8 10,求利润最大的生产方案。,3,例2：例1的要求多元化：决策者在原材料供应受严格限制的基础上：,1、首先是产品,A,的产量不大于产品,B,的产量。,2、其次是充分利用设备的有效台时，不加班。,3,、再次是使利润额尽可能达到并超过计划利润指标56元。,此问题即为多目标决策问题，目标规划就是解这类问题的方法。,A B,限量,原材料（,kg),设备（台时）,2 1,1 2,11,10,单位利润,8 10,minZ=P,1,d,1,+,+P,2,(d,2,-,+d,2,+,)+P,3,d,3,-,4,例2的解法,解：问题分析：找差别、定概念（与单目标规划相比）,1）绝对约束：必须严格满足的等式约束和不等式约束，称之为绝对约束。,2,x,1,+1.5,x,2,50 (1),x,1,+2,x,2,40 (2),2）目标约束：那些,不必严格,满足的等式约束和不等式约束，称之为目标约束（软约束）。目标约束是目标规划特有的，这些约束不一定要求严格完全满足，允许发生正或负偏差，因此在这些约束中可以加入,正负偏差变量,。,5,3）,偏差变量：目标约束不是刚性的，而是弹性的，允许在一定范围内有偏差，这更接近于实际。为表达这种灵活性，便引入了,偏差变量,的概念，偏差变量有正负之分，,正偏差变量表示为：,d,+,，,d,+,表示超过目标值的部分；,负偏差变量表示为：,d,-,，,d,-,表示不足,目标值,的部分.,显然有,d,-,d,+,=0（,？,）,6,4）目标（期望）值：是指预先给定的某个目标的期望值。,5）实际值：是指当决策变量选定以后，目标函数的对应值。,显然：,d,+,实际值目标值,0,d,-,目标值实际值,0,尽可能达到并超过计划利润指标56元，此处的,56,元即为目标值,7,6）,目标函数的优先级与权系数:目标的重要程度不同，因此目标的满足有先有后，即有优先级别。设最重要的为,P,1,级，次之者为,P,2,级,P,看成实数,，且有,P,1,P,2,注：目标的优先级是一个定性概念，不同的优先级之间无法用数量衡量，仅仅表示优化过程中的目标考虑的先后次序。,对于同一优先级的不同目标，按其重要程度可分别赋予不同的权系数。权系数是一种可以用数量表示的指数，因此，对于一个具体的目标规划问题，它是一个数字。,8,7）,目标规划的目标函数：,目标规划的目标函数是按各约束的正、负偏差变量和赋予相应的优先因子而构造的。,目标函数的基本形式有三种：,1、要求,恰好,达到目标值，即正负偏差变量都要尽可能地小，这时，,minZf(,d,+,d,-,).,2、要求,不超过,目标值，即允许达不到目标值但正偏差变量要尽可能地小，这时，,minZf(,d,+,).,3、要求,超过,目标值，即超过量不限但负偏差变量要尽可能的小，这时，,minZf(,d,-,),显然，本题目标函数表示为：,minZ=P,1,d,1,+,+P,2(,d,2,-,+,d,2,+,),+P,3,d,3,-,9,综上所述，本题的数学模型为：,minZ=P,1,d,1,+,+P,2(,d,2,-,+,d,2,+),+P,3,d,3,-,2,x,1,+,x,2,11,x,1,-,x,2,+,d,1,-,-,d,1,+,=0,x,1,+2,x,2,+,d,2,-,-,d,2,+,=10,8,x,1,+10,x,2,+,d,3,-,-,d,3,+,=56,x,1，,x,2，,d,i,-,，,d,i,+,0,i=1,2,3,10,几点说明：,1）,有时绝对约束转化为目标约束，则不再表示为绝对约束。,2）有时同级别的目标中，其重要程度又有差别，则设置不同的权重。,11,目标规划问题的特点：,1）,问题的目标函数是关于优先等级、权系数和偏差变量的极小化函数；,2）约束条件由绝对约束或目标约束构成；,3）所有决策变量和偏差变量都受到非负约束。,12,例3：请建立以下问题的数学模型,某建筑施工单位计划生产,A,B,两种预制构件。决策者首先考虑要,充分利用,供电部门分配的电量限额指标62.5,kw/,日，其次考虑完成与超额完成利润指标10百元/日。每日可供给予制水泥8吨。其它有关数据如下表，问应如何确定,A,B,的产量。,产品,耗电量(,kw/,产品）,水泥消耗（吨/产品）,利润（百元/产品）,A,10,2,1,B,12,1,2,13,课堂练习：,某工厂生产A、B两种产品，已知有关数据如下：,要求：首先、B产品不超过10单位；其次，利润不低于1600元，再次，充分利用2车间的生产能力，尽量不加班。请建立该问题的模型。,产品,资源,A B,限量,1,车间,2,车间,2,1.5,1 2,50,40,单位利润,8,0 100,14,图解法的基本步骤：,（1）先作硬约束与决策变量的非负约束，同一般线性规划作图法。,（2）作目标约束，此时，先让,d,i,-,-,d,i,+,0，,然后标出,d,i,-,及,d,i,+,的增加方向（实际上是目标值减少与增加的方向）。,（3）按优先级的次序，逐级让目标规划的目标函数中极小化偏差变量取0，从而逐步缩小可行域，最后找出问题的解。,5.2目标规划的图解法,15,5.2目标规划的图解法,图解例2:,minZ=P,1,d,1,+,+P,2(,d,2,-,+,d,2,+),+P,3,d,3,-,2,x,1,+,x,2,11,x,1,-,x,2,+,d,1,-,-,d,1,+,=0,x,1,+2,x,2,+,d,2,-,-,d,2,+,=10,8,x,1,+10,x,2,+,d,3,-,-,d,3,+,=56,x,1，,x,2，,d,i,-,，,d,i,+,0,i=1,2,3,16,例4：,17,考虑目标规划数学模型的一些特点，作以下规定：,1）因目标函数为求最小化，所以要求,2）因非基变量检验数中含有不同等级的优先因子，即 ，因,p,1,p,2,p,k,；,从每个检验数的整体看：检验数的正、负首先决定于,p,1,的系数,a,1j,的正负，若,a,1j,0，,则此检验数的正、负就决定于,p2,的系数,a,2j,的正负，依次类推。,5.3 目标规划的单纯形解法,18,3),目标规划使用单纯形法求解，,d,i,-,，d,i,+,视为普通变量。,P1P2,PL,19,求解目标规划单纯形法的步骤：,P,105,1、建立初始单纯形表，在表中将检验数行按优先因子个数分别列成,K,行，置,k=1。,2、,检查该行中是否存在负数，且对应的前,k1,行的系数是零。若有负数，取其中最小者对应的变量为换入变量，转（3），若无负数，则转（5）。,3、按最小比值规则确定换出变量，当存在两个和两个以上相同的最小比值时，选取具有较高优先级别的变量为换出变量。,4、按单纯形法进行基变换运算，建立新的计算表，返回（2）。,5、当,k=K,时，计算结束。表中的解即为满意解。否则置,k=k 1，,返回到（2）。,20,例题5:用单纯形法求解下列目标规划问题,minZ=P,1,d,1,+,+P,2(,d,2,-,+,d,2,+),+P,3,d,3,-,2,x,1,+,x,2,11,x,1,-,x,2,+,d,1,-,-,d,1,+,=0,x,1,+2,x,2,+,d,2,-,-,d,2,+,=10,8,x,1,+10,x,2,+,d,3,-,-,d,3,+,=56,x,1，,x,2，,d,i,-,，,d,i,+,0,i=1,2,3,21,5.5 目标规划的灵敏度分析,例5：已知目标规划问题：,目标函数的等级变化为：,试分析原解有什么变化？,22,C,B,X,B,b,x,1,x,2,2,p,1,3,p,1,p,2,p,3,x,2,X,1,6,4,18,2,0,1,0,0,1,0,0,0,1,0,-3,-1,-1,0,3,1,-1,1,-2,0,1,-1,2,0,0,0,1,0,0,0,-1,0,0,0,0,1,0,0,0,-1,0,0,P,2,0,0,0,0,0,0,0,0,3,0,2,-3,0,0,2,0,3,-2,0,0,0,0,0,1,0,0,0,0,0,0,1,P,1,P,2,p,3,解:原问题的最优单纯形表为：,23,问题1的变化情况为：,24,C,B,X,B,b,x,1,x,2,2,p,1,3,p,1,p,2,p,3,x,2,X,1,6,4,18,2,0,1,0,1,1,0,0,0,1,0,-3,-1,-1,0,3,1,-1,1,-2,0,1,-1,2,0,0,0,1,0,0,0,-1,0,0,0,0,1,0,0,0,-1,0,0,P,2,0,0,0,0,0,0,0,0,3,0,2,-3,0,0,2,0,3,-2,0,0,0,0,0,1,0,0,0,0,0,0,1,P,1,P,2,p,3,p,2,p,3,0,0,0,此时，检验数大于等于零，可见，原解仍是满意解。,p,3,0,0,3,2,0,3,0,0,2,3,0,2,0,0,1,0,1,0,25,C,B,X,B,b,x,1,x,2,2,p,1,3,p,1,p,2,p,3,x,2,X,1,6,4,18,2,0,1,0,1,1,0,0,0,1,0,-3,-1,-1,0,3,1,-1,1,-2,0,1,-1,2,0,0,0,1,0,0,0,-1,0,0,0,0,1,0,0,0,-1,0,0,P,2,0,0,0,0,0,0,0,0,3,0,2,-3,0,0,2,0,3,-2,0,0,0,0,0,1,0,0,0,0,0,0,1,P,1,P,2,p,3,p,1,2,p,2,3,p,2,p,1,-3,2,0,3,0,0,2,0,0,-2,3,0,1,0,0,p,1,级的检验数不是大于等于零，则,p,1,级目标未实现，继续迭代。过程见书第108页。,26,某单位考虑职工的升级调资方案时，依次遵守得规定：,1,、不超过年工资总额,60000,元；,2,、每级的人数不超过定编规定的人数；,3,、二、三级的升级面尽可能达到现有人数的,20,，且无越级提升；,4,、三级不足编制的人数可录用新职工，又一级的职工中有,10,要退休。,有关资料如下，问应如何拟定一个满意的方案。,等级,工资额（元,/,年）,现有人数,编制人数,1,2,3,2000,1500,1000,10,12,15,12,15,15,合计,37,42,27,已知有三个产地给四个销地供应某种产品，产销地之间地供需量和单位运费见下表，有关部门在研究调运方案时依次考虑以下七项目标，并规定其相应地优先等级：,P,1,：,B,4,是重点保证单位，必须全部满足其需要；,P2,：,A3,向,B1,提供地产量不少于,100,；,P3,：每个销地地供应量不小于其需求量地,80,；,P4,：所定调运方案的总运费不超过最小运费调运方案的,10,。,P5,：因路段的问题，尽量避免安排将,A2,的产品往,B4,；,P6,：给,B1,和,B3,的供应率要相同；,P7,：力求总运费最省。,试求满意的调运方案。,销地产地,B1,B2,B3,B4,产量,A1,A2,A3,5,3,4,2,5,5,6,4,2,7,6,3,300,200,400,销量,200,100,450,250,900/1000,其它条件不考虑，用表上作业法得最小运费为,2950,。,28,习题：某工厂计划期内要安排生产,A,B,两种产品。已知生产单位产品的利润与所需资源消耗如下表：,产品,A,产品,B,资源限量,原材料,1,原材料,2,设备,1,0,3,0,2,2,4,12,8,利润,元/,kg,3,5,29,问题：,（1）请建立该问题的线性规划模型