发布时间 : 星期四 文章线性规划问题更新完毕开始阅读
分类号
UDC
.门-~.........-网‘一一‘.-........ 密级 编号
..‘..，....口.侧卜......叫口.....勺.曰.，.，.......匕勺， 中.菊大净
CENTRALSOUTHUNIVERSITY 硕士学位论文
论文题目线性规划逐维选优 强，..项式解诊 _.
学科、专业应用数学 研究生妓名 导师姓名及 专业技术职务
彭猛
彭岳林教授
中南大学硕士学位论文线性规划逐维选优强多项式解法
摘要
随着现代科学技术的迅猛发展，最优化理论得到了越来越广泛的应用，同时 对其理论发展也提出了新的要求。
最优化学科的基础是线性规划。然而，实际计算和理论分析表明，当决策变
量数目猛烈增大时，目前广泛使用的线性规划的各种迭代算法都存在严重缺陷。 因此，进一步改进和完善线性规划的算法，努力降低计算的时间复杂度和提高对 最优解集的完整描述，具有十分重要的理论意义和实践意义。
通过对低维空间线性规划问题进行分析及研究，我们提取出其中具有普遍性 的规律，并将其向高维空间进行推广，研究出了一种新的算法一逐维选优直接 算法，以强多项式时间复杂度求出线性规划问题的结构清晰的全部最优解的集合 为目的。
此解法以逐次投影为手段，首先将线性代数方程组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 目录 中文摘要 英文摘要
第一章关于最优化传统理论的回顾与总结·····························??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提出的。任何线性规划问题均可化成下列标准型线性 规划问题SLP:
maxf(x)=eTxe，x任Rne#O
5.t.Ax=bAeR”nb#0任R’l延m x)0 1947年Dantzig提出求解线性规划问题的单纯形方法。此后，以单纯形迭代 方法为主要计算基础的最优化理论和方法或者说运筹学理论和方法飞速发展。 1977年，Bland修正Dantzig的最负检验数法则，使单纯形法必能经有限次迭代 求出线性规划问题的最优解或肯定该问题无最优解，线性规划单纯形理论结构趋 于完善。然而，随着科学技术的飞速发展，现代线性规划实际问题的变量和约束 条件数目猛增，理论分析和计算实例表明，单纯形法的时间复杂度为0(mnZn)， 几乎是各种时间复杂度中最差的，不能满足现代人类活动的需要。于是，如何提 高求解线性规划问题的速度就成为具有时代气息的一个重要课题，1979年xa、二 提出时间复杂度为O(n4Lz)的椭球算法，5年后Karmarkar提出另一种时间复杂度 为O(n4L)的内点算法，它们从理论上讲都是多项式算法，也曾经使很多人欢欣鼓 舞。但是，由于计算机有限精度计算的限制，椭球算法实际计算时收敛速度极慢， 一般认为该算法的任何合理实现方法都不大可能是多项式时间的。内点算法不是 沿可行域顶点进行迭代，而是通过内点迭代达到最优解，每次迭代要在可行域内 按正确选定的步长沿较好方向推进，实际计算的收敛速度也很不理想。尽管人们 后来对它们作出过多种修补，但是情况并无根本改善。而且，由于迭代算法是倾 全力于求出一个最优点，而线性规划的广泛实际问题却更对全体最优解的集合有 兴趣，二者相距甚远。这一点可以从下图明显看出。 中南大学硕士学位论文线性规划逐维选优强多项式解法6 为简便起见，我们假设最优解集为二:上的一条与目标函数梯度C的方向垂 直的直线L.，L，与二，、二。的交为A、B两点，迭代算法只能求出A、B两点中的 一点，而不能求出整条直线L，的方程。而在实践中我们对最优解集L，更感兴趣， 因为如果知道了L，的方程的表达式及其边界条件，工程师们就可以非常容易地设 计出和实现实际需要的最佳解决方案。 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