大学精品课件：5目标规划.ppt

1、运筹学运运 筹筹 学学Chapter 4 目标规划目标规划Goal Programming 运筹学运筹学Operations Research4.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目标规划的数学模型目标规划的数学模型Mathematical Model of GP【例例4.】考虑例考虑例1.1资源消耗如表资源消耗如表4-1所示。所示。x1、x2、x3分分别为甲、乙、丙的产量。别为甲、乙、丙的产量。使企业在计划期内总利润最大的线性规划模型为：使企业在计划期内总利润最大的线性规划模型为：产品产品 资源资源甲甲乙乙丙丙现有资源现有资源设备设备A312200设备设备B224200材料材料C451360材料材料D235300利润（元利润（元/件）件）403050表表4

4、-14.1.1 引例引例4.1目标规划的数学模型目标规划的数学模型Mathematical Model of GP321503040maxxxxZ0003005323605420042220023321321321321321xxxxxxxxxxxxxxx，最优解最优解X（50，30，10），），Z34004.1目标规划的数学模型目标规划的数学模型Mathematical Model of GP 现在决策者根据企业的实际情况和市场需求，需要重新制现在决策者根据企业的实际情况和市场需求，需要重新制定经营目标，其目标的优先顺序是：定经营目标，其目标的优先顺序是：（1）利润不少于）利润不少于3200

5、元元（2）产品甲与产品乙的产量比例尽量不超过）产品甲与产品乙的产量比例尽量不超过1.5（3）提高产品丙的产量使之达到）提高产品丙的产量使之达到30件件（4）设备加工能力不足可以加班解决，能不加班最好不加班）设备加工能力不足可以加班解决，能不加班最好不加班（5）受到资金的限制，只能使用现有材料不能再购进）受到资金的限制，只能使用现有材料不能再购进【解解】设甲、乙、丙产品的产量分别为设甲、乙、丙产品的产量分别为x1、x2、x3。如果按线。如果按线性规划建模思路，最优解实质是求下列一组不等式的解性规划建模思路，最优解实质是求下列一组不等式的解4.1目标规划的数学模型目标规划的数学模型Mathemat

6、ical Model of GP00030053236054200422200233005.13200503040321321321321321321321xxxxxxxxxxxxxxxxxxxxx，通过计算不等式无解，即使设备加班通过计算不等式无解，即使设备加班10小时仍然无解在实小时仍然无解在实际生产过程中生产方案总是存在的，无解只能说明在现有资际生产过程中生产方案总是存在的，无解只能说明在现有资源条件下，不可能完全满足所有经营目标源条件下，不可能完全满足所有经营目标这种情形是按事先制定的目标顺序逐项检查，尽可能使得结这种情形是按事先制定的目标顺序逐项检查，尽可能使得结果达到预定目标，即使

7、不能达到目标也使得离目标的差距最果达到预定目标，即使不能达到目标也使得离目标的差距最小，这就是目标规划的求解思路，对应的解称为满意解下小，这就是目标规划的求解思路，对应的解称为满意解下面建立例面建立例4.1的目标规划数学模型的目标规划数学模型 4.1目标规划的数学模型目标规划的数学模型Mathematical Model of GP设设d为未达到目标值的差值，称为负偏差变量（为未达到目标值的差值，称为负偏差变量（negative deviation variable）d+为超过目标值的差值，称为正偏差变量为超过目标值的差值，称为正偏差变量（positive deviation variable

8、）,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

9、x2+50 x3+d1d1+=32004.1目标规划的数学模型目标规划的数学模型Mathematical Model of GP3200503040min113211ddxxxd（2）设）设 分别为未达到和超过产品比例要求的偏差变分别为未达到和超过产品比例要求的偏差变量量,则产量比例尽则产量比例尽 量不超过量不超过1.5的数学表达式为的数学表达式为：22dd、05.1min22212ddxxd （3）设）设d3、d分别为品丙的产量未达到和超过分别为品丙的产量未达到和超过30件的偏差件的偏差变量，则产量丙的产量尽可能达到变量，则产量丙的产量尽可能达到30件的数学表达式为：件的数学表达式为：30m

