（运筹学与控制论专业论文）线性规划的最钝角对偶松弛算法.pdf

摘要 本文将最钝角原理与放松约束的思想相结合，提出了求解标准线性规划问题的。最 钝角对偶松弛算法先基于最钝角原理略去对偶问题中的部分约束条件得到个规模较 小的子饲题，它的原问题有较少的变量用亏基对偶单纯形方法求得其最优解后，舔加略 去的变量( 作为非基变量) 得到一个与原来问题等价的问题，检验相应的解是否为其最优 解；如果不是，则它必为一个原始基本可行解。于是可用亏基单纯形法求解得到最优解 我们的初步数值试验表明，与传统两阶段单纯形算法相比，本文提出的算法能有效 地减少迭代次数；由于其中用于较小松弛子问题的迭代占很大比重，从而就大大降低了 求解线性规划问题所需要的c p u 对闯，新算法对于大规模同题的求解具有潜在的优势， 值得进一步研究 关键词：线性规划最钝角原理放松问题亏基原始单纯形法亏基对偶单纯形法 a b s t r a c t w ec o m b i n et h em o s t - o b t u s e - a n g l ep r i n c i p l ea n dt h ei d e ao fr e h x i n gc o n s t r a i n t st oo f f e r as o - c a l l e d 。m o s t - o b t u s e - a n g l ed u a lr e l a x a t i o nm e t h o d f o rs o l v i n gs t a n d a r dl i n e a rp r o 掣a m - m i n gp r o b l e m s b a s e do nt h em o s t - o b t u s e - a n g l ep r i n c i p l e ，w ef i r s td e l e t eac e r t a i np a r to f c o n s t r a i n t s ，a n dc o n s e q u e n t l yo b t a i nas m a l l e rd u a ls u b p r o b l e m ，c o r r e s p o n d i n gt ow h i c ht h e p r i m a ls u b p r o b l e mh a sl e a sv a r i a b l e s w eu b et h ed e f i c i e n t - b a s i sd u a ls i m p l e xm e t h o dt os o l v et h e l a t t e r e x p a n d i n gt h ed e l e t e dv a r i a b l e s ( a sn o n b a s i co n e s ) ，w et h e no b t a i nap r o b l e me q u i v a l e n t t ot h eo r i g i n a lp r o b l e m ，t ow h i c ht h ea s s o c i a t e ds o l u t i o nm u s tb ep r i m a lf e a s i b l eb a s i c i nt h e c a s ew h e nt h i ss o l u t i o ni sn o to p t i m a l ，w ec o n t i n u eo nf o ro p t i m a u t yb yu s i n gt h ed e f i c i e n t - b a s i s s i m p l e xm e t h o d o u rp r e h m i n a r yc o m p u t a t i o n a lt e s t ss h o w ，c o m p a r e dw i t ht h ec o n v e n t i o n a lp h a s et w os i v a - p l e xm e t h o d ，t h a tt h ea l g o r i t h mp u tf o r w di nt h i sp a p e rc a l lr e d u c et h en u m b e ro fi t e r a t i o n s b e c t h ei t e r a t i o n sr e q u i r e dt os o l v et h es m a l lr e l a x a t i o np r o b l e mf o r mt h em o s tp a r ta m o n g t o t a li t e r a t i o n s ，m o r e o v e r ，t h ea v e r a g ec p ut i m en e e d e df o ro n ei t e r a t i o ni 8a l s or e d u c e d f o r p r o g r a m sw i t hl a r g e 髓8 l 鹪，t h e r e f o r e ，t h en e w a l g o r i t h mh a sp o t e n t i a la d v a n t a g e s ，a n dd e s e v v e s af u r t h e ri n v e s t i g a t i o n k e y w o r d s ：l i n e a rp r o g r a m m i n gt h em to b t u s ea n g l ep r i n c i p l e r e l a x a t i o np r o b l e m d e f i c i e n t - b a s i ss i m p l e xm e t h o dd e f i c i e n t - b a s i sd u a ls i m p l e xm e t h o d 东南大学学位论文 独创性声明及使用授权的说明 一学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成 果尽我所知，除了文中特别加以标明和致谢的地方外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过的 材料与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表 示了谢意 二、关于学位论文使用授权的说明 签名：毖d ! 燕日期：望1 2 ：f 1 2 口 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文本人电子文档的内容 和纸质论文的内容相一致除在保密期内的保密论文外，允许论文被查阅和借阅，可以公 布( 包括刊登) 论文的全部或部分内容论文的公布( 包括刊登) 授权东南大学研究生院办 理 签名：拯! j ! 垂导师签名日期：越f ：丝 第一章引言 1 1 综述 线性规划是产生较早，影响最深远和应用最广泛的一个运筹学分支历经半个多世 纪的发展，其理论已日臻成熟，并已成为国民经济，科学技术。管理和工程等诸多领域不 可或缺的数学工具 线性规划经历了三个里程碑式的发展。 1 1 9 4 7 年，g b d a n t z i g 1 ，2 】中首次提出了线性规划模型及单纯形算法，标志着这 一学科的创立随后，线性规划的理论，算法和应用如雨后春笋般迅猛发展单纯形算 法本身也日趋成熟与完善尽管该算法的时间复杂性是指数阶的，然而它在实际应用中 的表现却十分出色，取得了令人注目的显著效果，成为应用最广泛的数学工具之一后 来，b o r g w a r d t ： 3 】和s m a l e 证明了单纯形算法的平均运算次数是多项式阶的因而无论在 理论上还是实践中，单纯形算法都具有极其重要的地位 2 1 9 7 9 年，苏联青年数学家哈奇扬提出了第一个具有多项式时间复杂性的算法一 椭球算法【4 ，5 】，从而证明了线性规划问题确实存在多项式时间算法椭球算法是理论上 的个重大突破但遗憾的是广瑟的实际检验表明其计算效果远比单纯形算法差 3 1 9 8 4 年，k a r m a r k a r 6 1 中提出了求解线性规划问题的另个具有多项式时间复杂 性的算法- - k a r m a r k a r 算法，并由此掀起了一股内点法热理论上，k a r m a r k a r 算法的计 算复杂性的阶比椭球算法还有所降低，且实际效果很好，因而引起了学术界的广泛关注 许多学者曾认为，对于中小型线性规划问题而言，内点算法稍逊于单纯形算法；而对于大 型稀疏线性规划问题，前者则胜于后者然而近年来单纯形类算法也有重要进展，使这两 类算法形成了不相上下难分胜负的局面特别是在求解整数规划问题上。单纯形类算法 的地位目前尚是不可替代的 本文提出算法属于单纯形类算法，致力于进一步减少迭代次数提高效率对于大规 模线性规划问题，通过减少约束条件来降低其规模似乎是一种很吸引人的想法如文献 【4 2 】就介绍了。松弛算法。其基本思想是：若原问题的约束条件很多，可先取其中一部 分约束条件求解，得到最优解后判别它是否为原问题的最优解；若不是，就换一些约束再 奎童奎耋堡圭堂堡篁塞 篁三塞! ! 童 2 求解，如此重复直至求出原问题的最优解以此化为规模较小的予问题的求解然而该方 法略去和加入约束都带有很大的盲目性，以至于有可能增加所需要的迭代次数 显然，若预知哪些约束是最优解处的积极约束，那么只要略去那些非积极约束，就可 以立即求出问题的最优解，可惜我们事先并不知道尽管如此，潘平奇教授给出的最优 基的启发式特征刻划( 最钝角原理) 【7 】可以作为一个较好的出发点他引入的反映约束 梯度与目标梯度夹角大小的。主元标可以作为略去或保留约束的依据文【4 3 】基于此提 出了个新的松弛算法，所构造的子问题有较少的约束条件但并不改变变量个数而本 文则从对偶角度出发，提出了最钝角对偶松弛算法，该算法构造的子问题有较少的变量 我们对该算法用f o r t r a n 语言编写程序加以实现，进行了初步的数值试验结果表明，与 传统两阶段单纯形算法相比，该算法能够有效地减少迭代次数；更由于其中用于较小松 弛子问题的迭代占很大比重，从而大大降低了所需要的c p u 时间新算法对于大规模问 题的求解具有潜在优势，是个极有前途的算法 本文的框架如下。随后一节将介绍本文所用的一些记号并简述单纯形法的基本概念 和定理；第二章，简要介绍亏基的概念【8 】和亏基原始单纯形算法【9 ，1 0 及亏基对偶单纯 形算法【8 ，i i ，1 2 】第三章，介绍主元标和最优基的启发式特征刻划；第四章，给出了最钝 角对偶松弛算法；最后一章报告我们的数值试验结果，并将新算法和传统两阶段单纯形 算法进行了比较和分析 1 2 基本概念和定理 单纯形算法的基本思路是，从个基本可行解开始，先判定其是否为最优解若是最 优解则停止否则，沿某边方向到达另一个基本可行解，再进行判定如此迭代进行。直 至找到最优解，或判定其无界但怎祥进行迭代，判定，如何判断是否是最优解或无界， 则需要相应的理论和方法下面我们简单介绍单纯形算法的基本理论及相关概念 考虑如下标准线性规划问题 r a i n c t = ( 1 1 a ) 8 t 血= b f 1 1 b ) z 0 ( 1 1 c ) 塞塞查堂堡圭耋垒篁塞篁三塞! ! 童 3 其中a r m 一，r a n k ( a ) = m ( m n ) ，c 、z 酽，b 矽，并且b 20 ，b 、x 、c 的分量不全 为零 相应的对偶问题为 i n a x b r v( 1 2 a ) 8 t a t y + ；= c( 1 2 b ) ：0 ( 1 2 c ) 其中驴，z 舻 此外，符号作如下规定 口j a 的第j 列； e 第 个分量为1 的单位向量； 向量的第j 个分量； 跪( ) 矩阵的域空间； i i j | 向量的2 - 范数； 矩阵 用大写的英文字母a ，b ，l ，u 等表示； 列向量用小写的英文字母a , b ，c 等表示 定义1 1 设b 为矩阵a 中的一个m 阶满秩方阵，则称口为一个基( b a s l s ) ；b 中 m 个线性无关的列向量称为基向量( b a s i sv e c t ；中与之对应的m 个分量称为基变量 ( b a 8 i bv a r i a b l e ) ，其余的变量称为非基变量令所有的非基变量取值为零，得到的解z 。 功 ”【甜j= p 0 称为相应于b 的基本解( b a s i cs o l u t i o n ) 定义1 2 若一个基本解满足z 0 ，即其也是一个可行解，则称z 为一个基本可行 解( b a s i cf e a s i b l es o l u t i o n ) ，这时对应的基b 称为可行基( f e a s i b l eb a s i s ) 定义1 3 一个基本可行解z ，如果其所有的基变量都取正值，则称之为非退化的 ( n o n d e g e g e n e r a t e ) ；反之，如果有的基变量也取零值，则说其是退化的( d e g e n e r a t e ) 个 线性规划问题，如果它的所有基本可行解都是非退化的，就称该问题是非退化的，否则就 说它是退化的 壅室查兰塑圭堂堡垒茎量三塞! 堕 4 定义1 4 一个基本可行解z ，如果满足式( 1 1 a ) ，则称之为线性规划问题的最优解； 相应的目标函数值，z 称为线性规划问题的最优值 关于解、基本解、基本可行解等概念之间的关系，我们列举下面的基本结论 定理1 5 可行解z 是基本可行解的充分必要条件是其正分量所对应的列向量线性 无关 定理1 6 若一个标准的线性规划问题有可行解，则其必有基本可行解 定理1 7 若个标准的线性规划l 可题的目标函数有有限最优值，则必可在某个基本 可行解处达到 上面的定理说明对于标准的线性规划问题，若其存在有限最优值，则我们可以在基 本可行解的集合中去寻找最优解然而当矩阵的列数n 很大时，基本可行解的个数比较 大，枚举法显然是不可取的单纯形算法则是依照一定的规则在基本可行解的一个子集 中去寻找最优解下面介绍单纯形算法的相关理论 假设我们已有个非退化的基本可行解s z 七 n 。， 对应的基矩阵为b ，非基矩阵为，= 【，西】，则式( 1 1 b ) 化为， x b + b 一1 n x , v = b 一1 6( 1 4 ) 不妨设s = ( a l ，口，1 ) ，记向量 动= b 一1 即= ( 面u ，砧玎) r ，j = l ， 5 = b b = ( 5 1 ，k ) t 以及 则式( 1 4 ) 化为t 幻+ q 勘= 5 东南大学硕士学位论文第- - 章亏基单纯形算法 或 z b + r z n = i 目标函数化为。 c t z = 靠5 + e ( 勺一矗嘞) 巧 j = 仇+ l 令白= 乌一霸弓，j = i ，t l ，则有 5 ( 1 5 ) ，= c t 一西b - 1 a = 妇，厶) = ( 徭，留) = ( o ，磊一n r b - t c b ) 则问题( i i ) 可化为t m i n 西b 一1 6 + c t z( 1 6 a ) & t x b + b 一1 n x = b 一1 b( 1 6 b ) 0 ( 1 6 c ) 定理1 8 如果i 使得式( 1 6 a ) 中e 0 ，则牙为原问题的最优解 定理1 9 如果式( 1 6 a ) 中向量e 有分量厶 o ( 显然m + 1 s k n ) ，而向量乱s0 ， 则原问题无界 定理1 1 0 如果式( 1 6 a ) 中向量e 有分量矗 0 ，且碓至少有一个正分量，则能找 到基本可行解量，使，圣 c t e 以上三个定理给出了单纯形算法的工作原理，即不断地从一个可行基迭代到与它相 邻的另个可行基，直至找到最优基( 若最优基存在) ，或判定原问题无界下一章将要介 绍的亏基单纯形算法就是在这些原理的基础上建立不同的构架得到的 第二章亏基单纯形算法 单纯形方法是求解线性规划问题最为有效的方法之一，可惜退化现象严重影响了它 的计算效率为了克服退化带来的困扰，众多学者相继提出了如扰动法【l9 】字典序规则 【2 2 l 及b l a n d 规则 2 0 l 等各种不同的有限规则主元规则，虽从理论上避免了循环的出现， 但实际计算中迭代次数太多，表现远不及传统规则好；而非有限规则中，实用的h a r r i s 行 主元规则【2 5 】表现甚佳，最陡边规则被认为是目前最好的列主元规则近年来，潘平奇教 授引入了亏基的概念，并由此提出了亏基单纯形算法。该算法能够有效地克服退化带来 的计算困难本章中，我们将介绍亏基的概念及其算法的基本结果【8 】 2 1 亏基 单纯形算法中，基是一个最基本，最重要的概念，传统的基定义为由系数矩阵的1 3 1 个线性无关列所构成的方阵。m 是系数矩阵的行数由于基的列数被固定为m ，故当右端 项b 在基的域空问的某一真子空间时，就会出现退化现象 考虑问题( 1 1 ) ，潘平奇教授把传统基的概念推广如下 定义2 1 系数矩阵a 的若干线性无关列所构成的矩阵称为基，若其张成的空间包 含右端项b 据以上定义，基可以分为两类t 定义2 2 如果基的列数小于行数，则称为亏基；否则称其为完全基 可见传统单纯形算法所使用的基只限于完全基 设矩阵口是由8 0 m ) 个列向量组成的基矩阵，为a 中除去b 的各列所构成的 非基矩阵，其列数是n 一8 ，相应的基指标集和非基指标集定义如下 j 童= j l ，南，j o ，j n = k l ，如，k 一。)( 2 1 ) 其中五o = 1 ，s ) ，为口的第i 列的指标；幻u = 1 ，n 一。) 为的第j 列的指标我 们称基指标五的下标为行指标，非基指标b 的下标为列指标；向量z 、c 和矩阵a 相应 于基和非基指标的各分量或列分别称为基( 本) 的和非基( 本) 的相应的，对a ，c ，z 可 6 奎童查兰堡圭兰堡垒塞篁三耋茎董苎堡翼塞堡 做如下划分： a = 归，卅= q l 一，a j - ，i ，一，一) ，= 障，西】= ( 勺。，c k l c ，c k 一。) ，= 陋暑，z 爵】= ，k 。，。k 一。) 由以上分块，问题( 1 1 ) 可改写为t r a i n 西x b + 西z s t b x b + n x n = b z b ，z 0 相应的对偶问题( 1 2 ) 可写为 矿 & t 阱+ 卧矧 z b ，z n 0 ( 2 6 ) 下一节中，我们将在亏基的基础上，介绍对传统单纯形算法进行修改而建立的亏基 原始单纯形算法在计算过程中，基的列数将随着迭代过程动态的变化 2 2 亏基原始单纯形算法 为方便起见。我们利用增广矩阵来代替问题( 1 1 ) 对于任意的非奇异矩阵q r ”， q r b ，q t n ，q 7 6 j 显然与陋， 6 】等价特别地，可以确定一个正交矩阵q z ，使得 q t b 舻m ( 其中，8 为基b 的列的个数) 是个上三角矩阵，此时，矩阵 q t b ，q t n , q 7 6 】 被称为正则矩阵( 或增广矩阵) 可以看出，由于b 是一个基，因此，q r b 的对角元均为 非零，并且。若q r b 的最后m s 个分量存在，则全部为零 现假设已知个正则矩阵 q r b ，q t n , q r b 及相应的指标集如和j 为叙述方便， 仍记此正则阵为旧， 6 | 假设s m ，并加入价值向量行，然后对矩阵进行适当划分，则 7 刁 钟 砷 p 0 q 0 奎童查兰堡圭竺堡墼塞篁三兰茎董呈堡堡垒堡8 问题( 1 1 ) 可描述为如下的表格形式； f bn6 1 【奄西。j 2 b 1 n 1b l 0n 20 瑶西0 其中b 1 彤。为上三角阵，l 彤( n m 。2 r ( m - s ) 。如一w ，he 彤 从表( 2 7 ) 可得个基本解 ( 2 7 ) 牙= 0 2 b = b i l 6 l ( 2 8 ) 检验数i 也可从表格上得到事实上，用g a u s s 滑去法将( 2 7 ) 中价值向量行中的基 指标集对应的元素消去，就可得到表格 b x lh 0 20 2 0 蟊一l ( 2 9 ) 同时可得知= c n w c b ，目标函数值，= 西b i l 6 1 我们称( 2 9 ) 为正则表 下面考虑某一次迭代不妨假设当前的正则表( 2 9 ) 原始可行，即2 b 0 ( 1 ) 若和0 ，则已求得最优解，停止 ( 2 ) 否则，即籼中有小于零的分量，由传统的d a n t z i g 列主元规则确定一个非基列进 基，其列指标确定如下： q = a r 9 m 舌n ( 魂。b = 1 ，2 ，n 一8 ) ( 2 1 0 ) 显然魂 0 ，此时n 的第q 个非基列a k 将进基，相应的基变量为虿k 考虑如下两 种情形， 情形1 ：8 = m 或s 0 ，则可由最小比检验确定行指标p l a = 警= m 州等睢，p 0 ( 2 1 3 ) t j p地 此时让基列出基，其中行标p 满足式( 2 1 3 ) 当非退化时，i b 0 ，则( 2 1 3 ) 对应 的不等式成立此时，随着非基变量砘的值由零增加到a ，的值由减为零，并且 其它的非基变量的值以及原始可行性均保持不变这样就得到了如下的修正过的基本可 行解牙的迭代公式 瓢：2 瓢一吣 v i 2 l ，5 ( 2 1 4 、 虿b ：= a ； 然后我们将正则表中的第p 个基列移至非基列的末尾，将指标q 所对应的非基列移 至基列末尾。并相应地调整有序集合如和知若p = 8 则所得到的b j p ”已经是 上三角；否则( p 8 ) ，b 是上h e s s e n b e f g 阵，其第p 列至第8 1 列的次对角元素非零， 此时通过g a u s s 消去或g i v e n s 旋转变换将该h e s s e n b e r g 矩阵化为上三角阵，并保证对角 元非零这时b 胪或b i 彤是上三角且对角线元素非零 这样就完成了一次迭代 ( n ) 情形2 出现时，当且仅当o g 瓣( b ) 在这种情况下，进基变量孟k 的值不能从零开始增加，因为这样有可能破坏后( r t - 8 ) 个约束条件，因此必须增加基的列数我们可以对矩阵 b ， b l 左乘h o u s e h o l d e r 反射变 换矩阵，将n k 的第8 + 2 到第m 个元素化为零，并将正则表( 2 0 ) 中的第g 个非基列移 至基的末尾，然后令s = 8 + 1 ，并相应地调整有序集合西和如，此时基增加一列，再 塞堕奎堂堑圭竺堡篁奎篁三塞重董塞丝堡堡堡 1 0 用g u 蝴变换即可得到上三角矩阵b t r ( 1 + 1 ) 。n 此时原来的基本可行解不变，这样 亦完成一次迭代 在这两种情况下，显然6 的子分量0 2 并未改变，依旧为零当我们用g a u s s 变换将 新进基的列所对应的价值向量中的元素零化后，就产生了一张新的正则表重复这样的 步骤，直至得到最优解或者判断问题无界 由于基的列数在情形1 中没有改变，而在情形2 中增加了一列，故相应地迭代分别 称为保秩迭代和增秩迭代在整个计算过程中，基的列数会动态的增加，但不会减少 我们将以上步骤归纳为如下的算法： 算法2 1 ( 亏基原始单纯形表格算法) 对于问题( 1 1 ) ，给定初始正则表( 2 9 ) 及相应的有序集合如和如，并假定由此导出 的基为可行基 1 如果i 0 ，则停止； 2 据式( 2 1 0 ) 确定进基的列指标q ； 3 如果s m 且q t a l q 的第8 + 1 至第m 个元素不全为零，转1 1 ； 4 由( 2 1 1 ) 式计算向量”； 5 若( 2 1 2 ) 式定义的集合j 为空集，则停止； 6 按规则( 2 1 3 ) 确定步长a 及相应的行指标仍 7 据式( 2 1 4 ) 修正基本可行解i ； 8 将( 2 9 ) 中的第p 个基本列移出基列，并将指标q 所对应的非基列放至基本列的末 尾，相应的调整如和妇； 9 若p s 。则将上h e s s e n b e r g 矩阵b 上三角化，并保证对角元非零； l o 转1 3 ； 1 1 若s m 一1 ，通过对旧，l v , b 左乘一个适当的h o u s e h o l d e r 矩阵，将o k 的第s + 2 至第m 个元素化为零，并令s = 8 + 1 ； 1 2 将( 2 9 ) 中的第q 个非基列进基，移至基列末端，并相应地调整如和j n ； 1 3 用g a u s s 变换消去黾； 1 4 转1 东南大学硕士学位论文第二章亏基单纯形算法 1 1 由于基的个数有限，故若算法不出现循环，必将有限步终止此外，由于增秩迭代不 会产生循环，故循环只会出现在保秩迭代中若在保秩迭代中保证了非退化，则循环情况 就不会发生这样，就得到了如下结论。 定理2 4 在保秩迭代中的原始非退化假设下，算法2 1 终止于 ( i ) 步骤( 1 ) ，则找到原线性规划问题的最优解；或 ( n ) 步骤( 5 ) ，说明原线性规划问题无界 2 3 亏基对偶单纯形算法 本节我们将在亏基的基础上，简单的介绍对传统对偶单纯形算法进行修改而建立的 亏基对偶单纯形算法，详细内容可参见文【8 】 算法2 2 ( 亏基对偶单纯形表格算法) 设标准线性规划问题( 1 1 ) 的对偶问题( 1 2 ) 相应的初始正则表为 h b 。1 飓n 1 。l 仁埘 相对应的的集合为如和j 知。且设细= c n 一f b f 印20 1 计算妇= f 下1 6 i ； 2 若劢0 ，则停止( 获得最优解) ； 3 据式i ：= m i n 孑j , l i = l ，2 ，8 ) 0 确定行指标p ； 4 将b 的第p 列移到的末尾，并相应的调整如，如； 5 若p 8 ，对旧，n b l 左乘一系列适当的g i v e n s 旋转，将b 的第p 列到第0 1 ) 列的次对角线上的元素化为零； 6 计算d = 一黝n ( e 三。钾6 1 ) 矸q 1 。； 7 若集合，= d i 而 0 ( 3 1 0 ) 注意到，对充分小的口 0 , x = 矿+ 唧 满足后n + m p 个约束此外，利用a 0 。( 3 7 ) 和( 3 8 ) 我们有 a z = a z + n a y b( 3 1 1 ) 利用a 0 和( 3 1 0 ) 式，我们有 = + + a c y + f 3 1 2 ) 也就是说z 这一可行解，其对应的函数值比大，这与矿是最优解矛盾所以。 对任何满足( 3 8 ) 的y ，( 3 9 ) 都成立于是，由f a r k a s 引理，我们知存在一个p 维列向量 p = m l ，脚) t 0 ( 3 1 3 a ) 使得 c = 一p( 3 1 3 b ) 壅室奎耋堡圭兰堡堡兰篁里塞塞墼丝塑堡垒些星鋈 1 8 将( 3 1 3 b ) 两端同乘以c 。利用( 3 1 3 a ) 和主元标的定义，可得 0 0 ，对任意i = 1 ，m 1 ，有，啦 0 ，则结论 显然成立于是，我们可以较容易地证明向量= 是可行解，这里 a 2 丘= m a x 1 ，l m a x 。 蠢h u 、 在点处，目标函数值a c r e 是无界的 上面的推论有时会比较有用例如，以例子2 来说，我们根本无需运用单纯形法，因 为从上面我们在约束条件后列出的主元标全为非负的这一特点中，我们就能得出目标函 数在可行域上是无界的这一结论 现在我们简单地讨论一下把结论1 应用于单纯形法的可能性我们从任意一个单纯 形表格开始( 以典式形式，不必可行) 在一步迭代中，我们在所有基变量中挑选具有最小 可能主元标的变量出基，在所有非基变量中，我们选择具有最大主元标的变量进基( 假设 对应的主元非零) ，形成一个新的表格，这种循环一直进行下去，直到 t t 个基变量所对应 的主元标是前m 个最大的那个表格出现为止如果这个表格是不可行的，我们通过一阶 段使其达到可行，然后象往常一样用第二阶段得到最优解 第四章最钝角对偶松弛算法 4 1 松弛算法及最钝角松弛算法 关于松弛算法，已有学者提出过( 如文献【4 1 】) ，下面本文将文献【4 1 l 中所介绍的算法 列出 考虑如下形式的线性规划问题； m i uz = c t x ( 4 1 a ) s t 如b z 0 ( 4 1 6 ) ( 4 1 c ) 其中a 驴一，c 。z 舻，b j p ，并且b 0 ，以z ，c 的分量不全为零 松弛算法的基本思想是：如果问题( 4 1 ) 的约束条件个数m 很多，为了计算方便，可 以先取其中一部分约束条件求解，求得最优解之后判断此最优解是否为( 4 1 ) 的最优解 若不是就换一些约束重新求解，直至求出( 4 1 ) 的最优解 令m = 1 ，m ) ，冗m ，构造放松问题如下， m i nz = ，z s t d ka 固 $ 2o 文献【4 1 】中所描述的松弛算法的计算步骤如下 0 d 置j = 一m ，挑选一个初始的r ，使放松问题( p r ) 的目标函数值有下界 1 0 求解放松问题( p r ) 若( p r ) 无解，则原问题( 4 1 ) 无解，停止；否则设( p r ) 的 最优解为一。最优值为z o 2 0 若妒满足a x b ，则护也是( 4 1 ) 的最优解，停止；否则令 毋v 矗ia t x 凡 玩， m r 奎童查耋望圭竺堡垒塞 董望塞量矍鱼塑堡堡塑堡堡 2 0 d = o l 砰矿 j ，划j z 0 ，再以f = d ) u v 代替原来的r ，返回1 0 在文献【4 2 1 中，在第三章所介绍的最钝角原理的基础上，提出了一个新的松弛算法 不过与第三章的主元标稍微有些不同的是，对于0 的约束不给予主元标的定义，定义 啦= 黑，扛l ，m ( 4 2 ) 啦。丽4 2 1 ” 【4 2 ， 为第 个约束的主元标 该松弛算法是将所有主元标为负值的那些约束挑出，构造放松问题( p r ) 此放松问 题( p r ) 在绝大多数情况下是有界的，但有时也会出现无界的情况此时，我们通过加入 一个人工约束来构造新的放松问题 r a i n ；：j - ? s t 口b io r )( _ p 爿) 畅m o 0 其中m 为个充分大的数，j 为( p 8 ) 闯题中的非基变量的下标。 最钝角松弛算法的计算步骤如下t 0 0 用( 4 2 ) 式计算各约束条件的主元标啦， = 1 ，m ，将主元标为负值的那些约 束条件挑出，记r = a i 啦 0 ， = 1 ，1 ) ，l = i( 4 4 ) 这里i i 表示集合中元素个数( 即，主元标为正值的约束个数) 若j o ，i = 1 ，t l = t 1 ，由) ；若l m + 1 ，则取 j = i l ，+ 1 ) 。令l = m + 1 ，构造于问题( 4 5 ) 和( 4 6 ) 童用亏基对偶单纯形法求解子问题( 4 5 ) 和( 4 6 ) 若( 4 5 ) 无可行解，则原对偶问题( 1 2 ) 无可行解，且原问题( 1 1 ) 无界或无可行解，停止；否则，得最优解：z ；，才，v 7 ，( ； 0 ，才o ) ；若( 4 5 ) 无界，则求解问题( 4 1 0 ) 和( 4 a 1 ) 得最优解；：，。刁，掰，( 哮 0 ，z 7 , o ) 4 计算都= c j 一碍掰若幻0 ，子问题的最优解z ；，疗就是原问题的最优解，停止 五否则，z ；是( 4 8 ) 的一个原始可行解，利用亏基原始单纯形法继续求解，直到获得最 优解 下面我们对该算法做几点说明一 说明l t 对于放松问题，由于是通过略去原问题的一些变量得到的，原来线性无关的 m 个约束条件可能会变为线性相关，因此我们采用亏基对偶单纯形法求解 说明2 。算法1 在整体上可分为两个阶段；第一阶段求解个放松子问题，第二阶段 求出最优解，所以此算法可以认为是求解线性规划问题的一种新的两阶段算法 第五章数值试验 5 1 数值试验结果及分析 为了考察算法1 的实际表现与理论分析是否吻合，我们进行了初步的数值试验和比 较本节报告数值试验的有关结果并进行相应的分析 我们所试验的是如下两个f o r t r a n 程序； 程序c l s t 两阶段原始单纯形算法 程序m d r t 最钝角对偶松弛算法( 即：算法1 ) 以上的程序均用标准的f o r t r a n 语言编写，在w i n d o w s x p 操作系g a ：用v i s u a lf o r t r a n 9 0 环境进行编译和运行数值试验所使用的计算机为a m ds e m p r o n ( t m ) 1 4 9 g h z 的兼容 机，内存4 4 s m t w t e s ，机器精度为3 2 位所有的程序都以e = 1 0 6 为原始和对偶可行容 限，并采用了相同的均衡尺度技术( s e a l i n g ) ，都采用了h a r r i s 主元规则 用于测试的是6 0 个l p 问题表5 1 ( 表5 2 是表5 1 的继续) 给出了算法c l s 和算法 m d r 的数值结果表格的第二三四列分别列出问题的行数m 、列数n 及行列数之和 m + n ( 问题的规模) ；m d r 的表头下分别列出了算法m d r 求解放松子问题所用的迭代次 数i t e r s l 和所需的总迭代次数i t e r s ；c l s 的表头下分别列出了用两阶段单纯形算法c l s 第一阶段所用的迭代次数i t e r s l 和所需的总迭代次数i t e r s 为了比较算法的效率，在表5 3 ( 表5 4 是表5 3 的继续) 中c l s m d r 的表头下给出 了两种算法总迭代次数之比 塞童查堂堡圭耋堡垒塞篁至塞墼堡堡矍 2 6 t a b l e5 1 数值结果 m d rc l s p r o b l e m l + 竹i t e r s li t e r si t e r s li t e r s 13582234 23581133 33581134 42681222 53692235 6369 2 235 72791224 8 27 9l223 9 27 9 1l24 1 0279l223 1 1371 01l34 1 2371 03345 1 3371 02235 1 4571 2l467 1 5571 22256 1 628l o 1 3 2 3 1 7381 13435 1 8 3 81 13 3 36 1 9481 22444 2 0481 24847 2 1481 22345 2 2481 23346 2 3481 22446 2 4481 28857 2 558 1 35 6 55 2 6491 32 3 45 2 7491 31244 2 8591 44 6 67 2 9591 43357 3 0591 42637 奎室奎耋堑圭耋堡垒塞篁圣塞墼堡塑 2 7 呦l e5 , 2 数值结果( 续) m d rc l s p r o b l e mm + ni t o r s li t 七r si t e r s li t e r s 3 1 791 62 6 77 3 241 01 4 5545 3 351 01 58 8 5 1 0 3 461 01 61167 3 56l o1 6l369 61 01 62467 3 761 01 63466 勰31 11 41l36 3 941 11 5284 5 4 0 71 11 84488 4 181 11 93688 4 2 61 21 84577 4 3 61 21 84668 4 4 61 21 81l68 4 561 2 1 85678 4 671 3 加881 01 0 4 71 01 32 3341 01 0 4 881 42 21 51 5 l l1 1 4 9 61 42 03381 1 5 0 61 52 12261 3 5 17 1 5 2 2 4777 5 271 52 25 691 l 5 381 52 3 1 11 18l l 5 491 52 46 799 5 51 21 6船2 8 1 21 2 5 6 8 2 4 3 23591 5 5 78 2 43 2 881 2 弱1 12 5451 31 9 l l2 8 羽51 91 l3 1 6 01 53 7 5 27 7 2 3 3 6 t o t a l 3 2 36 6 5 9 鹄 1 9 92 7 83 5 34 8 3 塞翼查兰堡圭竺垒垒茎篁三塞墼堡塑 2 8 t a b l e5 3 算法c l s 与新算法m d r 的迭代次数之比 p r o b l e mm + nc l s m d r 13582 0 0 23583 0 0 33584 ，0 0 4268 1 0 0 53 692 5 0 63692 5 0 72792 0 0 82791 5 0 92794 0 0 1 02791 5 0 1 1371 04 1 2371 0 1 - 6 7 1 3371 02 5 0 1 4571 21 7 5 1 5571 23 1 6281 01 0 0 1 7381 11 2 5 1 8381 12 0 0 1 9 4 8 1 21 0 0 如481 20 8 8 2 1481 21 6 7 2 2481 22 0 0 2 3481 21 5 0 2 4481 20 8 8 2 5 581 30 8 3 2 6491 31 6 7 2 7491 32 0 0 嬲591 41 1 7 四591 42 3 3 3 0591 41 1 7 奎童奎耋堡圭耋堡篁兰篁三塞墼堡篁墼 2 9 t a b l e5 4 算法c l s 与新算法m d r 的迭代次数之比( 续) p r o b l e m m + n c l s m d r 3 l 7 9 1 6 1 1 7 3 241 01 4 1 0 0 3 351 01 51 2 5 3 461 01 67 3 56 1 0 1 0 3 3 661 01 61 7 5 3 7 61 01 61 5 0 黯31 l1 46 3 941 11 5 0 6 3 4 071 11 82 4 181 11 91 3 3 4 26 1 2 1 81 _ 4 0 4 3 6 1 21 8 1 3 3 4 4 61 21 88 4 561 2 1 8 1 3 3 4 671 32 01 2 5 4 71 01 32 32 5 0 鹌81 42 20 7 3 曲61 4 2 0 3 6 7 5 061 52 16 5 0 5 171 5 2 2 1 o o 5 271 52 2 1 韶 5 381 52 31 0 0 5 491 52 41 2 9 5 51 21 6船1 _ 5 0 5 682 43 23 0 0 5 78 2 4 3 22 5 0 5 8 1 12 5笳3 8 0 5 91 1船1 6 3 6 01 53 7 5 2 5 1 4 t o t a l3 2 36 6 5 9 8 8 1 7 4 奎童奎兰塑圭兰堡篁塞篁三塞墼堡塑 3 0 由表5 1 ( 表5 2 是表5 1 的继续) 和表5 3 ( 表5 4 是表5 3 的继续) 可以看出，从迭代次 数上新算法m d r 明显胜过了算法c l s 进步比较看出，在这个问题中有4 9 个问题 所需迭代次数比传统两阶段算法少，有6 个问题相当，只有5 个问题需要迭代次数较传 统两阶段算法多事实上，从表5 1 ( 表5 2 是表5 1 的继续) 和表5 3 ( 表5 4 是表5 3 的继 续) 的最后一行可以看出新算法m d r