线性规划单纯形法-课件

实用优化方法

第2章线性规划：单纯形法

刘红英理学院数学系实用优化方法

第2章线性规划：单纯形法

刘红英1线性规划：目标函数是线性的，约束条件是线性等式或不等式线性规划线性规划：目标函数是线性的，约束条件是线性规划2线性规划的历史渊源要追溯到Euler、Liebnitz、Lagrange等GeorgeDantzig,NonNeumann(Princeton)和LeonidKantorovich在1940’s创建了线性规划1947年,GeorgeDantzig于发明了单纯形法1979年，L.Khachain找到了求解线性规划的一种有效方法(第一个多项式时间算法－椭球内点法)1984年，NarendraKarmarkan发现了另一种求解线性规划的有效方法，已证明是单纯形法的强有力的竞争者(投影内点法)现在求解大规模、退化问题最有效的是原－对偶内点法线性规划的历史渊源要追溯到Euler、Liebnitz、La3线性规划单纯形法-课件4线性规划单纯形法-课件5线性规划单纯形法-课件6◎问题：确定食品数量，满足营养需求，花费最小？◎变量：n种食品，m种营养成份；－第j种食品的单价－每单位第j种食品所含第i种营养的数量

－食用第j种食品的数量－为了健康，每天必须食用第i种营养的数量◎模型：例1.食谱问题◎问题：确定食品数量，满足营养需求，花费最小？◎变量：n7例2.运输问题产销平衡/不平衡的运输问题例2.运输问题产销平衡/不平衡的运输问题8

例3.目标值带绝对值的问题

假设：事实：转化为：

例3.目标值带绝对值的问题

假设：事实：转化为：9

例4.其它应用

数据包络分析(dataenvelopeanalysis,DEA)网络流问题(Networkflow)博弈论(gametheory)等

例4.其它应用

数据包络分析(dataenvelope10线性规划的一般形式线性规划的一般形式11线性规划的标准形(分析、算法)*****标准形的特征：极小化、等式约束、变量非负向量表示：线性规划的标准形(分析、算法)*****标准形的特征：极小化12一般形式标准形转化称

松弛(slack)/盈余(surplus)变量一般形式标准形转化称松弛(slack)/盈余(13例5.化成标准形等价表示为例5.化成标准形等价表示为14定义设B是A的m个线性无关列组成的矩阵.置所有与B无关列对应的变量为零，称所得方程组的解是Ax=b的基本解(basicsolution)称B是基(basis)；称与B对应的变量为基变量(basicvariables)基本解与基变量(*****)其中满秩假定：m<n，且A的行向量线性无关定义设B是A的m个线性无关列组成的矩阵.置所有与B无15基本可行解定义称的非负基本解是标准形的基本可行解(basicfeasiblesolution)；例6.基本可行解及几何意义基本可行解的个数不超过基本可行解定义称的非负基本解是标准形的基本可行解16线性规划的基本定理(*****)i)若有可行解，则必存在基本可行解；ii)若有解，则必有某个基本可行解是最优解.考虑线性规划标准形，其中A是秩为m的m×n阶矩阵，则以下结论成立：线性规划的基本定理(*****)i)若有可行解，则必存在基17与凸性的关系线性规划的基本定理(标准形)基本可行解线性方程组的基本性质代数理论(与表述形式有关)设计算法极点凸集理论几何理论(与表述形式无关)直观理解与凸性的关系线性规划的基本定理(标准形)基本可行解线性方程组18凸性(凸集及性质)几何解释：连接集合中任两点的线段仍含在该集合中性质定义是凸集(convexset)，如果对S中任意两点x,y和(0,1)中的任一数满足凸性(凸集及性质)几何解释：连接集合中任两点的线段仍含在该集19一些重要的凸集有限个闭半空间的交集多面集(polyhedralconvexset):推广平面上：多边形注：任一线性规划的可行集是多面集！超平面(hyperplane):正/负闭半空间：一些重要的凸集有限个闭半空间的交集多面集(polyhedra20极点几何上：极点即不能位于连接该集合中其它两点的开线段上的点定义称凸集C中的点x是C的极点，如果存在C中的点y,z和某，有则必有y=z.极点几何上：极点即不能位于连接该集合中其它两点的开线段上的点21极点与基本可行解的等价性定理推论：线性规划基本定理的几何形式i)若K非空，则至少有一个极点.ii)若线性规划有解，则必有一个极点是最优解.iii)K的极点是有限集.

