Chapter4目标规划目标规划GoalProgramming运筹学运筹学OperationsResearch4.1目标规划数学模型目标规划数学模型Mathematical Model of GP4.2目标规划的图解法目标规划的图解法The graphical method of GP4.3单纯形法单纯形法Simplex Method8/24/20244.1目标规划数学模型目标规划数学模型Mathematical Model of GP8/24/2024Ch4目标规划目标规划GoalProgramming Page 3 线性规划模型的特征是在满足一组约束条件下，寻线性规划模型的特征是在满足一组约束条件下，寻求一个目标的最优解（最大值或最小值）。求一个目标的最优解（最大值或最小值）。而而在现实生活中最优只是相对的，或者说没有绝对在现实生活中最优只是相对的，或者说没有绝对在现实生活中最优只是相对的，或者说没有绝对在现实生活中最优只是相对的，或者说没有绝对意义下的最优，只有相对意义下的满意。意义下的最优，只有相对意义下的满意。意义下的最优，只有相对意义下的满意。意义下的最优，只有相对意义下的满意。1978年诺贝尔经济学奖获得者年诺贝尔经济学奖获得者.西蒙西蒙(H.A.Simon-美美国卡内基国卡内基-梅隆大学梅隆大学,1916-)教授提出教授提出“满意行为模型满意行为模型要比最大化行为模型丰富得多要比最大化行为模型丰富得多”，否定了企业的决策，否定了企业的决策者是者是“经济人经济人”概念和概念和“最大化最大化”行为准则，提出了行为准则，提出了“管理人管理人”的概念和的概念和“令人满意令人满意”的行为准则，对现的行为准则，对现代企业管理的决策科学进行了开创性的研究代企业管理的决策科学进行了开创性的研究 4.1目标规划的数学模型目标规划的数学模型MathematicalModelofGP8/24/2024Ch4目标规划目标规划GoalProgramming Page 4 【例例4.】考虑用考虑用4种资源生产种资源生产3种产品的问题。资源消耗如表种产品的问题。资源消耗如表4-1所示。所示。x1、x2、x3分别为甲、乙、丙的产量。分别为甲、乙、丙的产量。使使企企业业在在计计划划期期内内总总利利润润最大的线性规划模型为：最大的线性规划模型为：产品产品资源资源甲甲乙乙丙丙现有资源现有资源设备设备A312200设备设备B224200材料材料C451360材料材料D235300利润利润（元（元/件）件）403050表表4-14.1.1引例引例4.1目标规划的数学模型目标规划的数学模型MathematicalModelofGP最优解：最优解：最优解：最优解：X（50，30，10）;Z3400。8/24/2024Ch4目标规划目标规划GoalProgramming Page 5 现现在在决决策策者者根根据据企企业业的的实实际际情情况况和和市市场场需需求求，需需要要重重新新制制定定经营目标，其目标的优先顺序是：经营目标，其目标的优先顺序是：（1 1）利润不少于）利润不少于32003200元；元；（2 2）产品甲与产品乙的产量比例尽量不超过）产品甲与产品乙的产量比例尽量不超过1.51.5；（3 3）提高产品丙的产量使之达到）提高产品丙的产量使之达到3030件；件；（4 4）设备加工能力不足可以加班）设备加工能力不足可以加班解决，能不加班最好不加班；解决，能不加班最好不加班；（5 5）受到资金的限制，只能使用）受到资金的限制，只能使用现有材料不能再购进。现有材料不能再购进。【解解】设甲、乙、丙产品的产量设甲、乙、丙产品的产量分别为分别为x1、x2、x3。如果按线性规划。如果按线性规划建模思路，最优解实质是求下列一建模思路，最优解实质是求下列一组不等式的解组不等式的解4.1目标规划的数学模型目标规划的数学模型MathematicalModelofGP8/24/2024Ch4目标规划目标规划GoalProgramming Page 6 通通过过计计算算不不等等式式无无解解，即即使使设设备备加加班班1010小小时时仍仍然然无无解。解。在在实实际际生生产产过过程程中中生生产产方方案案总总是是存存在在的的，无无解解只只能能说说明明在在现现有有资资源源条条件件下下，不不可可能能完完全全满满足足所所有有经经营营目目标。标。这这种种情情形形是是按按事事先先制制定定的的目目标标顺顺序序逐逐项项检检查查，尽尽可可能能使使得得结结果果达达到到预预定定目目标标，即即使使不不能能达达到到目目标标也也使使得得离离目目标标的的差差距距最最小小，这这就就是是目目标标规规划划的的求求解解思思路路，对对应的解称为满意解。应的解称为满意解。下面建立例下面建立例4.14.1的目标规划数学模型。的目标规划数学模型。4.1目标规划的数学模型目标规划的数学模型MathematicalModelofGP8/24/2024Ch4目标规划目标规划GoalProgramming Page 7 设设d为为未未达达到到目目标标值值的的差差值值，称称为为负负偏偏差差变变量量（negativedeviationvariable）。）。d +为为超超过过目目标标值值的的差差值值，称称为为正正偏偏差差变变量量（positivedeviationvariable）, d0、d0。设设d1未达到利润目标的差值未达到利润目标的差值,d1+为超过目标的差值。为超过目标的差值。当利润小于当利润小于3200时时,d1且且d10,有有40x1+30x2+50x3+d1=3200成立；成立；当利润大于当利润大于3200时，时，d1且且d1，有，有40x1+30x2+50x3d1+=3200成立；成立；当利润恰好等于当利润恰好等于3200时，时，d1=且且d1+=0,有有40x1+30x2+50x3=3200成立。成立。实实际际利利润润只只有有上上述述三三种种情情形形之之一一发发生生，因因而而可可以以将将三三个个等等式式写写成一个等式成一个等式40x1+30x2+50x3+d1d1+=32004.1目标规划的数学模型目标规划的数学模型MathematicalModelofGP8/24/2024Ch4目标规划目标规划GoalProgramming Page 8 （2）设）设d2、d2分别为未达到和超过产品比例要求的偏差分别为未达到和超过产品比例要求的偏差变量变量,则产量比例尽则产量比例尽量不超过量不超过1.5的数学表达式为的数学表达式为：（3）设设d3、d3分分别别为为产产品品丙丙的的产产量量未未达达到到和和超超过过30件件的的偏差变量，则产品丙的产量尽可能达到偏差变量，则产品丙的产量尽可能达到30件的数学表达式为：件的数学表达式为：（1）利润不少于）利润不少于3200理解为达到或超过理解为达到或超过3200，即使不能达到，即使不能达到也要尽可能接近也要尽可能接近3200,可以表达成目标函数可以表达成目标函数d1取最小值，则取最小值，则有有4.1目标规划的数学模型目标规划的数学模型MathematicalModelofGP8/24/2024Ch4目标规划目标规划GoalProgramming Page 9 （4）设设d4、d4+为为设设备备A的的使使用用时时间间偏偏差差变变量量,d5、d5+为为设设备备B的的使使用用时时间间偏偏差差变变量量，最最好好不不加加班班的的含含义义是是d4+和和d5+同同时时取取最最小小值值，等等价价于于d4+d5+取取最最小小值值，则则设设备备的的目目标标函函数数和和约束为：约束为：（5）材材料料不不能能购购进进表表示示不不允允许许有有正正偏偏差差，约约束束条条件件为为小小于于等于约束。等于约束。由由于于目目标标是是有有序序的的并并且且四四个个目目标标函函数数非非负负，因因此此目目标标函函数数可以表达成一个函数：可以表达成一个函数：4.1目标规划的数学模型目标规划的数学模型MathematicalModelofGP式式中中：Pj（j=1,2,3,4）称称为为目标的优先因子。目标的优先因子。第第一一目目标标优优于于第第二二目目标标，第第二二目目标标优优于于第第三三目目标标等等等等，其其含含义义是是按按P1,P2,Pn的的次次序序分分别求后面函数的最小值。别求后面函数的最小值。8/24/2024Ch4目标规划目标规划GoalProgramming Page 10 4.1目标规划的数学模型目标规划的数学模型MathematicalModelofGP该问题的目标规划数学模型为：该问题的目标规划数学模型为：该问题的目标规划数学模型为：该问题的目标规划数学模型为：（1）利利润润不不少少于于3200元；元；（2）产产品品甲甲与与产产品品乙乙的的产产量量比比例例尽尽量量不不超超过过1.5；（3）提提高高产产品品丙丙的的产产量使之达到量使之达到30件；件；（4）设设备备加加工工能能力力不不足足可可以以加加班班解解决决，能能不加班最好不加班；不加班最好不加班；（5）受受到到资资金金的的限限制制，只只能能使使用用现现有有材材料料不不能再购进。能再购进。8/24/2024Ch4目标规划目标规划GoalProgramming Page 11 约束约束实际实际偏差偏差目标目标1 1C1C132203220= =320032002 2C2C22 2= =0 03 3C3C33030= =30304 4C4C4164= =2002005 5C5C5216216= =2002006 6C6C6242242118=3603607 7C7C726626634=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目标规划的数学模型目标规划的数学模型MathematicalModelofGP8/24/2024Ch4目标规划目标规划GoalProgramming Page 12 （1）目目标标规规划划数数学学模模型型的的形形式式有有：线线性性模模型型、非非线线性性模模型型、整数模型、交互作用模型等；整数模型、交互作用模型等；（2）一一个个目目标标中中的的两两个个偏偏差差变变量量di、di至至少少一一个个等等于于零零，偏差变量向量的叉积等于零：偏差变量向量的叉积等于零：dd=0；（3）一一般般目目标标规规划划是是将将多多个个目目标标函函数数写写成成一一个个由由偏偏差差变变量量构构成成的的函函数数求求最最小小值值，按按多多个个目目标标的的重重要要性性，确确定定优优先先等等级级顺顺序序求求最小值；最小值；（4）按决策者的意愿，事先给定所要达到的目标值：）按决策者的意愿，事先给定所要达到的目标值：当期望结果不超过目标值时，目标函数求正偏差变量最小当期望结果不超过目标值时，目标函数求正偏差变量最小;当期望结果不低于目标值时，目标函数求负偏差变量最小当期望结果不低于目标值时，目标函数求负偏差变量最小;当当期期望望结结果果恰恰好好等等于于目目标标值值时时，目目标标函函数数求求正正负负偏偏差差变变量量之之和最小。和最小。4.1.2 4.1.2 4.1.2 4.1.2 目标规划的数学模型目标规划的数学模型目标规划的数学模型目标规划的数学模型4.1目标规划的数学模型目标规划的数学模型MathematicalModelofGP8/24/2024Ch4目标规划目标规划GoalProgramming Page 13 （5）由由目目标标构构成成的的约约束束称称为为目目标标约约束束，目目标标约约束束具具有有更更大大的的弹弹性性，允允许许结结果果与与所所制制定定的的目目标标值值存存在在正正或或负负的的偏偏差差。如如例例4.1中中的的5个个等等式式约约束束；如如果果决决策策者者要要求求结结果果一一定定不不能能有有正正或或负负的的偏偏差差，这种约束称为系统约束，如例这种约束称为系统约束，如例4.1的材料约束。的材料约束。（6）目目标标的的排排序序问问题题。多多个个目目标标之之间间有有相相互互冲冲突突时时，决决策策者者首首先先必必须须对对目目标标排排序序。排排序序的的方方法法有有两两两两比比较较法法、专专家家评评分分等等方方法，构造各目标的权系数，依据权系数的大小确定目标顺序。法，构造各目标的权系数，依据权系数的大小确定目标顺序。（7）合合理理的的确确定定目目标标数数。目目标标规规划划的的目目标标函函数数中中包包含含了了多多个个目目标标，决决策策者者对对于于具具有有相相同同重重要要性性的的目目标标可可以以合合并并为为一一个个目目标标，如如果果同同一一目目标标中中还还想想分分出出先先后后次次序序，可可以以赋赋予予不不同同的的权权系系数数，按按系系数数大大小小再再排排序序。例例如如，在在例例4.1中中要要求求设设备备B的的加加班班时时间间不不超超过过设设备备A的的时时间间，目目标标函函数数可可以以表表达达为为d42d5,表表示示在在d4、d5中中先求先求d4最小最小再求再求d5最小。最小。4.1目标规划的数学模型目标规划的数学模型MathematicalModelofGP8/24/2024Ch4目标规划目标规划GoalProgramming Page 14 （8 8）多目标决策问题。多目标决策研究的范围比）多目标决策问题。多目标决策研究的范围比较广泛，在决策中，可能同时要求多个目标达到最优。较广泛，在决策中，可能同时要求多个目标达到最优。例如，企业在对多个项目投资时期望收益率尽可能例如，企业在对多个项目投资时期望收益率尽可能最大，投资风险尽可能最小，属于多目标决策问题。最大，投资风险尽可能最小，属于多目标决策问题。本章的目标规划尽管包含有多个目标，但还是按单本章的目标规划尽管包含有多个目标，但还是按单个目标求偏差变量的最小值，目标函数中不含有决策个目标求偏差变量的最小值，目标函数中不含有决策变量，只是多目标决策的一种特殊情形。变量，只是多目标决策的一种特殊情形。本章不讨论多目标规划的求解方法，只给出本章不讨论多目标规划的求解方法，只给出WinQSBWinQSB软件求解线性多目标规划的操作步骤。软件求解线性多目标规划的操作步骤。4.1目标规划的数学模型目标规划的数学模型MathematicalModelofGP8/24/2024Ch4目标规划目标规划GoalProgramming Page 15 （9 9）目标规划的一般模型设）目标规划的一般模型设）目标规划的一般模型设）目标规划的一般模型设x xj j（j j=1,2,=1,2,n n）为决策变量为决策变量为决策变量为决策变量4.1目标规划的数学模型目标规划的数学模型MathematicalModelofGP式中：式中：pk为第为第k级优先因子级优先因子,k=1,2,K；wkl-,wkl+,为为分分别别赋赋予予第第l个个目目标标约约束束的的正正负负偏偏差差变变量量的权系数。的权系数。目标函数目标函数系统约束系统约束目标约束目标约束非负限制非负限制8/24/2024Ch4目标规划目标规划GoalProgramming Page 16 【例例4.2】某某企企业业集集团团计计划划用用1000万万元元对对下下属属5个个企企业业进进行行技技术术改改造造，各各企企业业单单位位的的投投资资额额已已知知，考考虑虑2种种市市场场需需求求变变化化、现现有有竞竞争争对对手手、替替代代品品的的威威胁胁等等影影响响收收益益的的4个个因因素素，技技术术改改造造完完成成后后预预测测单单位位投投资资收收益益率率(单单位位投投资资获获得得利利润润/单单位位投投资资额额)100)如如表表42所所示示集团制定的目标是：集团制定的目标是：（1）希望完成总投资额又不超过预算；）希望完成总投资额又不超过预算；（2）总期望收益率达到总投资的）总期望收益率达到总投资的30%；（3）投资风险尽可能最小；）投资风险尽可能最小；（4）保证企业）保证企业5的投资额占的投资额占20%左右左右集团应如何作出投资决策。集团应如何作出投资决策。4.1目标规划的数学模型目标规划的数学模型MathematicalModelofGP8/24/2024Ch4目标规划目标规划GoalProgramming Page 17 企业企业1企业企业2企业企业3企业企业4企业企业5单位投资额单位投资额( (万元万元) )1210151320单位单位投资投资收益收益率预率预测测rij市场需求市场需求1 14.3255.845.26.56市场需求市场需求2 23.523.045.084.26.24现有竞争对手现有竞争对手3.162.23.563.284.08替代品的威胁替代品的威胁2.243.122.62.23.24期望期望(平均平均)收益率收益率3.313.344.273.725.03表表表表4 4 4 42 2 2 24.1目标规划的数学模型目标规划的数学模型MathematicalModelofGP【解解】设设xj（j=1,2,5）为集团对第为集团对第j 个企业投资的单位数。个企业投资的单位数。（1）总投资约束：）总投资约束：8/24/2024Ch4目标规划目标规划GoalProgramming Page 18 4.1目标规划的数学模型目标规划的数学模型MathematicalModelofGP（2）期望利润率约束：）期望利润率约束：整理得整理得(3）投）投资风险约束束投投资风险值的的大大小小一一般般用用期期望望收收益益率率的的方方差差表表示示，但但方方差差是是x的的非非线性性函函数数这里里用用离离差差（rijE(rj)）近近似似表表示示风险值，例例如如，集集团投投资5个企个企业后后对于市于市场需求需求变化第一情形的化第一情形的风险是：是：则则4种因素风险最小的目标函数为：种因素风险最小的目标函数为：8/24/2024Ch4目标规划目标规划GoalProgramming Page 19 （4）企业）企业5占占20%的投资的目标函数为：的投资的目标函数为：即：即：4.1目标规划的数学模型目标规划的数学模型MathematicalModelofGP约束条件为：约束条件为：约束条件：约束条件：8/24/2024Ch4目标规划目标规划GoalProgramming Page 20 4.1目标规划的数学模型目标规划的数学模型MathematicalModelofGP根据目标重要性依次写出目标函数，整理后得到投资决策的根据目标重要性依次写出目标函数，整理后得到投资决策的目标规划数学模型：目标规划数学模型：8/24/2024Ch4目标规划目标规划GoalProgramming Page 21 【例例4.3】车车间间计计划划生生产产I、II两两种种产产品品，每每种种产产品品均均需需经经过过A、B两两道道工工序序加加工工工工艺艺资资料料如如表表4-3所所示。示。产品产品工序工序甲甲乙乙每天加工每天加工能力能力(小时小时)A22120B12100C2.20.890售价售价(元元/件件)5070利润利润(元元/件件)108（1）车车间间如如何何安安排排生生产产计计划划，使使产产值值和和利利润润都都尽尽可可能能高高；（2）如如果果认认为为利利润润比比产产值值重重要，怎样决策。要，怎样决策。表表434.1目标规划的数学模型目标规划的数学模型MathematicalModelofGP【解解】设设x1、x2分分别别为为产产品品甲甲和和产产品品乙乙的的日日产产量量，得到线性多目标规划模型：得到线性多目标规划模型：8/24/2024Ch4目标规划目标规划GoalProgramming Page 22 （1）将模型化为目标规划问题）将模型化为目标规划问题首先，通过分别求产值最大和利润最大的线性规划最优解首先，通过分别求产值最大和利润最大的线性规划最优解产值最大的最优解：产值最大的最优解：X(1)（20，40），），Z13800利润最大的最优解：利润最大的最优解：X(2)（30，30），），Z2540目标确定为产值和利润尽可能达到目标确定为产值和利润尽可能达到3800和和540，得到目标规划，得到目标规划数学模型：数学模型：4.1目标规划的数学模型目标规划的数学模型MathematicalModelofGP8/24/2024Ch4目标规划目标规划GoalProgramming Page 23 4.1目标规划的数学模型目标规划的数学模型MathematicalModelofGP（2）给）给d2赋予一个比赋予一个比d1的系数大的权系数的系数大的权系数,如如minZd12d2，约约束束条条件件不不变变。权权系系数数的的大大小小依依据据重重要要程程度度给给定定，或或者者根根据据同同一一优优先先级级的的偏偏差差变变量量的的关关系系给给定定，例例如如，当当利利润润d2减减少少一一个个单单位位时时，产产值值d1减少减少3个单位，则赋予个单位，则赋予d2权系数权系数3，则目标函数为，则目标函数为8/24/2024Ch4目标规划目标规划GoalProgramming Page 24 本节介绍了如何建立目标规划的数学模型及有关概念本节介绍了如何建立目标规划的数学模型及有关概念1.1.目标规划由哪些要素构成，与线性规划有哪些不同目标规划由哪些要素构成，与线性规划有哪些不同之处之处2.2.偏差变量的含义及其作用偏差变量的含义及其作用3.3.目标函数的表达方法目标函数的表达方法4.4.优先级别的含义优先级别的含义作业：教材作业：教材P90 1 P90 1 ，2 2，4 44.1目标规划的数学模型目标规划的数学模型MathematicalModelofGP下一节：目标规划的图解法下一节：目标规划的图解法8/24/20244.2目标规划的图解法目标规划的图解法The graphical method of GP8/24/2024Ch4目标规划目标规划GoalProgramming Page 26 4.2目标规划的图解法目标规划的图解法ThegraphicalmethodofGP当当目目标标规规划划模模型型中中只只含含两两个个决决策策变变量量（不不包包含含偏偏差差变变量量）时时，可以用图解法求出满意解可以用图解法求出满意解【例例4.4】企业计划生产企业计划生产I 、 II 两种产品，这些产品需要使用两两种产品，这些产品需要使用两种材料，要在两种不同设备上加工工艺资料如表种材料，要在两种不同设备上加工工艺资料如表44所示所示产品品资源资源产品甲产品甲产品乙产品乙现有资源现有资源材料材料I3012(kg)材料材料II0414(kg)设备设备A2212(h)设备设备B5315(h)产品利润产品利润(元元/件件)2040表表448/24/2024Ch4目标规划目标规划GoalProgramming Page 27 【解解】设设x1、x2分别为产品甲和产品乙的产量，目标规划数学分别为产品甲和产品乙的产量，目标规划数学模型为：模型为：企业怎样安排生产计划，尽可能满足下列目标：企业怎样安排生产计划，尽可能满足下列目标：(1)力求使利润指标不低于力求使利润指标不低于80元元(2)考虑到市场需求考虑到市场需求,、II两种产品的生产量需保持两种产品的生产量需保持1:1的比例的比例(3)设备设备A既要求充分利用，又尽可能不加班既要求充分利用，又尽可能不加班(4)设备设备B必要时可以加班，但加班时间尽可能少必要时可以加班，但加班时间尽可能少(5)材料不能超用。材料不能超用。4.2目标规划的图解法目标规划的图解法ThegraphicalmethodofGP8/24/2024(2)(1)(3)(4 )x2x1(6)(5)o464622图图41ABC满意解满意解C(3,3)满意解满意解X(3,3)8/24/2024(3)x1x22040608010020406080100(2)(1)(4)图图53BC满意解是线段满意解是线段上任意点，端点的上任意点，端点的解是解是B(100/3，80/3)，C(60，0)决策者根据实际情形进行二次选择决策者根据实际情形进行二次选择A8/24/2024(3)x1x22040608010020406080100(2)(1)(4)图图53BC满意解是点满意解是点B，X=(100/3，80/3)A8/24/2024(3)x1x22040608010020406080100(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/98/24/2024Ch4目标规划目标规划GoalProgramming Page 32 本节介绍了目标规划的图解法本节介绍了目标规划的图解法1.画出系统约束和目标约束直线画出系统约束和目标约束直线2.标明偏差变量大于零的变量标明偏差变量大于零的变量X的取值区域的取值区域3.按优先次序分别求各目标的最小值按优先次序分别求各目标的最小值作业作业:教材教材P91T3下一节：目标规划的单纯形法下一节：目标规划的单纯形法4.2目标规划的图解法目标规划的图解法ThegraphicalmethodofGP8/24/20244.3单纯形法单纯形法SimplexMethod8/24/2024Ch4目标规划目标规划GoalProgramming Page 34 单单纯纯形形法法求求解解目目标标规规划划可可参参照照第第一一章章的的步步骤骤，只只是是目标规划的检验要按优先级顺序逐级进行，不同的是：目标规划的检验要按优先级顺序逐级进行，不同的是：（1）首首先先使使得得检检验验数数中中P1的的系系数数非非负负，再再使使得得P2的的系数非负，依次进行；系数非负，依次进行；（2）当当P1、P2、Pk对对应应的的系系数数全全部部非非负负时时得得到到满意解；满意解；（3）如如果果P1，Pi行行系系数数非非负负，而而Pi+1行行存存在在负负数数，并并且且负负数数所所在在列列上上面面P1，Pi行行中中存存在在正正数数时时，得到满意解，计算结束得到满意解，计算结束4.3单纯形法单纯形法SimplexMethod8/24/2024Ch4目标规划目标规划GoalProgramming Page 35 【例例4.64.6】用单纯形法求解下述目标规划问题用单纯形法求解下述目标规划问题【解解】以以d1、d2、d3为为基基变变量量，求求出出检检验验数数，将将检检验验数数中中优优先先因因子子分分离离出出来来，每每一一优优先先级级做做一一行行，列列出出初始单纯形表初始单纯形表4-54.3单纯形法单纯形法SimplexMethod8/24/2024Ch4目标规划目标规划GoalProgramming Page 36 Cj00P100P1P20bCB基基x1x2d1d1+d2d2+d3d3+P1d112110000500d22100110040P2d32200001180CjZjP1120101000P2220000010表表454.3单纯形法单纯形法SimplexMethod8/24/2024Ch4目标规划目标规划GoalProgramming Page 37 表表45中中，P1行行中中(2)最最小小，则则x2进进基基，求求最最小小比比值值易易知知d1出出基基，将将第第二二列列主主元元素素化化为为1，其其余余元元素素化化为为零零，得到表得到表4-6Cj00P100P1P20bCB基基x1x2d1d1+d2d2+d3d3+0x21/211/21/20000250d23/2001/2110015P2d31001001130CjZjP1001001000P2101100010表表464.3单纯形法单纯形法SimplexMethod8/24/2024Ch4目标规划目标规划GoalProgramming Page 38 表表4-6中中P1行行全全部部检检验验数数非非负负，表表明明第第一一目目标标已已经经得得到到优优化化P2行行存存在在负负数数，x1的的检检验验数数为为P20，选选x1进进基基（也也可可以以选选d1+进进基），则基），则d3出基，迭代得到表出基，迭代得到表4-7Cj00P100P1P20bCB基基x1x2d1d1+d2d2+d3d3+0x2012/3 2/301/300200x11001/32/300010P2d30002/302/31120CjZjP100100100P2002/3-2/32/3 -2/3014.3单纯形法单纯形法SimplexMethod 表表4-78/24/2024Ch4目标规划目标规划GoalProgramming Page 39 在在表表4-7中中，P1行行的的系系数数全全部部非非负负，P2行行存存在在负负数数，d1+的的检检验验数数2/3P20,所有检验数非负，得到满意解所有检验数非负，得到满意解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-134.3单纯形法单纯形法SimplexMethod求满意解求满意解8/24/2024Ch4目标规划目标规划GoalProgramming Page 41 Cj00P100P1P2P20P3bCB基基x1x2d1d1+d2d2+d3d3+d4d4+P1d1105114000d27811560P2d322111200d412.511100CjZjP110511P2222P31表表4-94.3单纯形法单纯形法SimplexMethod8/24/2024Ch4目标规划目标规划GoalProgramming Page 42 Cj00P100P1P2P20P3bCB基基x1x2d1d1+d2d2+d3d3+d4d4+0x111/21/101/10400d29/2-7/107/1011280P2d311/51/511400d42-1/101/101160CjZjP111P2-11/51/52P31表表4-104.3单纯形法单纯形法SimplexMethod8/24/2024Ch4目标规划目标规划GoalProgramming Page 43 Cj00P100P1P2P20P3bCB基基x1x2d1d1+d2d2+d3d3+d4d4+0x115/405/401/41/4250d2-19/4019/40119/49/4145P2d33/203/20111/21/2100x211/201/201/21/230CjZjP11P23/203/2021/21/2P31表表4114.3单纯形法单纯形法SimplexMethod8/24/2024Ch4目标规划目标规划GoalProgramming Page 44 Cj00P100P1P2P20P3bCB基基x1x2d1d1+d2d2+d3d3+d4d4+0x115/65/62/32/3100/30d21119/619/62/32/3340/30d1+1120/320/310/310/3200/30x211/31/32/32/380/3CjZjP11P211P31表表4-124.3单纯形法单纯形法SimplexMethod8/24/2024Ch4目标规划目标规划GoalProgramming Page 45 Cj00P100P1P2P20P3bCB基基x1x2d1d1+d2d2+d3d3+d4d4+0x1111/21/2600d21117/27/21400d1+511552000d43/21/21/213/440CjZjP11P211P31表表4134.3单纯形法单纯形法SimplexMethod8/24/2024Ch4目标规划目标规划GoalProgramming Page 46 （2）如果将目标函数）如果将目标函数改写成改写成以表以表4-124-12为基础，计算过程见表为基础，计算过程见表4-144-144-164-16表表4-14Cj00P1P1P300P20P4bCB基基x1x2d1d1+d2d2+d3d3+d4d4+0x115/65/62/32/3100/3P3d211-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单纯形法单纯形法SimplexMethod8/24/2024Ch4目标规划目标规划GoalProgramming Page 47 Cj00P1P1P300P20P4bCB基基x1x2d1d1+d2d2+d3d3+d4d4+0x111/81/81/41/425P3d219/4019/401-19/49/4145 0d33/203/201-11/21/2100x211/201/201/21/230CjZjP111P21P319/4019/4019/49/4P41表表4-154.3单纯形法单纯形法SimplexMethod8/24/2024Ch4目标规划目标规划GoalProgramming Page 48 Cj00P1P1P300P20P4bCB基基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满意解满意解X(20，40)T，对应于图，对应于图4-6中点中点A(20,40),Z120，然而该满意解是错误的，然而该满意解是错误的，正确的算法见表正确的算法见表4-17。4.3单纯形法单纯形法SimplexMethod求解，单纯形法计算如表求解，单纯形法计算如表4-17所示所示在（在（2）中仍然按）中仍然按8/24/2024Ch4目标规划目标规划GoalProgramming Page 49 00P1P1P2002P20P3bx1x2d1d1+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单纯形法单纯形法SimplexMethod8/24/202400P1P1P2002P20P3bx1x2d1d1+d2d2+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最终表：最终表：8/24/2024Ch4目标规划目标规划GoalProgramming Page 51 4.3单纯形法单纯形法SimplexMethod满满意意解解X(80/9，560/9)T，d3+200/9而而d20，d4+580/9，Z108.88，目标函数值比表，目标函数值比表4-16的结果小。的结果小。图图解解法法时时如如果果按按权权系系数数大大小小顺顺序序求求最最小小值值就就很很容容易易得得到表到表4-16所示错误的解。所示错误的解。例例4.7（2）是是在在原原问问题题中中作作了了部部分分变变动动后后再再求求解解，等等价于第二章的灵敏度分析，求解原理基本相同价于第二章的灵敏度分析，求解原理基本相同由由表表4-17的的计计算算可可以以看看出出，同同一一级级目目标标中中有有不不同同权权系系数时，不是按大小顺序求最小，而是求加权最小。数时，不是按大小顺序求最小，而是求加权最小。8/24/2024Ch4目标规划目标规划GoalProgramming Page 52 TheEndofChapter4目标规划的单纯形法与线性规划比较主要有两点不同。目标规划的单纯形法与线性规划比较主要有两点不同。第一，目标规划是按优先次序顺序求解，逐个满足最优（检第一，目标规划是按优先次序顺序求解，逐个满足最优（检验数大于等于零）；验数大于等于零）；第二，不一定所有检验数都能满足大于等于零，如果某个检第二，不一定所有检验数都能满足大于等于零，如果某个检验数小于零，所在列存在检验数大于零时，则认为得到满意解。验数小于零，所在列存在检验数大于零时，则认为得到满意解。计算方法和基本原理与线性规划类似。计算方法和基本原理与线性规划类似。作业：作业：P91T3、54.3单纯形法单纯形法SimplexMethod8/24/2024Ch4目标规划目标规划GoalProgramming Page 53 8/24/2024Ch4目标规划目标规划GoalProgramming Page 54 习题习题4.3(1)(3)x110203040501020304050(2)(1)x2习题答案习题答案A(50/3,20/3)B(30,0)满意解在意解在线段段上上8/24/2024Ch4目标规划目标规划GoalProgramming Page 55 习题习题4.3(2)(3)x11212(2)(1)x2习题答案习题答案满意解满意解X=(2,0)8/24/2024Ch4目标规划目标规划GoalProgramming Page 56 习题习题4.3(3)(3)x110203040501020304050(2)(1)x2习题答案习题答案满意解：满意解：X=(50,10)60(4)(50,10)608/24/2024Ch4目标规划目标规划GoalProgramming Page 57 习题习题4.3(4)(3)x1123451234(2)(1)x2习题答案习题答案满意解：满意解：X=(0,3)6(4)(0,3)8/24/2024Ch4目标规划目标规划GoalProgramming Page 58 习题习题4.5(1)(3)x1123451234(2)(1)x2习题答案习题答案满意解：满意解：X(13/2,5/4)6(4)9(13/2,5/4)8/24/2024Ch4目标规划目标规划GoalProgramming Page 59 习题习题4.5(2)(a)(3)x1123451234(2)(1)x2习题答案习题答案满意解：满意解：X(5,1/2)6(4)9(5,1/2)8/24/2024Ch4目标规划目标规划GoalProgramming Page 60 习题习题4.5(2)(b)(3)x1123451234(2)(1)x2习题答案习题答案满意解在线段满意解在线段上上6(4)9AB8/24/2024Ch4目标规划目标规划GoalProgramming Page 61 (3)x1123451234(2)(1)x2习题答案习题答案满意解在满意解在B点（点（13/2，5/4）6(4)9AB习题习题4.5(2)(b)8/24/2024Ch4目标规划目标规划GoalProgramming Page 62 (3)x1123451234(2)(1)x2习题答案习题答案满意解在满意解在A点（点（5，2）6(4)9AB习题习题4.5(2)(b)8/24/2024