（应用数学专业论文）运输问题的直接算法.pdf

摘要 运输问题是一类常见而又极其典型的线性规划问题 本文基于标准线性规划逐维选优强多项式算法的基本理论，结合运输问题模 型的特殊结构，提出了运输问题直接算法的基本定理和直接算法的一般步骤该 算法根据目标函数的梯度向量在可行域的低维界面上的投影，通过确定运输问题 在可行域上的低维等值界面，直接得出运输问题的最优解集 全文共有五章：第一章是绪论，简单介绍了线性规划与运输问题的起源、发 展，运输问题的传统理论及算法，算法复杂性分析等；第二章介绍了线性规划 强多项式直接算法的基本理论第三章主要是给出了运输问题直接算法的基本 定理和算法复杂性分析；第四章为运输问题的直接算法的算例，通过几个简单 实例说明了该算法的计算过程；第五章结束语 本人的所做的研究主要在第三章和第四章，它包括以下几个方面： ( 1 ) 利用投影矩阵简化了逐维选强多项式算法理论的表达 ( 2 ) 提出了运输问题直接算法的基本理论 ( 3 ) 给出了运输问题直接算法的一般步骤，进行了算法时间复杂性分析 ( 4 ) 对几个规模较小的运输问题，利用运输问题直接算法进行实际计算 对比求解运输问题最常用的表上作业法，该方法具有几何意义明确、计算过 程操作方便、且求解效率高等特点理论分析和大量的计算实例说明了直接算法 是种有效算法 从现有文献资料表明，运输问题的直接算法是首次提出；对比运输问题的主 要解法一一表上作业法，该算法求解效率更高，因而该算法具有十分重要的理论 意义和实际意义 关键词：线性规划、运输问题、强多项式算法、等值界面、最优解集 an e wa l g o r i t i l mo f d i r e c tm = e t h o df o r t ra n s p o r t a t i o np r o b l e m a b s t r a c t i nm i sp a p e r ，t b ea u t h o rp r e s e n t sad i r e c tm 就h o dt os 0 1 v e 扛a n s p o 删o n p r o m e m t h et r 锄s p o r t a t i o np r o b l e mi sal i n e a rp r 0 掣a i n m i i l gt h a ti sc o 衄o na n d c l a s s i c 1 1 1 i sp a p e ri sb a s e do nm eb a s i cm e 嘶e so fs 仃o n 9 1 yp o l y n o m i a la 1 9 嘶血m 南rt i l el i i l e a rp r o 掣a 玎：l 玎1 i n g ，卸dw eh a v ec o n s i d e r e de s p e c i a ls 拓【i c t i l r eo ft h e t a n s p o r t a d o np r o b 】e m ，m m u g h 也eg 础e mv e c t o rp r o j e c t 幻no ft h eo b j e c 6 v e 劬c t i o na r ec o m p u t e 正mt h er 瑚i b l er e 西o na ne q l l i l a c e m lf i a c e to fl o wd 曲e n s i o ni s e s t l b l i s h c df o rt r a s p o r t a t i o np r o b l e ma i l dt h eo p t i i n a ls o h l t i o i l so fs t p 咖b cf o u n d d i r e c t l y t h e 丘r s t c h 印t e p r 0 1 o m e n o n ，s i m p l y i i 】订o d u c e st h e p r o v e i l i e n c ea n d d e v e l o p m c n to fl i e a rp m 孕a 衄i i l ga 1 1 dt 瑚n s p o 僦i o np m b l e m 卸d 1 en c w e s t r 锚e a r c ho ft h ea j g o r i m m ，a 1 9 0 r i t l l mc o m p l e x 时a n a l y s i s t h es e c o n dc 壬l a p t e r ，、e i i 血o d u c et h eb a s i cm e o r i e so fs 仃o n g l yp o l y n o m i a la l g o 打t h mf o r l el i i l e a r p r o 伊孤岫g 1 h e 曲_ i r dc h a p t 郎 w ep r e s e mad i r e c tm e t l l o dt os o l v e 昀n s p o r t a t i o n p r o b l e m t h ef o u r d lc h a p t e rw ei n 们d u c ead i r e c ta l g o r i t h mf o rt r a n s p o n a t i o n p r o b l e ma n dm ea p 】i c 撕o no f 出ea l g o m m n ef i f i l lc h 印t e re n dw o r d s t h ed i s s e n a t i o nm 血l yf o l l rp a s t s ： 1 s 血p 】i 聊n gm es o m ef o r m u l a so fm es 仃o n g l yp 0 1 ) 哪m i a l 舢g 鲥1 1 1 i 玎f o r 血e l i n e a rp r o 留阳姗i n gb yp r c d e c t j o nm 瓶x 2 p r e s e i m n gt h eb 船i ct h e o d e so f d i i ；e c tm 吐h o dt os o l v e 缸蛆s p o 删o np r o b l e m 3 g i v i i 培t 1 1 eg b 印so fd i r e c t l e t h o dt 0s o l v e 咖s p 0 删o np r o b l e ma r l da c h i e v i g t b l ea l g o r i 山mc o 珊p l e x i 母a i l a 】，s i s 4 如衄) d u c i i l g 也ea p p i i 训o no f 也ea i g 嘶也m 、i ms o m ei n s t a i l c e t h e o r e t i c a l 锄_ a l y s i s 锄dc o m p m m o n a lp m c t i c eh a v es h o w e dt h a t 曲ed i r e c t 2 m e t h o di se s s e n t i a l l yd i f r e r e n tf r o mm et a b l ea l g o r i m mo f1 、r a n s p o 血m o np r o b l e m t h ea l g o r i t l l t no fd i r e c tm e t h o dh a sc l e a r e rg e o m e t r yr n e a n i n ga n ds i m p l ec a l c u l a t i o n c o l l r s ea 1 1 di ti sa ne m c i e n c ya l g o r i t h l no nt h e o 珥 k e y w o r d s ：s t r o n g i yp o i y n o m i a la l g o r i t h m ；e q u i i a t e r a lf a c e t ；o p t i m a i s o l u t i o n ；t r a n s p o n a t i o np m b l e m ； l i n e a rp r o g r a m m i n g 士壶盘生塑至焦查盘墨叠虽塑鱼直蕉墨盘 第一章绪论 1 1 线性规划和运输问题 从数学上说，线性规划的模型是一个特殊的条件极值：寻求一个线性函数在 满足一组线性不等式条件下的最大值或最小值1 9 3 9 年，前苏联数学家康托洛维 奇( k o n t c 粕v i c h ) 在解决工业生产组织和计划问题时，提出了类似线性规划的模 型，并给出了“解乘数法”的求解方法之后，陆续有人发现，有不少问题属于 求一个线性函数在某些线性约束下的最优化问题其中最经典的例子有 h i t c h c o c k ( 1 9 4 0 ) 和k o o p m a n “1 9 4 1 ) 独立地提出的运输问题和s t i g l 叫1 9 4 5 ) 的食 物配料问题等在美国，1 9 4 7 年丹切克( d a n t z i g ) 给出了线性规划一般问题的 数学描述，并独立地提出求解线性规划问题的单纯形方法1 9 5 2 年，线性规划 的问题首次在计算机上获得解决，用的是原始单纯形方法2 0 世纪6 0 年代，随 着计算机技术的进步，求解大规模线性规划问题的方法得到迅速发展，使得单纯 形方法及其变形卓有成效地解决了一个又一个的大型实际问题线性规划也开始 成为理论上逐步成熟的学科现在，线性规划已广泛用于国防、科技、经济、工 业、农业、环境工程、教育及社会科学中数学规划己成为世界上使用最广泛的 数学方法 1 9 7 5 年，k 舢t e m v i c h 和k o o p m a i l s ，由于他们在创建经济模型、经济理论以 及数理经济方法中所做出的贡献，获得了n o b e l 学奖金，其中也包括了在线性规 划中的卓越贡献 从数学上说，线性规划的理论和方法是线性不等式和凸多面体理论的更新和 发展凸多面体的三个基本概念是顶点、棱和边界面n 维空间中凸多面体的顶点 是n 个独立的边界面的交点；它的棱是n - 1 个独立的边界面的交在线性规划问 题中，不等式约束条件对应于凸多面体的边界面；用代数语言描述的基本允许解 和极方向，对应于凸多面体的顶点和棱的方向 线性规划的单纯形算法便是从凸多面体的一个顶点出发，沿着凸多面体的 士壹盘至塑至焦叠塞墨叠塑壅鱼直垫差鲎 棱，由一个顶点走到另一个顶点，不断改进目标函数值，最后走到了最优解 线性规划最早和最富有成果的应用之一就是把运输问题作为线性规划问题 来描述和求解运输问题最初是由h i t c h c o c k ( 1 9 4 1 ) 和k o o p m 趾“1 9 4 7 ) 独立提 出，后来由k 0 0 p m a i l s ( 1 9 4 9 ) 详细地加以讨论k o n 士e ：v i c h ( 1 9 5 8 ) 对运输问题 做了早期的研究 运输问题数学模型有自己的特性与简化的计算方法，对于工农业生产和政府 决策来说运输问题是一个重要的模型它的重要性也反映在可以把许多其它问题 从形式上变成运输问题这些问题包括分配问题、转运问题、合同裁决问题、伙 食承包商问题等运输问题还有很多的变形，例如有效性和需求问题、限容量运 输问题、广义运输问题、多目标运输问题等 1 2 运输问题的现行传统理论和算法 线性规划方法最早和最富有成果的应用之一就是把运输问题作为线性规划 问题来描述和求解，形成了运输问题的现行传统理论和算法，本文的工作是在这 些传统理论和算法的基础上进行和发展的，因此将有关结论用1 2 1 节、1 2 2 节 和1 2 3 节摘抄如下 1 2 1 平衡运输问题的数学模型 运输问题的一般提法是： 有m 个生产地4 ，4 ：，。，可供应某种物质，其产量分别为l ，口：，。，另 有挖个销售地目，垦，e ，其销售量分别为6 l ，6 ：，“，从4 到易运输单位物 资地运价为勺问应如何组织调运，要求总运费最小的调运方案 建立数学模型：设从4 到q 的发运量为工f ，那么，由于从4 运出的物资总 量应该不超过4 的产量q ，因此，吩应满足： z f q ，f 1 ，2 ，珊 = 】 2 土壹盘至塑圭至焦鱼圭墨整塑壅鱼童蕉差盘 同理，运到易的物资总量应该不少于哆的销量屯，所以，矗还应满足： 总运费为： x f 6 j ，= l ，2 ，一，九 j 爿 z = 勺而 j _ 1 = l 于是，可得到一般运输问题的数学模型如下： mn m i i l z = 白 ，_ 1j - l “矗q ，j _ 1 ，2 ，优 = 1 m 矗6 ，_ ，= l ，2 ，挖 x o ，f = l ，2 ，矾；，= 1 ，2 。一，玲 其中q 0 ( f = l ，2 ，肌) ，6 0 ( j = l ，2 ，h ) ， 卅 特别当q = 0 时，称为产销平衡运输问题，也简称运输问题，其数学 仁lj - 1 模型如下： m i n z = 岛矗 仁1j - j n = 口，f - 1 ，2 ，研 j = l 6 ，= 1 ，2 ，珂 。f o ，f2 1 ，2 ，一，研；_ ，21 ，2 ，玎 ( 1 2 ) 这是一个具有肛+ m 个等式约束，珑n 个变量的线性规划问题，自然可用单 纯形法进行求解 若记： x = k l工1 2 x l 。x 2 l3 吃 工2 h - x m lx _ 2 x 聊，r c = g 1 lc 1 2 c l 。c 2 lc 2 2 c 2 n c m lc 2 c 。y 生壹盘至塑生焦叠童墨堑鱼壅鱼直蕉墨量 爿= 0 1 lp 1 2- p l ，p 2 lp 2 2 p 2 。p 。lp 。2 p 册) 6 = ( 口。啦岛岛屯) 7 其中 q = l ， 其中 扛l j = l p f = 巳+ e p ，( f = l ，2 ，历；- ，= 1 ，2 ，一，h ) ， 为第k 个分量为l 的掰+ 胛维单位向量 模型( 1 2 ) 用矩阵形式表示为： m mc 了 s j 触= b x o 卸lx 1 2 而n 吃lx 2 2 x 2 h x 小lx 2 x 删 是一个( m + ) ( 肌n ) 型矩阵 1 2 2 运输问题数学模型的特性 ，z 行 ( 1 3 ) 由( 1 3 ) 可以看出，是一个结构特殊的稀疏矩阵，因此运输问题数学模型具 有以下特点： ( 1 ) 等式约束的系数矩阵也可表示为： = 日 0 o 墨 o0 l ，l ， o 0 e ，。 4 其中巨为元素全为1 的维行向量，即日= ( 11 1 ) ，l 为n 阶单位方阵 、。、，。一 n ( 2 ) 运输问题( 1 2 ) 存在最优解，当所有参数为整数时，运输问题( 1 2 ) 必 有最优整数解 ( 3 ) 运输问题( 1 2 ) 的约束矩阵4 的秩为( m + n 一1 ) ( 4 ) 爿的任一子方阵的行列式的值为1 或0 ( 5 ) 对于( 1 1 ) 给出的产销不平衡的运输问题，总可以通过把问题转化为 一个产销平衡的运输问题来求解 1 2 3 运输问题的算法 从理论上说来，线性规划的所有算法都可直接用于求解运输问题但要花费 大量的时间与计算费用因而结合运输问题数学模型自己的特性，人们得到了极 为丰富的求解运输问题的方法如d a n z j g 的表上作业法、我国运筹学者管梅谷 提出的图上作业法、f o r d 和f u l k e r s o n 的对偶方法、c l m r i l e s 和c o o p e r 的脚踏石 方法、网络方法、由g r i g o r i a d i s 和w 甜k e r 修改的r o s e n 的原始剖分规划、g a s s 的对偶形方法、m 吼k r ；e s 和e g e r v a r y 在运输问题上推广的匈牙利算法、h o f l h a l l 和m a r k o 嘶t z 的最短路径方法、l a g e m a n 的最短路径计算法的修改和推广、 w m i a m s 的分解算法以及b a l i n s k i 和g o m o r y 的原始匈牙利方法等等 在这些传统的求解运输问题的方法中，很难指出哪一种方法在计算时间上是 最有效的g l o v e r ( 1 9 7 4 ) 等对单纯形方法和一种网络方法做出试验后得出了上 述结论在有些情况下，由于问题的结构，某种方法可能比其它方法好例如， 当m 比n 小得多时，对于分配问题，虽然它们可以用运输方法来求解，但匈牙 利方法及其变形看来更有效这些方法基本上都是根据运输问题数学模型的特 殊结构，将各种已有的方法加以简化和改造，应用和推广到运输问题中其中最 有代表性和最常用的是d a n 五g 给出的表上作业法表上作业法的出发点是根据 运输问题的特殊结构，减少单纯形方法中每步迭代的计算量，但迭代次数和单纯 形方法完全相同表上作业法实质上还是一种单纯形方法 土壶太空塑至焦查圭墨堑塑墨鱼直蕉差造 1 3 算法时间复杂性分析 提高大规模最优化问题求解速度，也就是降低最优化算法的时间复杂度， 是人类信息时代的最优化学科前沿 1 3 1 多项式算法( p ) 与非定多项式算法0 巾) 从算法复杂性理论上来说，目前习惯将算法分为：多项式时问算法和非多项 式时间算法所谓多项式( 时间) 算法就是其计算时间( 量) ，作为输入数据量 ( 长) 的函数，有一个多项式作为上界一个算法的基本运算总次数( + 、一、 、和比较) 也可称为该算法的计算时间 这两种类型的算法在问题规模较小时，差别不明显；但在规模增加时，有很 大差别若一个多项式时间算法的基本运算总次数为2 ”甩2 ，而另一个非多项式 时间算法的计算次数为2 “当n = 1 0 时，多项式时间算法的计算次数是非多项式 时间算法的计算次数的1 0 2 倍但当n - 2 5 时，非多项式时间算法的计算次数上升 非常快，是多项式时间算法的计算次数的2 ”倍 一个有多项式时问算法的问题称为多项式时间可解问题，或者p 问题在组 合优化中并非都是p 问题，迄今为止，对许多的组合优化问题都没有找到求最优 解的多项式时间算法因此，比多项式问题更广泛的是一类是不知道是否为p 问 题的问题，即非定多项式( o n d e t e 珊硒s t i cp o i y n o m i a l ，简记n p ) 问题 1 9 7 2 年， i ( 1 e e 和m i n 哆发表了一个出乎人们意料之外的例子，说明了单 纯形方法的时间复杂度是指数阶的，其时间复杂度是o ( m n 2 n ) ，虽然单纯形方法 在实际应用中很有效，但从理论上来说，它不是一个好的算法从此，众多学者 开始了对线性规划问题及单纯形方法时间复杂度的研究一部分学者研究如何合 理的解释这一现象，b o r g 娴i r d t ( 1 9 8 2 ) 和s m a 域1 9 8 3 ) 的工作说明了单纯形方法 的平均运算次数是多项式级的；另一些学者则考虑线性规划问题是否存在多项式 时间的算法 第一个这样的算法是原苏联的数学家哈奇扬( k h a c b i y 姐) 于1 9 7 9 年提出的 6 士壹盘堂亟至焦叠圭墨叠鱼塑鱼直蕉差迭 椭球算法，其时间复杂度为0 ( 4 l 2 ) 椭球算法从理论上说是个重要的突破，因 为它提供了第一个多项式时间复杂度的方法，遗憾的是广泛的实际检验表明其计 算效果比单纯形方法差1 9 8 4 年，在美国贝尔实验室工作的印度学者k 釉a r k a r 提出另一种时间复杂度为o ( 0 l ) 的多项式算法，从理论上说，k a 皿a r k a r 算法的 阶比椭球算法有所降低，从实际效果来说也好得多，但是否胜过单纯形方法，目 前尚无定论但k 锄a r k a r 算法所提出的不沿多面体区域表面搜索前进，而是从 可行区域内部穿行到最优解的思想是很有意义的基于该思想，产生了很多 k 衄1 d 算法的新变种，如仿射均衡尺度法、内点障碍函数法等在一定的条 件下，它们也是多项式时间的算法但它们对k 锄a r k a r 算法并无本质改进椭 球算法和k 锄a r k a r 算法被誉为线性规划两次重大突破尽管线性规划多项式时 间算法的研究，己取得了很大的进展，但目前出现的各种迭代新算法尚难以完全 取代传统的单纯形法原因之一在于，它们在迭代中往往要解多个最小二乘问题 以及多次求逆矩阵，从而使计算量变的很大另外就是一些实际应用人员往往有 这样一种观念在起主导作用：无论算法的复杂性，不管解的效果如何，能找到 个算法或比较己有的各种算法求得一解即可 1 3 2 强多项式算法( s p ) 虽然线性规划的k h a c l l i y a n 椭球算法和k 锄a r k a r 内点算法理论上是多项 式时间算法，但它们提出后的长期计算实践表明它们常常比d a i l 五g 的单纯形法收 敛得更慢上世纪末，人们意识到应该寻求真正的快速算法 算法分析中，一个多项式算法，如果它的计算量只与问题的变量数目和条件 数目有关，则称其为强多项式算法c s p ) 或基于实数的多项式算法1 9 9 7 年6 月， 当代一流数学家s s m a l c 提出了1 8 个2 1 世纪的数学问题，其中第九个问题是“线 性规划问题”，即“是否存在基于实数的多项式算法来决定不等式线性系统血 6 的可行性”，也就是线性规划问题是否有强多项式算法线性规划的理论和算法 的改进已经成为人类进入2 l 世纪就亟待解决的重大问题迭代算法包括内点算 法、椭球算法、单纯形法以及它们的各种改进算法由于具有时间复杂度高和最优 解集结构不明两大缺陷，很难在解决这一重大问题上有所突破，线性规划的新的 非迭代算法的时代已经到来 士壹盘至塑星焦垒耋墨整塑墨鱼童垫墨鲎 由中国大陆湖湘数学学派创建的线性规划逐维选优新算法和新理论改变了 最优化学科的传统观念，着眼于求最优集，最优点只作为其特例零维最优集处 理；新算法和新理论改良了展优化学科的传统数学工具，提出行满秩线性代数方 程组的法向消元解法，指出它与点和法向量组的逐次投影等价，并进一步将其修 正为最小投影法，用来判定坐标超平面的低维子集的可行性；新算法和新理论通 过逐次投影在等式约束解集平面上建立序结构，逐维选优和判定可行性，使线性 规划单纯形迭代解法所进行的r n 空间中平面组合穷举的计算变成逐次降维的等 式约束平面上低维平面的形和位的判定的代数计算，得到了线性规划的低于 o ( m n 3 ) 的强多项式直接算法 本文在线性规划逐维选优直接算法及理论的基础上，提出了运输问题直接算 法的基本定理和直接算法的一般步骤对比求解运输问题最常用的表上作业法， 该方法具有几何意义明确、计算过程操作方便、求解效率很高等特点理论分析 和大量的计算实例说明了运输问题直接算法是一种比运输问题现有各种传统算 法有效得多的先进算法 士壹盘堂塑差焦叠童 墨鳌鱼壅鱼直接蔓蓝 第二章线性规划逐维选算法 的基本理论 线性规划的算法和理论是最优化学科的理论和实践基础本章主要简介中国 大陆湖湘数学学派创建的线性规划逐维选优新算法和新理论的基本结果 首先描述有关问题及术语、符号： 设有标准型线性规划问题s l p ： m a xf ( x ) = c 7 xc ，x r nc 0( 2 1 ) s t a x - ba r i ”b 0 r - 1 m nr a n k ( a ) = m( 2 2 ) x o ( 2 3 ) 其可行域是一个凸多面锥，即等式约束( 3 2 ) 规定的n - m 维平面卜。与非负约束 ( 2 3 ) 规定的n 个坐标超平面j ：x j = 1 j n ) 的内部的交 以下记1 恤与k ( o k n m ) 个坐标超平面的交是r k 、r k 与坐标超平面一的 交是r ：“、r n 的原点o 在r k 上的投影为0 。、r n 的标准正交基向量c j ( 1 j n ) 和 目标函数梯度c 在r k 上的投影向量为e ? ( 1 j n ) 和c 。若r 。上有点x o ，称r k 是可行的，由于s l p 的可行域连续，也就有r k 是s l p 的可行域的n 一1 k 维低维界 面；否则称r 2 是不可行的 2 1 法向消元和最小法向消元 定义2 1 1r n 中的不等式a t x b 规定a 为平面：a x = b 的内法向，凸域 d 、= ( x l a t x b 为的内部，凸域d f x i a k b 为n 的外部多个平面的内部的交称 作这多个平面的交的内部 特别地，r “中的超平面n 1 ：x 。= o 称作r n 的第i 个坐标超平面而不等式x 。o 规 9 士壹盘生塑圭堂焦叠主 墨量鱼壅鱼童蕉墨造 定标准正交基向量e 。为其内法向 定义2 1 2 称点x ，- x + ( b a t x ) a a 2 为r “中的点x 到r “中的超平面a t x - b 上 的投影；称向量v r _ a r v a a 2 为r n 中的向量v 到r n 中的向量a 上的投影向量；称 v 1 = v a j v a ，a 为向量v 到r n 中的超平面t ：a j x = b t 上的投影向量 定义2 1 3 称丁i 卜k _ ( x l a j x = b l ，a ：x = b k ，x r n ，l k n ，b 。如k r ，a 。、 a k r n 且线性无关) 为畔的n k ( 1 k n ) 维平面 由于r n 的n - k l 维平面是r n 的n _ k 维平面上的超平面，可以逐次按照定义 2 1 2 求出r n 中的点和向量到r n 中的超平面n 1 、r n 中的超平面n l 和n 2 的交即 r n 中的n 2 维平面1 2 、r n 中的超平面“1 和“2 直到“k 的交即r n 中的1 1 k 维平 面“卜k 上的投影 定理2 1 1r n 中的点和向量在r n 的低维平面上的投影与投影次序无关 定理2 1 2r “的超平面，：at x = b ，的法向量a ，到。、z 、。t 上的投影向 量a 。a 。：。、a 。，以及点p r n 的相应投影p 1 、p 2 、p 。可由递推公式 p 1 = p 。1 + ( b 。一a j ，p 1 ) a 。a ( 1 i k ) a 卜- i j = a 卜( 。厂a j i a l ( i 圳j a l ，a i ( 1 i k ) 求出，式中b 卜。= b 。- ( 1 - 1 ) ，一a j i a n ”- ) j b - 。a i ( 1 i k ) 推论2 1 2r 。的n k ( 1 k n ) 维n ，t 的k 个线性无关的法向量a 。、a z 、巩 作逐次投影得到的向量组 a 。、a 。：、a 。 就是向量组( a ，、如、a 。) 的s c h m i d t 正交化： d 。= a 。、 d 2 = a 2 一a ；d 。d ，d ；= a ，2 、 d k = a t a ! d d 。d ；_ - 一a ：d 卜- d 卜- d ：，= a 。t 因而也就是l 一。在f 中的正交补 的一组正交基若a 。、a 2 、a t 是内法向，则 d 1 、d ：、d 。是玑。的一组正交内法向 定理2 1 3r n 中的向量v 在n k 维平面n “和它在硭中的正交补。上的 1 0 主壹盘至塑生焦途塞墨垒塑墨鱼童蕉蔓鲎 投影向量是： v 。= v 一( v t d d ，df 十v d ：d 。d ；+ + v d k d 。di ) v 。= v q l d ，d f + v d 2 d 2 d ；+ + v 7 d k d k d ： 以下用a ；，记r “中的任意向量a ；的第j 个分量 推论2 1 3 群的坐标基向量e 。在n 。和n 。上的投影向量是 e ；= e j 一( d l j d t d + d z j d 2 d ；+ + d k j d t d ：) e 2 d - j d d + d 2 j d z d ；+ + d k ，d d ： 推论2 1 4r n 的原点0 在n 。上的投影是 o 。= d j 0 。d 。d + d j o 。d ：d ；+ + d ：o 。d d i 其中d j o 】c = b 。、d ；o k - b r a j d - d j o k d 、d ：o k _ b k - 一a ：d k - 。dt _ 。o “d2 - 1 推论2 1 4 r n 的标准正交基向量e l j n ) 在玑n 上的投影向量e ；是n 。 和坐标超平面n 的交n ：+ 在n 。上的内法向，且 e ；2 ( e ；) t e ，2 ( e ；) t e ；= ( e ) 2 o ，e ：= ( e j ) 1 e 。= ( e ? ) 7 e ，= e ： 定理2 1 4r n 中的n k ( 1 k n ) 维平面玑“和坐标超平面3 的相关位置有 三种情形若e ：o ，n t 和5 相交；若e ：= o 且o ；= o ，n “在上；若e ：= o 且 o ? 0 ，l m 和n3 平行n 。t 和n3 交于n ：+ 时，点p r n 在n p 上的投影是 p k + 1 = p 。一p ；e ；e ； 坐标超平面n 1 ：x 。= 0 的单位内法向e i 在n ，上的投影向量是 它是九y 和“，的交在n y 上的内法向甜中的任意向量c 在n y 上的投影向量是 c k + 1 毫c ：e ：，e ： 定理2 1 5r n 中的k x n 皿n ) 行满秩线性方程组的解o ( 个法向线性无关超 平面的交) 主壹盘生塑堂焦途童墨鳌塑塑鱼鱼整簋造 ( l 1 ) a j x = b l ( “1 )a ：x 2 b 2 ( “2 ) a ：x 2 b l 文“l ( ) 与下列经法向消元得到的k xn 行满秩线性代数方程组的解相同： ( l 2 ) d 孓【= = b l ；- ld ：x = ：b 2 一a j d l i d ；e d ：x 爿埝a ：d l i d ? 一a z d k _ l 瓦d b ；瓦 而且，行满秩线性代数方程组的上述法向消元解法与点和法向量组的逐次投影等 价 以上法向消元方法可以推广成下面的最小法向消元方法： 记e ：o 的下标集为q t ，其基数为q “设r 。是n 寸k 维，e ：0 的q k 个下标中 有r 个使0 为负在r 。上作逐次投影，记o k 和e ；在第i 次投影后的投影是0 1 和 e ? ，使e ：0 的下标集为q ：注意到相邻两次投影点的有向距离0 1 _ o ”1 = o j e j e ；， 其长度是oi ( e ；) “2 ，对所有j q ：的负坐标oj 令 o ：( e ：) 1 i n o j ( e ；) 1 。1 0 j 0 ，而对所有j q ：的非负坐标o j 令 s 产0 ；e ；= m i n ( o j e ；1 0 j 0 ，e ； 0 ，记s 。= 一o ：e ；若s 。 o ，无最优解，计算终止：否则进行步骤( 2 ) ( 2 ) k 由0 到n 1 i i 循环求最优解集 2 1 若( c 。) 2 = o ，r 。是s l p 的最优解集，定理2 2 4 中的z 。是其中一个最优解，计 算终止 2 2 对j q 且c ；o 计算s j _ ( c ；) 2 e ；，记m a x ( s 。) 对应的下标集为s ，其基数 为s 计算( c “) 毡( c ) 乙a 】【( s ，) 若( c 2 0 ，转步骤2 4 2 3 若( c “) 2 = 0 ，由于r 。上直线x = 0 。+ t c 。与i s 的坐标超平面1 相交且对应有 t 。= 一o ：c ，计算t 。一o ! c ? ( i s ) ，设t j = i n ( t t ) ，则向j 对应的低维平面投影可 保证投影点的坐标x 。0 对所有i s 成立将i s 且i j 的下标从下标集q 中 删去计算o = o l o j e ；e ；和e = e 一e ；e ；e ；( i q ，i j ) 按定理2 2 4 判定 对应的新r 。是否可行，若可行且有i 0 使c i o ，转步骤2 1 ：若不可行则因其子 集也一定不可行，将j 从下标集q 中删去并转步骤2 4 2 4 按s 。( j q ) 由大到小的次序构成下标集t ，逐个对j t 计算 o 。= o l o ：e ；e ：和e j 2e 一e ：e j e ；( i q ，i j ) 按定理2 2 4 判定对应的新r 。 是否可行，若不可行，将j 从下标集q 中删去若可行且有i q 使c o ，仍记其 对应的下标为j ，将j 和其它有e ：= o 的下标i 从下标集q 中删去并计算 c 睦c l c ；e ；e ：和k = k + l - 如果k n m ，转步骤2 2 否则s l p 没有最优解，计算终 止 按照以上步骤进行算法复杂性分析，有下列重要结论： 定理2 3 1线性规划逐维选优直接解法有小于0 ( m n 3 ) 的强多项式时间复杂 度 1 4 土壹盘至塑圭茎焦盘童墨鳌塑墨鱼直蕉差溘 第三章运输问题直接算法 运输问题有自己的特殊性，如何针对运输问题，研究出更有效的逐维选优算 法，本章在这方面做了一些尝试 3 1 逐维选优算法的矩阵表示 注意到线性规划逐维选优算法的主要计算过程，只与线性方程组、向量投影 有关因此，我们可以利用矩阵来表达，使得主要计算过程系统化一些相应的 主要定理也从矩阵形式上给出了新的证明并得到了投影矩阵的一个新结果( 定 理3 1 4 ) 3 1 1 投影矩阵 定义3 1 1 设p 为n 阶方阵，若p = p 7 且p 2 = p ，则称p 为投影矩阵 显然，若0 为力矩阵，秩为m ，令 日= 7 ( 朋7 ) 。1 4 及 p = ，一爿7 ( 4 爿7 ) _ 1 爿 则p 和日均为投影矩阵 定义3 1 2 对于任意的秩为m 的m x 甩矩阵4 ，称 日= 7 ( 删7 ) 。彳 与 p = 一7 ( 4 彳7 ) - 1 为投影矩阵偶 投影矩阵具有下列性质： 性质l 若p 为投影矩阵，则p 为半正定矩阵 性质2p 为投影矩阵的充要条件是h = j p 为投影矩阵 性质3 设p 是n 阶投影矩阵，且日= ，一p ，则 土壹盘至塑圭至焦逢主墨叠塑墨鱼直蕉墨渣 上= p x 卜r “ 与 p = 妇水r ” 是正交线性子空间，三是玎堋维，r 是m 维且任一z r ”可唯一分解成 x = 材+ k “三，1 ，e r 从投影矩阵偶的定义可得：对任一z 月“，必满足 ( a ) = o ，工= a + 溉 由投影矩阵的性质可得下列定理： 定理3 1 1 设n - m 的维平面石= 扛i 血= 6 ，工且”，6 r ”，m 庸( 彳) = 埘 ， 且h = 4 7 ( 删7 ) _ 1 4 ，尸= ，一4 7 ( 埘7 ) 。4 ：则任一向量v r ”在石上的投影 为：v = p ，在石的正交补上的投影为：v “= 协 证明：设v r ”，v = v + v “，因为v 在平面，r 上，所以 爿v = o 而v “与平面万垂直，可设v “= 7 y ，y r ” 于是有 4 v = 一v + 一v 1 = 4 4 7 y 因为r ( 爿) = 川，所以似7 可逆 则 j ，= ( 删7 ) 。1 彳v 故 v 1 = 爿7 ( 倒7 ) 一1 4 1 ，= 协，v = u 一忉1 = p ， 证毕 特别地，v 为r “的标准正交基e j ( 1 ，n ) ，e ：= n e 1 = 胁， 因此有： p = ( ，e ：，e ：) ，日= ( e ：1 ，e ：1 ，p ：1 ) 1 6 壹盘至塑至焦查塞 墨叠塑墨鱼童蕉篷垦：一 定理3 1 2 任一点z r 4 在石上的投影为x = 工+ 4 7 ( 州7 ) - 1 一删 证明记p = 搿7 ，由于p v = 0 ，即有v = 7 ( 朋7 ) 。一v 于是 x 一x = 4 7 ( a 4 7 ) _ 1 一( x 一力， 注意到血= 6 ，因此有 一= x + 4 7 ( 4 a r ) - 1 ( 6 4 功 = a + 4 7 ( 州7 ) 1 6 证毕 定理3 1 3 设向量“，v 在，上的投影分别是“，v ； 贝日 “7 7 v = 嚣7 v = “7 v 证明：设= 砌，v = 则“v = ( p 甜) 7 p v = ”7 p p v = 甜7 p 2 1 ，= ”7 v 证完 特别地：v = e 时，“7 p ：= “：；“= v = g ，时，e ：= 0 ：) 2 o - 定理3 1 4 对任给的m 刀矩阵4 ，打矩阵e ， 且矩阵丑= 豳的秩为m + f ，只小以。1 4 冉， 且r a n k ( e ) 乇p = 一矸( 巨矸) 1 e ， 则有 p 8 = p a p = p p = p + p i 证明：先证只p = 喝= 只+ 尸一， 因为只，尸是投影矩阵，e 7 = 只e 7 所以爿印= o ，巨4 7 = o ，显然有巴p = 喝= 只+ p 一， 再证最= 只p = 玛= 巴+ p 一，只需验证： 对任一z r “，b ( 只= 0 ，或者曰“只十尸一) x ) = o 士壹盘至塑至焦叠圭墨叠塑塑鱼童垫差渣 注意到：五= 肼。+ 玛，爿矸= d ，e = e 匕，皿j = 巨矸 于是有 睨趔w 柚一c 叫私啪。1 巨