考虑线性规划标准形，其中A是秩为m的m×n矩阵，令则x是K

的极点当且仅当x是线性规划的基本可行解.极点与基本可行解的等价性定理推论：线性规划基本定理的i)若22例2.

K有2个极点有3个基本解，2个可行K有3个极点有3个基本解，均可行例1.例2.K有2个极点有3个基本解，2个可行K有3个极点有23例3.Subjectto5个极点－极点问题/作业考虑集合证明这两个集合的极点是一一对应的！例3.Subjectto5个极点－极点问题/作业考虑集合24线性规划问题解的几种情况线性规划问题解的几种情况25线性规划解的几何特征唯一解(顶点)！线性规划解的唯一解(顶点)！26顶点一条边无(下)界顶点一条边无(下)界27线性规划解的几何特征无界：没有有限最优解不可行：没有可行解无解可行集：多边形(二维)→多边集(高维空间)给出有效的代数刻画和严谨的几何描述，从理论上证实上述几何特征，并寻求有效算法有解：唯一解/多个解(整条边、面、甚至整个可行集)有顶点解线性规划解的几何特征无界：没有有限最优解无解可行集：多边形(28单纯形法简介适用形式：标准形(基本可行解=极点)理论基础：线性规划的基本定理！基本思想：从约束集的某个极点/BFS开始，依次移动到相邻极点/BFS，直到找出最优解，或判断问题无界.初试化：如何找到一个BFS？判断准则：何时最优？何时无界？迭代规则：如何从一个极点/BFS迭代到相邻极点/BFS？单纯形法简介适用形式：标准形(基本可行解=极点)初试化：如何291.转轴(基本解→相邻基本解)满秩假定：A是行满秩的1.转轴(基本解→相邻基本解)满秩假定：30规范形(canonicalform)基本解基变量非基变量等价变形不妨设线性无关一般地：次序可以打乱！只要有m个单位列规范形(canonicalform)基本解基变量非基变量等31规范形的转换问题⊙什么时候可以替换？⊙替换后新规范形是什么？◎替换问题假设在上述规范形中，想用规范形的转换问题⊙什么时候可以替换？⊙替换后新规范形是什32转轴(pivot)◎当且仅当，可以替换◎替换后，新规范形的系数转轴公式－转轴元(pivotelement)第二种解释：表格中第i列的数据－用当前基表示ai时的系数转轴(pivot)◎当且仅当，可以替换◎替换后33转轴例1.求下列方程组以为基变量的基本解转轴例1.求下列方程组以为基变量的基本解34转轴转轴转轴x=(0,0,0,4,2,1)转轴转轴转轴x=(0,0,0,4,2,1)35如何得到第一个规范形处理：给表格附加m个单位列向量开始迭代，用A中的列依次替换这些单位列向量以下运算同例1!例2.

利用转轴解方程组为了得到第一个规范形，形成增广表格如何得到第一个规范形处理：给表格附加m个单位列向量开始迭代，362.BFS→相邻BFS(极点→相邻极点)◎问题：确定出基变量，使转轴后新规范形对应BFS？设x是BFS,且规范形如前，且假设

aq进基因为令可否选取合适的使得是BFS？所以2.BFS→相邻BFS(极点→相邻极点)◎问题：确定出基变37确定离基变量至少有一个正元确定离基变量至少有一个正元38例3.

考虑线性方程组a4进基转轴B=(a1,a2,a3)X=(4,3,1,0,0,0)a1进基x=(0,1,3,2,0,0)例3.考虑线性方程组a4进基转轴B=(a1,a2,a3)a393.BFS→目标值减小的相邻BFS⊙将Ax=b的任一解用非基变量表示；设x是BFS，且规范形如前，则有◎问题：确定进基变量，转轴后使新BFS的目标值变小？用非基变量表示.——选取进基变量的依据⊙将目标函数3.BFS→目标值减小的相邻BFS⊙将Ax=b的任一解用40相对/既约费用系数(relative/reducedcostcoefficients)将Ax=b

的任一解x用非基变量表示为相对/既约费用系数(relative/reducedcos41确定进基变量◎最优性定理◎定理(BFS的提高)◎相对费用系数的经济解释！(合成价格、相对价格)给定目标值为z0的非退化基本可行解，且假定存在j使得rj<0，则

i)如果用aj替换基中某列得到了新的BFS，则新解处的目标值比z0严格小.

ii)如果任何替换都产生不了新的BFS，则问题无界.

