发布时间 : 星期四 文章线性规划问题更新完毕开始阅读e3c3d680b9d528ea81c77989
反向垂直，r{+l是n一m--k一l维最优集;若没有刚好反向垂直的，最优解一定在最 接近反向垂直的r:+l上达到(可参看图2.2)。
注3.若原始等式约束平面r‘，不空且目标函数在F。上有界，则由微分学可
知最优解一定在r‘，上达到。如果F‘，不是n一m维最优解集，定理3.9保证了可以由 r‘’出发，将逐维选优过程向前推进。而且由推论3.2，若rk是n一m一k维且e}共O， 中南大学硕士学往论文线性规划逐维选优强多项式解法27
则e}是F{‘，在r“上的内法向，取d’+1·e}，则r:‘，有一组非零正交法向量d;、一d.、 d，、?、d“、dk‘，，其中d，、?、dk、dk‘，是r{‘，的内法向，因而r{‘，是n一m一k一1维，也就
是说，我们在逐维选优过程中得到的不同维数的rk(1(k蕊n一m)的非零正交内法向 d’、?、dk恰恰是对应的坐标基向量的非零投影向量，当逐维选优过程向前推进时， 只是向其中再添加应用定理3.9新选中的坐标基向量的非零投影向量，也就是让 其对应的坐标超平面与当前等式约束平面的交是降了一维的新的当前等式约束平 面。
3 .
5完整的解题步骤
(1)计算r的基向量ej(1蕊j蕊n)、原点0和目标函数梯度c在r“上的投影和判 别数(eo)’
.
1将法向量组{a}、aZ、?、氏}正交化，取 dl=a‘
dZ=aZ一a百dldl/d{
命a。一a二d;d】/d}-一a万嵘.鲡/d 1
.
2计算Rn的基向量ej(l蕊j簇n)、原点O和目标函数梯度C在r“上的投影 及判别数
e
{=e厂(d.jd:/d{+dZjdZ/d; 石.=b，石，二bZ一a川.石:/dl
+’‘·+d:jdd
石。=b.一a二d:石./dl-一a二d一，瓦_./d几一 Ok=石.d，/dl+石，dZ/d;+.二+石 e‘，=e一艺eTd‘d*‘d 。d./d几 (e。)’=(e。)‘e 一二1 ·
3记e签‘0的下标集为Q，其基数为q。按定理3.6判定F‘，是否可行。若 不可行，无最优解，计算终止;否则进行步骤1.4。
1.4检查是否对所有i任Q有c)>0，若是，最优解无界，计算终止;否则进 中南大学硕士学位论文线性规划逐维选优强多项式解法28 行步骤(2)。
(2)k由O到n一In循环，求最优解集
2.1若(ck)乍。，rk是sLP的n一m一k维最优解集，定理3.6中的zk是其中一个 最优解，最优解集的正交内法向基也已求出，计算终止。
2 .
2对jeQ且e{蕊0计算sj=(e{)’/e氢，记max(sj)对应的下标集为S，其基 数为s。计算(ek)’=(ek)’一max(sj)。若(ek)’井O，转步骤2.4。
2 .
3若(ck)2=0，由于Fk上直线X二Ok+tck与i任S的坐标超平面二‘相交且对应 有t。=一。)/e梦，计算ti=一。{/e)(i任s)，设tj=min(ti)，则向j对应的低维平面 投影可保证投影点的坐标Xi)0对所有i任S成立。将1ES且i#j的下标从下 标集Q中删去。计算Ok=Ok一O{e{/e;和e卜e卜e:e{/e氢(i任Q，i护j)。按定 理3.6判定对应的新Fk是否可行，若可行，转步骤2.1;若不可行则因其子集也 一定不可行，将j从下标集Q中删去并转步骤2.4。 2
.
4按Sj(j任Q)由大到小的次序构成下标集T，逐个对jET计算 Ok=口一O{e{/e氢和e卜e卜e}e{/e氢(i任Q，‘共j)。按定理3.6判定对应的新 Fk是否可行，若不可行，将j从下标集Q中删去。若可行，仍记其对应的下标为 j，将j和其它有e:=0的下标i从下标集Q中删去并计算ck=ck一c{e{/e;和k=k+‘。 如果k 线性规划逐维选优直接算法采用法向消元和最小法向消元为工具，不但使逐 维选优寻求最优集的过程最多进行n一m次，而且可以几乎避免一切不必要的重复 或无功效的计算，这主要指: (l)按推论3.5，由向量的正交分解有向量vERn在Fk上的投影向量vk与e: 的内积简单地是取其对应坐标(vk)‘e{=(vk)下ej=v{，大量的内积乘法不用重复计 算。 (2)按定理3.4，由rk降维到F{+，时，e{+l=e卜e牛e{/e氢中有k+‘个分量为 零而且e{‘’一0和c:+l=0，大量的计算结果为零不用重复计算。 (3)由于不可行平面的低维子平面一定不可行，使得由n一m到0维，判定不 一 可行性最多做m次，大量的不可行性判定不用重复计算。 下述定理保证线性规划逐维选优直接算法是强多项式算法。 定理4.1线性规划逐维选优直接解法有小于O(mn3)的强多项式时间复杂 度。 证由于计算机乘除一次耗时比加减或其它基本运算一次高几个数量级，上 章线性规划逐维选优直接算法步骤(1)的主要计算量是a，、?、氏正交化的乘除法 次数，计算每个a丁djdj/d:(2毛i蕊m，l毛j延i一l)作3n+l次乘除法，a.、一、 正交化的乘除法次数是(3n+1)【1+2+?+(m一1)〕=m(m一)(3n+l)/2，m簇n，其时间 复杂度小于O(n3)。步骤(2)的主要计算量是基向量e，(1延i蕊n)在F‘，上的非零投 影向量e)再继续投影的乘除法次数。在r“上，由于e{+l=e卜e氢e{/。氢，注意到 e)+，有k+1个分量为零而不必计算，每个e)再投影一次所作乘除法次数是n一k， e，(1蕊i延n)在rk上的所有q个非零投影向量(e{+l=0不必计算)再投影一次所作 乘除法次数是(q一l)(n一k)，每投影一次，集Q的基数q至少减1，Fk是n一m一k维， 在rk上最多作n一m一k次投影，其乘除法次数不超过(q一1)(n一k)+(q一2)(n一k一1)+.二 中南大学硕士学位论文线性规划逐维选优强多项式解法30 +(q+m+k一n)(m+l)。基向量e。(1毛i蕊n)在r。上的非零投影向量最多n个，在rk 上的非零投影向量最多n一k个，由r”直接作n一m次降维得到SLP的孤立最优解或 判定F。的可行性都最多作(n一1)n+(n一2)(n一1)+?+m(m+1)二O(n，一耐)次乘除法，判 定每个r“的可行性最多作(n一卜r)(n一k)+(n一k一2)(n一k二l)+?+m(m+l)= O〔(n一k)’一m门次乘除法。若r‘，可行，由于它是n一m维，其上的r’至少有n一m个可 行，也就是最多有n一(n一m)=m个不可行。若降维到Fk(1延k成n--m)时己按定理3.6 判定过p次低维平面不可行但。k可行，则由于不可行平面的低维子平面一定不可 行，己至少从下标集Q中删去k+P个下标，厂k上的Fk‘，至少有n一m一k个可行即最 多n一(k+p)一(n一m一k)二m一p个不可行，也就是说，判定不可行性最多做m次，其时 间复杂度小于O〔m(岸一m3)]。因此，线性规划逐维选优直接解法的时间复杂度一 定小于O(m岸)，mn3是只与问题变量数目和约束条件数目有关的多项式，故线性 规划逐维选优解法有强多项式时间复杂度，而且最优解集的维数越高，时间复杂 度越低，与线性规划迭代解法形成鲜明对照。 注1 . 定理4.1的证明中，“不可行平面的低维子平面一定不可行”起了显 著的作用，虽然这是一个不争的事实，却常被人们所忘记。 注2.定理4.1计算的是求出全部最优解的集合的时间复杂度，而现行各种 迭代算法计算的是求出一个最优点的时间复杂度，所以按照定理4.1的结果进行 线性规划逐维选优强多项式算法和现行各种迭代算法的时间复杂度比较实际上 并不是公平的。 线性规划逐维选优强多项式算法的时间节省是十分显著的，且不说该法求出 的是全部最优解，即使对孤立最优解的情形，单纯形算法最坏情况与逐维选优强 多项式算法最坏情况的耗时比>mnZ”/mn:，=2n一2。若n=34，逐维选优直接算法最坏 情况已经比单纯形算法最坏情况至少快一千万倍;若n=72，单纯形法在最坏情 况的计算时间至少是逐维选优直接算法最坏情况的计算时间的258倍，也就是地 球现有寿命与半秒钟的时间之比;在n)1口时，单纯形算法最坏情况与逐维选 优算法最坏情况的耗时L匕>mnZ”/mn3=2，，，‘，(2’。)，/(10)8>2黔，。(一0，)3/(一。)8>2阴，，。 中南大学硕士学位论文线性规划逐维选优强多项式解法31 第五章逐维选优算法计算程序 5.1主程序流程图 开开始始 建立数组 A[l。，n]，B[，n]，C[n]，E[n]，D[]，O〔n]，e[n]，e[n]，Q[] 输入矩阵A，B，e，E 调用正交化子程序，得到r“，将产 生的正交法向量基存入存入数组D口 计算原点。，E，c在I’“上的投影 00，EO，eo，存入O[n]，E[n]，c[n] 调用可行性判断子程序 是否可行?N_!无最优解 最最优解为无穷大 中南大学硕士学位论文线性规划逐维选优强多项式解法32 判断是否为最 优解集? S=n，Q=0，P=O，L=m FORk=0ton一In P=O? Y 习、、FORj=1TOSSSSSFORj=1TOSSS 根根据e}护0，将其下标加入Q集集 NNNextjjjjjjjjjjjjjjjjjjjjj 不不不不不不不可行，终终 」」卜计算算 对对于j属于Q，且cj*毛0，计算sj一(cjt)2/eukkk 将将满足MAX(sj)的下标记为rrr ·· Nextjjj 调用可行性判断子程序判断坐标平面nr的可行性及统计S值 中南大学硕士学位论文线性规划逐维选优强多项式解法 今 是否可行?P=l Y亨 L=卜l;n(L卜e六rk”为rk与:r的交 计计算原点ok，Ek，ek在r.卜‘’上的投影。“’，E“’，e“’，， 存存入O[nl，E[n]，e[n]]] NNNEXTkkk 创创建数组下〔n一m一k，n]]] 将将剩余的坐标平面的法向量ek向r卜投影，得到T(i))) FFFORj=0toi一lll zzz=下(i)‘T(j))) NNNEXTjjj NNNEXTiii 将可行点Z“代入公式x=Z‘+人，T，+人2:2+??+人。一、:一，k， 利用Xi)0(1毛i延 N)，解出入。的范围 完成 中南大学硕士学位论文线性规划逐维选优强多项式解法34 5.2正交化子程序流程图