运筹学-3、目标规划.ppt

上传人:桔**** 文档编号:571401286 上传时间:2024-08-10 格式:PPT 页数:55 大小:4.59MB
返回 下载 相关 举报
运筹学-3、目标规划.ppt_第1页
第1页 / 共55页
运筹学-3、目标规划.ppt_第2页
第2页 / 共55页
运筹学-3、目标规划.ppt_第3页
第3页 / 共55页
运筹学-3、目标规划.ppt_第4页
第4页 / 共55页
运筹学-3、目标规划.ppt_第5页
第5页 / 共55页
点击查看更多>>
资源描述

《运筹学-3、目标规划.ppt》由会员分享,可在线阅读,更多相关《运筹学-3、目标规划.ppt(55页珍藏版)》请在金锄头文库上搜索。

1、运筹学运运运运 筹筹筹筹 学学学学Operations ResearchOperations ResearchChapter4目标规划目标规划GoalProgramming运筹学运筹学OperationsResearch4.1目标规划数学模型目标规划数学模型Mathematical Model of GP4.2目标规划的图解法目标规划的图解法The graphical method of GP4.3单纯形法单纯形法Simplex Method4.1目标规划数学模型目标规划数学模型Mathematical Model of GP线性规划模型的特征是在满足一组约束条件下,寻求一个目线性规划模型的特

2、征是在满足一组约束条件下,寻求一个目标的最优解(最大值或最小值)。标的最优解(最大值或最小值)。而在现实生活中最优只是相对的,或者说没有绝对意义下的最而在现实生活中最优只是相对的,或者说没有绝对意义下的最优,只有相对意义下的满意。优,只有相对意义下的满意。1978年诺贝尔经济学奖获得者年诺贝尔经济学奖获得者.西蒙西蒙(H.A.Simon-美国卡内基美国卡内基-梅隆大学梅隆大学,1916-)教授提出教授提出“满意行为模型要比最大化行为模型满意行为模型要比最大化行为模型丰富得多丰富得多”,否定了企业的决策者是,否定了企业的决策者是“经济人经济人”概念和概念和“最大最大化化”行为准则,提出了行为准则

3、,提出了“管理人管理人”的概念和的概念和“令人满意令人满意”的行的行为准则,对现代企业管理的决策科学进行了开创性的研究为准则,对现代企业管理的决策科学进行了开创性的研究 4.1目标规划的数学模型目标规划的数学模型MathematicalModelofGP【例例4.】考虑例考虑例1.1资源消耗如表资源消耗如表4-1所示。所示。x1、x2、x3分分别为甲、乙、丙的产量。别为甲、乙、丙的产量。使企业在计划期内总利润最大的线性规划模型为:使企业在计划期内总利润最大的线性规划模型为: 产品产品 资源资源甲甲乙乙丙丙现有资源现有资源设备设备A312200设备设备B224200材料材料C451360材料材料

4、D235300利润(元利润(元/件)件)403050表表4-14.1.1引例引例4.1目标规划的数学模型目标规划的数学模型MathematicalModelofGP最优解最优解X(50,30,10),),Z34004.1目标规划的数学模型目标规划的数学模型MathematicalModelofGP 现在决策者根据企业的实际情况和市场需求,需要重新制现在决策者根据企业的实际情况和市场需求,需要重新制定经营目标,其目标的优先顺序是:定经营目标,其目标的优先顺序是:(1)利润不少于)利润不少于3200元元(2)产品甲与产品乙的产量比例尽量不超过)产品甲与产品乙的产量比例尽量不超过1.5(3)提高产品

5、丙的产量使之达到)提高产品丙的产量使之达到30件件(4)设备加工能力不足可以加班解决,能不加班最好不加班)设备加工能力不足可以加班解决,能不加班最好不加班(5)受到资金的限制,只能使用现有材料不能再购进)受到资金的限制,只能使用现有材料不能再购进【解解】设甲、乙、丙产品的产量分别为设甲、乙、丙产品的产量分别为x1、x2、x3。如果按线。如果按线性规划建模思路,最优解实质是求下列一组不等式的解性规划建模思路,最优解实质是求下列一组不等式的解4.1目标规划的数学模型目标规划的数学模型MathematicalModelofGP通过计算不等式无解,即使设备加班通过计算不等式无解,即使设备加班10小时仍