◆退化基本可行解：某个或某些基变量取零的基本可行解！问题：基本可行解与基的对应关系？确定进基变量◎最优性定理◎定理(BFS的提高)◎相对费用系数424.计算过程－单纯形法单纯形表：BFS对应规范形的表格＋既约费用系数和BFS目标值的相反数单纯形表可以提供计算所需的所有信息！4.计算过程－单纯形法单纯形表：BFS对应规范形的表格＋单43如何得到第一张单纯形表◎用转轴运算(初等行变换)将最后一行与基变量对应的元素化为零，即得第一张单纯形表！◎初始表格：BFS对应规范形的表格＋[c0]如何得到第一张单纯形表◎用转轴运算(初等行变换)将◎初始44例1.

化标准形转轴得标准形的初始表格/第一张单纯形表例1.化标准形转轴得标准形的初始表格/第一张单纯形表45转轴0↓-2↓-4↓-27/5转轴转轴0转轴46最优解：最优值：原问题的极大值：最优解：最优值：原问题的极大值：47单纯形法的步骤步0形成与初始BFS对应的初始表格.通过行变换求出第一张单纯形表.步1若对每个j都有，停；当前BFS是最优的.步2选取q满足步4以为转轴元进行转轴，更新单纯形表，返步1.步3若，停，问题无界；否则，选p满足转轴规则：进基变量：最小相对费用系数规则；出基变量：最小指标规则！单纯形法的步骤步0形成与初始BFS对应的初始表格.步148单纯形法的收敛性◎非退化线性规划：任一基本可行解非退化

对非退化线性规划，从任一基本可行解出发，利用单纯形法可在有限步内得到最优解或判断问题无界.◎收敛性定理：单纯形法的收敛性◎非退化线性规划：任一基本可行解非退化495.如何启动单纯形法－人工变量◎目标判断Ax=b,x≥0是否有界；有解时找一个基本可行解；⊙给有需要的行乘以-1，使得b≥0◎方法(x,y)=(0,b)是基本可行解！故可以(0,b)为初始BFS，利用单纯形法求解辅助问题假设最后得最优解(x,y)、最优值z*和最优基B⊙构造辅助问题人工变量5.如何启动单纯形法－人工变量◎目标判断Ax=b50得到原问题的基本可行解◎z*>0，无可行解！◎z*=0，有可行解！⊙基变量中无人工变量→x

是BFS，B是对应的基⊙基变量中有人工变量→驱赶人工变量出基假设第i个基变量是人工变量，且当前单纯形表第i行的前n个数据是第i个约束冗余；删除单纯形表的第i

行数据以任一非零元为转轴元转轴得辅助问题的一个新最优BFS，且基变量中少1个人工变量！得到原问题的基本可行解◎z*>0，无可行解！◎z*=51例1.

