（运筹学与控制论专业论文）线性规划二分内点算法.pdf

摘要 潘平奇教授提出的二分单纯形算法通过引入一个与目标函数相关的超平面以及对最 优值存在区间不断二分，产生一系列子问题并求解之。本文将二分单纯形算法的思想与 仿射变换相结合，导出一个新的内点算法一“二分内点算法”。该算法对最优值存在区间 不断二分生成一系列子问题，通过其求解产生一个趋于最优解的内点序列。由于每个子 问题的解为下一个子问题提供了很好的初始解，使得子问题易于求解。 为了检测新算法的有效性，本文对原仿射尺度算法和二分内点算法进行了初步的对 比试验。数值结果表明，二分内点算法好于仿射尺度算法，且对于大规模问题的求解有 潜在优势，是一种有前途的新算法。 关键词：线性规划内点算法二分子问题仿射变换 a b s t r a c t p r o f e s s o rp a np i n g - q ip r o p o s e dt h eb i s e c t i o ns i m p l e xm e t h o d i ts o l v e das e r i e so fs u b - p r o b l e m sr e s u l t i n gf r o mi n t r o d u c i n gah y p e r p l a n ew h i c hi sr e l e v a n tt ot h eo b j e c t i v ef u n c t i o n a n db i s e c t i n ge x i s t e n c ei n t e r v a l so ft h eo p t i m a lv a l u e i nt h i sp a p e r ，c o m b i n i n gt h ei d e ao ft h e b i s e c t i o ns i m p l e xa l g o r i t h mw i t ht h ea f f i n es c a l i n gt e c h n i q u e ，w ed e r i v ean e wi n t e r i o r p o i n t a l g o r i t h m - - “b i s e c t i o ni n t e r i o r - p o i n ta l g o r i t h m ”i ts o l v e sas e r i e so fs u b p r o b l e m sr e s u l t i n g f r o mb i s e c t i n ge x i s t e n c ei n t e r v a l so ft h eo p t i m a lo b j e c t i v ev a l u et oy i e l das e q u e n c eo fi t e r a t e s a p p r o a c h i n ga no p t i m a ls o l u t i o n a st h es o l u t i o no fe a c hs u b p r o b l e mi sag o o ds t a r t i n gp o i n t f o rt h en e x to n e ，e a c hs u b p r o b l e mi se a s yt ob es o l v e d w em a k ep r e l i m i n a r yc o m p u t a t i o n a le x p e r i m e n t sw i t ht h eb i s e c t i o ni n t e r i o r - p o i n t a l g o - r i t h ma g a i n s tt h ea f f i n es c a l i n ga l g o r i t h m o u rn u m e r i c a lr e s u l t ss h o wt h a tt h ef o r m e ro u t p e r f o r m e dt h el a t t e r t h en e wa l g o r i t h mi s v e r yp r o m i s i n g a 8i ts e e m st ob ea m e n a b l et ol a r g e s c a l ep r o b l e m s k e y w o r d s ：l i n e a rp r o g r a m m i n g i n t e r i o r p o i n ta l g o r i t h mb i s e c t i o n s u b p r o b l e m a f f m es c a l i n g 东南大学学位论文 独创性声明及使用授权的说明 一，学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成 果尽我所知，除了文中特别加以标明和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过 的材料与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意。 二，关于学位论文使用授权的说明 签名：l 基盥插日期；z ! 立：! 至! 鎏 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文本人电子文档的内 容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可 以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研究生 院办理。 一糊各肇吼幽s 第一章引言 1 9 4 7 年，g b d a n t z i g 【7 ，8 】开创性地提出了求解线性规划问题的单纯形算法，标志 着线性规划乃至整个运筹学学科的创立从几何直观上说，该算法从可行区域的一个顶 点沿着下降( 或上升) 边方向移动到相邻顶点，反复进行直到达到最优顶点单纯形算 法在实际计算中获得了巨大的成功，成为数十年来求解线性规知模型的主要工具学者 们随后在选主元规则、初始可行基、抗退化，数值稳定性、计算复杂性和实现技术等方 面作了广泛而深入地探索，提出了许多单纯形算法的新变种 4 ，1 1 ，4 1 1 1 9 7 2 年，美国学者k l e e 和m i n t y 【1 4 以实例表明单纯形算法不是多项式时间算法， 激发了寻找非单纯形算法的极大兴趣1 9 7 9 年，苏联青年数学家k h a c h i y a n 提出了求解 线性规划问题的第一个多项式时间算法一椭球算法( 1 3 1 ，取得了线性规划理论上的一个 重要突破然而，不久广泛的计算经验表明其实际效果并不理想，效率远比单纯形算法 差 单纯形算法在线性规划领域的统治地位一直延续到1 9 8 4 年，当k a r m a r k a r 【1 2 】提出 他的多项式时间算法时才受到动摇k a r m a r k a r 算法是一个内点算法。它从可行域多面 体一个内点出发，产生个穿过多面体内部的点列逼近最优解不仅在理论上该算法计 算复杂性的阶比椭球算法有所降低，且接着在求解大规模稀疏问题上的数值效果也超过 单纯形算法这些成功引起学术界的广泛关注，迅速掀起了一股内点法研究的热潮，获 得了丰富的成果t o d d 【3 7 把不断涌现的内点算法分为四大类，即仿射尺度方法、投影 方法、路径跟踪方法和评价函数方法其实，前苏联学者d i k i n 【1 0 】早于1 9 6 7 年就提出 了仿射尺度算法，后来又被b a r n e s 3 1 、c a v a l i e r 和s o y s t e r 5 】等重新发现仿射尺度算 法的实际效果非常好它首次表明，对大规模问题而言，内点算法是可以超越单纯形算 法的【1 ，2 另一方面，潘平奇教授1 9 9 1 年提出了二分单纯形算法f l7 j ，引入一个与目标函数相 关的超平面以及对最优值存在区间不断二分，产生一系列子问题并求解之。为了进一步 提高计算效率，本文试图将这个思想与仿射变换相结合，导出一个新的内点算法，通过 对一系列子问题的求解产生一个趋于最优解的内点序列 壅室奎兰堡圭兰堡垒塞篁三耋! ! 童 2 本文中除特别说明以外，将使用如下符号和记法t 矩阵用大写的英文字母表示，如a 、b 、l 、u 等 向量用小写的英文字母表示，如a ，b 、c 等 r n n 维实向量空间，本文中向量均指列向量 胛“m n 阶实矩阵空间 r a n k ( a )矩阵a 的秩 向量的第j 个分量 岛第i 个分量为1 的单位向量 e元素均为1 的列向量 一 第次迭代后得到的向量 丁 矩阵或向量的转置 l j矩阵或向量的2 一范数 j 单位矩阵 0空集 本文的基本框架如下；第二章简要介绍求解线性规划问题的仿射尺度算法；第三章 简要介绍二分单纯形算法；第四章给出二分内点算法；最后一章报告了我们的数值试验 结果，将原仿射尺度算法和二分内点算法进行了比较和分析 第二章仿射尺度算法 本章对求解线性规划问题的仿射尺度内点算法和仿射尺度可行点算法【4 3 】作简要地 回顾，其中的某些思想和技巧将运用在我们的新算法中 2 1 基本概念 下面简要介绍一些相关基本概念 考虑如下形式的线性规划问题； ( 2 1 0 ) ( 2 ，1 6 ) o 0( 2 1 c ) 其中a r m m ，且r a n k ( a ) = m ；c ，z 彤；b r ”；并且c 、b 以及a 的行与列 均为非零向量c t z 称为该线性规划问题的目标函数；式( 2 1 b ) 和( 2 1 c ) 称为该问题的 约束条件 定义2 1 1 在线性规划问题( 2 1 ) 中，满足约束条件( 2 1 b ) 和( 2 1 c ) 的向量 z = ( z l ，x n ) t 称为( 2 1 ) 的可行解或可行点所有可行点组成的集合称为( 2 1 ) 的可行域，记作； d = z 舻la x = b ，x2o )( 2 2 ) 其中使得目标函数取得最小值的可行解称为( 2 1 ) 的最优解 定义2 1 2 我们定义可行域d 的内部为； d o = z r “| a x = b ，x o 若z d o ，则称x 为问题( 2 1 ) 的内点可行解，简称内点若向量x d 且x 至少有 一个分量为零，则称z 为问题( 2 1 ) 的边界点 贯穿此文，假设线性规划问题的可行域d o 3 东南大学硕士学位论文第二章 仿射尺度算法 4 2 2 仿射尺度算法 本节首先介绍仿射尺度内点算法的基本思想及过程 4 6 在此，假定已知问题( 2 1 ) 的初始内点x o ，下节中具体介绍求得初始内点的一阶段方法 仿射尺度内点算法的基本思想是t 通过仿射变换，将当前迭代点移至充分远离可行 域边界的点，即利用仿射变换将当前内点映射到像空间的点e ，然后从点e 沿着最 速下降方向在某个零空间的投影移动，且移动距离不超过1 ，以保证新的迭代点仍为内 点，然后再进行逆变换，在原空间中得到一个改进的新内点解 对于线性规划问题( 2 1 ) ，假设有一个内点= x k = d i a g ( x = z 0 - 0 z 一 睡 ：0 。 0 ，我们定义对角阵 显然x k 是非奇异矩阵，则其逆矩阵x f l 是有意义的考虑仿射尺度变换； 则问题( 2 1 ) 可变换为； y = 巧1 z( 2 3 ) ( 2 4 a ) ( 2 舶) y 0( 2 4 c ) 其中芒= x k c ，五= a x k 易见仿射变换( 2 3 ) 是把正卦限映射到自身，将变换成向量e ，从而离各个坐 标平面等距离，从某种意义上局部地均衡了各个变量的尺度如果e 点在j 的零空间中 沿着下降方向移动不到1 的步长至新内点，则一也在原空间中沿着下降方向得到一个改 奎堕奎兰堡圭兰竺篁苎 篁三翼笪墅垦矍篁塑 5 进的内点x k + 1 因此，对于线性规划问题( 2 4 ) ，我们采取最速下降策略，选取负梯度 方向一# 在矩阵互的零空问中的投影为搜索方向，即； 罐= r ( 一动 ( 2 5 ) 其中的投影矩阵t 乓= i 一2 r ( 元i r ) 一1 五= i j a t ( a 艇a t ) 一1 a j ( 2 6 ) 则搜索方向为： d ：= 一【，一甄a r ( a x ：a 丁) 一1 a x k x k c ( 2 7 ) 在变换后的像空间中，从点y 。= e 沿着罐的方向移动到一个改进的新内点解y 1 0 ， 即： + 1 = y + a 硝 0 ( 2 8 ) 其中步长取为： ，一7 叫袁畹 0 ，令k = 0 ，找出初始内点。o 0 ，使得 a x o = b 1 0 计算对偶变量 。2 = ( a 髭a r ) 一1 a 磺c 2 0 计算下降费用 矿= c a t w k 3 0 检查最优性如果矿0 ，且对偶间隙e t x k s e ，停止，已得到问题( 2 】) 的最优解扩 4 0 求迭代方向 砖= 一凰扩 5 0 检查无界性和目标函数值若硝0 ( 但鹂0 ) ，停止，问题( 2 1 ) 无界； 若砖= 0 ，停止，问题( 2 1 ) 已达到最优 6 0 计算迭代步长 a * = 1 叫赢协 。 其中0 0 ，令k = 0 ，找出初始可行点z o20 ，使得 a x o = b 1 0 计算对偶变量 u = ( a 霹a t ) 一1 a x 2 c 此算法中x k 按照( 2 加) 式计算 2 0 计算下降费用。 s = c a r u k 3 0 检查最优性如果扩20 ，且对偶间隙e t x k s 2 o 作为辅助问题( 2 1 1 ) 的初始内点，利用上述仿射尺度算法 1 1j 求解如果辅助问题( 2 1 1 ) 的最优值z 乳1 0 ，则原问题( 2 1 ) 无可行解；如果问题 ( 2 1 1 ) 的最优值+ 12 o ，则由问题( 2 1 1 ) 的最优解i ：l 得到原问题2 。1 的 一个初始可行解矿 通常，在最初的时候，我们取虿= e r n 来构造辅助问题求得初始内点，即： s t a x + ( b a e ) x n + 1 = b z 20 ，z n + 1 0 显然，e r n + 1 是辅助问题( 2 1 2 ) 的初始内点 ( 2 1 2 a ) ( 2 1 2 b ) ( 2 1 2 c ) 第三章二分单纯形算法 3 1 基本定义 本节主要介绍二分单纯形算法的一些基本概念 1 7 ，2 1 】 定义3 1 1 对于线性规划问题( 2 1 ) ，设b 为矩阵a 中的一个m 阶满秩方阵，则称 b 为基矩阵，不妨设b = ( a 1 ，a 。) ；矩阵b 中m 个线性无关的列向量称为基向量； x 中与之对应的m 个分量称为基变量，其余的变量称为非基变量令所有的非基变量取 值为0 ，得到的解x ： z 七 爿 称为对应于口的基本解 定义3 1 2 若一个基本解满足z 0 ，即其也是一个可行解，则称z 为一个基本可 行解，其对应的基b 称为可行基 定义3 1 3 令集合z 是线性规划问题( 2 1 ) 所有可行值组成的集合即： z = ，z i a x = 6 ，z 0 ( 3 1 ) l p 的最优值是； z = m i n z ( 3 2 ) 定义3 1 4 对于满足 q z + 卢且口z 的区间( n ，p ) 称为线性规划问题( 2 1 ) 的最优值z + 的存在区间 定义3 1 ，5 对于线性规划问题( 2 1 ) ，所有小于z + 的可行值中最大的可行值用z 。 表示，即： z c = m a x c t x ic t x z + ，a x = 6 ，z 20 ( 3 4 ) 壅堕奎兰堡圭竺堡丝塞篁三塞三坌里丝丝塞鎏 l l 如果所有可行值均小于等于z ，则令x d = + o o 很明显，当且仅当最优值z + 存在时， ( 如，x d ) 是z + 的一个存在区间，即： z c z + x d( 3 5 ) 我们称区间( z 。，x d ) 是理想存在区问，简称理想区间 3 2 二分单纯形算法概述 1 9 9 1 年，潘平奇教授提出了二分单纯形算法【1 7 ，2 l 】，下面对其基本思想作简要的介 绍 二分单纯形算法与单纯形算法不同单纯形算法是从一个基本可行解开始，先判断 其是否为最优解，若是则停止；否则，沿着某边方向到达另一个基本可行解，如此迭代 进行直至找到最优解，或判定线性规划问题无界从几何意义上来说，它是从可行域的 一个顶点沿着下降( 上升) 边方向迭代至相邻顶点，直到达到最优顶点而二分单纯形 算法的基本思想是t 给定一个最优值存在区间，对此存在区间进行二分，判断最优值存 在于哪半个区间内，从而使得线性规划问题的可行域缩小，进而得出下一个迭代基本可 行解它不是由一个顶点迭代至相邻顶点而最终找到最优解，而是从一个顶点出发，可 能跳过很多顶点到达下一个顶点，最后得出最优基本可行解从而有效减少迭代次数 考虑如下形式的线性规划问题； 其中a 冗”。”；c ，z r “； b r m 引入一个约束条件c t x = z ，把它作为第0 个约束条件，令 ”a = h 则仍用a x = b 表示问题的约束条件且有a r ( r e + 1 ) 。“；ber ”1 ；其中a 0 3 ；c 3 ，j = 1 ，”；b o ez 假设r a n k ( a ) = k + 1 m + 1 n z = 如 一 血 痧 8 眦 土 东南大学硕士学位论文第三章二分单纯形算法 1 2 令b r ( m + 1 ) 。( + 1 ) 是基矩阵，其基指标集为； j b = j 0 ，j k 引入记号 则对应于基b 的典式为： 其中b + 是b 的m o o r e - p e n r o s e 逆 给定，如果行指标集 j b = l ，n ) j b b + a i b + b i = i i ( b + b ) i 0 ，i = 0 ，磷 是空集，则已找到一个可行解，其目标函数值是否则，利用如下主元规则换基 规则3 2 1 如果集合，非空。选择主元行指标r ； r = a r g m i n ( b + b ) i l i ， 如果集合 非空，选择主元列指标8 ： j = j i ( b + 0 f 3 1 3 ( 3 1 4 ) ( 3 1 5 a ) 东南大学硕士学位论文 第三章二分单纯形算法 1 3 ( 百+ 6 h = ( b + 6 k 一( ( b + ，( b + o 。b ) ( 口+ o 。) 。，i r ( 3 1 5 6 ) 其中r 和s 分别由( 3 1 0 ) 和( 3 1 2 ) 确定 这样一个迭代步完成显然，换基后右边项大部分分量变为正分量不断迭代，直到 j 为空集，说明已得到目标函数值为6 0 的可行解；或者集合，非空，但j 是空集，说明 不存在目标函数值为b o 的可行解然后，根据文 17 j 算法3 i i 相同步骤将当前子问题的 一个可行解校正为一个顶点一原问题的基本可行解，对此基本可行解进行最优性检测 由此，我们可以得出求解子问题的如下子算法 子算法3 2 2 ( 胁，子算法2 2 ) 给定6 0 ，令b + 是基b 的m o o r e 。p e u r o s e 逆 1 0 计算b + b 2 0 如果由( 3 9 ) 定义的集合，为空集，则， 例如果集合= 倒( b + 印) t 0 ，则令b o = b o + 盯，b + b = b + b + 盯( b + e o ) ； 似甜如果集合j = j i ( b + a j ) i 0 ，停止； “l ”计算口= 一( 口+ 6 ) ，( b + e o ) ， 0 ，令k = 0 ，初始内点x 0 = e r 时2 令 a = a , b - a e e r ( m + 1 ) x ( n + 2 ) , z = 。二。 月，+ 2 ，c = o ，。， r r ”+ 2 1 0 计算对偶变量 u 。= ( a 磺a t ) 一1 a 磙c 2 0 计算下降费用 驴：c 一4 7 0 3 0 检查最优性。如果0 ，且对偶间隙e t x k 8 e ，停止，已得到子问题( 4 5 ) 的最优值 4 0 求迭代方向 砖= 一戤s 塞童奎兰堡主竺堡垒苎墅塑塞三坌堕皇堡望 r 7 5 0 若硝= 0 ，停止，问题( 4 5 ) 已达到最优 6 0 否则，计算迭代步长 一1 哑n 赢怖 。) 其中0 曾) 0 得到新的迭代点后( 此时迭代点为边界点) ，以当前迭代点的目标函数值为p ，更新 6 0 ，得到新的子问题( 4 5 ) 再执行子算法4 1 1 求解该子问题，从而得到下一个内点， 再利用式( 4 6 ) 得出下一个边界点，不断重复上述步骤，直至两相邻的迭代点之间的距 离在一定范围内，即t 错 0 为一给定常数 这样第一阶段的加速完成。得出如下子算法 子算法4 2 1 0 0 给定一个最优值存在区间( o t 。p ) ，以及充分小的数e 1 0 ，e 2 0 - 。4 a = o , 虿= e = t t ，- ，丁形+ l ，a = ； ，z = 。二。 。却峒亿晤”b o 3 0 执行子算法4 i 1 求解子问题( 4 5 ) 4 0 如果子问题( 4 5 ) 的最优值z ：+ 2 0 ，则令口= b o ，返回步2 0 5 0 否则令一1 = z h ，卢= 矿z ， k = k + 1 伊争b o = ( a + g ) 2 , 。= 7 0 执行子算法4 1 1 求解子问题( 4 5 ) 。 8 0 如果子问题( 4 5 ) 的最优值z ：+ 2 0 ，则令口= b o ，返回步6 0 9 0 否则令z 7 。+ 1 = z “，检查最优性，如果 h c t x k 可+ i 万- - c 1 广t x 一 k i i e 0 矿z 臆1 1 、” 成立，则已经达到最优，停止 1 0 0令z ，2 = z “。k = k - 4 - 1 东南大学硕士学位论文第四章二分内点算法 1 9 1 1 0 根据式( 4 6 ) 得出边界点x t k + 1 1 2 0 如果( 4 7 ) 成立，印 锗 0 为一给定常数从几何意义上解释：在已知当前边界点时，增加一个与目标函 数相关的约束条件，使得当前边界点是新形成的子问题的一迭代点，然后利用仿射变换 进行迭代，迫使迭代点往中间跑，从而加速目标函数值的下降 由此得到如下形式的子问题： r a i n 矿 ( 4 9 a ) 令 s t ，- a x 7 = 5 - s t x 7 + z + 1 = 已丁z 臆+ 占 z 0 ，z n + 1 0 ； ，z = 。二。 ，。= 。，。：+ 。 ，c = i 则子问题( 4 9 ) 简化为如下形式： ( 4 9 6 ) ( 4 9 c ) ( 4 9 d ) ( 4 1 0 a ) ( 4 1 0 b ) 东南大学硕士学位论文第四章二分内点算法 2 0 z 0( 4 1 0 c ) 其中a r ( m + 1 。f “+ ，b 品m + 1 ，c r - + z 显然，舻= ： 是问题c a ，。，的一个边界点，利用仿射尺度变换迭代至下一个 边界点用一很小的正数e 取代边界点扩中的零分量i k ，对角阵为t 则可以得出搜索方向 x k = d i a g ( x h = z 乎0 00 0 谚00 0 0 0 z n i k0 00 06 ( 4 1 1 ) 砖= 一 j 一( a 霹a r ) - 1 a x k x k c( 4 1 2 ) 从而迭代至下一个边界点z 蚪1 ，即t z = 扩+ a 甄鹂 ( 4 ，1 3 ) 其中迭代步长为z 。k 。叩赢i ( d ；) z 0 ， 0 已知原问题的一边界点扩 t 。令a = ；： ，c = i ，z = ： 2 0 根据式( 4 1 2 ) 求出搜索方向，即 露= 一f ，一x ；a r ( a 髭a 丁) 一1 a x k x k c 此子算法中玩根据式( 4 1 1 ) 计算 3 0 迭代出下一个边界点即 z + 1 = x + a k x k d ； 其中迭代步长为： 一呀n 赢协 0 ，j 0 ， 0 1 0 执行子算法4 2 1 2 0 如果子算法4 2 1 终止于步9 ，停止，原问题已达到最优 东南大学硕士学位论文第四章二分内点算法 2 2 3 0 如果子算法4 2 1 终止于步1 2 ，则转为执行子算法4 3 1 最终原问题达到最优， 停止 第五章数值试验 5 1 数值试验结果及结论 前一章阐述了二分内点算法的基本过程为了进一步了解该算法的实际表现，我们 进行了初步的数值试验和比较本节将报告数值试验所得到的有关结果，并对这些结果 进行相应的分析 我们试验了如下两个程序： c o d ea s a ：算法2 2 1 仿射尺度算法( a f f m es c a l i n ga l g o r i t h m ) c o d eb i p a ：算法4 4 1 二分内点算法( b i s e c t i o ni n t e r i o r - p o i n ta l g o r i t h m ) 以上两个程序是用f o r t r a n7 7 编写，在m i c r o s o f tw i n d o w sx p 操作系统上利用v i s u a l f o r t r a n5 0 环境进行编译和运行的数值试验所使用的计算机为i n t e l ( r ) p e n t i u m ( r ) mp r o c e s s o r1 6 0 g h z7 9 7 m h z 的d e l ll a t i d u d e6 1 0 ，内存5 1 2 m b y t e s 这两个程序均采 用稠密的数据存储结构计算，且采用了相同的预处理过程计算运行时间所用的工具为 v i s u a lf o r t r a n5 0 的标准库函数c p u t i m e ，以秒为单位，不包括数据预处理的时间。 以上两个程序采用相同的可行性容限求搜索方同时均使用了c h o l e s k y 因子分解方 法在使用的仿射尺度算法中其安全系数均取为o 9 5 在第二个程序二分内点算法b i p a 中，我们利用求得初始内点的一阶段方法求得原问题的初始内点，并以此初始内点的目 标函数值作为初始最优值的上界卢，初始最优值的下界。由试验确定，由此确定初始的 最优值存在区间( q ，卢) 程序b i p a 中的e 1 、e 2 分别取1 0 _ 5 和1 0 一，6 初始取 o 0 1 当迭代点是边界点时，其对角阵凰中取代迭代点零分量的e 取l o 一8 ( 小问题情 况) 或1 0 _ 6 ( 大问题情况) 我们测试了一组来自h t t p ：w w w n e t l i b o r g l p d a t a 的标准的2 1 个线性规划问题，问 题的规模从5 9 到9 7 1 表1 给出了用仿射尺度算法( a s a ) 测试2 1 个标准线性规划问题所得到的结果 表格的第一列列出的是问题的名称，第二、三、四列列出了问题的规模( 分别是问题的 行数m 、列数n 及行列数之和m + n ) 第五六两列分别列出仿射尺度算法总迭代次数 和时间。第七列列出一阶段求得初始内点的迭代次数 东南大学碛士学位论文 第五章数值试验 2 4 表2 给出了用二分内点算法( b i p a ) 测试2 1 个标准线性规划问题所得到的结果 表格的第一列列出的是问题的名称，第二三、四列列出了问题的规模( 分别是问题的 行数m 、列数n 及行列数之和m + n ) 第五、六两列分别列出二分内点算法总迭代次数 和时间 然后我们对仿射尺度算法与二分内点算法分别测试2 1 个标准线性规划问题所得到 的结果进行了比较，其比较结果在表3 中列出，表格的第一列列出的是问题的名称，第 二、三、四列列出了问题的规模( 分别是问题的行数m 、列数n 及行列数之和m + n ) 第五、六两列分别列出仿射尺度算法( a s a ) 与二分内点算法( b i p a ) 总迭代次数之 比和总时间之比 奎童奎堂塑主竺堡丝塞里三塞墼堡苎墼 2 5 表1sc o d e a s a 数值结果 p r o b l e mm + nt o t a li t e r st o t a lt i m e p h a s e li t e r s a f i r o2 73 25 9 1 8 0 0 24 s c 5 0 b5 04 89 83 7o 2 26 s c 5 0 a5 04 89 84 20 2 33 a d l i t t l e5 69 71 5 32 40 2 83 b l e n d7 48 31 5 72 0o 3 94 s h a r e 2 b9 67 91 7 52 40 9 56 s c l 0 51 0 51 0 32 0 88 44 7 3 3 s t o c f o r l1 1 71 1 12 2 82 41 9 45 s c 2 0 5 2 0 52 0 34 0 81 6 97 5 0 57 b e a c o n f d1 7 32 6 24 3 55 91 9 8 41 4 l o t f i1 5 33 0 84 6 18 42 32 58 b r a n d y 2 2 02 4 94 6 96 32 6 9 51 2 e 2 2 62 2 3 2 8 25 0 54 32 8 6 61 2 a g g4 8 81 6 3 6 5 11 0 85 5 4 8 92 3 s c o r p l 0 n3 8 8 3 5 87 4 62 26 2 0 08 s c t a p l3 0 04 8 0 7 8 02 45 1 7 73 s c f x m l3 3 04 5 7 7 8 71 6 54 1 8 9 l1 8 a g g 25 1 63 0 28 1 8 1 2 9 9 2 9 1 42 0 a g g 35 1 63 0 28 1 81 l l8 0 1 1 9 1 9 s c s d l7 7 7 6 0 8 3 7 1 82 3 61 s c a g r 2 54 7 15 0 09 7 1 3 4 52 3 9 42 72 1 t o t a l4 6 3 55 2 2 79 8 6 2 1 6 1 35 3 9 7 0 42 0 0 塞童奎兰堡圭兰堡垒塞篁三塞墼篁堡墼 2 6 表2 ：c o d e b i p a 数值结果 p r o b l e mm + nt o t a ii t e r st o t a lt i m e a f i r o 2 7 3 25 92 5 0 0 3 s c 5 0 b5 04 89 83 00 1 7 s c 5 0 a5 04 89 83 30 1 9 a d l i t t l e5 69 71 5 32 5 0 2 8 b l e n d7 4 8 31 5 7 2 30 5 0 s h a r e 2 b9 67 91 7 52 4o 9 5 s c l 0 51 0 51 0 32 0 84 22 3 8 s t o c f o r l 1 1 7 1 1 12 2 82 51 9 8 s c 2 0 52 0 5 2 0 3 4 0 86 4 2 8 5 8 b e a c o n f d1 7 3 2 6 2 4 3 54 11 4 2 5 l o t f i1 5 33 0 84 6 17 9 2 2 0 2 b r a n d y 2 2 02 4 9 4 6 9 4 0 1 7 9 4 e 2 2 62 2 32 8 25 0 54 52 9 1 1 a g g4 8 81 6 36 5 11 1 35 7 7 ，8 4 s c o r p i o n3 8 83 5 87 4 62 67 1 3 3 s c t a p l3 0 04 8 07 8 02 24 4 5 9 s c f x m l3 3 04 5 77 8 77 01 8 0 3 0 a g g 25 1 63 0 28 1 86 44 5 49 1 a g g 35 1 63 0 28 1 87 45 2 6 3 4 s c s d l7 77 6 08 3 73 03 6 7 s c a g r 2 54 7 15 0 09 7 11 1 78 1 8 3 0 t o t a l4 6 3 55 2 2 79 8 6 21 0 1 22 7 9 56 6 奎童查兰堡主堂堡垒塞萋至耋墼篁塑 2 7 表3 ：a s a 与b i p a 的数值结果比较 a s a b i p a p r o b l e mm + nt o t a li t e r st o t a lt i m e a f i r o2 73 25 90 7 2 00 6 6 7 s c 5 0 b5 04 89 81 2 3 31 ，2 9 4 s c 5 0 a5 04 89 81 2 7 3 1 2 1 1 a d l i t t l e5 69 71 5 30 9 6 01 0 0 0 b l e n d7 4 8 31 5 70 8 7 0 0 7 8 0 s h a r e 2 b9 67 91 7 51 0 0 01 ，0 0 0 s c l 0 51 0 51 0 32 0 82 0 0 01 9 8 7 s t o c f o r l 1 1 7 1 1 12 2 80 9 6 00 9 8 0 s c 2 0 5 2 0 5 2 0 34 0 82 5 6 3 2 6 2 6 b e a c o n f d 1 7 32 6 2 4 3 51 4 3 9 1 3 9 2 l o t f i1 5 33 0 84 6 11 0 6 31 0 5 6 b r a n d y2 2 0 2 4 9 4 6 9 1 5 7 5 1 5 0 2 e 2 2 6 2 2 3 2 8 2 5 0 5 0 9 5 6 0 9 8 5 a g g4 8 81 6 36 5 109 5 60 9 6 0 s c o r p i o n 3 8 8 3 5 8 7 4 6 0 8 4 60 8 6 9 s c t a p l3 0 04 8 07 8 01 0 9 11 1 6 1 s c f x m l3 3 04 5 77 8 72 3 5 72 3 2 3 a g g 25 1 63 0 28 1 82 0 1 62 0 4 2 a g g 35 1 63 0 28 1 81 5 0 01 5 2 2 s c s d l7 77 6 08 3 70 6 0 006 4 3 s c a g r 2 54 7 15 0 09 7 12 9 4 92 9 2 6 t o t a l4 6 3 55 2 2 79 8 6 215 9 41 9 3 1 东南大学硕士学位论文第五章数值试验 2 8 由表1 ，表2 、表3 可以看出，对于2 1 个标准线性规划问题，二分内点算法b i p a 比仿射尺度算法a s a 的总迭代次数减少了6 0 1 次，减少了a s a 计算2 1 个标准问题的总 迭代次数的3 7 2 6 ；总运行时间减少了2 6 0 1 3 8 秒，减少了a s a 计算2 1 个标准问题的 总运行时间的4 8 2 0 可见，二分内点算法b i p a 在迭代次数和运行时间上都比仿射尺 度算法a s a 有明显的进步，二分内点算法b i p a 要优于仿射尺度算法a s a 进一步比较看出，在