线性规划的单纯形算法课程设计论文.doc

四川理工学院 最优化方法课程论文 题目：线性规划的单纯形算法 姓 名： 专 业：统计学 班 级：2011 级 1 班 学 号： 完成日期：2014 年 6 月 27 日 四川理工学院理学院 二 o 一 四 年 六 月 摘 要 线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分 支，它是辅助人们进行科学管理的一种数学方法。是研究线性约束条件下线性目标函 数的极值问题的数学理论和方法。为了得到线性目标函数的极值，我们有多重方法。 本文采用单纯性算法求解线性规划问题，并通过 matlab 软件编写程序进行求解。 关键词：关键词：线性规划 单纯性算法 matlab 编程 目 录 一、 单纯性方法简介.1 1.1 单纯性方法提出1 1.2 单纯性方法的基本思想和步骤.1 1.2.1 基本思想.1 1.2.2 计算步骤.1 二、问题的提出与分析.1 2.1 问题提出.1 2.2 问题分析.2 三、程序设计.2 3.1 算法设计.2 3.2 算法框图.3 3.3 程序编制.4 四、结果分析.6 4.1 设计结果.6 4.2 进一步讨论和验证8 五、结束语.8 5.1 设计的优缺点8 5.2 收获与总结.9 参考文献.10 附 录.11 四川理工学院最优化方法课程论文 1 1、单纯性方法简介 1.1 单纯性方法提出 单纯形法，求解线性规划问题的通用方法。单纯形是美国数学家 g.b.丹齐克于 1947 年首先提出来的,这是 20 世纪数学界最重大的成果之一。由于这一方法的有效性， 几十年来一直在几乎所有的领域得到广泛应用。 它的理论根据是：线性规划问题的可行域是 n 维向量空间 rn 中的多面凸集，其最 优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。 1.2 单纯性方法的基本思想和步骤 1.2.1 基本思想 单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优 解；若不是，则按照一定法则转换到另一改进的基本可行解，再鉴别；若仍不是，则 再转换，按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的 最优解。如果问题无最优解也可用此法判别。 1.2.2 计算步骤 1、对于一般的的线性规划，将其化为标准型； 2、求出初始基本可行解； 3、先检验其最优性； 4、如果不是最优的，则从取负值的非基变量中选取一个最负确定为入基变量； 5、选好入基变量后，再在基变量中选取一个出基变量； 6、选好入基变量和出基变量后，进行高斯消去，得到新的可行解； 7、重复以上过程，直至找到最优解。 、 二、问题的提出与分析 2.1 问题提出 本文运用单纯性算法求解下列问题： max 321 453xxxz s.ts.t 120032 21 xx 80042 32 xx 2000523 321 xxx 0, 321 xxx 四川理工学院最优化方法课程论文 2 并编写 matlab 程序求解。 2.2 问题分析 在用单纯性算法解决现行规划问题时，我们通常考察标准形现行规划问题，其标准形 如下： xcxf t )(min 0,. .xbaxts 现在将本文所讨论的线性规划化为标准线性规划的形式： min 321 453xxxzy s.t. 120032 421 xxx 80042 532 xxx 2000523 6321 xxxx 其中4, 5, 3c a=2 3 0 1 0 0 0 2 4 0 1 0 3 2 5 0 0 1 2000,800,1200b ，6 , 5 , 4 b x3 , 2 , 1 n x 三、程序设计 3.1 算法设计 1、解，求得，令，计算目标函数值,以 bbxbbbxb 1 0 n x bbx cf 记的第 i 个分量；)m, 2 , 1(ibibb 1 2、计算单纯性乘子 w，,得到,对于非基变量，计算判别系数 b cwb 1 bcw b ，令，r 为非基变量集合，若判别系数 iibiii cpbccz 1 ii ri k cz max ，则得到一个最基本可行解，运算结束；否则，转到下一步0 k 3、解，得到；若，即的每一个分量均非正数，则停止计算， kk pba kk pba 1 0 k a k a 问题不存在有限最优解，否则，进行步骤 4; 四川理工学院最优化方法课程论文 3 4、确定下标 r，使，为出基变量，为入基变量，用 0min rk rk i rk r a a b a b r b x k x 替换，得到新的基矩阵 b，返回步骤 1。 k p r b p 3.2 算法框图 是是 否否 是是 否否 开始 初始可行解b 令 1 ,0, bnbb xb bb xfc x 计算单纯形乘子，计算判别数（非基变 1 b wc b, ijj wpcjr 量）令max, kj jr 0? k 得到最优解 解方程，得到。 kk pba kk pba 1 ?0 k a 不存在有限最优解 确定下标，是r 0min rk rk i rk r a a b a b 四川理工学院最优化方法课程论文 4 3.3 程序编制 a=input(a=); b=input(b=); c=input(c=); format rat m,n=size(a); e=1:m;e=e; f=n-m+1:n;f=f; d=e,f; x=zeros(1,n); if(n0) r=i; end end fprintf(x(%d)进基，x(%d)退基n,k,d(r,2); b(:,r)=a(:,k); cb(r)=c(k); 四川理工学院最优化方法课程论文 6 d(r,2)=k; end end end end 四、结果分析 4.1 设计结果 在命令窗口中输入： a=2,3,0,1,0,0;0,2,4,0,1,0;3,2,5,0,0,1 b=1200,800,2000 0 , 0 , 0 , 4, 5, 3c 得到如下结果: 四川理工学院最优化方法课程论文 7 四川理工学院最优化方法课程论文 8 我们可以看到，程序经过 4 次换基迭代，得到目标函数的最优值为-2600，即目标函数 的最小值为-2600。从而，原问题的最大值为 2600。 4.2 进一步讨论和验证 对于 matlab 程序的正确性与软件运行的可行性。由于计算量并不是很大，我们通过 单纯性表进行手工计算。经过几次换基迭代，我们选取的入基变量和出基变量与以上 软件运行过程得到的结果完全相同。由此，我们可以认定目标函数的最小值为-2600， 即原问题的最大值为 2600。 五、结束语 5.1 设计的优缺点 设计优点： 1、设计的程序是根据课本的步骤编写的； 2、程序的编制能得到正确结果； 3、编制的程序得到的结果中具体体现每一步的出基变量与入基变量，清晰明了； 四川理工学院最优化方法课程论文 9 设计缺点： 1、不能直观的反应迭代步数，如若迭代次数过多，则想要了解迭代步数则比较麻烦； 2、不能给出完整的单纯性表。 5.2 收获与总结 通过本次课程论文设计，让我对单纯性法有了进一步的了解，明确了它的具体思想理论，算法 步骤。此外，通过此次课程设计，初次接触了 matlab 软件，让我对 matlab 软件有了初步的 了解，此次论文的完成，主要是通过根据算法设计，编制 matlab 程序，通过 matlab 软件对 模型求解。因此，此次设计的最大问题在于怎样设计算法程序，但这对于我们来说难度还是比较大， 所以，此次的单纯性算法程序直接利用网上给出的算法程序进行设计。但网上的很多程序也存在很 多问题，需要在一次一次的错误中不断的更正问题，直到最后得到模型正确的结果。由于对 matlab