给出下面系统的一个基本可行解，或者说明其无解引入人工变量目标：辅助问题的初始表格！BFS例1.给出下面系统的一个基本可行解，或者说明其无解引入人工52第一张单纯形表第二张单纯形表第一张第二张53辅助问题的最优值是0.原问题的BFS：辅助问题的最优值是0.原问题的BFS：54例2.

利用两阶段法求解下面的问题辅助问题第I阶段：例2.利用两阶段法求解下面的问题辅助问题第I阶段：55辅助问题的最后一张单纯形表原问题的初始表格：辅助问题的最后一张单纯形表原问题的初始表格：56原问题的最优解：原问题的最优解：57两阶段法－可求任一线性规划问题◎第I阶段：启动单纯形法

→构造、求解辅助问题→判断原问题不可行、或可行

→可行时找到基本可行解及对应规范形⊙第II阶段：利用单纯形法求原问题

→从上述BFS出发，求解所给问题

→原问题无界或者有解两阶段法－可求任一线性规划问题◎第I阶段：启动单纯形法58退化(degenerate)与循环(cycling)◎退化问题⊙单纯形法可能出现循环！⊙实际中经常碰到退化问题，但很少出现循环⊙避免出现循环的措施：摄动法、Bland法则、字典序法

基本可行解是退化的当且仅当单纯形表最后一列有一个或者多个零！一次转轴是退化的当且仅当目标函数没有发生变化！退化(degenerate)与循环(cycling)◎退化问59最小系数规则：◎进基变量：最小系数规则◎出基变量：最小指标规则循环的例子Beale循环定义：从某张单纯形表开始返回到该单纯形表的一串转轴转轴规则：选取进基变量和离基变量的明确规则(可以选时！)最小系数规则：◎进基变量：最小系数规则循环的例子Beale60线性规划单纯形法-课件61线性规划单纯形法-课件62

循环！注：循环转轴序列中所有BFS都是退化的！是同一个BFS！第七张单纯形表循环！注：循环转轴序列中所有BFS都是退化的！是同一个BF63避免循环的方法⊙能进基的变量(使目标值减小)中选指标最小者进基◎摄动法(Dantzig，1954年)◎

Bland法则(Bland,1977)－最小指标法则◎字典序法(Orden和Wolfe，1954年)⊙能出基的变量(保持可行)中选指标最小者出基美好愿望：构造某种永远不会产生循环的转轴规则！避免循环的方法⊙能进基的变量(使目标值减小)中选指标最小者进64前四张单纯形表相同！利用Bland法则作为转轴规则求解Beale的例子！前四张单纯形表相同！利用Bland法则作为转轴规则求解Bea65最后一张单纯形表/最优单纯形表最后一张单纯形表/最优单纯形表66退化的线性规划－退化的基本可行解(几何解释)对于标准形而言，当极点仅对应一个基时，是非退化的；当极点对应多个基时，是退化的。退化的线性规划－退化的基本可行解(几何解释)676.单纯形法的矩阵形式给定基B

