第五章目标规划.ppt

《第五章目标规划.ppt》由会员分享，可在线阅读，更多相关《第五章目标规划.ppt（54页珍藏版）》请在三一文库上搜索。

1、第五章 目标规划,目标规划问题的模型 目标规划问题的解法,Goal Programming,1、理解目标规划概念； 2、掌握目标规划建模技巧； 3、能够运用单纯形法求解模型。,本章教学基本要求,一个公司可能同时有许多目标； 比如：保持比较稳定的价格和利润；提高自己产品的市场占有率；增加产品的品种；维持比较稳定的职工队伍等。 各个目标并非都相互协调，目标之间甚至还可能是相互矛盾的； 由于目标之间的不协调性和矛盾性，要想同时实现每一个目标，显然是不可能的，因此要寻求一种折衷的方案，目标规划就是寻找最优折衷方案的一种有效的方法。,为什么会产生目标规划问题？,东风电机厂生产型和型两种TV受到A、B两种

2、关键资源的限制必须从另外的厂购买。生产每台电视机对资源的耗定额及每天可利用的资源数量已知。,东风厂的管理部门提出生产经营要达到3个目标 ：,a)原材料A的每日用量控制在90 公斤以内； b)型TV的日产量在15台以上； c) 日利润超过140(百元),多目标决策问题举例,首先对于管理部门提出的每一个目标(Objective)，由决策者确定一个具体的数量目标(numeric goal ，也叫管理目标),并对每一个目标 ，建立目标函数(objective function)，然后寻求一个使目标函数和对应目标(goal)之间的偏差(赋权)之和达到最小的解。,目标规划的基本思想,具有连续变量的线性目标

3、规划，简称目标规划(Goal Programming,简记为GP) 。 目标规划中目标函数和约束条件可以是线性的，也可以是非线的，变量可以是连续的，也可以是离散的。本书中我们只研究具有连续变量的线性目标规划。,本章目标规划的研究范围,相同等级的目标 有优先等级的目标 有赋权的优先等级的目标,一、目标规划的模型,例5-1 ：,东风电机厂生产型和型两种TV受到A、B两种关键资源的限制必须从另外的厂购买，生产每台电视机对资源的耗定额及每天可利用的资源数量如表5.1。 需要解决的问题：每天应如何安排两种TV的产量，才能使利润最大？,表5.1,1、相同等级的目标规划的模型,例5-1 见书P150页 ，问

4、题1：,设生产TV型和型产量各为x1，x2则得LP模型为 ： max z =4 x1+5 x2 s1t 2 x1+3 x2100 4 x1+2x280 x1.x20,可求最优解为x1=5 x2=30 Z=170,但市场形势发生变化： 供应 A 原料的厂家提出，减少10公斤的供应； 型产品供不应求，必须扩展型产品的产量x1 。,东风厂的管理部门提出对下一阶段生产经营要达到3个目标 ：,a)原材料A的每日用量控制在90 公斤以内； b)型TV的日产量在15台以上； c) 日利润超过140(百元)。,如何用目标规划的方法来描述和解决上述问题,（1）原材料A的每日用量控制在90公斤以内,2 x1+3x

5、290,引进两个偏差变量 d-i和di+ d-i表示原材料A的实际日用量未达到目标值的部分； di+表示A的实际日用量超过目标值部分 d+10 d-10 d+1 d-1=0,90是数量目标，原材料A的实际取值(每日实际用量)与目标值之间可能有一个偏差,2 x1+3x2 d1+d1-=90目标约束,min d+1,（2）型电视机的日产量在15台以上,x115,用d2-和d2+分别表示型电视机的日产量未达到和超过目标值的部分。,x1- d+2+ d-2=15 目标约束,min d-2,（3）日利润超过140(百元),4x1+5x2140,用d-3和d+3分别表示日利润未达到和超过目标值的部分,4

