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

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

2、ogramming： 多目的线性规划，含有多个优化目的的线性规划。第一节 多目的规划问题二、多目的规划的提出例：甲乙产品的最优消费方案。产品资源甲乙现有资源 设备A2016设备B0210设备C3432单位利润 35解：线规划模型： maxZ=3x1+5x2 2x1 16 2x2 10 3x1+4x2 32 x1，x2 0根据市场需求：希望尽量扩展甲产品减少乙产品产量。又添加二个目的： maxZ1=3x1+5x2 maxZ2=x1minZ3=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. 解: 设 分别表示下月经销甲、乙货物的吨数。对只具有两个决策变量的目的规划的数学模型，可以用图解法来分析求解。用例2来阐明图5-1)。解为线段GD(G(2,

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

9、周尽量不超越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尽能够小，这就是E点。故E点为称心解。其坐标为(24，26)，即

10、该厂每周应装配彩色电视机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-为初始基变量，列初始单纯形表，见表5-1。 取k=1，检查检验数的P1行，该行无负检验数。

12、 查出检验数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-为换出变量，经迭代得到表5-4。由表5-4得到解x1*=10/3，x2*=10/3，此解相当于图

13、5-1的D点，G、D两点的凸线性组合都是例1的称心解。第五节 目的规划的运用案例一、无穷多称心解解：设x1,x2表示A、B产品的产量。两个等级的目的：P1：充分利用设备工时，正负偏向之和为最小 目的达成函数 目的约束条件 P2 ：利润额希望不能低于100元，负偏向最小 目的达成函数 目的约束条件 方案消费两种产品，首先要充分利用设备工时而不加班；然后思索利润不低于100元。问应如何制定产品A、B的产量。2A24BDx26810 x1第五节 目的规划的运用案例一、无穷多称心解由于资料供应限量为8单位，所以有绝对约束条件，如下该问题的目的规划模型如下，图解法求解如图CG 例 某单位指点在思索本单位

14、职工的晋级调资方案时，依次遵守以下规定：(1) 不超越月工资总额60000元；(2) 每级的人数不超越定编规定的人数；(3) 、级的晋级面不低于现有人数的20%且无越级提升；(4) 级缺乏编制的人数可录用新职工，又级的职工中有10%要退休。有关资料汇总于表中，问该指点应如何拟订一个称心的方案。回本章目录二、晋级调资问题 解 设x1、x2、x3分别表示提升到、级和录用到级的新职工人数。对各目确实定的优先因子为：P1不超越月工资总额60000元；P2每级的人数不超越定编规定的人数；P3、级的晋级面不低于现有人数的20%。先分别建立各目的约束。月工资总额不超越60000元 2000(10-100.1

15、+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力求总运费最省。试求称心的调运方案。三、运输问题解 该运输问题是一个产量小于销量的问题，首先添加一个虚设的产地A4，将其转化为产销平衡的运输问题。用软件求解该问题，可知其共有4个最优方案，最小运费为2950元供应

17、约束 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+=250A3向B1提供的产品量不少于100 x31+d5-d5+=100然后再根据各工程标的要求建立目的规划模型每个销地的供应量不小于其需求量的80%x11+x21+x31+d6-d6+=2000.8x12+x22+x32+d7-d7+=1000.8x13+x23+x33+d8-d8+=4500.

18、8x14+x24+x34+d9-d9+=2500.8调运方案的总运费不超越最小运费调运方案的10%因路段的问题，尽量防止安排将A2的产品运往B4x24+d11-d11+=0给B1和B3的供应率要一样(x11+x21+x31)-(200/450)(x13+x23+x33)+d12-d12+=0力求总运费最省目的函数为：计算结果，得到称心调运方案见表总运费为3360元。第五节 目的规划的运用案例四、目的管理方案 例：某公司预备消费甲、乙产品，据市场调查：甲产品的最大市场需求8台，乙产品的最大市场需求6台。 在满足现有电力资源严厉供应约束的前提下，该厂长思索两个目的：一是总利润不低于3600元；二是

19、充分利用设备台时，但尽量少加班。问应如何制定产品甲、乙的产量，试建立其目的规划的数学模型。第五节 目的规划的运用案例四、目的管理方案 1. 利润期望优先目的规划数学模型： 运用图解法进展求解 FECx1 =8x2 =65x1 +5x2 =600 x12410126ABx20842D10Gx1 =8, x2 = 3第五节 目的规划的运用案例1. 利润期望优先 总利润：3600单位甲：300单位乙：400消费部目的甲产品的产量：8，本钱：900乙产品的产量：3，本钱：1400技术部目的甲的设备单耗25，需降低5工时 乙的设备单耗50，需降低10工时 销售部目的甲产品的销量：8，单价：1200乙产品

20、的销量：3，单价：1800称心解：x1 =8, x2 = 3设备才干：需求：308+60 3=420，实践：360实现目的P1和P2，降低甲乙产品的设备耗费:降低率(420-360)/360=17%， 甲产品的设备耗费降为30 (1-17%)=25, 乙产品的设备耗费降为60 (1-17%)=50。第五节 目的规划的运用案例四、目的管理方案 2. 设备工时优先目的规划数学模型： 运用图解法进展求解 FECx1 =8x2 =65x1 +5x2 =600 x12410126ABx20842D10Gx1 =8, x2 = 2第五节 目的规划的运用案例2. 设备工时优先 总利润：3600单位甲：337

21、.5单位乙：450 消费部目的甲产品的产量：8，本钱：862.5 乙产品的产量：2 ，本钱：0 技术部目的保证设备的正常运转甲的设备单耗30 ，乙的单耗60 销售部目的甲产品的销量：8，单价：1200乙产品的销量：2 ，单价：1800称心解：x1 =8, x2 = 2利润总额3008+4002=3200，目的：3600不能提价，就必需降低本钱以添加利润，利润增长率为12.5% 甲产品的本钱需求降为1200-300(1+12.5%)=862.5元/台，降低幅度4.2% 乙产品的本钱需求降为1800-400(1+12.5%)=0元/台，降低幅度3.6% 课堂练习1.知条件如表所示工序型号每周最大加

22、工能力AB（小时/台）（小时/台）436215070利润（元/台）300450假设工厂运营目的的期望值和优先等级如下：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产品的单位利润分别为25