管理运筹学目标规划.ppt

《管理运筹学目标规划.ppt》由会员分享，可在线阅读，更多相关《管理运筹学目标规划.ppt（53页珍藏版）》请在三一办公上搜索。

1、1,第九章 目标规划,1 目标规划问题举例2 目标规划的图解法3 复杂情况下的目标规划4 加权目标规划 5 目标规划的单纯型法,2,1目标规划问题举例,线性规划模型的特征是在满足一组约束条件下，寻求一个目标的最优解（最大值或最小值）。而在现实生活中最优只是相对的，或者说没有绝对意义下的最优，只有相对意义下的满意。1978年诺贝尔经济学奖获得者.西蒙(H.A.Simon-美国卡内基-梅隆大学,1916-)教授提出“满意行为模型要比最大化行为模型丰富得多”，否定了企业的决策者是“经济人”概念和“最大化”行为准则，提出了“管理人”的概念和“令人满意”的行为准则，对现代企业管理的决策科学进行了开创性的

2、研究,3,1目标规划问题举例,例1企业生产不同企业的生产目标是不同的。多数企业追求最大的经济效益。但随着环境问题的日益突出，可持续发展已经成为全社会所必须考虑的问题。因此，企业生产就不能再如以往那样只考虑企业利润，必须承担起社会责任，要考虑环境污染、社会效益、公众形象等多个方面。兼顾好这几者关系，企业才可能保持长期的发展。例2商务活动企业在进行盈亏平衡预算时，不能只集中在一种产品上，因为某一种产品的投入和产出仅仅是企业所有投入和产出的一部分。因此，需要用多产品的盈亏分析来解决具有多个盈亏平衡点的决策问题（多产品的盈亏平衡点往往是不一致的）。,4,1目标规划问题举例,例3投资企业投资时不仅仅要考

3、虑收益率，还要考虑风险。一般地，风险大的投资其收益率更高。因此，企业管理者只有在对收益率和风险承受水平有明确的期望值时，才能得到满意的决策。例4裁员同样的，企业裁员时要考虑很多可能彼此矛盾的因素。裁员的首要目的是压缩人员开支，但在人人自危的同时员工的忠诚度就很难保证，此外，员工的心理压力、工作压力等都会增加，可能产生负面影响。例5营销营销方案的策划和执行存在多个目标。既希望能达到立竿见影的效果，又希望营销的成本控制在某一个范围内。此外，营销活动的深入程度也决定了营销效果的好坏和持续时间。,5,1目标规划问题举例,【例1.】考虑例1.1资源消耗如表9-1所示。x1、x2、x3分别为甲、乙、丙的产

4、量。,使企业在计划期内总利润最大的线性规划模型为：,表9-1,1.1 引例,6,1目标规划问题举例,最优解X（50，30，10），Z3400,7,1目标规划问题举例,现在决策者根据企业的实际情况和市场需求，需要重新制定经营目标，其目标的优先顺序是：（1）利润不少于3200元（2）产品甲与产品乙的产量比例尽量不超过1.5（3）提高产品丙的产量使之达到30件（4）设备加工能力不足可以加班解决，能不加班最好不加班（5）受到资金的限制，只能使用现有材料不能再购进,【解】设甲、乙、丙产品的产量分别为x1、x2、x3。如果按线性规划建模思路，最优解实质是求下列一组不等式的解,8,1目标规划问题举例,通过计

5、算不等式无解，即使设备加班10小时仍然无解在实际生产过程中生产方案总是存在的，无解只能说明在现有资源条件下，不可能完全满足所有经营目标,这种情形是按事先制定的目标顺序逐项检查，尽可能使得结果达到预定目标，即使不能达到目标也使得离目标的差距最小，这就是目标规划的求解思路，对应的解称为满意解下面建立例1.1的目标规划数学模型,9,1目标规划问题举例,设d为未达到目标值的差值，称为负偏差变量（negative deviation variable）d+为超过目标值的差值，称为正偏差变量（positive deviation variable）,d0、d0,设d1-未达到利润目标的差值,d1+为超过目

