线性规划的单纯形算法课程设计论文.doc
《线性规划的单纯形算法课程设计论文.doc》由会员分享,可在线阅读,更多相关《线性规划的单纯形算法课程设计论文.doc(13页珍藏版)》请在三一文库上搜索。
1、四川理工学院 最优化方法课程论文 题目:线性规划的单纯形算法 姓 名: 专 业:统计学 班 级:2011 级 1 班 学 号: 完成日期:2014 年 6 月 27 日 四川理工学院理学院 二 O 一 四 年 六 月 摘 要 线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分 支,它是辅助人们进行科学管理的一种数学方法。是研究线性约束条件下线性目标函 数的极值问题的数学理论和方法。为了得到线性目标函数的极值,我们有多重方法。 本文采用单纯性算法求解线性规划问题,并通过 Matlab 软件编写程序进行求解。 关键词:关键词:线性规划 单纯性算法 Matlab 编程 目 录 一
2、、 单纯性方法简介.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.
3、B.丹齐克于 1947 年首先提出来的,这是 20 世纪数学界最重大的成果之一。由于这一方法的有效性, 几十年来一直在几乎所有的领域得到广泛应用。 它的理论根据是:线性规划问题的可行域是 n 维向量空间 Rn 中的多面凸集,其最 优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。 1.2 单纯性方法的基本思想和步骤 1.2.1 基本思想 单纯形法的基本思想是:先找出一个基本可行解,对它进行鉴别,看是否是最优 解;若不是,则按照一定法则转换到另一改进的基本可行解,再鉴别;若仍不是,则 再转换,按此重复进行。因基本可行解的个数有限,故经有限次转换必能得出问题的 最优解。如果问
4、题无最优解也可用此法判别。 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 四川理工
5、学院最优化方法课程论文 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 三、程序设计
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 线性规划 单纯 算法 课程设计 论文
链接地址:https://www.31doc.com/p-3960204.html