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

运筹学运运运运 筹筹筹筹 学学学学Operations ResearchOperations ResearchChapter 4  目标规划目标规划Goal Programming 运筹学运筹学Operations Research4.1  目标规划数学模型目标规划数学模型    Mathematical Model of GP4.2  目标规划的图解法目标规划的图解法  The graphical method of GP4.3  单纯形法单纯形法  Simplex Method4.1  目标规划数学模型目标规划数学模型Mathematical Model of GP     线性规划模型的特征是在满足一组约束条件下，寻求一个目线性规划模型的特征是在满足一组约束条件下，寻求一个目标的最优解（最大值或最小值）标的最优解（最大值或最小值）    而在现实生活中最优只是相对的，或者说没有绝对意义下的最而在现实生活中最优只是相对的，或者说没有绝对意义下的最优，只有相对意义下的满意优，只有相对意义下的满意        1978年诺贝尔经济学奖获得者年诺贝尔经济学奖获得者.西蒙西蒙(H.A.Simon-美国卡内基美国卡内基-梅隆大学梅隆大学,1916-)教授提出教授提出“满意行为模型要比最大化行为模型满意行为模型要比最大化行为模型丰富得多丰富得多”，否定了企业的决策者是，否定了企业的决策者是“经济人经济人”概念和概念和“最大最大化化”行为准则，提出了行为准则，提出了“管理人管理人”的概念和的概念和“令人满意令人满意”的行的行为准则，对现代企业管理的决策科学进行了开创性的研究为准则，对现代企业管理的决策科学进行了开创性的研究 4.1目标规划的数学模型目标规划的数学模型Mathematical Model of GP【【例例4.１１】】考虑例考虑例1.1．资源消耗如表．资源消耗如表4-1所示。

所示x1、、x2、、x3分分别为甲、乙、丙的产量别为甲、乙、丙的产量使企业在计划期内总利润最大的线性规划模型为：使企业在计划期内总利润最大的线性规划模型为： 产品产品 资源资源甲甲乙乙丙丙现有资源现有资源设备设备A312200设备设备B224200材料材料C451360材料材料D235300利润（元利润（元/件）件）403050表表4-14.1.1 引例引例4.1目标规划的数学模型目标规划的数学模型Mathematical Model of GP最优解最优解X＝（＝（50，，30，，10），），Z＝＝34004.1目标规划的数学模型目标规划的数学模型Mathematical Model of GP 现在决策者根据企业的实际情况和市场需求，需要重新制现在决策者根据企业的实际情况和市场需求，需要重新制定经营目标，其目标的优先顺序是：定经营目标，其目标的优先顺序是：（（1）利润不少于）利润不少于3200元元（（2）产品甲与产品乙的产量比例尽量不超过）产品甲与产品乙的产量比例尽量不超过1.5（（3）提高产品丙的产量使之达到）提高产品丙的产量使之达到30件件（（4）设备加工能力不足可以加班解决，能不加班最好不加班）设备加工能力不足可以加班解决，能不加班最好不加班（（5）受到资金的限制，只能使用现有材料不能再购进）受到资金的限制，只能使用现有材料不能再购进【【解解】】 设甲、乙、丙产品的产量分别为设甲、乙、丙产品的产量分别为x1、、x2、、x3。

