管理运筹学讲义第5章目标规划.ppt

1、第5章 目标规划,Sub title,学习要点,了解目标规划与线性规划的异同 理解目标约束中的正负偏差变量 思考目标约束与系统约束的差异 理解目标的优先级和目标权系数 了解目标规划图解法和单纯形法,第一节 多目标规划问题,一、线性规划的局限性,线性规划的局限性 只能解决一组线性约束条件下，某一目标而且只能是一个目标的最大或最小值的问题 实际决策中，衡量方案优劣考虑多个目标 生产计划决策，通常考虑产值、利润、满足市场需求等 生产布局决策，考虑运费、投资、供应、市场、污染等 这些目标中，有主要的，也有次要的；有最大的，有最小的；有定量的，有定性的；有互相补充的，有互相对立的，LP则无能为力。 目标

2、规划（Goal Programming）： 多目标线性规划，含有多个优化目标的线性规划。,第一节 多目标规划问题,二、多目标规划的提出,例：甲乙产品的最优生产计划。,解：线规划模型： maxZ=3x1+5x2 2x1 16 2x2 10 3x1+4x2 32 x1，x2 0,根据市场需求： 希望尽量扩大甲产品 减少乙产品产量。 又增加二个目标：,maxZ1=3x1+5x2 maxZ2=x1 minZ3=x2 2x1 16 2x2 10 3x1+4x2 32 x1，x2 0,这些目标之间相互矛盾，一般的线性规划方法不能求解,第一节 多目标规划问题,二、多目标规划的提出,多目标线性规划模型的原始一

3、般形式如下：,n个决策变量，m个约束条件，L个目标函数。 当L=1时，即为我们熟悉的单目标线性规划模型。,例1 某工厂生产、两种产品，已知有关数据见下表。试求获利最大的生产方案。,为了具体说明目标规划与线性规划在处理问题方法上的区别，先通过例子来介绍目标规划的有关概念及数学模型。,第二节 目标规划的数学模型,解： 这是求获利最大的单目标的规划问题，用x1，x2分别表示、产品的产量，其线性规划模型表述为：,用图解法求得最优决策方案为：x1*=4, x2*=3, z*=62(元)。,(4,3),对于例一，计划人员被要求考虑以下意见：,（1）超过计划供应原材料时，需用高价采购，会使成本大幅度增加。因

4、此，原材料供应受严格限制。 （2）根据市场信息，产品的销售量有下降的趋势，故考虑产品的产量不超过产品的产量。 （3）应尽可能充分利用设备台时。 （4）应尽可能实现利润总额不小于56元。,这样在考虑产品决策时，便成为多目标决策问题。目标规划方法是解这类决策问题的方法之一。下面引入与建立目标规划数学模型有关的概念。,1.设x1，x2为决策变量，此外，引进正、负偏差变量d+，d- 。 正偏差变量d表示决策值超过目标值的部分；负偏差变量d-表示决策值未达到目标值的部分。,2.绝对约束和目标约束,绝对约束是指必须严格满足的约束条件，不能满足这些约束条件的解称为非可行解，它们是硬约束。,目标约束是目标规划

5、特有的，可把约束右端项看作要追求的目标值，在达到此目标值时允许发生偏差，因此是软约束。 8x1+10 x2+d1-d1+=56 2x1+x2+d2- -d2+=11。,3.优先因子(优先等级)与权系数,一个规划问题常常有若干目标，要求第一位达到的目标赋予优先因子P1，次位的目标赋予优先因子P2，并规定PkPk+1,k=1,2,，K。 若要区别具有相同优先因子的两个目标的差别，这时可分别赋予它们不同的权系数j。,4.目标规划的目标函数,当每一目标值确定后，决策者的要求是尽可能缩小偏离目标值。因此目标规划的目标函数只能是 min z=f(d+,d-)。,其基本形式有三种：,(1) 要求恰好达到目标

6、值，即正、负偏差变量都要尽可能地小，这时 min z=f(d+d-) (2) 要求不超过目标值，但允许达不到目标值。这时不希望决策值超过目标值。这时min z=f(d+) (3) 要求不低于目标值，但允许超过目标值。这时，不希望决策值低于目标值。这时min z=f(d-) 对每一个具体目标规划问题，可根据决策者的要求和赋予各目标的优先因子来构造目标函数，以下用例子说明。,例2 例1的决策者在原材料供应受严格限制的基础上考虑：首先是产品的产量不超过产品的产量；其次是充分利用设备有效台时；再次是利润额不小于56元。求决策方案 。,解 按决策者所要求的，分别赋予这三个目标P1，P2，P3优先因子。这

7、问题的数学模型是：,目标规划的一般数学模型为,为权系数。,课堂练习：,某公司经销两种货物，售出每吨甲货物可盈利202元，乙货物可盈利175元，各种货物每吨所占用的流动资金为683元，公司现有流动资金1200万元，货物经销中有8.48%的损耗。公司的决策者希望下月能达到以下目标。 （1）第一目标：盈利5030000元以上； （2）第二目标：经销甲货物5000吨以上； （3）第三目标：经销乙货物18000吨以上； （4）第四目标：经销损耗在1950吨以下。 试问应怎样决策？,s.t.,解: 设 分别表示下月经销甲、乙货物的吨数。,对只具有两个决策变量的目标规划的数学模型，可以用图解法来分析求解。用

