运筹学-目标规划.ppt

第5章目标规划,Subtitle,学习要点,了解目标规划与线性规划的异同理解目标约束中的正负偏差变量思考目标约束与系统约束的差异理解目标的优先级和目标权系数了解目标规划图解法和单纯形法,目标规划,本章内容重点目标规划模型目标规划的几何意义目标规划的单纯形方法,问题的提出,线性规划的局限性线性规划只研究在满足一定条件下，单一目标函数取得最优解，而在企业管理中，经常遇到多目标决策问题，如拟订生产计划时，不仅考虑总产值，同时要考虑利润，产品质量和设备利用率等。这些指标之间的重要程度(即优先顺序)也不相同，有些目标之间往往相互发生矛盾。线性规划致力于某个目标函数的最优解，这个最优解若是超过了实际的需要，很可能是以过分地消耗了约束条件中的某些资源作为代价。,线性规划把各个约束条件的重要性都不分主次地等同看待，这也不符合实际情况。求解线性规划问题，首先要求约束条件必须相容，如果约束条件中，由于人力，设备等资源条件的限制，使约束条件之间出现了矛盾，就得不到问题的可行解，但生产还得继续进行，这将给人们进一步应用线性规划方法带来困难。为了弥补线性规划问题的局限性，解决有限资源和计划指标之间的矛盾，在线性规划基础上，建立目标规划方法，从而使一些线性规划无法解决的问题得到满意的解答。,问题的提出,第一节多目标规划问题,一、线性规划的局限性,线性规划的局限性只能解决一组线性约束条件下，某一目标而且只能是一个目标的最大或最小值的问题实际决策中，衡量方案优劣考虑多个目标生产计划决策，通常考虑产值、利润、满足市场需求等生产布局决策，考虑运费、投资、供应、市场、污染等这些目标中，有主要的，也有次要的；有最大的，有最小的；有定量的，有定性的；有互相补充的，有互相对立的，LP则无能为力目标规划（GoalProgramming）多目标线性规划含有多个优化目标的线性规划,目标规划与线性规划的比较,线性规划只讨论一个线性目标函数在一组线性约束条件下的极值问题；而目标规划是多个目标决策，可求得更切合实际的解。线性规划求最优解；目标规划是找到一个满意解。线性规划中的约束条件是同等重要的，是硬约束；而目标规划中有轻重缓急和主次之分，即有优先权。线性规划的最优解是绝对意义下的最优，但需花去大量的人力、物力、财力才能得到；实际过程中，只要求得满意解，就能满足需要(或更能满足需要)。,目标规划与线性规划的比较,例5-1：某厂计划在下一个生产周期内生产甲、乙两种产品，已知资料如表所示。试制定生产计划，使获得的利润最大？同时，根据市场预测，甲的销路不是太好，应尽可能少生产；乙的销路较好，可以扩大生产。试建立此问题的数学模型。,目标规划数学模型,设：甲产品x1，乙产品x2,根据市场预测：,maxZ=70 x1+120 x29x1+4x236004x1+5x220003x1+10 x23000 x1，x20,maxZ1=70 x1+120 x2minZ2=x1maxZ3=x29x1+4x236004x1+5x220003x1+10 x23000 x1，x20,这些目标之间相互矛盾，一般的线性规划方法不能求解,第一节多目标规划问题,二、多目标规划的提出,多目标线性规划模型的原始一般形式如下：,n个决策变量，m个约束条件，L个目标函数。当L=1时，即为我们熟悉的单目标线性规划模型。,二、多目标规划的提出,上述,第一节多目标规划问题,三、多目标的处理方法,加权系数法：为每一目标赋一权数，把多目标转化成单目标。但权系数难以科学确定。优先等级法：各目标按重要性归不同优先级而化为单目标。有效解法：寻求能照顾到各目标而使决策者感到满意的解。但可行域大时难以列出所有有效解的组合。目标规划法：对每一个目标函数引入正的或负的偏差变量；引入目标的优先等级和加权系数。,第二节目标规划的数学模型,1.目标期望值,每一个目标希望达到的期望值(或目标值、理想值)。根据历史资料、市场需求或上级部门的布置等来确定。,一、目标值和偏差变量目标规划通过引入目标值和偏差变量，可以将目标函数转化为目标约束。,实现值或决策值：是指当决策变量xj选定以后，目标函数的对应值。,第二节目标规划的数学模型,2、偏差变量,正偏差变量dk+表示第k个目标超过期望值的数值；负偏差变量dk-表示第k个目标未达到期望值的数值。同一目标的dk+和dk-中至少有一个必须为零。,偏差变量(事先无法确定的未知数)：是指实现值和目标值之间的差异,记为d。偏差可能存在正的或负的。正偏差变量:表示实现值超过目标值的部分，记为d。负偏差变量:表示实现值未达到目标值的部分，记为d。,目标规划的数学模型,在一次决策中，实现值不可能既超过目标值又未达到目标值，故有dd0,并规定d0,d0当完成或超额完成规定的指标则表示：d0,d0当未完成规定的指标则表示：d0,d0当恰好完成指标时则表示：d0,d0,目标规划的数学模型,二.目标约束和绝对约束引入了目标值和正、负偏差变量后，就对某一问题有了新的限制，既目标约束。目标约束即可对原目标函数起作用，也可对原约束起作用。目标约束是目标规划中特有的，是软约束。绝对约束(系统约束)是指必须严格满足的等式或不等式约束。如线性规划中的所有约束条件都是绝对约束，否则无可行解。所以，绝对约束是硬约束。,目标规划的数学模型,例如：在例一中，规定Z1的目标值为50000,正、负偏差为d、d,则目标函数可以转换为目标约束，既:,若规定3600的钢材必须用完，原式9x1+4x23600变为,第二节目标规划的数学模型,引入正负偏差变量，对各个目标建立目标约束(软约束),1.目标约束表示,例：甲乙产品的最优生产计划。,根据市场需求/合同规定：希望尽量扩大甲产品减少乙产品产量。又增加二个目标：,maxZ1=3x1+5x2maxZ2=x1minZ3=x22x1162x2103x1+4x232x1，x20,第二节目标规划的数学模型,要求：目标一是利润最大，拟定利润目标是30；目标二是减少乙产品产量但希望不低于4件；目标三是甲产品产量希望不少于6件；对各目标引入正、负偏差变量：3x1+5x2+d1-d1+=30 x2+d2-d2+=4x1+d3-d3+=6,目标规划的数学模型,三.优先因子(优先等级)与优先权系数目标等级化:将目标按重要性程度不同依次分成一级目标、二级目标.。最次要的目标放在次要的等级中。(1)对同一目标而言，若有几个决策方案都能使其达到，可认为这些方案就这个目标而言都是最优方案；若达不到，则与目标差距越小的越好。(2)不同级别的目标的重要性是不可比的。即较高级别的目标没有达到的损失，任何较低级别目标上的收获不可弥补。故在判断最优方案时，首先从较高级别的目标达到的程度来决策，然后再其次级目标的判断。(3)同一级别的目标可以是多个。各自之间的重要程度可用数量（权数）来描述。因此，同一级别的目标的其中一个的损失，可有其余目标的适当收获来弥补。,目标规划的数学模型,三.优先因子(优先等级)与优先权系数优先因子Pk是将决策目标按其重要程度排序并表示出来。P1P2PkPk+1PK，k=1,2,K。表示Pk比Pk+1有更大的优先权。即首先保证P1级目标的实现，这时可不考虑次级目标；而P2级目标是在实现P1级目标的基础上考虑的；依此类推。若要区别具有相同优先因子的两个目标的差别，这时可分别赋予它们不同的权系数j,这些都由决策者按具体情况而定。,目标规划的数学模型,四.达成函数(即目标规划中的目标函数)目标规划的目标函数(准则函数)是按各目标约束的正、负偏差变量和赋予相应的优先因子及权系数而构造的。当每一目标值确定后，决策者的要求是尽可能缩小偏离目标值。因此目标规划的目标函数只能是minZ=f(d、d)。一般说来，有以下三种情况，但只能出现其中之一：(1)要求恰好达到规定的目标值，即正、负偏差变量要尽可能小，则minZ=f(dd)。(2)要求不超过目标值，即允许达不到目标值，也就是正偏差变量尽可能小，则minZ=f(d)。(3)要求超过目标值，即超过量不限，但不低于目标值，也就是负偏差变量尽可能小，则minZ=f(d)。对由绝对约束转化而来的目标函数，也照上述处理即可。,例：甲乙产品的最优生产计划。,根据市场需求/合同规定：希望尽量扩大甲产品减少乙产品产量。又增加二个目标：,maxZ1=3x1+5x2maxZ2=x1minZ3=x22x1162x2103x1+4x232x1，x20,第二节目标规划的数学模型,例如P1级目标实现利润至少30元；P2级目标是甲乙产品的产量假设：乙产品产量不少于4件比甲产品产量不少于6件更重要，取其权重为2minG=P1d1-+P2(2d2-+d3-)3x1+5x2+d1-d1+=30 x2+d2-d2+=4x1+d3-d3+=6x1,x2,dk-,dk+0(k=1,2,3),目标规划的数学模型,五.多目标规划的解(1)若多目标规划问题的解能使所有的目标都达到，就称该解为多目标规划的最优解；(2)若解只能满足部分目标，就称该解为多目标规划的次优解；(3)若找不到满足任何一个目标的解，就称该问题为无解。(4)前面的目标可以保证实现或部分实现，而后面的目标就不一定能保证实现或部分实现，有些可能就不能实现，就称该解为多目标规划的满意解(具有层次意义的解),单目标规划,例5-2:某工厂生产A，B两种产品，有关数据如下。实现目标利润为140万元的最优生产方案,从决策者的角度看，他希望超过利润目标值，若达不到，也希望尽可能接近，即负偏差最小,级别相等的多目标规划,例5-3：若上例中假设决策者根据市场预测，产品A的销售量有下降的趋势，故考虑实现下列两个目标：(1)实现利润目标122万元(2)产品A的产量不多于10,分析:两个目标级别相等，即两个目标的重要程度一样，不存在谁优先的问题设d，d-分别为超过目标值的部分，以及未完成目标值的部分，于是两个目标可以等价表示为：,级别相等的多目标规划,x1=10，x2=7，d10，d+20，利润为122，两个目标均已经实现,具有优先级别的多目标规划,对于多个目标，如果有一定的优先顺序，即第一位重要的目标，其优先因子为P1，第二位重要的目标，其优先因子为P2，并规定P1P2优先保证P1级目标的实现，此时不考虑次级目标；次级目标P2在实现了P1级目标的基础上再予以考虑。如果无法实现P1目标，则不考虑P2目标能否取得最优若有k个不同优先顺序的目标，则有P1P2Pk将权重与偏差相乘构成目标函数，这样，权重越大，越先迫使相应的偏差等于零，这样可保证优先级高的目标首先实现。,具有优先级别的多目标规划,例5-4：若上例中决策者拟订下列经营目标，并确定了目标之间的优先顺序P1级目标：充分利用设备有效台时，不加班；P2级目标：产品B的产量不多于4；P3级目标：实现利润值130万元,分析：题目有三个目标层次，包含三个目标值。第一目标：P1(d1+d1-)第二目标：P2d2第二目标：P3d3-,具有优先级别的多目标规划,例5-5：某厂计划下一个生产周期内生产甲、乙两种产品，已知资料如表所示。制定生产计划，满足下列目标：P1级目标：完成或超额完成利润指标50000元；P2级目标：产品甲不超过200件，产品乙不低于250件；P3级目标：现有钢材3600吨必须用完,具有优先级别的多目标规划,分析：题目有三个目标层次，包含四个目标值。第一目标：P1d1-第二目标：有两个要求即甲d2，乙d3-，但两个具有相同的优先因子，需要确定权系数。本题可用单件利润比作为权系数即70:120，化简为7:12，P2(7d2+12d3-)第三目标：P3(d4+d4-),六、目标规划数学模型的一般形式,其中Pl为优先因子，w-lk，w+lk为优先系数,七、建模的步骤,根据要研究的问题所提出的各目标与条件，确定目标值，列出目标约束与绝对约束；可根据决策者的需要，将某些或全部绝对约束转化为目标约束。这时只需要给绝对约束加上负偏差变量和减去正偏差变量即可。给各目标赋予相应的优先因子Pk对同一优先等级中的各偏差变量，若需要可按其重要程度的不同，赋予相应的权系数kl+和kl-。根据决策者的要求，构造一个由优先因子和权系数相对应的偏差变量组成的，要求实现极小化的目标函数，即达成函数。,线性规划与目标规划,第三节目标规划的图解法,F,G,H,满意解：x1=5,x2=4,第三节目标规划的图解法,目标规划的图解法首先，按照绝对约束画出可行域，其次，不考虑正负偏差变量，画出目标约束的边界线，最后。按优先级别和权重依次分析各级目标。,F,G,H,满意解：x1=5,x2=4,0,12345678,123456,A,x2,x1,B,C,B(0.6250,4.6875)C(0,5.2083)，B、C线段上的所有点均是该问题的解(无穷多最优解)。,第三节目标规划的图解法,0,x2,0,(1),x1,14012010080604020,20406080100,(2),(3),(4),A,B,C,D,结论：C(60,58.3)为所求的满意解。,目标规划的图解法,目标规划的图解法,图解法解题步骤如下：1.确定各约束条件的可行域，即将所有约束条件(包括目标约束和绝对约束，暂不考虑正负偏差变量)在坐标平面上表示出来；2.在目标约束所代表的边界线上，用箭头标出正、负偏差变量值增大的方向；3.求满足最高优先等级目标的解；4.转到下一个优先等级的目标，在不破坏所有较高优先等级目标的前提下，求出该优先等级目标的解；5.重复4，直到所有优先等级目标都已审查完毕为止；6.确定最优解和满意解。,第四节目标规划的单纯形法,目标规划与线性规划的数学模型的结构相似可用前述单纯形算法求解目标规划模型：将优先等级Pk视为正常数(大法)正负偏差变量dk+、dk-视为松弛变量以负偏差变量dk-为初始基变量，建立初始单纯形表检验数的计算与LP单纯形法相同，即j=cj-CBiPj最优性判别准则类似于LP的单纯形算法：检验数一般是各优先等级因子的代数和判断检验数的正负和大小,目标规划的单纯形法,目标规划的数学模型结构与线性规划的数学模型结构形式上没有本质的区别，所以可用单纯形法求解。但要考虑目标规划的数学模型一些特点，作以下规定：(1)因目标规划问题的目标函数都是求最小化，所以以cj-zj0，j=1,2,，n为最优准则。(2)因非基变量的检验数中含有不同等级的优先因子，即,因P1P2PK；从每个检验数的整体来看：检验数的正、负首先决定于P1的系数1j的正、负。若1j=0，这时此检验数的正、负就决定于P2的系数2j的正、负。,例,见表4-13.,目标规划的单纯形法,例：用单纯形法求解下列目标规划问题,MinZ=P1d1-+P2(d2-+d2+)+P3(3d3-+5d4-)5x1+4x2+d1-d1+=204x1+3x2+d2-d2+=24x1+d3-d3+=3-x1+x2+d4-d4+=2x1,x2,dk-,dk+0,目标规划的单纯形法,目标规划的单纯形法,目标规划的单纯形法,目标规划的单纯形法,例：用单纯形法求解下列目标规划问题,minZ=P1d1+P2(d2-+d2+)+P3d3-2x1+x2+x3=11x1-x2+d1-d1+=0 x1+2x2+d2-d2+=108x1+10 x2+d3-d3+=56xi,dk-,dk+0,目标规划的单纯形法,第五节目标规划的应用案例,一、无穷多满意解,解：设x1,x2表示A、B产品的产量。两个等级的目标：P1：充分利用电量限额，正负偏差之和为最小目标达成函数目标约束条件P2：利润额希望不能低于100元，负偏差最小目标达成函数目标约束条件,计划生产两种产品，首先要充分利用设备工时而不加班；然后考虑利润不低于100元。问应如何制定产品A、B的产量。,第五节目标规划的应用案例,一、无穷多满意解,由于材料供应限量为8单位，所以有系统约束条件，如下,该问题的目标规划模型如下，图解法求解如图,C,G,第五节目标规划的应用案例,二、加班时间问题,例：某音像店有5名全职售货员和4名兼职售货员，全职售货员每月工作160小时，兼职售货员每月工作80小时。根据记录，全职每小时销售CD25张，平均每小时工资15元，加班工资每小时22.5元。兼职售货员每小时销售CD10张，平均工资每小时10元，加班工资每小时10元。现在预测下月CD销售量为27500张，商店每周开门营业6天，所以可能要加班。每出售一张CD盈利1.5元。商店经理认为，保持稳定的就业水平加上必要的加班，比不加班就业水平要好，但全职销售员如果加班过多，就会因为疲劳过度而造成效率下降，因此不允许每月加班超过100小时，建立相应的目标规划模型。,第五节目标规划的应用案例,二、加班时间问题,首先，确定目标约束的优先级。如下：P1：下月的CD销售量达到27500张；P2：全职售货员加班时间不超过100小时；P3：保持全体售货员充分就业，对全职的要比兼职的加倍优先考虑；P4：尽量减少加班时间，对两种售货员区别对待，权重由他们对利润的贡献而定。其次，建立目标约束函数（1）销售目标约束，设全体全职售货员下月的工作时间x1，全体兼职售货员下月的工作时间x2；达不到销售目标的偏差d1-，超过销售目标的偏差d1+。,第五节目标规划的应用案例,二、加班时间问题,（2）正常工作时间约束。设全体全职售货员下月的停工时间d2-，加班时间d2+；全体兼职售货员下月的停工时间d3-，加班时间d3+。（3）加班时间的限制。设全体全职售货员下月的加班不足100小时的偏差d4-，加班超过100小时的偏差d4+。两类售货员区别对待，权重比d2+:d3+=1:3，另一加班目标约束为,第五节目标规划的应用案例,二、加班时间问题,第三，按目标的优先级，写出相应的目标规划模型：,运用LINGO软件求解得x1=900,x2=500，下月共销售CD盘27500张，获利275001.5-80015-10022.5-50010=22000。,第五节目标规划的应用案例,三、目标管理方案,例：某公司准备生产甲、乙产品，据市场调查：甲产品的最大市场需求3台，乙产品的最大市场需求2台。,在满足现有电力资源严格供给约束的前提下，该厂长考虑两个目标：一是总利润不低于3600元；二是充分利用设备台时，但尽量少加班。问应如何制定产品甲、乙的产量，试建立其目标规划的数学模型。,第五节目标规划的应用案例,三、目标管理方案,1.利润期望优先目标规划数学模型：,运用图解法进行求解,F,E,G,x1=8,x2=3,第五节目标规划的应用案例,1.利润期望优先,满意解：x1=8,x2=3设备能力：需求：308+603=420，实际：360实现目标P1和P2，降低甲乙产品的设备消耗:降低率(420-360)/360=17%，甲产品的设备消耗降为30(1-17%)=25,乙产品的设备消耗降为60(1-17%)=50。,第五节目标规划的应用案例,三、目标管理方案,2.设备工时优先目标规划数学模型：,运用图解法进行求解,F,E,G,x1=8,x2=2,第五节目标规划的应用案例,2.设备工时优先,满意解：x1=8,x2=2利润总额3008+4002=3200，目标：3600不能提价，就必须降低成本以增加利润，利润增长率为12.5%甲产品的成本需要降为1200-300(1+12.5%)=862.5元/台，降低幅度4.2%乙产品的成本需要降为1800-400(1+12.5%)=1350元/台，降低幅度3.6%,第五节目标规划的应用,例5-10：已知一个生产计划的线性规划模型，经营目标：P1：总利润不低于40P2：充分利用设备能力，且尽量不超过140如何安排生产？,minZ=P1d1-+P2(d2-+d2+)x16x2105x1+2x2+d1-d1+=4020 x1+10 x2+d2-d2+=140 x1,x2,d1-,d1+,d2-,d2+0,(6,5),满意解:x1=6，x2=5设备能力:需求206+105=170，实际140实现目标P1和P2，降低甲乙产品的设备消耗:降低率(170-140)/170=18%，甲产品的设备消耗降为20(1-18%)=16.4，乙产品的设备消耗降为10(1-18%)=8.2。,总利润：40单位甲：5单位乙：2,生产部目标甲产品的产量：6，成本：5乙产品的产量：5，成本：6,技术部目标甲产品的设备单耗：16.4乙产品的设备单耗：8.2,销售部目标甲产品的销量：6，单价：10乙产品的销量：5，单价：8,第五节目标规划的应用,降低设备消耗很困难，则调整经营目标的次序P1：充分利用设备能力，且尽量不超过140，P2：总利润不低于40如何安排生产？,minZ=P2d1-+P1(d2-+d2+)x16x2105x1+2x2+d1-d1+=4020 x1+10 x2+d2-d2+=140x1,x2,d1-,d1+,d2-,d2+0,A,(6,2),E,第五节目标规划的应用,满意解：x1=6,x2=2利润指标：实际56+22=34，期望40实现目标P1和P2，增加甲乙产品的单位利润:增长率(40-34)/34=18%产品售价由市场决定，为提高利润，应从降低成本入手：甲产品的成本由5降为10-5(1+18%)=4.12,乙产品的成本由6降为8-2(1+18%)=5.63。,总利润：40单位甲：5.88单位乙：2.36,生产部目标甲产品的产量：6，成本：4.12乙产品的产量：2，成本：5.63,技术部目标甲产品的设备单耗：20乙产品的设备单耗：10,销售部目标甲产品的销量：6，单价：10乙产品的销量：2，单价：8,第五节目标规划的应用,例：某副食品批发店预测某商品今后4月的购进与售出价格如表。假设