管理运筹学教学课件PPT目标规划.pptx

《管理运筹学教学课件PPT目标规划.pptx》由会员分享，可在线阅读，更多相关《管理运筹学教学课件PPT目标规划.pptx（55页珍藏版）》请在三一文库上搜索。

1、版权归工商管理系刘艳老师所有1 第五讲 目标规划 导 言 前面所研究的线性规划模型都是假定决策者力求在一 些约束条件下优化一个单一目标，譬如利润最大或费用最 小。但是，由于现实世界的复杂性，许多决策情况仅考虑 一个目标往往是不够的。 通常，决策者考虑到的各个目标，其中有些是互相补 充的，另外一些则是互相抵触的。 本讲所要介绍的目标规划就是解决多目标决策问题的 有效工具，在目标规划中，决策者的所有目标都可以按其 重要性的顺序在模型中加以考虑。目标规划的解是对每一 个决策变量，根据各个目标与预定目标值的偏差量为最小 的方式来赋予数值。如果所有的目标不能同时得到满足， 目标规划技术能够按照优先级来满

2、足各个目标。 版权归工商管理系刘艳老师所有2 本 章 要 求 1、理解概念 2、学会建模 3、学会图解法和单纯形解法 4、计算机求解 5、举一反三，学会应用 版权归工商管理系刘艳老师所有3 5.1目标规划的概念及数学模型 多目标问题 多目标线性规划 例1 产品 资源 A B限量 1车间 2车间 2 1.5 1 2 50 40 单位利润 80 100 求利润最大的生产方案 版权归工商管理系刘艳老师所有4 例2：例1的要求多元化： 1、B产品不超过10单位 2、利润不低于1600元 3、充分利用2车间的生产能力，尽量不加班。 解：问题分析：找差别、定概念 1）系统约束：原有约束条件是一种刚性约束，

3、 称之为系统约束：2x1+1.5x250 (1) x1+ 2x2 40 (2) 2）目标约束：新提出的目标要求实际上也是约 束条件，称之为目标约束。 版权归工商管理系刘艳老师所有5 3）目标期望值：目标约束的目标一定要明确， 给出确切 的量值，即目标期望值 4）偏差变量：目标约束不是刚性的，而是弹性的，允许 在一定范围内有偏差，这更接近于实际。为表达这种 灵活性，便引入了偏差变量的概念，偏差变量有正负 之分，表示为：d+和d-， d+表示超过目标值的部分 ； d-表示不足目标值的部分.显然有d- d+=0 本题三个目标约束依次表示为： x2+ d1- -d1+ =10 80x1+100x2+

4、d2- -d2+ =1600 x1 + 2x2+ d3- -d3+ =40 版权归工商管理系刘艳老师所有6 5）目标的重要程度不同，因此目标的满足有先有 后，即有优先级别。设最重要的为P1级，次之 者为P2级 P看成实数 P1P2 6）目标规划的目标函数： 目标规划有多个目标，我们已经把它转化为目 标约束，整个问题的目标就是使得实施结果与目标 期望值的偏差最小 于是本题目标函数表示为： minZ=P1 d1 + +P 2 d2 - +P 3( d3 - +d 3 +) 版权归工商管理系刘艳老师所有7 综上所述，本题的数学模型为： minZ=P1 d1 + +P 2 d2 - +P 3( d3

5、- +d 3 +) 2x1+1.5x2 50 x2+ d1- -d1 +=10 80x1+100x2+ d2- -d2 + =1600 x1 + 2x2+ d3- -d3 + =40 x1，x2，di-，di + 0 ,i=1,2,3 8 目标规划数学模型：设问题有K个目标，L个优先 等级，数学模型为： minZ= PL (WL-i di-+WL+i di + ) s.t aijxj+ di- - di+ =b i, i=1,2,k aijxj (= ) bi i=k+1,k+m xj ，di-，di+ 0 , j=1,n;i=1,2,k 说明： 1）有时系统约束转化为目标约束，则不再表示 为

6、系统约束。 2）有时同级别的目标中，其重要程度又有差别 ，则设置不同的权重。 版权归工商管理系刘艳老师所有 版权归工商管理系刘艳老师所有9 5.2目标规划的图解法 图解例2 d3+ d2- x1 x2 10 20 30 40 10 203040 d1- d1 + d2+ d3- O B C A D H F E 版权归工商管理系刘艳老师所有10 5.3 目标规划的单纯形解法 目标规划使用单纯形法求解， di-，di+ 视为普 通变量， P1P2 PL 例题4：一家生产某种产品的公司在生产周期内的正常 生产时间为100小时。为了提高产品产量，该公司可以 加班生产、转承包或雇用临时工，具体数据见下表