及对应BFS(xB,0),其中xB=B-1b用非基变量表示目标函数：用非基变量表示基变量：相对费用向量6.单纯形法的矩阵形式给定基B及对应BFS(xB,68初始表格－单纯形表初始表格通常不是单纯形表！与基矩阵B

对应的单纯形表初始表格－单纯形表初始表格与基矩阵B对应的单纯形表697.修正单纯形法(Revisedsimplexmethod)◎重要事实：⊙通常仅有少数列发生转轴(2m-3m)◎

核心问题：如何更新当前基的逆→新基的逆理论上的表现表格实现⊙仅需原始数据(c,A,b)和基B

的逆矩阵7.修正单纯形法(Revisedsimplexmeth70修正单纯形法的计算步骤步2选取q满足步3计算yq=B-1aq；若步1计算。如果停；得最优解.步0给定BFS及对应的B-1。计算核心计算：B-1涉及到的计算：，停，问题无界；否则，选p满足步4更新B-1,B-1b和，返步1.修正单纯形法的计算步骤步2选取q满足步3计算71基的转换定理左乘该矩阵等价于对矩阵进行初等行变换！定理不妨设B=.则aq进基，ap出基后所得新基的逆这里ei

表示n

维单位向量，向量v定义为基的转换定理左乘该矩阵等价于对矩阵进行初等行变换！定理不72相关数据的更新－初等行变换设转轴元是，即aq出基，ap进基以为转轴元，转轴后即得新基对应的数据！相关数据的更新－初等行变换设转轴元是，即aq出基，73例1求解例2.3.4例1求解例2.3.474a2进基，计算y2.计算表格如下：计算a2进基，计算y2.计算表格如下：计算75a1进基，计算y1.得如下表格：a1进基，计算y1.得如下表格：76最优值：最优解：最优值：最优解：77问题.设用单纯形法求解标准形式的LP时得到如下单纯形表.还假设矩阵A的后三列形成单位矩阵1.给出由该表描述的当前基是最优的充分必要条件(依照表中的系数).2.假设该基是最优的且.找出另外一个最优基本可行解，其与该表所描述的不同.问题.设用单纯形法求解标准形式的LP时得到如下1.给出由该78假定与当前表所联系的基是最优的假设将原问题中的，给出使基保持最优的的范围.假设将原问题中的，给出使基保持最优的的范围问题.设用单纯形法求解标准形式的LP时得到如下单纯形表.还假设矩阵A的后三列形成单位矩阵假定与当前表所联系的基是最优的问题.设用单纯形法求解标准形79实用优化方法

第2章线性规划：单纯形法

刘红英理学院数学系实用优化方法

第2章线性规划：单纯形法

刘红英80线性规划：目标函数是线性的，约束条件是线性等式或不等式线性规划线性规划：目标函数是线性的，约束条件是线性规划81线性规划的历史渊源要追溯到Euler、Liebnitz、Lagrange等GeorgeDantzig,NonNeumann(Princeton)和LeonidKantorovich在1940’s创建了线性规划1947年,GeorgeDantzig于发明了单纯形法1979年，L.Khachain找到了求解线性规划的一种有效方法(第一个多项式时间算法－椭球内点法)1984年，NarendraKarmarkan发现了另一种求解线性规划的有效方法，已证明是单纯形法的强有力的竞争者(投影内点法)现在求解大规模、退化问题最有效的是原－对偶内点法线性规划的历史渊源要追溯到Euler、Liebnitz、La82线性规划单纯形法-课件83线性规划单纯形法-课件84线性规划单纯形法-课件85◎问题：确定食品数量，满足营养需求，花费最小？◎变量：n种食品，m种营养成份；－第j种食品的单价－每单位第j种食品所含第i种营养的数量

－食用第j种食品的数量－为了健康，每天必须食用第i种营养的数量◎模型：例1.食谱问题◎问题：确定食品数量，满足营养需求，花费最小？◎变量：n86例2.运输问题产销平衡/不平衡的运输问题例2.运输问题产销平衡/不平衡的运输问题87

例3.目标值带绝对值的问题

假设：事实：转化为：

例3.目标值带绝对值的问题

假设：事实：转化为：88

例4.其它应用

数据包络分析(dataenvelopeanalysis,DEA)网络流问题(Networkflow)博弈论(gametheory)等

例4.其它应用

数据包络分析(dataenvelope89线性规划的一般形式线性规划的一般形式90线性规划的标准形(分析、算法)*****标准形的特征：极小化、等式约束、变量非负向量表示：线性规划的标准形(分析、算法)*****标准形的特征：极小化91一般形式标准形转化称

松弛(slack)/盈余(surplus)变量一般形式标准形转化称松弛(slack)/盈余(92例5.化成标准形等价表示为例5.化成标准形等价表示为93定义设B是A的m个线性无关列组成的矩阵.置所有与B无关列对应的变量为零，称所得方程组的解是Ax=b的基本解(basicsolution)称B是基(basis)；称与B对应的变量为基变量(basicvariables)基本解与基变量(*****)其中满秩假定：m<n，且A的行向量线性无关定义设B是A的m个线性无关列组成的矩阵.置所有与B无94基本可行解定义称的非负基本解是标准形的基本可行解(basicfeasiblesolution)；例6.基本可行解及几何意义基本可行解的个数不超过基本可行解定义称的非负基本解是标准形的基本可行解95线性规划的基本定理(*****)i)若有可行解，则必存在基本可行解；ii)若有解，则必有某个基本可行解是最优解.考虑线性规划标准形，其中A是秩为m的m×n阶矩阵，则以下结论成立：线性规划的基本定理(*****)i)若有可行解，则必存在基96与凸性的关系线性规划的基本定理(标准形)基本可行解线性方程组的基本性质代数理论(与表述形式有关)设计算法极点凸集理论几何理论(与表述形式无关)直观理解与凸性的关系线性规划的基本定理(标准形)基本可行解线性方程组97凸性(凸集及性质)几何解释：连接集合中任两点的线段仍含在该集合中性质定义是凸集(convexset)，如果对S中任意两点x,y和(0,1)中的任一数满足凸性(凸集及性质)几何解释：连接集合中任两点的线段仍含在该集98一些重要的凸集有限个闭半空间的交集多面集(polyhedralconvexset):推广平面上：多边形注：任一线性规划的可行集是多面集！超平面(hyperplane):正/负闭半空间：一些重要的凸集有限个闭半空间的交集多面集(polyhedra99极点几何上：极点即不能位于连接该集合中其它两点的开线段上的点定义称凸集C中的点x是C的极点，如果存在C中的点y,z和某，有则必有y=z.极点几何上：极点即不能位于连接该集合中其它两点的开线段上的点100极点与基本可行解的等价性定理推论：线性规划基本定理的几何形式i)若K非空，则至少有一个极点.ii)若线性规划有解，则必有一个极点是最优解.iii)K的极点是有限集.

