（应用数学专业论文）线性规划与约束非线性规划问题的算法研究.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 线性规划与约束非线性规划是优化与决策理论中的两个重要问题，本文 在已有研究成果的基础上，对这两类问题的算法做了进一步的探讨与研究 文章内容由两个部分组成。第一部分内容是在n 维欧氏空间理论的基础 上提出了一种求解线性规划问题的新算法一“点线蘑”循环寻优法。f 本算法 是基于如下思想提出来的：我们知道，在三维欧氏空 司中，线性规瑚问惠的 可行域是一个由若干个平面围成的广义多面体，目标函数可以看作是以目标 函数值为参变量的一个平行平面束。如果线性规划问题有最忧解，那么过可 行域的一已知顶点必至少存在这样一条棱它以该已知顶点为一端点，可 行域的另一顶点为另一端点，并使目标函数在另一端点的函数值忧于已知端 点的函数值，否则，该已知点就是线性规划问题豹最优解。继续上述过程， 就能求得线性规划问题的最优解。这就是说，自可行域的某顶点出发，沿可 行域的棱经过若干次可行域顶点的转移后就能得到线性规划问题的最忧解 ( 在最优解存在的情况下) 。这样，我们自然会想到这样一个问题：能番把 这种方法从三维情形推广到n 维情形? 这就是“点线面”循环寻优法的学术 背景。与现有的单纯形法相比，新算法具有如下主要特征：第一，求解教程 不需要引进诸如松驰变量、人工变量等参变量参与运算，计算量大大减少了； 第二，新算法较单纯形法的结构化程度高更容易转化为程序语言，进葡在 计算机上更快地得以实现；第三，新算法在运算过程中不会引起摄动瑗象。 第二部分内容是关于如何利用s u m t 与a g 求解带约束条件的非线性规划 问题透过这部分内容，我们将发现，把$ u m t 与a g 结合在起运用到 求解帮约束条件的非线性规划问题可以克服其他一些算法的局限性，譬如， 函数的可导性、单峰性等，因而这种方法的应用苹围更广尤其在求解大型 带约束条件的非线性规划问题上效果更为明显) 关键词：线性规划； 、一， 柬啡线性规划； v 算法 ， 甲 西南交通大学硕士研究生学位论文第1 l 页 a b s t r a c t a sf o rt h et h e o r yo f 0 p t i m i z a t i o na n ds t r a d e g y ，l i n e a rp r o g r a m m i n ga n d c o n s t r a i n e dn o n l i n e a rp r o g r a m m i n ga r ct w o i m p o r t a n tp r o b l e m i na c c o r dw i t h p r e s e n tc o n c l u s s i o n s ，t h ep a p e rh a sd o n es o m ef u r t h n ra n db e n e f i c i a lw o r ki n t h e i ra l g o r i t h m s n l i sp a p e ri sm a d e u p o f t w os e c t i o n s i ns e c t i o no n e b a s e do n t h e o r y - o f n d i m e n s i o n a le u c l i d s p a c e a n e wm e t h o d1 a b e l e d a s “p o i n t l i n e p t a n e ” r e c y c l i n go p t i m i z a t i o na l g o r i t h m i sp r o p o s e dt os o l v et h el i n e a rp r o g r a m m i n g p r o b l e m t h i sa l g o r i t h mi sp r o p o s e do nt h eb a s i so f t h et h o u g h ta sf o l l o w s ：a s f o rt h r e ed i m e n s i o n a le u c l i d s p a c e , t h e f e a s i b l e r e g i o n o f a n y l i n e a r p r o g r a m m i n gp r o b l e mi s ae x t e n d e dc o n v e xp o l y h c d r o n o fw h i c hs u r f a c ei s c o n s i s t e do fs o m ep l a n e s 。a n di t s o b j e c t i v ef u n c t i o nc a nb er e g a r d e da s a p a r a l l e lp l a n ep e n c i lw i t ho b j e c t i v ef u n c t i o nv a l u ea c t i n ga sp a r a m e t e r i fs o m e l i n e a rp r o g r a m m i n gp r o b l e mh a so p t i m u ms o l u t i o n ，t h e nt h e r em u s ta tl e a s t e x i s ts u c hae d g ea m o n ga l l e d g e sp a s s i n gt h r o u g hs o m ek n o w nv e r t e x o f f e a s i b l er e g i o nt h a tt h eo b j e c t i v ef u n c t i o nv a l u eo ft h eo t h e rv e r t e xi sm o r e o p t i m i ct h a nt h eo n eo f t h ek n o w nv e r t e x ，o t h e r w i s e ，t h ek n o w nv e r t e xl st h e o p t i m u m s o l u t i o no ft h el i n e a rp r o g r a m m i n gp r o b l e m c o n t i n u i n ga b o v ec u r s e ， t h e nw ec a ng e ti t so p t i m u ms o l u t i o n ，t h a ti st os a y , s t a r t i n gf r o ms o m ef e ) s i b l e v e r t e x ，w ew i l lg e tt h eo p t i m u ms o l u t i o no fs o m e l i n e a rp r o g r a m m i n gp r o b l e m a f t e rf i n i t et i m e st r a n s i t i o no fv e r t e x a l o n ge d g e o ff e a s i b l e r e g i o n s p o n t a n e o u s l y , i to c c u r st ou sw h e t h e rw e c o u l dg e n e r a l i z et h ea l g o r i t h mf r o m t h i n ed i m e n s i o n a lc a s et ond i m e n s i o n a lo n e ，t h i si st h ea c a d e m i cs e t t i n go ft h e “p o i n t l i n e p l a n e r e c y c l i n go p t i m i z a t i o na l g o r i t h m i nc o n t r a s t t o e x i s t i n g s i m p l e xm e t h o d 。t h i sm e t h o d h a ss e v e r a lp e c u l i a r i t i e sa sf o l l o w s ：t ob e g i n 诚m ， a p p l y i n gi t t os o l v el i n e a rp r o g r a m m i n gp r o b l e m o n en e 圮d n ti n t r o d u c ea n y a d d i t i o n a lv a i l a t ) l es u c ha sr e l a x i n gv a r i a b l e ，a r t i f i c i a l v a r i a b l ea n do t h e r p a r a m e t e r s ，s ot h a tc a l c u l a t i o ni ss u b t r a c t e do n al a r g es c a l e i na d d i t i o n1 1 3t h i s ， a sar e s u l to fi t sh i g h e rd e g r e eo fs t r u c t u r a l i z a t i o n ，t h i sa l g o r i t h mc a nb em o r e e a s i l y t r a n s f o r m e di n t o p r o g r a ml a n g u a g e a n d ，o fc o u r s e ，m o r eq u i c k l y 西南交通大学硕士研究生学位论文第1 li 页 p e r f o r m e db yc o m p u t e r s m o r e o v e r ，c o m p a r i n g w i t h s i m p l e xm e t h o d ，t h i s a l g o r i t h m c o u l d n tc a u s ev i b r a t i o np h e n o m e n o n i ns e c t i o nt w o i s s u ei n v o l v e s h o wt oc a l c u l a t et h ec o n s t r a i n e dn o n l i n e a rp r o g r a m m i n gp r o b l e mb ys u m t a n d a g mm e t h o do v e r c o m e ss o m e l i m i t a t i o n ss u c ha s d i f f e r e n t i a b i l i t y , c o n t i n u i t y o r s i n g l e p e a k o ff u n c t i o n se t c i t s a p p l y i n gc a t e g o r y i sm o r e e x t e n s i v et h a na n yo t h e re x i s t i n gm e t h o d s e s p e c i a l l y , i ti sv e r ye f f i c i e n tf o rb s t oc a l c u l a t eh u g ec o n s t r a i n e dn o n l i n e a rp r o g r a m m i n gp 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 r n m i n g ( l p ) ；c o n s t r a i n e d n o n l i n e a r p r o g r a m m i n g ( c n p ) ；a l g o r i t h m 西南交通大学硕士研究生掌位论文蕈1 页 1 1 问麓的提出 第1 章绪论 线性规划( l i n e a rp r o g r a m m i n g 简称l p ) 是运筹学的重要分支，自1 9 4 7 年丹麦捷格( g b d a n t z i n g ) 提出了一般线性规划问题求解法单纯形法 之后，线性规划在理论上趋向成熟，在实际应用中也日益变得广泛与深入。 特别是在电子计算机能处理成千上万个约束条件和决策变量的线性规划问 题之后，线性规划的适用领域更为广泛了从解决技术问题的最优化设计， 到工业、农业、商业、交通运输业、军事、经济计划和管理决筑等领域都可 以发挥重大作用，它已是现代科学管理的重要手段之一。 尽管如此就基本的算法而言，单纯形法由于引进了大量的松驰交量和 人工变量或其它参数，使其计算量大大增加，尤其是，单纯形法中的旋转变 换极其烦琐，并且利用单纯形法有时会出现摄动现象，从而导致寻优过程出 现障碍。另外，由于结构化程度不高，把整个过程编辑成能用计算机实现的 应用软件程序很复杂，虽然现在具有这方面的软件能实现单纯法求解普通线 性规划问题，但不可避免地浪费了信息储存资源，影响计算机处理速度。 鉴于上述情况，我们基于已有知识，即空间解析几何、线性代数等几门 学科理论，对n 维e u c l i d 空间理论进行了有益的探讨，并建立了相关理论 ( 主要是对三维欧氏空间知识的推广与应用方面) ，以此为基础，进两从一 个全新的角度对线性规划问题的算法进行了再研究，并形成了新的算法 “点一线一面”循环寻优法。 约束非线性规划( c o n s t r a i n e dn o n l i n e a rp r o g r a m m i n g 简称c n p ) 是运 筹学的又一重要分支，并在最优设计、管理科学、系统控制等许多领域得到 非常广泛的应用。 一般说来，解非线性规划问题( 简称n p 问题) 要比解线性规划闻题困 难得多，而且，也不象线性规划那样有单纯形法这一通用方法，非线性规划 目前还没有适于各种问题的般算法，各种方法( 如共轭梯度法，n o w t o n 法，内、外罚函数法等) 都存在很大局限性各有自己特定的适用范围并 且对一些病态型n p 问题，用上述方法无法解决，因此这是需要人们更深入 地进行研究的一个领域。 为此文章在最后一个部分，通过引进遗传算法( g e n e t i ca l g o r i t h m 简 西南交通大学硕士研究生学位论文第2 页 称g a ) 并结合序列罚函数变换在解决上述问题方面取得了较好的效果。众 所周知，g a 算法有很好的普棒性，即适应范围广，搜索效率高，很好地克 服了以往各种算法的诸多缺陷，通过引进序列罚函数变换使我们处理c n p 问题时，在方法上更加灵活多变，尤其是搜索范围可根据实际情况进行适当 的缩放，给闯题的解决和处理带来很大的方便随着计算机的广泛运用和处 理能力的不断提高，这种方法在处理c n p 问题方面，具有很好的应用前景。 1 2 理论与实际意义 与单纯形法相比，首先，运用“点线面”循环寻优法求解线性规划问 题，由于不需要引入松弛变量、人工变量和其它参变量而把一般型转变为标 准型，因而避免了用单纯型法求解大型线性规划问题时所出现的变量爆炸现 象。其次，由于在运算中没有基变量与非基变量的迭代过程，因此运用“点 线面”循环寻优法求解线性规划问题时不会产生摄动现象。另外，由于运 用“点线面”循环寻优法求解线性规划问题的过程相对较为简单，算法的 结构化程度更高，求解工作用计算机更容易实现从而较单纯形法有更好的 应用前景。 通过序列罚函数变换把约束非线性规划问题转化为一系列无约束非线 性规划问题然后运用g a 算法求解，这种方法突破了传统算法的诸多局限 性，适用范围广，为求解此类问题提供了一条崭新的途径，特别对求解大型 复杂的约束非线性规划阉题效果明显，这种方法不受目标函数和约束函数的 可导性、单峰性等条件的限制，使解决约束极值问题在方法上更为灵活、可 求解的问题范围更广。 西南交通大学硕士研究生学位论文第3 页 第2 章( 预备知识) n 维e u c | d 空间理论 2 1引言 文章后面将提出的新算法“点一线一面”循环寻优法是建立在n 维 欧氏空问知识基础之上、用来解决线性规划问题的解析算法，在此，有必要 把解析几何( 以三维欧氏空间为基础) 中的相关命题进行推广和延伸使它 们在r l 维( = 3 ) 欧氏空间中同样适用，同时，根据实际情况与需要更新或 添加一些新的概念和定理为后面的内容提供必须的理论支持，鉴于文章结 构和层次性方面的考量，我们特把这部分内容作为预备知识单独构成一个章 节，使整个文章的内容层次更加分明，结构更为合理。 2 2 数性积、矢性积与混合积 2 2 1 数性积与向量的正交性 在n 维e u c l i d 空间r “中，由于内积是两个向量对应分量之积的和，因而它是一 个实数，我们常把两个向量的内积也称为这两个向量的数性积。 根据上节( 2 3 ) ，向量x = ( x i ，x 2 ，x n ) ，y = ( y i ，y 2 ，y 。) 的数量积表示为 卫 ( x ，y ) = x l y l - - x 2 y 2 - - x n y n 2 x i y i ( 2 - 1 ) i = i 特别地，当( x ，y ) = 0 时，我们称向量x 与y 向量正交。 2 。2 2 矢性积及其性质 在向量代数中，当空间维数n = 3 时我们定义 。c x ，y ，= 基要善：i c 其中qc i = - ，：，为单位向量， 为向量x 与向量y 的矢性积( 或差积) 。 显然，在三维e u c l i d 空间中，两个向量的矢性积仍为一个三维向量。 在这里，我们把矢性积的定义从三维情形推广到n 维情形： 定义2 2 i 我们把 西南交通大学硕士研究生学位论文第4 页 e 2 e 工 砖) ) x x 称为n 一1 个n 维向量x ( 1 ( i = 1 ，2 ， ( 2 2 ) n 一1 ) 的矢积性，其中e i = ( o ， p ) 0 ，l ，0 ，o ) ( i = 1 ，2 ，n ) 记作 固( x ( ，x ( 2 ) ，x “一) 我们很容易验证 ( x n ，o ( x ，x n ，x ( a - - i ) ) = o( i = 1 ，2 ，n 一1 ) 即向量x x ( 2 ) ，x ”。的矢性积与其中每一个向量都正交。而且， 由矢性积的定义式可以看出矢性积不满足交换律。 因此，在n 维e u c l i d 空问中n 一1 个向量的矢性积仍为一个n 维向蛀，并且该向苗与 其中所有n 1 个向量都正交 2 2 3 混台积与共面向 基于n 维e u c l i d 空间向量的数性积与矢性积这两个重要概念我们来定 义何为混合积 我们称 ( x ( ， ( x ( 孙，x ( 3 ) ，x “)( 2 3 ) 为t l 维向量x ( ( 滓1 ，2 ，n ) 的混合积 记作 n ( x 0 ) ，x 舢，。x “) 我们很容易验证 i - i ( x n ，x ( 舶，x “) = 工 ) x p x p ( 2 - 4 ) 显然，n 个n 维向量的混合积的结果与数性积一样是一个实数，特别地，如 果 f i ( x ( ”x f “，x ) = 0 我们就说这n 个向量共面。 圳 西南交通大学硕士研究生学位论文第5 页 2 3 n 维f u o iid 空间的点、直线与平面 2 3 1点 u 维e u c l i d 空间r n 的向量也称为点，向量x 的第i 个分量x l 也称为点的 第i 个坐标，点与向量的表示方式完全相同，都用n 维有序数组表示为( x ， ) q ，x n ) 。 同时t 在1 1 维e u c l i d 空间r “中，两点x 与y 之间的距离定义为 d ( x y ) = i t x - - y u = 一 j 酚吖i ) 2 2 3 2 直线与直线方程 定义2 3 1 在n 维e u c l i d 空间r n 中，我们把具有 趟：邋 巧e ( 2 5 ) ：迸( 2 6 ) t n ( t i r ，i = l ，2 ，n ) 解析式的几何图形称为一条u 维欧氏空削( 超) 直线( 本文统称为直线) ，其中x 【o ) = ( x l 仇，x 字，x ? ) 为该直线上的已知 点，( t - ，t 2 ，t n ) 被称为该直线的方向矢( 或方向向量) ，并称上述( 2 6 ) 为该直线的点向式方程。 很显然，与三维情形样，在n 维e u c l i d 空间中直线同样由直线上的 一已知点和其方向矢唯一确定。 定理2 3 1 在n 维e u c l i d 空间中，两点确定一条直线。 从解析角度来看，这个定理正确性是显而易见的事，如果设这两点的坐 标分别为( x x 2 ，x ：) ，( x 1 2 ) , x 字，一，x 乎) ，那么该直线方程为 藉= 瓣x 2 - - x 2 ) 一= 蒜( 2 - - 7 )x 舶一x ( 1 )x 严一x 2 1x 一x ： 并称( 2 - - 7 ) 为该直线的两点式方程 2 3 3 平面与平面方程 定义2 3 2 在n 维e u c l i d 空间中，我们把具有 西南交通大学硕士研究生学位论文第6 页 a l ( x ! 一x ：o ) + a 2 ( x 2 一x 于) + + a 。( x 。一x 紫) = o n 。 ( a i r ，净l ，2 ，n 且a ? 0 ) 解析式的几何图形称为一个 i _ 1 n 维欧氏空间( 超) 平面( 本文统称为平面) ，其中( x l o ) , x 严，x ，) 为 该平面上的一己知点，向量( a l ，a 2 ，) 为该平面的法矢量，并 称之为平面的点法式方程。 通常情况下，平面的方程一般转化为如下形式 n a t xn + a 2 x 2 + + a n x n 。b ( 其中b = a j x l o ) i - l 并称之为平面的一般式方程。 很显然，欧氏空间中的平面可由平面上的一已知点和法矢量来唯一确 定。 定理2 3 2 在n 维e u c l i d 空间中，过n 个线性独立的点有且只有一个平面。 证明：存在性，设( x i ) ，x 2 1 ，x ? ) ( i = 1 2 ，n ) 为e u c l i d 空间中 n 个线性独立的点，不难验证 邑 = 0( 2 8 ) 是一个平面方程，且题设中各点的坐标满足该方程，即存在性得证。 难一性，设满足题设的r l 维平面方程为 a l x l + a 2 x 2 + + a 。x n = b ( a ；0 ) ( 2 9 ) i _ l 因( x 似x ，x ：) ( i = 1 2 ，n ) 均在平面上，由此可得下列方程 组 矗 西南交通大学硕士研究生学位论文第7 页 x l ”a l + x ! a 2 + x ：a 。= b x 2 ) a 1 + x 舢2 + x 黜。= b ( 2 一l o ) x l ”a l + x 字a 2 + x 拿a 。= b 把( 2 1 0 ) 看作为关于变量a i ，a 2 ，a 。的n 元一次线性方程组， 因为( x x 2 ，x ：) ( _ 1 ，2 ，。n ) 线性独立。所以该线性方骥组 的系数行列式的值非零，且b ：f ：0 ，由克兰姆法则和线性方程组( 2 1 0 ) 有 唯一解： a i = x 卜扎。驴 x p 1 x 乎 代入( 2 9 ) ，整理得 喜匡 n x 1 x 孑1 4 ) 1 x 紫 b( i = l ，2 ，1 1 ) l y - ! i “r - - t ” 矿p 妒- i 。 b ， ( 2 1 1 ) 显然( 2 8 ) 与( 2 - 1 1 ) 可以互化，即唯一性得证。 从而命题得证。 另外，在n 维e u c l i d 空间中与三维情形一样，任何一个平面 芝a i x i = b ( a i e r ，i = 1 ，2 ，：”n 且a ；o ) 均把整个空间分成三个解 i = l i = l 析性质不同的区域s l 、s 2 和s 3 ，使得 n s l = ( ( x i ，x 2 ，x n ) r ”i a i x i b ，a i 、b e r ， i = l n i = l ，2 ，n ，f a ? 0 青 卫 我们把s 2 称为s l 与s 3 的界面，方程a i x i = b 称为s i 与s 3 的界面方程。 i = l 2 4 r l 维e u c i d 空间图形的位置关系 2 4 1 直线与直线 在n 维e u c l i d 空间中，与三维情形一样，直线闯的位置关系也有如下三 种情形： 1 平行：无公共点，且方向向量线性相关； 2 相交：有唯一公共点： 3 异面：无公共点，且方向向量线性无关 2 4 2 直线与平面 在n 维e u c l i d 空间中，直线与平面之间与三维情形一样也有如下三种位 置关系 1 平行；直线与平面无公共点； 2 相交：直线与平面有唯一公共点( 这个公共点称为它们的交点) ； 3 在平面内：直线与平面有无数多个公共点( 至少有两个公共点) 。 定理2 4 1 在n 维e u c l i d 空间甜中 1 ) 如果直线的方向矢与平面的法矢不正交，那么直线与平面相交； 2 ) 如果直线的方向矢与平面的法矢正交，且直线与平面无公共点，那 么直线与平面平行； 3 ) 如果直线的方向矢与平面的法矢正交，且直线与平面有一公共点， 那么直线在平面内。 上述命题证明从略。 rbab = a 如。试如 厶汹吲扛谢 ， d ， n x n ： 2 2 1 卜 1 f | q i l = 西南交通大学硕士研究生学位论文第9 页 2 4 3 平面间的位置关系 类似地与三维情形相同，在n 维e u c l i d 空间中，平面与平面有如下两 种位置关系 1 平行：两平面无公共点( 或法矢量线性相关) ： 2 相交：两平面的法矢量线性无关； 特别说明：当维数n 3 时，两个平面的交不再是一条直线，即“两相 交平面确定一条直线”这一命题不再成立。 与上述命题相对应，当维数n ( n 3 ) 时，有下述命题成立： 定理2 4 2 在n 维e u c l i d 空间中，n 1 个法矢线性独立的平面的交构成 一条n 维直线，且该直线的方向矢与每一个平面的法矢都正交( 我们把该直 线称为这n 1 个平面的交线) 。 证明：设a 日x j = b i ( i = l ，2 ，n 1 ) 为n 一1 个法矢线性独立的 j = l 平面方程由此可构成如下n 元线性方程组 i a l l xj + a 1 2 x 2 + a l n x n = b l j a 2 1 x l + a 2 2 x 2 + 咀2 卸2 ( 2 - - 1 2 ) - 。 i a n - l , l x l + a n - i ，2 x 2 + a n 1 ，n xn = b - 1 并设a i ：( a i l ，a i 2 ，a i 。) ( i = l ，2r - n 一1 ) 为( 2 1 2 ) 的系 数矩阵 a 1 1a 1 2 a l “ a 2 1a 2 2 a 2 n a n - i 1a n i 2 a n l ，“ o ( a i ，a 2 ，a n 一1 ) 2i a 2 ia 2 2 a l lf 1 1 2 a a l 2 n n i。 l o l0 2 e n l a n - i ia n - 1 ，2 a n 一1 ，“ 西南交通大学硕士研究生学位论文第1 0 页 鼽州叫臣：兰芝。 即t l 是矩阵( ) 的行列式第一行第i 列元素e i 的代数余子式。 根据矢性积的性质，向量( t l ，t 2 ，t n ) 与每个向量a i ( i = l ，2 ， n 都正交，为了证明上述命题，现在我们构造如下直线 丑：趟一 弓 ：兰g 二兰墨 ( 2 一1 3 ) t “ ( 其中( x 1 0 ) , x 字，x ) 为线性方程组( 2 1 2 ) 的一特解) 很明显，要证明上述命题，我们只需证明如下结论 卜翰，x n 制x t - - x 1 0 ) 一警一= 半 = f c x ，x ：，x 。r “4 喜a i ，x ，= b ；= ，2 ，n 一， ( i ) 先证明“”关系 若 ( y ，y 2 ，y n ) x i ，x 2 ，x 。r n ) i 趟：进一：进l t 1i j1 i i j 则必然有一实数t ，使得 。 钆 吨 - 一 州缈 等一 一 _ - - 圳 钆虬 卜 。h = 西南交通大学硕士研究生学位论文第”页 因为a y j j = l ( t r )( 2 1 4 ) nnn = a 珏，v 0 j + t i t ) = a u x p + t au t j = b i + t = b i + t 0 = b l ( i = i ，2 ，n i ) 所以 c ，t ，：，y 。， c x ，x ：，x 。e r “，i 姜a 。x ，= b 。c t = t ，：，n 一 即 卜u - ，x n 刚，i x ! - l x l 。) = 学一华 c x 。，x z ，x 。e r “i 萎a ；。x ，= b t c i = ，z ， 成立。 ( i i ) 我们再来证“”关系 若 ( y l ，y 2 ，y 。) e x - ，x ：，x 。er “1 喜a t ，x = b ) ( i ：1 ，2 ，n 1 ) i j 令x n = - - l ，我们就可以得到( 2 - - 1 2 ) 的导出组的一基础解系 a = ( 寻专，等- 因此对( 2 - - 1 2 ) 的任意解( y t ；y 2 ，y n ) ，必然存在实数t ，使得 ( y 1 y 2 ，”，y n ) = t c t - l - x ( 0 ) = 晤( 0 ) ， 妒，寻t + x 跏硝) 西南交通大学硕士研究生学位论文第1 2 页 即 y y 2 ：玉 t n t 1 t n t + x ( 0 】 由( 2 - - 1 5 ) 消去参数t 得： t + x 字 逍：趟 t lt 2 ( t 为参数)( 2 1 5 ) ：趟 l 也就是说( y 1 y 2 ，y n ) 在直线( 2 - - 1 3 ) 上，即 ( y l ，y 2 ，y n ) 所以 x 。，x ：，x 。r “ ( x 。，x ：，x 。r “) ：进一： l x 。一x 紫 进：趟l t 2t nl c x - ，x ：，x 。r “，i 喜a ；，x ，= b t 综合证明过程中的( i ) ，( i i ) 可知 t x ，x ：，x 。s n ) 1 ( i = 1 , 2 ，n 一1 ) l x ，一x 于) = 耋j 一= l = 卜翰，x n 俐分 曲 x 一x ? = ! ! l 石 i ( i = 1 , 2 ，n 一1 ) j 州 x ， + n t xk l = = n n y y 华 簪 ， 一 西南交通大学硕士研究生学位论文第1 3 页 从而定理2 4 2 得证。 上述证明过程不仅验证了n 1 个法矢量线性独立的平面的交是一条直 线而且具体给出了该直线( 即交线) 的点法式方程。 定理2 4 3 法矢量线性独立的n 个n 维平面必相交于一点。 这个定理的证明较简单，直接由克兰姆法则就可以得出上述结论，证明 从略。 说明：利用定理2 4 2 和定理2 4 3 的结论可直接验证定理2 4 1 的正确性。 2 5 几个重要概念 1 凸集 定义2 5 1 设s 是n 维e u c l i d 空间的一点集，若任意两点”s ，妒 s 的连线上的一切点旺一”+ ( 1 一0 0 x ( 2 ) s ，( o 伍1 ) ，称s 为凸集。 我们很容易证明任何两个凸集的交集仍是凸集。 2 凸组合 定义2 5 2 设x ( ，x 1 2 ) ，x 。是n 维e u c l i d 空间的k 个点，若存 在l ，p 2 ，其中o 1 ，i 2 1 ，2 ，k ，“= 1 使x 。 p ix ( 1 + m x 2 ) + + 队x ( ，则称x 可表为x ，x 孙，x 。的凸组合。 3 凸集的顶点 定义2 5 3 设s 是凸集，x s ，若x 不能用不同的两点x 1 e s ，x 2 s 的线性组合表示为x = a ( 1 + ( 1 - a ) x a ( 0 ( ( 1 ) 则称为x 为凸集s 的 一个顶点。 4 多酉体与多面体的棱 定义2 5 4 在n 维e u c l i d 空间中，把由若干个n 维平面所围成的几何 体称为n 维多面体：把围成多面体的面的交线在多面体上的部分称为多面体 的棱。 我们按多面体的形状特征通常把多面体分为两个类型：凸多面体与凹多 面体，它们分别是凸集与凹集的两种特殊情形 2 6 几个重要定理 定理2 6 1若线性( l p ) 问题存在可行域，则其可行域 西南交通大学硕士研究生学位论文第14 页 d = x 1 ，x ：，一，x 。r r “id 2 妊1 ，x 2 ，一，xn “h a i j x j 茎( = ，) b i ，x j o ，i = l ，2 ，m ，j = 1 ，2 ，n j ：i j 1 是凸集i l l j 。 定理2 6 2 如果线性规划问题中n 个约束条件的界面方程组有唯一的 解并且可行那么此解表示的点是可行域的顶点( 即可行顶点) 。 分析：根据定理2 6 2 的题设可知线性规划( l p ) 问题的可行域存在，并由 定理2 6 1 得到其可行域为凸集，所以要证明上述命题成立，只需证明鞲足 条件的解不能表为不同的两个可行解的凸组合就行了。 证明：若x t o 是l p 问题n 个约束条件的界面方程组的唯一解，且可行。现 假设在可行域内存在两个相异点x ( i ) tx 孙，使x 1 0 1 能表为x ( 。x 1 2 的凸组合， 即存在实数旺e 【0 ，l 】，使得 x ( o ) = ax ( + ( 1 - a ) x ( 2 ( o o 1 )( 1 ) 因为x ( ，x ( 2 为可行域内两相异点，且n 个约束条件的界面方程组的解唯一。 因此x ，x ( 2 ) 至少有一个不是该方程组的解。 现不防假设x 【i ) 非该约束条件的界面方程组的解，那么在该方程组中必然 nnn 存在一个方程a 卑i = b ，使得a i x 1 ) b ，且方程a i x i = b 对应的约束 i - li = li = l 条件不为等式约束( 否则与x ( 1 是可行域内的点矛盾) n n ( i ) 如果a i x i = b 对应的约束条件为a i x i b i - 1j = l n 那么 a i x 1 ) b ( 2 ) i = i 同时由x ( 2 是可行点得 n y a i x1 2 b ( 3 ) 智一 而杰a ；x 。，- b 故宝a ；【濂 ，+ 0 一口) x 2 ) 】 兰a ；x 。， i ：1i = l i = l b = ba o +bn旺一 。 0 +味 磐酗 一+a2 西南交通大学硕士研究生学位论文第1 5 页 依照( i ) 可证得： a i o 【x l 。+ ( i - o o x 2 ) 】 a i x 0 ) i = li = l 由( i ) ，( i i ) 得 nn a i 【旺x ”+ ( 1 一a ) x 2 】a i x 们 i = li = l 这与假设所得( 1 ) 矛盾，即假设不成立，x t o 不能表示为可行域内两捃异点 x i ，x 1 2 的凸组合。 根据凸集顶点的定义可知：x 【o 为可行域的顶点。 推论1 如果l p 问题可行域的棱与其界面豹交点是可行点，那么这样 的点必是可行域的顶点( 即可行顶点) 。 推论2l p 问题的可行域的每条棱上至多有两个可行顶点。 推论3 过l p 问题的可行域的顶点至少有n 条棱。 附注：为了与可行顶点相区别，我们把l p 问题中n 个约束界面的唯一交点 称为由这n 个约束条件确定的一顶点。简称顶点，当然，如果此顶点的坐标 满足所有约束条件，它就是一个可行顶点。 引理若s 是有界凸集，则任何一点x s ，可表示为s 的顶点的t 凸组 合。 定理2 6 3 若可行域有界，l p 问题的目标函数一定可以在其可行域豹顶 点达到最优l ”l 。 需要指出的是，有时目标函数可能在多个顶点达到最优值，这对，在这 些顶点的凸组合上也必然达到最优值，称这种l p 问题有无穷多个最优解。 假设j ( ，j ( 2 1 ，受( ，是目标函数达到最大值的顶点，若文是这 些顶点的凸组合，即 kk i = 0 【i 囊( i ) ，心i o ，a i = 1 ) 于是 设 kk c 盘= c i 羽= a i ( c 囊( i ) ) i _ li = i c j ( ) = m ，( i = 1 ，2 ，k ) ：旺i m = m 。 吾 另外，若可行域为无界，则可能无最优解，若有也必定在某顶点上得到， 根据以上讨论，可以得到如下结论： l p 问题的所有可行解构成的集会( 可行域) 是凸集( 凸多面体) ，不管可行 域有界还是无界，它们均有有限个顶点；l p 问题中，如果系数行向量投性 独立的n 个约束条件的界面方程组有唯一可行解，那么此解对应可行域的一 个顶点：过可行域的顶点至少有n 条棱；若l p 问题有最优解，必可在某顶 点处达到等。在这些结论的基础上，下面让我们以e u c l i d 空间理论为背景， 以传统的代数方法为研究工具，渐进地介绍l p 问题又一种新的算法一点 一线一面”循环寻优法。 西南交通大学硕士研究生学位论文第17 页 第3 章l p 问题与“点一线一面”循环寻优法 3 1l p 问题的数学模型 l p 闯题做为一类优化问题，它们具有以下共同特征： ( 1 ) 每一个问题都用一组决策变量( x l ，x 2 ，x n ) 表示一方案，这组 决策变量的值就代表一个具体方案，一般这些变量取值是非负的； ( 2 ) 存在一定的约束条件，这些约束条件可以用一组线性等式或不等式时 来表示； ( 3 ) 都有一个要求达到的目标，它可以用决策变量的线性函数( 称为目标 函数) 来表示，按问题的不同，要求目标函数实现最大化或最小化。 满足以上三个条件的数学模型称为l p 问题的数学模型( 简称l p 模型) 其一般形式为 0 p t i m i z e z 2 c x s u b j e c t t o ( 3 2 ) ( 3 - 3 ) ( 3 一1 ) (m) 其中c = ( c l ，c 2 ，c 。) x = 【x 1 ，x 2 ，x n ) 1 ，a l ，a 2 是约束条 件的两个系数矩阵，b l ，b 2 是约束条件的常数项构成的两个列向量，并规定 b 】，b 2 0 。 在l p 模型中，方程( 3 - - 1 ) 称为目标函数；( 3 2 ) 、( 3 - - 3 ) 称为约束 条件，( 1 3 ) 也称为变量的非负条件。 3 2l p 问题的简单分类 基于研究问题的需要，我们可班根据约束条件的不同情况t 把l p 问题 分为三种类型： 1 内敛型，其基本模型为 o p t i m i z e z = c x 疗2 = b 且仁 0 ) ( i = l ， 西南交通大学硕士研究生学位论文第19 页 2 ，n ) 的可行解称为l p 问题的截距可行解。 3 l p 问题约束条件的界面组 定义3 3 3 把l p 问题的所有不等式约束转化为等式约束后所得的界 面簇( 丽) 叫做l p 问题约束条件的界面组，即 j a l x s b ll a l x = b l ( m ) a 2 x ( = ) b 2 = ( m ) a 2 x = b 2 卜i 0卜i = 0 约束条件约束条件的界面组 3 4 “点一线一面”循环寻优法 “点一线一面”循环寻优法与单纯形法在解题思想上有一个共同的特点 转移搜索。单纯形法是根据问题的标准从可行域中某个基可行解开始经 基变换转换到另一个基可