6、x1+5x2 d3+ d3-=140 目标约束,min d-3,目标规划模型(GP问题1) 上述目标对于该厂来说，是同等重要的 ，因此：,min z = d1+ d2-+ d3- s.t. 2x1+3x2-d1+ d1-=90 4x1+2x2+s2 =80 x1- d2+ d2- =15 4x1+5x2-d3+ d3-=140 x1, x2, s2, d1+, d1-, d2+,d2- , d3+,d3-0,东风厂的管理部门提出对下一阶段生产经营要达到3个目标，决策者认为上例中3个目标并非同等重要，其中：（b）目标为最重要；（c）目标次重要；（a）目标排在第三位 ：,b)型TV的日产量在15台

7、以上； c) 日利润超过140(百元) a)原材料A的每日用量控制在90 公斤以内,如何用目标规划的方法来描述和解决上述问题,2、有优先等级的目标规划的模型,优先因子：描述问题中目标重要性程度的差别，一般用pi表 示，通常i值越小，代表的优先程度越高。 在目标规划中：对于最重要目标，赋予优先因子P1 第二位重要目标，赋予优先因子P2 以此类推，各个优先因子是一些特殊的正常数，它们之间有如下关系： P1 P2 P3 “ ”远远大于,min z = P3d1+ P1d2-+ P2d3- s.t. 2x1+3x2-d1+ d1-=90 4x1+2x2+s2 =80 x1- d2+ d2- =15 4

8、x1+5x2-d3+ d3-=140 x1, x2, s2, d1+, d1-, d2+,d2- , d3+,d3-0,根据东风厂对3个目标的分级，可写出GP问题：,3、有赋权的优先等级的目标规划的模型,有关的偏差变量定义如下: d1+和d1-分别表示日利润超过和未达到目标值的部分; d2+和d2-分别表示原材料A的日用量超过和未达到目标值的部分; d3+和d3-分别表示原材料B的日用量超过和未达到目标值; d4+和d4-分别表示I型电视机的日产量超过和未达到目标值的部分; d5+和d5-分别表示II型电视机的日产量超过和未达到目标值的部分。,min z = 2P1d3+ P1d2+ P2d1

9、-+P3d5-+ P4d4- s.t. 4x1+5x2-d1+ d1-=110 2x1+3x2 -d2+ d2-=70 4x1+2x2 -d3+ d3-=40 x1 -d4+ d4-=5 x2 -d5+ d5-=18 x1, x2, d1+,d5+, d1-d5- 0,各目标有优先等级和赋权情况下 ，可写出GP问题：,概念 偏差变量：实际值与目标值之间差距的变量表示，通常以 di+ di-表示，分别为正、负偏差变量，且有di+0、 di- 0， di+ di- =0 优先因子：描述问题中目标重要性程度的差别，一般用pi表 示，通常i值越小，代表的优先程度越高。 目标约束：用来描述允许对给定目标

10、值有一定偏离程度的限 制条件。,目标规划的概念,目标规划模型的特点： 1、引进正负偏差变量 2、模型中必须有目标约束 3、目标函数为偏差变量的表达式 4、以优先级因子描述目标的重要性程度,目标规划的模型,解GP问题,我们首先要找一个初始基并作其单纯形表, 由于GP模型的约束条件中,含有许多负偏差变量,其系 数均为1,故常可取它们为初始基变量； 但因目标函数中也常含有负偏差变量,因此将目标函数 行搬上单纯形表时,应注意将其中基变量的系数变为0。,GP问题初始基的确定,1、相同等级的目标规划的解法,为了简化制表手续,节省不必要的重复书写,我们将GP 问题的初始单纯形表设计为有两个z行的形式； 第一

