机械优化设计-第五章第次课

机械优化设计2017年6月上

海

海

事

大

学SHANGHAIMARITIMEUNIVERSITY何军良上海海事大学ShanghaiMaritimeUniversity

1909

2009

2004

1912

19587机械优化设计中的几个问题1优化设计概述2优化设计的数学基础2目录CONTENTS3一维搜索方法4无约束优化方法5线性规划6约束优化方法第四章无约束优化方法

线性规划的标准形式与基本性质02基本可行解的转换

单纯形方法单纯形方法应用举例030405

修正单纯形法06

概述014（1）

定义5.1概述目标函数和约束条件都是线性的，像这类约束函数和目标函数都是为线性函数的优化问题，称作线性规划问题。它的解法在理论和方法上都很成熟，实际应用也很广泛。虽然大多数工程设计是非线性的，但是也有采用线性逼近方法求解非线性问题的。此外，线性规划方法还常被用作解决非线性问题的子问题的工具，如在可行方向法中可行方向的寻求就是采用线性规划方法。当然，对于真正的线性优化问题，线性规划方法就更有用了。5（2）

主要研究的问题5.1概述一类是已有一定数量的资源（人力、物质、时间等），研究如何充分合理地使用它们，才能使完成的任务量为最大。另一类是当一项任务确定以后，研究如何统筹安排，才能使完成任务所耗费的资源量为最少。——实际上，上述两类问题是一个问题的两个不同的方面，都是求问题的最优解（max或min）。6（3）

线性规划模型建立5.1概述建模步骤1确定决策变量：即需要我们作出决策或选择的量。一般情况下，题目问什么就设什么为决策变量。2找出所有限定条件：即决策变量受到的所有的约束；3写出目标函数：即问题所要达到的目标，并明确是max还是min。7（1）

线性规划实例5.2标准形式与基本性质解：设生产A、B两产品分别为x1,x2台，则该问题的优化数学模型为：例5-1：某工厂要生产A、B两种产品，每生产一台产品A可获产值2万元；需占用一车间工作日3天，二车间工作日6天；每生产一台产品B可获产值1万元；需占用一车间工作日5天，二车间工作日2天。现一车间可用于生产A、B产品的时间15天，二车间可用于生产A、B产品的时间24天。试求出生产组织者安排A、B两种产品的合理投资产数，以获得最大的总产值。8（1）

线性规划实例5.2标准形式与基本性质例5-2：生产甲种产品每件需使用材料9kg、3个工时、4kw电，获利润60元。生产乙种产品每件需用材料4kg、10个工时、5kw电，可获利120元。若每天能供应材料360kg，有300个工时，能供200kw电。试确定两种产品每天的产量，使每天可能获得的利润最大？

分析：每天生产的甲、乙两种产品分别为

件（工时约束）（电力约束）（材料约束）(利润最大)9（1）

线性规划实例5.2标准形式与基本性质将其化成线性规划标准形式：求使且满足10（1）

线性规划实例5.2标准形式与基本性质例5-3：某厂生产甲、乙两种产品，已知：①两种产品分别由两条生产线生产。第一条生产甲，每天最多生产9件，第二条生产乙，每天最多生产7件；②该厂仅有工人24名，生产甲每件用2工日，生产乙每件用3工日；③产品甲、乙的单件利润分别为40元和80元。问工厂如何组织生产才能获得最大利润？