6、然无解在实小时仍然无解在实际生产过程中生产方案总是存在的,无解只能说明在现有资际生产过程中生产方案总是存在的,无解只能说明在现有资源条件下,不可能完全满足所有经营目标源条件下,不可能完全满足所有经营目标这种情形是按事先制定的目标顺序逐项检查,尽可能使得结果这种情形是按事先制定的目标顺序逐项检查,尽可能使得结果达到预定目标,即使不能达到目标也使得离目标的差距最小,达到预定目标,即使不能达到目标也使得离目标的差距最小,这就是目标规划的求解思路,对应的解称为满意解下面建立这就是目标规划的求解思路,对应的解称为满意解下面建立例例4.1的目标规划数学模型的目标规划数学模型4.1目标规划的数学模型目标规划

7、的数学模型MathematicalModelofGP设设d为未达到目标值的差值,称为负偏差变量(为未达到目标值的差值,称为负偏差变量(negativedeviationvariable)d+为超过目标值的差值,称为正偏差变量为超过目标值的差值,称为正偏差变量(positivedeviationvariable), d0、d0设设d1-未达到利润目标的差值未达到利润目标的差值,d1+为超过目标的差值为超过目标的差值当利润小于当利润小于3200时时,d1且且d10,有有40x1+30x2+50x3+d1=3200成立成立当利润大于当利润大于3200时,时,d1且且d1,有,有40x1+30x2+5

8、0x3-d1+=3200成立成立当利润恰好等于当利润恰好等于3200时,时,d1=且且d1+=0,有有40x1+30x2+50x3=3200成立成立实际利润只有上述三种情形之一发生,因而可以将三个等式写成一实际利润只有上述三种情形之一发生,因而可以将三个等式写成一个等式个等式40x1+30x2+50x3+d1d1+=32004.1目标规划的数学模型目标规划的数学模型MathematicalModelofGP(2)设)设分别为未达到和超过产品比例要求的偏差变分别为未达到和超过产品比例要求的偏差变量量,则产量比例尽则产量比例尽量不超过量不超过1.5的数学表达式为的数学表达式为:(3)设)设d3、d

9、分别为品丙的产量未达到和超过分别为品丙的产量未达到和超过30件的偏差件的偏差变量,则产量丙的产量尽可能达到变量,则产量丙的产量尽可能达到30件的数学表达式为:件的数学表达式为:利润不少于利润不少于3200理解为达到或超过理解为达到或超过3200,即使不能达到也要尽,即使不能达到也要尽可能接近可能接近3200,可以表达成目标函数可以表达成目标函数d1取最小值,则有取最小值,则有4.1目标规划的数学模型目标规划的数学模型MathematicalModelofGP(4)设设d4 、d4+为设备为设备A的使用时间偏差变量的使用时间偏差变量,d5、d5+为设备为设备B的使用时间偏差变量,最好不加班的含义

10、是的使用时间偏差变量,最好不加班的含义是d4+和和d5+同时取最同时取最小值,等价小值,等价于于d4+d5+取最小值,则设备的目标函数和约束为:取最小值,则设备的目标函数和约束为:(5)材料不能购进表示不允许有正偏差,约束条件为小于等于)材料不能购进表示不允许有正偏差,约束条件为小于等于约束约束由于目标是有序的并且四个目标函数非负,因此目标函数可以由于目标是有序的并且四个目标函数非负,因此目标函数可以表达成一个函数:表达成一个函数:4.1目标规划的数学模型目标规划的数学模型MathematicalModelofGP式中:式中:Pj(j=1,2,3,4)称为目标的优先因子,第一目标优于第二)称为

11、目标的优先因子,第一目标优于第二目标,第二目标优于第三目标等等,其含义是按目标,第二目标优于第三目标等等,其含义是按P1、P2、的次的次序分别求后面函数的最小值序分别求后面函数的最小值.则问题的目标规划数学模型为:则问题的目标规划数学模型为:4.1目标规划的数学模型目标规划的数学模型MathematicalModelofGP约束约束实际实际 偏差偏差目标目标1 1 C1C132203220= =320032002 2 C2C22 2= =0 03 3 C3C33030= =30304 4 C4C4164= =2002005 5 C5C5216216= =2002006 6 C6C6242242