考虑线性规划标准形，其中A是秩为m的m×n矩阵，令则x是K

的极点当且仅当x是线性规划的基本可行解.极点与基本可行解的等价性定理推论：线性规划基本定理的i)若101例2.

K有2个极点有3个基本解，2个可行K有3个极点有3个基本解，均可行例1.例2.K有2个极点有3个基本解，2个可行K有3个极点有102例3.Subjectto5个极点－极点问题/作业考虑集合证明这两个集合的极点是一一对应的！例3.Subjectto5个极点－极点问题/作业考虑集合103线性规划问题解的几种情况线性规划问题解的几种情况104线性规划解的几何特征唯一解(顶点)！线性规划解的唯一解(顶点)！105顶点一条边无(下)界顶点一条边无(下)界106线性规划解的几何特征无界：没有有限最优解不可行：没有可行解无解可行集：多边形(二维)→多边集(高维空间)给出有效的代数刻画和严谨的几何描述，从理论上证实上述几何特征，并寻求有效算法有解：唯一解/多个解(整条边、面、甚至整个可行集)有顶点解线性规划解的几何特征无界：没有有限最优解无解可行集：多边形(107单纯形法简介适用形式：标准形(基本可行解=极点)理论基础：线性规划的基本定理！基本思想：从约束集的某个极点/BFS开始，依次移动到相邻极点/BFS，直到找出最优解，或判断问题无界.初试化：如何找到一个BFS？判断准则：何时最优？何时无界？迭代规则：如何从一个极点/BFS迭代到相邻极点/BFS？单纯形法简介适用形式：标准形(基本可行解=极点)初试化：如何1081.转轴(基本解→相邻基本解)满秩假定：A是行满秩的1.转轴(基本解→相邻基本解)满秩假定：109规范形(canonicalform)基本解基变量非基变量等价变形不妨设线性无关一般地：次序可以打乱！只要有m个单位列规范形(canonicalform)基本解基变量非基变量等110规范形的转换问题⊙什么时候可以替换？⊙替换后新规范形是什么？◎替换问题假设在上述规范形中，想用规范形的转换问题⊙什么时候可以替换？⊙替换后新规范形是什111转轴(pivot)◎当且仅当，可以替换◎替换后，新规范形的系数转轴公式－转轴元(pivotelement)第二种解释：表格中第i列的数据－用当前基表示ai时的系数转轴(pivot)◎当且仅当，可以替换◎替换后112转轴例1.求下列方程组以为基变量的基本解转轴例1.求下列方程组以为基变量的基本解113转轴转轴转轴x=(0,0,0,4,2,1)转轴转轴转轴x=(0,0,0,4,2,1)114如何得到第一个规范形处理：给表格附加m个单位列向量开始迭代，用A中的列依次替换这些单位列向量以下运算同例1!例2.

利用转轴解方程组为了得到第一个规范形，形成增广表格如何得到第一个规范形处理：给表格附加m个单位列向量开始迭代，1152.BFS→相邻BFS(极点→相邻极点)◎问题：确定出基变量，使转轴后新规范形对应BFS？设x是BFS,且规范形如前，且假设

aq进基因为令可否选取合适的使得是BFS？所以2.BFS→相邻BFS(极点→相邻极点)◎问题：确定出基变116确定离基变量至少有一个正元确定离基变量至少有一个正元117例3.

考虑线性方程组a4进基转轴B=(a1,a2,a3)X=(4,3,1,0,0,0)a1进基x=(0,1,3,2,0,0)例3.考虑线性方程组a4进基转轴B=(a1,a2,a3)a1183.BFS→目标值减小的相邻BFS⊙将Ax=b的任一解用非基变量表示；设x是BFS，且规范形如前，则有◎问题：确定进基变量，转轴后使新BFS的目标值变小？用非基变量表示.——选取进基变量的依据⊙将目标函数3.BFS→目标值减小的相邻BFS⊙将Ax=b的任一解用119相对/既约费用系数(relative/reducedcostcoefficients)将Ax=b

的任一解x用非基变量表示为相对/既约费用系数(relative/reducedcos120确定进基变量◎最优性定理◎定理(BFS的提高)◎相对费用系数的经济解释！(合成价格、相对价格)给定目标值为z0的非退化基本可行解，且假定存在j使得rj<0，则

i)如果用aj替换基中某列得到了新的BFS，则新解处的目标值比z0严格小.

ii)如果任何替换都产生不了新的BFS，则问题无界.

