搜索
实用优化方法线性规划：单纯形法线性规划：目标函数是线性的，约束条件是线性等式或不等式线性规划线性规划的历史•渊源要追溯到Euler、Liebnitz、Lagrange等•GeorgeDantzig,VonNeumann(Princeton)和LeonidKantorovich在1940’s创建了线性规划•1947年,GeorgeDantzig发明了单纯形法•1979年，L.Khachain找到了求解线性规划的一种有效方法(第一个多项式时间算法－椭球内点法)•1984年，NarendraKarmarkan发现了另一种求解线性规划的有效方法，已证明是单纯形法的强有力的竞争者(投影内点法)•现在求解大规模、退化问题最有效的是原－对偶内点法◎问题：确定食品数量，满足营养需求，花费最小？◎变量：n种食品，m种营养成份；－第j种食品的单价－每单位第j种食品所含第i种营养的数量－食用第j种食品的数量－为了健康，每天必须食用第i种营养的数量◎模型：例1.食谱问题例2.运输问题产销平衡/不平衡的运输问题例3.其它应用•数据包络分析(dataenvelopeanalysis,DEA)•网络流问题(Networkflow)•博弈论(gametheory)等线性规划的一般形式线性规划的标准形(分析、算法)标准形的特征：极小化、等式约束、变量非负向量表示：一般形式标准形转化称松弛(slack)/盈余(surplus)变量；自由变量例5.化成标准形等价表示为定义：给定含有n个变量，m个方程的线性方程组Ax=b，设B是由A的列组成的任一非奇异m×m子阵，则如果置x的所有与B无关的n-m个分量为零后，所得方程组的解是Ax=b关于基B的基本解(basicsolution)，称x中与基B对应的分量为基变量(basicvariables)退化基本解：基本解中如果有一个或多个基变量的值为零基本解与基变量其中满秩假定：m×n矩阵A满足mn，且A的行向量线性无关•在满秩假定下，方程组Ax=b总有解，且至少有一个基本解基本可行解定义称的非负基本解是标准形的基本可行解(basicfeasiblesolution)；约束系统线性规划的基本定理i)若标准型有可行解，则必有基本可行解；ii)若标准型有最优解，则必有最优基本可行解。考虑线性规划标准形，其中A是秩为m的m×n阶矩阵，则以下结论成立：基本可行解的个数不超过与凸性的关系线性规划的基本定理(标准形)基本可行解线性方程组的基本性质代数理论(与表述形式有关)设计算法极点凸集理论几何理论(与表述形式无关)直观理解凸性(凸集及性质)几何解释：连接集合中任两点的线段仍含在该集合中性质定义是凸集(convexset)，如果对S中任意两点x,y和(0,1)中的任一数满足一些重要的凸集有限个闭半空间的交集多面集(polyhedralconvexset):推广平面上：多边形注：任一线性规划的可行集是多面集！超平面(hyperplane):正/负闭半空间：极点几何上：极点即不能位于连接该集合中其它两点的开线段上的点定义称凸集C中的点x是C的极点，如果存在C中的点y,z和某，有则必有y=z.极点与基本可行解的等价性定理推论：i)若K非空，则至少有一个极点.ii)若线性规划有最优解，则必有一个极点是最优解.iii)Ax=b对应的约束集K最多有有限个极点.考虑线性规划标准形，其中A是秩为m的m×n矩阵，令则x是K的极点，当且仅当x是线性规划的基本可行解.（线性规划基本定理的几何形式）例2.K有2个极点有3个基本解，2个可行K有3个极点有3个基本解，均可行例1.例3.Subjectto5个极点－极点线性规划解的几何特征唯一解(顶点)！线性规划解的几何特征•无界：没有有限最优解•不可行：没有可行解无解可行集：多边形(二维)→多边集(高维空间)给出有效的代数刻画和严谨的几何描述，从理论上证实上述几何特征，并寻求有效算法•有解：唯一解/多个解(整条边、面、甚至整个可行集)有顶点解顶点一条边无(下)界线性规划问题解的几种情况单纯形法简介•适用形式：标准形(基本可行解=极点)•理论基础：线性规划的基本定理！•基本思想：从约束集的某个极点/BFS开始，依次移动到相邻极点/BFS，直到找出最优解，或判断问题无界.•初始化：如何找到一个BFS？•判断准则：何时最优？何时无界？•迭代规则：如何从一个极点/BFS迭代到相邻极点/BFS？1.转轴(基本解→相邻基本解)满秩假定：A是行满秩的规范形(canonicalform)基变量基本解非基变量等价变形不妨设线性无关一般地：次序可以打乱！只要有m个单位列规范形的转换问题⊙什么时候可以替换？⊙替换后新规范形是什么？◎替换问题假设在上述规范形中，想用转轴(pivot)◎当且仅当，可以替换◎替换后，新规范形的系数转轴公式－转轴元(pivotelement)转轴例1.求下列方程组以为基变量的基本解转轴转轴转轴x=(0,0,0,4,2,1)2.BFS→相邻BFS(极点→相邻极点)◎问题：确定出基变量，使转轴后新规范形对应BFS？设x是BFS,且规范形如前，且假设aq进基因为令可否选取合适的使得是BFS？所以确定离基变量至少有一个正元例3.考虑线性方程组a4进基转轴B=(a1,a2,a3)X=(4,3,1,0,0,0)x=(0,1,3,2,0,0)3.BFS→目标值减小的相邻BFS⊙将Ax=b的任一解用非基变量表示；设x是BFS，且规范形如前，则有◎问题：确定进基变量，转轴后使新BFS的目标值变小？用非基变量表示.——选取进基变量的依据⊙将目标函数相对/既约费用系数(relative/reducedcostcoefficients)将Ax=b的任一解x用非基变量表示为度量变量相对于给定基的费用确定进基变量◎最优性定理◎定理(BFS的提高)◎相对费用系数的经济解释！(合成价格、相对价格)给定目标值为z0的非退化基本可行解，且假定存在j使得rj0，则i)如果用aj替换基中某列得到了新的BFS，则新解处的目标值比z0严格小.ii)如果任何替换都产生不了新的BFS，则问题无界.◆退化基本可行解：某个或某些基变量取零的基本可行解！问题：基本可行解与基的对应关系？4.计算过程－单纯形法单纯形表：BFS对应规范形的表格＋既约费用系数和BFS目标值的相反数单纯形法的步骤步0形成与初始BFS对应的初始表格.通过行变换求出第一张单纯形表.步1若对每个j都有，停；当前BFS是最优的.步2选取q满足步4以为转轴元进行转轴，更新单纯形表，返步1.步3若，停，问题无界；否则，选p满足转轴规则：进基变量：最小相对费用系数规则；出基变量：最小指标规则！例1.化标准形转轴得标准形的初始表格/第一张单纯形表转轴0↓-2↓-4↓-27/5转轴最优解：最优值：原问题的极大值：退化(degenerate)与循环(cycling)◎退化问题⊙单纯形法可能出现循环！⊙实际中经常碰到退化问题，但很少出现循环⊙避免出现循环的措施：摄动法、Bland法则、字典序法基本可行解是退化的当且仅当单纯形表最后一列有一个或者多个零！一次转轴是退化的当且仅当目标函数没有发生变化！最小系数规则：◎进基变量：最小系数规则◎出基变量：最小指标规则循环的例子Beale循环定义：从某张单纯形表开始返回到该单纯形表的一串转轴转轴规则：选取进基变量和离基变量的明确规则循环！注：循环转轴序列中所有BFS都是退化的！是同一个BFS！第七张单纯形表避免循环的方法⊙如果有多个费用系数是负的，选取下标最小的相对费用系数对应的变量为进基变量◎摄动法(Charnes，1952年)◎Bland法则(Bland,1977)－最小指标法则◎字典序法(Dantzig,Orden和Wolfe，1954年)⊙如果最小正比值在多个指标处取得，取下标最小者对应的变量为进基变量美好愿望：构造某种永远不会产生循环的转轴规则！前四张单纯形表相同！利用Bland法则作为转轴规则求解Beale的例子！最后一张单纯形表/最优单纯形表单纯形法的收敛性◎非退化线性规划：任一基本可行解非退化对非退化线性规划，从任一基本可行解出发，利用单纯形法可在有限步内得到最优解或判断问题无界.◎收敛性定理：5.两阶段法如何启动单纯形法－人工变量◎目标判断Ax=b,x≥0是否有界；有解时找一个基本可行解；⊙给有需要的行乘以-1，使得b≥0◎方法(x,y)=(0,b)是基本可行解！故可以(0,b)为初始BFS，利用单纯形法求解辅助问题假设最后得最优解(x,y)、最优值z*和最优基B⊙构造辅助问题人工变量得到原问题的基本可行解◎z*0，无可行解！◎z*=0，有可行解！⊙基变量中无人工变量→x是BFS，B是对应的基⊙基变量中有人工变量→驱赶人工变量出基假设第i个基变量是人工变量，且当前单纯形表第i行的前n个数据是第i个约束冗余；删除单纯形表的第i行数据以任一非零元为转轴元转轴得辅助问题的一个新最优BFS，且基变量中少1个人工变量！例1.给出下面系统的一个基本可行解，或者说明其无解引入人工变量目标：辅助问题的初始表格！BFS第一张单纯形表第二张单纯形表注意基变量整列包括末行z在内除了基变量其他元素都是0辅助问题的最优值是0.原问题的BFS：两阶段法－可求任一线性规划问题◎第I阶段：启动单纯形法→构造、求解辅助问题→判断原问题不可行、或可行→可行时找到基本可行解及对应规范形⊙第II阶段：利用单纯形法求原问题→从上述BFS出发，求解所给问题→原问题无界或者有解例2.利用两阶段法求解下面的问题辅助问题第I阶段：先构造辅助向量z=x4+x5辅助问题的最后一张单纯形表原问题的初始表格：得到辅助问题的最后一张单纯形表后，去掉辅助变量，将原始问题的z带入表格，启动单纯形法原问题的最优解：6.修正单纯形法(Revisedsimplexmethod)◎重要事实：⊙通常仅有少数列发生转轴(2m-3m)◎核心问题：如何更新当前基的逆→新基的逆理论上的表现表格实现⊙仅需原始数据(c,A,b)和基B的逆矩阵7.单纯形法的矩阵形式给定基B及对应BFS(xB,0),其中xB=B-1b用非基变量表示目标函数：用非基变量表示基变量：相对费用向量初始表格－单纯形表初始表格通常不是单纯形表！与基矩阵B对应的单纯形表修正单纯形法的计算步骤步2选取q满足步3计算yq=B-1aq；若步1计算。如果停；得最优解.步0给定BFS及对应的B-1。计算核心计算：B-1涉及到的计算：，停，问题无界；否则，选p满足步4更新B-1,B-1b和，返步1.基的转换定理左乘该矩阵等价于对矩阵进行初等行变换！定理不妨设B=.则aq进基，ap出基后所得新基的逆这里ei表示n维单位向量，向量v定义为相关数据的更新－初等行变换设转轴元是，即aq出基，ap进基以为转轴元，转轴后即得新基对应的数据！例1a2进基，计算y2.计算表格如下：计算a1进基，计算y1.得如下表格：最优值：最优解：利用两阶段单纯形过程求解1234123412341234min33.2022339260ixxxxstxxxxxxxxxxxxx