最优化方法线性规划单纯形法

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

－食用第j种食品的数量－为了健康，每天必须食用第i种营养的数量◎模型：例1.食谱问题第七页，共七十四页，2022年，8月28日例2.运输问题产销平衡/不平衡的运输问题第八页，共七十四页，2022年，8月28日

例3.其它应用

数据包络分析(dataenvelopeanalysis,DEA)网络流问题(Networkflow)博弈论(gametheory)等第九页，共七十四页，2022年，8月28日线性规划的一般形式第十页，共七十四页，2022年，8月28日线性规划的标准形(分析、算法)标准形的特征：极小化、等式约束、变量非负向量表示：第十一页，共七十四页，2022年，8月28日一般形式标准形转化称松弛(slack)/盈余(surplus)变量；自由变量第十二页，共七十四页，2022年，8月28日例5.化成标准形等价表示为第十三页，共七十四页，2022年，8月28日定义：给定含有n个变量，m个方程的线性方程组Ax=b，设B是由A的列组成的任一非奇异m×m子阵，则如果置x的所有与B无关的n-m个分量为零后，所得方程组的解是Ax=b关于基B的基本解(basicsolution)，称x中与基B对应的分量为基变量(basicvariables)退化基本解：基本解中如果有一个或多个基变量的值为零基本解与基变量其中满秩假定：m×n矩阵A满足m<n，且A的行向量线性无关在满秩假定下，方程组Ax=b总有解，且至少有一个基本解第十四页，共七十四页，2022年，8月28日基本可行解定义称的非负基本解是标准形的基本可行解(basicfeasiblesolution)；约束系统第十五页，共七十四页，2022年，8月28日线性规划的基本定理i)若标准型有可行解，则必有基本可行解；ii)若标准型有最优解，则必有最优基本可行解。

考虑线性规划标准形，其中A是秩为m的m×n阶矩阵，则以下结论成立：基本可行解的个数不超过第十六页，共七十四页，2022年，8月28日与凸性的关系线性规划的基本定理(标准形)基本可行解线性方程组的基本性质代数理论(与表述形式有关)设计算法极点凸集理论几何理论(与表述形式无关)直观理解第十七页，共七十四页，2022年，8月28日凸性(凸集及性质)几何解释：连接集合中任两点的线段仍含在该集合中性质

定义是凸集(convexset)，如果对S中任意两点x,y和(0,1)中的任一数满足第十八页，共七十四页，2022年，8月28日一些重要的凸集有限个闭半空间的交集多面集(polyhedralconvexset):推广平面上：多边形注：任一线性规划的可行集是多面集！超平面(hyperplane):正/负闭半空间：第十九页，共七十四页，2022年，8月28日极点几何上：极点即不能位于连接该集合中其它两点的开线段上的点定义称凸集C中的点x是C的极点，如果存在C中的点y,z和某，有则必有y=z.第二十页，共七十四页，2022年，8月28日极点与基本可行解的等价性定理推论：i)若K非空，则至少有一个极点.ii)若线性规划有最优解，则必有一个极点是最优解.iii)Ax=b对应的约束集K最多有有限个极点.

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

的极点，当且仅当x是线性规划的基本可行解.（线性规划基本定理的几何形式）第二十一页，共七十四页，2022年，8月28日例2.

K

有2个极点有3个基本解，2个可行K有3个极点有3个基本解，均可行例1.第二十二页，共七十四页，2022年，8月28日例3.Subjectto5个极点－极点第二十三页，共七十四页，2022年，8月28日线性规划解的几何特征唯一解(顶点)！第二十四页，共七十四页，2022年，8月28日线性规划解的几何特征无界：没有有限最优解不可行：没有可行解无解可行集：多边形(二维)→多边集(高维空间)给出有效的代数刻画和严谨的几何描述，从理论上证实上述几何特征，并寻求有效算法有解：唯一解/多个解(整条边、面、甚至整个可行集)

有顶点解第二十五页，共七十四页，2022年，8月28日顶点一条边无(下)界第二十六页，共七十四页，2022年，8月28日线性规划问题解的几种情况第二十七页，共七十四页，2022年，8月28日单纯形法简介适用形式：标准形(基本可行解=极点)理论基础：线性规划的基本定理！基本思想：从约束集的某个极点/BFS开始，依次移动到相邻极点/BFS，直到找出最优解，或判断问题无界.初始化：如何找到一个BFS？判断准则：何时最优？何时无界？迭代规则：如何从一个极点/BFS迭代到相邻极点/BFS？第二十八页，共七十四页，2022年，8月28日1.转轴(基本解→相邻基本解)满秩假定：A是行满秩的第二十九页，共七十四页，2022年，8月28日规范形(canonicalform)基变量基本解非基变量等价变形不妨设线性无关一般地：次序可以打乱！只要有m个单位列第三十页，共七十四页，2022年，8月28日规范形的转换问题⊙什么时候可以替换？⊙替换后新规范形是什么？◎替换问题假设在上述规范形中，想用第三十一页，共七十四页，2022年，8月28日转轴(pivot)◎当且仅当，可以替换◎替换后，新规范形的系数转轴公式－转轴元(pivotelement)第三十二页，共七十四页，2022年，8月28日转轴例1.求下列方程组以为基变量的基本解第三十三页，共七十四页，2022年，8月28日转轴转轴转轴x=(0,0,0,4,2,1)第三十四页，共七十四页，2022年，8月28日2.

BFS→相邻BFS(极点→相邻极点)◎问题：确定出基变量，使转轴后新规范形对应BFS？设x是BFS,且规范形如前，且假设