如果按线如果按线性规划建模思路，最优解实质是求下列一组不等式的解性规划建模思路，最优解实质是求下列一组不等式的解4.1目标规划的数学模型目标规划的数学模型Mathematical Model of GP通过计算不等式无解，即使设备加班通过计算不等式无解，即使设备加班10小时仍然无解．在实小时仍然无解．在实际生产过程中生产方案总是存在的，无解只能说明在现有资际生产过程中生产方案总是存在的，无解只能说明在现有资源条件下，不可能完全满足所有经营目标．源条件下，不可能完全满足所有经营目标．这种情形是按事先制定的目标顺序逐项检查，尽可能使得结果这种情形是按事先制定的目标顺序逐项检查，尽可能使得结果达到预定目标，即使不能达到目标也使得离目标的差距最小，达到预定目标，即使不能达到目标也使得离目标的差距最小，这就是目标规划的求解思路，对应的解称为满意解．下面建立这就是目标规划的求解思路，对应的解称为满意解．下面建立例例4.1的目标规划数学模型．的目标规划数学模型． 4.1目标规划的数学模型目标规划的数学模型Mathematical Model of GP设设d－－为未达到目标值的差值，称为负偏差变量（为未达到目标值的差值，称为负偏差变量（negative deviation variable））d+为超过目标值的差值，称为正偏差变量为超过目标值的差值，称为正偏差变量（（positive deviation variable））, d－－≥0、、d＋＋≥0．．设设d1-未达到利润目标的差值未达到利润目标的差值, d1+ 为超过目标的差值为超过目标的差值当利润小于当利润小于3200时时,d1－－＞０且＞０且d1＋＋＝＝0,有有40x1+30x2+50x3+d1－－=3200成立成立当利润大于当利润大于3200时，时，d1＋＋＞０且＞０且d1－－＝０，有＝０，有40x1+30x2+50x3-d1+=3200成立成立当利润恰好等于当利润恰好等于3200时，时，d1－－=０且０且d1+=0,有有40x1+30x2+50x3=3200成立成立实际利润只有上述三种情形之一发生，因而可以将三个等式写成一实际利润只有上述三种情形之一发生，因而可以将三个等式写成一个等式　　　个等式　　　40x1+30x2+50x3+d1－－－－d1+=32004.1目标规划的数学模型目标规划的数学模型Mathematical Model of GP（（2）设）设                  分别为未达到和超过产品比例要求的偏差变分别为未达到和超过产品比例要求的偏差变量量,则产量比例尽则产量比例尽 量不超过量不超过1.5的数学表达式为的数学表达式为：  （（3）设）设d3ˉ、、d３３＋＋分别为品丙的产量未达到和超过分别为品丙的产量未达到和超过30件的偏差件的偏差变量，则产量丙的产量尽可能达到变量，则产量丙的产量尽可能达到30件的数学表达式为：件的数学表达式为： 利润不少于利润不少于3200理解为达到或超过理解为达到或超过3200，即使不能达到也要尽，即使不能达到也要尽可能接近可能接近3200,可以表达成目标函数｛可以表达成目标函数｛d1－－｝取最小值，则有｝取最小值，则有4.1目标规划的数学模型目标规划的数学模型Mathematical Model of GP（（4）） 设设d4ˉ 、、d4+为设备为设备A的使用时间偏差变量的使用时间偏差变量,  d5ˉ、、d5+为设备为设备B的使用时间偏差变量，最好不加班的含义是的使用时间偏差变量，最好不加班的含义是 d4+ 和和d5+同时取最同时取最小值，等价小值，等价 于于d4+ + d5+取最小值，则设备的目标函数和约束为：取最小值，则设备的目标函数和约束为：  （（5）材料不能购进表示不允许有正偏差，约束条件为小于等于）材料不能购进表示不允许有正偏差，约束条件为小于等于约束．约束．由于目标是有序的并且四个目标函数非负，因此目标函数可以由于目标是有序的并且四个目标函数非负，因此目标函数可以表达成一个函数：表达成一个函数：4.1目标规划的数学模型目标规划的数学模型Mathematical Model of GP式中：式中：Pj（（j=1,2,3,4）称为目标的优先因子，第一目标优于第二）称为目标的优先因子，第一目标优于第二目标，第二目标优于第三目标等等，其含义是按目标，第二目标优于第三目标等等，其含义是按P1、、P2、、…的次的次序分别求后面函数的最小值序分别求后面函数的最小值.则问题的目标规划数学模型为：则问题的目标规划数学模型为：4.1目标规划的数学模型目标规划的数学模型Mathematical Model of GP约束约束实际实际 偏差偏差目标目标1 1 C1C132203220= =320032002 2 C2C2－－2 2= =0 03 3 C3C33030= =30304 4 C4C4164= =2002005 5 C5C5216216= =2002006 6 C6C6242242－－118<=<=3603607 7 C7C7266266－－34<=<=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目标规划的数学模型目标规划的数学模型Mathematical Model of GP（（1）目标规划数学模型的形式有：线性模型、非线性模型、）目标规划数学模型的形式有：线性模型、非线性模型、整数模型、交互作用模型等整数模型、交互作用模型等（（2）一个目标中的两个偏差变量）一个目标中的两个偏差变量di-、、 di+至少一个等于零，偏至少一个等于零，偏差变量向量的叉积等于零：差变量向量的叉积等于零：d－－×d＋＋=0     （（3）一般目标规划是将多个目标函数写成一个由偏差变量构）一般目标规划是将多个目标函数写成一个由偏差变量构成的函数求最小值，按多个目标的重要性，确定优先等级，顺成的函数求最小值，按多个目标的重要性，确定优先等级，顺序求最小值序求最小值  （（4）按决策者的意愿，事先给定所要达到的目标值）按决策者的意愿，事先给定所要达到的目标值当期望结果不超过目标值时，目标函数求正偏差变量最小当期望结果不超过目标值时，目标函数求正偏差变量最小;当期望结果不低于目标值时，目标函数求负偏差变量最小当期望结果不低于目标值时，目标函数求负偏差变量最小;当期望结果恰好等于目标值时，目标函数求正负偏差变量之和最当期望结果恰好等于目标值时，目标函数求正负偏差变量之和最小小4.1.2 数学模型数学模型4.1目标规划的数学模型目标规划的数学模型Mathematical Model of GP（（5）由目标构成的约束称为目标约束，目标约束具有更大的弹）由目标构成的约束称为目标约束，目标约束具有更大的弹性，允许结果与所制定的目标值存在正或负的偏差，如例性，允许结果与所制定的目标值存在正或负的偏差，如例4.1中的中的5个等式约束；如果决策者要求结果一定不能有正或负的偏差，个等式约束；如果决策者要求结果一定不能有正或负的偏差，这种约束称为系统约束，如例这种约束称为系统约束，如例4.1的材料约束；的材料约束；（（6）目标的排序问题。

