线性规划问题

线性规划问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 分类号 UDC .门-~.........-网‘一一‘.-........ 密级 编号 ..‘..，....口.侧卜......叫口.....勺.曰.，.，.......匕勺， 中.菊大净 CENTRALSOUTHUNIVERSITY 硕士学位论文 论文题目线性规划逐维选优 强，..项式解诊 _. 学科、专业应用数学 研究生妓名 导师姓名及 专业技术职务 彭猛 彭岳林教授 中南大学硕士学位论文线性规划逐维选优强多项式解法 摘要 随着现代科学技术的迅猛发展，最优化理论得到了越来越广泛的应用，同时 对其理论发展也提出了新的要求。 最优化学科的基础是线性规划。然而，实际计算和理论分析 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 明，当决策变 量数目猛烈增大时，目前广泛使用的线性规划的各种迭代算法都存在严重缺陷。 因此，进一步改进和完善线性规划的算法，努力降低计算的时间复杂度和提高对 最优解集的完整描述，具有十分重要的理论意义和实践意义。 通过对低维空间线性规划问题进行分析及研究，我们提取出其中具有普遍性 的规律，并将其向高维空间进行推广，研究出了一种新的算法一逐维选优直接 算法，以强多项式时间复杂度求出线性规划问题的结构清晰的全部最优解的集合 为目的。 此解法以逐次投影为手段，首先将线性代数方程组Ax=b进行法向消元，然 后将各个坐标超平面的法向量向其投影，并按其空间几何位置建立序结构，通过 逐维选优求出线性规划问题的最优解集，其算法为时间复杂度低于O(mn3)的强多 项式算法。 线性规划逐维选优强多项式解法己经形成一套完整的理论和成熟的算法，我 在其中做的工作主要是: 1.从线性规划实际工程应用的角度出发，提出线性规划的理论研究和算法 设计需要注重关心最优化问题的最优解集而不只是问题的一个最优解; 2.线性规划逐维选优强多项式解法刚开始形成时，判定原始等式约束平面 与若干坐标超平面的交不可行是一直投影到零维平面即一个点，我从二维平面的 特例情况出发提出只要在每降一维时考查那些投影向量是零的坐标基向量对应 的坐标超平面即可; 3.提出和实现了计算有关参数以用最优解集平面的切向基的线性组合明显 表示最优解集各点; 中南大学硕士学位抢文线性规划逐维选优强多项式解法2 4.设计了线性规划逐维选优强多项式算法程序流程图和主要模块的程序代 码，编制了线性规划逐维选优强多项式算法程序并以此计算了若干实例。 关键词:线性规划;最优解集;法向消元;逐次投影;序结构;强多项式 算法 中南大学硕士学位论文线性规划逐维选优强多项式解法 StronglyPolynomialAlgorithmforLinearProgramming Abstraet:InthisPaperanormaldirectioneliminationProeessand aminimalnormaldireetioneliminationProeessforsolvingsimu1taneous algebraieequationshavebeenadvaneedWhich15equivalenttosueeessive ProjeetionsofPointandno二alvectorsofPlanes.Basedonitanorder eons加etionontheequalityeonstraintPlanehasbeenestablished50that weeangetanewtheoryandstronglyPolynomialalgorlthmwith eo娜lexi妙les。小ano(mn3)todireetxyeo呷ut。all‘optimaltsolutionsofa linearProgranuningProblem. Myworksareasfollowing: 1.BasedonmyengineeringeXPerienee1suggestedthattheoryand algorithmofOPtimizationshouldPayagooddealofattentiontothe oPtimalsolutionsetbutnottoonlyanindividualoPtimalsolution. 2.1suggestedthatwhenjudgeWhetheran一m一k(0(k延n一m) dimensionalPlaneinRn15nonfeasibleit15enoughtodoProjeetionoften oulysometimesgreatlylessthann一mbyexaminationofonlythose coordinatehyPerplaneswithzeroProjeetionveetorofeorresPonding eoordinateveetorbutnotneedProjeetfinallytoaPoint. 3.1gotthemethodtoeXPressanyPointintheoPtimalsetbythe tangentbasisoftheset. 4.1desighedthefiowdiagramandtheeomPuteProgrambyitl eomPutedsomeexamPles. Keywords:LinearProgramming，OrdereonstrUetion，Directmethod，StronglyPolynomialalgorithm， SetofoPtimalsolutions. MR(1991)SubjeetClassifieation:90C05，gOC6O，68Q25 ChineseLibraryClassifieation:0221.1，0184，TP3OI.6 中南大学硕士学位伦文线性规划逐维选优强多项式解法4 目录 工贸企业有限空间作业目录特种设备作业人员作业种类与目录特种设备作业人员目录1类医疗器械目录高值医用耗材参考目录 中文摘要 英文摘要 第一章关于最优化传统理论的回顾与总结?????????????????????????????„„5 第二章新算法的设想?????????????????????????????.??...?....................„„ 2.1低维空间给我们的启迪???????????????„„，??.....................„„7 2 . 2基于逐维选优算法的设想??????????.???...........„„，..........„„9 第三章新理论的构成???4???????????????????????，???????????????????????????„„13 3 . 1相关定义??????????????????????????????????????????????????????..???..„„13 ,勺9，.人，.13.2 3.3 基础性的定理及公式 主要的新工具???„„ 3 . 3.1法向消元法???????????????????....?............................„„19 3.3.2最小投影法?????????????????????„„，„，.„，..............„„21 3.4主要的判据?????????????????????????????????????????????????????????„„23 3.4.1确定坐标超平面与等式约束平面相交的判据??????????„„23 3.4.2rk是否可行的判据??????????????????????????????????????????„„24 3.4.3r“上目标函数是否有界的判据???????????????????????????„„24 3.4.4rk和r尸是否最优集的判据???????????????????????，?????一25 3.4.5最优解一定在低一维的F{+1上达到的判据?????????????„„25 3.5完整的解题步骤???????????????????????????????????????????????„„27 第四章逐维选优算法的时间复杂度?????????????????????????????????????„„29 第五章逐维选优算法计算程序????????????????????????，??????????????????„„1 5.1主程序流程图???????????????????‘????????????????????????????，，????„„31 5 . 2正交化子程序流程图?????????????????????????????????????????????„„34 5.3可行性判断子程序流程图???????????????........................„„35 5.4主程序代码??????????????????????????.?....?.............„„，....„„39 5.5函数及子程序程序代码???????????????????????????????????..???..„„40 第六章计算样例?????????????????????，??，，?????????????????????..............„„44 致 谢?????????????????????????????????????????„„:?????????????????????????????? ????„„47 参考文献?????????????????????????????????????????????????????...........?...........„„48 中南大学硕士学往论文线性规划逐维选优强多项式解法5 第一章关于最优化传统理论的回顾与 总结 线性规划的模型是1939提出的。任何线性规划问题均可化成下列 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 型线性 规划问题SLP: maxf(x)=eTxe，x任Rne#O 5.t.Ax=bAeR”nb#0任R’l延m 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 。 1997年6月，因证明维数n)5的广义Poincare猜想而获Fields奖并在若 干其它数学领域颇有建树的当代一流数学家5.Smale提出了18个21世纪的数学 问题，其中第九题就是“线性规划问题”，即“是否存在基于实数的多项式算法 来决定不等式线性系统Ax)b的可行性?”人们逐渐意识到，应该努力寻求计算 时间只与问题变量数目和约束条件数目有关的多项式算法(称作强多项式算法或 基于实数的多项式算法)，创建线性规划强多项式算法及其理论成为人类信息时 代亚待解决的重大科学技术问题。迭代算法包括内点算法、椭球算法、单纯形法 以及它们的各种改进算法由于具有时间复杂度高和最优解集结构不明两大缺陷， 很难在解决这一重大问题上有所突破，因此我们需要寻找全新的非迭代算法的线 性规划解法。 中南大学硕士学位论文线性规划逐维选优强多项式解法7 第二章新算法的设想 2 . 1低维空间给我们的启迪 由于对于高维空间的分析缺乏直观性，我们先从最常见的低维空间入手，进 行分析和研究，找出其中的规律来。通过对二维和三维空间线性规划问题的考查， 我们发现在处理此类低维的最优化问题时，我们都可以不是采用纯代数的迭代解 法，而可以用图象很清晰的几何方法进行处理。 在二维空间，假设存在如下线性规划问题: maxf(x)=elxl+eZxZ 5.t.a、lxl+a;2x2=b: x;)0 xZ)0 我们可以采取如下方法求解:通过作图，首先画出各个方程所代表的直线，然后 根据其几何位置判断出最优点A为直线L:a;:x，+a12xZ=b;和xZ轴的交点，将其求 出并代入f(x)=c、x、+c2x2就可以求出最优目标函数值。 在此过程中，我们在判断最优点为凰2时.实际上是利用了目标函数梯度C的正交分 解，将C投影到直线L上，有C二C，+C2，由直线L上C‘的方向就可以判断出最优 解是直线L与坐标轴xZ即直线x;=0的交点A。明显地，如果目标函数梯度C在直 中南大学硕士学位论文线性规划逐维选优强多项式解法8 线L上的投影向量CL=0，直线L是一维最优解集。 再看三维空间，假设存在如下线性规划问题 毗xf(x)=elx，+eZxZ+e3x3 5.t.al:x;+a12x2+al3x3=bl aZlxl+a22x2+a23x3=bZ xl)0 xZ)0 x3)0 同样，通过作图我们也可直接判断出实际存在的某一维数的最优解集并将其 通过直接计算求出。与二维空间解法类似，设直线L是 a;lx:+aLZxZ+al3x3=bl a21xl+a22x2+a23x3=bZ 的公共解，将目标函数梯度C向其投影，在下图图左的情形，点A是零维最优解 集，目标函数梯度C在点A上的投影向量为零，可以通过正交化产生它的三个线 性无关的法向量;在下图图右的情形，目标函数梯度C在直线L上的投影向量为 零，直线L是一维最优解集，可以通过正交化产生它的两个线性无关的法向量。 虽然在二维或三维情况谈到确定最优解集的二个或三个相互正交的线性无关法 向量和考查目标函数梯度C在最优解集上的投影向量为零的事实没有很大必要， 一般情况下我们都不会这样做，但是对于更高维的情况，要确定最优解集的线性 无关法向量和考查目标函数梯度C在低维平面上的投影向量是否为零就是完全 不同的关键所在了，这在后面我们会详细讨论。 若如下图图右，目标函数梯度C在直线L上的投影向量为零，则说明L与第 一象限的交就是最优解集，剩下的工作就是对其进行判断，看它是否穿过第一象 限，这可以通过判断直线L上是否存在某一点x的所有坐标满足x，)O来进行。 若如上图图左，目标函数梯度C在直线L上的投影向量不为零，则说明L与第一 象限的交不是最优解集，下一步的工作是继续进行向更低维的平面投影，直到出 中南大学硕士学位论文线性规划逐维选优强多项式解法9 现目标函数梯度C在低维平面上的投影向量为零的情形。由于向量在零维平面即 一点上的投影向量总为零，对于一般的n维高维空间的线性规划问题SLP，这种 逐维降维进行投影的工作最多做n次。 为为 卒木、 右 “ 舀筹冬 一xl一xl 图2.2 我们再回过头来对单纯形迭代解法进行分析，与上述几何求解方法比较就会 发现它们二者的不同之处在于单纯形法是通过对坐标超平面上的极点进行搜索 而得到最优点，在搜索过程中实际上是以极点的函数值作为判断的依据，这样对 于存在多个极点的坐标超平面，一般情况会出现在该坐标超平面多次甚至重复搜 索的状况。而从几何解法可以看出，如果我们对坐标超平面按照其与可行域的交 的几何位置进行排序，然后依此顺序逐个进行搜索，对于已经查找过的坐标超平 面就不会再进行重复搜索，于是可以大大减少运算的次数，实现基于强多项式时 间复杂度的算法。 2.2基于逐维选优算法的设想 2.2.1目标分解 为了实现线性规划基于逐维选优算法的设想，我们首先分析线性规划问题最 优集的构成，它由两部分凸集的交构成，一部分是由代数方程组Ax=b的解集构 成的n一m维原始等式约束平面，另一部分是所有坐标xi)O(1簇i簇n)的点集即n 维空间的第一象限，而n维空间的第一象限的n个边界是n个n一1维的坐标超平 中南大学硕士学位抢文线性规划逐维选优强多项式解法10 面:、:xi二O的非负部分。由于问题的线性，如果线性规划问题存在最优解集，则 最优解集一定是n一m维原始等式约束平面与若干个坐标超平面的非负部分的交。 所以，我们可以断定线性规划问题最优解集是n维空间的一个低维平面r(在此， 我们把直线和点都看成低维平面的特例)的非负部分。为了明确描述n维空间的 一个低维平面P的非负部分，我们必须引入平面的内部和平面的内法向的定义。 定义2.1称Rn的凸域DI={Xla仪)b}为平面aTx=b的内部，a为平面犷x=b的 内法向，Rn一D，为扩x=b的外部。多个平面的内部的交为这多个平面的交的内部。 于是，利用法向基和切向基互补的性质，为了确定n维空间中一个k(k成n) 维的低维平面的非负部分，我们只需要确定它的一组k个线性无关的内法向量构 成的内法向基以及在此平面上的一个可行点即其所有坐标x;)0(1毛i簇n)的点 即可。这样也就可以接着求出n一k个切向量构成的切向基并用它们和求出的可行 点直接表出线性规划问题最优集上的所有点。 至此，我们明确了实现线性规划基于逐维选优算法的关键，是寻找出最优解 集的一组内法向基和最优集上的一个可行点。 2.2.2初步设想 我们把由Ax=b确定的原始等式约束平面记作FO，f’“与某个坐标超平面:‘: xj=0(1毛i延n)相交时，其交记作F:。F。与k(o毛k蕊n一m)个坐标超平面的交是 。k、Fk与坐标超平面二j的交是r尸、Rn的原点。在Fk上的投影为O众、Rn的标准正 交基向量ej(1簇j成n)和目标函数梯度c在rk上的投影向量为e}(1簇j毛n)和ck. 若r“上有点x)O，称I’*是可行的，由于SLP的可行域连续，也就有rk是SLP的可行 域的n一m--k维低维界面;否则称rk是不可行的.明显地，当点x在Fk上移动时，当 且仅当它穿过Fk与坐标超平面二‘的交时，其坐标x，才改变正负号。 在线性规划逐维选优算法中，确定当前可行低维平面rk与坐标超平面:‘的 位置关系是其核心问题之一。由于rk是维数比坐标超平面二‘的维数要小的低维 平面，它们之间的位置关系总共只有三种状态。 (1)Fk与二’平行 中南大学硕士学位伦文线性规划逐维选优强多项式解法11 当rk有法向量与二‘的法向量相同且它们没有公共点时，rk与二‘平行。此 时若rk在所有坐标超平面二‘(1延i蕊n)的内部，Fk的内部可行;若Fk在某一个 坐标超平面二‘的外部，r“的内部不可行。 (2)Fk在二‘上 当rk有法向量与二‘的法向量相同且它们有公共点时，rk在二‘上。此时r“ 与二‘的交的可行性与Fk的可行性相同。 (3)rk在二‘相交 当Fk的所有法向量都与二‘的法向量不同时，Fk与:‘相交。此时若rk可行， 则Fk与二‘的交r梦+l又存在两种状态。 (3 . 1)rk与二‘的交F黔中存在可行点，这说明F)+1可行，r尸上还具 有存在最优解的可能性，若rk不是最优解集，可以降维到F梦+l上继续逐维选优。 (3 . 2):k与二‘的交F全+l中不存在可行点，这说明F梦+l不可行，F)+l上 不可能存在最优解，若Fk不是最优解集，应该降维到别的存在可行点的r{+1上 继续逐维选优。 若rk可行且己经判定最优解在Fk上达到，但Fk不是最优解集，其上可行 的r}+1可能有多个，应该降维到哪一个F{+l上继续逐维选优呢?我们可以仍然由 二维情况得到启发。 rk+l J rk+l J 口 沙、ej讯人lleseses C k.几l W下e爪人lleewewe ‘爪 C 图2‘3 上图图左中可行域的边界面r{+1在rk上的内法向e:与rk上的梯度ck反 向垂直，因而P尸是最优解集;上图图右中可行域的所有边界面中没有一个的内 法向与ck反向垂直，但一定有某一r州在Fk上的内法向e{与ck最接近反向垂 直，因而最优解不论其是否有界都一定在F{+l上达到。“r{+l在Fk上的内法向 中南大学硕士学位论文线性规划逐维选优强多项式解法12 e :与Ck最接近反向垂直”就是计及正负号时rk上。k与所有非零的e梦的夹角中 ck与e:的夹角最小。 由此我们可以写出基本的解题步骤。 (i)对于犷x=b的处理:利用Sc腼idt正交化求出原始等式约束平面 r。的m个法向量构成的法向基并由它求出原点O在r。上的投影。 (11)对于x)0的处理:将n个坐标基向量ei(1毛i共n)投影到P“，记其投 影向量为ei0。由于F。有法向量与二‘的法向量相同等价于ei。=0，可以判断出n 个坐标超平面二’(1毛i毛n)与r。的几何位置。首先判断F。是否可行，如果可行， 将目标函数梯度C投影到r“上，记其投影向量为C0。然后将与F“相交也就是ei0 护O对应的坐标超平面(假设其个数为q)按C0与e，”夹角计及正负号由小到大排 序。 _ (111)按所排次序逐个判断对应的r‘是否可行，对第一个可行的F’继续判 断F‘是否为最优解集，若是最优解集，计算终止，若不是最优解集，进行投影 降维到该厂’，用它取代ro继续逐维选优，直到求出最优解集或确定最优解无界。 (iv)若求出了n一m一k维的最优解集rk，则同时可以确定它的k个相互正交 的法向量及原点在Fk上的投影Zk，利用这k个正交法向量可以确定rk的n一In--k 个线性无关的切向量(::，下2，„，T。~) (v)最优解集Fk中的任何点都可用x=zk十入;!，十入2TZ+.二十人n~kTn~k表出， 其中n一In--k个参数人i的变化范围可由对应的n一二k个独立的xi多0确定。 中南大学硕士学位论文线性规划逐维选优强多项式解法13 第三章新理论的构成 3.1相关定义 新算法的解题步骤明确后，为了从数学上进一步明确地描述和准确地展开讨 论，需要先给出如下一些定义。 一、低维有向平面 定义3.1称卫，„k={xla丁x=b:，a百x=bZ，„，a万x==bk，xERn，1蕊k簇n，bl、 aZ、„、akER“且线性无关}为Rn的n一k(1毛k毛n)维平面。 bZ、„、bkER，aL、 注1.低维有向平面的基本构成 二卜~k有k个线性无关的法向量a，、„、ak和n一k个线性无关的切向量 e犷、„、e:_、。并且这k个法向量的任意线性组合人;al十„十人ka、都是平面二卜二 的法向量，它们一起构成了平面二，一k在Rn中的正交补二八。 注2.低维平面的切向确定 平面二卜一，上的任意一点Pk和二，一、的n一k个切向量的线性组合x=Pk十 巧e卜?‘’十汽一ke;‘构成了该n一k维平面。明显地，切向确定的办法不能描述低维 有向平面的方向。 注3.低维有向平面的法向确定 如果我们规定a，、„、氏为平面二卜~、的内法向，则得到的是Rn的一个 n一k维有向平面，可以认为n一k维有向平面就是平面:卜一、及它的k个线性无关的 内法向共同构成的。 注4.Rn中的0维有向平面 特别地，Rn中的O维有向平面由Rn中的某一点和它的n个线性无关内法 向共同构成。 二、凸多面锥 中南大学硕士学往论文线性规划逐维选优强多项式解法14 定义3.ZRn中k(k)n)个含n个线性无关法向量的超平面的内部的交称作 Rn中的凸多面锥，这些超平面称作该凸多面锥的界定平面，界定平面与凸多面锥 的交称作该凸多面锥的界面。凸多面锥的若干界面的交称作该凸多面锥的一个低 维界面，两个相交的维数相同的低维界面互为邻接界面。 注1.凸多面锥的界面的基本构成 Rn中的凸多面锥的界定平面不一定是该凸多面锥的界面，只有那些与凸 多面锥相交的界定平面上有该凸多面锥的界面。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的一组正交内法向。 、„、k并分别投影到“:?几2、一凡~?(k一l) 证在式(3.5)中，让j分别为2 上，得到式(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 然后用一a百d】/d:、„、一a石d，/dl乘d了x?石一b!两边再分别加到平面a丁x=bj (2延j延k)上，得到 d丁x=石l d百x=石2二bZ一a百dl石，/d} 可x二(ak一a二d.d./d:)’x 二bk一a乙d，石，/d:二石k 再用一a丁dZ/d;、„、一a贾dZ/d;乘d百x=石2两边分别加到平面可x=石j(3延j延k)上， 得到 d不x=石l d百x=石2 d丁x=瓦‘b3一a丁dl石，/d了一a丁dZ石2/d圣 中南大学硕士学位抢文线性规划逐维选优强多项式解法21 如此进行k一1次法向消元同解变换，最后得到同解方程组(L2)，以Ok的表达式代 入(L2)，注意到d，、dZ、„、dk相互正交，可知ok是方程组的一个特解。再与推 论2.2及推论2.4比较，可知Rn中的kxll(k蕊n)行满秩线性代数方程组的上述法 向消元解法与点和法向量组的逐次投影等价。 注1.行满秩线性代数方程组的法向消元和点与法向量的逐次投影是同一解 法的不同描述，线性代数方程组的法向消元解法因此而具有鲜明的几何意义。行 满秩线性代数方程组的法向消元解法也称作逐次投影解法。 注2.由行满秩线性代数方程组(Ll)的法向消元解法可知，方程组(L1)的解 集是过点Ok的n一k维平面即二.、„、二k的交:，„k，dl、dZ、„、dk是二卜~k的正 交法向基。 注3.将(Ll)中的等号改成)，我们得到规定了内法向的行满秩不等式线性 系统，几乎重复上述讨论可知，该行满秩不等式线性系统的解是有向平面二，、„、 二k的交Fk的内部，d，、dZ、„、dk是Fk的正交内法向基。 3 . 3.2最小法向消元法 卜节法向消元解法不能解决非满秩线性代数方程组和非满秩不等式线性系 统的求解问题，山于含有非负约束，一般线性规划问题恰恰是非满秩不等式线性 系统的求解问题，必须将上节法向消元解法加以推广。 设Fk是n一m一k维，在F“上作逐次投影，将Ok和e{在第i(o延‘蕊n一m一k)次投 影后的投影简记为01和e;，记使e毖共0的下标集为Q岌。由(3?巧)式，相邻两投 影点的有向距离O‘一0，飞O;e;/e启，其长度是0{/(e盗)’/2，因此对所有j任Q孔的 负坐标O;令O;/(e::)’‘，=min[o;/(e启)’/，10;<0]，记st=一O:/e，:，而且对所有 j任Q;的非负坐标O;令sp=一O;/e{。=minGO{/e乞10;多0，e乞0、„) :x:=O、„、x‘一二O 图3.2(箭头指向内法向) 点X的坐标xj<0;又r的内部的每个边界面都分别是某一坐标超平面的子集， 。“的其余的点一定在r的内部的某一边界面的外部，因而也一定有某一坐标为 负，即:“的任何点都有负坐标，。“不可行。而在:“上:的内部与坐标超平面:， 相交是不可能的(参看图3.2)，否则可重排下标，使由第i次最小投影得到的投影 点。，有坐标。{一。、o生一。、„、o:一。、o{+.o，点P在坐标超平面:i的内部且不在 兀’上，作第i次投影时，若投影前的点oi一，在坐标超平面:‘十，的外部(如图3.2中 点A或点B)，则不满足对负坐标距离最大的投影条件min[O;/(e;)’“lO;<0];若 投影前的点Oi一’在二‘+’的内部(如图3.2中点C)，则不满足对非负坐标距离最小 中南大学硕士学位论文线性规划逐维选优强多项式解法23 的投影条件min(一O;/e七}O;)0，c七<0)，因为这两种投影情况得到的投影点都应 当至少是P而不是创。 注1.Rn中的点x到Rn中的低维平面F上的投影x，实际上是建立它们之间的 一一对应，并不要求x，一定是x到平面r的垂线的垂足。最小法向消元方法正是 利用这一点来保持投影点的非负坐标仍然非负，同时使投影点的负坐标尽可能多 地变成非负。 注2.最小法向消元方法之所以成为成功地解决5.Smale提出的“是否存在 基于实数的多项式算法来决定不等式线性系统Ax)b的可行性?”的基本数学工 具，是因为它在表面上是离散数学的凸多面体上求极值的问题中，充分利用了可 行域和可行域上的函数包括点和向量的符号变化的连续性。 3.4主要的判据 逐维选优方法获得最优解集的过程中，对于当前考查的等式约束平面与任何 一个坐标超平面，从理论上讲都需要进行五种判断，即 (i)该坐标超平面是否与当前考查的等式约束平面相交? (ii)如果相交，该交是否是可行域的低维边界面，也就是是否可行? (iii)如果可行，该可行低维边界面上目标函数是否有界? (iv)如果目标函数有界，该可行低维边界面是否是最优集? (v)如果不是最优集，当前考查的等式约束平面的所有可行的低一维的边界 面中，最优解一定会在哪一个上达到? 现设Fk为当前考查的等式约束平面，将这几种判断的判据列出如下: 3.4.1确定坐标超平面与等式约束平面相交的判据 由定理3.4，对于当前考查的Rn中的n一k(O毛k蕊n)维等式约束平面Fk和坐 标超平面开’，若e氢‘0，rk和“j相交;若e;=0且O{二0，rk在二’上;若e氢=0 中南大学硕士学位论文 且O{、0，rk和卫j平行。 由于实际的逐维选优过程中 e氢一0和e;‘O两种情况。 线性规划逐维选优强多项式解法24 。k在:j上的情形并不起作用，我们只要区分 3.4.2rk是否可行的判据 由定理3.6，当rk的判别点列中有点O‘)0时rk可行;当有0;<0且e益=0 时Fk不可行。 由于判别点列是由最小法向消元方法也就是最小投影法得出的，判断某一个 rk是否可行时，常常还要进行多次投影。但是，注意到Pk是n一m一k维，最多作n一m一k 次投影，就使坐标基向量在[’k上的所有非零投影向量全部变成零，也就是使所有 jEQ、的e罗一“=O，因此，应用定理3.6判断某一个「k是否可行时，总会或者有点 O，)0，r卜可行;或者有e孟?0且O;O，则sLP的最优解无界。 证注意到c梦=(ck)’e卜若对Fk的所有iEQk有c卜>0，则r卜与Rn的等值面 的交可以在「k上无限上升，即SLP的最优解无界。 由于若目标函数在SLP的可行域上有界，则目标函数在可行域的任何子集上 也一定有界:若目标函数在可行域上无界，则SLP的最优解无界，实际的逐维选 中南大学硕士学位论文线性规划逐维选优强多项式解法25 优过程中，关于目标函数是否有界的判断只要对r“进行一次。 3.4.4r“和r{+l是否最优集的判据 定理3.8若SLP的低维等值界面「k的所有内法向朝下，则rk是SLP的最优 解集。 证若rk是SLP的低维等值界面，按关于界面的定义3.2和等值面的定义3.4， Rn的等值面二与SLP的可行域相交。让SLP的等值面的高度h增大，在h=hk时SLP 的等值面变成SLP的低维等值界面Fk，故「k在可行域内，又由于SLP的可行域是 凸集，则当且仅当r“的所有内法向方向朝下时，rk上点的目标函数值取得SLP的 可行域上目标函数最大值，也就是低维等值界面rk是SLP的最优解集。 按内法向的定义，n一m一k维的rk的所有内法向朝下就是有cTd，蕊O、„、 cTdk毛D;按等值面的定义，Fk是n一m一k维等值面就是rk上的目标函数梯度ck=0， 也就是判别数(ck)’=0。 由定理3.4的式(3?17)，对于I’k与坐标超平面“j的交F{+’，其上的目标函 数梯度是 ck‘’二ck一c{e{ze盗 于是，应用推论3.5 (ek‘’)’=(ek一e{e梦/e盏)‘(ek一e{e}/e;)=(ek)’一(e})’/e; 令(ck+，)’=0，得到当最优解在rk上达到而rk不是n一m一k维最优集时，r:+I是 n一m一k一l维最优集的判据是r:‘，可行、e‘d，簇0、一e，d“毛o、e，d“‘，蕊0且 (e})’/e盖=(ek)’。 3.4.5当最优解在r“上达到而P“不是最优集时，最优解一定在低一维的r{+I上 达到的判据 定理3.9若rk可行且内法向朝下但不是SLP的n一m一k维等值界面，SLP有最 优解且(e{)’/e盏=max[(e:)’/e:}i任Qk，e:蕊0，r{二可行]，则SLp的最优解一定在 中南大学硕士学位杏文线性规划逐维选优强多项式解法26 巴?，上达到. 证「k的内法向朝下故c{成0，再由(c全)’/e;=max〔(c{)’/e门两边开方，不论 e全(1oQk)的正负都有一e黔/(e轰)’/，蒸一e}/(e盏)’/，。再在投影式e}?，?e}一e盏e)/e尝两 边用c点乘得到 C}‘，=c卜e;c黔/e尝 (e尝)’/，/〔e尝(e盗)’‘，〕=e}「l一(e})’e梦川e全l}e)1)]蕊。 (e全一e梦e盗 即F州的所有邻接界面上目标函数向r{“单调增大，F尸的任意邻接界面r{+I与 C二不. 1 SLP的等值面的交即r{‘，的等值面朝r州上 升。于是，可行域内r{+I的邻域内每一个点 的目标函数向F{+I单调增大。再注意到SLP 的可行域是凸集，由凸分析可知其局部最优 解就是整体最优解，即若SLP有最优解，最 优解必在F{‘，上达到(可参看图3.3)。 r，。飞‘.， 丫呀一r洲心+l.城厂e， 图3.3(e})’/e盗=max[(e卜)’/e:] 注1.明显地，定理3.9在线性规划的逐维选优强多项式算法和理论中具有 基石性的地位，正是它保证了整个逐维选优过程可以向前推进。 注2.定理3.9有几乎是明白无误的几何解释:由推论3.5和推论3.6 (C{)2/e:=〔(ek)’e)〕2/(e))2 ={ek{’„e){’eosZ(ek，e))/le){’ =}ek{Zeos，(ek，e李) 因此对于rk上所有ioQ，、e{蕊o且可行的。{一，条件(e})’/e盗=max[(e:)’/e轰〕 就是在rk上，所有可行的Ff+’中，r{+l的内法向e{与ck最接近反向垂直。若刚好 反向垂直，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+‘。 如果kmnZ”/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正交化子程序流程图 开始 创建数组T[.川 o[l]一A[l];T[l]=A[一]z(A[l]TA[l]) FFForj=1tommm PPP=000 FFFori=1tojjj PPP=P一A口]To[i]*A[i]]] NNNextiii DDDO]=A口]一PPP NNNEXTjjj 释释放数组T[.n]]] 返返回 中南大学硕士学位论文线性规划逐维选优强多项式解法35 5.3可行性判断子程序流程图 甲 创建数组E.[n，n]，Qk〔，2]，o[n]，Ik[，2] 一O,一,月，一一万,一一z‘、一一O一一一一UI一 „ c白)=C白) Fofl=1t0N E，口，i]=E口，i] NeXt NeXtJ K卜0;s=0，s下一0.00000001 FFForj=1tonnn kkkk=kk+l 中南大学硕士学位论文线性规划逐维选优强多项式解法36 Qk(kk，1):j; Qk(kk，2)=l: NeXtj 可行，返回FFFord=1tokkkk EEE护EI，于。。 FFForTI=1ton一m一kkk FFForj=1tonnn SSS=S+lll WWWWWWWWWWWWWWWWW=20)/Eto)’几几 QQQk(d，2)=00000000000000000000000 LLLk(s，1):j;;; LLLk(s，2)=w;;; SSS二w;t:jjj NNNextj 中南大学硕士学位论文线性规划逐维选优强多项式解法37 Qk(d，2)=0? 可行: S怜一z(t)/Et(t);sP=+co Forj=1tokk iii=QkO，l))) WWW=一z(i)/Et(t))) SSSP=w;P二iii NNNextj 中南大学硕士学位论文线性规划逐维选优强多项式解法38 222=2+sp*Et(t)))))2=2+st*Et(t))) 计计算Et的投影影 NNNextTttt QQQk(d，2)=000 NNNextkkkk 不可行。返回 中南大学硕士学位论文线性规划逐维选优强多项式解法39 5.4主程序 100 1011 801 1012 】001 PROGRAMSLP PARAMETER(M=，N=，EK=l.OE一9) COMMONL(N)，X(N) DIMENSIONG(N，N)，GK困，N)，S(N)，C(N) eALLTv(M，N，qe，eZ)一求e、ei、o到等式约束平面的投影e、o一笼e{}、x:eZ记(ck)， CALLPKX困，G，N一M，KK，MO)一判断尸的可行性，KK二0表示不可行 lF(KKEQ.0)TH阴一当r0不可行时可行域空 wRITE(*，*)‘Feasible一?gionise一nPty’ GOTO901 ENDIF KY=0一判断最优解是否无界，初值ky=0表示最优解无界 DO1001=l，N IF(C(l).LE.O.0.AND.L(I).GT.0)KY=l~如果有e卜护0且e{毛0则KY二l CONTINUE IF(KY.EQ . 0)THEN WRITE(*，*)‘OPtimalu，，bou，lded’ GOI，0901 ENDIF M于0一Mo记己判定不可行F丫的个数 DO1olK=N一M，0，一l IF(CZ . LT.EK)TllEN一当(ek)2=o时有k维最优解集 WRITE(*，*)‘OPtimalset15’，k，‘di一nension.ltsasolution15:’ WRITE(*，*)X GOTO901 END!F 00一。川一，N一计算51一(e))，ze: ?o一当e卜0或者e{护0且c}>0时51=一l<一0?5 S(l)一1 IF(L(I)?GT.o?AND?C(I)?LE?0?0)S(I卜C(I)*C(I)/G(I，I)一当e卜共o且e}蕊0时51 多o CONTINUE 11一o一对e卜共0且c}毛0找max(sj)对应的下标11 T=一0.5 DO10121=l，N IF(S(I).GT.T)THEN T=S(l) 11=l END!F CONTINUE DO!001卜l，N~用数组存e卜和以I)以免其值改变，对同一维数k可能多次判断r丫 的可行性 LL(I)=L(I) DO100IJ=l，N GG(l，J)=G(I，J) 10131 】0132 】013 1002 ， 10021 101 901 中南大学硕士学位论文线性规划逐维选优强多项式解法40 DO1013I=l，N~向低维平面r罕投影 lF(LL(I).GT.0)THEN~对所有e{井0计算点和法向量的投影x和GG 51=GG(11，l)/GG(11，11) X(I)=X(I)一X(11)*51 DO1013IJ=I，N~利用对称性 GG(I，J)=GG(l，J)一GG(11，J)*51 GG(J，I)=GG(I，J) DO101321=l，N IF(GG(I，l).LT.EK)LL(I)=一l~当el=O时用LL(I)=一l记其序号 CONTINUE ENDIF CONTINUE IF(MO?LT.M)CALLpKX侧，GK，K一l，KK，，MO)一判断F}J，的可行性 IF(KK?EQ?o)THEN一若r{J，不可行转801找次大的max(sj)对应的下标11 coTo80-~子程序中己用以11卜o表示已判定不可行并让Mo=Mo+- ELsE一若l’丫可行将ck向r丫投影并恢复用G记投影后的{e协 DO10021=1，N Z(I)=GK(11，I) 51=Z(I)/GK(11，11) C(I)=C(I)一C(11)*51 DO1002)=l，N G(l，J)=GK(I，J) DO100211=I，N IF(L(I) . GT.o.AND.G(l，l).LT.EK)L(I)=一I~当e黔=o时用L(x)=一记其序号 CONTINUE WRITE(*，*)‘D，，K，‘=，，Z~输出正交法向基向量 CZ=CZ一S(11)一计算新的(ek)， ENDIF CONTINUE END 5 . 5函数及子程序 FUNCTIONP困，X) ) DIMENSIONX倒 P=0.0 DO1011=l，N IOIP=P+X(I)*X(I) P=】.0/P END ~求向量平方及其倒数 FUNCTIONQ州，X，Y) D1MENSIONX(N)，Y(N) Q=0.0 DO1011=l，N I01Q=Q+X(l)*Y(I) END ~求向量内积 中南大学硕士学位铸文线性规划逐维选优强多项式解法们 SUBROUTINETY(M，N，qC，CZ) COMMON以N)，X(N) ~求到等式约束平面的投影 1011 !0】 1012 10131 】013 !021 10221 】022 】023 1024 】0251 1025 102 DIMENSIONA(M，N)，B(M)，C(N)，G(N，N)，D(M，N)，Y困)，Z倒) wRITE(*，*)‘一NPuTe’~给e，A，b赋初值 READ(*，*)C WRITE(*，*)‘INPUTA， READ(*，*)A WRITE(*，*)‘INPUTB’ READ(*，*)B DO1011=l，N Y(J)=A(1，J)~用y记d，以求向量的平方 DO101IJ=1，N G(I，J)=0.0 G(I，I)=一。一给e.赋最初值 *)‘DI=，，Y~输出正交法向基向量d. WRITE(*， S=P(N，Y)~求s=l/dl T=Q(N，e，Y)一求t=cTd. DO101ZJ=1，N Z(J)=S*Y(J)~用z记dl/dl DO10131=l，N R=Y(I)~)4JR记d11 DO1013IJ=1，N G(一，J)=G(一，J)一R*Z(J)~求el=ei一d.id./dl x(I)=B(l)*Z(I)~求X=b，d，/dl e(l)=e(一)一T*z(l)~求ek=e一eTd，d一沮l DO1OZK=2，M DO102IJ=l，N Z(J)=A(K，J)一用z记aK以求向量的平方 S=Q(N，Z，Y)*S~求s=aJdK_l/d乏_， DO10221=K，M DO1022IJ二l，N D(I，J)=D(I，J)一S*Y(J)~求dk=dk一a奋dK_.dK_!/d畏_， B(K)二B(K)一S少B(K一1)~求bk=bk一a万dK一bK_!/d孟_. DO1023)=l，N Y(J)=D(K，J)一用y记dk以求向量的平方 WRITE(*，*)‘D，，K，‘=，，Y~输出正交法向基向量dk S=P(N，Y)~求s=l/d是 卜Q(N，e，Y)~求卜cTdk DO1O24)=I，N Z(J)=S*Y(J)~用z记dK/d是 00一0251=l，N~给e梦、ok、ck赋初值 R=Y(I)~用R记dks DO1025IJ=l，N G(I，J)=G(I，J)一R*Z(J)~求e{=e。一dkidK/d乏 X(l)=B(K)*Z(I)~求X=bKdK/d乏 e(一)=e(l)一T*z(一)~求ek=c一cTdkdK厄乏 CONTINUE 中南大学硕士学位论文线性规划逐维选优强多项式解法42 DO1031=l，N~给L(l)赋初值 IF(G(l，I).GT.EK)THEN L(l)=l一当e卜#0时用以I)=I>0表示以后要参加选优和判定 ELSEIF(X(l).LT.EK)THEN L(I卜I一当“黔一o且O{<0时用L(I)=一ll.4O103一118，1992 41.1).E.Gill，andW.Marray，AnunlerieallystableformoftheSimPlexalgoritl、m，J. l 一 J ，Vol.7，1973 inearalgebraaPPlications 42 . 1飞E.Gilletal，OnProjeetedNewtonbarriermethodsforlinearProgram，ni，，9and a，1equivale，ieetoKarmarkar’5PrO.jeetivemethod，Teell.RePortSOL85一11.DePt. ofOPer.Res.，StanfordUniv.，1985 43 . R . I一1.Bal?tels，a一ld(1.1一1.Golub，TI、esixnPlexmethodoflinearPl?ogrammingusing I 一矛 [J〔leeo一11Positioxl，Co一nln:1llieatio一1ACM，Vol.12，1969 44 . Slla一111一、l之.，rrhee日Icieneyoftllesixl:Plex1llethod:asurvey，Ma一lage一11entsciellce， VO1 . 33，301一304，】987 45.S.Smale，MathelllatiealProblemsfortl飞。NextCentury，TlleMatllelllatieal 1Iltellige一iee，VOI.20，19981’且rdos，E.AstroliglyPolynomialminimumeost e11?eulatiollalgoritll一11，Co一11bil飞atoriea，VOI.5，1983 46 .r l，aPia，R.A.，alldZllang，Y.，Cubieallyeollverge;Itmethodforloeatinganearby vertexi一111一飞earP一ogralllllli一19，Jotl一nalofoPtinlizationtheorya一ldaPPlieatio一15， VOI . 67，217一225，1990 47 .『 I，(’ddM.J.ANDB.P.Burrell，AnextellsionofKarnlarkar’5algorithrllforlinear Programmingusingdualvariables，Algoritl、miea，Vol.1，1986 48 . Ye，Y.，Karmarkar’5algorithmandtheelliPsoidmethod，OPer.Res.，Vol.35 177一182，1992 下面为朱自清的散文欣赏，不需要的朋友可以下载后编辑删除～～～谢谢～～～ 荷塘月色 作者: 朱自清 这几天心里颇不宁静。今晚在院子里坐着乘凉，忽然想起日日走过的荷塘，在这满月的光里，总该另有一番样子吧。月亮渐渐地升高了，墙外马路上孩子们的欢笑，已经听不见了;妻在屋里拍着闰儿，迷迷糊糊地哼着眠歌。我悄悄地披了大衫，带上门出去。 沿着荷塘，是一条曲折的小煤屑路。这是一条幽僻的路;白天也少人走，夜晚更加寂寞。荷塘四面，长着许多树，蓊蓊郁郁的。路的一旁，是些杨柳，和一些不知道名字的树。没有月光的晚上，这路上阴森森的，有些怕人。今晚却很好，虽然月光也还是淡淡的。 路上只我一个人，背着手踱着。这一片天地好像是我的;我也像超出了平常的自己，到了另一世界里。我爱热闹，也爱冷静;爱群居，也爱独处。像今晚上，一个人在这苍茫的月下，什么都可以想，什么都可以不想，便觉是个自由的人。白天里一定要做的事，一定要说的话，现在都可不理。这是独处的妙处，我且受用这无边的荷香月色好了。 曲曲折折的荷塘上面，弥望的是田田的叶子。叶子出 水很高，像亭亭的舞女的裙。层层的叶子中间，零星地点缀着些白花，有袅娜地开着的，有羞涩地打着朵儿的;正如一粒粒的明珠，又如碧天里的星星，又如刚出浴的美人。微风过处，送来缕缕清香，仿佛远处高楼上渺茫的歌声似的。这时候叶子与花也有一丝的颤动，像闪电般，霎时传过荷塘的那边去了。叶子本是肩并肩密密地挨着，这便宛然有了一道凝碧的波痕。叶子底下是脉脉的流水，遮住了，不能见一些颜色;而叶子却更见风致了。 月光如流水一般，静静地泻在这一片叶子和花上。薄薄的青雾浮起在荷塘里。叶子和花仿佛在牛乳中洗过一样;又像笼着轻纱的梦。虽然是满月，天上却有一层淡淡的云，所以不能朗照;但我以为这恰是到了好处——酣眠固不可少，小睡也别有风味的。月光是隔了树照过来的，高处丛生的灌木，落下参差的斑驳的黑影，峭楞楞如鬼一般;弯弯的杨柳的稀疏的倩影，却又像是画在荷叶上。塘中的月色并不均匀;但光与影有着和谐的旋律，如梵婀玲上奏着的名曲。 荷塘的四面，远远近近，高高低低都是树，而杨柳最多。这些树将一片荷塘重重围住;只在小路一旁，漏着几段空隙，像是特为月光留下的。树色一例是阴阴的，乍看像一团烟雾;但杨柳的丰姿，便在烟雾里也辨得出。树梢上隐隐约约的是一带远山，只有些大意罢了。树缝里也漏 着一两点路灯光，没精打采的，是渴睡人的眼。这时候最热闹的，要数树上的蝉声与水里的蛙声;但热闹是它们的，我什么也没有。 忽然想起采莲的事情来了。采莲是江南的旧俗，似乎很早就有，而六朝时为盛;从诗歌里可以约略知道。采莲的是少年的女子，她们是荡着小船，唱着艳歌去的。采莲人不用说很多，还有看采莲的人。那是一个热闹的季节，也是一个风流的季节。梁元帝《采莲赋》里说得好: 于是妖童媛女，荡舟心许;鷁首徐回，兼传羽杯;欋将移而藻挂，船欲动而萍开。尔其纤腰束素，迁延顾步;夏始春余，叶嫩花初，恐沾裳而浅笑，畏倾船而敛裾。 可见当时嬉游的光景了。这真是有趣的事，可惜我们现在早已无福消受了。 于是又记起《西洲曲》里的句子: 采莲南塘秋，莲花过人头;低头弄莲子，莲子清如水。今晚若有采莲人，这儿的莲花也算得“过人头”了;只不见一些流水的影子，是不行的。这令我到底惦着江南了。——这样想着，猛一抬头，不觉已是自己的门前;轻轻地推门进去，什么声息也没有，妻已睡熟好久了。 在北京住了两年多了，一切平平常常地过去。要说福气，这也是福气了。因为平平常常，正像“糊涂”一样“难得”，特别是在“这年头”。但不知怎的，总不时想着在那儿过了五六年转徙无常的生活的南方。转徙无常，诚然算不得好日子;但要说到人生味，怕倒比平平常常时候容易深切地感着。现在终日看见一样的脸板板的天，灰蓬蓬的地;大柳高槐，只是大柳高槐而已。于是木木然，心上什么也没有;有的只是自己，自己的家。我想着我的渺小，有些战栗起来;清福究竟也不容易享的。 这几天似乎有些异样。像一叶扁舟在无边的大海上，像一个猎人在无尽的森林里。走路，说话，都要费很大的力气;还不能如意。心里是一团乱麻，也可说是一团火。似乎在挣扎着，要明白些什么，但似乎什么也没有明白。“一部《十七史》，从何处说起，”正可借来作近日的我的注脚。昨天忽然有人提起《我的南方》的诗。这是两年前初到北京，在一个村店里，喝了两杯“莲花白”以后，信笔涂出来的。于今想起那情景，似乎有些渺茫;至于诗中所说的，那更是遥遥乎远哉了，但是事情是这样凑巧:今天吃了午饭，偶然抽一本旧杂志来消遣，却翻着了三年前给S的一封信。信里说着台州，在上海，杭州，宁波之南的台。这真是“我的南方”了。我正苦于想不出，这却指引我一条路，虽然只是“一条”路而已。 ---------------朱自清《一封信》 燕子去了，有再来的时候;杨柳枯了，有再青的时候;桃花谢了，有再开的时候。但是，聪明的，你告诉我，我们的日子为什么一去不复返呢?——是有人偷了他们罢:那是谁?又藏在何处呢?是他们自己逃走了罢:现在又到了哪里呢? 我不知道他们给了我多少日子;但我的手确乎是渐渐空虚了。在默默里算着，八千多日子已经从我手中溜去;像针尖上一滴水滴在大海里，我的日子滴在时间的流里，没有声音，也没有影子。我不禁头涔涔而泪潸潸了。 --载自《匆匆》 这时我们都有了不足之感，而我的更其浓厚。我们却只不愿回去，于是只能由懊悔而怅惘了。船里便满载着怅惘了。直到利涉桥下，微微嘈杂的人声，才使我豁然一惊;那光景却又不同。右岸的河房里，都大开了窗户，里面亮着晃晃的电灯，电灯的光射到水上，蜿蜒曲折，闪闪不息，正如跳舞着的仙女的臂膊。我们的船已在她的臂膊里了;如睡在摇篮里一样，倦了的我们便又入梦了。那电灯下的人物，只觉像蚂蚁一般，更不去萦念。这是最后的梦;可惜是最短的梦!黑暗重复落在我们面前，我们看见傍岸的空船上一星两星的，枯燥无力又摇摇不 定的灯光。我们的梦醒了，我们知道就要上岸了;我们心里充满了幻灭的情思。 --载自《桨声灯影里的秦淮河》 近几年来，父亲和我都是东奔西走，家中光景是一日不如一日。他少年出外谋生，独力支持，做了许多大事。那知老境却如此颓唐!他触目伤怀，自然情不能自已。情郁于中，自然要发之于外;家庭琐屑便往往触他之怒。他待我渐渐不同往日。但最近两年的不见，他终于忘却我的不好，只是惦记着我，惦记着我的儿子。我北来后，他写了一信给我，信中说道，“我身体平安，惟膀子疼痛利害，举箸提笔，诸多不便，大约大去之期不远矣。”我读到此处，在晶莹的泪光中，又看见那肥胖的，青布棉袍，黑布马褂的背影。唉!我不知何时