日利润最大生产能力限制劳动力限制变量非负解:设甲、乙两种产品的日产件数分别为s.t.11（1）线性性规规划划实实例例5.2标准准形形式式与与基基本本性性质质例5-4：某工工厂厂生生产产A、、B、、C三三种种产产品品，，现现根根据据订订货货合合同同以以及及生生产产状状况况制制定定5月月份份的的生生产产计计划划，，已已知知合合同同甲甲为为：：A产产品品1000件件，，单单件件价价格格为为500元元，，违违约约金金为为100元元/件件；；合合同同乙乙为为：：B产产品品500件件，，单单件件价价格格为为400元元，，违违约约金金为为120元元/件件；；合合同同丙丙为为：：B产产品品600件件，，单单件件价价格格为为420元元，，违违约约金金为为130元元/件件；；C产产品品600件件，，单单件件价价格格为为400元元，，违违约约金金为为90元元/件件；；有有关关各各产产品品生生产产过过程程所所需需工工时时以以及及原原材材料料的的情情况况见见下下表表。。试试以以利利润润为为目目标标，，建建立立该该工工厂厂的的生生产产计计划划线线性性规规划划模模型型。。工序1工序2工序3原材料1原材料2其他成本产品A/件2323410产品B/件1132310产品C/件2124210总工时或原材料460040006000100008000工时或原材料成本（元）151010204012（1）线性规规划实实例5.2标准形形式与与基本本性质质例5-5：成批生产企企业年年度生生产计计划的的按月月分配配。。在成批批生产产的机机械制制造企企业中中，不不同产产品劳劳动量量的结结构上上可能能有很很大差差别。。如：：某种种产品品要求求较多多的车车床加加工时时间，，另一一种产产品的的劳动动量可可能集集中在在铣床床和其其他机机床上上。因因此，，企业业在按按月分分配年年度计计划任任务时时，应应考虑虑到各各种设设备的的均衡衡且最最大负负荷。。在年度度计划划按月月分配配时一一般要要考虑虑:1）从数量量和品品种上上保证证年度度计划划的完完成；；2））成批批的产产品尽尽可能能在各各个月月内均均衡生生产或或集中中在几几个月月内生生产；；3））由于于生产产技术术准备备等方方面原原因，，某些些产品品要在在某个个月后后才能能投产产；4）根根据合合同要要求，，某些些产品品要求求在年年初交交货；；5））批量量小的的产品品尽可可能集集中在在一个个月或或几个个月内内生产产出来来，以以便减减少各各个月月的品品种数数量等等等。。如何在在满足足上述述条件件的基基础上上，使使设备备均衡衡负荷荷且最最大负负荷。13（2）线性规规划的的标准准形式式5.2标准形形式与与基本本性质质14（2）线性规规划的的标准准形式式5.2标准形形式与与基本本性质质矩阵形形式决策变量常数项系数矩阵价值系数其中：：15（2）线性规规划的的标准准形式式5.2标准形形式与与基本本性质质矩阵形形式的的另一一种表表示max(min)z＝CTXs.t.AX≤(＝,≥)bX≥016（2）线性性规规划划的的标标准准形形式式5.2标准准形形式式与与基基本本性性质质线性性规规划划的的向向量量形式式设则得LP的向量量形形式式：：17（2）线性性规规划划的的标标准准形形式式5.2标准准形形式式与与基基本本性性质质线性性规规划划数数学学模模型型的的一一般般形形式式：：求使且满满足足说明明：：1）m=n,唯一一解解2）m>n,无解解3）m<n,无穷穷解解18（2）线性性规规划划的的标标准准形形式式5.2标准准形形式式与与基基本本性性质质标准准型型特特征征：：目标标函函数数极极大大化化约束束条条件件为为等等式式决策策变变量量非非负负资源源向向量量非非负负maxZ=CXSt.AX=bX≥019（2）线性性规规划划的的标标准准形形式式5.2标准准形形式式与与基基本本性性质质x3为松松弛弛变变量量约束束条条件件为““”时时：：约束束条条件件包括括两两部部分分：：一一是是等式式约约束束条条件件，二是是变变量量的的非负负要要求求，它它是是标标准准形形式式中中出出现现的的唯唯一一不不等等式式形式式。。将一一般般形形式式的的线线性性规规划划化化为为标标准准形形式式的的方方法法（1）如如果果有有不不等等式式约约束束则可可加上上新的的变变量量此时时称称xn+i为松松弛弛变变量量，，把把他他们们全全变为为等等式式约约束束20（2）线性性规规划划的的标标准准形形式式5.2标准准形形式式与与基基本本性性质质约束束条条件件为“”时：：（2）如如果果有有不不等等式式约约束束则可可减去去新的的变变量量此时时称称xn+i为剩剩余余变变量量，，把把他他们们全全变为为等等式式约约束束x3为剩余余变变量量21（2）线性性规规划划的的标标准准形形式式5.2标准准形形式式与与基基本本性性质质（3）如如果果有有变变量量1、x0，令x'＝-x。2、x取值值无无约约束束，，令x=x'-x"3x1'-3x1"+2x28x1'

-

x1"-4x2

14x1',x1",

x2

03x1+2x28x1-4x214x203x1'-3x1"+2x2+x3=8x1'-x1"-4x2+x4=14x1',x1",x2,x3,x40如：：22（2）线性性规规划划的的标标准准形形式式5.2标准准形形式式与与基基本本性性质质（4）x两边边有有约约束束的的情情况况。。x1'