7、： 加工方式单产耗时工时费用 优质率 资源量 正常生产 2.01000.99100 加班生产 2.01500.98 转承包2.5800.95 临时工3.0800.90 版权归工商管理系刘艳老师所有11 例题4建模 要求：P1：尽量满足市场需求（100件） P2：优质率不低于98% P3：生产费用不超过22000元 解：设四种生产方式依次为x1,x2,x3,x4，则： minZ=P1 d1 - +P 2 d2 - +P3 d3 + 2x1 100 x1+x2+x3+ x4+ d1 - - d 1 + =100 x1- 3x3-8x4+ d2 - - d 2 + =0 200x1+300x2+20

8、0x3+240x4+ d3 - - d 3 + =22000 xj, di -,d i + 0 j=1,2,3,4 i=1,2,3 版权归工商管理系刘艳老师所有12 例题4 求解(P134) . Cj00000 P10P200P3 CBXBb x1x2x3x4x5d1 - d1 + d2 - d2 + d3 - d3 + j 0 P1 P2 0 X5 d1 - d2 - d3 - 100 100 0 22000 2 1 (1 ) 200 0 1 0 300 0 1 3 200 0 1 -8 204 1 0 0 0 0 1 0 0 0 -1 0 0 0 0 1 0 0 0 -1 0 0 0 0

9、1 0 0 0 -1 50 100 0 110 j P1 P2 P3 -1 -1 0 -1 0 0 -1 -3 0 -1 8 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 版权归工商管理系刘艳老师所有13 5.5 目标规划应用举例之一 例5.要求： P1:充分利用工时 P2：A、B、C分别达到5、5、8件，并按单位工时利润确定权重 P3：加班时间不要超过16小时 P4：A、B、C月销售量10、12、10件，并按单位工时利润确定权重 P5：尽量减少加班时间 A B C工时限制 工时/件 5 8 12170 利润/件 100 144 252 版权归工商管理

10、系刘艳老师所有14 例5建模 minZ=P1d1-+P2(20 d2 - +18 d3- +21d4-)+P3 d5+ +P4(20d6 -+18 d7-+21 d8-)+P5 d1+ s.t 8X1+5X2+12X3 +d1- - d1+ =170 X1+ d2 - -d2+= 5 X2+ d3 - -d3+= 5 X3+ d4 - -d4+= 8 8X1+5X2+12X3 +d5- - d5+ =170+16 X1 + d6 - -d6+= 10 Xj, di - , d i + 0 ,j=1,2,3 i=1,2,5 版权归工商管理系刘艳老师所有15 5.5 目标规划应用举例之二 例6：混

11、和配方问题要求如下表。目标要求： P1：必须按规定比例兑制； P2：获利最大； P3：混合酒A每天至少生产2000千克。 混合酒 兑制要求售价（元/千克 ） A B C III不多于10%，I不少于50% III不多于70%，I不少于20% III不多于50%，I不少于10% 16.5 15 14.4 原料酒I、II、III的每日供应量分别为1500千克、2000 千克和1000千克，供应价格分别为18元/千克、13.5元/千克 和9元/千克 解：设Xij为第i级原料酒在混合酒j中的千克数。 x11+ x12 + x13 1500 x21+ x22 + x32 2000 x31+ x32 +

12、x33 1000 -0.1x11 0.1x21 + 0.9x31 + d1- d1+=0 0.5x11 0.5x21 0.5x31 + d2- d2+=0 -0.7x12 0.7x22 + 0.3x32 + d3- d3+=0 0.8x12 0.2x22 0.2x32 + d4- d4+=0 -0.5x13 0.5x23 + 0.5x33 + d5- d5+=0 0.9x13 0.1x23 0.1x33 + d6- d6+=0 -1.5x11 3x12 3.6x13 + 3x21 + 1.5x22 + 0.9x23 + 7.5x31 + 6x32 + 5.4x33 + d7 d7+=10000

13、0 x11+ x21 + x13 + d8- d8+=2000 xij , dk-dk+ 0 i=1,2,3,4 j=1,2,3 k=1,8 minZ=P1(d1+d2-+d3+ d4-+d5+d6-)+P2d7-+P3 d8- 16 例6建模 版权归工商管理系刘艳老师所有17 5.5 目标规划应用举例之三 例7：多目标运输问题如下表。目标要求： P1：产地不存货，且销量至少满足一半 P2：满足B1需求，且A4B2尽量少运 P3：总运费最小 销地 产地 B1 B2 B3产 量 A1 A2 A3 A4 5 8 3 7 4 5 2 6 9 4 6 6 100 40 40 120 销 量 120 1

