运筹学——目标规划.ppt

《运筹学——目标规划.ppt》由会员分享，可在线阅读，更多相关《运筹学——目标规划.ppt（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、OPERATIONS RESEARCH 运筹学徐 玲OR21第五章第五章目标规划目标规划n要求要求1、理解概念、理解概念2、掌握建模、掌握建模3、掌握图解法和单纯形解法、掌握图解法和单纯形解法4、理解目标规划的灵敏度分析、理解目标规划的灵敏度分析OR225.1目标规划的概念及数学模型1n多目标问题多目标问题n多目标线性规划多目标线性规划n例例1 产品资源 A B限量原材料（kg)设备（台时）2 1 1 2 11 10单位利润 8 10求利润最大的生产方案。求利润最大的生产方案。OR23n例例2：例：例1的要求多元化：决策者在原材料供应的要求多元化：决策者在原材料供应受严格限制的基础上：受严格限

2、制的基础上：1、首先是产品、首先是产品A的产量不大于产品的产量不大于产品B的产量。的产量。2、其次是充分利用设备的有效台时，不加班。、其次是充分利用设备的有效台时，不加班。3、再次是使利润额尽可能达到并超过计划利润、再次是使利润额尽可能达到并超过计划利润指标指标56元。元。此问题即为多目标决策问题，目标规划就是解这类问此问题即为多目标决策问题，目标规划就是解这类问题的方法。题的方法。A B限量原材料（kg)设备（台时）2 1 1 2 11 10单位利润 8 10minZ=P1 d1+P2(d2-+d2+)+P3 d3-OR24例2的解法解：问题分析：找差别、定概念（与单目标规划相比）解：问题分

3、析：找差别、定概念（与单目标规划相比）1）绝对约束：必须严格满足的等式约束和不）绝对约束：必须严格满足的等式约束和不等式约束，称之为绝对约束。等式约束，称之为绝对约束。2x1+1.5x250(1)x1+2x240(2)2）目标约束：那些）目标约束：那些不必严格不必严格满足的等式约束和满足的等式约束和不等式约束，称之为目标约束（软约束）。目标约不等式约束，称之为目标约束（软约束）。目标约束是目标规划特有的，这些约束不一定要求严格完束是目标规划特有的，这些约束不一定要求严格完全满足，允许发生正或负偏差，因此在这些约束中全满足，允许发生正或负偏差，因此在这些约束中可以加入可以加入正负偏差变量正负偏差

4、变量。OR253）偏差变量：目标约束不是刚性的，而是偏差变量：目标约束不是刚性的，而是弹性的，允许在一定范围内有偏差，这更弹性的，允许在一定范围内有偏差，这更接近于实际。为表达这种灵活性，便引入接近于实际。为表达这种灵活性，便引入了了偏差变量偏差变量的概念，偏差变量有正负之分，的概念，偏差变量有正负之分，正偏差变量表示为：正偏差变量表示为：d+，d+表示超过目标表示超过目标值的部分；值的部分；负偏差变量表示为：负偏差变量表示为：d-，d-表示不足表示不足目标目标值值的部分的部分.显然有显然有d-d+=0（？）OR264）目标（期望）值：是指预先给定的某个目标的期望值。5）实际值：是指当决策变量

5、选定以后，目标函数的对应值。显然：d+实际值目标值0 d-目标值实际值 0尽可能达到并超过计划利润指标尽可能达到并超过计划利润指标56元，此处的元，此处的56元即为目标值元即为目标值OR276）目标函数的优先级与权系数目标函数的优先级与权系数:目标的重要目标的重要程度不同，因此目标的满足有先有后，即程度不同，因此目标的满足有先有后，即有优先级别。设最重要的为有优先级别。设最重要的为P1级，次之者级，次之者为为P2级级P看成实数看成实数，且有，且有P1P2注：目标的优先级是一个定性概念，不同的注：目标的优先级是一个定性概念，不同的优先级之间无法用数量衡量，仅仅表示优优先级之间无法用数量衡量，仅仅

6、表示优化过程中的目标考虑的先后次序。化过程中的目标考虑的先后次序。对于同一优先级的不同目标，按其重要程度对于同一优先级的不同目标，按其重要程度可分别赋予不同的权系数。权系数是一种可分别赋予不同的权系数。权系数是一种可以用数量表示的指数，因此，对于一个可以用数量表示的指数，因此，对于一个具体的目标规划问题，它是一个数字。具体的目标规划问题，它是一个数字。OR287）目标规划的目标函数：目标规划的目标函数：目标规划的目标函数是按各约束的正、负偏目标规划的目标函数是按各约束的正、负偏差变量和赋予相应的优先因子而构造的。差变量和赋予相应的优先因子而构造的。目标函数的基本形式有三种：目标函数的基本形式有