6、标的差值,当利润小于3200时,d1且d10,有40 x1+30 x2+50 x3+d1=3200成立当利润大于3200时，d1且d1，有40 x1+30 x2+50 x3-d1+=3200成立当利润恰好等于3200时，d1=且d1+=0,有40 x1+30 x2+50 x3=3200成立实际利润只有上述三种情形之一发生，因而可以将三个等式写成一个等式,40 x1+30 x2+50 x3+d1d1+=3200,10,1目标规划问题举例,（2）设 分别为未达到和超过产品比例要求的偏差变量,则产量比例尽 量不超过1.5的数学表达式为：,（3）设d3、d分别为品丙的产量未达到和超过30件的偏差变量，

7、则产量丙的产量尽可能达到30件的数学表达式为：,利润不少于3200理解为达到或超过3200，即使不能达到也要尽可能接近3200,可以表达成目标函数d1取最小值，则有,11,1目标规划问题举例,（4）设d4、d4+为设备A的使用时间偏差变量,d5、d5+为设备B的使用时间偏差变量，最好不加班的含义是 d4+和d5+同时取最小值，等价 于d4+d5+取最小值，则设备的目标函数和约束为：,（5）材料不能购进表示不允许有正偏差，约束条件为小于等于约束,由于目标是有序的并且四个目标函数非负，因此目标函数可以表达成一个函数：,12,1目标规划问题举例,式中：Pj（j=1,2,3,4）称为目标的优先因子，第

8、一目标优于第二目标，第二目标优于第三目标等等，其含义是按P1、P2、的次序分别求后面函数的最小值.则问题的目标规划数学模型为：,13,2目标规划的图解法,例6一位投资商有一笔资金准备购买股票。资金总额为90000元，目前可选的股票有A和B两种（可以同时投资于两种股票）。其价格以及年收益率和风险系数如表1：从上表可知，A股票的收益率为（320）10015，股票B的收益率为4501008，A的收益率比B大，但同时A的风险也比B大。这也符合高风险高收益的规律。试求一种投资方案，使得一年的总投资风险不高于700，且投资收益不低于10000元。用来全部投资一个股票两个目标不能同时达到.,14,2目标规划

9、的图解法,显然，此问题属于目标规划问题。它有两个目标变量：一是限制风险，一是确保收益。在求解之前，应首先考虑两个目标的优先权。假设第一个目标（即限制风险）的优先权比第二个目标（确保收益）大，这意味着求解过程中必须首先满足第一个目标，然后在此基础上再尽量满足第二个目标。建立模型：设x1、x2分别表示投资商所购买的A股票和B股票的数量。首先考虑资金总额的约束：总投资额不能高于90000元。即 20 x150 x290000。,15,2目标规划的图解法,一、约束条件 再来考虑风险约束：总风险不能超过700。投资的总风险为0.5x10.2x2。引入两个变量d1+和d1-,建立等式如下：0.5x1+0.

10、2x2=700+d1+-d1-其中，d1+表示总风险高于700的部分，d1-表示总风险少于700的部分，d1+0。目标规划中把d1+、d1-这样的变量称为偏差变量。偏差变量的作用是允许约束条件不被精确满足。,16,2目标规划的图解法,把等式转换，可得到 0.5x1+0.2x2-d1+d1-=700。再来考虑年收入:年收入=3x1+4x2 引入变量d2+和d2-，分别表示年收入超过与低于10000的数量。于是，第2个目标可以表示为 3x1+4x2-d2+d2-=10000。,17,2目标规划的图解法,二、有优先权的目标函数 本问题中第一个目标的优先权比第二个目标大。即最重要的目标是满足风险不超过

11、700。分配给第一个目标较高的优先权P1,分配给第二个目标较低的优先权P2。针对每一个优先权，应当建立一个单一目标的线性规划模型。首先建立具有最高优先权的目标的线性规划模型，求解；然后再按照优先权逐渐降低的顺序分别建立单一目标的线性规划模型，方法是在原来模型的基础上修改目标函数，并把原来模型求解所得的目标最优值作为一个新的约束条件加入到当前模型中，并求解。,18,2目标规划的数学模型,（1）目标规划数学模型的形式有：线性模型、非线性模型、整数模型、交互作用模型等（2）一个目标中的两个偏差变量di-、di+至少一个等于零，偏差变量向量的叉积等于零：dd=0,（3）一般目标规划是将多个目标函数写成