◆退化基本可行解：某个或某些基变量取零的基本可行解！问题：基本可行解与基的对应关系？确定进基变量◎最优性定理◎定理(BFS的提高)◎相对费用系数1214.计算过程－单纯形法单纯形表：BFS对应规范形的表格＋既约费用系数和BFS目标值的相反数单纯形表可以提供计算所需的所有信息！4.计算过程－单纯形法单纯形表：BFS对应规范形的表格＋单122如何得到第一张单纯形表◎用转轴运算(初等行变换)将最后一行与基变量对应的元素化为零，即得第一张单纯形表！◎初始表格：BFS对应规范形的表格＋[c0]如何得到第一张单纯形表◎用转轴运算(初等行变换)将◎初始123例1.

化标准形转轴得标准形的初始表格/第一张单纯形表例1.化标准形转轴得标准形的初始表格/第一张单纯形表124转轴0↓-2↓-4↓-27/5转轴转轴0转轴125最优解：最优值：原问题的极大值：最优解：最优值：原问题的极大值：126单纯形法的步骤步0形成与初始BFS对应的初始表格.通过行变换求出第一张单纯形表.步1若对每个j都有，停；当前BFS是最优的.步2选取q满足步4以为转轴元进行转轴，更新单纯形表，返步1.步3若，停，问题无界；否则，选p满足转轴规则：进基变量：最小相对费用系数规则；出基变量：最小指标规则！单纯形法的步骤步0形成与初始BFS对应的初始表格.步1127单纯形法的收敛性◎非退化线性规划：任一基本可行解非退化