7、三种：1、要求、要求恰好恰好达到目标值，即正负偏差变量都要尽达到目标值，即正负偏差变量都要尽可能地小，这时，可能地小，这时，minZf(d+d-).2、要求、要求不超过不超过目标值，即允许达不到目标值但正目标值，即允许达不到目标值但正偏差变量要尽可能地小，这时，偏差变量要尽可能地小，这时，minZf(d+).3、要求、要求超过超过目标值，即超过量不限但负偏差变量目标值，即超过量不限但负偏差变量要尽可能的小，这时，要尽可能的小，这时，minZf(d-)显然，本题目标函数表示为：显然，本题目标函数表示为：minZ=P1 d1+P2(d2-+d2+)+P3 d3-OR29n综上所述，本题的数学模型为

8、：综上所述，本题的数学模型为：minZ=P1 d1+P2(d2-+d2+)+P3 d3-2x1+x2 11 x1-x2+d1-d1+=0 x1+2x2+d2-d2+=10 8x1+10 x2+d3-d3+=56 x1，x2，di-，di+0,i=1,2,3OR210几点说明：几点说明：n1）有时绝对约束转化为目标约束，则不有时绝对约束转化为目标约束，则不再表示为绝对约束。再表示为绝对约束。n2）有时同级别的目标中，其重要程度又）有时同级别的目标中，其重要程度又有差别，则设置不同的权重。有差别，则设置不同的权重。OR211目标规划问题的特点：n1）问题的目标函数是关于优先等级、权系问题的目标函数

9、是关于优先等级、权系数和偏差变量的极小化函数；数和偏差变量的极小化函数；n2）约束条件由绝对约束或目标约束构成；）约束条件由绝对约束或目标约束构成；n3）所有决策变量和偏差变量都受到非负）所有决策变量和偏差变量都受到非负约束。约束。OR212例3：请建立以下问题的数学模型n某建筑施工单位计划生产某建筑施工单位计划生产A,B两种预制构件。两种预制构件。决策者首先考虑要决策者首先考虑要充分利用充分利用供电部门分配的供电部门分配的电量限额指标电量限额指标62.5kw/日，其次考虑完成日，其次考虑完成与超额完成利润指标与超额完成利润指标10百元百元/日。每日可供日。每日可供给予制水泥给予制水泥8吨。其

10、它有关数据如下表，问吨。其它有关数据如下表，问应如何确定应如何确定A,B的产量。的产量。产品耗电量(kw/产品）水泥消耗（吨/产品）利润（百元/产品）A1021B1212OR213课堂练习：n某工厂生产A、B两种产品，已知有关数据如下：n要求：首先、B产品不超过10单位；其次，利润不低于1600元，再次，充分利用2车间的生产能力，尽量不加班。请建立该问题的模型。产品资源 A B限量1车间2车间 2 1.5 1 25040单位利润 80 100OR214n图解法的基本步骤：图解法的基本步骤：n（1）先作硬约束与决策变量的非负约束，）先作硬约束与决策变量的非负约束，同一般线性规划作图法。同一般线性

11、规划作图法。n（2）作目标约束，此时，先让）作目标约束，此时，先让di-di+0，然后标出然后标出di-及及di+的增加方向（实际上的增加方向（实际上是目标值减少与增加的方向）。是目标值减少与增加的方向）。n（3）按优先级的次序，逐级让目标规划）按优先级的次序，逐级让目标规划的目标函数中极小化偏差变量取的目标函数中极小化偏差变量取0，从而，从而逐步缩小可行域，最后找出问题的解。逐步缩小可行域，最后找出问题的解。5.2目标规划的图解法OR2155.2目标规划的图解法n图解例2:minZ=P1 d1+P2(d2-+d2+)+P3 d3-2x1+x2 11 x1-x2+d1-d1+=0 x1+2x2

12、+d2-d2+=10 8x1+10 x2+d3-d3+=56 x1，x2，di-，di+0,i=1,2,3OR216n例4：OR217n考虑目标规划数学模型的一些特点，作以下规定：考虑目标规划数学模型的一些特点，作以下规定：n1）因目标函数为求最小化，所以要求）因目标函数为求最小化，所以要求n2）因非基变量检验数中含有不同等级的）因非基变量检验数中含有不同等级的优先因子，即优先因子，即，因，因p1p2pk；从每个检验数的整体看：从每个检验数的整体看：检验数的正、负首先决定于检验数的正、负首先决定于p1的系数的系数a1j的的正负，若正负，若a1j0，则此检验数的正、负就决定于则此检验数的正、负就

13、决定于p2的系数的系数a2j的正负，依次类推。的正负，依次类推。5.3 目标规划的单纯形解法OR218n3)目标规划使用单纯形法求解，目标规划使用单纯形法求解，di-，di+视为普通变量。视为普通变量。P1P2PLOR219求解目标规划单纯形法的步骤：P105n1、建立初始单纯形表，在表中将检验数行按优、建立初始单纯形表，在表中将检验数行按优先因子个数分别列成先因子个数分别列成K行，置行，置k=1。n2、检查该行中是否存在负数，且对应的前检查该行中是否存在负数，且对应的前k1行的系数是零。若有负数，取其中最小者对应的行的系数是零。若有负数，取其中最小者对应的变量为换入变量，转（变量为换入变量，