12、118=3603607 7 C7C726626634=3003001 1X1X128282 2X2X220203 3X3X330304 4d1-d1-0 05 5d1+d1+20206 6d2-d2-2 27 7d2+d2+0 08 8d3-d3-0 09 9d3+d3+0 01010d4-d4-36361111d4+d4+0 01212d5-d5-0 01313d5+d5+1616满意解:满意解:约束分析:约束分析:4.1目标规划的数学模型目标规划的数学模型MathematicalModelofGP(1)目标规划数学模型的形式有:线性模型、非线性模型、)目标规划数学模型的形式有:线性模型、非

13、线性模型、整数模型、交互作用模型等整数模型、交互作用模型等(2)一个目标中的两个偏差变量)一个目标中的两个偏差变量di-、di+至少一个等于零,偏至少一个等于零,偏差变量向量的叉积等于零:差变量向量的叉积等于零:dd=0(3)一般目标规划是将多个目标函数写成一个由偏差变量构)一般目标规划是将多个目标函数写成一个由偏差变量构成的函数求最小值,按多个目标的重要性,确定优先等级,顺成的函数求最小值,按多个目标的重要性,确定优先等级,顺序求最小值序求最小值(4)按决策者的意愿,事先给定所要达到的目标值)按决策者的意愿,事先给定所要达到的目标值当期望结果不超过目标值时,目标函数求正偏差变量最小当期望结果

14、不超过目标值时,目标函数求正偏差变量最小;当期望结果不低于目标值时,目标函数求负偏差变量最小当期望结果不低于目标值时,目标函数求负偏差变量最小;当期望结果恰好等于目标值时,目标函数求正负偏差变量之和最当期望结果恰好等于目标值时,目标函数求正负偏差变量之和最小小4.1.2数学模型数学模型4.1目标规划的数学模型目标规划的数学模型MathematicalModelofGP(5)由目标构成的约束称为目标约束,目标约束具有更大的弹)由目标构成的约束称为目标约束,目标约束具有更大的弹性,允许结果与所制定的目标值存在正或负的偏差,如例性,允许结果与所制定的目标值存在正或负的偏差,如例4.1中的中的5个等式

15、约束;如果决策者要求结果一定不能有正或负的偏差,个等式约束;如果决策者要求结果一定不能有正或负的偏差,这种约束称为系统约束,如例这种约束称为系统约束,如例4.1的材料约束;的材料约束;(6)目标的排序问题。多个目标之间有相互冲突时,决策者首)目标的排序问题。多个目标之间有相互冲突时,决策者首先必须对目标排序。排序的方法有两两比较法、专家评分等方先必须对目标排序。排序的方法有两两比较法、专家评分等方法,构造各目标的权系数,依据权系数的大小确定目标顺序;法,构造各目标的权系数,依据权系数的大小确定目标顺序;(7)合理的确定目标数。目标规划的目标函数中包含了多个目)合理的确定目标数。目标规划的目标函

16、数中包含了多个目标,决策者对于具有相同重要性的目标可以合并为一个目标,标,决策者对于具有相同重要性的目标可以合并为一个目标,如果同一目标中还想分出先后次序,可以赋予不同的权系数,如果同一目标中还想分出先后次序,可以赋予不同的权系数,按系数大小再排序。例如,在例按系数大小再排序。例如,在例4.1中要求设备中要求设备B的加班时间不的加班时间不超过设备超过设备A的时间,目标函数可以表达为的时间,目标函数可以表达为,表示在表示在中先求中先求最小再求最小再求最小。最小。4.1目标规划的数学模型目标规划的数学模型MathematicalModelofGP(8)多目标决策问题多目标决策研究的范围比较广泛,在

17、)多目标决策问题多目标决策研究的范围比较广泛,在决策中,可能同时要求多个目标达到最优例如,企业在对多决策中,可能同时要求多个目标达到最优例如,企业在对多个项目投资时期望收益率尽可能最大,投资风险尽可能最小,个项目投资时期望收益率尽可能最大,投资风险尽可能最小,属于多目标决策问题,本章的目标规划尽管包含有多个目标,属于多目标决策问题,本章的目标规划尽管包含有多个目标,但还是按单个目标求偏差变量的最小值,目标函数中不含有决但还是按单个目标求偏差变量的最小值,目标函数中不含有决策变量,目标规划只是多目标决策的一种特殊情形本章不讨策变量,目标规划只是多目标决策的一种特殊情形本章不讨论多目标规划的求解方

