线性规划单纯形法学习教案

1、会计学1第一页，共79页。线性规划线性规划(xin xn u hu)：目标函数是线性的，约束条件是：目标函数是线性的，约束条件是线性等式或不等式线性等式或不等式线性规划线性规划(xin xn u hu)第1页/共79页第二页，共79页。第2页/共79页第三页，共79页。第3页/共79页第四页，共79页。第4页/共79页第五页，共79页。第5页/共79页第六页，共79页。 问题：确定食品数量，满足营养问题：确定食品数量，满足营养(yngyng)需求，花需求，花费最小？费最小？ 变量变量(binling)：n种食品，种食品，m种营养成份；第种营养成份；第 j 种食品的单价种食品的单价每单位第每单位

2、第 j 种食品所含第种食品所含第 i 种营养的数量种营养的数量食用第食用第 j 种食品的数量种食品的数量为了健康，每天必须食用第为了健康，每天必须食用第i 种营养的数量种营养的数量 模型模型(mxng)：第6页/共79页第七页，共79页。产销产销(chnxio)平衡平衡/不平衡不平衡的运输问题的运输问题第7页/共79页第八页，共79页。假设假设(jish)：事实事实(shsh)：转化为：转化为：第8页/共79页第九页，共79页。第9页/共79页第十页，共79页。线性规划的一般线性规划的一般(ybn)形形式式第10页/共79页第十一页，共79页。线性规划线性规划(xin xn u hu)的标准形

3、的标准形(分析、算法分析、算法)*标准形的特征标准形的特征(tzhng)：极小化、等式约束、变：极小化、等式约束、变量非负量非负向量表示：向量表示：第11页/共79页第十二页，共79页。一般一般(ybn)形式形式 标准标准形形转化转化称称 松弛松弛(slack)/盈余盈余(surplus)变量变量第12页/共79页第十三页，共79页。等价表示为等价表示为第13页/共79页第十四页，共79页。定义定义 设设B是是A 的的m个线性无关列组成的矩阵个线性无关列组成的矩阵. 置置所有与所有与B无关列对应无关列对应(duyng)的变量为零，称所的变量为零，称所得方程组的解是得方程组的解是Ax=b的基本解

4、的基本解(basic solution) 称称B是基是基(basis)；称与称与B对应对应(duyng)的变量为基变量的变量为基变量(basic variables)基本基本(jbn)解与基变量解与基变量(*)其中其中满秩假定：满秩假定：mn，且，且A的行向量线性无关的行向量线性无关第14页/共79页第十五页，共79页。基本基本(jbn)可行解可行解定义定义 称称 的非负基本解是的非负基本解是标准形标准形的的基本可行解基本可行解( (basic feasible solution)；例例6. 6. 基本可行解及几何意义基本可行解及几何意义基本基本(jbn)(jbn)可行解的个数可行解的个数不超

5、过不超过第15页/共79页第十六页，共79页。线性规划线性规划(xin xn u hu)的的基本定理基本定理(*)i) 若有可行解，则必存在若有可行解，则必存在(cnzi)基本可行解；基本可行解；ii) 若有解，则必有某个若有解，则必有某个(mu )基本可行解是最优解基本可行解是最优解. 考虑线性规划标准形，其中考虑线性规划标准形，其中A是秩为是秩为m的的mn阶阶矩阵，则以下结论成立：矩阵，则以下结论成立：第16页/共79页第十七页，共79页。与凸性的关系与凸性的关系(gun x)线性规划线性规划(xin xn u hu)(xin xn u hu)的基本定理的基本定理( (标准形标准形) )基