8、例2来说明（图5-1)。解为线段GD(G(2,4),D(10/3,10/3),回本章目录,第三节 目标规划的图解法,注意目标规划问题求解时，把绝对约束作最高优先级考虑。在本例中能依先后次序都满足d1+=0，d2+d2-=0，d-3=0，因而z*=0。但在大多数问题中并非如此，会出现某些约束得不到满足，故将目标规划问题的最优解称为满意解。,例3 某电视机厂装配彩色和黑白两种电视机，每装配一台电视机需占用装配线1小时，装配线每周计划开动40小时。预计市场每周彩色电视机的销量是24台，每台可获利80元；黑白电视机的销量是30台，每台可获利40元。该厂确定的目标为：,第一优先级：装配线每周开动时间不低

9、于40小时； 第二优先级：允许装配线加班；但加班时间每周尽量不超过10小时； 第三优先级：装配电视机的数量尽量满足市场需要。因彩色电视机的利润高，取其权系数为2。 试建立这问题的目标规划模型，并求解彩色和黑白电视机的产量。,解 设x1，x2分别表示彩色和黑白电视机的产量。这个问题的目标规划模型为,用图解法求解，见图5.2,从图5.2中看到,在考虑具有P1、P2的目标实现后，x1、x2的取值范围为ABCD。考虑P3的目标要求时，因d3的权系数大于d4，故先考虑min d3；这时x1、x2的取值范围缩小为ABEF区域。然后考虑d4。在ABEF中无法满足d4=0，因此只能在ABEF中取一点，使d4尽

10、可能小，这就是E点。故E点为满意解。其坐标为(24，26)，即该厂每周应装配彩色电视机24台，黑白电视机26台。,目标规划的数学模型结构与线性规划的数学模型结构形式上没有本质的区别，所以可用单纯形法求解。但要考虑目标规划的数学模型一些特点，作以下规定： (1) 因目标规划问题的目标函数都是求最小化，因此以 j0，j=1,2,，n为最优准则。 (2) 各非基变量的检验数是各优先因子的线性组合，必须注意P1P2PK。,回本章目录,第四节 目标规划的单纯形法,因P1P2PK；从每个检验数的整体来看：检验数的正、负首先决定于P1的系数1j的正、负。若1j=0，这时此检验数的正、负就决定于P2的系数2j

11、的正、负，下面可依此类推。,解目标规划问题的单纯形法的计算步骤：,(1) 建立初始单纯形表，在表中将检验数行按优先因子个数分别列成K行。 (2) 检查检验数是否存在负数，若有负数取其中最小者对应的变量为换入变量，转(3)。若无负数，则转(5)。 (3) 按最小比值规则确定换出变量，当存在两个和两个以上相同的最小比值时，选取具有较高优先级别的变量为换出变量。 (4) 按单纯形法进行基变换运算，建立新的计算表，返回(2)。 (5) 当所有检验数 j0时，计算结束。表中的解即为满意解。,例4 试用单纯形法来求解例2。将例2的数学模型化为标准型：, 取xs，d1-，d2-，d3-为初始基变量，列初始单

12、纯形表，见表5-1。, 取k=1，检查检验数的P1行，该行无负检验数。 查出检验数P2行中有-1、-2；取min(-1,-2)= -2。它对应的变量x2为换入变量。 在表5-1上计算最小比值 =min(11/1，0，10/2，56/10)=10/2 它对应的变量d2-为换出变量。,即进行基变换运算，计算结果见表5-2,表5-3,返回到(2)。依此类推，直至得到最终表为止。见表5-3,表5-3所示的解x1*=2，x2*=4为例1的满意解。此解相当于图5-1的G点。,检查表5-3的检验数行，发现非基变量d3+的检验数为0，这表示存在多重解。在表5-3中以非基变量d3+为换入变量，d1-为换出变量，

13、经迭代得到表5-4。,由表5-4得到解x1*=10/3，x2*=10/3，此解相当于图5-1的D点，G、D两点的凸线性组合都是例1的满意解。,第五节 目标规划的应用案例,一、无穷多满意解,解：设x1,x2表示A、B产品的产量。两个等级的目标： P1：充分利用设备工时，正负偏差之和为最小 目标达成函数 目标约束条件 P2 ：利润额希望不能低于100元，负偏差最小 目标达成函数 目标约束条件,计划生产两种产品，首先要充分利用设备工时而不加班；然后考虑利润不低于100元。问应如何制定产品A、B的产量。,第五节 目标规划的应用案例,一、无穷多满意解,由于材料供应限量为8单位，所以有绝对约束条件，如下,

14、该问题的目标规划模型如下，图解法求解如图,C,G,例 某单位领导在考虑本单位职工的升级调资方案时，依次遵守以下规定： (1) 不超过月工资总额60000元； (2) 每级的人数不超过定编规定的人数； (3) 、级的升级面不低于现有人数的20%且无越级提升； (4) 级不足编制的人数可录用新职工，又级的职工中有10%要退休。 有关资料汇总于表中，问该领导应如何拟订一个满意的方案。,回本章目录,二、升级调资问题,解 设x1、x2、x3分别表示提升到、级和录用到级的新职工人数。对各目标确定的优先因子为： P1不超过月工资总额60000元； P2每级的人数不超过定编规定的人数； P3、级的升级面不低于

15、现有人数的20%。,先分别建立各目标约束。月工资总额不超过60000元,2000(10-100.1+x1)+1500(12-x1+x2) +1000(15-x2+x3)+d1-d1+ =60000,每级的人数不超过定编规定的人数： 对级有 10(1-0.1)+x1+d2-d2+=12 对级有 12-x1+x2+d3-d3+=15 对级有 15-x2+x3+d4-d4+=15 ，级的升级面不低于现有人数的20%； 对级有 x1+d5-d5+=120.2 对级有 x2+d6-d6+=150.2 目标函数： min z=P1d1+P2(d2+d3+d4+)+P3(d5-+d6-),以上目标规划模型可

16、用单纯形法求解，得到多重解。现将这些解汇总于下表，这单位的领导再按具体情况，从表中选一个执行方案,已知有三个产地给四个销地供应某种产品，产销地之间的供需量和单位运价见表。有关部门在研究调运方案时依次考虑以下七项目标，并规定其相应的优先等级：,P1B4是重点保证单位，必须全部满足其需要； P2A3向B1提供的产量不少于100； P3每个销地的供应量不小于其需要量的80%； P4所定调运方案的总运费不超过最小运费调运方案的10%； P5因路段的问题，尽量避免安排将A2的产品往B4； P6给B1和B3的供应率要相同； P7力求总运费最省。 试求满意的调运方案。,三、运输问题,解 该运输问题是一个产量

17、小于销量的问题，首先增加一个虚设的产地A4，将其转化为产销平衡的运输问题。,用软件求解该问题，可知其共有4个最优方案，最小运费为2950元,供应约束 x11+x12+x13+x14300 x21+x22+x23+x24200 x31+x32+x33+x34400 需求约束：x11+x21+x31+d1-d1+=200 x12+x22+x32+d2-d2+=100 x13+x23+x33+d3-d3+=450 x14+x24+x34+d4-d4+=250 A3向B1提供的产品量不少于100 x31+d5-d5+=100,然后再根据各项目标的要求建立目标规划模型,每个销地的供应量不小于其需要量的8

18、0% x11+x21+x31+d6-d6+=2000.8 x12+x22+x32+d7-d7+=1000.8 x13+x23+x33+d8-d8+=4500.8 x14+x24+x34+d9-d9+=2500.8,调运方案的总运费不超过最小运费调运方案的10%,因路段的问题，尽量避免安排将A2的产品运往B4 x24+d11-d11+=0 给B1和B3的供应率要相同 (x11+x21+x31)-(200/450)(x13+x23+x33)+d12-d12+=0,力求总运费最省,目标函数为：,计算结果，得到满意调运方案见表,总运费为3360元。,第五节 目标规划的应用案例,四、目标管理方案,例：某

19、公司准备生产甲、乙产品，据市场调查：甲产品的最大市场需求8台，乙产品的最大市场需求6台。,在满足现有电力资源严格供给约束的前提下，该厂长考虑两个目标：一是总利润不低于3600元；二是充分利用设备台时，但尽量少加班。问应如何制定产品甲、乙的产量，试建立其目标规划的数学模型。,第五节 目标规划的应用案例,四、目标管理方案,1. 利润期望优先 目标规划数学模型：,运用图解法进行求解,F,E,G,x1 =8, x2 = 3,第五节 目标规划的应用案例,1. 利润期望优先,满意解：x1 =8, x2 = 3 设备能力：需求：308+60 3=420，实际：360 实现目标P1和P2，降低甲乙产品的设备消

20、耗:降低率(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% 乙产品的成本需要

21、降为1800-400(1+12.5%)=1350元/台，降低幅度3.6%,课堂练习 1.已知条件如表所示,如果工厂经营目标的期望值和优先等级如下： p1: 每周总利润不得低于10000元； p2: 因合同要求，A型机每周至少生产10台，B型机每周至少 生产15台； p3: 希望工序的每周生产时间正好为150小时，工序的生产时间最好用足，甚至可适当加班。 试建立这个问题的目标规划模型。,2.在上题中，如果工序在加班时间内生产出来的产品，每台A型机减少利润10元，每台B型机减少利润25元，并且工序的加班时间每周最多不超过30小时，这是p4级目标，试建立这个问题的目标规划模型。,3一工艺品厂商手工生产某两种工艺品A、B，已知生产一件产品A需要耗费人力2工时，生产一件产品B需要耗费人力3工时。A、B产品的单位利润分别为250元和125元。为了最大效率地利用人力资源，确定生产的首要任务是