发布时间 : 星期四 文章线性规划问题更新完毕开始阅读
多面锥相交的界定平面上有该凸多面锥的界面。Rn中的凸多面锥的界面可以是 n一1维、n一2维、?、1维、O维，1维和0维界面常常称作凸多面锥的棱和顶点。 有些文献只把凸多面锥的n一l维界面称作它的界面，这样定义并不完整，不利于 进行一般情况的讨论。
注2.凸多面锥界面的切向和内法向
R”中的凸多面锥的n一k(1蕊k(n)维低维界面有n一k个线性无关的切向量， 但要完全确定该低维界面必须指定它的k个线性无关的内法向和界面上的一点。 特别地，对于凸多面锥的顶点，还必须指定它的n个线性无关的内法向。 三、若干基本术语和记号
1.由等式约束条件线性代数方程组Ax=b的解集构成的平面称为原始等式约 束平面，记作r。。A的m个线性无关行向量Schmidt正交化后得到 F。的一组正交法向基{dl、由、?、d洽。
2.记原始等式约束平面r。与k(O毛k蕊n一m)个Rn的坐标超平面二‘:xi=0 (1簇i蕊n)的交是rk。线性规划的逐维选优强多式算法就是最多n、次每次选出 一个坐标超平面，使得若线性规划问题有最优解，则最优解一定在选出的坐标超 平面与原始等式约束平面的交上达到。称每次选优前原始等式约束平面与已选出 的那些坐标超平面的交为当前等式约束平面。 3.记:k与坐标超平面二’的交是r尸。 4.记Rn的原点O在Fk上的投影为Ok。
5.记Rn的标准正交基向量ej(1毛j毛n)在rk上的投影向量为e{(1燕j簇n)， 中南大学硕士学位论文线性规划逐维选优强多项式解法巧
e全刘的下标集为Qk。下一节的推论3.2将证明，e}是Pk+l在Fk上的内法向。 6.记目标函数梯度c在rk上的投影向量为ck 3.2基础性的定理及公式 定义3.3称点
x’=x+(b一aTx)a/aZ(3.1)
为Rn中的点x到Rn中的超平面aTx=b上的投影;称 v，=a，va/a，(3.2)
为Rn中的向量v到Rn中的向量a上的投影向量;称 v‘=v一a万va;/a矛(3.3)
为向量v到Rn中的超平面二、:a丁x=b、上的投影向量.
定理3.IRn中的点和向量在Rn的低维平面上的投影与投影次序无关。 证向量v在超平面二，上的投影向量是vl二v一a万val/a}
aZ在超平面二，上的投影向量是alZ=aZ一a7aZal/a了(可参看图1) 超平面二2的法向量 因此，
a几v，=(aZ一a7aZa，/a})下(v一a7val/a了) 二a妙一a汤a卜/a矛一a冲a孙1/a了+a汤a冲a}/ =a卯一a扭Za万v/ar
a几=(aZ一a丁aZal/a:)’(aZ一a丁aZa，/al)
=a;一a卜Za歹al/a矛一a沁a万aZ/al+a冲Za万aZa:/ =a;一(a7az)’/a矛 (a矛a矛 (a厂a矛)
图3.1
于是向量v先向二:投影再向二，和二2的交二，2投影的投影向量是 v，2=v;一a》;a，2/a几
=v一a丁va，/a矛一(a歹v一a丁aZa丁v/a矛)(aZ一a了aZa，/al)/仁a;一(a丁aZ)’/al」 =v+{[(a丁aZ)2一a矛a;〕a丁v+(a}alv一a万aZa丁v)a了aZ}a，/{a{[a矛a; 一(a丁aZ)’〕}+(a丁aZa丁v一a:a百v)aZ/[a矛a:一(a丁aZ)’] 中南大学硕士学位论文线性规划逐维选优强多项式解法16
=V+〔(a7aZa卯一a:a7v)al+(a知a冲一a矛aiv)aZ〕/[ata:一(a沁)2」
注意到上式中下标1和2的对称性，可知交换投影次序即向量v先向二2投影再向 二12投影的投影向量vZ，与向量v先向二，投影再向:，2投影的投影向量vlZ相等: vZ;=vZ一a枷2a2，/a:，=v;2
由于以上推导与平面的交的维数无关，多次重复该推导，即得定理3.1。 注1.定理3.1是R3中著名的三垂线定理在Rn中的推广，三垂线定理关心的
是向量的垂直分量，定理3.1关心的是向量的切向分量，定理3.1保证了Rn中向 量到Rn的低维平面上的投影的唯一性，是Rn中一切与向量投影有关的运算和结果 正确的基础。
注2.由定理3.1，注意到Rn的n一k一1维平面是R“的n一k维平面上的超平面， 可以取自然顺序l、2、?、k，按投影公式(3.1)和(3.3)逐次计算r中的点和向量
到Rn中的超平面二l、Rn中的超平面二1和二2的交即Rn中的n一2维平面二12、?、Rn中的
超平面二，和二2直到二k的交即Rn中的n一k维平面二卜~k上的投影。于是，R”的超平面
二j:a了x=bj的法向量a;到卫，、“小一石·k上的投影向量al;、a二j、一al·kj以 及点P任Rn的相应投影P，、P“、?、P“可由递推公式 Pi=Pi一l+(bl--一i一砰、Pi一l)a卜了a乏、(1〔i蕊k)(3.4)
al. .
ij=al.~(i一l)j一a二lal.二(i一l)jal..丫a异，(1毛:蕊k)(3.5)
求出，式中b，?ij=b卜二(卜:)厂a二.、al?(卜l)jb，二i/a已‘*(1延i簇k)。
定理3.ZRn中的向量v在n一k维平面“，?k和它在Rn中的正交补兀亡、上的投 影向量是
v“=v一(v，dldLzd:+v’dZdZ/d圣+?+v下dkdk/d;)(3.6)
v匕=v，d:dl/d:+v，dZdZ/d;+?+v，dkdk/d:(3.7)
证任意向量v任r可分解为v=vk+v肚，其中vk是v在二卜一k上的投影向量， v匕是v在“亡_、上的投影向量，由于{d，、dZ、?、d*}是二六、的一组正交基，就有 式(3.6)和式(3.7)。
以下用aij记R”中的任意向量a*的第j个分量。
中南大学硕士学位论文线性规封逐维选优强多项式解法17
推论3.1点P任Rn与它到二，?k上的投影点Pk的连线和二卜~k垂直，于是二，，..k 的所有点中，投影点Pk到点P的距离最小。
证由式(3.4)，向量PkP是二，?，的法向量的线性组合因而与二卜一k垂直。
推论3.ZRn的n一k(1毛k延n)维平面二卜~、的k个线性无关的法向量a，、aZ、?、 a，作逐次投影得到的向量组{aL、alZ、?、al.~k}就是向量组{a;、灸、?、ak}的Sc腼idt 正交化:
d;=al
dZ=aZ一a互d，d，/d:=a，2
(3.8)
dx=ak一a万dldl/d:-一a二dk一八一l/d;_1二al.~k夕
因而也就是二卜~k在Rn中的正交补·二之*的一组正交基。若al、aZ、?、ak是内法向， 则d:、dZ、?、dk是二，一k的一组正交内法向。
证在式(3.5)中，让j分别为2、?、k并分别投影到“:·几2、一凡~·(k一l) 上，得到式(3.8)。按式(3.3)，平面二j:alx=bJ的内法向aJ向平面二，:a万x=b，投 影时不会穿过平面Jt、和平面二j，因而是它们的交二，j的内法向，逐次继续下去， 可知d;、dZ、?、dk是二卜一、的一组正交内法向。
注.推论3.2将逐次投影与SC恤id七正交化公式联系起来，代数的Sc腼idt 正交化公式因而有鲜活的几何图解，几何的逐次投影因而有简明的代数计算公 式。
推论3.3Rn的坐标基向量eJ在二卜~，和二之.，上的投影向量是 e卜ej一(d，jdl/d:+dZjdZ/d;+?+dkjdk/d;)(3.9) e{1·dLjd，/d:+dZjdZ/d;+?+dkjdk/d;(3.10)
推论3.4Rn的原点O在二卜一k上的投影是
ok=d万Okdl/d子+d百okdZ/d圣+?+d万okdk/d乏(3.11) 其中
d了O性bl
中南大学硕士学拉论文线性规划逐维选优强多项式解法18 dlo性bZ一a百d;d丁。分d子
d万ok=b二一a百d卜，d乙;ok/d是_l(3.12) 证由推论3.1，口与二;~.‘正交，由式(3.7)可得
ok=(ok)Td;d;/d子+(ok)TdZdZ/d圣+?+(ok)’dkdk/d是(3.13)
以(3.8)式代入并注意到Ok在二卜二‘上即(Ok)’ai=(ai)‘Ok=b，，得到式(3.11). 定理3.3Rn中的向量u和v在:，一k上的投影向量uk和vk的内积等于u和 vk的内积，也等于v和uk的内积。 证对向量u、v二R”，有u=uk+u匕和v=vk+v匕，注意到u匕与vk垂直和v址与 uk垂直，内积u‘vk=(uk+u匕)了vk=(uk)丁vk。
推论3.5向量vERn在二，一~k上的投影向量vk与Rn的坐标基向量ej在二、一 上的投影向量e{的内积简单地是其对应坐标:
(vk)，e:=(v“)Tej=v:(3.14)
推论3.6Rn的标准正交基向量ej(1蕊j蕊n)在:卜二k上的投影向量e{是“卜、 和坐标超平面“j的交兀梦+l在兀卜.k上的内法向，e览=(e:)Tej=(e{)Te卜(e{)’)0， e二=(e:)‘ei=(e{)下ej=e:。
定理3.4Rn中的n一k(l〔k蕊n)维平面二卜一k和坐标超平面二j的相关位置有
三种情形。若e七‘。，“，?k和“’相交;若e全·O且O{=0，兀卜一k在“j上;若e盗=0
且O{‘o，只卜.k和“’平行。“l一k和兀j交于兀{+l时，点”任Rn在二{+I上的投影是 p卜，·pk一p{e{/e盔(3·15) 坐标超平面川:xi=0的单位内法向e*在“:+l上的投影向量是 e梦+，=e卜e焦e:/e盗(3·16)
它是二{+l和二李+l的交在“l+l上的内法向。r中的任意向量c在“{+l上的投影向
量是
ek一ek一e:e:/e氢 证由于。鉴=(e})’，
(3.17)
ej=0就是ej在“卜.k上的投影向量e卜O即兀，一k和“j有
相同的法向量ej，此时若Ok的第j个坐标o:·0，孔卜*在下’上;若O梦‘0，维 中南大学硕士学位论文线性规划逐维选优强多项式解法19
数不高于“怕勺维数的低维平面“:?。和，j无公共点即平行。在e监共0时，直线 x=Ok+te{和xj=0有解t=一O{/e氢，即“卜·、和兀j相交于兀男，此时由定义3.2， 有式(3·‘5)、(3·‘6)和(3·17);由推论3·2，e{‘，是兀{‘，和“梦‘，的交在兀:+，上的 内法向。。
注1.由于Rn中的n一k(l延k簇n)维平面;:一、的维数一定不比坐标超平面:’
的维数高，Rn中JT一，和二j的相关位置不可能出现类似于R，中两条直线异面的情 况。
注2.定理3.4在线性规划逐维选优强多项式算法理论中起十分重要的作
用，它不但表明Rn中的n个坐标超平面可由条件e毛=0分成两大等价类，从而在 这两大等价类中再分别建立序结构，而且式(3.15)、(3.16)和(3.17)给出了线性 规划问题的所有起作用的量的简单明了的逐次降维计算公式，于是我们实际上已 经只要考虑由rk到rk“降一维中的选优和判定可行性的问题。 3.3主要的新工具
欲善其功，必先利其器。为了处理由rk到rk‘，降一维中的选优和判定可行性 的问题，我们要发展一些新的数学工具。 3.3.1法向消元法
定理3.SRn中的kxn(k毛n)行满秩线性方程组(Ll)的解(k个法向线性无关 超平面的交)
(LI)a丁x=b，(二t)
a百x=bZ(二2) a乙x=b，(二、)
与下列经法向消元得到的kxn行满秩线性代数方程组(L2)的解相同: 中南大学硕士学位论文线性规划逐维选优强多项式解法20 (LZ)d不x=石，
d丁x=石2
d石x·石、二bk一a贾d，石，/d}-一a石dk一玩_./d;_， 而且，R”的原点O到二，、:2、?、JTk的交上的投影 ok=石!d，/d{+石2dZ/d;+?+石kdk/d;
是方程组(Ll)的一个特解，行满秩线性代数方程组的上述法向消元解法与点和法 向量组的逐次投影等价. 证由线性无关法向量组{a，、aZ、?、a.}Schmidt正交化得到向量组{dl、 dZ、?、dk}: d:=al
.
dZ=aZ一a互d.d./d:
dk=ak一a二dld:/d}-一a泛d卜，dk一，/d:_l