aq

进基因为令可否选取合适的使得是BFS

？所以第三十五页，共七十四页，2022年，8月28日确定离基变量至少有一个正元第三十六页，共七十四页，2022年，8月28日例3.

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

的任一解x用非基变量表示为度量变量相对于给定基的费用第三十九页，共七十四页，2022年，8月28日确定进基变量◎最优性定理◎定理(BFS的提高)◎相对费用系数的经济解释！(合成价格、相对价格)

给定目标值为z0的非退化基本可行解，且假定存在j使得rj<0，则

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

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

◆退化基本可行解：某个或某些基变量取零的基本可行解！问题：基本可行解与基的对应关系？第四十页，共七十四页，2022年，8月28日4.计算过程－单纯形法单纯形表：BFS对应规范形的表格＋既约费用系数和BFS目标值的相反数第四十一页，共七十四页，2022年，8月28日单纯形法的步骤步0形成与初始BFS对应的初始表格.

通过行变换求出第一张单纯形表.步1若对每个j都有，停；当前BFS是最优的.步2选取q满足步4以为转轴元进行转轴，更新单纯形表，返步1.步3若，停，问题无界；否则，选p满足转轴规则：进基变量：最小相对费用系数规则；出基变量：最小指标规则！第四十二页，共七十四页，2022年，8月28日例1.

化标准形转轴得标准形的初始表格/第一张单纯形表第四十三页，共七十四页，2022年，8月28日转轴0↓-2↓-4↓-27/5转轴第四十四页，共七十四页，2022年，8月28日最优解：最优值：原问题的极大值：第四十五页，共七十四页，2022年，8月28日退化(degenerate)与循环(cycling)◎退化问题⊙单纯形法可能出现循环！⊙实际中经常碰到退化问题，但很少出现循环⊙避免出现循环的措施：摄动法、Bland法则、字典序法

基本可行解是退化的当且仅当单纯形表最后一列有一个或者多个零！一次转轴是退化的当且仅当目标函数没有发生变化！第四十六页，共七十四页，2022年，8月28日最小系数规则：◎进基变量：最小系数规则◎出基变量：最小指标规则循环的例子Beale循环定义：从某张单纯形表开始返回到该单纯形表的一串转轴转轴规则：选取进基变量和离基变量的明确规则第四十七页，共七十四页，2022年，8月28日第四十八页，共七十四页，2022年，8月28日第四十九页，共七十四页，2022年，8月28日

循环！注：循环转轴序列中所有BFS都是退化的！是同一个BFS！第七张单纯形表第五十页，共七十四页，2022年，8月28日避免循环的方法⊙如果有多个费用系数是负的，选取下标最小的相对费用系数对应的变量为进基变量◎摄动法(Charnes，1952年)◎

Bland法则(Bland,1977)－最小指标法则◎字典序法(Dantzig,

Orden和Wolfe，1954年)⊙如果最小正比值在多个指标处取得，取下标最小者对应的变量为进基变量美好愿望：构造某种永远不会产生循环的转轴规则！第五十一页，共七十四页，2022年，8月28日前四张单纯形表相同！利用Bland法则作为转轴规则求解Beale的例子！第五十二页，共七十四页，2022年，8月28日最后一张单纯形表/最优单纯形表第五十三页，共七十四页，2022年，8月28日单纯形法的收敛性◎

非退化线性规划：任一基本可行解非退化

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

基变量中无人工变量→x

是BFS，B是对应的基⊙

基变量中有人工变量→驱赶人工变量出基假设第i个基变量是人工变量，且当前单纯形表第i行的前n个数据是第i

个约束冗余；删除单纯形表的第i

行数据以任一非零元为转轴元转轴得辅助问题的一个新最优BFS，且基变量中少1个人工变量！第五十六页，共七十四页，2022年，8月28日例1.

给出下面系统的一个基本可行解，或者说明其无解引入人工变量目标：辅助问题的初始表格！BFS第五十七页，共七十四页，2022年，8月28日第一张单纯形表第二张单纯形表注意基变量整列包括末行z在内除了基变量其他元素都是0第五十八页，共七十四页，2022年，8月28日辅助问题的最优值是0.原问题的BFS：第五十九页，共七十四页，2022年，8月28日两阶段法－可求任一线性规划问题◎

第I阶段：启动单纯形法

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

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

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

→原问题无界或者有解第六十页，共七十四页，2022年，8月28日例2.

利用两阶段法求解下面的问题辅助问题第I阶段：先构造辅助向量z=x4+x5第六十一页，共七十四页，2022年，8月28日辅助问题的最后一张单纯形表原问题的初始表格：得到辅助问题的最后一张单纯形表后，去掉辅助变量，将原始问题的z带入表格，启动单纯形法第六十二页，共七十四页，2022年，8月28日原问题的最优解：第六十三页，共七十四页，2022年，8月28日6.修正单纯形法(Revisedsimplexmethod)◎重要事实：⊙通常仅有少数列发生转轴(2m-3m)◎

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

的逆矩阵第六十四页，共七十四页，2022年，8月28日7.单纯形法的矩阵形式给定基B

及对应BFS(xB,0),其中xB=B-1b用非基变量表示目标函数：用非基变量表示基变量：相对费用向量第六十五页，共七十四页，2022年，8月28日初始表格－单纯形表初始表格通常不是单纯形表！与基矩阵B

对应的单纯形表第六十六页，共七十四页，2022年，8月28日修正单纯形法的计算步骤步2选取q满足步3计算yq=B