最优化方法课程设计

四川理工学院《最优化方法》课程论文题目：基于Matlab的单纯形法仿真实验姓名：刘宇泽专业：信息与计算科学班级：一班学号：12071030113完成日期：2015年6月27日四川理工学院理学院二O一五年六月摘要线性规划是运筹学中研究最早、发展最快、应用广泛、方法较成熟的一个重要分支，它是辅导人们进行科学管理的一种数学方法。是研究线性约束条件下线性目标函数的极值问题的数学理论和方法。为了得到线性目标函数的极值，我们有多重方法。本文采用单纯形算法求解线性规划问题的最优解，并通过Matlab软件编写程序进行求解。最终得到线性规划问题的最优解，进一步验证了求解问题的精度，较良好。关键词：线性规划单纯性算法Matlab程序目录一、问题提出.............................................................1二、设计思路和步骤.......................................................1三、程序设计.............................................................23.1问题分析..........................................................23.2算法设计..........................................................33.3程序编制..........................................................33.4算法框图..........................................................4四、结果分析.............................................................54.1设计结果..........................................................54.2进一步讨论和验证..................................................5五、收获和总结...........................................................5六、结束语...............................................................66.1设计的优缺点......................................................66.2设计工作展望......................................................66.3学习心得与体会....................................................6四川理工学院毕业论文1一、问题提出本文运用单纯形算法解下列问题：0,0,0,0,43252-2.5.53.26.00.2)(min43214321432143214321xxxxxxxxxxxxxxxxtsxxxxxf，，二、设计思路和步骤2.1设计思路单纯形法的基本思路：根据单纯形法的原理，在线性规划问题中，决策变量（控制变量）x1，x2，…xn的值称为一个解,满足所有的约束条件的解称为可行解。使目标函数达到最大值（或最小值）的可行解称为最优解。这样，一个或多个最优解能在整个由约束条件所确定的可行区域内使目标函数达到最大值（或最小值）。求解线性规划问题的目的就是要找出最优解。最优解可能出现下列情况之一：①存在着一个最优解；②存在着无穷多个最优解；③不存在最优解，这只在三种情况下发生，即没有可行解或各项约束条件不阻止目标函数的值无限增大（或向负的方向无限增大）。单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。用单纯形法求解线性规划问题所需的迭代次数主要取决于约束条件的个数。现在一般的线性规划问题都是应用单纯形法标准软件在计算机上求附录2解，对于具有10^6个决策变量和10^4个约束条件的线性规划问题已能在计算机上解得。2.2设计步骤1、对于一般的线性规划，将其化为标准形；2、求出基本初始可行解；3、先检验其最优性；4、如果不是最优的，则从取负值的非基变量中选取一个最负确定为入基变量；5、选好入基变量后，再在基变量中选取一个出基变量；6、选好入基变量和出基变量后，进行高斯消去，得到新的可行解；7、重复以上过程，直至找到最优解。三、程序设计3.1问题分析在用单纯性算法解决线性规划问题时，考虑标准型线性规划问题，其标准型如下：0,.)(minxbAxtsxcxfT现在将本文所讨论的线性规划化为标准型线性规划的形式。0,0,0,0,0,0,0,43252-2.5.53.26.00.2)(min76543217432164321543214321xxxxxxxxxxxxxxxxxxxxxxtsxxxxxf，，其中四川理工学院毕业论文3[2.00.62.35.5][1111100;1121010;2311001][2;5;4][5,6,7],[1,2,3,4]BNcAbxx3.2算法设计1、解bBxB，求得bBxB1，令0Nx,计算目标函数值BBxcf，以mibi,...2,1记bB1的第i个分量；2、计算单纯性乘子w，1,BCwCwBBB得到，对于非基变量，计算判别系数iikiiBiiiczcpBccz令,1，R为非基变量集合，若判别系数0k，则得到一个最基本可行解，运算结束；否则，转到下一步3、kkkkkkaapBapBa，即若得到0;,1的每一个分量均非正数，则停止计算，问题不存在有限最优解，否则，进行步骤4：4、为入基变量，为出基变量，使确定下表kBrrkrkirkrxxaababr,0,min,BppBrk得到新的基矩阵代替用,，返回步骤1.3.3程序编制c=[-2.0-0.62.3-5.5]';A=[11-1-1;1-1-2-1;231-1];b=[2-54]';lb=[0000]';[x,fval,exitflag]=linprog(c,A,b,[],[],lb)附录43.4算法框图把LP问题化成标准型建立初始单纯型表计算0z和非基变量x是最优解么计算2min0jj对应于k，存在0jk吗？计算min0iikikllkbaaba确定主元lka以lka为主元进行一次换基运算求出最优解停解无界是否四川理工学院毕业论文5四、结果分析4.1设计结果（可用文字描述和贴图等方式表现设计结果）x=1.0e+031*2.49550.00000.00004.9910fval=-3.2442e+032exitflag=-3由以上结果可以看出本文所提问题具有无限的解，不具有收敛的解4.2进一步讨论和验证（比如：设计的改进、推广等）本文所提问题用单纯形方法求解，需要得到的初始基本可行解，根据调用函数得到的结果来看，不存在有限次迭代然后得到收敛的解，Matlab程序直观的看出存不存在最优解。五、收获和总结5.1个人总结通过做这次课程设计，对最优化方法的理解又上了一个层次，同时学到了书本上没有的知识，通过这次课程设计我学习到了理论与实际结合是很重要的，只有理论知识是远远不够的，只有把所有的知识与实践结合起来，才能学到更多，而不是纸上谈兵。同时编写Matlab程序，也更直观的体现了一个问题的收敛性，方法只是解决问题的一途径，只有不断学习，才有可能设计出更好的算法，做成一件事，不是一蹴而就的。附录6六、结束语6.1设计的优缺点优点：1、调用Matlab里自带的函数，方便实用，不用耗时的去编写程序。2、画出框图更好地对程序进行理解。缺点：1、不能给出完整的实现过程。2、由于本题不收敛，所以也不知道迭代次数。6.2设计工作展望单纯形法已经是解决此类问题的不二之选，但我想通过自己努力，能设计出更好的算法，解决更多的线性问题。6.3学习心得和体会通过这次试验，使我对单纯形法的计算有了更进一步的了解。但是在编程过程中由于对matlab不是很熟悉还是遇到了很多麻烦，所以我觉得老师在让我们编程的时候不能只是简单的介绍一下算法，更要着重说明一下软件的使用方法。这样我们在编程的时候就能更加的得心应手。本次完全仿照老师给的程序，没有能够形成自己的东西。自己编程的能力还是很差的，对于这种已经给出算法的程序也不能正确的编写出来。所以在今后要加强这方面的学习。