+x211x1'16x1',x20x1+x25-6x110x20-6+6x1+610+6令x1'=x1+60x1'16（5）右右端常数数。。右端端项项b＜0时，，只只需需将将等等式式或或不不等等式式两两端端同同乘乘(一1)，则则等等式式右右端端项项必必大大于于零零。。23（2）线性性规规划划的的标标准准形形式式5.2标准准形形式式与与基基本本性性质质例5-1的数数学学模模型型可可化化为为如如下下的的标标准准形形式式用矩矩阵阵和和向向量量表表示示则则有有：：24（3）线性性规规划划的的基基本本性性质质5.2标准准形形式式与与基基本本性性质质图5.1线性规划的几何意义以例例5-1为例例，，用用图图解解法法解解释释线线性性规规划划的的几几何何意意义义，，并并与与代代数数法法得得到到的的解解加加以以对对照照说说明明25（3）线性性规规划划的的基基本本性性质质5.2标准准形形式式与与基基本本性性质质线性规划的几何意义通过顶点ＣＣ的直线满满足上述条条件，故点点Ｃ是该问问题的最优优解。令松弛变量量x3=0，x4=0,画出上述约约束方程的的图线。取Z为不同的常常数，可画画出一系列列平行直线线。在此直直线族中，，确定出一一条直线满满足以下条条件，即：：尽可能远远离原点O，且与多边边形OACD至少有一交交点。26（3）线性规划的的基本性质质5.2标准形式与与基本性质质用代数法解解联立方程程组。设变变量个数为为n，方程个数数为m，令p=n-m，为使方程程组有唯一一解，让p个变量等于于0。在例5.1中，p=4-2=2，因此，若若4个变量中使使任意两个个等于0，则必存在在两个变量量组的唯一一解。序号123456变量值X10005415/4X20312003/4X3150-45030X424180-600图中对应的顶点ODEBAC下表列出了了6个可能的解解，其中4个解恰好等等于多边形形的4个顶点，余余下的2个解违反了了变量非负负的条件。。27（3）线性规划的的基本性质质5.2标准形式与与基本性质质可行域可行解：同时满足所所有约束条条件的任何何一个解x=[x1,x2,…,xn]T。例：多边边形OACD域中任任意一个解解。基本解：令线性规划划标准形式式中任意(n-m)个个变量等于于零，若剩剩余的m个个变量构成成的m个线线性方程有有唯一解，，则称由此此得到的n个变量的的解为基本本解。例：上表5列列出的６个解(或图对应的６个顶点点A、B、、C、D、、E、O)。基本可行解解：如果基本解解还满足非非负条件xj≥0(j=1,2,…,n),则称之之为基本可可行解（既既是基本解解，又是可可行解）。例：表中列出的4个个解(或图图6.1对对应的4个个顶点A、、C、D、、O)。28（3）线性规划的的基本性质质5.2标准形式与与基本性质质可行域最优解：使目标函函数达到最最小值的基基本可行解解。例：图中的点C为最最优解，对对应的目标标函数值为为-33/4.基、基向量量、基变量量与非基变变量基：在系数矩阵阵A中，选选择m列线线性无关向向量构成m×m阶非非奇异子矩矩阵B,则则称B为线线性规划的的一个基。。基向量：组成基B的的列向量pj(j=1,2,…,m)。基变量：与基向量对对应的变量量xj(j=1,2,…,m)。用用xB表示。基变量取正正值。非基变量：：除基变量外外的其余(n-m)个变量。。用xN表示。非基变量取取零。29（3）线性规划的的基本性质质5.2标准形式与与基本性质质基变量和非非基变量是是相对于基基而言的。。30（3）线性规划的的基本性质质5.2标准形式与与基本性质质线性规划问问题的以上上几个解的的关系，可可用下图来来描述：31（3）线性规划的的基本性质质5.2标准形式与与基本性质质32（3）线性规划的的基本性质质5.2标准形式与与基本性质质基本解共10个,每个基本解解中有n-m＝2变量取零值值。基本可可行解5个。33（3）线性规划的的基本性质质5.2标准形式与与基本性质质线性规划的的两个重要要性质线性规划可可行解的集集合构成一一个凸集，，且这个凸凸集是凸多多面体，它它的每一个个顶点对应应于一个基基本可行解解，即顶点点与基本可可行解相当当。线性规划的的最优解如如果存在，，必然在凸凸集的某个个顶点（即即某个基本本可行解））上达到。。34（3）线性规划的的基本性质质5.2标准形式与与基本性质质线性规划解的特殊情情形因此，线性规划划的最优解解不必在可可行域整个个区域内搜搜索，只要要在它的有限个基本本可行解（（顶点）中中去寻找即即可。35（3）线性规划的的基本性质质5.2标准形式与与基本性质质但是，在实际的的线性规划划问题中，，其变量的的个数n和和约束方程程的个数m都是很大大的，其基基本可行解解的数目非非常多，即即使采用计计算机也难难以实现；；同时，仅仅仅考察基基本可行解解，也不能能确定问题题何时有无无界解。故没有必要找找出所有的的基本可行行解以求得得最优解，，而是采用用一定的方方法如单纯纯形法来解解决这个问题。36（1）基本解到基基本解的转转换5.3基本可行解解的转换把约束条件件展开37（1）基本解到基基本解的转转换采用高斯-约当法(Gauss-Jordan)进行消元：：此过程称作作对变量xk进行转轴运运算，xk称为转轴变量，alk称为转轴元素。5.3基本可行解解的转换38（1）基本解到基基本解的转转换选取另一变变量作为转转轴变量进进行第二次次转轴运算算，并反复复此过程，，我们将得得到：这一方程组组称为正则则方程组（（高斯-约当消元过程））。从而得得到一组基基本解(基本解中所所有基本变变量的全体体称为基)：基本变量非基本变量量5.3基本可行解解的转换39（1）基本解到基基本解的转转换如果此时继继续对上述述形式的方方程组进行行附加的一一次转轴运运算，例如如选取作(t>m)为转轴元素素，此时xt进入基，xs出基。这样样就完成了了从一个基基本解到另另一个基本本解的转换换5.3基本可行解解的转换40（1）基本解到基基本解的转转换5.3基本可行解解的转换解：用a11,a22作为轴元素素进行两次次转轴运算算：例：给定如下方方程组，试试进行基本本解的转换换运算。得到一组基基本解：x1=-12x2=-20x3=x4=x5=041（1）基本解到基基本解的转转换5.3基本可行解解的转换用a25作为轴元素素进行第三三次转轴运运算：又得到一组组基本可行解解：x1=3x5=5x2=x3=x4=0此时x5进入基，x2出基。当已经得到到一组基本本可行解，，若要求把把xk选进基本变变量，并使使下一组基基本解是可可行解的话话，则在第k列要选取不不为任何负负值的元素素作为转轴轴元素。5.3基本可行解解的转换（2）基本可行解解到基本可可行解的转转换alk作为转轴元元素进行转转轴运算：：5.3基本可行解解的转换（2）基本可行解解到基本可可行解的转转换5.3基本可行解解的转换（2）基本可行解解到基本可可行解的转转换方程组第一一行发生的的变化：5.3基本可行解解的转换（2）基本可行解解到基本可可行解的转转换alk作为轴元素素，xk选进基本变变量后，xk的取值由零零变成了一个正值，则原来各基基本变量的的取值变为为:若是基本可行解解,应该保证各差值最小小者为零:决定了非基变量量为xi5.3基本可行解解的转换（2）基本可行解解到基本可可行解的转转换若想用xk取代xl成为可行解解中的基本本变量，就就应该选所对应的行行成为转轴轴行，即所所选取的行行要满足条条件:规则5.3基本可行解解的转换（2）基本可行解解到基本可可行解的转转换例：基本可行解解：x1=3x5=5x2=x3=x4=0基本变量x1、x5基本可行解解的转换：：1）x2、x4系数全部为为负，只能能选取x3所在的第3列为转轴轴行2）,由于，，则取取第一行为为转轴行,于是取a'13=2为转轴轴元素，使使x3取代x1成为基本变变量。5.3基本可行解解的转换（2）基本可行解解到基本可可行解的转转换经转轴运算算得：得基本可行行解：5.3基本可行解解的转换（2）基本本可可行行解解到到基基本本可可行行解解的的转转换换结论论：：可可把把松松驰驰变变量量作作为为初初始始基基本本可可行行解解中中的的一一部部分分基本本变变量量。原始始约约束束条条件件:引入入松松驰驰变变量量:可得得一一组组基基本本可可行行解解：：5.3基本本可可行行解解的的转转换换（3）初始始基基本本可可行行解解的的求求法法515.3单纯纯形形方法法及及应应用用举举例例要找找到到线线性性规规划划问问题题的的最最优优解解，，只只要要在在基基本本可可行行解解中中寻寻找找就就可可以以了了。。虽虽然然基基本本可可行行解解的的数数目目是是有有限限个个（（不不超过过个个），，但但当当m和n较大大时时，，要要用用“穷穷举举法法””求出出所所有有基基本本可可行行解解也也是是行行不不通通的的。。因因此此，，必必须须寻寻求求一一种种更更有有效效的的方方法法。单纯纯形形法法的基基本本思思路路是是：：从从线线性性规规划划问问题题的的一一个个基基本本可可行行解解开开始始，，转转换换到到另另一一个个使目目标标函函数数值值增增大大的基基本本可可行行解解。。反反复复迭迭代代，，直直到到目目标标函函数数值值达达到到最最大大时时，，就就得得到到了了最最优优解解。。按照照单纯纯形形法法的的思思路路求求解解线线性性规规划划问问题题,要解解决决三三个个技技术术问题题：：（1）给出出第第一一个个基基本本可可行行解解；（（2）转换换到到另另一一个个基本本可可行行解解；（3）检验验一一个个基基本本可可行行解解是是否否是是最优优解解。。525.3单纯纯形形方法法及及应应用用举举例例把线性性规规划划问问题题变变成成标准准形，观观察察是否否每每个个约约束束方方程程中中都都有有独独有有的的、、系系数数为为1的变量量。。如果果是，则则取这这些些变变量量作作为为基变变量量，，便便得得到到一个个基本本可可行行解解；；否则，，就就给没没有有这这种种变变量量的的约约束束条条件件添添加加一一个个人工工变变量量，同同时时修改改目目标标函函数数。（1）确确定定初初始始基基可可行行解解535.3单纯形形方法及及应用用举例例（1）确定定初始始基可可行解解标准形形变化化545.3单纯形形方法及及应用用举例例（1）确定定初始始基可可行解解首先有假定定的系数矩矩阵A中包含一一个m阶单位位矩阵阵，即有m个单位列列向量量，那那么这m个单位列列向量量所对对应的的基本本可行行解是是一个个基本可可行解解。设A的前m列为单位向向量，，即：（1）555.3单纯形形方法及及应用用举例例（1）确定定初始始基可可行解解显然，，是是（L,P）的一一个基基本可可行解解，其其中，。。我们们就从这这个初始基基本可可行解解，开开始单纯形形法的的迭代代（搜搜索））的第一一步。。从（1）式中中求解解出：：即