10、in3333ddxd利润不少于利润不少于3200理解为达到或超过理解为达到或超过3200，即使不能达到也要尽，即使不能达到也要尽可能接近可能接近3200,可以表达成目标函数可以表达成目标函数d1取最小值，则有取最小值，则有4.1目标规划的数学模型目标规划的数学模型Mathematical Model of GP（4）设设d4、d4+为设备为设备A的使用时间偏差变量的使用时间偏差变量,d5、d5+为设备为设备B的使用时间偏差变量，最好不加班的含义是的使用时间偏差变量，最好不加班的含义是 d4+和和d5+同时取最同时取最小值，等价小值，等价 于于d4+d5+取最小值，则设备的目标函数和约束为：取最

11、小值，则设备的目标函数和约束为：20042220023min553214432154ddxxxddxxxdd（5）材料不能购进表示不允许有正偏差，约束条件为小于等于）材料不能购进表示不允许有正偏差，约束条件为小于等于约束约束由于目标是有序的并且四个目标函数非负，因此目标函数可以由于目标是有序的并且四个目标函数非负，因此目标函数可以表达成一个函数：表达成一个函数：4.1目标规划的数学模型目标规划的数学模型Mathematical Model of GP)(min544332211ddPdPdPdPz式中：式中：Pj（j=1,2,3,4）称为目标的优先因子，第一目标优于第二称为目标的优先因子，第一

12、目标优于第二目标，第二目标优于第三目标等等，其含义是按目标，第二目标优于第三目标等等，其含义是按P1、P2、的次的次序分别求后面函数的最小值序分别求后面函数的最小值.则问题的目标规划数学模型为：则问题的目标规划数学模型为：5,2,1,0,0,0,030053236054200422200233005.13200503040)(min3213213215532144321333222111321544332211jddxxxxxxxxxddxxxddxxxddxddxxddxxxddPdPdPdPzjj、且为整数4.1目标规划的数学模型目标规划的数学模型Mathematical Model of

13、 GP约束约束实际实际 偏差偏差目标目标1 1 C1C132203220=320032002 2 C2C22 2=0 03 3 C3C33030=30304 4 C4C4164=2002005 5 C5C5216216=2002006 6 C6C6242242118=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 01212

14、d5-d5-0 01313d5+d5+1616满意解：满意解：约束分析：约束分析：4.1目标规划的数学模型目标规划的数学模型Mathematical Model of GP120d22d436d516d（1）目标规划数学模型的形式有：线性模型、非线性模型、）目标规划数学模型的形式有：线性模型、非线性模型、整数模型、交互作用模型等整数模型、交互作用模型等（2）一个目标中的两个偏差变量）一个目标中的两个偏差变量di-、di+至少一个等于零，偏至少一个等于零，偏差变量向量的叉积等于零：差变量向量的叉积等于零：dd=0 （3）一般目标规划是将多个目标函数写成一个由偏差变量）一般目标规划是将多个目标函数

15、写成一个由偏差变量构成的函数求最小值，按多个目标的重要性，确定优先等级，构成的函数求最小值，按多个目标的重要性，确定优先等级，顺序求最小值顺序求最小值 （4）按决策者的意愿，事先给定所要达到的目标值）按决策者的意愿，事先给定所要达到的目标值当期望结果不超过目标值时，目标函数求正偏差变量最小当期望结果不超过目标值时，目标函数求正偏差变量最小;当期望结果不低于目标值时，目标函数求负偏差变量最小当期望结果不低于目标值时，目标函数求负偏差变量最小;当期望结果恰好等于目标值时，目标函数求正负偏差变量之和最当期望结果恰好等于目标值时，目标函数求正负偏差变量之和最小小4.1.2 数学模型数学模型4.1目标规

16、划的数学模型目标规划的数学模型Mathematical Model of GP（5）由目标构成的约束称为目标约束，目标约束具有更大的弹）由目标构成的约束称为目标约束，目标约束具有更大的弹性，允许结果与所制定的目标值存在正或负的偏差，如例性，允许结果与所制定的目标值存在正或负的偏差，如例4.1中中的的5个等式约束；如果决策者要求结果一定不能有正或负的偏差，个等式约束；如果决策者要求结果一定不能有正或负的偏差，这种约束称为系统约束，如例这种约束称为系统约束，如例4.1的材料约束；的材料约束；（6）目标的排序问题。多个目标之间有相互冲突时，决策者）目标的排序问题。多个目标之间有相互冲突时，决策者首先

17、必须对目标排序。排序的方法有两两比较法、专家评分等首先必须对目标排序。排序的方法有两两比较法、专家评分等方法，构造各目标的权系数，依据权系数的大小确定目标顺序；方法，构造各目标的权系数，依据权系数的大小确定目标顺序；（7）合理的确定目标数。目标规划的目标函数中包含了多个目）合理的确定目标数。目标规划的目标函数中包含了多个目标，决策者对于具有相同重要性的目标可以合并为一个目标，标，决策者对于具有相同重要性的目标可以合并为一个目标，如果同一目标中还想分出先后次序，可以赋予不同的权系数，如果同一目标中还想分出先后次序，可以赋予不同的权系数，按系数大小再排序。例如，在例按系数大小再排序。例如，在例4.

18、1中要求设备中要求设备B的加班时间不的加班时间不超过设备超过设备A的时间，目标函数可以表达为的时间，目标函数可以表达为 ,表示在表示在中先求中先求 最小再求最小再求 最小。最小。542dd54dd、5d4d4.1目标规划的数学模型目标规划的数学模型Mathematical Model of GP（8）多目标决策问题多目标决策研究的范围比较广泛，在）多目标决策问题多目标决策研究的范围比较广泛，在决策中，可能同时要求多个目标达到最优例如，企业在对多决策中，可能同时要求多个目标达到最优例如，企业在对多个项目投资时期望收益率尽可能最大，投资风险尽可能最小，个项目投资时期望收益率尽可能最大，投资风险尽可

19、能最小，属于多目标决策问题，本章的目标规划尽管包含有多个目标，属于多目标决策问题，本章的目标规划尽管包含有多个目标，但还是按单个目标求偏差变量的最小值，目标函数中不含有决但还是按单个目标求偏差变量的最小值，目标函数中不含有决策变量，目标规划只是多目标决策的一种特殊情形本章不讨策变量，目标规划只是多目标决策的一种特殊情形本章不讨论多目标规划的求解方法，只给出论多目标规划的求解方法，只给出WinQSB软件求解线性多目软件求解线性多目标规划的操作步骤，参看例标规划的操作步骤，参看例4.3和和4.94.1目标规划的数学模型目标规划的数学模型Mathematical Model of GP（9）目标规划

20、的一般模型设）目标规划的一般模型设xj（j=1,2,n）为决策变量为决策变量)1.4(),1(0,)1.4(),1(0)1.4(),1()1.4(),1(),()1.4()(min1111eLldddnjxcLlgddxcbmibxaadwdwPzlljnjllljljnjijijLllkllklKkk4.1目标规划的数学模型目标规划的数学模型Mathematical Model of GP 式中式中p k 为第为第k 级优先因子级优先因子,k=1、2、K；wkl-、wkl+，为为分别赋予第分别赋予第l个目标约束的正负偏差变量的权系数；个目标约束的正负偏差变量的权系数；gl为目标为目标的预期目

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

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

23、.26.24现有竞争对手现有竞争对手3.162.23.563.284.08替代品的威胁替代品的威胁2.243.122.62.23.24期望期望(平均平均)收益率收益率3.313.344.273.725.03表表424.1目标规划的数学模型目标规划的数学模型Mathematical Model of GP【解解】设设xj（j=1,2,5）为集团对第为集团对第 j 个企业投资的单位数个企业投资的单位数100020131510121154321ddxxxxx（1）总投资约束：）总投资约束：4.1目标规划的数学模型目标规划的数学模型Mathematical Model of GP（2）期望利润率约束：

24、）期望利润率约束：)2013151012(3.003.572.327.434.331.3543212254321xxxxxddxxxxx整理得整理得097.018.023.034.029.02254321ddxxxxx079.152.167.122.007.1095.044.071.014.115.0021.148.081.03.021.0053.148.157.166.101.16654321555432144543213354321ddxxxxxddxxxxxddxxxxxddxxxxx（4）企业）企业5占占20%的投资的目标函数为的投资的目标函数为 ,约束条件约束条件77mindd)20