6、本可行解基本可行解线性方程组线性方程组的基本性质的基本性质代数理论代数理论(与与表述形式有关表述形式有关)设计算法设计算法极点极点凸集理论凸集理论几何理论几何理论( (与表述形式与表述形式无关无关) )直观理解直观理解第17页/共79页第十八页，共79页。凸性凸性( (凸集及性凸集及性质质(xngzh)(xngzh)几何解释：连接集合几何解释：连接集合(jh)中任两点的线段仍含在该集合中任两点的线段仍含在该集合(jh)中中性质性质 定义定义 是凸集是凸集(convex set)，如果对，如果对S中任意中任意 两两 点点 x , y 和和(0,1)中的任一数中的任一数 满足满足 第18页/共79

7、页第十九页，共79页。一些一些(yxi)(yxi)重要重要的凸集的凸集有限个闭半空间的交集有限个闭半空间的交集多面集多面集(polyhedral convex set):推推广广平面上：多边形平面上：多边形注：任一线性规划注：任一线性规划(xin xn u hu)的可的可行集是多面集！行集是多面集！超平面超平面(hyperplane):正正/ /负闭半空间：负闭半空间：第19页/共79页第二十页，共79页。极点极点(jd(jdin)in)几何几何(j h)上：极点即不能位于连接该集合中其上：极点即不能位于连接该集合中其它两点的开线段上的点它两点的开线段上的点定义定义 称凸集称凸集C中的点中的点

8、 x 是是C的极点，如果存在的极点，如果存在 C 中的点中的点 y, z 和某和某 ，有，有则必有则必有 y=z.第20页/共79页第二十一页，共79页。极点与基本极点与基本(jbn)(jbn)可行解的等价性定可行解的等价性定理理推论推论(tuln)：线性规划基本定理线性规划基本定理的的几何形式几何形式i) 若若K非空，则至少有一个非空，则至少有一个(y )极点极点.ii) 若线性规划有解，则必有一个极点是最优解若线性规划有解，则必有一个极点是最优解.iii) K的极点是有限集的极点是有限集.考虑线性规划标准形，其中考虑线性规划标准形，其中A是秩为是秩为m的的mn矩阵，令矩阵，令则则x是是 K

9、 的极点的极点当且仅当当且仅当x是线性规划的基本可行是线性规划的基本可行解解.第21页/共79页第二十二页，共79页。例例2.2. K有有2个极点个极点有有3个基本解，个基本解，2个个可可行行K 有有3个极点个极点有有3个基本解，个基本解，均可行均可行例例1. 1. 第22页/共79页第二十三页，共79页。例例3. 3. Subject to5个极点个极点极点极点问题问题/ /作业作业考虑集合考虑集合证明这两个集合的极点是证明这两个集合的极点是一一对应一一对应的！的！第23页/共79页第二十四页，共79页。第24页/共79页第二十五页，共79页。线性规划线性规划(xin xn u hu)解的解

10、的几何特征几何特征唯一唯一(wi y) 解解(顶点顶点)！第25页/共79页第二十六页，共79页。顶点顶点一条边一条边无无(下下)界界第26页/共79页第二十七页，共79页。线性规划线性规划(xin xn u hu)解的几何特征解的几何特征无解无解可行可行(kxng)(kxng)集：多边形集：多边形( (二维二维) )多边集多边集( (高维空间高维空间) )给出给出有效的代数刻画有效的代数刻画和和严谨的几何描述严谨的几何描述，从理论上证实上，从理论上证实上述几何特征，并述几何特征，并寻求有效算法寻求有效算法有解有解：唯一解唯一解/ /多个解多个解( (整条边、面、甚至整个整条边、面、甚至整个可

11、行集可行集) ) 有顶点解有顶点解第27页/共79页第二十八页，共79页。初试初试(chsh)化：如何找到一个化：如何找到一个BFS？判断准则：何时最优？何时无界？判断准则：何时最优？何时无界？迭代规则：如何从一个极点迭代规则：如何从一个极点/BFS迭代到相迭代到相邻极点邻极点/BFS？第28页/共79页第二十九页，共79页。1.转轴转轴(zhunzhu)(基本解基本解相邻基本解相邻基本解)满秩假定满秩假定(jidng)：A是行满秩的是行满秩的第29页/共79页第三十页，共79页。规范规范(gufn)形形(canonical form)基本解基本解基变量基变量非基变量非基变量等价变形等价变形不

12、妨设不妨设 线性无关线性无关 一般地一般地：次序可以打乱！次序可以打乱！只要有只要有m个单位列个单位列第30页/共79页第三十一页，共79页。规范形的转换规范形的转换(zhunhun)问题问题 什么时候什么时候(sh hou)可可以替换？以替换？ 替换替换(t hun)后新规范形是什后新规范形是什么？么？ 替换问题替换问题假设在上述规范形中，想假设在上述规范形中，想用用第31页/共79页第三十二页，共79页。转轴转轴(zhunzhu)(pivot) 当且仅当当且仅当 ，可以替换，可以替换 替换后，新规范形的系数替换后，新规范形的系数转轴公式转轴公式转轴元转轴元(pivot element)第二

13、种解释：第二种解释：表格中第表格中第 i 列的数据列的数据用当前基用当前基表示表示 ai 时的时的系数系数第32页/共79页第三十三页，共79页。转轴例例1. 求下列方程组以求下列方程组以 为基变量的基本为基变量的基本解解第33页/共79页第三十四页，共79页。转轴转轴转轴转轴转轴转轴x=(0,0,0,4,2,1)第34页/共79页第三十五页，共79页。如何如何(rh)得到第一个规得到第一个规范形范形处理：处理：给表格给表格附加附加m个单位列向量个单位列向量开始开始迭代，用迭代，用A中的列中的列依次替换依次替换这些单位列向量这些单位列向量以下以下(yxi)运运算算同例同例1 !例例2. 利用转

