运筹学第四章

1、1第四章第四章 目标规划目标规划第四章第四章 目标规划目标规划教学时数：教学时数：6学时 教学目的与要求：教学目的与要求：理解目标规划的概念与图解法, 能建立目标规划模型 教学内容：教学内容：1.目标规划的概念与模型2.目标规划的图解法与单纯形法3.目标规划的应用案例 教学重点：教学重点：目标规划的建模与图解法教学难点：教学难点：目标规划的建模与图解法 2第三节 求解模型第四节 灵敏度分析第二节 模型建立第一节 目标分析第四章第四章 目标规划目标规划第四章第四章 目标规划目标规划3 线性规划的局限性 建立目标体系的考虑第一节第一节 目标分析目标分析第四章第四章 目标规划目标规划4 线性规划只能

2、处理一个目标，而现实问题往往要处理多种目标； 线性规划立足于满足所有约束条件，而实际问题中可能存在相互矛盾的约束条件； 线性规划的约束条件是不分主次地同等对待，而现实中可根据需要给予轻重缓急的考虑。 线性规划寻求最优解，但很多实际问题只须找出满意解即可。一、线性规划的局限性第四章第四章 目标规划目标规划5 1、目标分为两大类，一类是必须的目标，另一类是希望实现的目标； 2、希望实现的目标根据轻重缓急的要求来分出层次； 3、同一层次的目标属性应是独立的。二、建立目标体系的考虑第四章第四章 目标规划目标规划6第二节目标规划的数学模型问题的提出解决目标规划的方法目标规划数学模型的一般形式示例第四章第