14、40 140400/300 版权归工商管理系刘艳老师所有18 例7建模 解：设Ai到Bj的运输量为xij X11+ X12 + X13 +d1-d1+=100 X21+ X22 + X23 +d2-d2+=40 X31+ X32 + X33 +d3-d3+=40 X41+ X42 + X43 +d4-d4+=120 X11+ X21 + X31 + X41+d5-d5+=120/2 X12+ X22 + X32+ X42+d6-d6+=140/2 X13+ X23+ X33 + X43 +d7-d7+=140/2 X11+ X21 + X31 + X41 +d8-d8+=120 X42 +d9

15、-d9+=0 Cij Xij +d10-d10+=0 Xij, dL-dL+ 0 i=1,2,3,4 j=1,2,3 L=1,2,10 minZ=P1(d1-+d1+ + d7+)+P2(d8-+d8+ +d9+)+P3 d10+ 版权归工商管理系刘艳老师所有19 目标规划问题重难点例析与练习 目标规划的原理及建模 LP：单一目标函数最优解 追求目标的极端值 dP：多个目标函数满意解 完成额定的总产值 版权归工商管理系刘艳老师所有20 甲 乙 有效工时 金工 4 2 400 装配 2 4 500 收益 100 80 EX1、 版权归工商管理系刘艳老师所有21 LP： maxZ=100X1 +

16、80X2 X* =(50,100) Z* =13000 dP：去年总收益9000，增长要求11.1% 即：今年希望总收益不低于10000 2X1+4X2 500 4X1+2X2 400 X1 , X2 0 版权归工商管理系刘艳老师所有22 引入 d+：决策超过目标值部分(正偏差变量 ) d-：决策不足目标值部分(负偏差变量 ) 目标约束： 100X1+80X2 -d+d- =10000 d+d- =0 d+,d- 0 版权归工商管理系刘艳老师所有23 minZ= d- 100X1+80X2 -d+d- =10000 4X1+2X2 400 2X1+4X2 500 X1 , X2 , d- ,

17、d+ 0 d+.d- =0 版权归工商管理系刘艳老师所有24 资源拥有量 原材料(公斤) 2 1 11 设备(小时) 1 2 10 利润(千元/件) 8 10 EX2 版权归工商管理系刘艳老师所有25 (1)、原材料价格上涨，超计划要高价购买， 所以要严格控制。 (2)、市场情况:产品销售量下降，要求产 品的产量不大于产品的产量。 (3)、充分利用设备，不希望加班。 (4)、尽可能达到并超过利润计划指标56千 元。 版权归工商管理系刘艳老师所有26 建模： (1)、设定约束条件。(目标约束、绝对约束) (2)、规定目标约束优先级。 (3)、建立模型 版权归工商管理系刘艳老师所有27 2X1+X

18、2 11 X1 -X2 +d1- -d1+=0 X1 +2X2 +d2- -d2+=10 8X1 +10X2 +d3- -d3+=56 X1 , X2 , di- , di+ 0 di- . di+ =0 设X1 ，X2为产品，产品产量。 d1- : X1产量不足X2 部分 d1+ : X1产量超过X2 部分 d2- : 设备使用不足10 部分 d2+ :设备使用超过10 部分 d3- : 利润不足56 部分 d3+ :利润超过56 部分 版权归工商管理系刘艳老师所有28 目标函数 minZ1 = d1+ minZ2 = d2- +d2+ minZ3 = d3- 或 minZ=P1d1+P2(

19、d2-+d2+)+P3(d3-) minP1d1+ , P2(d2-+d2+), P3(d3-) 版权归工商管理系刘艳老师所有29 EX3、电视机厂装配25寸和21寸两种彩电，每台 电视机需装备时间1小时，每周装配线计划开 动40小时，预计每周25寸彩电销售24台，每台 可获利80元，每周14寸彩电销售30台，每台可 获利40元。 该厂目标： 1、充分利用装配线，避免开工不足。 2、允许装配线加班，但尽量不超过10小时。 3、尽量满足市场需求。 版权归工商管理系刘艳老师所有30 minZ=P1d1-+P2d2+P3(2d3-+d4-) X1+X2 +d1- -d1+=40 X1 +X2+d2-