18、法,只给出论多目标规划的求解方法,只给出WinQSB软件求解线性多目软件求解线性多目标规划的操作步骤,参看例标规划的操作步骤,参看例4.3和和4.94.1目标规划的数学模型目标规划的数学模型MathematicalModelofGP(9)目标规划的一般模型设)目标规划的一般模型设xj(j=1,2,n)为决策变量)为决策变量4.1目标规划的数学模型目标规划的数学模型MathematicalModelofGP式中式中p k为第为第k级优先因子级优先因子,k=1、2、K;wkl-、wkl+,为,为分别赋予第分别赋予第l个目标约束的正负偏差变量的权系数;个目标约束的正负偏差变量的权系数;gl为目标的为

19、目标的预期目标值,预期目标值,l=1,L(4.1b)为系统约束为系统约束,(4.1c)为目标约束)为目标约束【例例4.2】某企业集团计划用某企业集团计划用1000万元对下属万元对下属5个企业进行技术个企业进行技术改造,各企业单位的投资额已知,考虑改造,各企业单位的投资额已知,考虑2种市场需求变化、现有种市场需求变化、现有竞争对手、替代品的威胁等影响收益的竞争对手、替代品的威胁等影响收益的4个因素,技术改造完成个因素,技术改造完成后预测单位投资收益率后预测单位投资收益率((单位投资获得利润(单位投资获得利润/单位投资额)单位投资额)100)如表如表42所示所示4.1目标规划的数学模型目标规划的数

20、学模型MathematicalModelofGP集团制定的目标是:集团制定的目标是:(1)希望完成总投资额又不超过预算;)希望完成总投资额又不超过预算;(2)总期望收益率达到总投资的)总期望收益率达到总投资的30%;(3)投资风险尽可能最小;)投资风险尽可能最小;(4)保证企业)保证企业5的投资额占的投资额占20%左右左右集团应如何作出投资决策集团应如何作出投资决策企业企业1企业企业2企业企业3企业企业4企业企业5单位投资额单位投资额(万元万元)1210151320单位投单位投资收益资收益率预测率预测rij市场需求市场需求14.3255.845.26.56市场需求市场需求23.523.045.

21、084.26.24现有竞争对手现有竞争对手3.162.23.563.284.08替代品的威胁替代品的威胁2.243.122.62.23.24期望期望(平均平均)收益率收益率3.313.344.273.725.03表表424.1目标规划的数学模型目标规划的数学模型MathematicalModelofGP【解解】设设xj(j=1,2,5)为集团对第)为集团对第j 个企业投资的单位数个企业投资的单位数(1)总投资约束:)总投资约束:4.1目标规划的数学模型目标规划的数学模型MathematicalModelofGP(2)期望利润率约束:)期望利润率约束:整理得整理得(4)企业)企业5占占20%的投

22、资的目标函数为的投资的目标函数为,约束条件约束条件即即4.1目标规划的数学模型目标规划的数学模型MathematicalModelofGP(3)投资风险约束投资风险值的大小一般用期望收益率的方)投资风险约束投资风险值的大小一般用期望收益率的方差表示,但方差是差表示,但方差是x的非线性函数这里用离差(的非线性函数这里用离差(rijE(rj))近)近似表示风险值,例如,集团投资似表示风险值,例如,集团投资5个企业后对于市场需求变化第个企业后对于市场需求变化第一情形的风险是:一情形的风险是:则则4种因素风险最小的目标函数为:种因素风险最小的目标函数为:,约束条件为,约束条件为4.1目标规划的数学模型

23、目标规划的数学模型MathematicalModelofGP根据目标重要性依次写出目标函数,整理后得到投资决策的根据目标重要性依次写出目标函数,整理后得到投资决策的目标规划数学模型:目标规划数学模型:【例例4.3】车间计划生产车间计划生产I、II两种产品,每种产品均需经过两种产品,每种产品均需经过A、B两道工序加工工艺资料如表两道工序加工工艺资料如表43所示所示 产品产品工序工序产品甲产品甲产品乙产品乙每天加工能力每天加工能力(小时小时)A22120B12100C2.20.890产品售价产品售价(元元/件件)5070产品利润产品利润(元元/件件)108(1)车间如何安排生产计划,使产值和利润都

