最优化方法线性规划单纯形法学习教案.pptx

会计学1最优化方法最优化方法(fngf)线性规划单纯形法线性规划单纯形法第一页，共77页。线性规划：目标线性规划：目标(mbio)函数是线性的，约束条件是函数是线性的，约束条件是线性等式或不等式线性等式或不等式线性规划线性规划(xin xn u hu)第1页/共77页第二页，共77页。线性规划线性规划线性规划线性规划(xin(xin xnxn u hu)u hu)的历的历的历的历史史史史n n渊源要追溯到渊源要追溯到渊源要追溯到渊源要追溯到EulerEuler、LiebnitzLiebnitz、LagrangeLagrange等等等等n nGeorge Dantzig,Von Neumann(Princeton)George Dantzig,Von Neumann(Princeton)和和和和Leonid Leonid KantorovichKantorovich在在在在1940s1940s创建了线性规划创建了线性规划创建了线性规划创建了线性规划n n19471947年年年年,George Dantzig,George Dantzig发明了单纯形法发明了单纯形法发明了单纯形法发明了单纯形法n n19791979年，年，年，年，L.KhachainL.Khachain找到了求解线性规划的一种有效方找到了求解线性规划的一种有效方找到了求解线性规划的一种有效方找到了求解线性规划的一种有效方法法法法(第一个多项式时间算法椭球内点法第一个多项式时间算法椭球内点法第一个多项式时间算法椭球内点法第一个多项式时间算法椭球内点法)n n19841984年，年，年，年，Narendra KarmarkanNarendra Karmarkan发现了另一种求解线性规发现了另一种求解线性规发现了另一种求解线性规发现了另一种求解线性规划的有效方法，已证明是单纯形法的强有力的竞争者划的有效方法，已证明是单纯形法的强有力的竞争者划的有效方法，已证明是单纯形法的强有力的竞争者划的有效方法，已证明是单纯形法的强有力的竞争者(投投投投影内点法影内点法影内点法影内点法)n n现在现在现在现在(xinzi)(xinzi)求解大规模、退化问题最有效的是原对求解大规模、退化问题最有效的是原对求解大规模、退化问题最有效的是原对求解大规模、退化问题最有效的是原对偶内点法偶内点法偶内点法偶内点法第2页/共77页第三页，共77页。第3页/共77页第四页，共77页。第4页/共77页第五页，共77页。第5页/共77页第六页，共77页。问题：确定食品数量，满足问题：确定食品数量，满足(mnz)营养需求，花费营养需求，花费最小？最小？变量变量(binling)：n种食品，种食品，m种营养成份；第种营养成份；第 j 种食品的单价种食品的单价每单位第每单位第 j 种食品所含第种食品所含第 i 种营养的数量种营养的数量食用第食用第 j 种食品的数量种食品的数量为了健康，每天必须食用第为了健康，每天必须食用第i 种营养的数量种营养的数量 模型模型(mxng)：例例例例1.1.1.1.食谱问题食谱问题食谱问题食谱问题第6页/共77页第七页，共77页。例例2.运输运输(ynsh)问题问题产销平衡产销平衡/不平衡的运输不平衡的运输(ynsh)问题问题第7页/共77页第八页，共77页。例例例例3.3.其它其它其它其它(qt)(qt)应用应用应用应用n n数据包络分析数据包络分析(data envelope(data envelope analysis,DEA)analysis,DEA)n n网络网络(wnglu)(wnglu)流问题流问题(Network(Network flow)flow)n n博弈论博弈论(game theory)(game theory)等等第8页/共77页第九页，共77页。线性规划线性规划(xin xn u hu)的一般形式的一般形式第9页/共77页第十页，共77页。线性规划的标准形线性规划的标准形(分析分析(fnx)、算、算法法)标准形的特征标准形的特征(tzhng)：极小化、等式约束、：极小化、等式约束、变量非负变量非负向量表示：向量表示：第10页/共77页第十一页，共77页。一般一般(ybn)形式形式 标准标准形形转化转化称称 松弛松弛(slack)/盈余盈余(surplus)变量；变量；自由自由(zyu)变变量量第11页/共77页第十二页，共77页。例例例例5.5.5.5.化成化成化成化成(hu(hu(hu(hu chn)chn)chn)chn)标准形标准形标准形标准形等等价价表表示示为为第12页/共77页第十三页，共77页。定义：定义：给定含有给定含有n个变量个变量(binling)，m个方程的线性方程个方程的线性方程组组Ax=b，设，设B是由是由A 的列组成的任一非奇异的列组成的任一非奇异mm子阵，则如子阵，则如果置果置x的所有与的所有与B无关的无关的n-m个分量为零后，所得方程组的解是个分量为零后，所得方程组的解是Ax=b关于基关于基B的基本解的基本解(basic solution)，称，称x中与基中与基B对应的对应的分量为基变量分量为基变量(binling)(basic variables)退化基本解：基本解中如果有一个或多个基变量退化基本解：基本解中如果有一个或多个基变量(binling)的的值为零值为零基本基本(jbn)解与基变解与基变量量其中其中满秩假定：满秩假定：mn矩阵矩阵A满足满足mn，且，且A的行向量线性无关的行向量线性无关 在满秩假定下，方程组在满秩假定下，方程组Ax=b总有解，且至少有一个总有解，且至少有一个(y)基本基本 解解第13页/共77页第十四页，共77页。基本基本(jbn)可可行解行解定义定义 称称 的非负基本解是的非负基本解是标准形标准形的的基本可行解基本可行解(basic feasible solution)；约束约束(yush)(yush)系统系统 第14页/共77页第十五页，共77页。线性规划线性规划(xin xn u hu)的基本定理的基本定理i)若标准型有可行若标准型有可行(kxng)解，则必有基本可行解，则必有基本可行(kxng)解；解；ii)若标准型有最优解，则必有最优基本若标准型有最优解，则必有最优基本(jbn)可行解。可行解。考虑线性规划标准形，其中考虑线性规划标准形，其中A是秩为是秩为m的的mn阶阶矩阵，则以下结论成立：矩阵，则以下结论成立：基本可行解的个数基本可行解的个数不超过不超过第15页/共77页第十六页，共77页。与凸性的关系与凸性的关系(gun x)线性规划线性规划(xin xn u hu)(xin xn u hu)的的基本定理基本定理(标准形标准形)基本可行解基本可行解线性方程组线性方程组的基本性质的基本性质代数理论代数理论(与与表述形式有关表述形式有关)设计算法设计算法极点极点凸集理论凸集理论几何理论几何理论(与表述形式与表述形式无关无关)直观理解直观理解第16页/共77页第十七页，共77页。凸性凸性(凸集及性质凸集及性质(xngzh)(xngzh)几何解释几何解释(jish)：连接集合中任两点的线段仍含在该集合中：连接集合中任两点的线段仍含在该集合中性质性质 定义定义 是凸集是凸集(convex set)，如果对，如果对S中任意中任意 两两 点点 x,y 和和(0,1)中的任一数中的任一数 满足满足第17页/共77页第十八页，共77页。一些一些(yxi)(yxi)重要重要的凸集的凸集有限个闭半空间的交集有限个闭半空间的交集多面集多面集(polyhedral convex set):推推广广平面上：多边形平面上：多边形注：任一线性规划注：任一线性规划(xin xn u hu)的可行的可行集是多面集！集是多面集！超平面超平面(hyperplane):正正/负闭半空间：负闭半空间：第18页/共77页第十九页，共77页。极点极点(jd(jdin)in)几何上：极点即不能位于几何上：极点即不能位于(wiy)连接该集合中其它连接该集合中其它两点的开线段上的点两点的开线段上的点定义定义 称凸集称凸集C中的点中的点 x 是是C的极点，如果存在的极点，如果存在 C 中中的点的点 y,z 和某和某 ，有，有则必有则必有 y=z.第19页/共77页第二十页，共77页。极点与基本可行极点与基本可行(kxng)(kxng)解的等价性定解的等价性定理理推论推论(tuln)：i)若若K非空，则至少有一个非空，则至少有一个(y)极极点点.ii)若线性规划有最优解，则必有一个极点是最优解若线性规划有最优解，则必有一个极点是最优解.iii)Ax=b对应的约束集对应的约束集K最多有有限个极点最多有有限个极点.考虑线性规划标准形，其中考虑线性规划标准形，其中A是秩为是秩为m的的mn矩阵，令矩阵，令则则x是是 K 的极点，的极点，当且仅当当且仅当x是线性规划的基本可行解是线性规划的基本可行解.（线性规划基本定理的几何形式）（线性规划基本定理的几何形式）第20页/共77页第二十一页，共77页。例例2.2.K有有2个极点个极点有有3个基本解，个基本解，2个个可行可行K 有有3个极点个极点有有3个基本解，个基本解，均可行均可行例例1.1.第21页/共77页第二十二页，共77页。例例3.3.Subject to5个极点个极点极点极点第22页/共77页第二十三页，共77页。线性规划线性规划(xin xn u hu)解解的的几何特征几何特征唯一唯一(wi y)解解(顶点顶点)！第23页/共77页第二十四页，共77页。线性规划解的几何线性规划解的几何(j h)特征特征n n无界：没有有限无界：没有有限(yuxin)(yuxin)最优解最优解n n不可行：没有可行解不可行：没有可行解无解无解可行可行(kxng)(kxng)集：多边形集：多边形(二维二维)多边集多边集(高维空间高维空间)给出给出有效的代数刻画有效的代数刻画和和严谨的几何描述严谨的几何描述，从理论上证实上述，从理论上证实上述几何特征，并几何特征，并寻求有效算法寻求有效算法有解：有解：唯一解唯一解/多个解多个解(整条边、面、甚至整条边、面、甚至整个可行集整个可行集)有顶点解有顶点解第24页/共77页第二十五页，共77页。顶点顶点一一条条边边无无(下下)界界第25页/共77页第二十六页，共77页。线性规划问题解的几种线性规划问题解的几种(j zhn)情况情况第26页/共77页第二十七页，共77页。单纯形法简介单纯形法简介单纯形法简介单纯形法简介(ji(ji n ji)n ji)n n适用形式：标准形适用形式：标准形(基本可行解基本可行解=极点极点)n n理论基础：线性规划的基本定理论基础：线性规划的基本定理理(dngl)！n n基本思想：从约束集的某个极基本思想：从约束集的某个极点点/BFS开始，依次移动到相邻开始，依次移动到相邻极点极点/BFS，直到找出最优解，直到找出最优解，或判断问题无界或判断问题无界.初始化：如何找到一个初始化：如何找到一个BFS？判断判断(pndun)准则：何时最优？何时无界准则：何时最优？何时无界？迭代规则：如何从一个极点迭代规则：如何从一个极点/BFS迭代到相邻迭代到相邻极点极点/BFS？第27页/共77页第二十八页，共77页。1.转轴转轴(zhunzhu)(基本解基本解相邻基本解相邻基本解)满秩假定满秩假定(jidng)：A是行满秩的是行满秩的第28页/共77页第二十九页，共77页。规范规范(gufn)形形(canonical form)基变量基变量基本解基本解非基变量非基变量等价变形等价变形不妨设不妨设 线性无关线性无关 一般地一般地：次序可以打乱！次序可以打乱！只要有只要有m个单位列个单位列第29页/共77页第三十页，共77页。规范形的转换规范形的转换(zhunhun)问题问题 什么什么(shn me)时候时候可以替换？可以替换？替换后新规范替换后新规范(gufn)形是什么？形是什么？替换问题替换问题假设在上述规范形中，想用假设在上述规范形中，想用第30页/共77页第三十一页，共77页。转轴转轴(zhunzhu)(pivot)当且仅当当且仅当，可以替换，可以替换 替换后，新规范形的系数替换后，新规范形的系数转轴公式转轴公式转轴元转轴元(pivot element)第31页/共77页第三十二页，共77页。转轴例例1.求下列方程组以求下列方程组以 为基变量的基本解为基变量的基本解第32页/共77页第三十三页，共77页。转转轴轴转转轴轴转转轴轴x=(0,0,0,4,2,1)第33页/共77页第三十四页，共77页。2.BFS相邻相邻(xin ln)BFS(极点极点相邻相邻(xin ln)极点极点)问题问题(wnt)：确定出基变量确定出基变量(binling)，使转轴后新规范形对应，使转轴后新规范形对应BFS？设设x是是BFS,且规范形如前，且且规范形如前，且假设假设 aq 进基进基因为因为令令可否选取合适的可否选取合适的 使得使得 是是BFS？所以所以第34页/共77页第三十五页，共77页。确定确定(qudng)离基变量离基变量至少有一个正元至少有一个正元第35页/共77页第三十六页，共77页。例例3.考虑考虑(kol)线性方程线性方程组组a4进基进基转转轴轴B=(a1,a2,a3)X=(4,3,1,0,0,0)x=(0,1,3,2,0,0)第36页/共77页第三十七页，共77页。3.BFS目标值减小的相邻目标值减小的相邻(xin ln)BFS 将将Ax=b的任一解用非基变量的任一解用非基变量(binling)表示；表示；设设x是是BFS，且规范，且规范(gufn)形如前，形如前，则有则有问题：问题：确定进基变量，转轴后使确定进基变量，转轴后使新新BFS的目标值的目标值变小变小？用非基变量表示用非基变量表示.选取进基变量的依据选取进基变量的依据 将将目标函数目标函数第37页/共77页第三十八页，共77页。相对相对/既约费用既约费用(fi yong)系数系数(relative/reduced cost coefficients)将将 Ax=b 的任一解的任一解 x 用非基变量表示为用非基变量表示为度量变量度量变量(binling)相对于给定基相对于给定基的费用的费用第38页/共77页第三十九页，共77页。确定确定(qudng)进基变量进基变量最优性定理最优性定理(dngl)定理定理(dngl)(BFS的提的提高高)相对费用系数的相对费用系数的经济解释经济解释！(合成价格、相对价格合成价格、相对价格)给定目标值为给定目标值为z0的的非退化非退化基本可行解，且假定存基本可行解，且假定存在在 j 使得使得 rj 0，无可行，无可行(kxng)解！解！z*=0，有可行，有可行(kxng)解！解！基变量中基变量中无无人工变量人工变量x 是是BFS，B 是对应的基是对应的基 基变量中基变量中有有人工变量人工变量驱赶人工变量出基驱赶人工变量出基假设第假设第 i 个基变量是人工变量，且当前单纯形表个基变量是人工变量，且当前单纯形表第第 i 行的前行的前n个数据是个数据是第第 i 个约束冗余；个约束冗余；删除单纯形表的第删除单纯形表的第 i 行数行数据据以以任一非零元任一非零元为转轴元转轴为转轴元转轴得辅助问题的一个新最优得辅助问题的一个新最优BFS，且基变量中少，且基变量中少1个人工变量！个人工变量！第55页/共77页第五十六页，共77页。例例1.给出下面系统的一个基本可行解，或者给出下面系统的一个基本可行解，或者(huzh)说明其无解说明其无解引入引入人工人工变量变量目标目标：辅助问题辅助问题的的初始表初始表格格！BFS第56页/共77页第五十七页，共77页。第一张第一张单纯形表单纯形表第二张第二张单纯形表单纯形表注意(zh y)基变量整列包括末行z在内除了基变量其他元素都是0第57页/共77页第五十八页，共77页。辅助辅助(fzh)(fzh)问题的最优值问题的最优值是是0.0.原问题原问题(wnt)(wnt)的的BFSBFS：第58页/共77页第五十九页，共77页。两阶段法可求任一线性规划两阶段法可求任一线性规划(xin xn u hu)问题问题 第第第第I I阶段：启动单纯形法阶段：启动单纯形法阶段：启动单纯形法阶段：启动单纯形法 构造、求解辅助问题构造、求解辅助问题构造、求解辅助问题构造、求解辅助问题 判断原问题不可行、或可行判断原问题不可行、或可行判断原问题不可行、或可行判断原问题不可行、或可行 可行时找到基本可行解及对应规范形可行时找到基本可行解及对应规范形可行时找到基本可行解及对应规范形可行时找到基本可行解及对应规范形 第第第第IIII阶段：利用单纯形法求原问题阶段：利用单纯形法求原问题阶段：利用单纯形法求原问题阶段：利用单纯形法求原问题 从上述从上述从上述从上述BFSBFS出发出发出发出发(chf)(chf)，求解所给问题，求解所给问题，求解所给问题，求解所给问题 原问题无界或者有解原问题无界或者有解原问题无界或者有解原问题无界或者有解第59页/共77页第六十页，共77页。例例2.利用两阶段法求解利用两阶段法求解(qi ji)下下面的问题面的问题辅助问题辅助问题第第I阶段：阶段：先构造辅助(fzh)向量z=x4+x5第60页/共77页第六十一页，共77页。辅助问题的辅助问题的最后一张单纯形表最后一张单纯形表原问题的原问题的初始初始表格：表格：得到辅助问题(wnt)的最后一张单纯形表后，去掉辅助变量，将原始问题(wnt)的z带入表格，启动单纯形法第61页/共77页第六十二页，共77页。原问题的原问题的最优解最优解：第62页/共77页第六十三页，共77页。6.修正修正(xizhng)单纯形法单纯形法(Revised simplex method)重要重要(zhngyo)事实：事实：通常通常(tngchng)仅有少数列发生转仅有少数列发生转轴轴(2m-3m)核心问题：核心问题：如何更新如何更新当前基的逆当前基的逆新基的逆新基的逆理论上的表现理论上的表现表格实现表格实现 仅需原始数据仅需原始数据(c,A,b)和基和基 B 的逆矩阵的逆矩阵第63页/共77页第六十四页，共77页。7.单纯形法的矩阵单纯形法的矩阵(j zhn)形式形式给定基给定基 B 及对应及对应(duyng)BFS(xB,0),其中其中xB=B-1b用用非基非基变量表示变量表示目标函数目标函数：用用非基非基变量表示变量表示基基变量：变量：相对相对费用向量费用向量第64页/共77页第六十五页，共77页。初始初始(ch sh)表格单表格单纯形表纯形表初始表格初始表格通常通常(tngchng)不是不是单纯形表！单纯形表！与基矩阵与基矩阵 B 对应的对应的单纯形表单纯形表第65页/共77页第六十六页，共77页。修正单纯形法的计算修正单纯形法的计算(j sun)步骤步骤步步2 选取选取 q 满足满足步步3 计算计算(j sun)yq=B-1aq；若；若步步1 计算计算 。如果。如果 停；得最优解停；得最优解.步步0 给定给定BFS及对应的及对应的B-1。计算。计算核心核心(hxn)计算：计算：B-1涉及涉及到的计算：到的计算：，停，停，问题问题无界无界；否则，选；否则，选 p 满足满足步步4 更新更新 B-1,B-1b和和 ，返步，返步1.第66页/共77页第六十七页，共77页。基的转换基的转换(zhunhun)定理定理左乘该矩阵等价于对矩阵进行左乘该矩阵等价于对矩阵进行(jnxng)初等行变初等行变换！换！定理定理 不妨设不妨设B=.则则 aq 进基，进基，ap出基后所得新基出基后所得新基 的逆的逆这里这里 ei 表示表示n 维单位向量，向量维单位向量，向量 v 定义定义为为第67页/共77页第六十八页，共77页。相关数据的更新初等相关数据的更新初等(chdng)行变换行变换设设转轴元转轴元是，即是，即 aq 出基，出基，ap进基进基以为转轴元，以为转轴元，转轴后转轴后即得新基对应的数据！即得新基对应的数据！第68页/共77页第六十九页，共77页。例例1第69页/共77页第七十页，共77页。a2进基，计算进基，计算(j sun)y2.计算计算(j sun)表格如下：表格如下：计算计算第70页/共77页第七十一页，共77页。a1进基，计算进基，计算(j sun)y1.得如下表格：得如下表格：第71页/共77页第七十二页，共77页。最优值：最优值：最优解：最优解：第72页/共77页第七十三页，共77页。利用两阶段单纯形过程(guchng)求解第73页/共77页第七十四页，共77页。第74页/共77页第七十五页，共77页。第75页/共77页第七十六页，共77页。第76页/共77页第七十七页，共77页。