《管理运筹学目标规划课件.ppt》由会员分享,可在线阅读,更多相关《管理运筹学目标规划课件.ppt(53页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、管管 理理 运运 筹筹 学学第九章第九章 目标规划目标规划1 1 目标规划问题举例目标规划问题举例2 2 目标规划的图解法目标规划的图解法3 3 复杂情况下的复杂情况下的目标规划目标规划4 4 加权目标规划加权目标规划 5 5 目标规划的单纯型法目标规划的单纯型法 1管管 理理 运运 筹筹 学学11目标规划问题举例目标规划问题举例 线性规划模型的特征是在满足一组约束条件下,寻求一个目线性规划模型的特征是在满足一组约束条件下,寻求一个目标的最优解(最大值或最小值)。标的最优解(最大值或最小值)。而在现实生活中最优只是相对的,或者说没有绝对意义下的最而在现实生活中最优只是相对的,或者说没有绝对意义
2、下的最优,只有相对意义下的满意。优,只有相对意义下的满意。1978年诺贝尔经济学奖获得者年诺贝尔经济学奖获得者.西蒙西蒙(H.A.Simon-美国卡内基美国卡内基-梅隆大学梅隆大学,1916-)教授提出教授提出“满意行为模型要比最大化行为模型满意行为模型要比最大化行为模型丰富得多丰富得多”,否定了企业的决策者是,否定了企业的决策者是“经济人经济人”概念和概念和“最大最大化化”行为准则,提出了行为准则,提出了“管理人管理人”的概念和的概念和“令人满意令人满意”的行的行为准则,对现代企业管理的决策科学进行了开创性的研究为准则,对现代企业管理的决策科学进行了开创性的研究 2管管 理理 运运 筹筹 学
3、学11目标规划问题举例目标规划问题举例例例1企业生产企业生产不不同同企企业业的的生生产产目目标标是是不不同同的的。多多数数企企业业追追求求最最大大的的经经济济效效益益。但但随随着着环环境境问问题题的的日日益益突突出出,可可持持续续发发展展已已经经成成为为全全社社会会所所必必须须考考虑虑的的问问题题。因因此此,企企业业生生产产就就不不能能再再如如以以往往那那样样只只考考虑虑企企业业利利润润,必必须须承承担担起起社社会会责责任任,要要考考虑虑环环境境污污染染、社社会会效效益益、公公众众形形象等多个方面。兼顾好这几者关系,企业才可能保持长期的发展。象等多个方面。兼顾好这几者关系,企业才可能保持长期的
4、发展。例例2商务活动商务活动企企业业在在进进行行盈盈亏亏平平衡衡预预算算时时,不不能能只只集集中中在在一一种种产产品品上上,因因为为某某一一种种产产品品的的投投入入和和产产出出仅仅仅仅是是企企业业所所有有投投入入和和产产出出的的一一部部分分。因因此此,需需要要用用多多产产品品的的盈盈亏亏分分析析来来解解决决具具有有多多个个盈盈亏亏平平衡衡点点的的决决策策问题(多产品的盈亏平衡点往往是不一致的)。问题(多产品的盈亏平衡点往往是不一致的)。3管管 理理 运运 筹筹 学学11目标规划问题举例目标规划问题举例例例3投资投资企企业业投投资资时时不不仅仅仅仅要要考考虑虑收收益益率率,还还要要考考虑虑风风险
5、险。一一般般地地,风风险险大大的的投投资资其其收收益益率率更更高高。因因此此,企企业业管管理理者者只只有有在在对对收收益益率率和和风风险承受水平有明确的期望值时,才能得到满意的决策。险承受水平有明确的期望值时,才能得到满意的决策。例例4裁员裁员同同样样的的,企企业业裁裁员员时时要要考考虑虑很很多多可可能能彼彼此此矛矛盾盾的的因因素素。裁裁员员的的首首要要目目的的是是压压缩缩人人员员开开支支,但但在在人人人人自自危危的的同同时时员员工工的的忠忠诚诚度度就就很很难难保保证证,此此外外,员员工工的的心心理理压压力力、工工作作压压力力等等都都会会增增加加,可可能能产产生负面影响。生负面影响。例例5营销
6、营销营销方案的策划和执行存在多个目标。既希望能达到立竿见影的营销方案的策划和执行存在多个目标。既希望能达到立竿见影的效果,又希望营销的成本控制在某一个范围内。此外,营销活动效果,又希望营销的成本控制在某一个范围内。此外,营销活动的深入程度也决定了营销效果的好坏和持续时间。的深入程度也决定了营销效果的好坏和持续时间。4管管 理理 运运 筹筹 学学11目标规划问题举例目标规划问题举例【例例1.】考虑例考虑例1.1资源消耗如表资源消耗如表9-1所示。所示。x1、x2、x3分分别为甲、乙、丙的产量。别为甲、乙、丙的产量。使企业在计划期内总利润最大的线性规划模型为:使企业在计划期内总利润最大的线性规划模
7、型为:产品产品 资源资源甲甲乙乙丙丙现有资源现有资源设备设备A312200设备设备B224200材料材料C451360材料材料D235300利润(元利润(元/件)件)403050表表9-11.1 引例引例5管管 理理 运运 筹筹 学学11目标规划问题举例目标规划问题举例最优解最优解X(50,30,10),),Z34006管管 理理 运运 筹筹 学学11目标规划问题举例目标规划问题举例 现在决策者根据企业的实际情况和市场需求,需要重新制现在决策者根据企业的实际情况和市场需求,需要重新制定经营目标,其目标的优先顺序是:定经营目标,其目标的优先顺序是:(1)利润不少于)利润不少于3200元元(2)产
8、品甲与产品乙的产量比例尽量不超过)产品甲与产品乙的产量比例尽量不超过1.5(3)提高产品丙的产量使之达到)提高产品丙的产量使之达到30件件(4)设备加工能力不足可以加班解决,能不加班最好不加班)设备加工能力不足可以加班解决,能不加班最好不加班(5)受到资金的限制,只能使用现有材料不能再购进)受到资金的限制,只能使用现有材料不能再购进【解解】设甲、乙、丙产品的产量分别为设甲、乙、丙产品的产量分别为x1、x2、x3。如果按线。如果按线性规划建模思路,最优解实质是求下列一组不等式的解性规划建模思路,最优解实质是求下列一组不等式的解7管管 理理 运运 筹筹 学学11目标规划问题举例目标规划问题举例通过
9、计算不等式无解,即使设备加班通过计算不等式无解,即使设备加班10小时仍然无解在实小时仍然无解在实际生产过程中生产方案总是存在的,无解只能说明在现有资际生产过程中生产方案总是存在的,无解只能说明在现有资源条件下,不可能完全满足所有经营目标源条件下,不可能完全满足所有经营目标这种情形是按事先制定的目标顺序逐项检查,尽可能使得结果这种情形是按事先制定的目标顺序逐项检查,尽可能使得结果达到预定目标,即使不能达到目标也使得离目标的差距最小,达到预定目标,即使不能达到目标也使得离目标的差距最小,这就是目标规划的求解思路,对应的解称为满意解下面建立这就是目标规划的求解思路,对应的解称为满意解下面建立例例1.
10、1的目标规划数学模型的目标规划数学模型 8管管 理理 运运 筹筹 学学11目标规划问题举例目标规划问题举例设设d为未达到目标值的差值,称为负偏差变量(为未达到目标值的差值,称为负偏差变量(negative deviation variable)d+为超过目标值的差值,称为正偏差变量为超过目标值的差值,称为正偏差变量(positive deviation variable),d0、d0设设d1-未达到利润目标的差值未达到利润目标的差值,d1+为超过目标的差值为超过目标的差值当利润小于当利润小于3200时时,d1且且d10,有有40 x1+30 x2+50 x3+d1=3200成立成立当利润大于当
11、利润大于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+=32009管管 理理 运运 筹筹 学学11目标规划问题举例目标规划问题举例(2)设)设 分别为未达到和超过产品比例要求的偏差变分别为未达到和超过产品比例要求的偏差变量量,则产量比例尽则产量比例尽 量
12、不超过量不超过1.5的数学表达式为的数学表达式为:(3)设)设d3、d分别为品丙的产量未达到和超过分别为品丙的产量未达到和超过30件的偏差件的偏差变量,则产量丙的产量尽可能达到变量,则产量丙的产量尽可能达到30件的数学表达式为:件的数学表达式为:利润不少于利润不少于3200理解为达到或超过理解为达到或超过3200,即使不能达到也要尽,即使不能达到也要尽可能接近可能接近3200,可以表达成目标函数可以表达成目标函数d1取最小值,则有取最小值,则有10管管 理理 运运 筹筹 学学11目标规划问题举例目标规划问题举例(4)设设d4、d4+为设备为设备A的使用时间偏差变量的使用时间偏差变量,d5、d5
13、+为设备为设备B的使用时间偏差变量,最好不加班的含义是的使用时间偏差变量,最好不加班的含义是 d4+和和d5+同时取最同时取最小值,等价小值,等价 于于d4+d5+取最小值,则设备的目标函数和约束为:取最小值,则设备的目标函数和约束为:(5)材料不能购进表示不允许有正偏差,约束条件为小于等于)材料不能购进表示不允许有正偏差,约束条件为小于等于约束约束由于目标是有序的并且四个目标函数非负,因此目标函数可以由于目标是有序的并且四个目标函数非负,因此目标函数可以表达成一个函数:表达成一个函数:11管管 理理 运运 筹筹 学学11目标规划问题举例目标规划问题举例式中:式中:Pj(j=1,2,3,4)称
14、为目标的优先因子,第一目标优于第二称为目标的优先因子,第一目标优于第二目标,第二目标优于第三目标等等,其含义是按目标,第二目标优于第三目标等等,其含义是按P1、P2、的次的次序分别求后面函数的最小值序分别求后面函数的最小值.则问题的目标规划数学模型为:则问题的目标规划数学模型为:12管管 理理 运运 筹筹 学学22目标规划的图解法目标规划的图解法 例例6一一位位投投资资商商有有一一笔笔资资金金准准备备购购买买股股票票。资资金金总总额额为为90000元元,目目前前可可选选的的股股票票有有A和和B两两种种(可可以以同同时时投投资资于于两两种种股股票票)。其其价价格格以以及及年年收收益率和风险系数如
15、表益率和风险系数如表1:从从上上表表可可知知,A股股票票的的收收益益率率为为(320)10010015,股股票票B的的收收益益率率为为4501001008,A的的收收益益率率比比B大大,但但同同时时A的的风风险险也也比比B大。这也符合高风险高收益的规律。大。这也符合高风险高收益的规律。试试求求一一种种投投资资方方案案,使使得得一一年年的的总总投投资资风风险险不不高高于于700,且且投投资资收收益不低于益不低于10000元。用来全部投资一个股票两个目标不能同时达到元。用来全部投资一个股票两个目标不能同时达到.股票价格(元)年收益(元)年风险系数A2030.5B5040.213管管 理理 运运 筹
16、筹 学学22目标规划的图解法目标规划的图解法 显显然然,此此问问题题属属于于目目标标规规划划问问题题。它它有有两两个个目目标标变变量量:一一是是限限制制风风险险,一一是是确确保保收收益益。在在求求解解之之前前,应应首首先先考考虑虑两两个个目目标标的的优先权。优先权。假假设设第第一一个个目目标标(即即限限制制风风险险)的的优优先先权权比比第第二二个个目目标标(确确保保收收益益)大大,这这意意味味着着求求解解过过程程中中必必须须首首先先满满足足第第一一个个目目标标,然然后在此基础上再尽量满足第二个目标。后在此基础上再尽量满足第二个目标。建立模型:建立模型:设设x x1 1、x x2 2分别表示投资
17、商所购买的分别表示投资商所购买的A A股票和股票和B B股票的数量。股票的数量。首先考虑资金总额的约束:总投资额不能高于首先考虑资金总额的约束:总投资额不能高于9000090000元。即元。即 20 x20 x1 150 x50 x2 29000090000。14管管 理理 运运 筹筹 学学22目标规划的图解法目标规划的图解法一、约束条件一、约束条件 再来考虑风险约束:总风险不能超过再来考虑风险约束:总风险不能超过700700。投资的总风险为。投资的总风险为0.5x0.5x1 10.2x0.2x2 2。引入两个变量引入两个变量d d1 1+和和d d1 1-,建立等式如下:建立等式如下:0.5
18、x0.5x1 1+0.2x+0.2x2 2=700+d=700+d1 1+-d-d1 1-其中,其中,d d1 1+表示总风险高于表示总风险高于700700的部分,的部分,d d1 1-表示总风险少于表示总风险少于700700的的部分,部分,d d1 1+00。目标规划中把目标规划中把d d1 1+、d d1 1-这样的变量称为偏差变量。偏差变量的作这样的变量称为偏差变量。偏差变量的作用是允许约束条件不被精确满足。用是允许约束条件不被精确满足。15管管 理理 运运 筹筹 学学22目标规划的图解法目标规划的图解法 把等式转换,可得到 0.5x1+0.2x2-d1+d1-=700。再来考虑年收入:
19、年收入=3x1+4x2 引入变量d2+和d2-,分别表示年收入超过与低于10000的数量。于是,第2个目标可以表示为 3x1+4x2-d2+d2-=10000。16管管 理理 运运 筹筹 学学22目标规划的图解法目标规划的图解法二、有优先权的目标函数二、有优先权的目标函数 本本问问题题中中第第一一个个目目标标的的优优先先权权比比第第二二个个目目标标大大。即即最最重重要要的的目目标标是是满满足足风风险险不不超超过过700700。分分配配给给第第一一个个目目标标较较高高的的优优先先权权P P1 1,分配给第二个目标较低的优先权分配给第二个目标较低的优先权P P2 2。针针对对每每一一个个优优先先权
20、权,应应当当建建立立一一个个单单一一目目标标的的线线性性规规划划模模型型。首首先先建建立立具具有有最最高高优优先先权权的的目目标标的的线线性性规规划划模模型型,求求解解;然然后后再再按按照照优优先先权权逐逐渐渐降降低低的的顺顺序序分分别别建建立立单单一一目目标标的的线线性性规规划划模模型型,方方法法是是在在原原来来模模型型的的基基础础上上修修改改目目标标函函数数,并并把把原原来来模模型型求求解解所所得得的的目目标标最最优优值值作作为为一一个个新新的的约约束束条条件件加加入入到到当当前前模模型型中中,并并求求解。解。17管管 理理 运运 筹筹 学学22目标规划的数学模型目标规划的数学模型(1)目
21、标规划数学模型的形式有:线性模型、非线性模型、)目标规划数学模型的形式有:线性模型、非线性模型、整数模型、交互作用模型等整数模型、交互作用模型等(2)一个目标中的两个偏差变量)一个目标中的两个偏差变量di-、di+至少一个等于零,偏至少一个等于零,偏差变量向量的叉积等于零:差变量向量的叉积等于零:dd=0 (3)一般目标规划是将多个目标函数写成一个由偏差变量构)一般目标规划是将多个目标函数写成一个由偏差变量构成的函数求最小值,按多个目标的重要性,确定优先等级,顺成的函数求最小值,按多个目标的重要性,确定优先等级,顺序求最小值序求最小值 (4)按决策者的意愿,事先给定所要达到的目标值)按决策者的
22、意愿,事先给定所要达到的目标值当期望结果不超过目标值时,目标函数求正偏差变量最小当期望结果不超过目标值时,目标函数求正偏差变量最小;当期望结果不低于目标值时,目标函数求负偏差变量最小当期望结果不低于目标值时,目标函数求负偏差变量最小;当期望结果恰好等于目标值时,目标函数求正负偏差变量之和最当期望结果恰好等于目标值时,目标函数求正负偏差变量之和最小小9.2 数学模型数学模型18管管 理理 运运 筹筹 学学22目标规划的数学模型目标规划的数学模型(5)由目标构成的约束称为目标约束,目标约束具有更大的弹)由目标构成的约束称为目标约束,目标约束具有更大的弹性,允许结果与所制定的目标值存在正或负的偏差,
23、如例性,允许结果与所制定的目标值存在正或负的偏差,如例1.1中的中的5个等式约束;如果决策者要求结果一定不能有正或负的偏差,个等式约束;如果决策者要求结果一定不能有正或负的偏差,这种约束称为系统约束,如例这种约束称为系统约束,如例1.1的材料约束;的材料约束;(6)目标的排序问题。多个目标之间有相互冲突时,决策者首)目标的排序问题。多个目标之间有相互冲突时,决策者首先必须对目标排序。排序的方法有两两比较法、专家评分等方先必须对目标排序。排序的方法有两两比较法、专家评分等方法,构造各目标的权系数,依据权系数的大小确定目标顺序;法,构造各目标的权系数,依据权系数的大小确定目标顺序;(7)合理的确定
24、目标数。目标规划的目标函数中包含了多个目)合理的确定目标数。目标规划的目标函数中包含了多个目标,决策者对于具有相同重要性的目标可以合并为一个目标,标,决策者对于具有相同重要性的目标可以合并为一个目标,如果同一目标中还想分出先后次序,可以赋予不同的权系数,如果同一目标中还想分出先后次序,可以赋予不同的权系数,按系数大小再排序。例如,在例按系数大小再排序。例如,在例1.1中要求设备中要求设备B的加班时间不的加班时间不超过设备超过设备A的时间,目标函数可以表达为的时间,目标函数可以表达为 ,表示在表示在中先求中先求 最小再求最小再求 最小。最小。19管管 理理 运运 筹筹 学学22目标规划的数学模型
25、目标规划的数学模型(8)目标规划的一般模型设)目标规划的一般模型设xj(j=1,2,n)为决策变量为决策变量 式中式中p k 为第为第k 级优先因子级优先因子,k=1、2、K;wkl-、wkl+,为为分别赋予第分别赋予第l个目标约束的正负偏差变量的权系数;个目标约束的正负偏差变量的权系数;gl为目标的为目标的预期目标值,预期目标值,l=1,L(4.1b)为系统约束为系统约束,(4.1c)为目标约为目标约束束20管管 理理 运运 筹筹 学学22目标规划的数学模型目标规划的数学模型【例例1.2】某企业集团计划用某企业集团计划用1000万元对下属万元对下属5个企业进行技术个企业进行技术改造,各企业单
26、位的投资额已知,考虑改造,各企业单位的投资额已知,考虑2种市场需求变化、现有种市场需求变化、现有竞争对手、替代品的威胁等影响收益的竞争对手、替代品的威胁等影响收益的4个因素,技术改造完成个因素,技术改造完成后预测单位投资收益率后预测单位投资收益率((单位投资获得利润(单位投资获得利润/单位投资额)单位投资额)100)如表如表12所示所示集团制定的目标是:集团制定的目标是:(1)希望完成总投资额又不超过预算;)希望完成总投资额又不超过预算;(2)总期望收益率达到总投资的)总期望收益率达到总投资的30%;(3)投资风险尽可能最小;)投资风险尽可能最小;(4)保证企业)保证企业5的投资额占的投资额占
27、20%左右左右集团应如何作出投资决策集团应如何作出投资决策21管管 理理 运运 筹筹 学学22目标规划的数学模型目标规划的数学模型企业企业1企业企业2企业企业3企业企业4企业企业5单位投资额单位投资额(万元万元)1210151320单位投单位投资收益资收益率预测率预测rij市场需求市场需求14.3255.845.26.56市场需求市场需求23.523.045.084.26.24现有竞争对手现有竞争对手3.162.23.563.284.08替代品的威胁替代品的威胁2.243.122.62.23.24期望期望(平均平均)收益率收益率3.313.344.273.725.03表表1222管管 理理 运
28、运 筹筹 学学22目标规划的数学模型目标规划的数学模型【解解】设设xj(j=1,2,5)为集团对第为集团对第 j 个企业投资的单位数个企业投资的单位数(1)总投资约束:)总投资约束:(2)期望利润率约束:)期望利润率约束:整理得整理得23管管 理理 运运 筹筹 学学22目标规划的数学模型目标规划的数学模型(4)企业)企业5占占20%的投资的目标函数为的投资的目标函数为 ,约束条件约束条件即即(3)投)投资风险约资风险约束投束投资风险值资风险值的大小一般用期望收益率的方的大小一般用期望收益率的方差表示,但方差是差表示,但方差是x的非的非线线性函数性函数这这里用离差(里用离差(rijE(rj))近
29、近似表示似表示风险值风险值,例如,集,例如,集团团投投资资5个企个企业业后后对对于市于市场场需求需求变变化第化第一情形的一情形的风险风险是:是:则则4种因素风险最小的目标函数为:种因素风险最小的目标函数为:,约束条件为,约束条件为24管管 理理 运运 筹筹 学学22目标规划的数学模型目标规划的数学模型根据目标重要性依次写出目标函数,整理后得到投资决策的根据目标重要性依次写出目标函数,整理后得到投资决策的目标规划数学模型:目标规划数学模型:25管管 理理 运运 筹筹 学学22目标规划的数学模型目标规划的数学模型【例例1.3】车间计划生产车间计划生产I、II 两种产品,每种产品均需经过两种产品,每
30、种产品均需经过A、B两道工序加工工艺资料如表两道工序加工工艺资料如表43所示所示 产品产品工序工序产品甲产品甲产品乙产品乙每天加工能力每天加工能力(小时小时)A22120B12100C2.20.890产品售价产品售价(元元/件件)5070产品利润产品利润(元元/件件)108(1)车间如何安排生产计划,使产值和利润都尽可能高)车间如何安排生产计划,使产值和利润都尽可能高(2)如果认为利润比产值重要,怎样决策)如果认为利润比产值重要,怎样决策表表1326管管 理理 运运 筹筹 学学22目标规划的数学模型目标规划的数学模型【解解】设设x1、x2分别为产品甲和产品乙的日产量,得到线性多分别为产品甲和产
31、品乙的日产量,得到线性多目标规划模型:目标规划模型:27管管 理理 运运 筹筹 学学22目标规划的数学模型目标规划的数学模型(1)将模型化为目标规划问题首先,通过分别求产值最大)将模型化为目标规划问题首先,通过分别求产值最大和利润最大的线性规划最优解和利润最大的线性规划最优解产值最大的最优解:产值最大的最优解:X(1)(20,40),),Z13800利润最大的最优解:利润最大的最优解:X(2)(30,30),),Z2540目标确定为产值和利润尽可能达到目标确定为产值和利润尽可能达到3800和和540,得到目标规划,得到目标规划数学模型:数学模型:28管管 理理 运运 筹筹 学学22目标规划的图
32、解法目标规划的图解法三、图解法三、图解法1 1针对优先权最高的目标建立线性规划针对优先权最高的目标建立线性规划建立线性规划模型如下:建立线性规划模型如下:Min dMin d1 1+s.t.s.t.20 x 20 x1 150 x50 x2 29000090000 0.5x 0.5x1 1+0.2x+0.2x2 2-d-d1 1+d+d1 1-=700=700 3x 3x1 1+4x+4x2 2-d-d2 2+d+d2 2-=10000=10000 x x1 1,x,x2 2,d,d1 1+,d,d1 1-0029管管 理理 运运 筹筹 学学22目标规划的图解法目标规划的图解法图2 图解法步骤
33、2010002000300040005000200030004000 x1x220 x150 x29000010000.5x1+0.2x2=70030管管 理理 运运 筹筹 学学22目标规划的图解法目标规划的图解法2 2针对优先权次高的目标建立线性规划针对优先权次高的目标建立线性规划优先权次高(优先权次高(P P2 2)的目标是总收益超过的目标是总收益超过1000010000。建立线性规划如下:建立线性规划如下:Min dMin d2 2-s.ts.t.20 x 20 x1 150 x50 x2 29000090000 0.5x 0.5x1 1+0.2x+0.2x2 2-d-d1 1+d+d1
34、 1-=700=700 3x 3x1 1+4x+4x2 2-d-d2 2+d+d2 2-=10000=10000 d d1 1+0 0 x x1 1,x,x2 2,d,d1 1+,d,d1 1-,d,d2 2+,d,d2 2-0031管管 理理 运运 筹筹 学学22目标规划的图解法目标规划的图解法3x1+4x2=10000图3 图解法步骤3010002000300040005000200030004000 x1x220 x150 x29000010000.5x1+0.2x2=700d1+0d1+0d2-=0d2-0(810,1476)32管管 理理 运运 筹筹 学学22目标规划的图解法目标规划
35、的图解法目标规划的这种求解方法可以表述如下:目标规划的这种求解方法可以表述如下:1 1确定解的可行区域。确定解的可行区域。2 2对对优优先先权权最最高高的的目目标标求求解解,如如果果找找不不到到能能满满足足该该目目标标的的解解,则寻找最接近该目标的解。则寻找最接近该目标的解。3 3对对优优先先权权次次之之的的目目标标进进行行求求解解。注注意意:必必须须保保证证优优先先权权高高的的目标不变。目标不变。4.4.重复第重复第3 3步,直至所有优先权的目标求解完。步,直至所有优先权的目标求解完。33管管 理理 运运 筹筹 学学22目标规划的图解法目标规划的图解法四、目标规划模型的标准化四、目标规划模型
36、的标准化 例例6 6中对两个不同优先权的目标单独建立线性规划进行求解。为简中对两个不同优先权的目标单独建立线性规划进行求解。为简便,把它们用一个模型来表达,如下:便,把它们用一个模型来表达,如下:Min PMin P1 1(d d1 1+)+P+P2 2(d d2 2-)s.ts.t.20 x 20 x1 150 x50 x2 29000090000 0.5x 0.5x1 1+0.2x+0.2x2 2-d-d1 1+d+d1 1-=700=700 3x 3x1 1+4x+4x2 2-d-d2 2+d+d2 2-=10000=10000 x x1 1,x,x2 2,d,d1 1+,d,d1 1-
37、,d,d2 2+,d,d2 2-00 34管管 理理 运运 筹筹 学学22目标规划的图解法目标规划的图解法【例例】企业计划生产企业计划生产I、II 两种产品,这些产品需要使用两两种产品,这些产品需要使用两种材料,要在两种不同设备上加工工艺资料如表种材料,要在两种不同设备上加工工艺资料如表44所示所示产产品品 资源资源产品甲产品甲产品乙产品乙现有资源现有资源材料材料I3012(kg)材料材料II0414(kg)设备设备A2212(h)设备设备B5315(h)产品利润产品利润(元元/件件)2040表表4435管管 理理 运运 筹筹 学学22目标规划的图解法目标规划的图解法【解解】设设x1、x2分别
38、为产品甲和产品乙的产量,目标规划数学分别为产品甲和产品乙的产量,目标规划数学模型为:模型为:企业怎样安排生产计划,尽可能满足下列目标:企业怎样安排生产计划,尽可能满足下列目标:(1)力求使利润指标不低于力求使利润指标不低于80元元(2)考虑到市场需求考虑到市场需求,、II两种产品的生产量需保持两种产品的生产量需保持1:1的比例的比例(3)设备设备A既要求充分利用,又尽可能不加班既要求充分利用,又尽可能不加班(4)设备设备B必要时可以加班,但加班时间尽可能少必要时可以加班,但加班时间尽可能少(5)材料不能超用。材料不能超用。36管管 理理 运运 筹筹 学学(2)(1)(3)(4)x2x1(6)(
39、5)o46462 2图图41ABC满意解满意解C(3,3)满意解满意解X(3,3)37管管 理理 运运 筹筹 学学22目标规划的图解法目标规划的图解法(3)x1x22040608010020406080100(2)(1)(4)BC满意解是线段满意解是线段 上任意点,端点的上任意点,端点的解是解是 B(100/3,80/3),C(60,0)决策者根据实际情形进行二次选择决策者根据实际情形进行二次选择A38管管 理理 运运 筹筹 学学22目标规划的图解法目标规划的图解法(3)x1x22040608010020406080100(2)(1)(4)图图53BC满意解是点满意解是点 B,X=(100/3
40、,80/3)A39管管 理理 运运 筹筹 学学(3)x1x22040608010020406080100(2)(1)(4)满意解是点满意解是点 A,X=(20,40)A(20,40)D(80/9,560/9)注:线段注:线段DA是第二目标函数的组合,是第二目标函数的组合,点点A对应的偏差:对应的偏差:d2-=100,d3=0点点D对应的偏差:对应的偏差:d2-=0,2d3=2200/9=400/940管管 理理 运运 筹筹 学学33复杂情况下的目标规划复杂情况下的目标规划例例7一一工工艺艺品品厂厂商商手手工工生生产产某某两两种种工工艺艺品品A、B,已已知知生生产产一一件件产产品品A需需要要耗耗
41、费费人人力力2工工时时,生生产产一一件件产产品品B需需要要耗耗费费人人力力3工工时时。A、B产产品品的的单单位位利利润润分分别别为为250元元和和125元元。为为了了最最大大效效率率地地利利用用人人力力资资源源,确确定定生生产产的的首首要要任任务务是是保保证证人人员员高高负负荷荷生生产产,要要求求每每周周总总耗耗费费人人力力资资源源不不能能低低于于600工工时时,但但也也不不能能超超过过680工工时时的的极极限限;次次要要任任务务是是要要求求每每周周的的利利润润超超过过70000元元;在在前前两两个个任任务务的的前前提提下下,为为了了保保证证库库存存需需要要,要要求求每每周周产产品品A和和B的
42、的产产量量分分别别不不低低于于200和和120件件,因因为为B产产品品比比A产产品品更更重重要要,不不妨妨假假设设B完完成成最最低低产产量量120件的重要性是件的重要性是A完成完成200件的重要性的件的重要性的1倍。倍。试求如何安排生产?试求如何安排生产?41管管 理理 运运 筹筹 学学33复杂情况下的目标规划复杂情况下的目标规划解:解:本本问问题题中中有有3个个不不同同优优先先权权的的目目标标,不不妨妨用用P1、P2、P3表表示示从高至低的优先权。从高至低的优先权。对对应应P1有有两两个个目目标标:每每周周总总耗耗费费人人力力资资源源不不能能低低于于600工工时时,也不能超过也不能超过680
43、工时;工时;对应对应P2有一个目标:每周的利润超过有一个目标:每周的利润超过70000元;元;对对应应P3有有两两个个目目标标:每每周周产产品品A和和B的的产产量量分分别别不不低低于于200和和120件。件。42管管 理理 运运 筹筹 学学33复杂情况下的目标规划复杂情况下的目标规划采用简化模式,最终得到目标线性规划如下:Min P1(d1+)+P1(d2)+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-
44、d4+d4-=200 对应第4个目标 x2-d5+d5-=120 对应第5个目标 x1,x2,d1+,d1-,d2+,d2-,d3+,d3-,d4+,d4-,d5+,d5-043管管 理理 运运 筹筹 学学33复杂情况下的目标规划复杂情况下的目标规划 使用运筹学软件求解可得:x1=250;x2=60;d1+=0;d1-=0;d2+=80;d2-=0;d3+=0;d3-=0;d4+=50;d4-=0;d5+=0;d5-=60,目标函数d4-+2d5-=120。可见,目标1、目标3和目标4达到了,但目标2、目标5都有一些偏差。44管管 理理 运运 筹筹 学学44加权目标规划加权目标规划加权目标规划
45、加权目标规划是另一种解决多目标决策问题的方法,其基是另一种解决多目标决策问题的方法,其基本方法是通过量化的方法分配给每个目标的偏离的严重程本方法是通过量化的方法分配给每个目标的偏离的严重程度一个罚数权重,然后建立总的目标函数,该目标函数表度一个罚数权重,然后建立总的目标函数,该目标函数表示的目标是要使每个目标函数与各自目标的加权偏差之和示的目标是要使每个目标函数与各自目标的加权偏差之和最小,假设所有单个的目标函数及约束条件都符合线性规最小,假设所有单个的目标函数及约束条件都符合线性规划的要求,那么,整个问题都可以描述为一个线性规划的划的要求,那么,整个问题都可以描述为一个线性规划的问题。问题。
46、如果在例如果在例7中我们对每周总耗费的人力资源超过中我们对每周总耗费的人力资源超过680工时或工时或低于低于600工时的每工时罚数权重定为工时的每工时罚数权重定为7;每周利润低于;每周利润低于70000元时,每元的罚数权重为元时,每元的罚数权重为5;每周产品;每周产品A产量低于产量低于200件时每件时每件罚数权重为件罚数权重为2,而每周产品,而每周产品B产量低于产量低于120件时每件罚数权件时每件罚数权重为重为4。45管管 理理 运运 筹筹 学学44加权目标规划加权目标规划则其目标函数化为:则其目标函数化为:min7d1+7d2-+5d3-+2d4-+4d5-这就变成了一个普通的单一目标的线性
47、规划问题这就变成了一个普通的单一目标的线性规划问题 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。46管管 理理 运运 筹筹 学学55目标规划的单纯型法目标规划的单纯型法单纯形法求解目标规划可参照第一章的步骤,只是目标规划的单纯形法求解目标规划可参照第一章的步骤,只是目标规划的检验要按优先级顺序逐级进行
48、,不同的是:检验要按优先级顺序逐级进行,不同的是:(1)首先使得检验数中)首先使得检验数中P1的系数非负,再使得的系数非负,再使得P2的系数非负,的系数非负,依次进行;依次进行;(2)当)当P1、P2、Pk对应的系数全部非负时得到最优解;对应的系数全部非负时得到最优解;(3)如果)如果P1,Pi行系数非负,而行系数非负,而Pi+1行存在负数,并且负行存在负数,并且负数所在列上面数所在列上面P1,Pi行中存在正数时,得到满意解,计算行中存在正数时,得到满意解,计算结束结束47管管 理理 运运 筹筹 学学55目标规划的单纯型法目标规划的单纯型法【例例4.6】用单纯形法求解下述目标规划问题用单纯形法
49、求解下述目标规划问题【解解】以以d1、d2、d3为基变量,求出检验数,将检验数中优为基变量,求出检验数,将检验数中优先因子分离出来,每一优先级做一行,列出初始单纯形表先因子分离出来,每一优先级做一行,列出初始单纯形表4-5 48管管 理理 运运 筹筹 学学55目标规划的单纯型法目标规划的单纯型法Cj00P100P1P20bCB基变基变量量x1x2d1d1+d2d2+d3d3+P1d11211500d2211140P2d3221180CjZjP112 11P2221表表4549管管 理理 运运 筹筹 学学55目标规划的单纯型法目标规划的单纯型法表表45中,中,P1行中行中(2)最小,则最小,则x
50、2进基,求最小比值易知进基,求最小比值易知d1出出基,将第二列主元素化为基,将第二列主元素化为1,其余元素化为零,得到表,其余元素化为零,得到表46 Cj00P100P1P20bCB基基x1x2d1d1+d2d2+d3d3+0 x21/211/21/2250d23/21/21115P2d3111130CjZjP111P21111表表4650管管 理理 运运 筹筹 学学55目标规划的单纯型法目标规划的单纯型法表表46中中P1行全部检验数非负,表明第一目标已经得到优化行全部检验数非负,表明第一目标已经得到优化P2行存在负数,行存在负数,x1的检验数为的检验数为P20,选,选x1进基(也可以选进基(