（2）

取非基变变量等等于零零，得到到初始始基可可行解解565.3单纯形形方法及及应用用举例例（2）基可可行解解转换换基可行行解转转换是从一个基基可行行解转转换为为相邻的的基可行行解（即从从一个顶顶点转转到另另一个个顶点点）。定义：：两个个基可可行解解是相邻的的，如果果它们们之间间变换换且仅仅变换换一个基基变量量。规则：：θ规则。。575.3单纯形形方法及及应用用举例例（2）基可可行解解转换换θ规则P1

P2P3

…PmPm+1…

Pj…Pn

b585.3单纯形形方法及及应用用举例例（3）最优优性检检验和和解的的判别别将基可行行解X(0)和X(1)分别代代入目标函函数得：被称为为检验数数，通常常简写写为或如果单单纯形形表最最后一一行中中的都满足足，则对应的的基本本可行行解是最优优解；否则则，就就不是最最优解解。595.3单纯形形方法及及应用用举例例用单纯形形法求求解线线性规规划问问题的的具体步步骤如下：找出初初始可可行基基，确确定初初始基基本可可行解解，建建立初初始单单纯形形表；；转②②。检验对对应于于非基基变量量的检检验数。。若若（（xj为非基基变量量）都都成立立，则则当前前单纯纯形表表对应应的基基本解解就是是最优优解，，停止止计算算；否否则转转③。。在所有中中，若最大大对对应的xk的系数a'ik≤0(i=1,2,…,m)，则此此问题题为无无界解解（无无解）），停停止计计算；；否则则转④④。605.3单纯形形方法及及应用用举例例根据确确定定xk为换入变变量；根据据θ规则确确定相相应的的换出变变量。转⑤。。以a‘ik为中心元元素进行变换，并得到到中心心元素素a'ik旋转运运算得得到新的单纯形形表。。转②单纯形形法的的基本思思路：从可可行域域中某某一个个顶点点开始始，判判断此此顶点点是否否是最最优解解，如如不是，，则再找另另一个个使得得其目目标函函数值值更优优的顶顶点，，称之之为迭迭代，，再判判断此此点是是否是是最优优解。。直到到找到到一个个顶点点为其其最优优解，，就是是使得得其目目标函函数值值最优的的解，或者能判断断出线线性规规划问问题无最优优解为止。。615.3单纯形形方法及及应用用举例例单纯形形表的的格式式：迭代次数XBCBx1x2…xnb比值C1C2…Cn0x1C1a11a12…a1nb1θ1x2C2a21a22…a2nb2θ2…...……………xmCmam1am2amnbmθmZjZjZj…Zjσjσ1σ2…σn625.3单纯形形方法及及应用用举例例（4）单纯纯形应应用举举例例5-6：用图解法法和单纯形形法求如下下线性性规划划问题题的最优解解。635.3单纯形形方法及及应用用举例例（4）单纯纯形应应用举举例

