（运筹学与控制论专业论文）对偶二分单纯形算法.pdfVIP

摘要 在单纯形算法的各种改进中，潘平奇教授在1 9 9 0 年的文章【2 l 】中提出的二分单纯形 算法是一个重要的改进它的优势在于通过对可行区域不断进行二分来达到对目标值的 改善进行有效控制，从而较为有效地解决了在可行域顶点过于密集时，迭代时目标值的 改善过于缓慢的弱点本文从对偶角度考虑，提出了对偶二分单纯形算法它形式上比原 始二分单纯形算法简洁，吸引人而实现也较为容易 关键词，线性规划对偶主元标单纯形方法二分摄动 a b s t ：r a c t a m o n gi m p r o v e m e n t0 ft h es i m p l e xm e t h o d t h es i m p l e xm e t h o dw i t hb i s e c t i o nf o rl i n e a r p r o g r a m m i n g 2 1 w r i t t e nb yp 一q p a ni n1 9 0 9 q i sa i m p o r t a n to n e i t ss u p e r i o r i t yi st h a ti tc a n c o n t r o lt h ep r o c e d u r eo ft h es i m p l e xm e t h o d ，t os o m ee x t e n t ，o v e r c o m i n gt h ew e a k n e s so ft h e c o n v e n t i o n a ls i m p l e xm e t h o dt h a tt h eo b j e c t i v ev a l u ep r o g r e s s e st o os l o ww h e nv e r t i c e so ft h e f e a s i b l er e g i o ni st o oc o n d e n s e t h i sp a p e rp u t sf o r w a r dt h e d u a ls i m p l e xm e c h o dw i t hb i s e c t i o n f o rl i n e a rp r o g r a m m i n g i nam o c o n c i s ef o r m ，t h ep r o p o s e dm 酏h o di s8 t t r a c t i v 黾a n de a s i e r t ob ei m p l e m e n t e d k e y w o r d s ：l i n e a rp r o g r a m m i n gd u a lp i v o t i n gi n d e xs i m p l e xm e t h o db i s e c t i o np e r t u r - b a t i o n 东南大学学位论文 独创性声明及使用授权的说明 一学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成 果尽我所知，除了文中特别加以标明和致谢的地方外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过的 材料与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表 示了谢意 = 、关于学位论文使用授权的说明 东南大学，中国科学技术信息研究所，国家图书馆有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印，缩印或其他复制手段保存论文本人电子文档的内容 和纸质论文的内容相一致除在保密期内的保密论文外，允许论文被查阅和借阅，可以公 布( 包括刊登) 论文的全部或部分内容论文的公布( 包括刊登) 授权东南大学研究生院办 理 签名：蜓导师签名：鼢日期：兰华7 第一章绪论 在这一章中，我们先对线性规划问题单纯形算法的发展历史及本文算法的形成思路 作一概述，并对以后章节的内容作出说明 1 1 本文算法的基本思想 线性规划是运筹学中产生最早的个领域g b d a n t z i g 于1 9 4 7 年提出的线性规划 模型和单纯形算法【8 ，9 | 成为解决线性规划问题的强有力工具此后该领域得到了迅速发 展和广泛的应用，并带动了非线性规划、网络规划、随机规划、组合优化等领域的产生 目前，线性规划已成为现代管理和决策的重要手段，从解决技术问题的优化设计到工业， 农业商业、交通运输业军事、经济计划等领域都发挥作用因此。如何进一步提高线 规划的计算效率，一直是运筹学界关注而具有深远意义的课题 直到今天，在解决线性规划问题的诸多方法中单纯形算法依然是最有效的方法之一 从理论上讲，该算法的时间复杂性是指数阶的，然而它在实际应用中的表现却十分出 色，取得了令人注目的显著效果，成为应用最广泛的数学工具之一尽管1 9 8 4 年出现 的k a r m a r k a r 算法【1 6 1 是一种多项式时间算法，在理论上优于单纯形算法目前许多学 者都认为，对于中小型线性规划问题而言，以k s r m a r k a r 算法为代表的内点算法的效率 稍逊于单纯形算法；但对于大型稀疏线性规划问题，前者则胜于后者因此总体来说， 两者的计算效率难分高下而另一方面由于k a n n a r k a r 算法属于内点算法，它只能从可 行域内部逼近最优解，不能精确达到顶点解，所以它并不适于求解实际中大量涌现的整 数规划问题再加上近年来单纯形类算法也有不少重要进展，更使这两类算法形成了不 相上下难分胜负的局面因而进一步改进单纯形算法依然是线性规划的重要课题事实 上，b o r g w a r d t 4 3 和s m a l e 阻】还证明了单纯形算法的平均运算次数是多项式阶的因而 无论在理论上还是实践中，单纯形算法都具有极其重要的地位本文的算法从本质上说 是单纯形算法的一种变种，致力于进一步减少其迭代次数以提高效率下面我们概括一 下本文算法的发展思路 奎查奎竺堡圭耋堡垒塞量三兰丝 2 在1 9 4 7 年d a n t z i g 提出单纯形算法【8 | 之后，出现了单纯形算法的各种改进变形上 世纪5 0 年代出现的修正单纯形算法【5 1 】是单纯形算法的个重要变种该算法省略了单 纯形表，以更紧凑的方式进行单纯形迭代，在解决大规模问题时，可极大地节约储存空问 和提高效率这使单纯形类算法更适于实际的需要，成为一种简洁，实用和高效的算法 尽管如此，此类算法也存在一些缺点，例如当求解实际问题时，由于可行域相邻顶点间距 离非常小，导致经很多次迭代目标值的改善仍微不足遭甚至在退化顶点长时间停顿而 难以跳出这就促使我们寻找使单纯形迭代摆脱这种困难的方法 潘平奇教授在1 9 9 0 年发表的。二分单纯形算法”【2 1 】可作如下几何解释在图1 1 中 线性规划问题的可行域为o ，a ，b ，d ，e ，g ，d ，不妨设要求解的l p 问题是求最大值，图中 e 点为最优值点目标函数等值面用粗线表示，且已得到了原始问题的一个基本可行解 田1 1 二分单纯形算法的几何解释 下面首先要确定最优值的一个存在区间，而当前点( b 点) 的目标值就可令为下界口此 时不妨设最优值存在区间为【0 ，明已经得到洳图) 再对原问题的可行域增加一个和目标 奎童查堂堡圭兰堡垒塞篁三塞丝 3 函数平行且目标值为区间中点b o = ( n + s ) 1 2 的超平面约束( 下图中x = h ) ，该超平 面约束的目标值显然比已有的基本可行解的目标值有一定改善此时就形成个子问 题。该子问题的可行域( 实际上就是图1 1 中的砑线段) 比原始问题多一个约束，所以 它的可行域比原始问题要小因为当前基本可行解( 对应b 点) 不在子问题增加的超平面 上，所以当前基本可行解对于子问题来说不可行这样就需要通过对子问题进行迭代来 达到子问题的一个基本可行解，这就存在两种可能性t 一种是经若干次迭代后达到了子 问题的一个基本可行解；另一种可能是迭代无法达到子问题的基本可行解 比如依本例中的情况，在迭代后达到了c 点，当然也可能是f 点( 不同的主元算法 得到的结果可能不同) ，属于第一种情况由于子问题的可行域是原始问题可行域的真子 集，所以该点对应解一定是原始问题的可行解由图看出，该可行解( 不妨设就是对应c 点的解) 一定是在原问题的某个一维界面( 哥d 线段) 上，即两个基本可行解( 对应b ，d 两 顶点) 之间所以只需沿着该一维界面再前进步c 从c 点走到d 点) 就可以达到原始问 题的个基本可行解( 对应d 点) 此时就可以做最优检验，要么达到最优，算法结束；要 么非最优( 本例即如此) 即可令当前基本可行解的目标值为新的最优区间下界口，结束本 次二分 至于另一种可能，即迭代无法达到子问题的基本可行解这就表明子问题无可行解， 即子问题增加的超平面约束的目标值已经超过了原始问题的最优值，所以可令子问题增 加的超平面约束的目标值为新的最优值区间上界，同样结束了本次二分 由此可见一次二分实质上是包含了若干次迭代的个过程，大致可分以下三组； 第一组迭代是从已有的基本可行解强迫达到子问题的一个基本解，通常来说此解并 非子问题的可行解，该组迭代只包含步迭代 第二组迭代是二分的主要部分，它通过一系列迭代来达到子问题的一个基本可行解 直观地说，这些迭代是在子问题增加的超平面上进行的如果达到了子问题的一个基本 可行解，就可以进入第三组迭代了；如果不能达到子问题的基本可行解，那么这一次二分 就直接结束了，没有第三组迭代( 基于本文算法，如果按照文【2 l ，2 7 】的算法，在这种情况 下也需要进入第三组迭代) 塞曼查兰堡圭兰竺墼茎塞三兰丝 4 第三组迭代也只包含一步迭代第二组迭代已经达到了子问题的基本可行解，它也 是原问题的某个一维界面上的可行解，那么再有一步迭代就可以脱离子问题增加的超平 面约束，从而达到原问题的基本可行解 这种改进的二分单纯形算法就成为了本文算法的主要依据和出发点以上文【2 1 】中 的算法在具体过程上较为繁琐，约束矩阵需要增加一行一列，从而增大了原问题的规模， 尤其是增加一行不好处理此外在达到子问题的基本可行解的迭代过程中右端项并不可 行，所以并不能用经典的单纯形算法的迭代方法此外，初始的最优值存在区间如何确 定也存在问题所以，潘平奇教授在1 9 9 6 年提出了该算法的改进算法，即一种修改二 分单纯形算法【2 7 】该算法在形式上比文【2 1 】有较大简化新算法的约束矩阵规模只增 加一行，而不增加列，当然在算法中实际上隐含了这一列；取消了原算法中自定义的。原 始”和。对偶形式；取消了用于间接定义右端项的向量h ( m + 1 ) ，转而赢接表示右端项； 在确定最优值存在区间时采用了一种较为可行的办法一估计误差界方法；进出基时采用 无比值检验法以较快地确定主元该改进算法将在后文详细叙述 另一方面，b 1 e 和l e m k e 在1 9 5 4 年提出了对偶单纯形方法 2 ，1 8 ，1 0 他们指出任 何问题都有对偶线性规划问题，当其中任一问题存在最优解时两个问题的最优解都存在 且最优值相等所以可以通过解决线性规划的对偶问题来解决原始问题然而这并不意 味着要把对偶问题显式地表达出来，而是可直接用原始问题的单纯形表进行迭代这可 以被看作是一个思维技巧t 几乎任何单纯形变种都可以从对偶角度找到相应的对偶算法， 且算法的执行只需在原始单纯形表上进行不仅如此，近年来的数值实验还表明，对偶类 算法常优于原始类算法这就启示我们，对于现有好的单纯形变种，不妨发展其对偶算 法，以使之具备某些吸引人的特性，进一步提高效能 基于这些思想。本文从对偶角度出发发展出了对偶二分单纯形算法其明显的好处 是t 对偶问题增加一个不等式约束( 行约束) 所形成的对偶子问题，其对偶问题( 原始子 问题) 只比原始问题多一列这样增加的一列可以用经典的单纯形步骤进出基，处理起来 较为方便，且可直接在原始表上进行该算法将在第五章详细描述 奎塞奎兰至圭耋篁垒塞篁三茎丝垒 5 1 2 下文章节安排 本文章节大致安排如下t 第二章，介绍本文所使用的符号和记法以及基本概念和定理 第三章，介绍年的一种修改= 分单纯形算法【2 7 】，它是本文算法的直接来源 包括其中的无比值检验法【2 1 ，矧及最优值存在区间生成算法一最优值误差估计法【2 7 】 第四章，介绍主元标刚及对偶主元标 4 5 ，5 0 】的概念，利用其生成初始基的办法和 优点 第五章，核心章节，详细介绍本文算法的主算法，即二阶段算法，以及最优值误差估 计法在本文中的改进 第六章，数值实验及其分析 第二章符号说明与基本概念 在本章介绍一下本文所使用的符号和记法以及基本概念和定理，这些符号和记法全 文通用 2 1 。基本符号说明 本文将引用以下的符号和记法，如不特别说明，则以下面为准： ( 1 ) 矩阵，集合用大写的英文字母a ，b ，m ，等表示 在具体使用时将对它们详细区分； ( 2 ) 列向量用小写的英文字母表示； ( 3 ) r a n k ( a )矩阵a 的秩； ( 4 ) 町矩阵a 的第j 列； ( 5 ) 吁向量的第j 个元素； ( 6 ) i i 向量的2 - 范数； ( 7 ) r ( ) 矩阵的域空间； ( 8 ) ，单位矩阵 2 2 基本概念和定理 考虑如下标准形式的线性规划问题， m i nc t z 8 ta x = b z 0 ( 2 1 n ) ( 2 1 6 ) ( 2 1 c ) 其中c = ( c 1 ，c 2 ，岛) r 为n 维列向量，啦0 = 1 2 n ) 为a 的列向量，c o x 称为目标函 数。( 2 1 b ) 式和( 2 1 c ) 式称为该线性规划问题的约束条件7 关于以上线性规划问题概念和定理很多，我们这里只介绍在本文中要用到的基本理 论。 6 奎曼奎耋望圭耋堡墼苎量三兰丝塑皇董奎堡垒 7 定义2 1 设口为矩阵a 中的一个m 阶满秩方阵，则称b 为一个基，口中m 个线性 无关的列向量称为基向量，这些列向量的下标做成一个集合，称为基指标集，记为j b ， 中与之对应的m 个分量称为基变量其余的变量称为非基变量，其对应列组成的矩阵称 为非基矩阵，记为这些变量的下标做成的集合相应称为非基指标集，记为j 知令所 有的非基变量取值为零。得到的解t z = = ( b - 。1 6 ) 称为对应千b 的基本孵 定义2 2 一个基奉解。满足z 0 ，即也是一个原始可行解，则称。为一个基本可行 解，这时它所对应的基b 称为基本可行基 定义2 3 利用目标函数，z 中的向量c 和基矩阵b 构造向量c n e b b i n ，该向量 称为检验数向量它的每个分量盘一e b b 一1 啦对应于非基变量善“称为该变量的检验数 当检验款o 时，称该检验数可行，否则称为不可行当检验数向量所有的分量都可行， 当前基就称为对偶可行基，基本解就称为对偶可行的基本解与之相对应，前面定义的基 本可行j 卑也可称为原始基本可行解，对应的基称为原始基本可行基，下文如不特别说明， 则依旧分别称为基本可行解和基本可行基 定义2 4 如果一个基本解既原始可行，又对偶可行，则称之为线性规划问题的最优 解，矸应基称为最优基，相应的目标函数值c t x 就称为线牲规划问题的最优值 定义2 5 一个基本可行解z ，如果所有的基变量都取正值，则称为非退化的；反之一 个或多个变量取值为零，则说其是退化的一个线性规划问题，如果它的所有基本可行解 都是非退化的，就称之为非退化的；否则有一个基本可行解是退化的，就说它是退化的 定理2 1 可行解是基本可行解z 的充分必要条件是正分量所对应的列向量线性无 关 定理2 2 若一标准的线性规划同题有可行解，则其必有基本可行解 定理2 3 若一个标准的线性规划问题的目标函数有有限最优值，则必在某个基本可 行解达到 根据定义2 1 在本文中有下面定义； 奎查奎耋堡圭耋堡垒兰篁三兰些塑量董奎丝8 定义2 6 与最优解相关联的基变量称为最优基变量，与最优解相关联的非基变量称 为最优非基变量 将线性规划同题( 2 1 ) 以表格形式表示如下t 4 ab 我们仍用b 表示基变量下标集合以及基本可行基，用n 表示非基变量下标集合以及非 基矩阵，不失一般性，设如= 1 ，2 ，m ，矗= m + 1 ，m + 2 ，n ) ，则问题( 2 1 ) 对应 的单纯形表分块为； 西西l0 bnb 将其进行g a u s s - j o r d a n 消去得， 0 西一n t b - t c bi 西口- 1 b 了1 i f t _ 五丁 令，= ( 0 西一n t 9 c b ) ，5 = b b ，这样线性规划问题( 2 1 ) 就转化为t r a i n 西b - 1 b + ， 8 tx b + b n z = 5 20 ( 2 纽) ( 2 2 6 ) ( 2 刎 定理2 4 如果有一z 使得上式偿8 础中e 20 ，则2 为原问题的最优解 定理2 5 如果向量e 有分量岛o 但然m + ls 曼n j ，而其对应的向量( b 一1 ) k 一。s 0 则原问题无界 定理2 6 如果仁l a ) 式中向量c 有分量矗0 ，且至少有一个负分量，则能找到另 一基苯可奄辫使一曼一t 。 以上三个定理给出了单纯形算法的工作原理，即不断地从一个可行基迭代到与它相 邻的另一个可行基，直至找到最优基偌最优基存在的话) ，或者判断原问题无界 第三章修改二分单纯形算法 在这一章中，我们将详细介绍文【27 】中的修改二分单纯形算法，部分和文【2 l 】不同 的地方会作出说明 3 1 无比值检验法 在这一节中，我们首先介绍修改二分单纯形算法的无比值检验法此算法来源于1 9 9 0 年的文章【2 1 】和1 9 9 4 年的文章阻，4 7 】 所谓无比值检验法，就是在选择进基或者出基变量时不再按通常主元规则中的最小 比检验( 有时是最大比检验) 规则来确定主元，而是在进基列( 出基行) 中选择符号为正 ( 负) 且绝对值最大的元素这种方法免除了每次迭代中比较最小比的庞大计算量，节约 了每次迭代的运行时间，而且这种只取最大元素作为主元的选法从平均概率上讲单位时 问目标值往往优化得幅度更大但正是由于不再检验最小比，所以在迭代过程中不再保 持可行性大量数值实验表明，这种算法的效率优于最小比检验算法 考虑以下标准形式的线型规划问题( 注意为了和文【2 7 1 保持一致，这里使用的目标函 数是求最大，而本文其他地方一般用的是最小) t mz = ，z ( 3 1 a ) s ta z = b z 0 ( 3 1 b ) f 3 1 c ) 其中a j p 一，b 妒，c 和z 是n 维列向量c r = 称为耳标函数，( 3 1 b ) 式和( 3 1 c ) 式 称为该线性规划问题的约束条件 在这一节中。我们将尝试获得目标值为某一预先给定值的可行解为了达到这个目 的，文【2 1 中的第3 节的方法在这里将被简化，转面使用无比值检验法 把c t = = 2 作为约束加到原问题约束矩阵里，并令其为第0 行，然后设 a = ( 云) ，b = ( ；) ( 3 2 ) 9 塞查查竺堡圭竺堡垒苎篁三塞璧鳖坌皇墼垄塞童 1 0 扩展后的矩阵依然按( 3 1 b ) 的体系定义那么我们有a 硝卅1 ) 一，b j p “，和a o je 白，j = 1 ， ，以及b o = z ，其中= 是目标值参数这里首先假设原问题的约束条件 a x = b 是相容的而且有r a n k ( a ) = + 1 s m + 1 n 设b 硝m + 1 x 斜。1 ) 是a 的基，其基指标集记为 如= j o ，靠， ( 3 3 ) 非基指标集记为 了f = t 1 ，n 如( 3 4 ) 对应的标准形可由以下单纯形表来表示 b + a i b + b( 3 5 ) 其中口+ 是b 的m o o r e p e n r o s e 广义逆对于给定的6 0 ，如果行指标集 i = 矗l ( b + 砷 0 , i = o ，材( 3 6 ) 为空，那么一个目标值为6 0 的可行解就已经得到了如果其非空，我们就可以用下面的 主元规则来更新基 规则3 1 如果桌，非空。那么按照下式选择旋转行指标r ； r = a r g m i n ( b + b ) i l ie n( 3 7 ) 如果集 j = j l ( v + k 0 时，设b o = b o + 口和b + b = b + b + a ( b + e o ) 。而且显然只需考虑口0 的 情形事实上当口= 0 时，以上更新甘于6 0 和( b + ) 6 来说是没有任何变化的更新后的 6 0 有所增大，也就是说此时的基本可行解的目标值优于6 0 ； 一彬如果集合 z = j i ( b + a a , _ - 0 ，则说明当前解的目标值为原问题可行域内的置小值偌意我 们是要求最大值j ，停； ，磁) 利用下式计算口t ，一黠 。，9 2 一而刮， 然后设b o = b o + 口和b + b = b + b + ( b + e o ) ，此时得到了一个目标值为6 0 的基本解，由 于6 0 有所缩小，所以这个新的基本解的目标值比子问题增加的超平面的目标值更接近最 优值而且事实上这个新的基本解是一个基本对偶可行解仰满足对偶可行的基本解 似j 如果由p 卅定义的集合j 为空，那么此基本解就满足了原始可行性，从而它 也是基本可行解该解原始和对偶都可行，因而它是最优解，停，整个算法结束； 俐达到原问题的对偶可行的基本解，停圭算法并没有结束， 5 通过倍鲫确定列指标8 6 牵l m 3 1 1 ) 丈新b + ，再通过1 3 ，1 1 2 ) 更新b + b 奎塞奎兰堡圭兰垒篁奎量三塞堡垒坌塞堡垄坠 1 3 7 一次迭代结束。但因为未达到原问题的可行解，也没能确定子问题可行域为空。所 以子算法并没有结束，需要继续迭代，回步骤2 现在我们利用下面的定理来来解释子算法的不同出口的意义，其证明类似文【2 1 】中 的定理( 3 1 3 ) t 定理3 1 假设子算法只j 结束，那么可能结束在 ，矽步骤即冽或4 砂，此时最优解达到，整个算法结束； 例步骤2 砂。达纠了一个非最优的基本解； 纠步骤4 例，或4 m ，表明最优值不在区闾( 一，6 0 】陟骤0 一圳，或者最优值不在区 间【b o ，) 内r 步骤4 w ； r 圳步骤2 例，表明问题无上界； 娜 r 印步骤4 御，表明原问题不可行，即可行域为空 现在的问题就是子算法是否会结束事实上由于基的数量是有限的，所以子算法一 定会结束，除非发生循环，或者说某些基会被无限的重复下去当然我们无法确认究竟是 否会发生循环，但是一般来说循环在实践中是很少发生的从本算法最后的数值实验也 能判断出这一点 注意：这个算法比文【2 1 】在形式上简化了许多，取消了用来间接定义右端项的向量 ( m ) ，给出了较明确的最优区间生成算法但是还是有些缺点，比如文【2 1 1 中显式增加的 一列。e o 改为隐含增加这一列( 步骤2 ( i ) ，2 ( n ) ，步骤3 0 ) ，3 ( n ) ，3 ( i i i ) 中出现的e o 就是这隐含 的一列造成的) ，实际并没有化简多少而且基矩阵的规模依然是( m + 1 ) ( m + 1 ) 另外 初始的6 0 和下面主算法中要出现的最优值误差估计j 也没有确定的生成算法 3 3 主算法，最优值误差估计法 下面我们就需要利用上一节中的子算法3 1 来生成主算法用以解决l p 问题( 3 1 ) 首先假设最优值存在为了加快解决过程，主算法需要更有弹性地获取最优值的信 息所以我们不再需要像文【2 1 】那样事先确定最优值存在区间( o ，所，而只需要一个初始 的b o 和6 0 与最优值可能的误差估计6 利用这些信息，我们可以在下面的算法中生成所 需的最优值存在区间( a ，国首先执行子算法3 1 ，如果子算法结束在步骤2 ( i v ) ，6 0 即可 奎查查竺堑圭兰堡垒苎整三重堡垒坌皇丝垄丝 1 4 作为下一次二分的最优值下界( 上界) ，即设a = 6 0 。b o = o l + 6 = 如，b o = 卢一回然后利 用新的b o 再一次执行子算法3 1 不断重复以上步骤，直到发现b 是最优值上界( 下界) ， 此时就可以设卢= b o ( n = 6 0 ) 现在最优值存在区间( q ，卢) 就已经完全确定下来了算法 中的二分，即6 0 = + 所2 就可以正常执行了当确在莱次二分落入了一个理想的区 间，子算法3 1 将因得到了最优解而结束，最优值也就得到了，不再需要其它步骤 主算法如下： 算法3 2r 即文廖刀的算法只j 肺是最优值的估计，6 是6 0 与最优值的误差估计矿 是a 的某个初话基的m o o r e p e n r o s e 广义逆，此算法用于解决标准l p 问题何砂 1 设q = 一，p = 2 执行子算法只j 3 如果子算法结束在2 似砂或者4 俐，置优解达到了，停 4 如果子算法结束在2 俐，那么原问题无上界，停 5 如果子算法结束在4 俐，原问题不可行，停 6 如果子算法结束在2 一或者4 让那就达到了一个非最优的基本可行解，此时得 到了一个新的最优值下界，那么： 倒设n = b ； r 矽如果卢= + o o ，那么还无法进行正常的二分步，只能继续使用最优值误差估计 算法，设b o = 口+ j ，一次二分结束了。转步骤f 纠 7 如果子算法结束在4 m ，那说明子问题可行域为空，此时的如已经超过了最优值， 所以可以作为最优值的一个上界，那么 例设卢= 6 0 ； f 砌如果口= 一，那么还是无法进行正常的二分步，设6 0 = p 一6 ，一次二分结束 1 ，转旁骤但) 8 在n 和口均为有限的情况下，作正常的二分步，设6 0 = n + 卢，一次二分结束了， 辏孝繇( 2 ) 利用上节的定理3 1 可以轻松证明以下结论( 证明略) ； 定理3 2 慑如主算法只2 终止，那么： 奎查奎耋堡圭兰堡垒塞量三塞堡垒坌皇墼垄塞童 1 5 俐终止在步骤只最优解达到。整个算法结束； 俐终止在步骤4 ，表明问题无上界，整个算法结束； r 砂终止在步骤5 ，表明问题不可行，整个算法结束 注意：在主算法里运行一次子算法结束后，我们称一次二分结束，在o t 和声没有都 达到有限的情况下，并不是标准的二分步，暂时称为广义的二分步和文【2 1 】相比，文 2 1 】并没有给出明确的最优值存在区间( o ，卢) 生成算法，而以上文 2 7 】采用了在计算过程 中逐渐生成最优值存在区间的办法。其形式优美，有利于编程实现，但也有一个缺点就 是如果子算法3 1 能在有限步终止，那么主算法3 2 在原问题有最优解时一定终止在步骤 3 ，而在原问题无上界时一定终止在步骤4 但如果原问题可行域为空时不能保证主算法 3 2 有限步终止这是因为如果有限的。始终都没有找到，而卢可能无限的缩小下去而根 本我不到有限值因为原问题根本就没有基本可行解，所以算法就会无限地进行下去 3 4 初始基生成和数值实验 初始基生成利用了文【2 1 1 中提出的主元标生成算法，这个算法将在第四章详细叙述 数值实验共计算了4 个标准问题和3 个k l e e m i n t y 问题【17 】在标准问题中它比 经典的两阶段算法好很多，而且比文 2 1 】中的算法也要好而在k l e e m i n t y 问题计算 中，由于k l e e m i n t y 问题严重退化，使用经典算法效率极低，所以该算法效率就比经 典算法提高了多达1 0 0 倍这正是因为二分单纯型算法控制了迭代过程，每次二分都强 迫目标值的改善幅度达到一定水平，不会在一些退化顶点迭代很多步出不来，甚至发生 循环，所以效率高很多 下面的章节就属于本文算法的组成部分了其中第四章介绍利用主元标【2 0 】生成初 始基的算法和利用摄动算法【3 2 ，嚣】以达到对偶可行的一阶段算法；第五章是本文的主体 部分，介绍对偶二分单纯形算法的主算法( 二阶段算法) ；第六章则是本算法的数值实验 结果和分析 第四章主元标概念及利用其生成初始基的算法 无论是经典的单纯形算法，还是它的哪种改进算法，其本质都是在每一步迭代中，确 定一个离基变量和一个出基变量，即确定主元，以寻求下一个使得目标函数下降的基本 解所以理想的办法应该是在迭代的过程中，使得最优基变量进基，同时使得最优非基变 量离基可是在没有找到最优基之前，我们当然是无法判断哪些变量是基变量，哪些是非 基变量但我们却可以从几何角度来刻划最优基的特征潘平奇教授在1 9 9 0 年发表的文 章【别中对于不等式约束的线性规划问题提出了一个启发式的主元标算法，受此影响随 后又出现了类似文章的发表，如【7 ，3 9 ，如】本章我们对主元标知识作一个回顾，并讨论由 此导出的对偶主元标的概念 4 1 主元标及其几何解释 在此我们首先引入文 2 0 】中的主元标概念以作对照，考虑以下形式的线性规划问题 h ， 8 to i r z 玩 i = 1 ，m( 4 1 b ) 0j = 1 ， ( 4 1 c ) 其中c = ( c 1 ，c 2 ，c n ) t ，a d j = 1 ，m ) 为n 维列向量 定义4 1 这是一个只含不等式约束的线性规划问题，其中变量的主元标定义 为； 哪= 白，j = 1 ，n ( 4 2 ) q = ( ，哪。) i q 。i j = n + 1 ，n + m ( 4 3 ) 坼1 ，z 。h 分别是相应于约束d t 7 玩a = 1 ，m ) 的松弛变量这里的主元标概念 含有明确的几何意义。o j i c i 正好等于目标函数的梯度( 价值系数向量) 与下列约束； 2 0 j = 1 ，“ 町r z 如一。 j = n + 1 ，n + 仇 1 6 ( 4 4 ) ( 4 5 ) 塞童查堂曼圭兰堡垒塞 量塑塞圭重量堡垒垦型星苎皇塞垫丝茎竺塞塑 1 7 左端函数梯度的夹角余弦，因此主元标也与各个约束之间建立了对应关系，故也可称之 为第j 个约束的主元标 为了对主元标概念有个清晰直观的了解，下面我们引入文【2 0 中的一个具体例子，考 虑线性规划问题， 蚴：= l o z + 4 0 y 8 t 屈一f20 - 3 z 一4 一 一+ 2 封一2 z 2 5 一- 7 5 z ，y 0 这是一个只含两个变量的线性规划问题，它可以由下图来表示 圈4 1 主元标昀几何解释 从上图可以看出在最优点( 1 0 ，7 5 ) 附近两个约束超平面的法向量和目标函数的法向 量的夹角是最大的因为一般这个角都是钝角，所以也可以说是最钝的这就是最初最钝 角思想的直观的几何解释同时在最优点附近的这两个约束是积极约束，它们所对应的 松弛变量取值应该为零一般地说取值为零的变量是最优非基变量，这也就是说最优非 塞塞奎竺矍圭堂堡垒茎 篁璺塞圭垂堡堡垒垦型星茎皇塞垫丝董箜塞鋈 1 8 基变量的主元标相对偏小，因此有下面结论 结论4 1 线性规划问题“u 的最优基变量倾向于具有较大的主元标，而其最优非 基变量则倾向于具有较小的主元标 ， 我们自然而然地有这样一个想法，就是在确定初始基的时候就尽可能取那些具有较 小主元标的变量作为初始基变量，这样生成的初始基就可能和最优基很接近那么就有 人要问了，这样是否能直接生成最优基呢应该说确实有这种可能性，图4 - 1 所表示的问 题就正好是这样而且事实上，结论4 1 所给出的启发式特征是非常有效的，一般可以来 说它可以产生个接近于最优的初始基，甚至在某些特殊情形下可以直接产生最优基( 详 见文 2 0 1 ) 同时我们也有以下结论： 结论4 2 线性规划问题“ 的约束矩阵的具有较大主元标的列有优先进基的权利， 当出基比较大小或者是比较最小比时出现多个变量相同时，即出现“e 时，具有较小主元 标的列则有优先出基的权利 现在我们就要利用这个原理来生成初始基，这个方法在文1 2 1 】上有详细叙述 我们首先根据定义( 4 2 ) 和( 4 3 ) 的主元标概念计算出包括松弛变量在内的每一个变 量的主元标，并且把这些变量按照从大到小排列起来，依次记为脚，r = 1 ，t 1 那么我 们是否就可以直接取前m 个变量作为基变量呢? 遗憾的是答案通常是否定的，这是因为 这m 个变量是否线形相关我们还不得而知，而基变量显然是不能线形相关的那么我们 可以这样找，先把主元标最大的一列作为基矩阵的第一列，然后再检查第二列是否与现 在基矩阵( 目前只有一列) 第一列线性相关如果线性无关，就将其加入基矩阵，作为基 矩阵的第二列；如果线性相关。就跳过这一列，再检查第三列是否与现在基矩阵线性相 关如此进行下去，直到找到m 个列向量为止，此时就得到了一个仇m 的满秩方阵， 这个方阵就可以作为初始基矩阵了那么这个过程具体怎么实现呢? 基矩阵的逆矩阵又 如何计算呢? 这里我们可以利用g r e v i l l e 技术( 1 9 6 0 ) 来解决这一问题假设也是( m k ) 矩阵， 是m 维列向量如果我们定义矩阵a k + l 如下； 敏4 1 = ( a ka k 4 1 ) ( 4 6 ) 奎塞查兰堡圭兰堡垒塞塞塑塞圭垂堡堡垒墨墅里苎皇堡垫丝董墼塞童 1 9 那么再分别定义k 维向量砝和m 维向量c k 如下。 靠= a z 毗 ( 4 7 ) e k = a k a k d k = a k a k a + 8 ( 4 f 8 ) 其中a 吉是血的m o o r e p e n r o a e 广义逆 那么由文【2 1 】第7 3 4 页的引理5 6 和上面的记号( 4 6 ) 到( 4 8 ) ，我们有以下性质： 性质4 1n 乏胆玎性质最砂假如如是列满秩，秩为k ，那么a k + 1 也列满秩，即秩为 + 1 的完要条件是“剐定义的c k 0 注意这里的0 是指零向量 下面的g r e v i l l e 方程给出了如何通过钟来计算a z + 。 定理4 1 仗 e l 定理e 圳使用“砂到“矽的记号，a k + 1 的m o o r e p e n r o a e 广 义逆可以按照下面的公式由 吉来生成t = ( 唾) 其中昭= = ( 露c k ) 一1 ，如果e k 0 ；唾= ( 1 + d k ) - 1 a z ，如果= 0 我们现在各项工作都准备好了，结合上述g r e v i l l e 技术和结论4 1 ，4 2 ，生成下面的算法 4 1 ，该算法逐步生成基矩阵及其m o o r e p e n r o s e 广义逆 算法4 1 矩阵a 是问题“ 的约束矩阵，主元标依次是q ，j = 1 ，n 1 对矩阵a 的所有变量，包括松弛变量按照主元标大小进行排序，并且依次记为 脚，r = 1 ，n 2 设- 4 0 = a 。，并计算a t = ( 嚷d 。) - 1 嵋 3 设k = 0 和r = 1 。 4 设k = 女+ 1 5 设r = r + 1 6 计算d k = + - l 口“和e k = a 一 一l 也 7 如果像= 0 和r n ，说明当前这一列，即第r 列和当前基线性相关，所以这一列 不能加到基矩阵里面去，需要跳过这一列，转步骤5 奎查奎皇至圭堂堡垒塞量堡塞 圭垂堡堡垒墨型里苎皇堡垫丝墨墅塞望2 0 8 如果0 ，则说明当前这一列，即第r 列和当前基线性无关，即这一列可以加到 基矩阵里面去，那么设a k = ( a k l t a b ) ，再利用g r e v i u e 方程计算a 吉 9 如果k m 且r n ，说明完整的基矩阵还没有找到，而整个矩阵a 的列也还没 有搜索完，所以可以可以往下继续寻找可以加入基矩阵的列，那么转步骤j 1 0 如果k = 仃l ，当前基矩阵的行敷和列数相等，说明完整的基矩阵已经找到，这就 是我们所需要的初始基，算法结束 定理4 2 如果算法# 1 在输出a k 后结束，这里也是一个m x m 的满秩方阵，而且 同时也得到了它的逆矩阵a 者，那么算法一定结束在步骤j 以 该定理无需证明总之，经过该算法就得到了初始基和初始解由于是按照主元标的 大小顺序进基的，由主元标的几何意义知。用这种方法生成的初始解的积极约束往往和 目标函数的超平面夹角比较钝，所以更接近于最优解那么现在我们就可以考虑它的对 偶形式，即对偶主元标陬，别 4 2 对偶主元标概念爰算法 在使用原始的主元标生成初始基的时候需要注意的是，它仅仅针对所有约束都是不 等式约束的问题，而大多数线性规划问题都是等式约束对于约束是等式约束的线性规 划问题，该算法就无能为力了不过我们考虑到等式约束的标准线性规划问题的对偶问 题恰恰是只包含不等式约束的线性规划问题，而原始问题和对偶问题在最优解存在的前 提下最优值相等这给了我们一个很好的提示，可以通过考虑对偶问题的主元标来生成 一个接近对偶最优基的初始基 下面我们来介绍对偶主元标的概念和性质由于最早引入对偶主元标概念的文【4 5 】 定义有误，我们按照文印1 中的正确定义来介绍 考虑如下标准线性规划同题， r a i nc t z ( 4 9 a ) 乳ta z b ( 4 9 b ) z 0 ( 4 ，9 c ) 其中c ，z i n ，b 胪，a r m 。“，r a n k ( a ) = m 奎! 查兰曼圭堂堡垒塞篁璺兰圭重堡堡垒垦型里苎生些垫篁董墼塞鎏 2 1 再考虑它的对偶问题； mb t y ( 4 1 0 a ) 8 ta 7 ”+ 8 = c ( 4 1 0 b ) 8 0( 4 1 0 c ) 其中c ，8 ，z 舻，b ，剪舻，a r m 。“，r a n k ( a ) = 仇 剔去松弛变量s 就得到了一个纯粹不等式约束的线性规划问题 ，r m 矿 ( 4 1 l a ) 8 t a t y 一c “1 l b ) 这样类似前一节的主元标定义，由于没有变量约束，所以定义较为简洁，仅有一种情形 按照文 5 0 l ，定义如下； 定义4 2 对于线性规划问题“1 1 ) ，变量8 j 的主元标定义为。 岛= 一( b t a j ) l l a j l ， ，= 1 ，竹( 4 1 2 ) 类似结论4 1 有如下结论， 结论4 3 线性规划问题“1 1 ) 的最优基变量具有较大的主元标，而其最优非基变量 具有较小的主元标 由于这是从对偶角度来定义的主元标，所以为了和前面定义的主元标相区别，我们 称之为对偶主元标利用定义4 2 同样就定义了线性规划问题( 4 9 ) 中变量$ 的主元标， 并根据互补松弛条件x t 8 = 0 得到了下面的结论， 结论4 4 线性规划问题似鲫的最优基变量具有较小的主元标，而其最优非基变量 具有较大的主元标 ， 因为情况和原始情形下主元标的特征正好相反，所以我们就可以按照主元标从小到大 的顺序来排列主元标，而不是从大到小，这样就形成线性规划问