11、个z行就是将GP模型中z行的系数反号而得,并将这 一行用括号括起来； 第二个z行则是正规单纯形表中的z行,其中基变量的检 验数都已化为0.,GP问题单纯形表的结构,例5-1 求解此GP问题,min z = d1+ d2-+ d3- s.t. 2x1+3x2-d1+ d1-=90 4x1+2x2+s2 =80 x1- d2+ d2- =15 4x1+5x2-d3+ d3-=140 x1, x2, s2, d1+, d1-, d2+,d2- , d3+,d3-0,例5-1 建立初始的单纯形表,X1为进基变量，d2-为离基变量,X2为进基变量，s2为离基变量,d2-为进基变量，d3-为离基变量,得到

12、最优解,1.d1- =10, d1+=0,则A的日用量不超过90公斤,实际为 2x1+3x2=80，实现目标 2.d2- =5,则有d2+=0, x1=10即I型TV的日产量仅有10台, 不在15台以上，没达到目标 3.则通过有x2=20, x1=10可知 4x1+5x2=4*10+5*20=140, 则有d3+= d3- =0即日利润正好为140百元。 恰好实现目标。,负偏差变量作为初始基变量； 但因目标函数中也常含有负偏差变量,因此将目标函数 行搬上单纯形表时,应注意将其中基变量的系数变为0.,GP问题初始基的确定,2、有优先等级的目标规划的解法,由于此类问题的目标函数中含有各个优先因子,

13、所以在单纯形表的z-行中,各检验数将是这些优先因子的线性组合； 我们将z-行写成若干行,每一级优先因子都各占一行； 前一段中节省制表的方法,我们现在同样采用,不过在这里, z-行已被分成若干行了,即有几个优先因子就分成几行,在初始表中用括号括起来的也不是一行,而是好几行.,GP问题单纯形表的结构,例5-2 求解此GP问题,min z = P3d1+ P1d2-+ P2d3- s.t. 2x1+3x2-d1+ d1-=90 4x1+2x2+s2 =80 x1- d2+ d2- =15 4x1+5x2-d3+ d3-=140 x1, x2, s2, d1+, d1-, d2+,d2- , d3+,

14、d3-0,例5-2 运算得单纯形表最优表,因为P1P2P3，所以检验数的符号首先取决于P1 行中各数的符号,其次决定于P2行中各数的符号,依 次类推。 P1行中各数全部0,故P1级目标已实现最优。划去 P1行和非基变量所在列，得到新单纯形表继续运算 当所有非基变量在检验数行的系数都0时，获得 最优解。,例5-2 建立初始单纯形表,X1为进基变量，d2-为离基变量,例5-2 单纯形表2,X2为进基变量，S2为离基变量,例5-2 建立单纯形表3,求得最优解,例5-2 可知最优折衷结果为：,x1=15, d2-= d2+=0, 则P1级目标恰好达到. 2. x1=15, x2=10, d3- =30

15、, 4 x1+5x2=4*15+5*10=110140, 即有日利润目标比要求值还差30百元, 则P2级目标没实现. 3. P3级目标d1- =30,则d1+=0, 2x1+3x2=2*15+3*10=60事实上A还剩30公斤. 日产量不超过90公斤,也已达到 则P3级目标实现.,负偏差变量作为初始基变量； 但因目标函数中也常含有负偏差变量,因此将目标函数 行搬上单纯形表时,应注意将其中基变量的系数变为0.,GP问题初始基的确定,3、有赋权优先等级的目标规划的解法,将z 行写成若干行,每一级优先因子各占一行； 赋权作为Pi级对应的系数写在目标函数检验数行； 以后求解方法实际上与前例相同,只是计