多个目标之间有相互冲突时，决策者首）目标的排序问题多个目标之间有相互冲突时，决策者首先必须对目标排序排序的方法有两两比较法、专家评分等方先必须对目标排序排序的方法有两两比较法、专家评分等方法，构造各目标的权系数，依据权系数的大小确定目标顺序；法，构造各目标的权系数，依据权系数的大小确定目标顺序；（（7）合理的确定目标数目标规划的目标函数中包含了多个目）合理的确定目标数目标规划的目标函数中包含了多个目标，决策者对于具有相同重要性的目标可以合并为一个目标，标，决策者对于具有相同重要性的目标可以合并为一个目标，如果同一目标中还想分出先后次序，可以赋予不同的权系数，如果同一目标中还想分出先后次序，可以赋予不同的权系数，按系数大小再排序例如，在例按系数大小再排序例如，在例4.1中要求设备中要求设备B的加班时间不的加班时间不超过设备超过设备A的时间，目标函数可以表达为的时间，目标函数可以表达为              ,表示在表示在中先求中先求       最小再求最小再求      最小 4.1目标规划的数学模型目标规划的数学模型Mathematical Model of GP（（8）多目标决策问题．多目标决策研究的范围比较广泛，在）多目标决策问题．多目标决策研究的范围比较广泛，在决策中，可能同时要求多个目标达到最优．例如，企业在对多决策中，可能同时要求多个目标达到最优．例如，企业在对多个项目投资时期望收益率尽可能最大，投资风险尽可能最小，个项目投资时期望收益率尽可能最大，投资风险尽可能最小，属于多目标决策问题，本章的目标规划尽管包含有多个目标，属于多目标决策问题，本章的目标规划尽管包含有多个目标，但还是按单个目标求偏差变量的最小值，目标函数中不含有决但还是按单个目标求偏差变量的最小值，目标函数中不含有决策变量，目标规划只是多目标决策的一种特殊情形．本章不讨策变量，目标规划只是多目标决策的一种特殊情形．本章不讨论多目标规划的求解方法，只给出论多目标规划的求解方法，只给出WinQSB软件求解线性多目软件求解线性多目标规划的操作步骤，参看例标规划的操作步骤，参看例4.3和和4.9．．4.1目标规划的数学模型目标规划的数学模型Mathematical Model of GP（（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）为目标约束）为目标约束【【例例4.2】】某企业集团计划用某企业集团计划用1000万元对下属万元对下属5个企业进行技术个企业进行技术改造，各企业单位的投资额已知，考虑改造，各企业单位的投资额已知，考虑2种市场需求变化、现有种市场需求变化、现有竞争对手、替代品的威胁等影响收益的竞争对手、替代品的威胁等影响收益的4个因素，技术改造完成个因素，技术改造完成后预测单位投资收益率后预测单位投资收益率(（单位投资获得利润（单位投资获得利润/单位投资额）单位投资额）×100％％)如表如表4－－2所示．所示．4.1目标规划的数学模型目标规划的数学模型Mathematical 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.26.24现有竞争对手现有竞争对手3.162.23.563.284.08替代品的威胁替代品的威胁2.243.122.62.23.24期望期望(平均平均)收益率％收益率％3.313.344.273.725.03表表4－－24.1目标规划的数学模型目标规划的数学模型Mathematical Model of GP【【解解】】设设xj（（j=1,2,…,5）为集团对第）为集团对第 j 个企业投资的单位数．个企业投资的单位数．（（1）总投资约束：）总投资约束：4.1目标规划的数学模型目标规划的数学模型Mathematical Model of GP（（2）期望利润率约束：）期望利润率约束：整理得整理得（（4）企业）企业5占占20%的投资的目标函数为的投资的目标函数为                    ,约束条件约束条件即即4.1目标规划的数学模型目标规划的数学模型Mathematical Model of GP(3）投资风险约束．投资风险值的大小一般用期望收益率的方）投资风险约束．投资风险值的大小一般用期望收益率的方差表示，但方差是差表示，但方差是x的非线性函数．这里用离差（的非线性函数．这里用离差（rij－－E(rj)）近）近似表示风险值，例如，集团投资似表示风险值，例如，集团投资5个企业后对于市场需求变化第个企业后对于市场需求变化第一情形的风险是：一情形的风险是：                                                                           则则4种因素风险最小的目标函数为：种因素风险最小的目标函数为：                      ，约束条件为，约束条件为4.1目标规划的数学模型目标规划的数学模型Mathematical Model of GP根据目标重要性依次写出目标函数，整理后得到投资决策的根据目标重要性依次写出目标函数，整理后得到投资决策的目标规划数学模型：目标规划数学模型：【【例例4.3】】车间计划生产车间计划生产I、、II 两种产品，每种产品均需经过两种产品，每种产品均需经过A、、B两道工序加工．工艺资料如表两道工序加工．工艺资料如表4－－3所示．所示． 产品产品工序工序产品甲产品甲产品乙产品乙每天加工能力每天加工能力(小时小时)A22120B12100C2.20.890产品售价产品售价(元元/件件)5070产品利润产品利润(元元/件件)108（（1）车间如何安排生产计划，使产值和利润都尽可能高）车间如何安排生产计划，使产值和利润都尽可能高（（2）如果认为利润比产值重要，怎样决策）如果认为利润比产值重要，怎样决策表表4－－34.1目标规划的数学模型目标规划的数学模型Mathematical Model of GP【【解解】】设设x1、、x2分别为产品甲和产品乙的日产量，得到线性多分别为产品甲和产品乙的日产量，得到线性多目标规划模型：目标规划模型：4.1目标规划的数学模型目标规划的数学模型Mathematical Model of GP（（1）将模型化为目标规划问题．首先，通过分别求产值最大）将模型化为目标规划问题．首先，通过分别求产值最大和利润最大的线性规划最优解．和利润最大的线性规划最优解．产值最大的最优解：产值最大的最优解：X(1)＝（＝（20，，40），），Z1＝＝3800利润最大的最优解：利润最大的最优解：X (2) ＝（＝（30，，30），），Z2＝＝540目标确定为产值和利润尽可能达到目标确定为产值和利润尽可能达到3800和和540，得到目标规划，得到目标规划数学模型：数学模型：4.1目标规划的数学模型目标规划的数学模型Mathematical Model of GP．4.1目标规划的数学模型目标规划的数学模型Mathematical Model of GP,等价于等价于（（2）给）给 d2-  赋予一个比赋予一个比d1-的系数大的权系数的系数大的权系数,如如                                       ，约束条件不变，约束条件不变.权系数的大小依据重要权系数的大小依据重要程度给定，或者根据同一优先级的偏差变量的关系给定，例如，程度给定，或者根据同一优先级的偏差变量的关系给定，例如，当利润当利润d2-减少一个单位时，产值减少一个单位时，产值d1-减少减少3个单位，则赋予个单位，则赋予d2-权权系数系数3，则目标函数为，则目标函数为 本节介绍了如何建立目标规划的数学模型及有关概念本节介绍了如何建立目标规划的数学模型及有关概念1.目标规划由哪些要素构成，与线性规划有哪些不同之处目标规划由哪些要素构成，与线性规划有哪些不同之处2.偏差变量的含义及其作用偏差变量的含义及其作用3.目标函数的表达方法目标函数的表达方法4.优先级别的含义优先级别的含义4.1目标规划的数学模型目标规划的数学模型Mathematical Model of GP4.2  目标规划的图解法目标规划的图解法The graphical method of GP4.2目标规划的图解法目标规划的图解法The graphical method of GP当目标规划模型中只含两个决策变量（不包含偏差变量）时，当目标规划模型中只含两个决策变量（不包含偏差变量）时，可以用图解法求出满意解．可以用图解法求出满意解．【【例例4.4】】企业计划生产企业计划生产I 、、 II 两种产品，这些产品需要使用两种产品，这些产品需要使用两种材料，要在两种不同设备上加工．工艺资料如表两种材料，要在两种不同设备上加工．工艺资料如表4－－4所所示．示．产品产品 资源资源产品甲产品甲产品乙产品乙现有资源现有资源材料材料I3012(kg)材料材料II0414(kg)设备设备A2212(h)设备设备B5315(h)产品利润产品利润(元元/件件)2040表表4－－4【【解解】】设设x1、、x2分别为产品甲和产品乙的产量，目标规划数学分别为产品甲和产品乙的产量，目标规划数学模型为：模型为：企业怎样安排生产计划，尽可能满足下列目标：企业怎样安排生产计划，尽可能满足下列目标：(1)力求使利润指标不低于力求使利润指标不低于80元元(2)考虑到市场需求考虑到市场需求,Ｉ、Ｉ、II两种产品的生产量需保持两种产品的生产量需保持1:1的比例的比例(3)设备设备A既要求充分利用，又尽可能不加班既要求充分利用，又尽可能不加班(4) 设备设备B必要时可以加班，但加班时间尽可能少必要时可以加班，但加班时间尽可能少(5)材料不能超用。

材料不能超用4.2目标规划的图解法目标规划的图解法The graphical method of GP(2)(1)(3)(4 )x2x1(6)(5)o46462 2图图4－－1ABC满意解满意解C(3,3)满意解满意解X＝＝(3,3)(3)x1x22040608010020406080100(2)(1)(4)图图5－－3BC满意解是线段满意解是线段           上任意点，端点的上任意点，端点的解是解是  B(100/3，，80/3)，，C(60，，0)．．决策者根据实际情形进行二次选择．决策者根据实际情形进行二次选择．A(3)x1x22040608010020406080100(2)(1)(4)图图5－－3BC满意解是点满意解是点 B，，X=(100/3，，80/3) A(3)x1x22040608010020406080100(2)(1)(4)图图5－－3满意解是点满意解是点 A，，X=(20，，40) A本节介绍了目标规划的图解法本节介绍了目标规划的图解法1.画出系统约束和目标约束直线画出系统约束和目标约束直线2. 标明偏差变量大于零的变量标明偏差变量大于零的变量X的取值区域的取值区域3.按优先次序分别求各目标的最小值按优先次序分别求各目标的最小值4.2目标规划的图解法目标规划的图解法The graphical method of GP4.3 单纯形法单纯形法Simplex Method单纯形法求解目标规划可参照第一章的步骤，只是目标规划的单纯形法求解目标规划可参照第一章的步骤，只是目标规划的检验要按优先级顺序逐级进行，不同的是：检验要按优先级顺序逐级进行，不同的是：（（1）首先使得检验数中）首先使得检验数中P1的系数非负，再使得的系数非负，再使得P2的系数非负，的系数非负，依次进行；依次进行；（（2）当）当P1、、P2、、…、、Pk对应的系数全部非负时得到满意解；对应的系数全部非负时得到满意解；（（3）如果）如果P1，，…，，Pi行系数非负，而行系数非负，而Pi+1行存在负数，并且负行存在负数，并且负数所在列上面数所在列上面P1，，…，，Pi行中存在正数时，得到满意解，计算行中存在正数时，得到满意解，计算结束．结束．4.3 单纯形法单纯形法Simplex Method【【例例4.6】】用单纯形法求解下述目标规划问题用单纯形法求解下述目标规划问题【【解解】】以以d1－－、、d2－－、、d3－－为基变量，求出检验数，将检验数中优为基变量，求出检验数，将检验数中优先因子分离出来，每一优先级做一行，列出初始单纯形表先因子分离出来，每一优先级做一行，列出初始单纯形表4-5．． 4.3 单纯形法单纯形法Simplex MethodCj00P100P1P20bCB基基x1x2d1－－d1+d2－－d2+d3－－d3+P1d1－－1[2]1－－150→0d2－－211－－140P2d3－－221－－180Cj－－ZjP1－－1－－2 11P2－－2－－21表表4－－54.3 单纯形法单纯形法Simplex Method表表4－－5中，中，P1行中行中(－－2)最小，则最小，则x2进基，求最小比值易知进基，求最小比值易知d1－－出出基，将第二列主元素化为基，将第二列主元素化为1，其余元素化为零，得到表，其余元素化为零，得到表4-6．．Cj00P100P1P20bCB基基x1x2d1－－d1+d2－－d2+d3－－d3+0x21/211/2－－1/2250d2－－[3/2]1/21－－115→P2d3－－111－－130Cj－－ZjP111P2－－11－－11表表4－－64.3 单纯形法单纯形法Simplex Method表表4-6中中P1行全部检验数非负，表明第一目标已经得到优化．行全部检验数非负，表明第一目标已经得到优化．P2行存在负数，行存在负数，x1的检验的检验数为－数为－P2<0，选，选x1进基（也可以选进基（也可以选d1+进基），则进基），则d3－－出基，迭代得到表出基，迭代得到表4-7．．Cj00P100P1P20bCB基基x1x2d1－－d1+d2－－d2+d3－－d3+0x212/3－－2/31/3200x11[1/3]2/310→P2d3－－2/32/31－－120Cj－－ZjP111P22/3-2/32/3-2/314.3 单纯形法单纯形法Simplex Method 表表4-7在表在表4-7中，中，P1行的系数全部非负，行的系数全部非负，P2行存在负数，行存在负数，d1+的检验数－的检验数－2/3P2<0，选，选d1+进基，则进基，则x1出基，迭代得到表出基，迭代得到表4-8．．应当注意应当注意，表，表4-7中不能选中不能选d2+进基，检验数进基，检验数P1－－2/3P2应理解为应理解为“大于零大于零”，，P1、、P2是优先级别的比较，而不是是优先级别的比较，而不是“数数”的比较．例如，的比较．例如，P1－－3P2+5P3理解为小于理解为小于零，零，2P2－－4P4理解为大于零等等．理解为大于零等等．Cj→00P100P1P20bCB基基x1x2d1－－d1+d2－－d2+d3－－d3+0x2211－－1400d1+3－－112－－230P2d3－－－－2－－221－－10Cj－－ZjP111P222－－21表表4－－84.3 单纯形法单纯形法Simplex Method表表4-8中中P2行的（－行的（－2）小于零，但（－）小于零，但（－2）列上面）列上面P1行存在正数行存在正数1，，检验数检验数P1－－2P2>0,所有检验数非负，得到满意解所有检验数非负，得到满意解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 单纯形法单纯形法Simplex Method求满意解求满意解Cj00P100P1P2P20P3bCB基基x1x2d1－－d1+d2－－d2+d3－－d3+d4－－d4+P1d1－－[10]51－－1400→→0d2－－781－－1560P2d3－－221－－11200d4－－12.51－－1100Cj－－ZjP1 11P2－－22P31表表4-94.3 单纯形法单纯形法Simplex MethodCj00P100P1P2P20P3bCB基基x1x2d1－－d1+d2－－d2+d3－－d3+d4－－d4+0x111/21/10－－1/10400d2－－9/2-7/107/101－－1280P2d3－－1－－1/51/51－－1400d4－－[2]-1/101/101－－160→→Cj－－ZjP111P2-1↑1/5－－1/52P31表表4-104.3 单纯形法单纯形法Simplex MethodCj00P100P1P2P20P3bCB基基x1x2d1－－d1+d2－－d2+d3－－d3+d4－－d4+0x115/40－－5/40－－1/41/4250d2－－-19/4019/401－－1－－9/49/4145P2d3－－－－3/20[3/20]1－－1－－1/21/210→→0x21－－1/201/201/2－－1/230Cj－－ZjP11P23/20－－3/20↑↑21/2－－1/2P31表表4－－114.3 单纯形法单纯形法Simplex MethodCj00P100P1P2P20P3bCB基基x1x2d1－－d1+d2－－d2+d3－－d3+d4－－d4+0x115/6－－5/6－－2/32/3100/30d2－－1－－1－－19/619/6－－2/32/3340/30d1+－－1120/3－－20/3－－10/310/3200/3→→0x21－－1/31/3[2/3]－－2/3Cj－－ZjP11P211P31表表4-124.3 单纯形法单纯形法Simplex MethodCj00P100P1P2P20P3bCB基基x1x2d1－－d1+d2－－d2+d3－－d3+d4－－d4+0x1111/2－－1/2600d2－－11－－1－－7/27/21400d1+5－－115－－52000d4－－3/2－－1/21/21－－3/440Cj－－ZjP11P211P31表表4－－134.3 单纯形法单纯形法Simplex Method（（2）将目标函数）将目标函数               改写成改写成 以表以表4-12为基础，计算出检验数得到表为基础，计算出检验数得到表4-14表表4-14Cj00P1P1P300P20P4bCB基基x1x2d1－－d1+d2－－d2+d3－－d3+d4－－d4+0x115/6－－5/6－－2/32/3100/3P3d2－－1－－1-19/619/6－－2/32/3340/3 P1d1+－－11[20/3]-20/3-10/310/3200/30x21－－1/31/32/3－－2/380/3Cj－－ZjP12-20/320/310/3-10/3P219/6－－7/62/3－－2/3P3119/61P414.3 单纯形法单纯形法Simplex MethodCj 00P1P1P300P20P4bCB基基x1x2d1－－d1+d2－－d2+d3－－d3+d4－－d4+0x111/8－－1/8－－1/41/425P3d2－－－－19/4019/401-1－－9/49/4145 0d3－－－－3/203/201-1－－1/2[1/2]100x21－－1/201/201/2－－1/230Cj－－ZjP111P21P319/40－－19/4019/4－－9/4P41表表4-154.3 单纯形法单纯形法Simplex MethodCj00P1P1P300P20P4bCB基基x1x2d1－－d1+d2－－d2+d3－－d3+d4－－d4+0x111/5－－1/5－－1/21/220P3d2－－1/5－－1/51－－1－－9/29/2100 P4d4+－－3/103/102－－2－－11200x21－－1/51/51－－140Cj－－ZjP111P21P3－－1/51/519/2－－9/2P43/10－－3/10－－21表表4-16用单纯形法求解得到最终表用单纯形法求解得到最终表4-16，满意解，满意解X＝＝(20，，40)T，对应于图，对应于图4-6中点中点A在（在（2）中如果按　　　　　　　　　　　　　　　　　　　　　　）中如果按　　　　　　　　　　　　　　　　　　　　　　求解，单求解，单纯形法计算如表纯形法计算如表4-17所示所示　　 4.3 单纯形法单纯形法Simplex Method00P1P1P2002P20P3bx1x2d1－－d1+d2－－d2+d3－－d3+d4－－d4+x115/6－－5/6－－2/32/3100/3d21－－1－－19/619/6－－2/32/3340/3d1+－－1120/3－－20/3－－10/3[10/3]200/3→→x21－－1/31/32/3－－2/380/3P12－－20/320/310/3－－10/3↑↑P219/6－－7/632/－－2/3P311表表4-17  转下表转下表4.3 单纯形法单纯形法Simplex Method00P1P1P2002P20P3bx1x2d1－－d1+d2－－d2+d3－－d3+d4－－d4+x118/45－－8/45－－1/91/980/9d3+2/45－－2/452/9－－2/9－－11200/9d4+－－19/9019/904/9－－4/9－－11580/9x21－－7/457/452/9－－2/9560/9P111P2－－4/454/455/94/92P319/90－－19/90－－4/94/91最终表：最终表：4.3 单纯形法单纯形法Simplex Method满意解满意解X＝＝(80/9，，560/9)T，，d3+＝＝200/9而而d2－－＝＝0，与目标要求，与目标要求相悖，还可以从图相悖，还可以从图4-6说明这个结果是错误的．说明这个结果是错误的．例例4.7（（2）是在原问题中作了部分变动后再求解，等价于第）是在原问题中作了部分变动后再求解，等价于第二章的灵敏度分析，求解原理基本相同．二章的灵敏度分析，求解原理基本相同．4.2目标规划的图解法目标规划的图解法The graphical method of GP目标规划的单纯形法与线性规划比较主要有两点不同。

目标规划的单纯形法与线性规划比较主要有两点不同    第一，目标规划是按优先次序顺序求解，逐个满足最优（检第一，目标规划是按优先次序顺序求解，逐个满足最优（检验数大于等于零）；验数大于等于零）；    第二，不一定所有检验数都能满足大于等于零，如果某个检第二，不一定所有检验数都能满足大于等于零，如果某个检验数小于零，所在列存在检验数大于零时，则认为得到满意解验数小于零，所在列存在检验数大于零时，则认为得到满意解    计算方法和基本原理与线性规划类似计算方法和基本原理与线性规划类似。