25、13151012(2.02054321775xxxxxddx0166.2324.27754321ddxxxxx即即4.1目标规划的数学模型目标规划的数学模型Mathematical Model of GP(3）投资风险约束投资风险值的大小一般用期望收益率的方）投资风险约束投资风险值的大小一般用期望收益率的方差表示，但方差是差表示，但方差是x的非线性函数这里用离差（的非线性函数这里用离差（rijE(rj)）近近似表示风险值，例如，集团投资似表示风险值，例如，集团投资5个企业后对于市场需求变化个企业后对于市场需求变化第一情形的风险是：第一情形的风险是：则则4种因素风险最小的目标函数为：种因素风险最

26、小的目标函数为：，约束条件为，约束条件为521)03.556.6()34.35()31.332.4(xxx63)(miniiidd)()()(min77463322111ddPddPdPddPZiii5,2,17,2,10,00166.2324.2079.152.167.122.007.1095.044.071.014.115.0021.148.081.03.021.0053.148.157.166.101.1097.018.023.034.029.0100020131510127754321665432155543214454321335432122543211154321jiddxddxx

27、xxxddxxxxxddxxxxxddxxxxxddxxxxxddxxxxxddxxxxxiij；、4.1目标规划的数学模型目标规划的数学模型Mathematical Model of GP根据目标重要性依次写出目标函数，整理后得到投资决策的根据目标重要性依次写出目标函数，整理后得到投资决策的目标规划数学模型：目标规划数学模型：【例例4.3】车间计划生产车间计划生产I、II 两种产品，每种产品均需经过两种产品，每种产品均需经过A、B两道工序加工工艺资料如表两道工序加工工艺资料如表43所示所示 产品产品工序工序产品甲产品甲产品乙产品乙每天加工能力每天加工能力(小时小时)A22120B12100C

28、2.20.890产品售价产品售价(元元/件件)5070产品利润产品利润(元元/件件)108（1）车间如何安排生产计划，使产值和利润都尽可能高）车间如何安排生产计划，使产值和利润都尽可能高（2）如果认为利润比产值重要，怎样决策）如果认为利润比产值重要，怎样决策表表434.1目标规划的数学模型目标规划的数学模型Mathematical Model of GP【解解】设设x1、x2分别为产品甲和产品乙的日产量，得到线性多分别为产品甲和产品乙的日产量，得到线性多目标规划模型：目标规划模型：0908.02.2100212022810max7050max21212121212211xxxxxxxxxxZx

29、xZ、4.1目标规划的数学模型目标规划的数学模型Mathematical Model of GP（1）将模型化为目标规划问题首先，通过分别求产值最大）将模型化为目标规划问题首先，通过分别求产值最大和利润最大的线性规划最优解和利润最大的线性规划最优解产值最大的最优解：产值最大的最优解：X(1)（20，40），），Z13800利润最大的最优解：利润最大的最优解：X(2)（30，30），），Z2540目标确定为产值和利润尽可能达到目标确定为产值和利润尽可能达到3800和和540，得到目标规划，得到目标规划数学模型：数学模型：2,1,0908.02.210021202254081038007050mi

30、n2121212221112121jddxxxxxxxddxxddxxddZjjj、4.1目标规划的数学模型目标规划的数学模型Mathematical Model of GP4.1目标规划的数学模型目标规划的数学模型Mathematical Model of GP,等价于等价于213minddZ1221mindpdpZ（2）给）给 d2-赋予一个比赋予一个比d1-的系数大的权系数的系数大的权系数,如如 ，约束条件不变，约束条件不变.权系数的大小依据重要权系数的大小依据重要程度给定，或者根据同一优先级的偏差变量的关系给定，例如，程度给定，或者根据同一优先级的偏差变量的关系给定，例如，当利润当利润

31、d2-减少一个单位时，产值减少一个单位时，产值d1-减少减少3个单位，则赋予个单位，则赋予d2-权权系数系数3，则目标函数为，则目标函数为 212minddZ本节介绍了如何建立目标规划的数学模型及有关概念本节介绍了如何建立目标规划的数学模型及有关概念1.目标规划由哪些要素构成，与线性规划有哪些不同之处目标规划由哪些要素构成，与线性规划有哪些不同之处2.偏差变量的含义及其作用偏差变量的含义及其作用3.目标函数的表达方法目标函数的表达方法4.优先级别的含义优先级别的含义4.1目标规划的数学模型目标规划的数学模型Mathematical Model of GP作业作业:教材教材P90 1，2，4 下

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

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

34、分利用，又尽可能不加班(4)设备设备B必要时可以加班，但加班时间尽可能少必要时可以加班，但加班时间尽可能少(5)材料不能超用。材料不能超用。4333322211)()mindPddPddPdPz（12121112221233124412312(1)416(2)204080(3)0(4)2212(5)5315(6),0(1,4)iixxxxddxxddxxddxxddx xddi4.2目标规划的图解法目标规划的图解法The graphical method of GP(2)(1)(3)(4)x2x1(6)(5)o46462 2图图41ABC4333322211)()mindPddPddPdPz（