16、算更加繁琐,GP问题单纯形表的结构,例5-3 求解此GP问题,min z = 2P1d3+ P1d2+ P2d1-+P3d5-+ P4d4- s.t. 4x1+5x2-d1+ d1-=110 2x1+3x2 -d2+ d2-=70 4x1+2x2 -d3+ d3-=40 x1 -d4+ d4-=5 x2 -d5+ d5-=18 x1, x2, d1+,d5+, d1-d5- 0,例5-3 可知最优折衷结果为(P195)：,两个P1级目标(两种原材料日用量的限制)均已实现(d2+=d3+=0) P2级目标(日利润110百元)不能完全实现,还差10百元(d1-=10) P3级目标(II型电视机日产

17、量不少于18台)也已实现，事实上还超额2台(d5+=2) P4级目标(I型电视机日产量5台)没有实现(x1=0, d4-=5),概念 偏差变量：实际值与目标值之间差距的变量表示，通常以 di+ di-表示，分别为正、负偏差变量，且有di+0、 di- 0， di+ di- =0 优先因子：描述问题中目标重要性程度的差别，一般用pi表 示，通常i值越小，代表的优先程度越高。 目标约束：用来描述允许对给定目标值有一定偏离程度的限 制条件。,目标规划小结,目标规划模型的特点 1、引进正负偏差变量 2、模型中必须有目标约束 3、目标函数为偏差变量的表达式 4、以优先级因子描述目标的重要性程度,目标规划

18、的决策案例,例题1 某公司管理层的目标: 保持稳定的利润; 增加市场份额; 多样化的产品线; 保持稳定的价格; 提高员工的士气; 保持对业务的控制力; 增加公司的声誉.,Min z=5 y1-+ 2y2+ + 4y2- + 3y3+ S.t 12x1+9x2+15x3- y1+ y1-=125 5x1+3x2+4x3- y2+ y2-=40 5x1+7x2+8x3- y3+ y3-=55 xi0 , yj+, yj- 0 X1=25/3,x2=0,x3=5/3, y1+=0, y1-=0, y2+=25/3, y2-=0, y3+=0, y3-=0,z=50/3,例题2，一位投资商有一笔资金准

19、备购买股票。资金总额为90000元，目前可选的股票有A和B两种（可以同时投资于两种股票）。其价格以及年收益率和风险系数如下表： 从上表可知，A股票的收益率为（320）10015，股票B的收益率为4501008，A的收益率比B大，但同时A的风险也比B大。这也符合高风险高收益的规律。 试求一种投资方案，使得一年的总投资风险不高于700，且投资收益不低于10000元。,显然，此问题属于目标规划问题。它有两个目标变量：一是限制风险，一是确保收益。在求解之前，应首先考虑两个目标的优先权。 假设第一个目标（即限制风险）的优先权比第二个目标（确保收益）大，这意味着求解过程中必须首先满足第一个目标，然后在此基

20、础上再尽量满足第二个目标。 建立模型： 设x1、x2分别表示投资商所购买的A股票和B股票的数量。 首先考虑资金总额的约束：总投资额不能高于90000元。即 20x150x290000。,一、约束条件 再来考虑风险约束：总风险不能超过700。投资的总风险为 0.5x10.2x2。引入两个变量d1+和d1-,建立等式如下： 0.5x1 +0.2x2-d1+d1-=700。 其中，d1+表示总风险高于700的部分，d1-表示总风险少于700的 部分，d1+0。 目标规划中把d1+、d1-这样的变量称为偏差变量。偏差变量的作 用是允许约束条件不被精确满足。,再来考虑年收入: 年收入=3x1+4x2 引入变量d2+和d2-，分别表示年收入超过与低于10000的数量。 于是，第2个目标可以表示为 3x1+4x2-d2+d2-=10000。,二、目标规划模型的标准化 例6中对两个不同优先权的目标单独建立线性规划进行求解。为简 便，把它们用一个模型来表达，如下： Min P1（d1+）+P2（d2-） s.t. 20x150x290000 0.5x1 +0.2x2-d1+d1-=700 3x1+4x2-d2+d2-=10000 x1,x2,d1+,d1-,d2+,d2-0,目标规划解题方法： 单纯形法:按单纯形法求解一般目标规划问题的满意解,求解时需按优先级的顺序进行逐步优化 。,