研究生学习课件管理运筹学 管理运筹：第5章单纯形法.ppt

《研究生学习课件管理运筹学 管理运筹：第5章单纯形法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、多媒体教学课件(05)南京财经大学工商管理学院李时椿管理运筹学1单纯形法基本原理单纯形法的表格形式目标函数为最小值的单纯形法单纯形法解的讨论第五章线性规划单纯形法21939年苏联数学家康托罗维奇在《生产组织与计划中的数学方法》一书中提出线性规划问题﹐并未引起重视。1947年美国数学家丹捷格﹐G.B.提出线性规划的一般数学模型和求解线性规划问题的通用方法──单纯形法﹐为这门学科奠定了基础。1947年美国数学家诺伊曼﹐J.von提出对偶理论﹐开创了线性规划的许多新的研究领域﹐扩大了它的应用范围和解题能力。线性规划的发展1975年以前，诺贝

2、尔经济学奖的获得者几乎都是西欧北美的经济学家。1975年，苏联学者列昂尼德·康托罗维奇却获得了此项殊荣。他之所以获得这项资金，是因为他把资源最优利用这一传统的经济学问题，由定性研究和一般的定量分析推进到现实计量阶段；对现代经济应用数学的重要分支——线性规划方法的建立和发展，做出了开创性的贡献。31951年美国经济学家T.C.库普曼斯结合列昂惕夫的投入产出分析，把线性规划应用到经济领域﹐为此与康托罗维奇一起获1975年诺贝尔经济学奖。50年代后对线性规划进行大量的理论研究﹐并涌现出一大批新的算法。例如﹐1954年C.莱姆基提出对偶单纯形

3、法﹐1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题﹐1956年A.塔克提出互补松弛定理﹐1960年丹捷格﹐G.B.和P.沃尔夫提出分解算法等。线性规划的发展4线性规划的研究成果还直接推动了其它数学规划问题包括整数规划﹑随机规划和非线性规划的算法研究。由于数字电子计算器的发展﹐出现了许多线性规划软件﹐如MPSX﹐OPHEIE﹐UMPIRE等﹐可以很方便地求解几千个变量的线性规划问题。规划线性的发展5第五章单纯形法§1单纯形法的基本思路和原理§2单纯形法的表格形式§3求目标函数值最小的线性规划的问题的单纯形表解法

4、§4几种特殊情况6§1单纯形法的基本思路和原理单纯形法的基本思路：从可行域中某一个顶点开始，判断此顶点是否是最优解，如不是,则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。通过第二章例1的求解来介绍单纯形法:在加上松弛变量之后我们可得到标准型如下：目标函数：max50x1+100x2约束条件：x1+x2+s1≤300，2x1+x2+s2≤400，x2+s3≤250.xj≥0（j=1，2）,sj≥0（j=

5、1，2,3）7它的系数矩阵,其中pj为系数矩阵A第j列的向量。A的秩为3,A的秩m小于此方程组的变量的个数n，为了找到一个初始基本可行解，先介绍以下几个线性规划的基本概念。基：已知A是约束条件的m×n系数矩阵，其秩为m。若B是A中m×m阶非奇异子矩阵（即可逆矩阵），则称B是线性规划问题中的一个基。基向量：基B中的一列即称为一个基向量。基B中共有m个基向量。非基向量：在A中除了基B之外的一列则称之为基B的非基向量。基变量：与基向量pi相应的变量xi叫基变量，基变量有m个。§1单纯形法的基本思路和原理8非基变量：与非基向量pj相应的变

6、量xj叫非基变量，非基变量有n－m个。由线性代数的知识知道，如果我们在约束方程组系数矩阵中找到一个基，令这个基的非基变量为零，再求解这个m元线性方程组就可得到唯一的解了，这个解我们称之为线性规划的基本解。在此例中我们不妨找到了为A的一个基，令这个基的非基变量x１，s2为零。这时约束方程就变为基变量的约束方程：§1单纯形法的基本思路和原理9x2+s1≤300，x2=400，x2+s3=250.求解得到此线性规划的一个基本解：x1=0，x2=400，s1=－100，s2=0，s3=－150由于在这个基本解中s1=－100，s3=－1

7、50，不满足该线性规划s1≥0，s3≥0的约束条件，显然不是此线性规划的可行解，一个基本解可以是可行解，也可以是非可行解，它们之间的主要区别在于其所有变量的解是否满足非负的条件。我们把满足非负条件的一个基本解叫做基本可行解，并把这样的基叫做可行基。§1单纯形法的基本思路和原理10一般来说判断一个基是否是可行基，只有在求出其基本解以后，当其基本解所有变量的解都是大于等于零，才能断定这个解是基本可行解，这个基是可行基。那么我们能否在求解之前，就找到一个可行基呢？也就是说我们找到的一个基能保证在求解之后得到的解一定是基本可行解呢？由于在线性

8、规划的标准型中要求bj都大于等于零，如果我们能找到一个基是单位矩阵，或者说一个基是由单位矩阵的各列向量所组成（至于各列向量的前后顺序是无关紧要的事）例如，那么显然所求得的基本解一定是基本可行解，这个单位矩阵或由单位矩阵各