（应用数学专业论文）标准形线性规划的直接解法及其时间复杂度.pdf

摘要 本文从标准形线性规划的几何理论出发，以垂直保交旋转平面作 一 为工具，讨论了等式约束平面在可行域的边界。通过对目标函数的有 效梯度与各坐标超平面间关系的判定，提出了标准形线性规划的基本 定理及其直接解法。最后，将直接解法应用于著名的b e a l e 算例，分析 了这一解法的计算复杂度。 理论分析和实践表明：本文提出的直接解法不同于传统的单纯形 法和繁难的内点法，是对线性规划新方法的有益探索。 关键词垂直保交旋转平面有效梯度直接解法时间复杂度 a b s t r a c t t h i sp a p e ri sb a s e do nt h eg e o m a t r i ct h e o r i e so nt h es t a n d a r dl i n e a rp r o g r a m m i n g ( s l p ) t h eb o u n do ft h ee q u a t i o n a lr e s t r i c t i n gp l a n e i nf e a s i b l er e g i o ni sp a r t l yd e t e r m i n e db yt h eo r t h o g o n a li n t e r s e c t i o np r e s e r v e dr o t a t i o n a | p l a n e a f t e rt h er e l a t i o nb e t w e e ne f f e c t i v eg r a d i e n to f o b j e c t i v ef u n c t i o na n da l l c o o r d i n a t eh y p e r p l a n e sw a sd e c i d e d ，t h eb a s i c l e m m aa n dt h ed i r e c ts o l v i n gm e t h o do fs l pa r ep r e s e n t e d l a s t l yt h e m e t h o di sa p h i e dt ot h ef a m o u sb e a l ee x a m p l ea n di t sc o m p u t a t i o n a ls i z e i sa l s oa n a l y s i s e d t h e o r e t i c a la n a l y s i sa n dc o m p u t a t i o n a lp r a c t i c eh a v es h o w e dt h a t t h em e t h o di se s s e n t i a l l yd i f f e r e n tf r o mt h et r a d i t i o n a ls i m p l e xm e t h o d a n dc o m p l i c a t e di n n e rp o i n tm e t h o d t h e r e f o r e ，i ti sa nu s e f u lw o r ko f d e wm e t h o dr e g e a r c ho fs i 。p k e yw o r d so r t h o g o n a li n t e r s e c t i o np r e s e r v e dr o t a t i o n a lp l a n e e f f c t i v eg r a d i e n td i r e c ts o l v i n gm e t h o d t i m ec o m p l e x i t y 第一章绪言 线性规划所涉及的问题是在对决策变量施加一组线性不等式、等 式及符号的约束下，求决策变量的线性目标函数的最优化( 极大化或 极小化) 。与其它的数学学科相比，线性规划是一个相当年轻又非常 活跃的数学分支，在过去的五十几年里，线性规划模型的广泛应用及 这些模型涉及到的数学理论和计算方法，都引起了专业人员和学者的 极其广泛的兴趣。 现代线性规划实际问题的自变量可达到几百万个之多。有人估 计，全世界用于数值计算的计算机时间，有2 5 用于线性规划的计 算，至于这些计算结果的使用所带来的经济、社会效益更是无法估 计。 1 1 线性规划发展概述 早在1 9 3 9 年苏联的康托洛维奇( j 1 b k a s t o p o b h a ) 和美国的希 奇柯克( f l h i t c h c o c k ) 等人就在生产组织管理和制定交通运输方案 方面首先研究和应用了线性规划方法。而其一般形式问题最初是1 9 4 7 年由g b d a n t z i g ，m a r s h a l lw o d d 及他们的当时属于美国空军的军 事合作者提出的，当时他们的小组受命于研究运用数学方法解决军事 上的计划问题的可能性。基于这种要求，d a n t z i g 提出了线性规划的数 学问题模型并给出了线性规划的系统性解法单纯形法，线性规划 也开始成为理论上逐步成熟的学科。 一1 一 1 9 7 7 年，b l a n d 修正了d a n t z i g 的最负判别数法则，使得修正了的 单纯形法能够处理著名的b e a l e 反例，并且证明了单纯形法经有限次 迭代必能求出最优解或者肯定该问题无最优解。 1 9 7 9 年，k h a c h i y a n 提出了时间复杂度为0 ( 7 2 4 l 2 ) 的椭球算法。 椭球算法首次表明，线性规划问题存在时间复杂度是问题规模竹的多 项式的迭代算法。 1 9 8 4 年，k a r m a r k a r 提出另一种时间复杂度为0 ( n4 l ) 的多项式 算法，它不是沿可行域顶点进行迭代，而是通过内点迭代达到最优 解。 k a r m a r k a r 法本质上是内点法，但其描述显得有些复杂，为克服 这一缺点，仿射变换法不用投影变换而用仿射变换，但该方法未被证 明是多项式算法，虽然其实际计算效率比k a r m a r k a r 方法要好。 另一种内点法是减势法，它和k a r m a r k a r 法是十分类似的，通过 利用势函数来决定搜索方向及步长，虽然在选取合适的初始点后，可 使其解法有所简化，但其时间复杂度却仍为0 ( 扎。l ) 。 1 2 本文的背景与目的 对于标准形线性规划问题s l p ： m i n f ( x ) = c x s t 口? x = b ii = 1 ，2 ，m z i 0j = 1 ，2 ，竹 其中c 丁= ( c l c 2 ，c 。) 是一个行向量，x = ( z 1 x 2 ，x 。) 丁 是一个列向量，口1 ，吐。为线性无关的列向量，b 1 ，b 。r 且掰 卵。 在最坏情况下其时间复杂度为0 ( 2 ”) ，是各种时间复杂度中最差 的。椭球算法虽然有着理论上为多项式的时间复杂度，但它在实际计 算中的结果却非常让人失望，远不及单纯形法有效。而以k a r m a r k a r 法为代表的内点法也仅是为许多大型复杂问题的解决带来一丝希望， 其现实的实现方法仍然十分繁琐。 理论分析和计算实践表明，上述方法存在诸多不足。努力减少线 性规划算法计算机时的庞大消耗，追求线性规划解法的尽善尽美有着 十分重要的理论和实际意义。 本文试图从另一个新的角度，由线性规划的几何理论，选出最优 解的临接平面，得到标准形线性规划问题s l p 的直接解法。 第二章线性规划的几何理论 在提出标准形线性规划的直接解法前，先阐述作为直接解法理论 基础的几何理论。 2 1 基本概念 x = ( z 1 ，z2 ，z 。) 丁r ”是7 z 维欧氏空间的点或向量，其中z ， r ( i = 1 ，2 ，7 z ) 是x 的第i 个分量，x ，x j ( i j ，i ，j n ) 表 示不同的点或向量。口丁表示向量n 的转置。向量口和b 的内积记为口 = b r a ，并记：盘毛= 口2 。 本文中记m = 1 ，2 ，3 ，m ，n = 1 ，2 ，3 ，扎 。 首先引述几个基本概念。 ( i ) 凸集 若点集dc r “，x 1 ，x 2 为d 中任意两点，对任给的实数a 0 ， 1 ，若都有 描1 + ( 1 一a ) x 2 d( 2 1 1 ) 则称d 为r ”中的凸集。 容易证明：可数个凸集的交仍然是凸集。 ( i i ) 超平面 丌= x i 1 2 r x = b ，盘er ”，盘0 ，xer ”，6 r 称作r ” 中的超平面，向量a 为该超平面的法向量。 超平面是凸集。 一6 一 r ”中的超平面也可由一点x o 和，z 一1 个线性无关的方位向量口， a z ，a 。一- 确定，即r ”中的超平面可有如下参数方程： x = x o + a 1 a 1 + a2 口2 + + a w l a h 一1( 2 1 2 ) 若已知超平面在各坐标轴的截距d l ，d 2 ，d 。，则超平面方程可 写成如下的截距式： 暑+ 爰+ + 罢= ， ( 2 t s ) r “中的两个超平面石r ：口= 6 i 和乃：盘= 岛的相关位置有 下述三种情形。 当a i a q ( a r ，a 0 ) 时丌f ，丌i 相交。 当a i = a 口j 且b f = a 屯( a r ，a o ) 时丌f ，r i 重合。 当a i2a 口j 且6 i 2 5 j ( a r ，a 0 ) 时丌i ，丌，平行。 ( i i i ) 直线和线段 = xi x = x o + t v ，掣r ”，口0 ，x o r n ，f r 称 作r ”中过点x o 具有方向u 的直线。而称s = xix ：口x 1 + ( 1 一 a ) x 2 ，x 1 ，x 2 r ”，0 口t 为r “中以x 1 和x 2 为端点的线段。 r ”中的直线x = x o + t v 与超平面口丁x = b 的相关位置有下述三 种情形： 当口0 时，直线与平面相交。 当口乙= 0 且a r x o b 时，直线与平面平行。 当t = 0 ，且盘7 x o = b 时，直线在平面上。 ( i v ) 离差 一一1 一 称艿= 鱼_ j 芋翌为点到超平面口r x = 6 的离差。r n 中的超平面 将r ”分成的三部分上的点到超平面的离差分别大于零，等于零和小 于零。 2 2r ”中的投影变换 在讨论r ”空间中的投影变换时，我们从几个定义入手。 定义1平面的内部、外部、内法向 不等式8 双b 规定口为平面口= b 的内法向。凸域d 1 = x i 盘丁x b 为平面a 7 x = b 的内部。凸域d 2 = xi 口1 x b 分别为平面口7 x = b 的内法向、内部、外部。 经不等式规定的平面是有向平面，它是其内部和外部的界面。 设有口盈b i ( i n ) 规定的有向平面心：口= b ，( i n ) ， 由点x o 作直线x = x o + t v ( x o ，口r ”，t r ) ，直线与平面内 部的交必须满足 t a 如b ，一口t x o( 2 2 1 ) 若口b = 0 ，则当且仅当口o = b i 时，t 可取( 一o o ，+ o o ) 上任 一值。此时直线与平面内部的交是直线本身。否则，直线与平面的交 为空集。至于口b 0 的情况将在定义2 中描述。 定义2 最小( 大) 离差向量、弦、能有界交方向、共轭直径 当口知 o 时，称艿而：丝罂，为由点x o 沿方向口到平面丌i ： 口? u 口? x = 6 r ( i n ) 的最小离差向量；当口知 0 且盘_ 0 且口知 0 的方向称作t 和q 的内部能有界交方 向。点x o 沿( 与) 能有界交方向 1 3 平行的方向移动时所得到的一组平 行弦的中点的集合称作平面丌，和平面n 的内部与方向铆共轭的直径。 疋义3技彤点、投影同量 称点x 7 = x + 生专擎口为点x 到超平面：口丁x = 6 上的投影 点。 称口7 = 窘口为向量口到向量口上的投影向量。称u = 可一 等品；为向量钉到超平面t ：口：6 i 上的投影向量。 特别地，记口在心的法向口。上的投影向量为臼士) = 等品i ；记原点 。到霸平面的投影为o i = i 并称作平面砧的原点。 x = x + 鱼_ 三字笔i 是r 一到平面丌，的映射，亦称投影变换。 若原象是r ”中的直线x = x o + t v ( x o ，口r ”，t r ) ，则 终投影峦换后的袅为 x ，一m 攀 l = x + t v ( 2 2 3 ) 而p 一 口f+ 因此，与平面霸的法线平行的任一直线上所有点经映射压缩成一点； 而当郇与凸。不平行时，映射把r ”中的直线变换成丌；上的直线，其方 向就是原象直线的方向在砖上的投影向量。 容易证明，这样的映射能够保持线段分点的分比不变。即投影变 换具有保线段分比不变性。 定义4r “中的挖一7 7 z 维平面 称丌= x i a t tx = b l ，a r x = b 2 ，n 驭= b 。 ( 其中x r 8 ，m ，z ，b l ，b2 ，b 州r ，丑l ，a2 ，丑m r ”且吐1 ，吐2 ，a 删 线性无关) 为r ”中的孢一m 维平面。 r “中的住一m 维平面有m 个线性无关的法向量口1 ，a2 ，c t 。和 ，z 一7 7 1 个线性无关的方位向量。用数学归纳法可以证明，这聊个法向 量的任意线性组合a 1 口l + a 2 口2 + + a 私。( a l ，a2 ，a 。r ) 都 是该咒一垅维平面的法向量。其全钵构成的拢维的空闺称为该聍一m 维平面在r “中的正交补。 r ”中的n m 维平面是包含它的咒一m + l 维空间中的超平面。 因此，和前述相应的不等式规定了它的内法向和内部。 设丌i ：口丁x = b i 和 ：, q x = b i( i m ，j m ，且i j ) 是r ”中两个法向线性无关的超平面，a j 在丌，上的投影向量为： 口1 ( 0 2q 一了产i 口k i 它是丌r 和叶的交即竹一2 维平面在丌i 上的法向量口i 。 如果把坐标架平行移动到啊的原点0 ；，则丌i 便成为r 一- 空间， 丌d 则是该7 z 一1 维空同中的超平面，它在7 ( i 中满足方程 卜挚ix = 屯一争i ( x h ，x q ) ( 2 2 4 ) 若盘t ，q 均是内法向，则口= q 争t 亦为玎。的内法向。 因 矿t 一卜净1 = 如嘶川 所以在r ”中，式( 2 2 4 ) 规定的平面是一个与玎。垂直的竹一1 维 超平面，但它与丌f 的交就是砷与t 的交。于是有： 定义5 垂直保交旋转平面 称r ”中的超平面：l q 一等2 ：x = 屯一i 为r ”中的超平面 q ：口j 腿= 屯，对于r ”中的超平面孔：口盈= 6 ；的垂直保交旋转平 面。 对于标准形线性规划的等式约束平面 丌= x j 口 x = b l ，口；x = b 2 ，口秘= 6 。，优扎 可按 上述同样的办法得到经过r ”中挖一m 维平面巧的挖一1 维超平面 一等口- 学盘， 口1 2 3 = 知i n t 2 r a l 3 ( 2 2 5 ) a 1 2 - , m = 口1 2 ( m - 2 ) m 堕粤堕尘二赴( 。川( 2 2 6 ) 口1 2 ( 一1 ) ”“7 b 。2 = b 2 一警b l 1 = 一等 6 1 3 = b a 一等b t 6 = 一寻i 6 1 2 。岫，一訾6 1 2 ( 2 2 7 ) ( 2 2 _ 8 ) ( 2 2 9 ) 6 t z m = 6 - ：c m z ，m 一! i 三二：i ：挚6 - z c m 一- ， ( 2 2 1 0 ) 虽然按照不同的投影序投影后得到的r ”中的丌。：。可能会有所 不同，但容易证明：按不同顺序投影后得到的所有的丌，：都是经过 丌的( 其证明在第三章中给出) ，而这一点恰恰是直接解法中需要的。 定义6凸多胞形、界面、顶点 称r ”中的九一研维平面7 t = xl 口 x = b 1 ，口手x = b 2 ， 口驭= b 。，口l ，盘2 ，口。r ”且线性无关，m 咒 与卵个坐标半 空间e ? = x i e z i x 0 ，g ，为r ”中第i 个分量为1 的单位向量 ( i = 1 ，2 ，咒) 的交称为r 4 中1 2 一m 维凸多胞形，若某坐标超平面e i = xf e 盈= 0 与，r 在可行域内有交，则称玎与e ；在可行域内的交称 作凸多胞形的界面，在不致引称混淆的情况下，亦称坐标超平面e ，是 该凸多胞形的界面。挖一m 维平面i t 与犯一研个界面的交称作凸多胞 形的顶点。 第三章标准形线性规划的直接解法 3 1 预备定理 作为标准形线性规划直接解法的主要几何工具r n 空间中的 投影变换，有下述结论成立。 设有向量c r ”及行一m 维平面丌： 丌= xl 口 x = b 1 ，口手x = b 2 ，口t x = b 。 其中x r ”，m 挖，b l ，b 2 ，b 。r ，a 1 ，n 。r n 且口1 ，口2 ， ，口。线性无关。 = xi 口= b i i m 若将，r 2 的法向量a 2 向丌1 投影，可得到r ”中的平面丌。：，其方程 为： 口i 2 x = b 1 2 其中a 1 2 ：一等a t6 1 2 叫：一警6 。 n i 一 。 疗j 1 它是丌2 对丌1 的垂直保交旋转平面。 同样可得：玎1 3 = xi n 丁3 x = b 1 3 7 r 1 2 3 = xi a 己3 x = b 1 2 3 其中3 = 一堕竽a 1 2 n i ， 一 6 1 2 。= 6 1 3 一堕笋6 1 2 口知 一 ( 3 1 1 ) ( 3 1 2 ) ( 3 1 3 ) 盯1 2 珥= xi 口己卅x = b 1 2 埘 其中知。= 知( 。吲。一塑半笋堕地( 州) ( 3 1 。4 ) “1 2 ( m 一1 ) 6 1 2 。= 6 1 2 ( 。一2 ) 。一! 互兰= i 竺主! l 垒坳6 1 2 ( 。一1 ) ( 3 1 5 ) 口1 2 - ( m 一1 ) 定理1 对r ”空间中的超平面t = xf 口= b i 采用不同的投 影次序得到的丌 0 2 气2 z i a 五铲= b p 。p 2 p 都包含r ”中的，2 一 m 维平面玎。 证明：由于7 f 1 2 是r ”中的玎2 对丌。的垂直保交旋转平面： 即丌1n 玎2c 丌1 2 同样：丌ln 丌3c 7 r 1 3 7 r 1 2n 丌1 3c ”1 2 3 故丌1n 玎2n 丌3 = ( 丌1n 丌2 ) n ( 丌1n 丌3 ) c 丌1 2n 玎1 3c 显然，上述集合关系与丌1 、丌2 、丌3 的投影次序无关。因而当研：3 时，命题成立。 假若当优= k ( 愚3 ) 时命题成立，即 丌1n7 r 2 n 孔c 丌1 2 且与投影次序无关 则当研= k 4 - 1 时，由归纳假设有： 7 1 n ；r 2 n 玎 + l = ( 丌ln 玎2n n 矾一ln + 1 ) n ( 丌ln 丌2n n ) c ( 丌1 2 ( i 一1 ) ( + 1 ) ) n 丌1 2 lc 7 f 1 2 ( + 1 ) 由于上式最后一个交运算的两边与投影次序无关，故当。：志+ 1 时 其集合间关系亦与顺序无关。 一1s 一 定理2r “中的向量和点到r ”中的低维平面上的投影与投影次序 无关。 证明：考虑r ”中的任意向量c ： c 到平面t = xi 口= 6 ； 上的投影向量为： c t ：c 一嚷二 口： 平面q = zi 口& = b j 到平面毛的垂直保交旋转投影平面为： 酽川旷李= 6 广挚” 其法向量盘“是丌；和q 的交即咒一2 维平面在玎，上的法向量。 c 先向疋投影后再向投影的投影向量为 钉一簪。 = c 一簪 = c + 亟灶鼍茅篆产量地 口缸：一( n ? 口) 向量c 到乃上的投影向量为： c ：c 一壤； 口 砖对玎j 的垂直保交旋转投影平面为： q l = x i 况j t f x = b j i 它的法向量q i 是t 与_ 的交( 咒一2 维平面) 在q 上的法向量： 亟蠢 q圣： m 莩磐f ，卜 扯一孕；= c 一争，一 一卜争， 卜争，】2 r7 霹j = c + 丝垫鼍罄菘a 笋l 业 口和：一? 口厂 n 1 2 , q 。2a 1 2 - - - ( k - 1 ：1 2 1 2 1 ) j 一啦宅1 2 e ( 3 1 6 ) n 0 2 一j 1 l j l 内) c 1 2 “1 2 廿一坠1 2 1 2 _ ( 3 7 t，( 女一1 ) 0 1 2 k ：0 1 2 ( k - i ) + 堕李螳m ( 3 1 8 ) “1 2 一 相应的6 1 2 好为： 6 1 2 巧呐：沁州一盘秽捃“( 3 ) 定理3r n 中的向量口和c 在r ”中的咒一优维平面r c i 2 。上的投 影向量口1 2 。m 和c 1 2 m 的内积等于口和c 1 2 ”的内积，即n 1 2 ” c 1 2 “= a t c 1 2 。 证明：因对任意的口，c r ”，口总可分解为：口= 口1 2 ”+ 口1 2 m 1 其中口1 2 ”是口在7 r 1 2 。上的投影向量，盘1 2 ”1 则与丌1 2 垂直， 又c 1 2 ”c 丌1 2 。 所以( 吐1 2 “1 ) 丁c 1 2 一“= 0 所以n 1 2 m c 1 2 州= 口1 2 m 1 c 1 2 卅+ ( 口1 2 坍1 ) 丁c i 2 删 = ( 口1 2 卅十盘1 2 卅。) t c 1 2 折= 丁c 1 2 m 3 2 标准形线性规划基本定理 设有标准形线性规划问题s l p ： m i n f ( x ) = c r x c ，xer ”( 3 2 1 ) s t 岔；x = b f口 r “，b 。ri = 1 ，2 ，m ( 3 2 2 ) z ，0j = i ，2 ，雄( 3 2 3 ) 其可行域由等式约束( 3 2 2 ) 和非受约束( 3 2 3 ) 所规定，非负约 束z j 0 规定的可行域是以第j 个分量为1 的单位向量e j = ( 0 ，0 ， ，0 ，1 ，0 ，0 ，0 ) 为内法向的坐标平面z ，= 0 的内部。 可行域中使目标函数，( x ) 取得最小值的点称作s l p 的最优解。 式( 3 2 3 ) 中不同的非负约束平面所规定的半空间与等式约束的 一m 维平面7 f 1 2 。= xi 盘= b i ，i = 1 ，2 ，扰 的交将界定 一个凸多胞形。 定义1最优解 在式( 3 2 3 ) 中坐标半空间与7 2 协一的交界定的凸多胞形上，使 目标函数f ( x ) 取得该凸多胞形上最小值的点称作该s l p 问题的最 优解。 定义2 平面= xi c r x = h ，c r “，her 称作s l p 的 一个等势面，h 是该等势面的高度。 定理4 s l p 的最优解必在凸多胞形的顶点上达到。 证明：不妨设某凸多胞形a 由下述超平面的内部构成：e ，= z i e 丁z 妻o l e ，= z f p ，t z = o t 和丌l ：。，其中r 挖一。 一1 9 先证最优解若存在，则它不可能在该凸多胞形a 的内部达到。 在a 内任取x o 点，则通过x o 点总可作一条不在通过x o 的等势 面巩= x lc r x = h ，c r ，her 上的直线l ，该直线l 与 该凸多胞形a 交于两点x 1 和x 2 ，由于l 不在等势面上，则x 1 和x 2 均不在等势面丌。上。 又由于目标函数，( x ) 的线性性质，一w ( x ) = 一c 这一方向与 有向线段l x 1x 2 必成一锐角或钝角。从而f ( s c ) 沿l x o ，x 1 或 l x o ，x 2 必有一方向是减小的，从而无论如何x o 均不可能是最优 解。 对于顶点的邻接界面上的点，任取y o 为某界面上非顶点的点， 则由于a 是凸集，且y o 不是顶点由顶点的定义，则必存在y 1 ，y 2 a 使得： y o l ( y 1 ，y 2 )( l 为以y 1 ，y 2 为端点的线段) 从而由前述方法可以证明在( y 1 ，y 2 ) 不在等势面上时，y o 不是 最优解，若l ( y 1 ，y 2 ) 总在等势面上，则此时，尽管y o 可以是最优 解，但此时其顶点亦为最优解。 定理5 凸多胞形的顶点x o 是s l p 的最优解的充分必要条件是过 x o 的等势面在该凸多胞形的上方。 证明：过凸多面体上任意点x 作等势面：( 一c ) t x = h ，过顶 点x o 的等势面丌一。：一c r x = h o 在凸多胞形的上方等价于h ho ，实 际上也就等价于对凸多胞形上任一点x 都有： ，( x ) ，( x o ) 于是定理5 得证。 一2 0 说明：定理5 中的“上方”是相对于一a f ( s c ) 的方向来说的，并不 是常义的上方。 定理5 等价于 定理5 7凸多胞形的顶点x o 是最优解的充分必要条件是该顶点的 内部上有界。 凸多胞形的顶点是行个法向线性无关平面的交点，对于标准形线 性规划问题而言，尚有礼一m 个非负约束平面是待定的，为了确定它 是否最优解，只需考虑以这露个平面为邻接界面的凸多胞形，该顶点 的内部仍然有挖个线性无关的方向，它们应该由这n 个邻接界面从上 方界定。 定义3有效梯度 称目标函数的梯度c 在等式约束( 3 2 2 ) 规定的咒一优维平面 丌1 2 。上的投影向量为s l p 的等式约束梯度并记作c ”，c “亦称为有 效梯度。 定义4第1 ( ) 类非负约束坐标平面 若等式约束梯度c ”的第j 个分量c 0 则称( 3 2 3 ) 中的非负 约束平面e = x l e f x = 0 为s l p 的第1 类非负约束坐标平面，若 c 7 0 ，则称e i 为第类非负约束坐标平面。 定理6 s l p 的最优解必在第1 类非负约束坐标平面上达到。 证明i 用反证法。假设s l p 的最优解x 的所有非负约束坐标平 面均为第类的，由定理4 知，x 。是可行域的顶点，不妨设x ”是 打，2 。与非负约束坐标平面e ，e2 ，e 的交，由假设知： c 7 0 ，c 7 0 ，c ：一。 0 一，1 一 由定理3 知： ( 8 t ) r c “= g j - c ”= ( 1 ，0 , 0 o ) c m = c t 0 同理： ( p ? ) r c ” 0 一c m 是等式约束中目标函数值减小的方向， 多只有砟一优个线性无关的方向。 ( 3 2 4 ) 由于在玎1 2 。内最 以x 作为起点，往顶点的内部引一直线段l x ，x ，记该线 段在咒一州维空间r ( e l ，8 2 e 。一。) 内的投影原象为l 7 x ，x 1 ，由 于l 是在非负约束坐标平面e 1 ，e 2 ，e 。一。与丌1 2 。的交x 的内部， 故l7 亦在r ( e l ，e 2 ，e 。一。) 的内部，从而l7 可以唯一地表为： l 7 x 。，x 1 = d l e l + d 2 e 2 + + d n - m e 。一。且d l ，d 。 0 ，d 1 ，d 。一。不全为零 由于投影变换的保分比性：故必有： l x + ，x = d l e 7 + d 2 e 翟+ - + d 。一。e “n - 。 x = x + d 1 p 7 + 十d 。一。p 嘉。 所以 ，( x ) = c t x = c 了( x + d l e ”l + + d 。一器。) = c t x + d l c r y 7 + + d 。一m c t ：一m 由式( 3 2 4 ) 因c t e i ”= ( c ”) 0 7 = ( p ) ” 0 ( i n ) 以及曰= 0 ( j n ) 且口l ，a 1 2 ，口1 2 。的 第j 个分量同时为零的第1 类非负约束坐标平面为s l p 的准必需坐 标平面。 记准必需坐标平面指标集为o 。 定理8 若s l p 的准必需坐标平面指标集n 。为空，则该s l p 问题 无最优解。 证明：由定理6 、7 易证。 定理9 若o ”的各个分量0 7 ( i = 1 ，2 ，n ) 全部不大于零，且不 全为零，则该s l p 元最优解。 证明：先看7 7 z = l 的情况： 因丌“= r 1 是竹一1 维超平面：它和坐标轴有且只有咒个交点( 截 距，若交于无穷远处，则o o 亦为其截距) ，因而可将它写成如下截距 式： 象+ 爰+ ”+ = - ( 3 2 6 ) 这里因0 7 不全为0 ，即一不过原点，因而7 1 m 总可写成上述( 3 2 6 ) 的形式。 由于o ? 0 ，故d ， 1 的情形，此时丌”为茏一优维超平面，o o ”是玎”的法 向之一，这时总可以过丌“作一与o o ”垂直的挖一1 维超平面丌，由前 述，这个砰一1 维超平面丌无可行域，而丌”c 丌，故丌”亦无可行域， 因而此时该s l p 问题无最优解。 定理1 0若o ”的分量中有咒一1 个非正，即只有某一0 7 为正，则 非负约束坐标平面e ；与，r ”的交无可行域。 证明：若m = 1 ，则由该超平面的截距或方程( 3 2 6 ) 式可知：d i 0 ，d l 0 ，d 2 0 ，d h 0 ，d 0 ，d 。0 ，此时：丌” 与e i 的交丌为： 詈十爰+ + 羞+ 鬻+ + 万z n = t z i = 0 ( 3 2 7 ) 从( 3 2 7 ) 式这一截距式方程，显然可以判定丌? 不可能经过可行域 ( z i = 0 中的可行域) ，因而e i 与玎”的交无可行域。 对扰 1 的情形的讨论与定理9 对m 1 的情形完全类似。 推论 若o ”的各个分量只有0 7 为正，则非负约束坐标平面 e f = x l x i = 0 中无可行域的边界。 从定理9 和定理1 0 的结论可以看出：对于丌”可行域的确定。可 依下述步骤完成： 从丌1 的截距式方程，使用定理诊可以判断出哪个非负约束平 o = z且l = 鱼矗 十十 坠如 + 塑出 邵 面和等式约束的交无可行域。 根据0 2 ，0 3 ，0 “可分别判断出丌2 ，行3 ，7 r ”与各非负坐标 约束平面或其某些组合的可行域的情况。 对上述得到的各种情况求并可取终得到，r ”与各非负约束坐标 平面或其某些组合的可行域情况。 定义7必需坐标平面 若某非负约束坐标平面e i 是准必需坐标平面，且同时亦为可行 域的临界平面，则称该坐标平面为必需坐标平面。 记必需坐标平面的指标集为1 。 考虑到可行域的情况，定理8 的结论成为： 定理1 l 若s l p 问题的必需平面指标集n 1 为空，则该s l p 问题无 最优解。 定理1 2线性规划基本定理 若n l 中的某坐标平面e i ：e s x = 0 是等式约束平面丌”在可行域 内的边界，且满足：曰c f ( i = 1 ，2 ，j 一1 ，j + 1 ，n ) 则：如 果该s l p 问题的最优解存在，那么其最优解必在e ，上达到。 证明： 1 。若s l p 问题的必需坐标平面指标集n 1 中只有e ，一个，则由 前述可知，该s l p 问题的最优解若存在，显然必在e ，上达到，因而此 时定理成立。 2 。若n l 中不止e 一个，不妨设c ”的各个分量有如下关系： 曰c 7 c 孑 其中c ? 0 ，且假设e 。，e ：是丌m 与可行域的边界。 一2 8 由于s l p 问题的最优解总在顶点上达到，因而只要证明不在e i 上的顶点不能达到目标函数的最优( 小) 值即可。 在e 1 啜上任取一不在e 上的顶点x ，c ”在丌扪上的投影为： 1 _ 一杀f 而c 矶与，r 州的法向e ，在丌叭上的投影的内积为： c 卜譬一象c ? 因e 7 ，e 7 ，1 所以l _ 老l - 而c 7 c t 0 故c 7 1 0 这就说明x 可沿一c 卅1 方向到达e j 面上。也即x 沿该方向运动 时( 到达e 坐标面时) 其目标函数值，( x ) 还可继续减小。故x 不可 能是s l p 问题的最优解。 至于那些临界平面不含必需坐标平面的顶点，前述定理知，它不 可能是s l p 的最优解。 这就证明了定理1 2 。 3 3 标准形线性规划的直接解法 对于标准形线性规划问题s l p ：在，r ”和各个p ，( i = 1 ，2 ，咒) 及c “都求出来后，由于其最优解总在c ”的各个分量中最大分量的下 标所对应的必需坐标平面上取得，这样，将某最大的c ，对应的： 马= xi 班= 0 定下后，对于原s l p 问题而言，只不过其等式约束增加一个，因而其 后的处理与未增加前完全应该一致。故在经过咒一优次这样的处理后 即可求得其最优解。但前提是e i 必须与丌”在可行域内有交。 另一方面，由于每次处理时，都保证了其选择与移动是在可行域 内进行的，因而经过上述处理得到的一定是最优解而不会是准优解。 所以，对于标准形线性规划s l p 的求解过程可概括为： ( 1 ) 求c ，e l ，e 2 ，p 。在等式约束7 r ”上的投影c “，e t ，p 罗， ，p ：= lo ( 2 ) 找出c ”中分量最大且同时满足丌”及可行域要求的e 。 对于边界的确定可根据0 1 ，0 2 ，o ”的符号情况排除一些。亦 可在可行域内找一点，沿各e y ( i = 1 ，2 ，z ) 方向移动，求出首次相 交者来确定。 若第一次得到的是e i ，则将c ”往丌”投影求出c 一，再找出是 7 r “o 的边界且分量最大的弓，如此继续，直至得到最优解的全部临接 平面或判定问题无最优解。 若在( 2 ) 中的某一中间环节中，得到的c ”1 2 的各分量全为负， 则原s l p 问题无最优解。 一3 0 ( 3 ) a b 可任选。 a 全部临接界面求出后，解研阶线性代数方程组，求出最优解。 b 在找出了最优解的7 一m 一1 个临接界面后，可以在它们与玎” 的交线( 通过投影已得出) 上取一在可行域内的点x 1 ，利用交线z ： x = x 1 一c “，1 2 ( 一1 ) t ( 3 3 1 ) 与它的必需坐标平面相交。取t = m i n hit l 0 ，矗n l ，并将t 代入( 3 3 1 ) 式，从而最终求得最优解x 。 鉴于口l ，口1 2 ，a 1 2 3 ，n 1 2 。的正交性，利用前述投影的递推公 式，c “，e ? 可按下述公式得到。 c “= c 一 等警知+ + 协1 ( 3 3 2 ) e ，i i 等篆+ 篆协】 i = 1 ，2 ，7 2( 3 3 3 ) 而c ”，p ，( i = 1 ，2 ，咒) 再向丌”与马的交丌卅( j i ) 投影为： c 椰= c “一鼢 ( 3 3 4 ) p 2 8 ，一e 勺? ( 3 5 ) 第四章直接解法的应用及算法分析 4 1 典型算例 作为露援解法的应用，今举例如f ： s l pi ： m i n ，( x ) = 一；z 。+ 2 0 z ，一吾z 。+ 6 z 。 s t z l + i 1 z 4 8 2 5 一z 6 + 9 2 7 = o z ： + 丢z 。一1 2 z ，一丢z 。+ 3 z ，= o x 3q - z 6 = 1 z f 0 ，i = 1 ，2 ，7 该算例为著名的b e a l e 算例，尽管在采用b l a n d 法则后可以利用 单纯形法求出其最优解，但需历经七次转轴运算，今用直接解法求 解。 解：( 1 ) c = ( o o ，o ，一, 2 0 ，一号，一6 ) 口1 = ( 1 ，o ，0 ，i 1 ，一8 ，一1 ，9 ) 6 1 ：0 口：( o 1 o ，丢，一1 2 ，一三 3 ) 6 ：o a 3 = ( 0 ，0 ，1 ，0 ，0 ，1 ，0 ) b 3 = 1 0 1 = ( o ，0 ，0 ，0 ，0 ，0 ，0 ) 口ia2 知2 幻一f q 塑 = ( o ，1 ，o ，丢，一1 2 ，一吾，3 ) 一2 - - 蠡5 3 ( 1 ，o ，o ，百1 ，一8 ，一1 ，9 ) 1 f 1 9 7 8 1 3 6 4 1 2 4 1 21 6 0 3 1 0 7 4 3 1 2 i 一丽，l ，u ，4 - g ，一1 5 亏 ，4 7 0 6 ，一l 丽j 口i 2 = 5 0 5 8b 1 2 = 0 0 2 = ( 0 ，0 ，0 ，0 ，0 ，0 ，0 ) = 口s 一訾口- = ( 0 ，o 1 0 o 1 o ) 一嘉( 1 0 ，0 ，丢，一8 ，“9 ) 1 6 = 【基0 ，- ，4 ，一器，丽2 3 3 7 ，拦】 6 1 3 = 6 3 一等6 l = 1 口己口1 2 a 1 2 3 2 钆3 一百吼2 = 【盖，o ，- ，志，一豢，麓，拦卜 - 1 9 7 8x1 6 + 6 8 2x4 + 1 2 4 1 2x1 2 8 + 8 0 1 5x 2 3 3 7 + ( - 1 0 7 4 3 ) x1 4 4 5 0 5 8 2 3 5 3 2 3 5 3 _ 器 。，罴，一器，鬻，一器 = 2 1 3 ( 2 9 2 ，一1 5 7 ，2 3 5 3 ，一0 5 ，一4 5 5 ，2 3 3 1 7 ，2 1 5 6 ) 6 1 2 ，= 6 1 。一警6 1 2 _ 6 1 ，= 1 而。圭2 c 。= c f 等譬1 2 + 等，j 盘 口i 2 3j 邛，。，”狰3 一扣一誓1 1 。，。，丢，飞吐9 ， 1 矿 一二三! 兰鱼! q ：到一1 9 7 _ 8 8 10 盟一些墼墨必一塑塑 5 0 6 8 2 3 5 3l2 3 5 3 ”2 3 5 3 2 3 5 3 2 3 5 3 2 3 5 3j i ；i 薹i 勰( 2 9 2 ，一1 5 7 ，2 3 5 3 ，一o 5 ，一4 5 3 ，2 3 3 1 7 ，2 1 5 6 ) = ( 一1 4 9 4 ，2 6 3 4 ，0 1 6 5 ，0 1 9 3 ，0 3 4 5 ，一0 1 5 7 6 ，0 。4 5 6 ) 。3 = n 堕掣1 2 3 蛐s = 是1 2 3 。 口 = 丢2 志5 3 ( 2 9 2 ，一1 5 7 ，2 3 5 3 ，一o 5 ，一4 5 3 2 3 3 1 7 ，2 1 5 6 ) 圭( 0 0 0 6 ，一0 0 0 3 ，0 5 ，一0 0 0 0 1 ，一0 0 1 ，0 5 ，0 0 4 8 ) 3睦口1e 手1 2e 吣3 1 。 5 8 z i 丁口1 + 百盘1 2 + i 口1 2 3 = ( o ，1 ，0 ，0 ，0 ，0 ，0 ) 一醋+ 志【- 丽1 9 7 8 o ，篇，一糌，觜，一器】 十j - 丽1 5 7 盎5 3 ( 2 9 2 ，1 5 7 ，2 3 5 3 ，一o 5 ，一4 5 3 , 2 3 3 1 7 , 2 1 5 6 ) l = ( 0 0 1 7 ，0 9 8 ，0 0 0 3 3 ，一0 0 0 5 7 ，0 1 0 4 ，一0 0 0 3 4 ，0 0 9 0 6 ) 如一 每州案a 1 2 + 警知，1 = ( 0 ，o 1 ，o 0 ，o ，o ) 一裂一而0 一志( 2 9 2 1 5 7 ，2 3 5 3 ，一o 5 ，一4 5 3 ，2 3 3 1 7 ，2 1 5 6 ) = ( 一0 0 0 6 2 ，0 0 0 3 3 ，0 5 ，0 0 0 0 1 ，0 0 0 9 6 ，一0 4 9 5 ，一0 0 4 5 8 ) 扣旷f 等警z 十訾