20、 -d2+=50 X1+d3- -d3+=24 X2 +d4- -d4+=30 X1 , X2 , di- , di+ 0 (i=1,2,3,4) 解：设X1 , X2 分别表示25寸，21寸彩电产量 版权归工商管理系刘艳老师所有31 建模小结： 1、约束条件： 硬约束(绝对约束) 软约束 (目标约束)，引入d-, d+ 2、目标优先级： P1 P2 PL 同一级中可以有若干个目标：P21 , P22 ,P23 其重要程度用权重系数W21 ,W22 ,W23 表示 版权归工商管理系刘艳老师所有32 3、目标函数： (1)、恰好达到目标： minZ= f (d -+d+) (2)、超过目标： m

21、inZ= f (d -) (3)、不超过目标： minZ= f (d+) 版权归工商管理系刘艳老师所有33 目标规划一般模型： 版权归工商管理系刘艳老师所有34 4、目标规划：求一组决策变量的满意值，使决 策结果与给定目标总偏差最小。 目标函数中只有偏差变量。 目标函数总是求偏差变量最小。 Z=0：各级目标均已达到 Z0：部分目标未达到。 版权归工商管理系刘艳老师所有35 minZ= d- 100X1+80X2 -d+d- =10000 4X1+2X2 400 2X1+4X2 500 X1 , X2 , d- , d+ 0 d+.d- =0 目标规划求解图解法 引用：EX1、 版权归工商管理系

22、刘艳老师所有36 EX1图解法 X2 X1 O 50100 50 100 125 2X1+4X2 = 500 100X1+80X2 = 10000 4X1+2X2 = 400 C E B d+ 版权归工商管理系刘艳老师所有37 (1)、绝对约束可行域OBEC (2)、目标约束满意域 (3)、多个可行满意解： (60,50),10000; (70,50),11000; E(50,100),13000。 (4)、Zmin =0 版权归工商管理系刘艳老师所有38 minZ=P1d1+P2(d2-+d2+)+P3(d3-) 2X1+X2 11 X1 -X2+d1- -d1+=0 X1 +2X2 +d2

23、- -d2+=10 8X1 +10X2 +d3- -d3+=56 X1 , X2 , di- , di+ 0 引用EX2、 39 11 10 10 5 57 X2 X1 A B C D E F G d2+ d1- d3+X1+2X2 = 10 X1 -X2=0 8X1+10X2=562X1+X2 =11 O 版权归工商管理系刘艳老师所有40 解： 可行域OAB 目标1：OBC 目标2：ED线段 目标3：GD线段 用 8X1+10X2=56 X1+ 2X2=10 求G=(2,4)利润=56 X1 -X2=0 X1+2X2=10 D=(10/3,10/3)利润=60 Zmin =0 解为X= =

24、+ (1-) (0 1) X1 2 10/3 X2 4 10/3 版权归工商管理系刘艳老师所有41 minZ=P1d1-+P2d2+P3(2d3-+d4-) X1+X2 +d1- -d1+=40 X1 +X2+d2- -d2+=50 X1 +d3- -d3+=24 X2+d4- -d4+=30 引用EX3、 42 X2 30 30 40 50 X1 O B A C D E F d3+ d4+ d1+ d2- X1+X2 =40 X1+X2 =50 X2 =30 X1 =24 版权归工商管理系刘艳老师所有43 (1)、满足目标、的满意域为ABCD (2)、先考虑的满意域为ABEF 再考虑，无公共

25、满意域。 (3)、取E X1+X2=50 X1=24 E(24,26) 获利2960 (4)、Zmin =d4- =30 - X2 + d4+=30-26=40 版权归工商管理系刘艳老师所有44 A B 电力 2 3 100(百度) 煤 4 2 120(百吨) 利润 6 4 (万元) 应用案例： EX4：红星制药厂生产A、B两种药品，有关数据如下： 版权归工商管理系刘艳老师所有45 （1）求最优生产计划 （2）电力可多供应20（百度），利润能达240（万元 ） （3）若（2）达不到，改为以下目标规划 目标1：保证利润不低于240万元 目标2：耗电量、耗煤量应尽量少地超过120 版权归工商管理系