对非退化线性规划，从任一基本可行解出发，利用单纯形法可在有限步内得到最优解或判断问题无界.◎收敛性定理：单纯形法的收敛性◎非退化线性规划：任一基本可行解非退化1285.如何启动单纯形法－人工变量◎目标判断Ax=b,x≥0是否有界；有解时找一个基本可行解；⊙给有需要的行乘以-1，使得b≥0◎方法(x,y)=(0,b)是基本可行解！故可以(0,b)为初始BFS，利用单纯形法求解辅助问题假设最后得最优解(x,y)、最优值z*和最优基B⊙构造辅助问题人工变量5.如何启动单纯形法－人工变量◎目标判断Ax=b129得到原问题的基本可行解◎z*>0，无可行解！◎z*=0，有可行解！⊙基变量中无人工变量→x

是BFS，B是对应的基⊙基变量中有人工变量→驱赶人工变量出基假设第i个基变量是人工变量，且当前单纯形表第i行的前n个数据是第i个约束冗余；删除单纯形表的第i

行数据以任一非零元为转轴元转轴得辅助问题的一个新最优BFS，且基变量中少1个人工变量！得到原问题的基本可行解◎z*>0，无可行解！◎z*=130例1.

给出下面系统的一个基本可行解，或者说明其无解引入人工变量目标：辅助问题的初始表格！BFS例1.给出下面系统的一个基本可行解，或者说明其无解引入人工131第一张单纯形表第二张单纯形表第一张第二张132辅助问题的最优值是0.原问题的BFS：辅助问题的最优值是0.原问题的BFS：133例2.

利用两阶段法求解下面的问题辅助问题第I阶段：例2.利用两阶段法求解下面的问题辅助问题第I阶段：134辅助问题的最后一张单纯形表原问题的初始表格：辅助问题的最后一张单纯形表原问题的初始表格：135原问题的最优解：原问题的最优解：136两阶段法－可求任一线性规划问题◎第I阶段：启动单纯形法

→构造、求解辅助问题→判断原问题不可行、或可行

→可行时找到基本可行解及对应规范形⊙第II阶段：利用单纯形法求原问题

→从上述BFS出发，求解所给问题

→原问题无界或者有解两阶段法－可求任一线性规划问题◎第I阶段：启动单纯形法137退化(degenerate)与循环(cycling)◎退化问题⊙单纯形法可能出现循环！⊙实际中经常碰到退化问题，但很少出现循环⊙避免出现循环的措施：摄动法、Bland法则、字典序法

基本可行解是退化的当且仅当单纯形表最后一列有一个或者多个零！一次转轴是退化的当且仅当目标函数没有发生变化！退化(degenerate)与循环(cycling)◎退化问138最小系数规则：◎进基变量：最小系数规则◎出基变量：最小指标规则循环的例子Beale循环定义：从某张单纯形表开始返回到该单纯形表的一串转轴转轴规则：选取进基变量和离基变量的明确规则(可以选时！)最小系数规则：◎进基变量：最小系数规则循环的例子Beale139线性规划单纯形法-课件140线性规划单纯形法-课件141

循环！注：循环转轴序列中所有BFS都是退化的！是同一个BFS！第七张单纯形表循环！注：循环转轴序列中所有BFS都是退化的！是同一个BF142避免循环的方法⊙能进基的变量(使目标值减小)中选指标最小者进基◎摄动法(Dantzig，1954年)◎

Bland法则(Bland,1977)－最小指标法则◎字典序法(Orden和Wolfe，1954年)⊙能出基的变量(保持可行)中选指标最小者出基美好愿望：构造某种永远不会产生循环的转轴规则！避免循环的方法⊙能进基的变量(使目标值减小)中选指标最小者进143前四张