（应用数学专业论文）一类线性规划问题的几何理论与直接解法.pdf

摘要 本文研究一般线性规划问题( u l p ) 的几何理论与直接解法。线 性规划的应用范围十分广泛，但理论分析和计算实践表明，近年来 关于线性规划的各种迭代算法都存在许多缺陷。努力降低计算复杂 度，追求线性规划解法的完善有着十分重要的理论和实际意义。 本文基于和已有方法完全不同的思想，考虑到一般线性规划问 题的最优解的结构，建立了新的几何理论和直接解法。方法分成两 步：第一步处理形状，提出了关予线性规划准优解的四个判别数， 在此基础上证明了判断准优解的一个充分必要条件；第二步处理位 置，针对准优解的几何特点，提出竞争的新概念，由准优解的竞争 求出最优解。最后，文章通过具体算例阐明直接解法的实际应用过 程，并作出了简要的算法分析。 关键词：一般线性规划问题；几何理论；直接解法；准优解；竞 争；时间复杂度 g e o m e t r i ct h e o r i e sa n dd i r e c tm e t h o df o r au n i v e r s a ll i n e a rp r o g r a m m i n gp r o b l e m a b s t r a c t ：i nt h i sp a p e r ，g e o m e t r i ct h e o r i e sa n dd i r e c tm o t h o d f o rau n i v e r s a ll i n e a rp r o g r a m m i n gp r o b l e mh a v eb e e ns t u d i e d l i n e a rp r o g r a m m i n gh a sav a s ta p p l i c a n tf i e l d h o w e v e r ，d i f f e r e n t k i n d so fi n e r a t i v ea l g o r i t h m sh a v eb e e ns h o w n i m p e r f e c ti nt h e o r e t i c a la n a l y s i sa n d c o m p u t a t i o n a lp r a c t i c et h e s ey e a r s t h e r e f o r e ， i th a sg r e a ts i g n i f i c a n c et or e d u c ec o m p u t a t i o n a lc o m p l e x i t ya n d p u r s u i te l e g a n tm e t h o da sc a na sw ep o s s i b l e b a s e do nt h o u g h sq u i t ed i f f e r e n tf r o me x i s t e dm e t h o d s ，w e h a v ec o n s i d e r e dt h es t r u c t u r eo ft h eu n i v e r s a ll i n e a rp r o g r a m r u i n gp r o b l e m so p t i m a ls o l u t i o na n db u i l tu pn o v e lg e o m e t r i ct h e o r i e sa n dd i r e c tm e t h o d t h em e t h o di sd e v i d e di n t ot w os t e p s f i r s t l y ，t h es h a p ei sp r o c e s s e d f o u rc r i t e r i ar e l a t e dt ol i n e a r p r o g r a m m i n g sa l m o s to p t i m a ls o l u t i o nh a v eb e e np r o p o s e d ，a n d t h a to u to ft h e s e ，an e c e s s a r ya n ds u f f i c i e n tc o n d i t i o nh a sb e e n p r o v e d s e c o n d l y ，w ed e a lw i t ht h el o c a t i o n i na c c o r d a n c ew i t h t h e g e o m e t r i cc h a r a c t e r i s t i c s o ft h ea l m o s to p t i m a ls o l u t i o n s ，a n e wc o n c e p tn a m e l yc o m p e t i t i o nh a sb e e np r e s e n t e d b yc o m p e t i t i o no ft h ea l m o s to p t i m a ls o l u t i o n s ，t h eo p t i m a ls o l u t i o nc a nb e o b t a i n e d f i n a l l y ，n u m e r i c a le x a m p l e sh a v eb e e ng i v e nt od e m o n s t r a t et h ea c t u a la p p l i c a n tp r o c e d u r ea n dab r i e fa l g o r i t h m a n a l y s i s h a sb e e nd r a w n k e yw o r d s ：u n i v e r s a ll i n e a rp r o g r a m m i n gp r o b l e m ；g e o m e t r i ct h e o r y ；d i r e c tm e t h o d ；a l m o s to p t i m a ls o l u t i o n ；c o m p e t i t i o n ； t i m ec o m p l e x i t y 第一章导言 数学规划是最优化理论的一个重要分支。线性规划问题( 1 i n e a r p r o g r a m m i n g ，简记为l p 问题) ，就是在一组线性的等式或不等式 的约束之下，求一个线性函数的最大值或最小值的问题。 与其它的数学学科相比，线性规划是一个相当年轻又非常活跃 的应用数学分支。在过去5 0 多年中，线性规划模型的广泛应用，以 及这些模型涉及到的数学理论和计算方法，都引起了专业人员和学 者们的浓厚兴趣。线性规划已成为几乎所有的商业活动、工业生产 和军事行动的一个组成部分。 1 1 线性规划发展概况 早在1 9 3 9 年，苏联数学家和经济学家l v k a n t o r o v i c h 曾指 出了一类有限界的线性规划模型对于生产计划的实际重要意义，并 提出了一个求解线性规划的基础算法。经济学家l e o n t i e f 在研究投 入产出分析法时也提到了线性规划闻题。1 9 4 1 年，k a n t o r o v i c h 与 美国的f l h i t c h c o c k 就交通运输问题研究和应用了线性规划方 法。由于对资源最优分配理论的贡献，k a n t o r o v i c h 获1 9 7 5 年n o - b e l 经济学奖。 1 9 4 7 年，美国空军的s c 0 0 p 小组研究资源分配时，g b d a n t z i g 提出了求解线性规划问题的单纯形方法( s i m p l e xm e t h o d ) 。 一1 对于标准形线性规划 m i n f ( x ) = c r x s t a x = 6( 1 1 1 ) x o 其中a 为m 竹矩阵，c ，x r 4 ，6 r ”。由线性规划基本定理： 如果( 1 1 1 ) 中函数，( x ) 有最优值，则必可在某个基本可行解处 达到。因而只须在基本可行解中寻找最优解。单纯形方法的主要思 想，就是先找一个基本可行解，判别它是否为最优解。如不是，就 找一个更好的基本可行解，再进行检验。如此迭代，直至找到最优 解，或者判定它无界。这一方法为线性规划的理论与计算奠定了基 础。1 9 7 7 年，r 。g b l a n d 修正d a n t z i g 的最负检验数法则，使单纯 形法必能经有限次迭代求出最优解或者肯定该问题无最优解。单纯 形法因其理论完整和操作方便，一直是实际应用中一种有效的计算 方法。 但是理论分析表明，由于单纯形法是沿可行域顶点进行迭代， 在最坏情况下其算法的时间复杂度是0 ( 2 ”) ，这是各种时间复杂度 中最差的。美国学者v k l e e 和g l m i n t y 曾给出了这样的反例 予以证明。 1 9 7 9 年，苏联青年学者l g k h a c h i y a n 总结前人成果，基于 和单纯形法完全不同的思想提出称为椭球法( e l l i p s o i dm e t h o d ) 的 新算法。椭球法不是直接处理线性规划问题，而是先判定线性不等 式组 a x b ( 1 1 2 ) 是否有解，其中a 是m n 矩阵，x r “，6 r “。算法的基本思 想是首先取一个很大的球，其半径大到足以包括( 1 1 2 ) 的一个解 一2 一 在球内。标明初始球中的解集为e ，然后按照体积收缩方式构造一 系列椭球b ( 五一1 ，2 ，) ，使得e s 巨。可以证明，经过多项式次 迭代后算法要么找到椭球的中心即为解，要么证明( 1 1 2 ) 没有解。 k h a c h i y a n 给出算法的时间复杂度为o ( n 4 l 2 ) ，这在理论上是个重 要突破，k h a c h i y a n 也因此在1 9 8 2 年获国际f u l k e r s o n 奖。遗憾的 是广泛的实际检验表明椭球算法的计算效果比单纯形方法差，因此 它还不能在实际使用方面取代单纯形法。 1 9 8 4 年，在美国工作的印度学者n k a r m a r k a r 提出了求解线 性规划阉题的另一个具有多项式时间的算法。他将标准形线性规划 问题( 1 1 1 ) 转化为另一形式的线性规划问题 m i n f ( x ) = c r x s t a x o( 1 1 3 ) ，x = 1 x 0 其中a 为行满秩的m n 矩阵，c ，x p ，p = ( 1 ，1 ，1 ) 7 ，记 o o = x r “1 4 x = 0 ，e 啊一1 ) ，s = x r 。l = 1 ，x 0 ) j 撇r a i n c r x = 0 ，口。一三珐，口。o 。其算法是通过 x 口 m n 一 沿负投影梯度方向，并借助投影变换，使函数，( x ) 趋于最小值。 即使得可行域中某个内点在可行域内部按正确选择的步长沿着“较 好的方向”穿行到最优解。k a r m a r k a r 算法的时间复杂度是 o ( n l ) ，比椭球法有所降低，而且，对于解决多变量的大型线性规 划问题，明显比单纯形法有效。受k a r m a r k a r 法的思想启发，所谓 内点法( i n t e r i o rm o t h o d ) 范畴里的各种方法在后阶段被相继提了出 来。但是，对于变量较少的问题，以及用分块解决综合性的线性规 一r 一 划闷题，单纯形法仍优于其它方法。 由于各种迭代算法包括单纯形法，椭球算法，k a r m a r k a r 算法 以及它们的改进算法均存在诸多不足，因此，努力降低算法的复杂 度，寻求线性规划解法的完善这一课题具有非常重要的理论和实际 意义。 1 2 ( u l p ) 的一般描述 对于线性规划问题 m a x f ( x ) = c r x ( 1 2 1 ) 文t a x 6 其中c = ( c i ，c 2 ，c ) 了和x q l ，z 2 ，z 。) 丁是，l 维列向量， 4 为m x n 常数矩阵，右端向量6 = ( 6 ，b ：，九) r 是研维列向 量。这里，( x ) 一伊x 称为目标函数，满足约束条件4 x b 的向量 x 组成的集合称为可行域，记为d 。 为讨论方便，假定上述问题的变量个数，z 比约束条件( 包括变 量约束条件) 个数m 小，用n r r 表示a 的第i 个行向量，口，r 一( 口n m 2 ，口“) ，i = 1 ，2 ，优。对向量口。t 和c 实施单位化，从而得 到本文主要讨论的一般线性规划问题( u n i v e r s a ll i n e a rp r o g r a m m i n g ) ，简记为( u l p ) ： m a x f ( x ) = 似 c ，x r 。，c 2 = l s f 口f 啊巩毋r 4 ，b i r ，口f 2 1 ( 1 2 2 ) 1 i m ，m ，l 我们这里对线性规划问题的提法没有自变量非负的限制。虽然 一t 一 实际应用中出现各种线性规划问题，但是其中很大一部分都可以变 成上述问题( 1 2 2 ) 的形式。 本文将从一个新的角度出发，由线性规划的几何理论提出 ( u l p ) 的直接解法。文章力求通过几何直观阐明算法的基本思想， 然后论证相应的定理作为算法的理论基础，最后用一定的算例说明 直接解法的应用并对算法的复杂性作出简要分析。 第二章尺“空间几何 本章的宗旨是为线性规划提供一个几何解释。一旦对其几何特 征有了理解，我们就可以循着直觉去处理使那些已知结果生效的代 数表示，并且去研究关于线性规划的新的理论。本章前3 节引述一 些基本概念。最后一节给出6 个重要定义，这些定义和概念是下一 章的几何基础。 2 1凸集 为了分析线性规划问题的几何特征，我们从研究可行域的凸性 着手，为此先介绍仿射集和凸集。 设x 1 和x 2 为竹维欧氏空间刃中相异的两个点，一个集合s 彤称为仿射集，如果对任意的x 1 ，x 2 s ，口r ，都有a x l + ( 1 一口) x 2 s 。 一个非空仿射集s 的维数定义为与它平行的子空间的维数，记 为d i m ( s ) 。维数为0 ，1 和2 的仿射集也称为点，直线和平面。 集合c r 4 称为凸集，如果对任意的x 1 ，x 。c ，口 o ，1 都有a x l + ( 1 一a ) x 2 c 。规定空集及仅含一点的点集是凸集。 由凸集定义容易得出：任意一组凸集的交集也是凸集。 一类重要的凸集是凸锥。如果一个凸集c 对非负的数乘封闭， 即由x c 和口0 可得以c ，则称c 为凸锥。 一6 一 2 2 超平面 线性规划中最基本的几何实体之一是超平面。 给定b r 及非零向量口r “，则集合 h = x i a r x = b ) 是p 中的一个超平面，并且彤中任一超平面都能表示成这种形式。 在a 和b 可约去一个常数的意义下，这种表示是唯一的。向量a 称为 胃的法向量，的任一个法向量都可由口乘以一个非零常数得到。 彤中的竹一1 维仿射集是超平面，超平面是凸集。 p 中的超平面可由一点x o 和”一1 个线性无关的方向向量a ， 口：，吼一。确定，即殿中的超平面有参数方程 x x o + a 1 口1 + + 九一l 口。一1 彤中的两个超平面 霄i ：a - x b 。 和 耗j ：n 天x b i 的相互位置有相交，平行和重合三种： ( 1 ) a f 2 a ( a o ) 时相交。 ( 2 ) 啦一, l a j ( a o ) 且以曲j 时平行。 ( 3 ) 啦= 妇( a o ) 且岛= 蝇时重合。 一个超平面将空间即分成两个闭凸域 h l 一 x f 盘r x b 及 一7 一 h u 一 x f a r x b 它们相交在超平面h 上，移开h 就导致两个不相交的开凸域。闭凸 域是凸集，它总能表成 x l 口t x b ) 的形式。 ( u l p ) 的可行域d 是p 中闭凸域( x f a 2 x b r ( ；一1 ，2 ， 辨) ) 的交集，故是凸集。通常称这种有限个闭凸域的交集为多面凸 集。若一个集合既是凸锥，又是多面凸集，则称为凸多面锥。容易 知道，一个凸多面锥是有限个过原点的闭凸域的交。 2 3 直线和线段、离差、界面与顶点 1 直线和线段 若x o 为殿中一定点，v 为非零的方向向量，则集合 z = x l x = x o + t v ，t r 称为p 中过点x o 具有方向矿的直线。集合 i x l ，x 2 一( x i x = a x l + ( 1 一a ) x 2 ，0 口1 称为印中以x 1 和x 2 为端点的线段。 彤中的直线x = x o + t v 与超平面口? x b 的相关位置有三 种情形： ( 1 ) 丑= 2 - 0 时，直线与平面相交。 ( 2 ) n 丁v = 0 且4 t x o b 时，直线与平面平行。 ( 3 ) 口w = 0 且口t x o = b 时，直线在平面上。 2 离差 称 一r 一 d ：b - - 。a r x 。( 2 3 1 ) 口。 为点x 。到超平面a r x = b 的离差。这样，彤中的超平面口r x = b 把 印空间分成三部分，各部分的点到该超平面离差分别大于零，等于 零和小于零。 3 界面 凸集c 的非空子集c 若满足条件：如果x c ，且x 是c 的 一条线段的内点，即存在x 1 ，x 2 c ，使x ( x 1 ，x 2 ) ，则可推得 x 1 ，x 2 c ，就称c ，是c 的一个界面。 显然，多面凸集的界面还是多面凸集。 4 顶点 c 是凸集，x c ，若x = a x l + ( 1 一a ) x 2 ，x 1 ，x 2 c ，口 ( o ，1 ) ，必有x 1 一x z x ，则称x 为c 的顶点或极点。直观地 说顶点不是c 中任一线段的内点。 凸集c 的1 维界面也称为边，0 维界面也称为顶点。 2 4r “空间中的投影变换 本节提出r n 空间中的6 个重要定义，进一步阐述( u l p ) 的几 - 何特征。 定义2 4 1 不等式a r x b 规定向量a 为平面a r x b 的内 法向，闭凸域d 。一 x i a r x b ) 为平面a r x = b 的内部，开凸域d z 一 xl a t x , 6 为平面口r x 一6 的内法向、内部、外部。 这种定义下平面4 t x = 6 已经是有向平面，它是其内部和外部 的界面。两个平面的内部的交称作两个平面的内部。若两个平面的 内部4 包含另外两个平面的内部b ，则称a b 。 设有口，t x b i 规定的有向平面 ：a i t x = b f 由点x o 作直线x x o + t v ，直线与平面的内部的交满足 t a f w b l a i t x o 若a , r v 0 ，则有 t 笋 若a l r v 0 ，则有 t 笋 若a l r v = 0 ，则仅当 a f 丁x 。b l 时，一o o t 0 时，称 踮= ( b _ - - r a i t x 。) v ( 2 4 1 ) 为由点x o 沿方向y 到平面毋：a i t x 一玩的最小离差向量。 当口r y 0 且口7 y 0 且a j t v n ) 将式( 3 1 2 ) 规定的凸集称为( u l p ) 的可行域，可行域中使目标函 数f ( x ) 取得最大值的点称为( u l p ) 的最优解。 式( 3 1 。2 ) 对应的有向平面的不同组合可能界定多个凸多面锥， 由于( u l p ) 的可行域是( 3 1 2 ) 中所有平面的内部的交，它在( 3 1 2 ) 中部分界定的所有可能的凸多面锥中最小。 定义3 。1 1 由式( 3 1 2 ) 中部分界定的凸多面锥上，使目标函 数取得该凸多面锥上最大值的点称为( u l p ) 的准优解。 一1 5 由定义3 1 1 得出的一个直接结论是： 定理3 1 2( u l p ) 的准优解必在相应的凸多面锥的顶点达 到。 证由于凸多面锥是凸集，过凸多面锥内任一点x 的直线l 与 凸多面锥的交构成的线段的端点必在凸多面锥的界面上。因为 ，( x ) 一伊x 是线性函数，则沿每一条线段目标函数呈单调变化， 故结论成立。 定义3 1 3 平面伊x h 称作( u l p ) 的一个等势面，h 是该 等势面的高度。 等势面的高度这个概念可以形象地说明下面的引理： 引理3 1 4 凸多面锥的顶点x 。是( u l p ) 的准优解的充分必 要条件是过x 。的等势面在该凸多面锥的上方。 证过凸多面锥的任意点x 作等势面x h ，过顶点x 的 等势面c 啊一h 在凸多面锥的上方等价于h h ，也就等价于对 凸多面锥内任一点x 都有，( x ) ，( x ) ，从而引理得证。 和引理3 1 4 一个等价的提法是： 引理3 1 5 凸多面锥的顶点x 是( u l p ) 的准优解的充分必 要条件是该顶点的内部上有界。 凸多面锥是顶点是恕个法向线性无关的超平面的交，为了确定 它是否为准优解，只需要考察以这”个平面为邻接界面的凸多面 锥。有两种情形，对于第一种情形即n 个法向线性无关的超平面包 含等势面，明显有： 定理3 1 6 含等势面研：口，x 一良的行个法向线性无关超平面 的交是准优解的充分必要条件是 口一一1( 3 1 3 ) 一】6 一 证对于以含等势面t ：a t x = b l 的竹个平面为邻接界面的凸 多面锥的顶点，其内部仍有行个线性无关的方向，它们可能也只能 由这，z 个邻接界面从上方界定，由引理3 1 5 ，凸多面锥的顶点是 准优解，此时 a r c = l a 。ii c i c o s 尢 = 一1 下面只讨论雄个法向线性无关的非等势面交于x 。的情形，这 时，每个非等势面都与等势面“：x = h 相交，从而有与引理3 1 4 等价的 引理3 1 7 不含等势面为邻接界面的凸多面锥的顶点x + 是 ( u l p ) 的准优解的充分必要条件是该顶点的内部的等势面上所有 线段当等势面的高度h 增大时在过x 。的等势面上收缩成点x 。 非等势面而：a t x = b ，的内法向a ，可分解为 口f 一( 啦一a r c c ) + a r c c = 口抽+ 口击( 3 1 4 ) 式中，口* 0 ，口古o 。 口艄= 鳓a r c c 是巧对于等势面“：c 7 x = h 的保交垂直旋转 平面 7 ：( m a t c c ) r x b f a r c h ( 3 1 5 ) 的内法向，它与等势面“的高度h 无关，因此，当高度h 变化时，r “ 垂直于口村平行移动。若x 。是准优解，则x 。的n 个邻接界面对于 等势面：口x 一h 的保交垂直旋转平面交于直线x = x 。+ t c ，而引理3 1 7 就成为 引理3 1 8 不含等势面为邻接界面的凸多面锥的顶点x 是 ( u l p ) 的准优解的充分必要条件是在h c r x 的等势面巩：c i r x = h 上，x 的咒个邻接界面对于等势面的保交垂直旋转平面的内 部是有界的，而且，这些垂直旋转平面之间的弦长当等势面的高度 一1 7 h 增大时减小。 日士= a t c c 的正向由口w 确定。有两种情况： ( 1 ) 当a t c 0 时，疋的内部沿曩的法向上有界； ( 2 ) 当日c 0 时，t 的内部沿有挖个线性无关的方向是上无界 的。 定义3 1 9 平面7 1 i ：a t x = b 。在a t c 0 时称作第1 类平面， 在盘玛0 时称作第类平面。 定理3 1 1 0 ( u l p ) 的准优解必在第1 类平面上达到。 证根据定义3 1 9 及两平面间的关系可知：两个第1 类平面 研和j 的内部沿其法向q 和口都是上有界的；两个第类平面的内 部有行个线性无关的方向是上无界的。因此，对于第1 类平面必须 有第1 类平面上方限定它才能使它们的内部上有界，于是定理3 1 1 0 成立。 3 2 ( u l p ) 准优解的判定 对于( u l p ) 准优解的判定，本节提出四个判别数。 定义3 2 1 称 一a t a 一a t c a f c ( 3 2 1 ) 为( u l p ) 的第一判别数。具有对称性，即巩j = 啄。 定理3 2 2 非等势面而：口r x = b ，是不含等势面为邻接界面 的准优解x 。的邻接界面的必要条件是存在x 的另一邻接界面巧： 口歹x b ，使得 一1 r 一 矾j 二0 证非等势面曩：a t z 一6 i 是不含等势面为邻接界面的准优解 x 的邻接界面，说明顶点x 的n 个邻接界面对于等势面丌 的保交 垂直旋转平面的内部在等势面巩上有界，则对每一个都有另一 个，使得 ( 啦一a y c c ) ? ( q 一口y c c ) 0 由定义3 2 1 ，此即 0 根据定理3 2 2 ，明显有 推论3 2 3 若式( 3 1 2 ) 中有平面孔满足 0 ( 1 j m ) 则( u l p ) 无最优解。 定义3 2 4 称 b ：錾+ 錾 ( 3 2 2 ) g i i o i i 为( u l p ) 的第二判别数。入；j 具有对称性，即b k 。 定理3 2 5 ( u l p ) 的准优解在平面吒：a t x b t 和第1 类平 面：a y x b ，的交上达到的必要条件是b 0 。 证容易验证 v 一a , - - 孓a 。t c c + a i - ；a ，c c ( 3 2 3 ) o n 6 1 l 是“和的内部能有界交方向，而且在等势面上 d 一堕堕咝堂二麦址3 4 ，一j - _ = = 坚二l _ 二业( 2 ) 0 o t tq 8 t l d t 是由丌 的原点0 。沿方向y 由平面到巩，的弦。( u l p ) 的准优解 在平面曩：n t x b l 和第1 类平面乃：盘r x ：b ，的交上达到，必有 巩。到“，的弦长i d l 当等势面的高度h 增大时减小，这等价于 屯 0 于是定理获证。 推论3 2 6 若第1 类平面l r i ：4 ，x = b ，的b 0 ( 1 j m ， _ i ) 的个数小于，l 一1 ，则不可能是准优解的邻接界面。 定义3 2 7 称 勘= a r c n j a f r c ( 3 2 5 ) 为( u l p ) 的第三判别数。当i j 时，筋= 0 。 定义3 2 8 若( u l p ) 的准优解x 。的邻接界面满足 筋0 且( 1 歹，l ，j i ) 屯 0 则该邻接界面称作x 。的基邻接界面。 定理3 2 9恕个法向线性无关的平面的交x 。是准优解的必 要条件是x 有基邻接界面。 证容易验证譬是毋和c 的夹角的余切，a t c n 接近一1 时， b 越小，即顶点x 。的挖个邻接界面中越接近等势面的第1 类平面 越能从上方限定x 。的其它邻接界面。若矩个法向线性无关的平面 的交x 。是准优解，即等势面高度h 增大时在x 。之下有弦长i d i 减 小，则在x 的邻接界面中需且仅需有一个第1 类平面毋对其它邻 接界面7 r ，满足 一2 0 ( c a t c a f ) 丁( 盘j a t a j a f ) o 即有 砌0 同时由定理3 2 5 可知 b 0 故由定义3 2 8 知x 有基邻接界面。 定义3 2 1 0若对于平面乃：a y x b ，和乃：4 x = b j 有 a t c 口弦 则称平面雨比平面吗大。 定义3 2 1 1 称 三l 上里l 。：坐o 盏 ( 3 2 6 ) 珊。；= _ l 5 b ， 、，口“ 为( u l p ) 的第四判别数。 称 r l ；i = 1 + 皇 ( 3 2 7 ) o i i o i i 为平蕊雨：a f x = b i 和吗：a f x = b j 的临界数。 定理3 2 1 2 不含等势超平面的n 个法向线性无关超平面玛： a ，x = b j ( 1 j n ) 的交是准优解的充分必要条件是其中有一个第1 类平面再使得 b 0 且( 1 - f 玑j i ) 阮i 0 2 1 而且对每个吗都有m 使得 正( 1 k 咒。k i ，k j ) 证设砜t 和砜j 是顶点x 。的邻接界面确和码对于等势面7 r h 的 保交垂直旋转平面，则 v ：a f - - a t c c i a i - - a t f c c o “ o i i 则砜i 和7 c h j 的直径方向，它指向砜i 和砜j 的内部，为了使7 【h i 和砜j 的内 部在托“上有界，需且仅需有一个札，其内法向介于一( a i - - a ，c c ) 和一( a j - - a 于c c ) 之间，也即 、 等势面砜上有且只有n 一1 个线性无关的方向，因此，顶点x 的n 个邻接界面对于砘的保交垂直旋转乎顽的内部在等势面7 r h 上有界 就等价于对x 。的某个第1 类邻接界面雨和x 。的其它邻接界面码 ( 1 j n ，j i ) ，都有x 的另一邻接界面孤( 1 k n ，k i ，k j ) 使得 l 沸 考虑到等号对应予准优解在低维等势面上的情形并联系定理3 2 9 ，可知定理3 2 1 2 成立。 3 3 ( u l p ) 的最优解 关于( u l p ) 的准优解个数与( u l p ) 的顶点个数的比较，有下述 定理： 定理3 3 1对准优解x 。的n 个邻接界面加入另外一个第1 2 2 类平面只能使准优解的个数增加1 。 证设x 是( u l p ) 的一个准优解，x + 的n 个邻接界砸是7 c ， ，丌。，现加入第1 类平面+ 。，使凸多面锥的顶点个数增加n 个， 它们是 c 。+ 。和x 。的n 条棱的交点。若+ 。和x 。的棱x 。a 的交a 是准优解，+ 。和x 。的任意另外一条棱x 。b 的交点是b ，不妨设 x 。a 是7 r ，一l 的交，棱x b 是行2 ，7 c n 的交，若 ，( a ) ，( x 。) 则a 在x 的下方，由于a 是7 r 1 ，一1 ，7 c n + 1 的交，b 是“2 ， ，砺+ l 的交，+ l 就和由x 。a 和x b 张成的x 。的二棱面丌交于 直线b b 7 ，b 7 在x 。a 上，则a a 和b b 平行。a 是兀1 ，7 c 。一1 ， 7 c 。+ ，界定的凸多面锥上的准优解，于是线段a b 在a a 7 的下方，也 就有a b 在b b 的上方，从而b 不可能是7 c 。，7 c n ，7 c 。+ 。界定的凸 多面锥上的准优解。若 ，( a ) ，( x 。) 则同理可证结论成立。 这样，( u l p ) 的准优解个数比其顶点个数要少很多。 ( u l p ) 的基本定理指出了如何判别准优解，这是对凸多面的锥 “形状”的处理。下一步是确定“位置”，即从( u l p ) 的准优解中找出 符合条件的最优解。 定义3 2 2 若( u l p ) 的k 个不同的准优解x 1 ，x 2 ，x 。都 有n 一1 个邻接界面 氆：, f i x = b ，( 1 i ，z 一1 ) 则它们的k 个不同的邻接界面 ：( a d 7 x = b i ( 1 i 托一1 ) 称作( u l p ) 的一组竞争平面，这k 个不同的准优解称作( u l p ) 的一 2 3 组竞争顶点，一组竞争顶点的公共的邻接界面的交称作这组竞争顶 点的一条基棱。 设x o 是基棱上一点，v 是基棱上目标函数增大的方向，则基 棱的方程是 x = x o 一- t v 它与可行域d 的交的下确界可以求出，该基棱上的竞争顶点即基棱 与竞争平面的交是否在可行域上以及它们的目标函数值的大小均可 以进行判断，于是逐组比较准优解可以最终求出( u l p ) 的最优解。 3 4 ( u l p ) 的直接解法 总结前3 节内容，可得出( u l p ) 的直接解法( d i r e c tm e t h o d ) 。 其计算步骤是： ( 1 ) 目标函数和约束平面法式法。 ( 2 ) 计算a ? c ，按式( 3 2 1 ) 、( 3 2 2 ) 、( 3 2 5 ) 计算百i j 入i j ，肛i j ， 并按平面由大到小的顺序( 不妨设a t c a c a v c ) 构造基本表 1 ： c ( o l ，c 2 ，h )b ld c a j c k 坤j v a la 2a ma la 2a m a l ( 8 n ，8 1 ) a 2 ( 8 n ，8 h ) a 。( a 。l ，a 。) 表1 中虚线以上的部分是第1 类平面，虚线以下是第类平 面。折线左下方是a ? s j ，折线右上方是，a t a j 和均具有对称性。 对h 和m 只要标明正负号即可，由于第1 类平面间的入j 总为负，故 表中可不予列出，第1 类平面问的蛳不起作用，表中也可不予列 出。 若有平面7 c k 满足0 ( 1 j m ) ，则( u l p ) 无最优解；若每 个第1 类平面雨满足k 0 ，仃1 4 0 ， 盯1 5 0 ，仃2 4 0 ，d 2 5 0 ，盯2 6 0o d 3 4 0 ，口3 5 0 ，盯3 6 0 ，盯3 7 0 ； d 5 6 ：0 ，盯5 7 0 ，卢1 7 o ； 产2 l 0 ，鲍3 0 ，牟。l 0 ，z 2 5 0 ，肛2 7 0 。 由此可列出基本表1 ，其中表的最后项每格上排为k 的符号，下排 为t z i j o 的符号( 包括零) a t c k i f 3154 1 ： 吨t i。l 而而而而j a t c a a 4 a s a i i l & l& i a 4a l , a l l t ( 杀，涪杀杀) 德 mm 4l 目月r r ， mm瓶 一 8 ( o 。1 0 ，o ) 日据 i 日, z g g - “i7 靠。 r 月1 - immm硝属 1 5 瓣 8 5 ( 1 0 0 ，o ) 日m- 4 1 6据 a ( 0 0 0 ，1 ) 辱 口日 a 7 ( 0 。0 1 o ) 时百百辱 5 日 从上表可知，p t j ( j i ，1 j 7 ) j , 于零的个数为2 ，p 动( j i ，1 j 7 ) j , 于零的个数为1 ，二者均小于3 ( 本题n = 4 ，则n l - - 3 ) ， 即所有第1 类平面的m o ( i = l ，2 ；，1 j 7 ) 的个数小于n - - 1 ，故 由定理3 2 1 2 可知问题无有限最优解。 例4 2 解下面的线性规划问题 m a x f ( x ) 一z l + 3 x 2 一z 3 5 t z 2 + 2 x 3 + z 4 一z l + 2 x z + z 3 + 甄4 3 x 1 + 3 x 2 + 毛4 z 1 ，z 2 ，2 3 ，z 4 0 解将目标函数和约束平面法式化，该问题可化为( u l p ) ： m a x f l ( x ) 2 _ 1 4 = 1 1 而+ _ 4 坠1 1 。z 一_ 4 圣1 1 z s ( ，1 ( x ) ：占，( x ) ) 1 1 “一 z 2 一每z 3 一下1z 4 一下4 n 六一万屯一万如一万气方一万 圭z l 一名z 2 一 秭一下1 毛一车4 万如一万屯一万秭一万毛乡一万 一 z 。一 。一士缸一7 4一- = z l 一_ = 0 3 一_ =