24、尽可能高)车间如何安排生产计划,使产值和利润都尽可能高(2)如果认为利润比产值重要,怎样决策)如果认为利润比产值重要,怎样决策表表434.1目标规划的数学模型目标规划的数学模型MathematicalModelofGP【解解】设设x1、x2分别为产品甲和产品乙的日产量,得到线性多分别为产品甲和产品乙的日产量,得到线性多目标规划模型:目标规划模型:4.1目标规划的数学模型目标规划的数学模型MathematicalModelofGP(1)将模型化为目标规划问题首先,通过分别求产值最大)将模型化为目标规划问题首先,通过分别求产值最大和利润最大的线性规划最优解和利润最大的线性规划最优解产值最大的最优解

25、:产值最大的最优解:X(1)(20,40),),Z13800利润最大的最优解:利润最大的最优解:X(2)(30,30),),Z2540目标确定为产值和利润尽可能达到目标确定为产值和利润尽可能达到3800和和540,得到目标规划,得到目标规划数学模型:数学模型:4.1目标规划的数学模型目标规划的数学模型MathematicalModelofGP4.1目标规划的数学模型目标规划的数学模型MathematicalModelofGP,等价于等价于(2)给)给d2-赋予一个比赋予一个比d1-的系数大的权系数的系数大的权系数,如如,约束条件不变,约束条件不变.权系数的大小依据重要权系数的大小依据重要程度给

26、定,或者根据同一优先级的偏差变量的关系给定,例如,程度给定,或者根据同一优先级的偏差变量的关系给定,例如,当利润当利润d2-减少一个单位时,产值减少一个单位时,产值d1-减少减少3个单位,则赋予个单位,则赋予d2-权权系数系数3,则目标函数为,则目标函数为本节介绍了如何建立目标规划的数学模型及有关概念本节介绍了如何建立目标规划的数学模型及有关概念1.目标规划由哪些要素构成,与线性规划有哪些不同之处目标规划由哪些要素构成,与线性规划有哪些不同之处2.偏差变量的含义及其作用偏差变量的含义及其作用3.目标函数的表达方法目标函数的表达方法4.优先级别的含义优先级别的含义4.1目标规划的数学模型目标规划

27、的数学模型MathematicalModelofGP4.2目标规划的图解法目标规划的图解法The graphical method of GP4.2目标规划的图解法目标规划的图解法ThegraphicalmethodofGP当目标规划模型中只含两个决策变量(不包含偏差变量)时,当目标规划模型中只含两个决策变量(不包含偏差变量)时,可以用图解法求出满意解可以用图解法求出满意解【例例4.4】企业计划生产企业计划生产I 、 II 两种产品,这些产品需要使用两种产品,这些产品需要使用两种材料,要在两种不同设备上加工工艺资料如表两种材料,要在两种不同设备上加工工艺资料如表44所所示示产品产品 资源资源产

28、品甲产品甲产品乙产品乙现有资源现有资源材料材料I3012(kg)材料材料II0414(kg)设备设备A2212(h)设备设备B5315(h)产品利润产品利润(元元/件件)2040表表44【解解】设设x1、x2分别为产品甲和产品乙的产量,目标规划数学分别为产品甲和产品乙的产量,目标规划数学模型为:模型为:企业怎样安排生产计划,尽可能满足下列目标:企业怎样安排生产计划,尽可能满足下列目标:(1)力求使利润指标不低于力求使利润指标不低于80元元(2)考虑到市场需求考虑到市场需求,、II两种产品的生产量需保持两种产品的生产量需保持1:1的比例的比例(3)设备设备A既要求充分利用,又尽可能不加班既要求充

29、分利用,又尽可能不加班(4)设备设备B必要时可以加班,但加班时间尽可能少必要时可以加班,但加班时间尽可能少(5)材料不能超用。材料不能超用。4.2目标规划的图解法目标规划的图解法ThegraphicalmethodofGP(2)(1)(3)(4 )x2x1(6)(5)o464622图图41ABC满意解满意解C(3,3)满意解满意解X(3,3)(3)x1x22040608010020406080100(2)(1)(4)图图53BC满意解是线段满意解是线段上任意点,端点的上任意点,端点的解是解是B(100/3,80/3),C(60,0)决策者根据实际情形进行二次选择决策者根据实际情形进行二次选择A

