运筹学课件Ch4目标规划.ppt

,Chapter 4 目标规划Goal Programming,运筹学Operations Research,4.1 目标规划数学模型 Mathematical Model of GP4.2 目标规划的图解法 The graphical method of GP4.3 单纯形法 Simplex Method,4.1 目标规划数学模型Mathematical Model of GP,2023/8/27,线性规划模型的特征是在满足一组约束条件下，寻求一个目标的最优解（最大值或最小值）。而在现实生活中最优只是相对的，或者说没有绝对意义下的最优，只有相对意义下的满意。1978年诺贝尔经济学奖获得者.西蒙(-美国卡内基-梅隆大学,1916-)教授提出“满意行为模型要比最大化行为模型丰富得多”，否定了企业的决策者是“经济人”概念和“最大化”行为准则，提出了“管理人”的概念和“令人满意”的行为准则，对现代企业管理的决策科学进行了开创性的研究,4.1目标规划的数学模型Mathematical Model of GP,2023/8/27,【例4.】考虑例1.1资源消耗如表4-1所示。x1、x2、x3分别为甲、乙、丙的产量。,使企业在计划期内总利润最大的线性规划模型为：,表4-1,4.1.1 引例,4.1目标规划的数学模型Mathematical Model of GP,2023/8/27,最优解X（50，30，10），Z3400,4.1目标规划的数学模型Mathematical Model of GP,2023/8/27,现在决策者根据企业的实际情况和市场需求，需要重新制定经营目标，其目标的优先顺序是：（1）利润不少于3200元（2）产品甲与产品乙的产量比例尽量不超过1.5（3）提高产品丙的产量使之达到30件（4）设备加工能力不足可以加班解决，能不加班最好不加班（5）受到资金的限制，只能使用现有材料不能再购进,【解】设甲、乙、丙产品的产量分别为x1、x2、x3。如果按线性规划建模思路，最优解实质是求下列一组不等式的解,4.1目标规划的数学模型Mathematical Model of GP,2023/8/27,通过计算不等式无解，即使设备加班10小时仍然无解在实际生产过程中生产方案总是存在的，无解只能说明在现有资源条件下，不可能完全满足所有经营目标,这种情形是按事先制定的目标顺序逐项检查，尽可能使得结果达到预定目标，即使不能达到目标也使得离目标的差距最小，这就是目标规划的求解思路，对应的解称为满意解下面建立例4.1的目标规划数学模型,4.1目标规划的数学模型Mathematical Model of GP,2023/8/27,设d为未达到目标值的差值，称为负偏差变量（negative deviation variable）d+为超过目标值的差值，称为正偏差变量（positive deviation variable）,d0、d0,设d1未达到利润目标的差值,d1+为超过目标的差值,当利润小于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,4.1目标规划的数学模型Mathematical Model of GP,2023/8/27,（2）设 分别为未达到和超过产品比例要求的偏差变量,则产量比例尽 量不超过1.5的数学表达式为：,（3）设d3、d分别为品丙的产量未达到和超过30件的偏差变量，则产量丙的产量尽可能达到30件的数学表达式为：,利润不少于3200理解为达到或超过3200，即使不能达到也要尽可能接近3200,可以表达成目标函数d1取最小值，则有,4.1目标规划的数学模型Mathematical Model of GP,2023/8/27,（4）设d4、d4+为设备A的使用时间偏差变量,d5、d5+为设备B的使用时间偏差变量，最好不加班的含义是 d4+和d5+同时取最小值，等价 于d4+d5+取最小值，则设备的目标函数和约束为：,（5）材料不能购进表示不允许有正偏差，约束条件为小于等于约束,由于目标是有序的并且四个目标函数非负，因此目标函数可以表达成一个函数：,4.1目标规划的数学模型Mathematical Model of GP,2023/8/27,式中：Pj（j=1,2,3,4）称为目标的优先因子，第一目标优于第二目标，第二目标优于第三目标等等，其含义是按P1、P2、的次序分别求后面函数的最小值.则问题的目标规划数学模型为：,4.1目标规划的数学模型Mathematical Model of GP,2023/8/27,满意解：,约束分析：,4.1目标规划的数学模型Mathematical Model of GP,2023/8/27,（1）目标规划数学模型的形式有：线性模型、非线性模型、整数模型、交互作用模型等（2）一个目标中的两个偏差变量di-、di+至少一个等于零，偏差变量向量的叉积等于零：dd=0,（3）一般目标规划是将多个目标函数写成一个由偏差变量构成的函数求最小值，按多个目标的重要性，确定优先等级，顺序求最小值,（4）按决策者的意愿，事先给定所要达到的目标值当期望结果不超过目标值时，目标函数求正偏差变量最小;当期望结果不低于目标值时，目标函数求负偏差变量最小;当期望结果恰好等于目标值时，目标函数求正负偏差变量之和最小,4.1.2 数学模型,4.1目标规划的数学模型Mathematical Model of GP,2023/8/27,（5）由目标构成的约束称为目标约束，目标约束具有更大的弹性，允许结果与所制定的目标值存在正或负的偏差，如例4.1中的5个等式约束；如果决策者要求结果一定不能有正或负的偏差，这种约束称为系统约束，如例4.1的材料约束；,（6）目标的排序问题。多个目标之间有相互冲突时，决策者首先必须对目标排序。排序的方法有两两比较法、专家评分等方法，构造各目标的权系数，依据权系数的大小确定目标顺序；,（7）合理的确定目标数。目标规划的目标函数中包含了多个目标，决策者对于具有相同重要性的目标可以合并为一个目标，如果同一目标中还想分出先后次序，可以赋予不同的权系数，按系数大小再排序。例如，在例4.1中要求设备B的加班时间不超过设备A的时间，目标函数可以表达为,表示在中先求 最小再求 最小。,4.1目标规划的数学模型Mathematical Model of GP,2023/8/27,（8）多目标决策问题多目标决策研究的范围比较广泛，在决策中，可能同时要求多个目标达到最优例如，企业在对多个项目投资时期望收益率尽可能最大，投资风险尽可能最小，属于多目标决策问题，本章的目标规划尽管包含有多个目标，但还是按单个目标求偏差变量的最小值，目标函数中不含有决策变量，目标规划只是多目标决策的一种特殊情形本章不讨论多目标规划的求解方法，只给出WinQSB软件求解线性多目标规划的操作步骤，参看例4.3和4.9,4.1目标规划的数学模型Mathematical Model of GP,2023/8/27,（9）目标规划的一般模型设xj（j=1,2,n）为决策变量,4.1目标规划的数学模型Mathematical Model of GP,式中p k 为第k 级优先因子,k=1、2、K；wkl-、wkl+，为分别赋予第l个目标约束的正负偏差变量的权系数；gl为目标的预期目标值，l=1,L(4.1b)为系统约束,（4.1c）为目标约束,2023/8/27,【例4.2】某企业集团计划用1000万元对下属5个企业进行技术改造，各企业单位的投资额已知，考虑2种市场需求变化、现有竞争对手、替代品的威胁等影响收益的4个因素，技术改造完成后预测单位投资收益率(（单位投资获得利润/单位投资额）100)如表42所示,4.1目标规划的数学模型Mathematical Model of GP,集团制定的目标是：（1）希望完成总投资额又不超过预算；（2）总期望收益率达到总投资的30%；（3）投资风险尽可能最小；（4）保证企业5的投资额占20%左右集团应如何作出投资决策,2023/8/27,表42,4.1目标规划的数学模型Mathematical Model of GP,2023/8/27,【解】设xj（j=1,2,5）为集团对第 j 个企业投资的单位数,（1）总投资约束：,4.1目标规划的数学模型Mathematical Model of GP,（2）期望利润率约束：,整理得,2023/8/27,4.1目标规划的数学模型Mathematical Model of GP,(3）投资风险约束投资风险值的大小一般用期望收益率的方差表示，但方差是x的非线性函数这里用离差（rijE(rj)）近似表示风险值，例如，集团投资5个企业后对于市场需求变化第一情形的风险是：则4种因素风险最小的目标函数为：，约束条件为,2023/8/27,4.1目标规划的数学模型Mathematical Model of GP,根据目标重要性依次写出目标函数，整理后得到投资决策的目标规划数学模型：,2023/8/27,【例4.3】车间计划生产I、II 两种产品，每种产品均需经过A、B两道工序加工工艺资料如表43所示,（1）车间如何安排生产计划，使产值和利润都尽可能高（2）如果认为利润比产值重要，怎样决策,表43,4.1目标规划的数学模型Mathematical Model of GP,2023/8/27,【解】设x1、x2分别为产品甲和产品乙的日产量，得到线性多目标规划模型：,4.1目标规划的数学模型Mathematical Model of GP,2023/8/27,（1）将模型化为目标规划问题首先，通过分别求产值最大和利润最大的线性规划最优解产值最大的最优解：X(1)（20，40），Z13800利润最大的最优解：X(2)（30，30），Z2540目标确定为产值和利润尽可能达到3800和540，得到目标规划数学模型：,4.1目标规划的数学模型Mathematical Model of GP,2023/8/27,4.1目标规划的数学模型Mathematical Model of GP,等价于,（2）给 d2-赋予一个比d1-的系数大的权系数,如，约束条件不变.权系数的大小依据重要程度给定，或者根据同一优先级的偏差变量的关系给定，例如，当利润d2-减少一个单位时，产值d1-减少3个单位，则赋予d2-权系数3，则目标函数为,2023/8/27,本节介绍了如何建立目标规划的数学模型及有关概念,1.目标规划由哪些要素构成，与线性规划有哪些不同之处2.偏差变量的含义及其作用3.目标函数的表达方法4.优先级别的含义,4.1目标规划的数学模型Mathematical Model of GP,作业:教材P90 1，2，4,下一节：目标规划的图解法,4.2 目标规划的图解法The graphical method of GP,2023/8/27,4.2目标规划的图解法The graphical method of GP,当目标规划模型中只含两个决策变量（不包含偏差变量）时，可以用图解法求出满意解,【例4.4】企业计划生产I、II 两种产品，这些产品需要使用两种材料，要在两种不同设备上加工工艺资料如表44所示,表44,2023/8/27,【解】设x1、x2分别为产品甲和产品乙的产量，目标规划数学模型为：,企业怎样安排生产计划，尽可能满足下列目标：(1)力求使利润指标不低于80元(2)考虑到市场需求,、II两种产品的生产量需保持1:1的比例(3)设备A既要求充分利用，又尽可能不加班(4)设备B必要时可以加班，但加班时间尽可能少(5)材料不能超用。,4.2目标规划的图解法The graphical method of GP,(2),(1),(3),(4),x2,x1,(6),(5),o,4,6,4,6,2,2,图41,A,B,C,满意解C(3,3),满意解X(3,3),(3),x1,x2,20,40,60,80,100,20,40,60,80,100,(2),(1),(4),图53,B,C,满意解是线段 上任意点，端点的解是 B(100/3，80/3)，C(60，0)决策者根据实际情形进行二次选择,A,(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,(3),x1,x2,20,40,60,80,100,20,40,60,80,100,(2),(1),(4),图53,满意解是点 D，X=(80/9，560/9),A(20,40),D(80/9,560/9),注：线段DA是第二目标函数的组合，点A对应的偏差：d2-=100,d3=0点D对应的偏差：d2-=0,2d3=2200/9=400/9,2023/8/27,本节介绍了目标规划的图解法,1.画出系统约束和目标约束直线2.标明偏差变量大于零的变量X的取值区域3.按优先次序分别求各目标的最小值,作业:教材P91 T3,下一节：目标规划的单纯形法,4.2目标规划的图解法The graphical method of GP,4.3 单纯形法Simplex Method,2023/8/27,单纯形法求解目标规划可参照第一章的步骤，只是目标规划的检验要按优先级顺序逐级进行，不同的是：（1）首先使得检验数中P1的系数非负，再使得P2的系数非负，依次进行；（2）当P1、P2、Pk对应的系数全部非负时得到满意解；（3）如果P1，Pi行系数非负，而Pi+1行存在负数，并且负数所在列上面P1，Pi行中存在正数时，得到满意解，计算结束,4.3 单纯形法Simplex Method,2023/8/27,【例4.6】用单纯形法求解下述目标规划问题,【解】以d1、d2、d3为基变量，求出检验数，将检验数中优先因子分离出来，每一优先级做一行，列出初始单纯形表4-5,4.3 单纯形法Simplex Method,2023/8/27,表45,4.3 单纯形法Simplex Method,2023/8/27,表45中，P1行中(2)最小，则x2进基，求最小比值易知d1出基，将第二列主元素化为1，其余元素化为零，得到表4-6,表46,4.3 单纯形法Simplex Method,2023/8/27,表4-6中P1行全部检验数非负，表明第一目标已经得到优化P2行存在负数，x1的检验数为P20，选x1进基（也可以选d1+进基），则d3出基，迭代得到表4-7,4.3 单纯形法Simplex Method,表4-7,2023/8/27,在表4-7中，P1行的系数全部非负，P2行存在负数，d1+的检验数2/3P20，选d1+进基，则x1出基，迭代得到表4-8应当注意，表4-7中不能选d2+进基，检验数P12/3P2应理解为“大于零”，P1、P2是优先级别的比较，而不是“数”的比较例如，P13P2+5P3理解为小于零，2P24P4理解为大于零等等,表48,4.3 单纯形法Simplex Method,2023/8/27,表4-8中P2行的（2）小于零，但（2）列上面P1行存在正数1，检验数P12P20,所有检验数非负，得到满意解X（0，40）,【例4.7】(1)用单纯形法求解例4.5（2）当目标函数变为,【解】（1）初始单纯形表见表4-9，最终单纯形表见表4-12满意解X(100/3，80/3)T，对应于图4-6点B不难看出有多重解，将d4进基x2出基，得到另一满意解X(60，0)T，对应于图4-6点C，见表4-13,4.3 单纯形法Simplex Method,求满意解,2023/8/27,表4-9,4.3 单纯形法Simplex Method,2023/8/27,表4-10,4.3 单纯形法Simplex Method,2023/8/27,表411,4.3 单纯形法Simplex Method,2023/8/27,表4-12,4.3 单纯形法Simplex Method,2023/8/27,表413,4.3 单纯形法Simplex Method,2023/8/27,（2）如果将目标函数 改写成,以表4-12为基础，计算过程见表4-144-16,表4-14,4.3 单纯形法Simplex Method,2023/8/27,表4-15,4.3 单纯形法Simplex Method,2023/8/27,表4-16,满意解X(20，40)T，对应于图4-6中点A(20,40),Z120，然而该满意解是错误的，正确的算法见表4-17。,4.3 单纯形法Simplex Method,求解，单纯形法计算如表4-17所示,在（2）中仍然按,2023/8/27,表4-17,转下表,4.3 单纯形法Simplex Method,最终表：,2023/8/27,4.3 单纯形法Simplex Method,满意解X(80/9，560/9)T，d3+200/9而d20，d4+580/9，Z108.88，目标函数值比表4-16的结果小。图解法时如果按权系数大小顺序求最小值就很容易得到表4-16所示错误的解。,例4.7（2）是在原问题中作了部分变动后再求解，等价于第二章的灵敏度分析，求解原理基本相同,由表4-17的计算可以看出，同一级目标中有不同权系数时，不是按大小顺序求最小，而是求加权最小。,2023/8/27,The End of Chapter 4,目标规划的单纯形法与线性规划比较主要有两点不同。第一，目标规划是按优先次序顺序求解，逐个满足最优（检验数大于等于零）；第二，不一定所有检验数都能满足大于等于零，如果某个检验数小于零，所在列存在检验数大于零时，则认为得到满意解。计算方法和基本原理与线性规划类似。,作业：P91 T 3、5,4.3 单纯形法Simplex Method,2023/8/27,第4章 部分习题答案,2023/8/27,习题4.3(1),(3),x1,10,20,30,40,50,10,20,30,40,50,(2),(1),x2,习题答案,A(50/3,20/3),B(30,0),满意解在线段 上,2023/8/27,习题4.3(2),(3),x1,1,2,1,2,(2),(1),x2,习题答案,满意解X=(2,0),2023/8/27,习题4.3(3),(3),x1,10,20,30,40,50,10,20,30,40,50,(2),(1),x2,习题答案,满意解：X=(50,10),60,(4),(50,10),60,2023/8/27,习题4.3(4),(3),x1,1,2,3,4,5,1,2,3,4,(2),(1),x2,习题答案,满意解：X=(0,3),6,(4),(0,3),2023/8/27,习题4.5(1),(3),x1,1,2,3,4,5,1,2,3,4,(2),(1),x2,习题答案,满意解：X(13/2,5/4),6,(4),9,(13/2,5/4),2023/8/27,习题4.5(2)(a),(3),x1,1,2,3,4,5,1,2,3,4,(2),(1),x2,习题答案,满意解：X(5,1/2),6,(4),9,(5,1/2),2023/8/27,习题4.5(2)(b),(3),x1,1,2,3,4,5,1,2,3,4,(2),(1),x2,习题答案,满意解在线段 上,6,(4),9,A,B,2023/8/27,(3),x1,1,2,3,4,5,1,2,3,4,(2),(1),x2,习题答案,满意解在B点（13/2，5/4）,6,(4),9,A,B,习题4.5(2)(b),2023/8/27,(3),x1,1,2,3,4,5,1,2,3,4,(2),(1),x2,习题答案,满意解在A点（5，2）,6,(4),9,A,B,习题4.5(2)(b),