12、一个由偏差变量构成的函数求最小值，按多个目标的重要性，确定优先等级，顺序求最小值,（4）按决策者的意愿，事先给定所要达到的目标值当期望结果不超过目标值时，目标函数求正偏差变量最小;当期望结果不低于目标值时，目标函数求负偏差变量最小;当期望结果恰好等于目标值时，目标函数求正负偏差变量之和最小,9.2 数学模型,19,2目标规划的数学模型,（5）由目标构成的约束称为目标约束，目标约束具有更大的弹性，允许结果与所制定的目标值存在正或负的偏差，如例1.1中的5个等式约束；如果决策者要求结果一定不能有正或负的偏差，这种约束称为系统约束，如例1.1的材料约束；,（6）目标的排序问题。多个目标之间有相互冲突

13、时，决策者首先必须对目标排序。排序的方法有两两比较法、专家评分等方法，构造各目标的权系数，依据权系数的大小确定目标顺序；,（7）合理的确定目标数。目标规划的目标函数中包含了多个目标，决策者对于具有相同重要性的目标可以合并为一个目标，如果同一目标中还想分出先后次序，可以赋予不同的权系数，按系数大小再排序。例如，在例1.1中要求设备B的加班时间不超过设备A的时间，目标函数可以表达为,表示在中先求 最小再求 最小。,20,2目标规划的数学模型,（8）目标规划的一般模型设xj（j=1,2,n）为决策变量,式中p k 为第k 级优先因子,k=1、2、K；wkl-、wkl+，为分别赋予第l个目标约束的正负

14、偏差变量的权系数；gl为目标的预期目标值，l=1,L(4.1b)为系统约束,（4.1c）为目标约束,21,2目标规划的数学模型,【例1.2】某企业集团计划用1000万元对下属5个企业进行技术改造，各企业单位的投资额已知，考虑2种市场需求变化、现有竞争对手、替代品的威胁等影响收益的4个因素，技术改造完成后预测单位投资收益率(（单位投资获得利润/单位投资额）100)如表12所示,集团制定的目标是：（1）希望完成总投资额又不超过预算；（2）总期望收益率达到总投资的30%；（3）投资风险尽可能最小；（4）保证企业5的投资额占20%左右集团应如何作出投资决策,22,2目标规划的数学模型,表12,23,2

