1、实用优化方法实用优化方法第第2章线性规划：单纯形法章线性规划：单纯形法刘红英刘红英理学院数学系理学院数学系线性规划：线性规划：目标函数是线性的，约束条件是目标函数是线性的，约束条件是线性等式或不等式线性等式或不等式线性规划线性规划线性规划的历史线性规划的历史 渊源要追溯到渊源要追溯到Euler、Liebnitz、Lagrange等等 George Dantzig,Non Neumann(Princeton)和和Leonid Kantorovich在在1940s创建了线性规划创建了线性规划 1947年年,George Dantzig于于发明了发明了单纯形法单纯形法 1979年年，L.Khacha
2、in找到了求解线性规划的一找到了求解线性规划的一种有效方法种有效方法(第一个多项式时间算法第一个多项式时间算法椭球内点法椭球内点法)1984年年，Narendra Karmarkan发现了另一种求发现了另一种求解线性规划的有效方法，已证明是单纯形法的强解线性规划的有效方法，已证明是单纯形法的强有力的竞争者有力的竞争者(投影内点法投影内点法)现在求解大规模、退化问题最有效的是现在求解大规模、退化问题最有效的是原对偶原对偶内点法内点法 问题问题：确定食品数量，满足营养需求，花费最小？：确定食品数量，满足营养需求，花费最小？变量：变量：n种食品，种食品，m种营养成份；第种营养成份；第 j 种食品的单
3、价种食品的单价每单位第每单位第 j 种食品所含第种食品所含第 i 种营养的数量种营养的数量食用第食用第 j 种食品的数量种食品的数量为了健康，每天必须食用第为了健康，每天必须食用第i 种营养的数量种营养的数量 模型：模型：例例1.1.食谱问题食谱问题例例2.运输问题运输问题产销产销平衡平衡/不平衡不平衡的运输问题的运输问题例例3.目标值带绝对值的问题目标值带绝对值的问题假设：假设：事实：事实：转化为：转化为：例例4.其它应用其它应用 数据包络分析数据包络分析(data envelope analysis,DEA)网络流问题网络流问题(Network flow)博弈论博弈论(game theor
4、y)等等线性规划的一般形式线性规划的一般形式线性规划的标准形线性规划的标准形(分析、算法分析、算法)*标准形的特征：标准形的特征：极小化极小化、等式约束等式约束、变量非负变量非负向量表示：向量表示：一般形式一般形式 标准形标准形转化转化称称 松弛松弛(slack)/盈余盈余(surplus)变量变量例例5.5.化成标准形化成标准形等价表示为等价表示为定义定义 设设B是是A 的的m个线性无关列组成的矩阵个线性无关列组成的矩阵.置置所有与所有与B无关列对应的变量为零，称所得方程组无关列对应的变量为零，称所得方程组的解是的解是Ax=b的基本解的基本解(basic solution)称称B是是基基(b
5、asis)；称与称与B对应的变量为对应的变量为基变量基变量(basic variables)基本解与基变量基本解与基变量(*)其中其中满秩假定：满秩假定：mn，且，且A的行向量线性无关的行向量线性无关基本可行解基本可行解定义定义 称称 的非负基本解是的非负基本解是标准形标准形的的基基本可行解本可行解(basic feasible solution)；例例6.6.基本可行解及几何意义基本可行解及几何意义基本可行解的个数基本可行解的个数不超过不超过线性规划的基本定理线性规划的基本定理(*)i)若有可行解，则若有可行解，则必存在必存在基本可行解；基本可行解；ii)若有解，则若有解，则必有某个基本可行
6、解必有某个基本可行解是最优解是最优解.考虑线性规划标准形，其中考虑线性规划标准形，其中A是秩为是秩为m的的mn阶阶矩阵，则以下结论成立：矩阵，则以下结论成立：与凸性的关系与凸性的关系线性规划的基本定理线性规划的基本定理(标准形标准形)基本可行解基本可行解线性方程组线性方程组的基本性质的基本性质代数理论代数理论(与与表述形式有关表述形式有关)设计算法设计算法极点极点凸集理论凸集理论几何理论几何理论(与表述形式与表述形式无关无关)直观理解直观理解凸性凸性(凸集及性质凸集及性质)几何解释几何解释：连接集合中任两点的线段仍含在该集合中：连接集合中任两点的线段仍含在该集合中性质性质 定义定义 是凸集是凸
7、集(convex set)，如果对，如果对S中任意中任意 两两 点点 x,y 和和(0,1)中的任一数中的任一数 满足满足 一些重要的凸集一些重要的凸集有限个闭半空间的交集有限个闭半空间的交集多面集多面集(polyhedral convex set):推推广广平面上：多边形平面上：多边形注：注：任一线性规划的可行集是任一线性规划的可行集是多面集多面集！超平面超平面(hyperplane):正正/负闭半空间：负闭半空间：极点极点几何上几何上：极点即不能位于连接该集合中其它两点：极点即不能位于连接该集合中其它两点的开线段上的点的开线段上的点定义定义 称凸集称凸集C中的点中的点 x 是是C的极点，如
8、果存在的极点，如果存在 C 中中的点的点 y,z 和某和某 ，有，有则必有则必有 y=z.极点与基本可行解的等价性定理极点与基本可行解的等价性定理推论：推论：线性规划基本定理线性规划基本定理的的几何形式几何形式i)若若K非空，则至少有一个极点非空，则至少有一个极点.ii)若线性规划有解，则必有一个极点是最优解若线性规划有解，则必有一个极点是最优解.iii)K的极点是有限集的极点是有限集.考虑线性规划标准形，其中考虑线性规划标准形，其中A是秩为是秩为m的的mn矩阵，令矩阵，令则则x是是 K 的极点的极点当且仅当当且仅当x是线性规划的基本可行解是线性规划的基本可行解.例例2.2.K有有2个极点个极
9、点有有3个基本解，个基本解，2个个可行可行K 有有3个极点个极点有有3个基本解，个基本解，均可行均可行例例1.1.例例3.3.Subject to5个极点个极点极点极点问题问题/作业作业考虑集合考虑集合证明这两个集合的极点是证明这两个集合的极点是一一对应一一对应的！的！线性规划问题解的几种情况线性规划问题解的几种情况线性规划线性规划解的解的几何特征几何特征唯一唯一 解解(顶点顶点)！顶点顶点一条边一条边无无(下下)界界线性规划解的线性规划解的几何特征几何特征 无界无界：没有有限最优解：没有有限最优解 不可行不可行：没有可行解：没有可行解无解无解可行集：可行集：多边形多边形(二维二维)多边集多边
10、集(高维空间高维空间)给出给出有效的代数刻画有效的代数刻画和和严谨的几何描述严谨的几何描述，从理论上证，从理论上证实上述几何特征，并实上述几何特征，并寻求有效算法寻求有效算法 有解有解：唯一解唯一解/多个解多个解(整条边、面、甚至整条边、面、甚至整个可行集整个可行集)有顶点解有顶点解单纯形法简介单纯形法简介 适用形式：适用形式：标准形标准形(基本可行解基本可行解=极点极点)理论基础：理论基础：线性规划的线性规划的基本定理基本定理！基本思想：基本思想：从约束集的从约束集的某个极点某个极点/BFS开始，开始，依次移动到依次移动到相邻极点相邻极点/BFS，直到找出最优，直到找出最优解，或判断问题无界
11、解，或判断问题无界.初试化：初试化：如何找到一个如何找到一个BFS？判断准则：判断准则：何时最优？何时无界？何时最优？何时无界？迭代规则：迭代规则：如何从一个极点如何从一个极点/BFS迭代到相迭代到相邻极点邻极点/BFS？1.转轴转轴(基本解基本解相邻相邻基本解基本解)满秩假定：满秩假定：A是行满秩的是行满秩的规范形规范形(canonical form)基本解基本解基变量基变量非基变量非基变量等价变形等价变形不妨设不妨设 线性无关线性无关 一般地一般地：次序可以打乱！次序可以打乱！只要有只要有m个单位列个单位列规范形的转换问题规范形的转换问题 什么时候可以替换？什么时候可以替换？替换后替换后新
12、新规范形规范形是什么？是什么？替换问题替换问题假设在上述规范形中，想用假设在上述规范形中，想用转轴转轴(pivot)当且仅当当且仅当，可以替换，可以替换 替换后，新规范形的系数替换后，新规范形的系数转轴公式转轴公式转轴元转轴元(pivot element)第二种解释：第二种解释：表格中第表格中第 i 列的数据列的数据用当前基用当前基表示表示 ai 时的时的系数系数转轴例例1.求下列方程组以求下列方程组以 为基变量的基本解为基变量的基本解转轴转轴转轴转轴转轴转轴x=(0,0,0,4,2,1)如何得到第一个规范形如何得到第一个规范形处理：处理：给表格给表格附加附加m个单位列向量个单位列向量开始开始
13、迭代，用迭代，用A中的列中的列依次替换依次替换这些单位列向量这些单位列向量以下运算以下运算同例同例1!例例2.利用转轴解方程组利用转轴解方程组为了得到第一个规范形，形成增广表格为了得到第一个规范形，形成增广表格2.BFS相邻相邻BFS(极点极点相邻相邻极点极点)问题：问题：确定出基变量，使转轴后确定出基变量，使转轴后新规范形新规范形对应对应BFS？设设x是是BFS,且规范形如前，且且规范形如前，且假设假设 aq 进基进基因为因为令令可否选取合适的可否选取合适的 使得使得 是是BFS？所以所以确定离基变量确定离基变量至少有一个正元至少有一个正元例例3.考虑线性方程组考虑线性方程组a4进基进基转轴
14、转轴B=(a1,a2,a3)X=(4,3,1,0,0,0)a1进基进基x=(0,1,3,2,0,0)3.BFS目标值减小的相邻目标值减小的相邻BFS 将将Ax=b的任一解的任一解用非基变量用非基变量表示；表示；设设x是是BFS，且规范形如前，则有，且规范形如前，则有问题：问题：确定进基变量，转轴后使确定进基变量，转轴后使新新BFS的目标值的目标值变小变小？用非基变量表示用非基变量表示.选取进基变量的依据选取进基变量的依据 将将目标函数目标函数相对相对/既约费用系数既约费用系数(relative/reduced cost coefficients)将将 Ax=b 的任一解的任一解 x 用非基变量
15、表示为用非基变量表示为确定进基变量确定进基变量最优性定理最优性定理定理定理(BFS的提高的提高)相对费用系数的相对费用系数的经济解释经济解释！(合成价格、相对价格合成价格、相对价格)给定目标值为给定目标值为z0的的非退化非退化基本可行解，且假定存基本可行解，且假定存在在 j 使得使得 rj 0，无无可行解！可行解！z*=0，有有可行解！可行解！基变量中基变量中无无人工变量人工变量x 是是BFS，B 是对应的基是对应的基 基变量中基变量中有有人工变量人工变量驱赶人工变量出基驱赶人工变量出基假设第假设第 i 个基变量是人工变量，且当前单纯形表个基变量是人工变量，且当前单纯形表第第 i 行的前行的前
16、n个数据是个数据是第第 i 个约束冗余；个约束冗余；删除单纯形表的第删除单纯形表的第 i 行数据行数据以以任一非零元任一非零元为转轴元转轴为转轴元转轴得辅助问题的一个新最优得辅助问题的一个新最优BFS，且基变量中少，且基变量中少1个人工变量！个人工变量！例例1.给出下面系统的一个基本可行解，或者说明其无解给出下面系统的一个基本可行解，或者说明其无解引入引入人工人工变量变量目标目标：辅助问题的辅助问题的初始表格初始表格！BFS第一张第一张单纯形表单纯形表第二张第二张单纯形表单纯形表辅助问题的辅助问题的最优值是最优值是0 0.原问题的原问题的BFS：例例2.利用两阶段法求解下面的问题利用两阶段法求
17、解下面的问题辅助问题辅助问题第第I阶段：阶段：辅助问题的辅助问题的最后一张单纯形表最后一张单纯形表原问题的原问题的初始初始表格：表格：原问题的原问题的最优解最优解：两阶段法两阶段法可求任一可求任一线性规划问题线性规划问题 第第I阶段：启动单纯形法阶段：启动单纯形法 构造、求解辅助问题构造、求解辅助问题 判断原问题判断原问题不可行、或可行不可行、或可行 可行时找到基本可行解及对应规范形可行时找到基本可行解及对应规范形 第第II阶段：利用单纯形法求原问题阶段：利用单纯形法求原问题 从上述从上述BFS出发，求解所给问题出发，求解所给问题 原问题原问题无界无界或者或者有解有解退化退化(degenera
18、te)与循环与循环(cycling)退化问题退化问题 单纯形法单纯形法可能出现可能出现循环！循环！实际中经常碰到退化问题，但实际中经常碰到退化问题，但很少出现很少出现循环循环 避免出现循环的措施：避免出现循环的措施：摄动法、摄动法、Bland法则、字典序法法则、字典序法 基本可行解是退化基本可行解是退化的当且仅当单纯形表最后一列有的当且仅当单纯形表最后一列有一个或者多个零！一个或者多个零！一次转轴是退化一次转轴是退化的当且仅当目标函数的当且仅当目标函数没有发生变化！没有发生变化！最小系数规则最小系数规则：进基变量：最小系数规则进基变量：最小系数规则 出基变量：最小指标规则出基变量：最小指标规则
19、循环的例子循环的例子Beale循环循环定义：从某张单纯形表开始返回到该单纯形表的一串转轴定义：从某张单纯形表开始返回到该单纯形表的一串转轴转轴规则：选取进基变量和离基变量的明确规则转轴规则：选取进基变量和离基变量的明确规则(可以选时！可以选时！)循环！循环！注：注：循环转轴序列中所有循环转轴序列中所有BFS都是退化的！是都是退化的！是同一个同一个BFS！第七张单纯形表第七张单纯形表避免循环的方法避免循环的方法 能进基的变量能进基的变量(使目标值减小使目标值减小)中选指标最小者进基中选指标最小者进基 摄动法摄动法(Dantzig，1954年年)Bland法则法则(Bland,1977)最小指标法
20、则最小指标法则 字典序法字典序法(Orden和和Wolfe，1954年年)能出基的变量能出基的变量(保持可行保持可行)中选指标最小者出基中选指标最小者出基美好愿望：构造某种美好愿望：构造某种永远不会产生循环的永远不会产生循环的转轴规则！转轴规则！前四张前四张单纯形表相同！单纯形表相同！利用利用Bland法则法则作为转轴规则求解作为转轴规则求解Beale的例子！的例子！最后一张单纯形表最后一张单纯形表/最优单纯形表最优单纯形表退化的线性规划退化的基本可行解退化的线性规划退化的基本可行解(几何解释几何解释)对于标准形而言，当极点仅对应一个基时，是非退化的；对于标准形而言，当极点仅对应一个基时，是非
21、退化的；当极点对应多个基时，是退化的。当极点对应多个基时，是退化的。6.单纯形法的矩阵形式单纯形法的矩阵形式给定基给定基 B 及对应及对应BFS(xB,0),其中其中xB=B-1b用用非基非基变量表示变量表示目标函数目标函数：用用非基非基变量表示变量表示基基变量：变量：相对相对费用向量费用向量初始表格单纯形表初始表格单纯形表初始表格初始表格通常不是单纯形表！通常不是单纯形表！与基矩阵与基矩阵 B 对应的对应的单纯形表单纯形表7.修正单纯形法修正单纯形法(Revised simplex method)重要事实：重要事实：通常仅有少数列发生转轴通常仅有少数列发生转轴(2m-3m)核心问题：核心问题
22、：如何更新如何更新当前基的逆当前基的逆新基的逆新基的逆理论上的表现理论上的表现表格实现表格实现 仅需原始数据仅需原始数据(c,A,b)和基和基 B 的逆矩阵的逆矩阵修正单纯形法的计算步骤修正单纯形法的计算步骤步步2 选取选取 q 满足满足步步3 计算计算 yq=B-1aq；若若步步1 计算计算 。如果。如果 停；得最优解停；得最优解.步步0 给定给定BFS及对应的及对应的B-1。计算。计算核心核心计算：计算：B-1涉及涉及到的计算：到的计算：，停，停，问题问题无界无界；否则，选；否则，选 p 满足满足步步4 更新更新 B-1,B-1b和和 ，返步，返步1.基的转换定理基的转换定理左乘左乘该矩阵
23、等价于对矩阵进行该矩阵等价于对矩阵进行初等行变换初等行变换！定理定理 不妨设不妨设B=.则则 aq 进基，进基，ap出基后所得新基出基后所得新基 的逆的逆这里这里 ei 表示表示n 维单位向量，向量维单位向量，向量 v 定义定义为为相关数据的更新相关数据的更新初等行变换初等行变换设设转轴元转轴元是，即是，即 aq 出基，出基，ap进基进基以为转轴元，以为转轴元，转轴后转轴后即得新基对应的数据！即得新基对应的数据！例例1 求解例求解例2.3.4a2进基进基，计算，计算y2.计算表格如下：计算表格如下：计算计算a1进基进基，计算，计算y1.得如下表格：得如下表格：最优值：最优值：最优解：最优解：问
24、题问题.设用单纯形法求解标准形式的设用单纯形法求解标准形式的LPLP时得到如下时得到如下 单纯形表单纯形表.还假设矩阵还假设矩阵A的的后三列形成单位矩阵后三列形成单位矩阵1.1.给出由该表描述的当前基是最优的充分必要条件给出由该表描述的当前基是最优的充分必要条件(依照表中的系数依照表中的系数).).2.2.假设该基是最优的且假设该基是最优的且 .找出另外一个最找出另外一个最优基本可行解，其与该表所描述的不同优基本可行解，其与该表所描述的不同.假定与假定与当前表所联系的基是最优当前表所联系的基是最优的的 假设将原问题中的假设将原问题中的 ，给出使基保，给出使基保持最优的持最优的 的范围的范围.1.1.假设将原问题中的假设将原问题中的 ，给出使基保，给出使基保持最优的持最优的 的范围的范围问题问题.设用单纯形法求解标准形式的设用单纯形法求解标准形式的LPLP时得到如下时得到如下 单纯形表单纯形表.还假设矩阵还假设矩阵A的的后三列形成单位矩阵后三列形成单位矩阵