14、轴解方程组利用转轴解方程组为了得到第一个规范形，形成增广表格为了得到第一个规范形，形成增广表格第35页/共79页第三十六页，共79页。2.BFS相邻相邻(xin ln)BFS(极点极点相邻相邻(xin ln)极点极点)问题问题(wnt)：确定出基变量确定出基变量(binling)，使转轴后新规范形对，使转轴后新规范形对应应BFS？设设x是是BFS, 且规范形如前，且且规范形如前，且假设假设 aq 进基进基因因为为令令可否选取合适的可否选取合适的 使得使得 是是BFS ？所所以以第36页/共79页第三十七页，共79页。确定确定(qudng)离基变量离基变量至少有一个正元至少有一个正元第37页/共

15、79页第三十八页，共79页。例例3. 考虑考虑(kol)线性方程线性方程组组a4进基进基转轴转轴B=(a1,a2,a3)X=(4,3,1,0,0,0)a1进基进基x=(0,1,3,2,0,0)第38页/共79页第三十九页，共79页。3. BFS目标值减小的相邻目标值减小的相邻(xin ln)BFS 将将Ax=b的任一解用非基变量的任一解用非基变量(binling)表示；表示；设设x是是BFS，且规范，且规范(gufn)形如前形如前，则有，则有问题：问题：确定进基变量，转轴后使确定进基变量，转轴后使新新BFS的目标值的目标值变小变小？用非基变量表示用非基变量表示. 选取进基变量的依据选取进基变量

16、的依据 将将目标函数目标函数第39页/共79页第四十页，共79页。相对相对/既约费用既约费用(fi yong)系数系数(relative/reduced cost coefficients)将将 Ax=b 的任一解的任一解 x 用非基变量表示为用非基变量表示为第40页/共79页第四十一页，共79页。确定确定(qudng)进基变量进基变量最优性定理最优性定理(dngl)定理定理(dngl)(BFS的提的提高高)相对费用系数的相对费用系数的经济解释经济解释！(合成价格、相对价格合成价格、相对价格) 给定目标值为给定目标值为z0的的非退化非退化基本可行解，且假定存基本可行解，且假定存在在 j 使得使

17、得 rj 0，无可行，无可行(kxng)解！解！ z*= 0，有可行，有可行(kxng)解！解！ 基变量中基变量中无无人工变量人工变量x 是是BFS，B 是对应的基是对应的基 基变量中基变量中有有人工变量人工变量驱赶人工变量出基驱赶人工变量出基假设第假设第 i 个基变量是人工变量，且当前单纯形表个基变量是人工变量，且当前单纯形表第第 i 行的前行的前n个数据是个数据是第第 i 个约束冗余；个约束冗余；删除单纯形表的第删除单纯形表的第 i 行数行数据据以以任一非零元任一非零元为转轴元转轴为转轴元转轴得辅助问题的一个新最优得辅助问题的一个新最优BFS，且基变量中少，且基变量中少1个人工变量！个人工

18、变量！第50页/共79页第五十一页，共79页。例例1. 给出下面系统给出下面系统(xtng)的一个基本可行解，或者说明其的一个基本可行解，或者说明其无解无解引入引入人工人工变量变量目标目标：辅助问题辅助问题的的初始表初始表格格！BFS第51页/共79页第五十二页，共79页。第一张第一张单纯形表单纯形表第二张第二张单纯形表单纯形表第52页/共79页第五十三页，共79页。辅助辅助(fzh)(fzh)问题的最优值问题的最优值是是0. 0. 原问题原问题(wnt)(wnt)的的BFSBFS：第53页/共79页第五十四页，共79页。例例2. 利用利用(lyng)两阶段法求解下两阶段法求解下面的问题面的问

19、题辅助问题辅助问题第第I阶段：阶段：第54页/共79页第五十五页，共79页。辅助问题的辅助问题的最后一张单纯形表最后一张单纯形表原问题的原问题的初始初始表格：表格：第55页/共79页第五十六页，共79页。原问题的原问题的最优解最优解：第56页/共79页第五十七页，共79页。两阶段法可求任一线性规划两阶段法可求任一线性规划(xin xn u hu)问题问题第57页/共79页第五十八页，共79页。退化退化(tuhu)(degenerate)与循环与循环(cycling)退化退化(tuhu)问题问题 单纯形法可能出现单纯形法可能出现(chxin)循环！循环！ 实际中经常碰到退化问题，但很少出现实际中