0123456712345(2.25,0)4x1+x2=91、图解解法求求解645.3单纯形形方法及及应用用举例例（4）单纯纯形应应用举举例2、单纯纯形法法求解解迭代次数基变量CBx1x2x3x4b比值01310742019Zjσj655.3单纯形形方法及及应用用举例例（4）单纯纯形应应用举举例2、单纯纯形法法求解解迭代次数基变量CBx1x2x3x4b比值41000x3013107x4042019Zj00000σj4100填目标标函数数系数、、填基基变量量列、、填CB列；计算Zj、计算算检验验数。。665.3单纯形形方法及及应用用举例例（4）单纯纯形应应用举举例2、单纯纯形法法求解解迭代次数基变量CBx1x2x3x4b比值41000x30131077x40420199/4Zj00000σj4100①最优吗？？查什什么？？不是是！②谁谁进基？检验数数最大大的x1进基，，谁出出基？③x1的系数数有正正的吗吗？求求比值值？基变量量列中中x4换为x1；改CB列，0换为4675.3单纯形形方法及及应用用举例例（4）单纯纯形应应用举举例2、单纯纯形法法求解解迭代次数基变量CBx1x2x3x4b比值41000x30131077x40420199/4Zj00000σj4100迭代次数基变量CBx1x2x3x4b比值41001x3002.51-0.254.75x1410.500.252.25Zj42019σj0-10-1685.3单纯形形方法及及应用用举例例（4）单纯纯形应应用举举例例5-7：用单纯形形法求如下下线性性规划划问题题的最优解解。695.3单纯形形方法及及应用用举例例（4）单纯纯形应应用举举例3x1+5x2+x3=150x2+x4=208x1+5x2+x5=300MaxZ=50x1+40x2+0x3+0x4+0x5标准化化x1，x2，x3，x4，x5≥0705.3单纯形形方法及及应用用举例例（4）单纯纯形应应用举举例迭代次数基变量CBx1x2x3x4x5b比值50400000x3035100150150/5x400101020-x5085001300300/8Zj000000σj5040000当前基基本可可行解解：(0,0,150,20,300)，Z=0。715.3单纯形形方法及及应用用举例例（4）单纯纯形应应用举举例迭代次数基变量CBx1x2x3x4x5b比值50400001x30025/810-3/875/212x40010102020x15015/8001/875/260Zj50125/40025/41875σj035/400-25/4当前基基本可可行解解：(75/2,0,75/2,20,0)，Z=1875。725.3单纯形形方法及及应用用举例例（4）单纯形形应用举举例迭代次数基变量CBx1x2x3x4x5b比值50400001x240018/250-3/2512x4000-8/2513/258x15010-5/2505/2530Zj504014/5026/51980σj00-14/50-26/5当前解：(30,12,0,8,0)，为最优优，Z*=1980。73例5-8：用单纯形法法求如下线线性规划划问题的的最优解。。5.3单纯形方法及应应用举例例（4）单纯形形应用举举例74迭代次数基变量CBx1x2x3x4x5b比值230001x301010-1/222x4040012164x2301001/43-σj2000-3/49迭代次数基变量CBx1x2x3x4x5b比值230000x301210084x404001116-x5004001123σj2300005.3单纯形方法及应应用举例例（4）单纯形形应用举举例75迭代次数基变量CBx1x2x3x4x5b比值230001x121001/404x5000-21/214x23011/2-1/802σj00-3/2-1/8014迭代次数基变量CBx1x2x3x4x5b比值230000x121010-1/22-x4000-41284x2301001/4312σj00-201/413此问题的的最优解解为:x1*=4,x2*=2,x5*=4，x3*=x4*=x1*=0,z*=24+32=145.3单纯形方法及应应用举例例（4）单纯形形应用举举例765.4单纯形方方法的特特殊情况况最终产生最优优值的单单纯形表表中，某某一非基本变变量的检验数为0，意味着着作任何何增大，，目标函函数的最最优值不变。此此时线性规划划问题的的最优解解并不唯唯一，有有多重最优解。。（见例例题）（1）无穷最最优解例5-9：用单纯形法法求如下线线性规划划问题的的最优解。。775.4单纯形方方法的特特殊情况况解：另Z=-Z，将原线线性规划划问题变变为MAX形式。（1）无穷最最优解迭代次数基变量CBx1x2x3x4b比值-3-1-1-10x3-1-221042x4-1310166σj-2200-8785.4单纯形方方法的特特殊情况况（1）无穷最最优解迭代次数基变量CBx1x2x3x4b比值-3-1-1-11x2-1-111/202-x4-140-1/2141σj00-10-6迭代次数基变量CBx1x2x3x4b比值-3-1-1-12x2-1013/81/43x1-310-1/81/41σj00-10-6最优解为为：X1*=（0204）X2*=（1300）所以：X*=αX1*+（1-α）X2*，其中0<α<1795.4单纯形方方法的特特殊情况况当枢列（进基变变量所在在列）中中的每一一项系数数不是0就是负值值时，说明明所有约约束条件件对进基基变量的的增加无约束作作用，因此目目标函数数可以无无限地增加，这这种情况我们们称为无无有限最最优解（（或称有有无界解或无最优解解）。但在现实实中，不不可能有有此情况况，往往往是模型型建立错错误，遗遗漏了一一些约束束条件所所致，无可行解的的情况在后面讨论论人工变变量法时再讨论。（2）无界解解805.4单纯形方方法的特特殊情况况（2）无界解解例5-10：用单纯形法法求如下线线性规划划问题的的最优解。。815.4单纯形方方法的特特殊情况况（2）无界解解迭代次数基变量CBx1x2x3x4b比值21000x30-11105-x402-501105σj21000迭代次数基变量CBx1x2x3x4b比值21001x300-3/211/210x121-5/201/25σj060-1-825.4单纯形方方法的特特殊情况况（2）无界解解注意到[6]所在的列无正元素素，将基变量x1，x3及目标函函数用非基变量x2，x4表示为：：从目标函函数看，，若令非非基变量x4=0，x2无限增大大，Z也无线增增大，且且没有影响响x1，x3的非负性，即该LP问题所追追求的目目标函数数是无界界的。即即无最大大值，于于是该LP问题无最优解解。835.4单纯形方方法的特特殊情况况（3）其他情情况在选取进进基变量量时，有有2个及2个以上变变量的检检验数具具有相同同的最大大正值（极小化化问题为为相同的的最小负负值），，这时可可任选其中中一个变量进基基。选择择进基变变量的不不同，可可能在达达到最优优解前迭迭代的次次数也不不同，但但事先无法法预测。1、进基变变量检验验数相同同2、最小比比值相同同此时可从具有有相同最最小比值值所对应应的基本本变量中中，选择择下标最小小的那个基本本变量为出基变变量。这时有可能出出现退化化的基本本可行解解，即至至少有一一个基本本变量为为零。出现现退化的基基本可行行解对运运算带来来麻烦，，理论上上可能出出现单纯纯形法陷陷入循环环或闭环环，在每每次迭代代中值保保持不变变，不能能使解趋趋向最优解。。845.4单纯形方方法的特特殊情况况（3）其他情情况幸运的是，在在实际应用用中从未遇到到或发生生过这种种情况。尽尽管如此此，人们还还是对如如何防止止出现循循环作了了大量研究，提提出了各种避免循环环的方法。在选择进基基变量和和出基变变量时作作以下规规定：①在选选择进基基变量时时，在所有σj>0的非基变变量中选选取下标最小小的进基基；②当有有多个变变量同时时可作为为出基变变量时，，选择下标最小小的那个个变量出出基。这样就就可以避免出现现循环，当然，这样也