单纯形法及其应用.doc
《单纯形法及其应用.doc》由会员分享,可在线阅读,更多相关《单纯形法及其应用.doc(26页珍藏版)》请在三一文库上搜索。
1、单纯形法及其应用 摘 要 单纯形法是一种主要的解决线性规划问题的方法,它在生活的成本问题、交通选 择或规划学术问题等方面得到广泛应用.本文系统的研究了单纯形法的相关概念以及原 理.并阐述了用单纯形法解决线性规划问题的步骤与方法及不同方法的特殊性.正确的 应用单纯形法解决问题能够提高准确率,从而进行合理的规划安排,使得效果或收益 达到期待化或最优化. 关键词:单纯形法;单纯形表;最优性 The Simplex Method and its Application Abstract: Simplex method is a main to solve linear programming prob
2、lems, it in life cost, the choice of traffic or academic planning problems are widely used. This paper study the simplex method of the related concepts and principles. It describes the steps and methods to use simplex method to solve linear programming problems, and the different method. Correct app
3、lication of the simplex method problem solving is able to improve the accuracy, in order to carry out reasonable planning arrangements, makes the effect or income reached expectations or optimization. Keywords:simplex method;simplex tableau;optimality 目 录 1 引言引言 .1 2 文献综述文献综述 .1 2.1 国内外研究现状.1 2.2 国内
4、外研究现状评价.2 2.3 提出问题.2 3 单纯形法的相关概念及原理单纯形法的相关概念及原理 .2 3.1 线性规划问题解的相关概念.2 3.2 初始基可行解的确定.4 3.3 最优性检验与解的判定.4 4 单纯形法的计算单纯形法的计算 .5 4.1 单纯形表的计算步骤.5 4.1.1 单纯形表.5 4.1.2 计算步骤.7 4.2 人工变量.9 4.2.1 大 M 法.10 4.2.2 两阶段法.12 4.3 单纯形法的改进对偶单纯形法.15 5 单纯形法在实际问题中的应用单纯形法在实际问题中的应用 .17 6 结论结论 .19 6.1 主要发现.19 6.2 启示.19 6.3 局限性.
5、19 6.4 努力方向.20 参考文献参考文献 .21 1 1 引言 线性规划问题算运筹学中比较早开始研究,在研究过程中发展比较快,在现实生 活和学术领域应用比较广泛,研究、解决方法比较成熟的一个不可缺少的分支,随着社 会的发展,线性规划也成了人们在解决问题时应用的一种数学方法,它主要应用于数 学管理问题的解决中.例如社会经济、交通选择、工业、农业生产等活动中.人们为了 提高回报或收益从而对已有的人力、资源、物力等进行合理的的规划安排,使得效果 或收益达到期待化或最优化. 在解决线性规划问题时,通常应用的方法有图像法和单纯形法等.而应用最多、最 有效的方法为单纯形法.单纯形法是一种解决线性规划
6、问题的有效方法,它的应用原理 方法为:把线性规划问题的解的可实施部分看做一个维向量空间中的凸集,由此nRn 可得线性规划问题存在最优值那么此最优值只能在凸集的顶点处.既然最优值在顶点处, 我们就把所有顶点看做一个集合,先在这个集合里面挑选出一个顶点的值,对它进行 判别,判别是否为最优值;如果判别结果不是最优值,那么就用一些方法把这个顶点 的值转换为另外一个更可能为最优值的顶点值,依次进行判别,因为顶点有限,所以 都可以转换出最终的结果,从而达到解决问题的要求,线性规划问题中没有最优的解 也可以利用单纯形法进行计算判别. 因此,单纯形法对于解决线性规划有非常重要的地位.单纯形法是一种解决线性规
7、划的方法,只有在线性规划问题中才能更好展现,在本文中,我首先就单纯形法所涉 及到的一些线性规划的基本概念、解的定义、专业名词等做出简要说明,然后在典型 的线性规划中充分揭示单纯形法的步骤、方法及应用,旨在开阔人们分析线性规划问 题的思路,加强人们实施实际问题的能力. 2 文献综述 2.1 国内外研究现状 现查阅到的参考文献中,分别就单纯形法的综述及其在解决线性规划问题中的应 2 用做出说明.敖特根、章学仁在1-2中强调单纯形法在线性规划中的产生与发展的重 要性.燕子宗等在3中给出了一种新的原对偶单纯形法.郭照庄等在4-5中详细阐述 单纯形法的基本原理.赵娜、唐帅等在 6-7中针对如何使用大 M
8、 法和两阶段法实现某 一线性目标最优化问题作出详细说明.胡运权在文献8中针对单纯形法的基本知识和 应用做出阐述文献9中,马振华举例说明单纯形法在解决不同线性规划问题中的应 用及规律.文献10中刘红英等对单纯形法的计算机算法进行了说明邓成梁等在11- 15中对单纯形法的迭代步骤与解的讨论进行研究,而且也对单纯形法的具体求解做出 的研究. 2.2 国内外研究现状评价 文献1-15分别就单纯形法的解题步骤及单纯形法在线性规划问题解题中的意义 举例作了说明,文献中主要阐述一种或几种单纯形法在线性规划解题中的应用,没有 全面地介绍常用单纯形法在不同线性规划问题的应用及解题步骤,而且文献中对怎样 应用单纯
9、形法解决线性规划问题提及甚少,对应用中存在的问题也未给出详细深入的 说明,以及遇到现实问题时,单纯形法的具体用法及计算机应用方法未有太多涉及. 2.3 提出问题 单纯形法的在线性规划中有广泛的应用,但是大部分书本只介绍了一些基础知识 或讲解线性规划时一带而过. 因此,除对解决线性规划问题过程中被一带而过单纯形 法作出介绍外,还需要对应用单纯形法解决问题过程中可能遇到的困难、不理解及解 决办法作出探讨,包括对使用不同单纯形法的目的、作用、要求作阐述体会在不同 题中单纯形法的不同应用,总结概括以指导方便快捷地解决问题 3 单纯形法的相关概念及原理 3.1 线性规划问题解的相关概念 线性规划问题是需
10、要用单纯形法解决的一类问题,所以我们在研究讨论单纯形法 3 时是基于线性规划的基础之上,利用单纯形法使线性规划问题简单、清楚的得出结果 是我们的最终目的.一般线性规划问题化为标准式是利用单纯形法求解线性规划问题的 基本步骤,对于单纯形法能否顺利得出结果,也有很大联系,在解题过程中,应该谨 记变量,目标函数,约束条件的相关要求. :线性规划问题的标准形式为 目标函数 1 max n jj j zc x 约束条件 1 1, . . 01, n ijji j j a xb im st xjn 我们不难看出上式的三个特点: (1)有决策变量:.0;1, j xjm (2)有目标函数,:,一般多用.两者
11、可以互换,即. maxmin或maxmaxminzz (3)有约束条件,通常为等式,对于“”或“”型的约束条件,可以添加变量转 换成等式约束条件,添加的变量称为松弛变量,在目标函数中,松弛变量相对应的系 数为 0.例如: 1231234 45154515xxxxxxx 1231235 2632026320 xxxxxxx 在利用单纯形法进行计算时,对于线性规划的解的相关概念也需要牢记,在接下 来的单纯形法格式中,是以基本概念的求解为基础.线性规划解的概念对于不同元素的 换入、换出等都有影响.下面将介绍线性规划问题解的概念: 1、可行解:,称为线性规划问题的可可以满足全部约束条件的解 1, ,
12、T n Xxx 行解.可行解的集合,称为可行域. 2、最优解:最符合题目要求的解,在可行域中,能够使目标函数取得最大值的可 行解称为最优解.最优解一定是可行解. 3、基:设 A阶系数矩阵(设) ,基为 A 的满秩子矩阵为约束方程组的m nnm 4 矩阵.m m 4、基可行解:,最优解一定是基可行满足变量非负约束条件的基解叫做基可行解 解. 5、可行基:对应于基可行解的基称为可行基. 3.2 初始基可行解的确定 我们说单纯形法是一种迭代算法.所以我们在迭代时需要确定每一次迭代的对象, 特别是在进行第一次迭代前,我们必须确定好对象才能使单纯形法的迭代顺利进行.第 一次迭代的对象我们称为初始基可行解
13、.为了确定初始基可行解,首先要找出初始可行 基.找出初始可行基的方法为: (1)有的线性规划问题中能直接观察得到一个初始可行基: 12 100 010 ,. 001 m Ba aa (2)如果所有约束条件是“”的不等式,在化为标准形式后,可以 重新对变量和 变量系数进行编号,得到一个的单位矩阵m m 12 100 010 ,. 001 m Ba aa 此时单位矩阵 可作为可行基.再将标准形式下的约束条件移项为 在同一B 12 , m x xx 边的等式,再令 ,可得,就此得到一个初 12 0 mmn xxx 1,2, ii xb im 始基可行解. 12 ,0,0 T m n m Xb bb
14、(3)如果所有约束条件是“ ”的不等式,及等式约束情况不存在单位矩阵时,就 采用人工造基方法.即对不等式约束中减去一个非负的变量后,再加上一个非负的人工 变量;对于等式约束一样加上一个非负的人工变量,就可以得到一个单位矩阵. 5 3.3 最优性检验与解的判定 线性规划问题解的结果有以下四种情况:唯一最优解、无穷多最优解、无界解和 无可行解.在用单纯形对线性规划进行迭代的过程中,对于什么样的情况使得线性规划 有解或无解、什么样的情况线性规划达到最优,这就需要进行最优性检验与解的判定. 所以对于线性规划的解需要建立判定准则. (1)最优解的判定 设 为一个基可行解,并且对于一切 都有检 0 12
15、,0,0 T m Xb bb1,jmn 验数,则可以判定在该线性规划问题中 max1,2,0 jkkjj czzcjn 0 X 为最优解. (2)无穷多最优解的判定 设为一个基可行解,并且对于一切都有检验 0 12 ,0,0 T m Xb bb1,jmn 数,同时又存在某个非基变量的检验数max1,2,0 jkkjj czzcjn ,则可以判定该线性规划问题有无穷多最优解.0 m k (3)无界解的判定 设为一个基可行解,有检验数,并且对于 0 12 ,0,0 T m Xb bb0 m k 有 则判定该线性规划问题有无界解也称之为无最优解.1,2,im , 0 i m k a 4 单纯形法的计
16、算 利用单纯形表时,我们首先要了解什么是单纯形表,它有什么样的特点、规则等, 其次,因为线性规划问题的多样性,我们针对不同类型的问题给出不同方法的单纯形 法帮助我们更快的解决问题,例如人工变量法,对偶单纯形法等. 4.1 单纯形表的计算步骤 用单纯形法求解线性规划问题时,正确、熟练的应用单纯形表能给我们带来更多 的便捷计算.下面将介绍单纯形表的计算使用方法以及进一步的讨论单纯形法的其他方 6 法应用. 4.1.1 单纯形表 单纯形表是为了便于展现单纯形法中各种计算关系、使计算过程规范简单不杂乱 所设计出的一种计算表格.它的功能、表达方式与增广矩阵类似,接下来,将为大家详 细介绍单纯形法中的重要
17、步骤单纯形表. 已知线性规划问题的标准形式为 1 max n jj j zc x 1 1, . . 01, n ijji j j a xb im st xjn 为了在下面的运算中便于观察进行迭代,我们可以先将上述的线性规划问题的形式改 写成增广矩阵的形式 121 1,11 2,12 ,1 121 0100 0010 0001 10 mmn mn mn m mmn mmn zxxxxxb aab aab aab ccccc 已知,所以它与的系数构成一个基,z 不参加基变换 12 , m x xx 换将 变换为零,即即可以采用行初等变 12 , m c cc,使对应的系数矩阵为单位矩阵 121 1
18、,11 2,12 ,1 1,1 111 0100 0010 0001 1000 mmn mn mn m mmn mmm mii mniinii iii zxxxxxb aab aab aab cc acc acb 根据上面的增广矩阵设计出以下单纯形表 7 j c 1 c m c 1m c n c B C 基 b 1 x m x 1m x n x 1 2 m c c c 1 2 m x x x 1 2 m b b b 1 0 0 0 0 1 1,1 2,1 ,1 m m m m a a a 1 2 n n mn a a a jj cz 0 0 1,1 1 m mii m i cc a 1 m n
19、iin i cc a 此表为初始单纯形表,在基列填入基变量,例如 ;在 列中填入基变量 12 , m x xx B C 的价值系数,例如,它们与基变量相对应;列中填入约束方程组右端的常 12 , m c ccb 数;行中填入基变量的价值系数 ;最后一行为检验数行,对应各非基变 j c 12 , n c cc 量 的检验数.每迭代一次可构成一个新的单纯形表. j x 4.1.2 计算步骤 对于单纯形法,我们已经对其中的重点,单纯形表做出了基本说明,在我们了解 了单纯形表的规格、用法等,现在我们对单纯形表的计算步骤加以说明整理. (1)根据目标方程,约束条件建立初始单纯形表. (2)找出初始可行基
20、,确定初始基可行解. (3)算出非基变量 的检验数是否大于零. j x (4)若检验数全部小于等于零,则可停止计算,若检验数有大于零,取最大的检验数 所对应的 为换入变量,以 为换出变量,重新列出单纯形法,进行 j xmin0 i ik ik b a a 迭代. 8 下面用一个例题对单纯形表的应用做进一步说明. 例 1 用单纯形表解下面线性规划问题. 12 max25zxx 1 2 12 12 4 3 . . 28 ,0 x x st xx x x 解:先将此线性规划问题化为标准式: 12345 max25000zxxxxx 13 14 125 12345 4 3 . . 28 ,0 xx x
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 单纯 及其 应用
链接地址:https://www.31doc.com/p-10798516.html