30、(3)x1x22040608010020406080100(2)(1)(4)图图53BC满意解是点满意解是点B,X=(100/3,80/3)A(3)x1x22040608010020406080100(2)(1)(4)图图53满意解是点满意解是点A,X=(20,40)A本节介绍了目标规划的图解法本节介绍了目标规划的图解法1.画出系统约束和目标约束直线画出系统约束和目标约束直线2.标明偏差变量大于零的变量标明偏差变量大于零的变量X的取值区域的取值区域3.按优先次序分别求各目标的最小值按优先次序分别求各目标的最小值4.2目标规划的图解法目标规划的图解法ThegraphicalmethodofGP4

31、.3单纯形法单纯形法SimplexMethod单纯形法求解目标规划可参照第一章的步骤,只是目标规划的单纯形法求解目标规划可参照第一章的步骤,只是目标规划的检验要按优先级顺序逐级进行,不同的是:检验要按优先级顺序逐级进行,不同的是:(1)首先使得检验数中)首先使得检验数中P1的系数非负,再使得的系数非负,再使得P2的系数非负,的系数非负,依次进行;依次进行;(2)当)当P1、P2、Pk对应的系数全部非负时得到满意解;对应的系数全部非负时得到满意解;(3)如果)如果P1,Pi行系数非负,而行系数非负,而Pi+1行存在负数,并且负行存在负数,并且负数所在列上面数所在列上面P1,Pi行中存在正数时,得

32、到满意解,计算行中存在正数时,得到满意解,计算结束结束4.3单纯形法单纯形法SimplexMethod【例例4.6】用单纯形法求解下述目标规划问题用单纯形法求解下述目标规划问题【解解】以以d1、d2、d3为基变量,求出检验数,将检验数中优为基变量,求出检验数,将检验数中优先因子分离出来,每一优先级做一行,列出初始单纯形表先因子分离出来,每一优先级做一行,列出初始单纯形表4-54.3单纯形法单纯形法SimplexMethodCj00P100P1P20bCB基基x1x2d1d1+d2d2+d3d3+P1d11211500d2211140P2d3221180CjZjP112 11P2221表表454

33、.3单纯形法单纯形法SimplexMethod表表45中,中,P1行中行中(2)最小,则最小,则x2进基,求最小比值易知进基,求最小比值易知d1出出基,将第二列主元素化为基,将第二列主元素化为1,其余元素化为零,得到表,其余元素化为零,得到表4-6Cj00P100P1P20bCB基基x1x2d1d1+d2d2+d3d3+0x21/211/21/2250d23/21/21115P2d3111130CjZjP111P21111表表464.3单纯形法单纯形法SimplexMethod表表4-6中中P1行全部检验数非负,表明第一目标已经得到优化行全部检验数非负,表明第一目标已经得到优化P2行存在负数,

34、行存在负数,x1的检验的检验数为数为P20,选,选x1进基(也可以选进基(也可以选d1+进基),则进基),则d3出基,迭代得到表出基,迭代得到表4-7Cj00P100P1P20bCB基基x1x2d1d1+d2d2+d3d3+0x212/32/31/3200x111/32/310P2d32/32/31120CjZjP111P22/3-2/32/3-2/314.3单纯形法单纯形法SimplexMethod 表表4-7在表在表4-7中,中,P1行的系数全部非负,行的系数全部非负,P2行存在负数,行存在负数,d1+的检验数的检验数2/3P20,所有检验数非负,得到满意解所有检验数非负,得到满意解X(0

35、,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-134.3单纯形法单纯形法SimplexMethod求满意解求满意解Cj00P100P1P2P20P3bCB基基x1x2d1d1+d2d2+d3d3+d4d4+P1d1

36、105114000d27811560P2d322111200d412.511100CjZjP1 11P222P31表表4-94.3单纯形法单纯形法SimplexMethodCj00P100P1P2P20P3bCB基基x1x2d1d1+d2d2+d3d3+d4d4+0x111/21/101/10400d29/2-7/107/1011280P2d311/51/511400d42-1/101/101160CjZjP111P2-11/51/52P31表表4-104.3单纯形法单纯形法SimplexMethodCj00P100P1P2P20P3bCB基基x1x2d1d1+d2d2+d3d3+d4d4+0

37、x115/405/401/41/4250d2-19/4019/40119/49/4145P2d33/203/20111/21/2100x211/201/201/21/230CjZjP11P23/203/2021/21/2P31表表4114.3单纯形法单纯形法SimplexMethodCj00P100P1P2P20P3bCB基基x1x2d1d1+d2d2+d3d3+d4d4+0x115/65/62/32/3100/30d21119/619/62/32/3340/30d1+1120/320/310/310/3200/30x211/31/32/32/3CjZjP11P211P31表表4-124.3单

38、纯形法单纯形法SimplexMethodCj00P100P1P2P20P3bCB基基x1x2d1d1+d2d2+d3d3+d4d4+0x1111/21/2600d21117/27/21400d1+511552000d43/21/21/213/440CjZjP11P211P31表表4134.3单纯形法单纯形法SimplexMethod(2)将目标函数)将目标函数改写成改写成以表以表4-12为基础,计算出检验数得到表为基础,计算出检验数得到表4-14表表4-14Cj00P1P1P300P20P4bCB基基x1x2d1d1+d2d2+d3d3+d4d4+0x115/65/62/32/3100/3P3