3、四章 目标规划目标规划7一、问题的提出产品计划期内限量设备 A(h/件）2212设备B (h/件）128设备C (h/件）4016设备D (h/件）0412利润（元/件）23第四章第四章 目标规划目标规划8问题1：如何安排生产计划，使在计划期内总利润最大？问题2：若企业的目标不仅仅是利润，还有其它目标，如按重要程度的不同从大到小排列如下：1）力求使利润指标不低于12元；2）考虑到市场的需求，两种产品的产量需保持1 1的比例；3）设备B必要时可以加班，但加班时间要控制；设备A既要求充分利用，又尽可能不加班。且设备A的重要性比B大3倍。问应如何安排生产计划？其中C和D为贵重设备，严格禁止超时使用。

4、第四章第四章 目标规划目标规划9二、解决目标规划的方法：1、设置偏差变量：表示实际值与目标值的差异正偏差变量d+ 实际值超出目标值的差值负偏差变量d- 实际值未达到目标值的差值注意： ，即两者之中必有一个为0表示实际值等于目标值值表示实际值未达到目标表示实际值超出目标值00, 00, 00dddddddd2、统一处理目标和约束0dd第四章第四章 目标规划目标规划10（1）绝对约束： 必须严格满足的等式和不等式约束，不能满足这些约束的解称为非可行解。也称硬约束或系统约束。如C和D为贵重设备，严格禁止超时使用，即12416421xx（2）目标约束： 是目标规划特有的，指对那些不严格限定的约束，目标

5、约束是一种同目标结合在一起的表达式。注：目标约束的右端项可看作要追求的目标值，在达到此目标时允许有误差。第四章第四章 目标规划目标规划11如：力求使利润指标不低于12元，对于目标值即利润值12允许有偏差1232, 012322121dxxdxx从而有则值，即实际值超出了目标若1232,012322121dxxdxx从而有，则若由于正负偏差变量至少有一个为0，所以总有123221ddxx第四章第四章 目标规划目标规划12力求使利润指标不低于12元，也就是说不希望出现 故力求使利润指标不低于12元可以表示为： 1232min21ddxxd02121xxxx，也即0d希望两种产品保持1 1的比例，即

6、00dd，也不希望也就是既不希望出现用目标约束可以表示为:0min21ddxxdd第四章第四章 目标规划目标规划13设备B必要时可以加班，但加班时间要控制可以表示为：82min21ddxxd设备A既要求充分利用，又尽可能不加班可以表示为1222min21ddxxdd第四章第四章 目标规划目标规划143、优先因子（P1P2PL）和权系数wk 要寻求的方案希望满足的目标往往不唯一，因此根据主次轻重进行层次划分。首先需要满足的目标为第一层次，可用优先因子P1表示，只有在寻得上一层次对应的目标最优的条件下，才考虑较低层次的目标。其次需要满足的为第二层次，用P2表示，依次类推。 对于在某一层次上需要综合

7、一起考虑的几个目标，这些目标的重要程度可用权系数表示。 对各目标约束中的正负偏差变量按序编号后，上述目标规划的数学模型可以表示为：第四章第四章 目标规划目标规划15)(3 ,),(,min4433322211ddpdpddpdpz)4 , 3 , 2 , 1(0,1222820123212416421442133212221112121iddxxddxxddxxddxxddxxxxii第四章第四章 目标规划目标规划16目标规划追求最满意解尽可能满足决策者的要求，也就是使未进入满意范围的偏差最小。 （1）要求不低于目标值。 （2）要求不超过目标值。 （3）要求恰好达到目标值。l目标规划中的目标函

8、数目标规划中的目标函数第四章第四章 目标规划目标规划)(mindf)(mindf),(minddf第四章第四章 目标规划目标规划17 【例例4-2】 某车间计划生产A、B两种产品。决策者首先考虑要充分利用供电部门分配的电量限额指标62.5kW /日，然后考虑完成与超额完成利润指标10元/日。每日可给车间供应所需原材料8t。其它有关数据汇总于表41。应当如何安排产品A、B的产量。解：设x1、 x2分别表示A、B两种产品的日产量。根据给出条件，可建立以下模型：产 品耗 电 量（Kw / 单位产品） 材料消耗（t / 单位品）利 润12211012AB表41185.6212101121ddxx102

9、2221ddxx2,10,8221iddxxxiii);(111ddP)(22dPmin解：设x1、 x2分别表示A、B两种产品的日产量。根据给出条件，可建立以下模型：第四章第四章 目标规划目标规划19三、目标规划数学模型的一般形式第四章第四章 目标规划目标规划kkddnjxbxakkgddxckkjijnjijkkkjnjkj,.,2, 1 0,.,2, 1 0n1,2,.,i ),(,.,2, 1 11,.,2 , 1 ) )(min1Lldwdwpkkklkklkl20【例例4-34-3 】有三个产地向四个销地供应物资。产地Ai(i=1,2,3)的供应量ai、销地Bj(j=1,2,3,4

10、)的需要量bj、各产销地之间的单位物资运费cij 见表4-1。表中ai和bj的单位为 t，cij的单位为元/ t。编制调运方案时要求按照相应的优先级依次考虑下列七项指标： P1：B4是重点保证单位，其需要量应尽可能全部满足； P2：A3向B1提供的物资不少于100 t； P3：每个销地得到的物资数量不少于其需要量的80%； P4：实际的总运费不超过当不考虑P1至P6各目标时的最小运费的110%； P5：因路况原因，尽量避免安排A2的物资运往B4； P6：对B1和B3的供应率要尽可能相同； P7：力求使总运费最省。 试求满意的调运方案。第四章第四章 目标规划目标规划21表412504501002

11、00bj4003254A32006453A23007625A1aiB4B3B2B1 cIJ Bj Ai解：该问题是销大于产的运输问题。用表上作业法可以求得不考虑P1至P6各目标时的最小运费调运方案，相应的最小运费为2950元。设xij为产地Ai配给销地Bj的数量。第四章第四章 目标规划目标规划22（1）供应量的约束400200300443332312423222114131211xxxxxxxxxxxx（2）需求量的约束25045010020044342414333323132232221211312111ddxxxddxxxddxxxddxxx第四章第四章 目标规划目标规划23（3） A3向

12、B1提供的物资不少于100 t。1005531ddx（4）每个销地得到的物资数量不少于其需要量的80%。16066312111ddxxx8077322212ddxxx36088332313ddxxx20099342414ddxxx（5）P4中运费上的限制324510103141ddxcijijij第四章第四章 目标规划目标规划24（6）考虑路况的限制0111124ddx（7）考虑B1和B3的供应率要尽可能相同0)(450200)(1212332313312111ddxxxxxx（8）力求使总运费最省295013133141ddxcijijij目标函数为min,52dP),(98763ddddP

13、,104dP,11-115）（ddP137dP),(12126 ddP,41dP第四章第四章 目标规划目标规划25第三节第三节 求解模型求解模型单纯形法单纯形法图解法图解法第四章第四章 目标规划目标规划26 求解目标规划问题常用的有两种方法求解目标规划问题常用的有两种方法 （1 1）图解法）图解法 特点：形象直观，但只适用于只有两个决策变量。特点：形象直观，但只适用于只有两个决策变量。 （2 2）单纯形法）单纯形法 目标规划的数学模型与线性规划的数学模型本质上目标规划的数学模型与线性规划的数学模型本质上是一致的，故可以利用单纯形方法求解目标规划问题。是一致的，故可以利用单纯形方法求解目标规划问

14、题。 第四章第四章 目标规划目标规划27 图解法步骤图解法步骤 1、画出平面直角坐标系。、画出平面直角坐标系。 2、如果有系统约束，运用线性规划图解法的步骤确定、如果有系统约束，运用线性规划图解法的步骤确定可行区域；如果没有系统约束，转下步。可行区域；如果没有系统约束，转下步。 3、从第一个目标（最重要目标）起，令偏差变量等于、从第一个目标（最重要目标）起，令偏差变量等于零，确定哪半个平面是超过目标的部分；哪半个平面是零，确定哪半个平面是超过目标的部分；哪半个平面是达不到目标的部分。达不到目标的部分。 4、分析半个平面的取舍并结合系统约束，确定满足第、分析半个平面的取舍并结合系统约束，确定满足

15、第一目标的可行区域并确定达成目标的函数一目标的可行区域并确定达成目标的函数 （1）要求不低于目标值：）要求不低于目标值：min f (d-) （2）要求不超过目标值：）要求不超过目标值： min f (d+) （3）要求恰好达到目标值：）要求恰好达到目标值： min f (d-，d+) 5 、第二目标在第一目标确定区域内选择、第二目标在第一目标确定区域内选择,依此类推依此类推第四章第四章 目标规划目标规划28【例4-3】 用图解法求解例4-2的目标规划模型x1x20 1 2 3 4 5 6 7 8 7 6 5 4 3 2 11d2dABDECA点坐标为（0.6，4.7)，B点坐标为（0，5.2

16、）。故最优解为102.50)1(7.46.0X首先在可行域考虑第一优先级目标函数 )(11dd然后在BC段上考虑第二优先级目标函数 2d一、图解法满意解为BC线段，满意解为AB段。)5.621210(21xx10221 xx第四章第四章 目标规划目标规划29【例4-4】 用图解法解下列目标规划模型问题：第四章第四章 目标规划目标规划x2x12x1+x2 =10d1-A-x1+2x2 =6d3-B112133min fpdp dp d1211122212331 ,2 ,1 022 6. .2601, 2 , 3ixxddxxdds txxddxxdi30【例4-5】 用图解法解下列目标规划模型问

17、题：第四章第四章 目标规划目标规划x2x120d1-d4+x1+x2 =90 x1+x2 =100 x1=70d2+x2=50d3-AB12111222331244129 07 0. .5 01 0 0,01, 2 , 3, 4iixxddxdds txddxxddxxddj143234211)56(mindpddpdpdpf31KkddnjxmibxaKkgddxcLldwdwPkkjinjjijkkknjjkjKkklkklkl,2, 10,2, 10,2, 1),(,2, 1,2, 1) )(min111三、目标规划数学模型的一般形式第四章第四章 目标规划目标规划32二、单纯形法 利用单

18、纯形法求解目标规划时，与求解线性规划相比，求解过程中需注意以下几点： 1、偏差变量与决策变量、松弛变量一样看待。一般可以利用偏差变量、松弛变量作为初始基变量，常常不需（或需较少的）人工变量； 2、目标规划是求极小化的目标函数，满意判别准则是所有检验数cj-zj0； 3、某一变量整体检验数正负取决于第一优先因子的检验数，只有当第一优先因子的检验数为零时，该变量的整体检验数的正负取决于第二优先因子的检验数，依此类推。第四章第四章 目标规划目标规划33 5、当有多重最满意解时，一般应将所有满意解都求出，以供决策者选择。 4、在整体检验数小于零的变量中选择进基变量时，应按第一优先因子选择检验数minc

19、j-zj/cj-zj0 对应的变量为进基变量；只有当第一优先因子的检验数均为0时，按第二优先因子选择检验数mincj-zj/cj-zj0 ，即1 / 21/4 时，原最满意解 当1- 2/40 ，即1 / 21/4时，原最满意解变化，可用单纯形法继续求解，最终求得最满意解 ；TTxx)2,5(),(21TTxx)4/5,2/3(),(21(此时d3- =0， d4- =3/4)不变；（此时d3- =3， d4- =0）；第四章第四章 目标规划目标规划46第四章第四章 目标规划目标规划第五节第五节 ：应用案例：应用案例例例1：某公司决定使用：某公司决定使用1000万元新产品开发基金开万元新产品开

20、发基金开发发A、B、C三种产品经预测估计，开发三种产品经预测估计，开发A、B、C三种新产品的投资利润率分别为三种新产品的投资利润率分别为5%、7%、10%。由于新产品开发有一定风险，因此，公。由于新产品开发有一定风险，因此，公司研究后确定了下列优先顺序目标：司研究后确定了下列优先顺序目标：第第1：A产品至少投资产品至少投资300万元万元第第2：为分散投资风险，任何一种新产品的开发投：为分散投资风险，任何一种新产品的开发投资不超过开发基金总额的资不超过开发基金总额的35%第第3：应至少留有：应至少留有10%的开发基金以备用的开发基金以备用第第4：使总的投资利润最大：使总的投资利润最大解：令解：令

21、x1、x2、x3为投资为投资A、B、C三种产品的金额三种产品的金额47第四章第四章 目标规划目标规划第第1：A产品至少投资产品至少投资300万元万元300111ddxmin11dP第第2：为分散投资风险，任何一种新产品的开：为分散投资风险，任何一种新产品的开发投资不超过开发基金总额的发投资不超过开发基金总额的35%350221ddx350332ddx350443ddx)(min4322dddP投资总额的限制投资总额的限制1000321xxx48第四章第四章 目标规划目标规划第第3：应至少留有：应至少留有10%的开发基金以备用的开发基金以备用90055321ddxxxmin53dP第第4：使总的

22、投资利润最大：使总的投资利润最大1001 . 007. 005. 066321ddxxxmin64dP49第四章第四章 目标规划目标规划,),(,min6453432211dPdPdddPdP300111ddx350221ddx350332ddx350443ddx1000321xxx90055321ddxxx1001 . 007. 005. 066321ddxxx5,.,1, 0,321iddxxxii50第四章第四章 目标规划目标规划例例2：某地区新建两个火力发电站，发电量用某地区新建两个火力发电站，发电量用来供应该地区来供应该地区3个城市的工业和生活用电，个城市的工业和生活用电，但由于发电量不能完全满足但由于发电量不能完全满足3个城市的用电个城市的用电需求，为此，经过讨论决定满足其中一个需求，为此，经过讨论决定满足其中一个城市的全部用电