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

版权归工商管理系刘艳老师所有,1,第五讲 目标规划,导 言 前面所研究的线性规划模型都是假定决策者力求在一些约束条件下优化一个单一目标，譬如利润最大或费用最小。但是，由于现实世界的复杂性，许多决策情况仅考虑一个目标往往是不够的。 通常，决策者考虑到的各个目标，其中有些是互相补充的，另外一些则是互相抵触的。 本讲所要介绍的目标规划就是解决多目标决策问题的有效工具，在目标规划中，决策者的所有目标都可以按其重要性的顺序在模型中加以考虑。目标规划的解是对每一个决策变量，根据各个目标与预定目标值的偏差量为最小的方式来赋予数值。如果所有的目标不能同时得到满足，目标规划技术能够按照优先级来满足各个目标。,版权归工商管理系刘艳老师所有,2,本 章 要 求,1、理解概念 2、学会建模 3、学会图解法和单纯形解法 4、计算机求解 5、举一反三，学会应用,版权归工商管理系刘艳老师所有,3,5.1目标规划的概念及数学模型,多目标问题 多目标线性规划 例1,求利润最大的生产方案,版权归工商管理系刘艳老师所有,4,例2：例1的要求多元化： 1、b产品不超过10单位 2、利润不低于1600元 3、充分利用2车间的生产能力，尽量不加班。 解：问题分析：找差别、定概念 1）系统约束：原有约束条件是一种刚性约束，称之为系统约束：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+ d2- -d2+ =1600 x1 + 2x2+ d3- -d3+ =40,版权归工商管理系刘艳老师所有,6,5）目标的重要程度不同，因此目标的满足有先有后，即有优先级别。设最重要的为p1级，次之者为p2级 p看成实数 p1p2 6）目标规划的目标函数： 目标规划有多个目标，我们已经把它转化为目标约束，整个问题的目标就是使得实施结果与目标期望值的偏差最小 于是本题目标函数表示为： minz=p1 d1+ +p2 d2- +p3( d3- +d3+),版权归工商管理系刘艳老师所有,7,综上所述，本题的数学模型为： minz=p1 d1+ +p2 d2- +p3( d3- +d3+) 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+ =bi, i=1,2,k aijxj (= ) bi i=k+1,k+m xj ，di-，di+ 0 ,j=1,n;i=1,2,k 说明： 1）有时系统约束转化为目标约束，则不再表示为系统约束。 2）有时同级别的目标中，其重要程度又有差别，则设置不同的权重。,版权归工商管理系刘艳老师所有,版权归工商管理系刘艳老师所有,9,5.2目标规划的图解法,图解例2,d,h,f,e,版权归工商管理系刘艳老师所有,10,5.3 目标规划的单纯形解法,目标规划使用单纯形法求解， di-，di+ 视为普通变量， p1p2 pl 例题4：一家生产某种产品的公司在生产周期内的正常生产时间为100小时。为了提高产品产量，该公司可以加班生产、转承包或雇用临时工，具体数据见下表：,版权归工商管理系刘艳老师所有,11,例题4建模,要求：p1：尽量满足市场需求（100件） p2：优质率不低于98% p3：生产费用不超过22000元 解：设四种生产方式依次为x1,x2,x3,x4，则： minz=p1 d1- +p2 d2- +p3 d3+ 2x1 100 x1+x2+x3+ x4+ d1- - d1+ =100 x1- 3x3-8x4+ d2- - d2+ =0 200x1+300x2+200x3+240x4+ d3- - d3+ =22000 xj, di-,di+ 0 j=1,2,3,4 i=1,2,3,版权归工商管理系刘艳老师所有,12,例题4 求解(p134),.,版权归工商管理系刘艳老师所有,13,5.5 目标规划应用举例之一,例5.要求： p1:充分利用工时 p2：a、b、c分别达到5、5、8件，并按单位工时利润确定权重 p3：加班时间不要超过16小时 p4：a、b、c月销售量10、12、10件，并按单位工时利润确定权重 p5：尽量减少加班时间,版权归工商管理系刘艳老师所有,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- , di+ 0 ,j=1,2,3 i=1,2,5,版权归工商管理系刘艳老师所有,15,5.5 目标规划应用举例之二,例6：混和配方问题要求如下表。目标要求： p1：必须按规定比例兑制； p2：获利最大； p3：混合酒a每天至少生产2000千克。,原料酒i、ii、iii的每日供应量分别为1500千克、2000千克和1000千克，供应价格分别为18元/千克、13.5元/千克和9元/千克,解：设xij为第i级原料酒在混合酒j中的千克数。 x11+ x12 + x13 1500 x21+ x22 + x32 2000 x31+ x32 + 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+=100000 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：总运费最小,版权归工商管理系刘艳老师所有,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-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,ex1、,版权归工商管理系刘艳老师所有,21,lp： maxz=100x1 + 80x2 x* =(50,100) z* =13000 dp：去年总收益9000，增长要求11.1% 即：今年希望总收益不低于10000,版权归工商管理系刘艳老师所有,22,引入 d+：决策超过目标值部分(正偏差变量) d-：决策不足目标值部分(负偏差变量) 目标约束： 100x1+80x2 -d+d- =10000 d+d- =0 d+,d- 0,版权归工商管理系刘艳老师所有,23,版权归工商管理系刘艳老师所有,24,ex2,版权归工商管理系刘艳老师所有,25,(1)、原材料价格上涨，超计划要高价购买，所以要严格控制。 (2)、市场情况:产品销售量下降，要求产品的产量不大于产品的产量。 (3)、充分利用设备，不希望加班。 (4)、尽可能达到并超过利润计划指标56千元。,版权归工商管理系刘艳老师所有,26,建模： (1)、设定约束条件。(目标约束、绝对约束) (2)、规定目标约束优先级。 (3)、建立模型,版权归工商管理系刘艳老师所有,27,设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(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,解：设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)、超过目标： minz= f (d -) (3)、不超过目标： minz= f (d+),版权归工商管理系刘艳老师所有,33,目标规划一般模型：,版权归工商管理系刘艳老师所有,34,4、目标规划：求一组决策变量的满意值，使决策结果与给定目标总偏差最小。 目标函数中只有偏差变量。 目标函数总是求偏差变量最小。 z=0：各级目标均已达到 z0：部分目标未达到。,版权归工商管理系刘艳老师所有,35,目标规划求解图解法 引用：ex1、,版权归工商管理系刘艳老师所有,36,ex1图解法,版权归工商管理系刘艳老师所有,37,(1)、绝对约束可行域obec (2)、目标约束满意域 (3)、多个可行满意解： (60,50),10000; (70,50),11000; e(50,100),13000。 (4)、zmin =0,版权归工商管理系刘艳老师所有,38,引用ex2、,39,版权归工商管理系刘艳老师所有,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,版权归工商管理系刘艳老师所有,41,引用ex3、,42,版权归工商管理系刘艳老师所有,43,(1)、满足目标、的满意域为abcd (2)、先考虑的满意域为abef 再考虑，无公共满意域。 (3)、取e x1+x2=50 x1=24 e(24,26) 获利2960 (4)、zmin =d4- =30 - x2 + d4+=30-26=40,版权归工商管理系刘艳老师所有,44,应用案例： ex4：红星制药厂生产a、b两种药品，有关数据如下：,版权归工商管理系刘艳老师所有,45,（1）求最优生产计划 （2）电力可多供应20（百度），利润能达240（万元） （3）若（2）达不到，改为以下目标规划 目标1：保证利润不低于240万元 目标2：耗电量、耗煤量应尽量少地超过120,版权归工商管理系刘艳老师所有,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,48,10,10,x2,x1,d,c,b,a,d3-,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点,版权归工商管理系刘艳老师所有,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 部分,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