39、d211-19/619/62/32/3340/3 P1d1+1120/3-20/3-10/310/3200/30x211/31/32/32/380/3CjZjP12-20/320/310/3-10/3P219/67/62/32/3P3119/61P414.3单纯形法单纯形法SimplexMethodCj 00P1P1P300P20P4bCB基基x1x2d1d1+d2d2+d3d3+d4d4+0x111/81/81/41/425P3d219/4019/401-19/49/4145 0d33/203/201-11/21/2100x211/201/201/21/230CjZjP111P21P319/

40、4019/4019/49/4P41表表4-154.3单纯形法单纯形法SimplexMethodCj00P1P1P300P20P4bCB基基x1x2d1d1+d2d2+d3d3+d4d4+0x111/51/51/21/220P3d21/51/5119/29/2100 P4d4+3/103/102211200x211/51/51140CjZjP111P21P31/51/519/29/2P43/103/1021表表4-16用单纯形法求解得到最终表用单纯形法求解得到最终表4-16,满意解,满意解X(20,40)T,对应于图,对应于图4-6中点中点A在(在(2)中如果按)中如果按求解,单求解,单纯形法计

41、算如表纯形法计算如表4-17所示所示4.3单纯形法单纯形法SimplexMethod00P1P1P2002P20P3bx1x2d1d1+d2d2+d3d3+d4d4+x115/65/62/32/3100/3d21119/619/62/32/3340/3d1+1120/320/310/310/3200/3x211/31/32/32/380/3P1220/320/310/310/3P219/67/632/2/3P311表表4-17 转下表转下表4.3单纯形法单纯形法SimplexMethod00P1P1P2002P20P3bx1x2d1d1+d2d2+d3d3+d4d4+x118/458/451/

42、91/980/9d3+2/452/452/92/911200/9d4+19/9019/904/94/911580/9x217/457/452/92/9560/9P111P24/454/455/94/92P319/9019/904/94/91最终表:最终表:4.3单纯形法单纯形法SimplexMethod满意解满意解X(80/9,560/9)T,d3+200/9而而d20,与目标要求,与目标要求相悖,还可以从图相悖,还可以从图4-6说明这个结果是错误的说明这个结果是错误的例例4.7(2)是在原问题中作了部分变动后再求解,等价于第)是在原问题中作了部分变动后再求解,等价于第二章的灵敏度分析,求解原

43、理基本相同二章的灵敏度分析,求解原理基本相同4.2目标规划的图解法目标规划的图解法ThegraphicalmethodofGP目标规划的单纯形法与线性规划比较主要有两点不同。目标规划的单纯形法与线性规划比较主要有两点不同。第一,目标规划是按优先次序顺序求解,逐个满足最优(检第一,目标规划是按优先次序顺序求解,逐个满足最优(检验数大于等于零);验数大于等于零);第二,不一定所有检验数都能满足大于等于零,如果某个检第二,不一定所有检验数都能满足大于等于零,如果某个检验数小于零,所在列存在检验数大于零时,则认为得到满意解。验数小于零,所在列存在检验数大于零时,则认为得到满意解。计算方法和基本原理与线性规划类似。计算方法和基本原理与线性规划类似。

展开阅读全文
相关资源
正为您匹配相似的精品文档
相关搜索

最新文档


当前位置:首页 > 高等教育 > 研究生课件

电脑版 |金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号