35、4d4d1d1d2d3d2d3d12121112221233124412312(1)416(2)204080(3)0(4)2212(5)5315(6),0(1,4)iixxxxddxxddxxddxxddx xddi满意解满意解C(3,3)1mind22mindd33mindd满意解满意解X(3,3)(3)x1x22040608010020406080100(2)(1)(4)1d1d2d3d2d3d4d4d图图534,1,0,)4(1005.2)3(12022)2(56087)1(400510)()(max21442133212221112143332211jddxxddxxddxxddxxd

36、dxxdPddPddPZjj、BC满意解是线段满意解是线段 上任意点，端点的上任意点，端点的解是解是 B(100/3，80/3)，C(60，0)决策者根据实际情形进行二次选择决策者根据实际情形进行二次选择BCA(3)x1x22040608010020406080100(2)(1)(4)1d1d2d3d2d3d4d4d图图534,1,0,)4(1005.2)3(12022)2(56087)1(400510214421332122211121jddxxddxxddxxddxxddxxjj、BC满意解是点满意解是点 B，X=(100/3，80/3)1122333441min()()ZP ddP dd

37、PdPdA(3)x1x22040608010020406080100(2)(1)(4)1d1d2d3d2d3d4d4d图图534,1,0,)4(1005.2)3(12022)2(56087)1(400510214421332122211121jddxxddxxddxxddxxddxxjj、满意解是点满意解是点 A，X=(20，40)43322111)2()(mindPddPddPZA本节介绍了目标规划的图解法本节介绍了目标规划的图解法1.画出系统约束和目标约束直线画出系统约束和目标约束直线2.标明偏差变量大于零的变量标明偏差变量大于零的变量X的取值区域的取值区域3.按优先次序分别求各目标的最小

38、值按优先次序分别求各目标的最小值作业作业:教材教材P91 T3 下一节：目标规划的单纯形法下一节：目标规划的单纯形法4.2目标规划的图解法目标规划的图解法The graphical method of GP4.3 单纯形法单纯形法Simplex Method单纯形法求解目标规划可参照第一章的步骤，只是目标规划的单纯形法求解目标规划可参照第一章的步骤，只是目标规划的检验要按优先级顺序逐级进行，不同的是：检验要按优先级顺序逐级进行，不同的是：（1）首先使得检验数中）首先使得检验数中P1的系数非负，再使得的系数非负，再使得P2的系数非负，的系数非负，依次进行；依次进行；（2）当）当P1、P2、Pk对

39、应的系数全部非负时得到满意解；对应的系数全部非负时得到满意解；（3）如果）如果P1，Pi行系数非负，而行系数非负，而Pi+1行存在负数，并且负行存在负数，并且负数所在列上面数所在列上面P1，Pi行中存在正数时，得到满意解，计算行中存在正数时，得到满意解，计算结束结束4.3 单纯形法单纯形法Simplex Method【例例4.6】用单纯形法求解下述目标规划问题用单纯形法求解下述目标规划问题)3,2,1(0,8022402502)(min2133212221112132211iddxxddxxddxxddxxdPddPzii【解解】以以d1、d2、d3为基变量，求出检验数，将检验数中优为基变量，

40、求出检验数，将检验数中优先因子分离出来，每一优先级做一行，列出初始单纯形表先因子分离出来，每一优先级做一行，列出初始单纯形表4-5 4.3 单纯形法单纯形法Simplex MethodCj00P100P1P20bCB基基x1x2d1d1+d2d2+d3d3+P1d11211500d2211140P2d3221180CjZjP112 11P2221表表454.3 单纯形法单纯形法Simplex Method表表45中，中，P1行中行中(2)最小，则最小，则x2进基，求最小比值易知进基，求最小比值易知d1出出基，将第二列主元素化为基，将第二列主元素化为1，其余元素化为零，得到表，其余元素化为零，得

41、到表4-6Cj00P100P1P20bCB基基x1x2d1d1+d2d2+d3d3+0 x21/211/21/2250d23/21/21115P2d3111130CjZjP111P21111表表464.3 单纯形法单纯形法Simplex Method表表4-6中中P1行全部检验数非负，表明第一目标已经得到优化行全部检验数非负，表明第一目标已经得到优化P2行存在负数，行存在负数，x1的检验的检验数为数为P20，选，选x1进基（也可以选进基（也可以选d1+进基），则进基），则d3出基，迭代得到表出基，迭代得到表4-7Cj00P100P1P20bCB基基x1x2d1d1+d2d2+d3d3+0 x2

42、12/32/31/3200 x111/32/310P2d32/32/31120CjZjP111P22/3-2/32/3-2/314.3 单纯形法单纯形法Simplex Method 表表4-7在表在表4-7中，中，P1行的系数全部非负，行的系数全部非负，P2行存在负数，行存在负数，d1+的检验数的检验数2/3P20,所有检验数非负，得到满意解所有检验数非负，得到满意解X（0，40）【例例4.7】(1)用单纯形法求解例用单纯形法求解例4.5 （2）当目标函数变为）当目标函数变为43322111)2()(mindPddPddPZ【解解】（1）初始单纯形表见表）初始单纯形表见表4-9，最终单纯形表见

43、表，最终单纯形表见表4-12满满意解意解X(100/3，80/3)T，对应于图，对应于图4-6点点B不难看出有多重解，不难看出有多重解，将将d4进基进基x2出基出基，得到另一满意解，得到另一满意解X(60，0)T，对应于图，对应于图4-6点点C，见表，见表4-134.3 单纯形法单纯形法Simplex Method求满意解求满意解Cj00P100P1P2P20P3bCB基基x1x2d1d1+d2d2+d3d3+d4d4+P1d1105114000d27811560P2d322111200d412.511100CjZjP1 11P222P31表表4-94.3 单纯形法单纯形法Simplex Me

44、thodCj00P100P1P2P20P3bCB基基x1x2d1d1+d2d2+d3d3+d4d4+0 x111/21/101/10400d29/2-7/107/1011280P2d311/51/511400d42-1/101/101160CjZjP111P2-11/51/52P31表表4-104.3 单纯形法单纯形法Simplex MethodCj00P100P1P2P20P3bCB基基x1x2d1d1+d2d2+d3d3+d4d4+0 x115/405/401/41/4250d2-19/4019/40119/49/4145P2d33/203/20111/21/2100 x211/201/2

45、01/21/230CjZjP11P23/203/2021/21/2P31表表4114.3 单纯形法单纯形法Simplex MethodCj00P100P1P2P20P3bCB基基x1x2d1d1+d2d2+d3d3+d4d4+0 x115/65/62/32/3100/30d21119/619/62/32/3340/30d1+1120/320/310/310/3200/30 x211/31/32/32/3CjZjP11P211P31表表4-124.3 单纯形法单纯形法Simplex MethodCj00P100P1P2P20P3bCB基基x1x2d1d1+d2d2+d3d3+d4d4+0 x11

46、11/21/2600d21117/27/21400d1+511552000d43/21/21/213/440CjZjP11P211P31表表4134.3 单纯形法单纯形法Simplex Method（2）将目标函数）将目标函数 改写成改写成 43322111)2()(mindPddPddPZ442332111)(mindPdPdPddPZ以表以表4-12为基础，计算出检验数得到表为基础，计算出检验数得到表4-14表表4-14Cj00P1P1P300P20P4bCB基基x1x2d1d1+d2d2+d3d3+d4d4+0 x115/65/62/32/3100/3P3d211-19/619/62/3

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

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

49、算如表4-17所示所示 43322111)2()(mindPddPddPZ4.3 单纯形法单纯形法Simplex Method00P1P1P2002P20P3bx1x2d1d1+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 单纯形法单纯形法Simplex Method00P1P1P2002P20P3bx1x2d1d1+d2d2+

50、d3d3+d4d4+x118/458/451/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 单纯形法单纯形法Simplex Method满意解满意解X(80/9，560/9)T，d3+200/9而而d20，与目标要，与目标要求相悖，还可以从图求相悖，还可以从图4-6说明这个结果是错误的说明这个结果是错误的例例4.7（2）是在原问题中作了部分变动后再求解，等价于第）是在原问题中作了