15、目标规划的数学模型,【解】设xj（j=1,2,5）为集团对第 j 个企业投资的单位数,（1）总投资约束：,（2）期望利润率约束：,整理得,24,2目标规划的数学模型,(3）投资风险约束投资风险值的大小一般用期望收益率的方差表示，但方差是x的非线性函数这里用离差（rijE(rj)）近似表示风险值，例如，集团投资5个企业后对于市场需求变化第一情形的风险是：则4种因素风险最小的目标函数为：，约束条件为,25,2目标规划的数学模型,根据目标重要性依次写出目标函数，整理后得到投资决策的目标规划数学模型：,26,2目标规划的数学模型,【例1.3】车间计划生产I、II 两种产品，每种产品均需经过A、B两道工

16、序加工工艺资料如表43所示,（1）车间如何安排生产计划，使产值和利润都尽可能高（2）如果认为利润比产值重要，怎样决策,表13,27,2目标规划的数学模型,【解】设x1、x2分别为产品甲和产品乙的日产量，得到线性多目标规划模型：,28,2目标规划的数学模型,（1）将模型化为目标规划问题首先，通过分别求产值最大和利润最大的线性规划最优解产值最大的最优解：X(1)（20，40），Z13800利润最大的最优解：X(2)（30，30），Z2540目标确定为产值和利润尽可能达到3800和540，得到目标规划数学模型：,29,2目标规划的图解法,三、图解法1针对优先权最高的目标建立线性规划建立线性规划模型如

17、下：Min d1+s.t.20 x150 x290000 0.5x1+0.2x2-d1+d1-=700 3x1+4x2-d2+d2-=10000 x1,x2,d1+,d1-0,30,2目标规划的图解法,31,2目标规划的图解法,2针对优先权次高的目标建立线性规划优先权次高（P2）的目标是总收益超过10000。建立线性规划如下：Min d2-s.t.20 x150 x290000 0.5x1+0.2x2-d1+d1-=700 3x1+4x2-d2+d2-=10000 d1+0 x1,x2,d1+,d1-,d2+,d2-0,32,2目标规划的图解法,33,2目标规划的图解法,目标规划的这种求解方法

18、可以表述如下：1确定解的可行区域。2对优先权最高的目标求解，如果找不到能满足该目标的解，则寻找最接近该目标的解。3对优先权次之的目标进行求解。注意：必须保证优先权高的目标不变。4.重复第3步，直至所有优先权的目标求解完。,34,2目标规划的图解法,四、目标规划模型的标准化 例6中对两个不同优先权的目标单独建立线性规划进行求解。为简便，把它们用一个模型来表达，如下：Min P1（d1+）+P2（d2-）s.t.20 x150 x290000 0.5x1+0.2x2-d1+d1-=700 3x1+4x2-d2+d2-=10000 x1,x2,d1+,d1-,d2+,d2-0,35,2目标规划的图解

19、法,【例】企业计划生产I、II 两种产品，这些产品需要使用两种材料，要在两种不同设备上加工工艺资料如表44所示,表44,36,2目标规划的图解法,【解】设x1、x2分别为产品甲和产品乙的产量，目标规划数学模型为：,企业怎样安排生产计划，尽可能满足下列目标：(1)力求使利润指标不低于80元(2)考虑到市场需求,、II两种产品的生产量需保持1:1的比例(3)设备A既要求充分利用，又尽可能不加班(4)设备B必要时可以加班，但加班时间尽可能少(5)材料不能超用。,37,(2),(1),(3),(4),x2,x1,(6),(5),o,4,6,4,6,2,2,图41,A,B,C,满意解C(3,3),满意解

20、X(3,3),38,2目标规划的图解法,(3),x1,x2,20,40,60,80,100,20,40,60,80,100,(2),(1),(4),B,C,满意解是线段 上任意点，端点的解是 B(100/3，80/3)，C(60，0)决策者根据实际情形进行二次选择,A,39,2目标规划的图解法,(3),x1,x2,20,40,60,80,100,20,40,60,80,100,(2),(1),(4),图53,B,C,满意解是点 B，X=(100/3，80/3),A,40,(3),x1,x2,20,40,60,80,100,20,40,60,80,100,(2),(1),(4),满意解是点 A，

21、X=(20，40),A(20,40),D(80/9,560/9),注：线段DA是第二目标函数的组合，点A对应的偏差：d2-=100,d3=0点D对应的偏差：d2-=0,2d3=2200/9=400/9,41,3复杂情况下的目标规划,例7一工艺品厂商手工生产某两种工艺品A、B，已知生产一件产品A需要耗费人力2工时，生产一件产品B需要耗费人力3工时。A、B产品的单位利润分别为250元和125元。为了最大效率地利用人力资源，确定生产的首要任务是保证人员高负荷生产，要求每周总耗费人力资源不能低于600工时，但也不能超过680工时的极限；次要任务是要求每周的利润超过70000元；在前两个任务的前提下，为

22、了保证库存需要，要求每周产品A和B的产量分别不低于200和120件，因为B产品比A产品更重要，不妨假设B完成最低产量120件的重要性是A完成200件的重要性的1倍。试求如何安排生产？,42,3复杂情况下的目标规划,解：本问题中有3个不同优先权的目标，不妨用P1、P2、P3表示从高至低的优先权。对应P1有两个目标：每周总耗费人力资源不能低于600工时,也不能超过680工时；对应P2有一个目标：每周的利润超过70000元；对应P3有两个目标：每周产品A和B的产量分别不低于200和120件。,43,3复杂情况下的目标规划,采用简化模式，最终得到目标线性规划如下：Min P1(d1+)+P1(d2)+

23、P2(d3-)+P3(d4-)+P3(2d5-)s.t.2x1+3x2-d1+d1-=680 对应第1个目标 2x1+3x2-d2+d2-=600 对应第2个目标 250 x1+125x2-d3-+d3+70000 对应第3个目标 x1-d4+d4-=200 对应第4个目标 x2-d5+d5-=120 对应第5个目标 x1,x2,d1+,d1-,d2+,d2-,d3+,d3-,d4+,d4-,d5+,d5-0,44,3复杂情况下的目标规划,使用运筹学软件求解可得：x1=250；x2=60；d1+=0；d1-=0；d2+=80；d2-=0；d3+=0；d3-=0；d4+=50；d4-=0；d5+

24、=0；d5-=60，目标函数d4-+2d5-=120。可见，目标1、目标3和目标4达到了，但目标2、目标5都有一些偏差。,45,4加权目标规划,加权目标规划是另一种解决多目标决策问题的方法，其基本方法是通过量化的方法分配给每个目标的偏离的严重程度一个罚数权重，然后建立总的目标函数，该目标函数表示的目标是要使每个目标函数与各自目标的加权偏差之和最小，假设所有单个的目标函数及约束条件都符合线性规划的要求，那么，整个问题都可以描述为一个线性规划的问题。如果在例7中我们对每周总耗费的人力资源超过680工时或低于600工时的每工时罚数权重定为7；每周利润低于70000元时，每元的罚数权重为5；每周产品A

25、产量低于200件时每件罚数权重为2，而每周产品B产量低于120件时每件罚数权重为4。,46,4加权目标规划,则其目标函数化为：min7d1+7d2-+5d3-+2d4-+4d5-这就变成了一个普通的单一目标的线性规划问题 min7d1+7d2-+5d3-+2d4-+4d5-s.t.2x1+3x2-d1+d1-=680 2x1+3x2-d2-+d2+=680 250 x1+125x2-d3-+d3+=70000 x1-d4+d4-=200 x2-d5+d5-=120 x1,x2,d1+,d1-,d2-,d2+,d3+,d3-,d4+,d4-,d5+,d5-0。,47,5目标规划的单纯型法,单纯形

26、法求解目标规划可参照第一章的步骤，只是目标规划的检验要按优先级顺序逐级进行，不同的是：（1）首先使得检验数中P1的系数非负，再使得P2的系数非负，依次进行；（2）当P1、P2、Pk对应的系数全部非负时得到最优解；（3）如果P1，Pi行系数非负，而Pi+1行存在负数，并且负数所在列上面P1，Pi行中存在正数时，得到满意解，计算结束,48,5目标规划的单纯型法,【例4.6】用单纯形法求解下述目标规划问题,【解】以d1、d2、d3为基变量，求出检验数，将检验数中优先因子分离出来，每一优先级做一行，列出初始单纯形表4-5,49,5目标规划的单纯型法,表45,50,5目标规划的单纯型法,表45中，P1行

27、中(2)最小，则x2进基，求最小比值易知d1出基，将第二列主元素化为1，其余元素化为零，得到表46,表46,51,5目标规划的单纯型法,表46中P1行全部检验数非负，表明第一目标已经得到优化P2行存在负数，x1的检验数为P20，选x1进基（也可以选d1+进基），则d3出基，迭代得到表4-7,表4-7,52,5目标规划的单纯型法,在表4-7中，P1行的系数全部非负，P2行存在负数，d1+的检验数2/3P20，选d1+进基，则x1出基，迭代得到表4-8应当注意，表4-7中不能选d2+进基，检验数P12/3P2应理解为“大于零”，P1、P2是优先级别的比较，而不是“数”的比较,表48,53,5目标规划的单纯型法,表4-8中P2行的（2）小于零，但（2）列上面P1行存在正数1，检验数P12P20,所有检验数非负，得到满意解X（0，40）,【例】,