《chap5目标规划》PPT课件.ppt

Chapter5 目标规划 ( Goal programming ) 目标规划问题及其数学模型 目标规划的图解分析法 目标规划的单纯性法 目标规划的层次算法 目标规划应用举例 本章主要内容：本章主要内容： Page 2目标规划问题及其数学模型 1. 设置偏差变量，用来表明实际值同目标值之间的差异。 偏差变量用下列符号表示： d+决策值超出目标值的部分，称正偏差变量 d-决策值未达到目标值的部分，称负偏差变量 正负偏差变量两者必有一个为0 当实际值超出目标值时： d+0, d -=0; 当实际值未达到目标值时： d+=0, d -0; 当实际值同目标值恰好一致时： d+=0, d -=0; 故恒有d+d -=0 Page 3目标规划问题及其数学模型 2. 统一处理目标和约束。 对资源使用上有严格限制的建立系统约束，在数学形式表现为 严格的等式或者不等式，同线性规划中的约束条件。如C和D设备 的使用限制。 对不严格限制的约束，连同原线性规划建模时的目标，均通过 目标约束来表达。 Page 4目标规划问题及其数学模型 3. 目标的优先级与权系数 在一个目标规划的模型中，为达到某一目标可牺牲其他 一些目标，称这些目标是属于不同层次的优先级。 优先级层次的高低可分别通过优先因子P1 ,P2 ,表示。 对于同一层次优先级的不同目标，按其重要程度可分别 乘上不同的权系数。权系数是一个个具体数字，乘上的权 系数越大，表明该目标越重要。 Page 5目标规划问题及其数学模型 4. 目标规划的目标函数 目标规划的目标函数(准则函数)是按各目标约束的正、负偏 差变量和赋予的优先因子及权系数构造的。 当每一目标值确定后，决策者的要求是尽可能缩小和目标值 的偏差。因此目标规划的目标函数的形式通常是 min z = f (d+,d) 其具体形式大致有三种： (1) 若要求恰好达到目标值，则应要求正、负偏差变量均尽 可能地小，这时，目标函数的形式为 min z = f (d+d) Page 6目标规划问题及其数学模型 4. 目标规划的目标函数 (3) 若要求超过目标值，即超过量不限，但负偏差变量要尽可能 地小，这时目标函数的形式为 min z = f (d) (2) 若要求不超过目标值，即允许达不到目标值，但正偏差变量 要尽可能地小，这时目标函数的形式为 min z = f (d+) Page 7目标规划问题及其数学模型 目标规划数学模型的一般形式 目标函数 目标约束 其中：gk为第k个目标约束的预期目标值， 和 为pl 优先因子 对应各目标的权系数。 系统约束 Page 8目标规划的图解分析法 目标规划的图解法：目标规划的图解法： 适用两个变量的目标规划问题，但其操作简单，原理一目了 然。同时，也有助于理解一般目标规划的求解原理和过程。 图解法解题步骤：图解法解题步骤： 1.将所有约束条件（包括目标约束和绝对约束，暂不考虑正负 偏差变量）的直线方程分别标示于坐标平面上。 2. 确定系统约束的可行域。 3. 在目标约束所代表的边界线上，用箭头标出正、负偏差变量 值增大的方向 Page 9目标规划的图解分析法 3. 求满足最高优先等级目标的解 4. 转到下一个优先等级的目标，在不破坏所有较高优先等级目标 的前提下，求出该优先等级目标的解 5. 重复4，直到所有优先等级的目标都已审查完毕为止 6. 确定最优解和满意解。 图解法解题步骤：图解法解题步骤： Page 10 目标规划的数学模型,特别是约束的结构与线性规划模型没 有本质的区别，只是它的目标不止是一个。 虽然其利用优先因子和权系数把目标写成一个函数的形式, 但在计算中无法按单目标处理。 可用单纯形法进行适当改进后求解。 目标规划的单纯形方法 Page 11 解目标规划问题的单纯形法的计算步骤 (1)建立初始单纯形表在表中将检验数行按优先因子个数 分别列成K行。初始的检验数需根据初始可行解计算出来，方 法同基本单纯形法。 当不含系统约束时，di- （i=1,2, ,K）构成了一组基本可行 解，这时只需利用相应单位向量把各级目标行中对应di- （ i=1,2, ,K）的量消成0即可得到初始单纯形表。置k 1； 目标规划的单纯形方法 Page 12 (2) 检查当前第k行中是否存在检验数小于0，且对应的前k-1 行的同列检验数为零。若有，取其中最小者对应的变量为换入 变量，转(3)。若无这样的检验数，则转(5)； (3) 按单纯形法中的最小比值规则确定换出变量，当存在两 个和两个以上相同的最小比值时，选取具有较高优先级别的变 量为换出变量，转（4）； (4) 按单纯形法进行换基运算，建立新的单纯形表，（注意 ：要对所有的行进行初等变换运算）返回(2)； (5) 当k K 时，计算结束。否则或者当满足下列准则时停 止：P1,PK行中所有的检验数都非负；若P1,Pi行所有检验 数非负，第Pi+1行存在负检验数，但在负检验数所在的列的上 面行中有正检验数。表中的解即为满意解。否则，置k = k+1， 返回（2）。 目标规划的单纯形方法 Page 13 例：电视机厂装配25寸和21寸两种彩电，每台电视机需装备 时间1小时，每周装配线计划开动40小时，预计每周25寸彩 电销售24台，每台可获利80元，每周21寸彩电销售30台， 每台可获利40元。 该厂目标： 1、充分利用装配线，避免开工不足。 2、允许装配线加班，但尽量不超过10小时。 3、尽量满足市场需求。 目标规划的单纯形方法 Page 14 解：设X1 , X2 分别表示25寸，21寸彩电产量 Min Z=p1d1-+p2d2+p3(2d3-+d4-) X1+X2 +d1- -d1+=40 X1 +X2+d2- -d2+=50 X1+d3- -d3+=24 X2 +d4- -d4+=30 X1 , X2 , di- , di+ 0 (i=1,2,3,4) 目标规划的单纯形方法 Page 15目标规划的单纯形方法 Page 16目标规划的单纯形方法 Page 17目标规划的单纯形方法 Page 18目标规划的单纯形方法 Page 19 例：已知目标规划问题例：已知目标规划问题 用单纯形法得到的最终标为表用单纯形法得到的最终标为表4 - 54 - 5 目标规划的灵敏度分析目标规划的灵敏度分析 Page 20 表表4 - 54 - 5 目标规划的灵敏度分析目标规划的灵敏度分析 Page 21 目标函数的优先等级变化为：目标函数的优先等级变化为： 分析原最优解有什么变化。分析原最优解有什么变化。 解：分析：（解：分析：（1 1）相当于检验数中第二行与第三行互换。）相当于检验数中第二行与第三行互换。 检验数仍为非负，最优解不变。检验数仍为非负，最优解不变。 分析：（分析：（2 2）相当于检验数中第一行与第二行互换。）相当于检验数中第一行与第二行互换。 有检验数为负，最优解变化了。有检验数为负，最优解变化了。 原问题的目标函数原问题的目标函数 目标规划的灵敏度分析目标规划的灵敏度分析 Page 22目标规划的灵敏度分析目标规划的灵敏度分析 Page 23目标规划的灵敏度分析目标规划的灵敏度分析 Page 24 目标规划数学模型的一般形式 其中：gk为第k个目标约束的预期目标值， 和 为pl 优先因子 对应各目标的权系数。 目标规划的层次算法 目标规划的求解原则：从高层到低层逐层优化。目标规划的求解原则：从高层到低层逐层优化。 Page 25目标规划的层次算法 目标规划的求解原则：从高层到低层逐层优化。 根据这个原则，求解目标规划的层次算法步骤如下： 步骤1：先对目标函数中的P1层次进行优化。建立第一层次的 线性规划模型LP1. LP1的目标函数为： 约束条件为： Page 26目标规划的层次算法 步骤2：接着对P2层次进行优化。根据下一层次优化时应在前 面各层次优化基础上进行的要求，若第一层次目标目标函数 最优值为z1*，则构建的P2层次的线性规划模型为LP2,其目标函 数为 约束条件为： Page 27目标规划的层次算法 步骤3：依次类推，得到Ps (s=2)层次进行优化时建立的线性 规划模型LPs为 约束条件为： 当进行到s=K时，对PK 层次建立的线性规划模型LPK的最优解 即为目标规划问题的满意解。 Page 28 例: P141. 目标规划的层次算法 Page 29 月份需求量(件) 最大产量(件)单位生产成本(元) 正常时间加班时间正常时间加班时间 18001600600100110 212001800800120130 320002000500125140 目标规划应用举例 Page 30目标规划应用举例 Page 31目标规划应用举例 Page 32目标规划应用举例 Page 33目标规划应用举例 Page 34目标规划应用举例 Page 35 例1: 某单位领导在考虑本单位职工的升级调资方案时,依次遵 守以下规定: (1)不超过月工资总额60000元; (2)每级人数不超过定编规定的人数; (3)、级的升级面尽可能达到现有人数的20%； (4)级不足的人数可录用新职工,又级的职工中有10%要退 休. 相关资料如下表: 目标规划应用举例 Page 36 等等级级工工资额资额 ( (元元/ /月月) )现现有人数有人数编编制人数制人数 2000 2000 15001500 10001000 1010 1212 1515 1212 1515 1515 37374242 目标规划应用举例 Page 37 解解: :设x1,x2,x3分别表示提升到、级和录用新职工的人数. P1:不超过月工资总额60000元; P2:每级人数不超过定编规定的人数; P3:、级的升级面尽可能达到现有人数的20% 调整以后各级的人数为: 级:10-1010%+ x1 级:12- x1+x2 级:15- x2+x3 目标规划应用举例 Page 38 分析: P1:不超过月工资总额60000元, P1d1+ 2000(10-1010%+ x1 )+1500(12- x1+x2)+1000(15- x2+x3)+ d1- d1+ =60000 P2:每级人数不超过定编规定的人数, P2(d2+ +d3+ +d4+) 级:10-1010%+ x1+d2- d2+ =12 级:12- x1+x2 +d3- d3+ =15 级:15- x2+x3 +d4- d4+ =15 目标规划应用举例 Page 39 P3:、级的升级面尽可能达到现有人数的20%, P3(d5- +d6-) 级: x1+d5 d5+ =1220% 级: x2 +d6 d6+ =1520% 目标规划应用举例 Page 40 数学模型为: Min z= P1d1+ P2(d2+ +d3+ +d4+)+P3(d5- +d6-) 2000(10-1010%+ x1 )+1500(12- x1+x2)+1000(15- x2+x3)+ d1- d1+ =60000 10-1010%+ x1+d2- d2+ =12 12- x1+x2 +d3- d3+ =15 15- x2+x3 +d4- d4+ =15 x1+d5 d5+ =1220% x2 +d6 d6+ =1520% X1,x2 , x3 0, di- di+ 0,i=1,2,3,4,5,6 目标规划应用举例 Page 41 例2:已知三个产地给四个销地供应某种产品,供需量与单位运价 表如下表: 销地 产地 B1B2B3B4产量 A15 2 6 7 300 A23 5 4 6 200 A3452 3 400 销量 200100450 250 90 0 1000 目标规划应用举例 Page 42 考虑调运方案时,依次考虑以下七项指标: P1: B4是重点保护单位必须全部满足其要求; P2:A3向B1提供的产量不少于100; P3:每个销地的供应量不小于需要量的80%; P4: 所订调运方案的总费用不超过最小调运方案的10%; P5:因路段的问题,尽量避免安排A2运往B4; P6:给B1和B3的供应率要相同; P7:力求总运费最省; 试求满意的调运方案 目标规划应用举例 Page 43 解:由于产量小于销量,假想一个产地A4,其产量为100. 用表上作业法求得最优表如下,最小运费为2950元. 销地 产地 B1B2B3B4产量 A1200 100 300 A20 200 200 A3 A4 250 150 100 400 100 销量 200100450 250 目标规划应用举例 Page 44 分析: 供应约束: 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 P1: B4是重点保护单位必须全部满足其要求,P1 d4- P2:A3向B1提供的产量不少于100, P2 d5- x31+ d5- d5+ =100 目标规划应用举例 Page 45 分析: P3:每个销地的供应量不小于需要量的80%, P3(d6- +d7-+d8-+ d9- ) 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 P4: 所订调运方案的总费用不超过最小调运方案的 10%, P4 d10+ 目标规划应用举例 Page 46 分析: P5:因路段的问题,尽量避免安排A2运往B4, P5 d11+ x24+ d11- d11+ =0 P6:给B1和B3的供应率要相同, P6 (d12-+d11+) 供应率=实际供应量/销量,即: (x11+x21 + x31) /200=(x13+x23 + x33 )/450,目标约束为: (x11+x21 + x31)-(200/450) (x13+x23 + x33 ) +d12- d12+ =0 P7:力求总运费最省, P7 d13+ 目标规划应用举例 Page 47 供应约束: 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 x31+ d5- d5+ =100 目标规划应用举例 Page 48 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 x24+ d11- d11+ =0 (x11+x21 + x31)-(200/450) (x13+x23 + x33 ) +d12- d12+ =0 Min z=P1 d4- +P2 d5-+P3(d6- +d7+-+d8-+ d9- )+ P4 d10+P5 d11+P6 (d12- +d11+)+ P7 d13+ 目标规划应用举例 Page 49 例3：友谊农场有友谊农场有3 3万亩农田欲种植玉米、大豆和小麦三种农作万亩农田欲种植玉米、大豆和小麦三种农作 物，各种作物每亩需施化肥分别为物，各种作物每亩需施化肥分别为0.120.12吨、吨、0.200.20吨、吨、0.150.15吨。预吨。预 计秋后玉米每亩可收获计秋后玉米每亩可收获500500千克，售价为千克，售价为0.240.24元元/ /千克千克, ,大豆每亩大豆每亩 可收获可收获200200千克千克, ,售价为售价为1.201.20元元/ /千克千克, ,小麦每亩可收获小麦每亩可收获300300千克千克, ,售售 价为价为0.700.70元元/ /千克千克. .农场年初规划时考虑如下几个方面农场年初规划时考虑如下几个方面: : : :年终收益不低于年终收益不低于350350万元万元; ; : :总产量不低于总产量不低于1.251.25万吨万吨; ; : :小麦产量以小麦产量以0.50.5万吨为宜万吨为宜; ; : :大豆产量不少于大豆产量不少于0.20.2万吨万吨; ; : :玉米产量不超过玉米产量不超过0.60.6万吨万吨; ; Page 50 : :农场现能提供农场现能提供50005000吨化肥吨化肥; ;若不够若不够, ,可在市场高价购买可在市场高价购买, ,但希望但希望 高价采购愈少愈好高价采购愈少愈好. . 试就该农场生产计划建立数学模型试就该农场生产计划建立数学模型( (不用求解不用求解). ). 玉米玉米大豆大豆小麦小麦 化肥化肥 吨吨/ /亩亩 0.120.120.200.200.150.15 收收获获 千克千克/ /亩亩 500500200200300300 售价售价 元元/ /千克千克 0.240.241.201.200.700.70 目标规划应用举例 Page 51 解解: :设种植玉米、大豆和小麦三种农作物各为亩设种植玉米、大豆和小麦三种农作物各为亩, ,该问题的数学模该问题的数学模 型为型为: : 目标规划应用举例 Page 52目标规划应用举例 例4 已知一个生产计划的线性规划模型如下，其中目标函数 为总利润，x1,x2 为产品A、B产量。 现有下列目标： 1. 要求总利润必须超过 2500 元； 2. 考虑产品受市场影响，为避免积压，A、B的生产量不超过 60 件 和 100 件； 3. 由于甲资源供应比较紧张，不要超过现有量140。 试建立目标规划模型，并用图解法求解。 Page 53目标规划应用举例 解：以产品 A,B 的单件利润比 2.5 :1 为权系数，模型如下： Page 54目标规划应用举例 0 x2 0 x1 140