26、刘艳老师所有46 解：(1)、 Max Z=6X1+4X2 2X1+3X2 100 4X1+2X2 120 X1 , X2 0 解为：X1 =20， X2=20 ，Zmax =200(万元) (2)、用灵敏度分析，可得： X1 =15， X2=30 ，Zmax =210 (3)、建立目标规划模型 版权归工商管理系刘艳老师所有47 minZ=P1(d1-)+P2(d2+d3+) 6X1+4X2 +d1- -d1+=240 2X1 +3X2+d2- -d2+=120 4X1 +2X2 +d3- -d3+=120 Xi , di- , di+ 0 48 10 10 X2 X1 D C B A d3-

27、 d1+ d2- 4X1+2X2 =120 6X1+4X2 =240 2X1+3X2 =120 O E 版权归工商管理系刘艳老师所有49 分析：满足P1，部分满足P2的点有A,B,C,D (如果不考虑A，B产品均需生产) 由解方程可得：A(40，0)， B(60，0) C(24，24)， D(0，60) 比较与目标的偏差 A点：ZA = P1d1- + P2d2+ P2d3+ = 0+0+ P2d3+ = (4X1+ 2X2 + d3- - 120) P2 = (440 -120） P2=40P2 B点：ZB =120P2 C点：ZC =24P2 D点：ZD =60P2 结论：取C点 版权归工

28、商管理系刘艳老师所有50 方案：A24 B24 利润240 电力未超，煤超用24(百吨) 为实施此项方案，需要进行技术改造，降低单位 耗煤量，按照120/144的比例 原来：A4 B2 现在：A4120/144=4 5/63.33 B25/6=1.66 可在原资源条件下实施计划 版权归工商管理系刘艳老师所有51 目标规划求解单纯形法 （引前例2的单纯形法） d1- : X1产量不足X2 部分 d1+ : X1产量超过X2 部分 d2- : 设备使用不足10 部分 d2+ :设备使用超过10 部分 d3- : 利润不足56 部分 d3+ :利润超过56 部分 2X1+X2 11 X1 -X2 +

29、d1- -d1+=0 X1 +2X2 +d2- -d2+=10 8X1 +10X2 +d3- -d3+=56 X1 , X2 , di- , di+ 0 di- . di+ =0 52 P1 P2 P2 P3 CB XB b X1 X2 X3 d1- d1+ d2- d2+ d3- d3+ X3 11 2 1 1 0 0 0 0 0 0 d1- 0 1 -1 0 1 -1 0 0 0 0 P2 d2- 10 1 (2) 0 0 0 1 -1 0 0 P3 d3- 56 8 10 0 0 0 0 0 1 -1 P1 0 0 0 0 1 0 0 0 0 cj-zj P2 -1 -2 0 0 0 0

30、 2 0 0 P3 -8 -10 0 0 0 0 0 0 1 X3 6 3/2 0 1 0 0 -1/2 1/2 0 0 d1- 5 3/2 0 0 1 -1 1/2 -1/2 0 0 X2 5 1/2 1 0 0 0 1/2 -1/2 0 0 P3 d3- 6 (3) 0 0 0 0 -5 5 1 -1 P1 0 0 0 0 1 0 0 0 0 P1 0 0 0 0 0 1 1 0 0 P1 -3 0 0 0 1 5 -5 0 1 版权归工商管理系刘艳老师所有 版权归工商管理系刘艳老师所有53 P1 P2 P2 P3 CB XB b X1 X2 X3 d1- d1+ d2- d2+ d3-

31、d3+ X3 3 0 0 1 0 0 2 -2 -1/2 1/2 d1- 2 0 0 0 1 -1 3 -3 -1/2 1/2 X2 4 0 1 0 0 0 4/3 -4/3 -1/6 1/6 X1 2 1 0 0 0 0 -5/3 5/3 1/3 -1/3 P1 0 0 0 0 1 0 0 0 0 P1 0 0 0 0 0 1 1 0 0 P1 0 0 0 0 0 0 0 1 0 相当G x=(2 , 4) 利润为56 版权归工商管理系刘艳老师所有54 说明： 1，还可以再做一步，d3+ d1-,可得 X=(10/3，10/3)，对应于D点 2，初始表中检验数行：要注意化为非基变 量表示式再填入 版权归工商管理系刘艳老师所有55 习题课 课本P1535.11 设A台广告X1分钟，B台广告X2分钟，C台广告X3分钟 系统约束： 40X1+60X2+80X3 2400 P1级目标： 2000X1+4000X2+1000X3+ d1 - -d 1 += 80000 P2级目标： X1+X2+X3 +d2 - -d 2 += 30 P3级目标： X3 +d3 - -d 3 += 0 目标函数：minZ=P1 d1 - +P2（2 d 2 -+ d 2 + ）+P 3 d3 +