20、经常碰到退化问题，但很少出现(chxin)循环循环 避免出现避免出现(chxin)循环的措施：摄动法、循环的措施：摄动法、Bland法则法则、字典序法、字典序法 基本可行解是退化基本可行解是退化的当且仅当单纯形表最后一列有一个或的当且仅当单纯形表最后一列有一个或者多个零！者多个零！一次转轴是退化一次转轴是退化的当且仅当目标函数没有发生变的当且仅当目标函数没有发生变化！化！第58页/共79页第五十九页，共79页。最小系数最小系数(xsh)(xsh)规则：规则：循环的例子循环的例子Beale定义：从某张单纯形表开始返回到该单纯形表的一串转轴定义：从某张单纯形表开始返回到该单纯形表的一串转轴转轴规则

21、：选取进基变量和离基变量的明确规则转轴规则：选取进基变量和离基变量的明确规则(可以选时！可以选时！)第59页/共79页第六十页，共79页。第60页/共79页第六十一页，共79页。第61页/共79页第六十二页，共79页。循环循环(xnhun)！注：循环注：循环(xnhun)转轴序列中所有转轴序列中所有BFS都是都是退化的！是同一个退化的！是同一个BFS！第七张单纯形表第七张单纯形表第62页/共79页第六十三页，共79页。避免循环避免循环(xnhun)的方法的方法 能进基的变量能进基的变量(使目标值减小使目标值减小)中选中选(zhng xun)指标最小者指标最小者进基进基 摄动法摄动法(Dantz

22、ig，1954年年) Bland法则法则(fz)(Bland, 1977)最小指标法最小指标法则则(fz) 字典序法字典序法(Orden和和Wolfe，1954年年) 能出基的变量能出基的变量(保持可行保持可行)中选指标最小者出基中选指标最小者出基美好愿望：构造某种美好愿望：构造某种永远不会产生循环的永远不会产生循环的转轴规则！转轴规则！第63页/共79页第六十四页，共79页。前四张单纯形表相同前四张单纯形表相同(xin tn)！利用利用Bland法则法则(fz)作为转轴规则求解作为转轴规则求解Beale的例子的例子！第64页/共79页第六十五页，共79页。最后最后(zuhu)(zuhu)一张

23、单纯形表一张单纯形表/ /最优最优单纯形表单纯形表第65页/共79页第六十六页，共79页。退化退化(tuhu)的线性规划退化的线性规划退化(tuhu)的基本可行解的基本可行解(几几何解释何解释) 对于标准形而言，当极点仅对应一个对于标准形而言，当极点仅对应一个(y )基时，是非退化的；基时，是非退化的；当极点对应多个基时，是退化的。当极点对应多个基时，是退化的。第66页/共79页第六十七页，共79页。6. 单纯形法的矩阵单纯形法的矩阵(j zhn)形形式式给定给定(i dn)基基 B 及对应及对应BFS (xB, 0), 其中其中xB=B-1b用用非基非基变量表示变量表示目标函数目标函数：用用

24、非基非基变量表示变量表示基基变量：变量：相对相对费用向量费用向量第67页/共79页第六十八页，共79页。初始初始(ch sh)表格表格单纯形表单纯形表初始表格初始表格(biog)通常不是单纯形表！通常不是单纯形表！与基矩阵与基矩阵 B 对应的对应的单纯形表单纯形表第68页/共79页第六十九页，共79页。7. 修正修正(xizhng)单纯形法单纯形法(Revised simplex method) 重要重要(zhngyo)事实：事实： 通常仅有少数通常仅有少数(shosh)列发生转轴列发生转轴(2m-3m) 核心问题：核心问题：如何更新如何更新当前基的逆当前基的逆新基的逆新基的逆理论上的表现理论

25、上的表现表格实现表格实现 仅需原始数据仅需原始数据(c, A, b)和基和基 B 的逆矩阵的逆矩阵第69页/共79页第七十页，共79页。修正修正(xizhng)单纯形法的单纯形法的计算步骤计算步骤步步2 选取选取 q 满足满足步步3 计算计算(j sun) yq=B-1aq；若；若步步1 计算计算 。如果。如果 停；得最优解停；得最优解.步步0 给定给定BFS及对应的及对应的B-1。计算。计算核心核心(hxn)计算：计算：B-1涉及涉及到的计算：到的计算： ， 停，停，问题问题无界无界；否则，选；否则，选 p 满足满足步步4 更新更新 B-1, B-1b和和 ，返步，返步1.第70页/共79页第七十一页，共79页。基的转换基的转换(zhunhun)定理定理左乘该矩阵等价左乘该矩阵等价(