14、转（3），若无负数，则转），若无负数，则转（5）。）。n3、按最小比值规则确定换出变量，当存在两个、按最小比值规则确定换出变量，当存在两个和两个以上相同的最小比值时，选取具有较高优和两个以上相同的最小比值时，选取具有较高优先级别的变量为换出变量。先级别的变量为换出变量。n4、按单纯形法进行基变换运算，建立新的计算、按单纯形法进行基变换运算，建立新的计算表，返回（表，返回（2）。）。n5、当、当k=K时，计算结束。表中的解即为满意解。时，计算结束。表中的解即为满意解。否则置否则置k=k1，返回到（返回到（2）。）。OR220例题5:用单纯形法求解下列目标规划问题 minZ=P1 d1+P2(d2

15、-+d2+)+P3 d3-2x1+x2 11 x1-x2+d1-d1+=0 x1+2x2+d2-d2+=10 8x1+10 x2+d3-d3+=56 x1，x2，di-，di+0,i=1,2,3OR2215.5 目标规划的灵敏度分析n例5：已知目标规划问题：目标函数的等级变化为：试分析原解有什么变化？OR222CBXBbx1x22p13p1p2p3x2X1641820100100010-3-1-1031-11-201-120001000-100001000-100P200000000302-300203-20000010000001P1P2p3解:原问题的最优单纯形表为：OR223问题1的变化

16、情况为：OR224CBXBbx1x22p13p1p2p3x2X1641820101100010-3-1-1031-11-201-120001000-100001000-100P200000000302-300203-20000010000001P1P2p3p2p3000此时，检验数大于等于零，可见，原解仍是满意解。p3003203002302001010OR225CBXBbx1x22p13p1p2p3x2X1641820101100010-3-1-1031-11-201-120001000-100001000-100P200000000302-300203-20000010000001P1P2

17、p3p12p23p2p1-320300200-230100p1级的检验数不是大于等于零，则p1级目标未实现，继续迭代。过程见书第108页。OR226n某单位考虑职工的升级调资方案时，依次遵守得某单位考虑职工的升级调资方案时，依次遵守得规定：规定：n1、不超过年工资总额、不超过年工资总额60000元；元；n2、每级的人数不超过定编规定的人数；、每级的人数不超过定编规定的人数；n3、二、三级的升级面尽可能达到现有人数的、二、三级的升级面尽可能达到现有人数的20，且无越级提升；，且无越级提升；n4、三级不足编制的人数可录用新职工，又一级、三级不足编制的人数可录用新职工，又一级的职工中有的职工中有10

18、要退休。要退休。n有关资料如下，问应如何拟定一个满意的方案。有关资料如下，问应如何拟定一个满意的方案。等级工资额（元/年）现有人数编制人数123200015001000101215121515合计3742OR227n已知有三个产地给四个销地供应某种产品，产销地已知有三个产地给四个销地供应某种产品，产销地之间地供需量和单位运费见下表，有关部门在研究之间地供需量和单位运费见下表，有关部门在研究调运方案时依次考虑以下七项目标，并规定其相应调运方案时依次考虑以下七项目标，并规定其相应地优先等级：地优先等级：nP1：B4是重点保证单位，必须全部满足其需要；是重点保证单位，必须全部满足其需要；nP2：A3

19、向向B1提供地产量不少于提供地产量不少于100；nP3：每个销地地供应量不小于其需求量地：每个销地地供应量不小于其需求量地80；nP4：所定调运方案的总运费不超过最小运费调运方：所定调运方案的总运费不超过最小运费调运方案的案的10。nP5：因路段的问题，尽量避免安排将：因路段的问题，尽量避免安排将A2的产品往的产品往B4；nP6：给：给B1和和B3的供应率要相同；的供应率要相同；nP7：力求总运费最省。：力求总运费最省。n试求满意的调运方案。试求满意的调运方案。销地产地B1B2B3B4产量A1A2A3534255642763300200400销量200100450250900/1000其它条件

20、不考虑，用表上作业法得最小运费为其它条件不考虑，用表上作业法得最小运费为2950。OR228n习题：习题：某工厂计划期内要安排生产某工厂计划期内要安排生产A,B两种两种产品。已知生产单位产品的利润与所需资源消产品。已知生产单位产品的利润与所需资源消耗如下表：耗如下表：产品A产品B资源限量原材料1原材料2设备1030224128利润元/kg35OR229n问题：问题：n（1）请建立该问题的线性规划模型；（）请建立该问题的线性规划模型；（5分）分）n（2）请将该问题的数学模型转变为标准型，并）请将该问题的数学模型转变为标准型，并用单纯形法求解该线性规划问题。（用单纯形法求解该线性规划问题。（10分）分）n（3）请写出该问题的对偶规划模型，并指出对）请写出该问题的对偶规划模型，并指出对偶问题的解。（偶问题的解。（5分）分）n（4）请指出该问题的影子价格对该工厂有什么）请指出该问题的影子价格对该工厂有什么指导意义？（指导意义？（5分）分）nOR230