单纯形法的表格解法

单纯形法原理及步骤

单纯形法，求解线性规划问题的通用方法。单纯形是美国数学家G.B.丹齐克于1947年首先提出来的。它的理论根据是：线性规划问题的可行域是 n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。

单纯形法是从某一基可行解出发，连续地寻找相邻的基可行解，直到达到最优的迭代过程，其实质是解线性方程组。

概述：

根据单纯形法的原理，在线性规划问题中，决策变量（控制变量）x1，x2，…x n的值称为一个解,满足所有的约束条件的解称为可行解。使目标函数达到最大值（或最小值）的可行解称为最优解。这样，一个最优解能在整个由约束条件所确定的可行区域内使目标函数达到最大值（或最小值）。求解线性规划问题的目的就是要找出最优解。

最优解可能出现下列情况之一：①存在着一个最优解；②存在着无穷多个最优解；③不存在最优解，这只在两种情况下发生，即没有可行解或各项约束条件不阻止目标函数的值无限增大（或向负的方向无限增大）。

单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。

２０１３年第１５卷第６期　总第１２３期　巢湖学院学报　Ｊｏｕｒｎａｌ　ｏｆ　Ｃｈａｏｈｕ　Ｃｏｌｌｅｇｅ　Ｇｅｎｅｒａｌ　Ｓｅｒｉａｌ　Ｎｏ．１　２３　

基于单纯形算法的表格求解法的研究及应用　

陈淼超　陈侃　

（巢湖学院数学系，安徽　巢湖　２３８０００）　

摘　要：单纯形法是解决线性规划问题的重要方法之一，表格直接求解法则是单纯形法中最　

直接有效的方法。本文主要研究了线性规划中的单纯形算法的表格直接求解法，并且通过所　给算例验证了表格求解法的可行性与有效性。　

关键词：可行域；凸集；单纯形；最优解；初始基可行解　中图分类号：Ｏ２２１．１　文献标识号：Ａ　文章编号：１６７２—２８６８（２０１３）０６—０００１—０５　

１　引言　随着社会的不断进步，人类对各种资源的需求不断提高，这将会导致资源的不断匮乏，提高产能效　

率成为现今人们亟待解决的问题。因此，线性规划作为运筹学的重要分支之一被越来越多地涉及，它在　工农业生产、经济管理、交通运输等经济活动占据着举足轻重的地位。通常情况下，我们通过两种途径　

来提高产能效率。第一种方法：通过不断的技术革新来提高产能效率。例如通过使用新设备和研究新型　

原材料，改善生产工艺等。第二种方法：通过统筹的安排和组织生产来提高产能效率，即合理安排人力　物力资源。线性规划所研究的内容就是：在一定条件所限制下，合理整合各方面资源，找到一个最优的　

方案，使产能效率达到最高。　线性规划发展到今天，经历了很长的一段历程，早在ｌ８３２年，法国数学家Ｊ．－Ｂ．一Ｊ．傅里叶就提出　了线性规划的概念，遗憾的是在当时并未引起重视。直到１９４７年，美国数学家Ｇ．Ｂ．丹齐克提出单纯形　

法Ｉ１．　，线性规划这门学科才得到空前的发展。单纯形算法为这门学科奠定了坚实的基础。５０年代后期，　许多专家学者对线性规划进行大量的理论研究，并相应的涌现出一大批新的算法。例如，ｌ９５４年Ｃ．莱　

姆基提出对偶单纯形法。同年，Ｓ．加斯和Ｔ．萨迪等人解决了线性规划的灵敏度分析和参数规划问题，Ｊ９５　６年Ａ．塔克提出互补松弛定理，１９６０年Ｇ．Ｂ．丹齐克和Ｐ．沃尔夫提出分解算法等。我国对线性规划的研　

单纯形法及其应用

摘 要

单纯形法是一种主要的解决线性规划问题的方法，它在生活的成本问题、交通选择或规划学术问题等方面得到广泛应用.本文系统的研究了单纯形法的相关概念以及原理.并阐述了用单纯形法解决线性规划问题的步骤与方法及不同方法的特殊性.正确的应用单纯形法解决问题能够提高准确率，从而进行合理的规划安排，使得效果或收益达到期待化或最优化.

关键词：单纯形法；单纯形表；最优性

The Simplex Method and its Application

Abstract: Simplex method is a main to solve linear programming problems, 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

application 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.（10分）用单纯形法求解以下线性规划问题。

 3215812xxxMaxZ

s.t:0,,48412112023321321321321xxxxxxxxxxxx

解：先化为标准型：Max3215812xxxZ

s.t.0,,,,,48412112023321321332123211321sssxxxsxxxsxxxsxxx (1分)

（以下三步迭代每步2分，指出最优解、最优值1分。）

迭代次数

基变量 BC 1x 2x 3x 1s 2s 3s b 比值

12 8 5 0 0 0

1s 0 3 2 1 1 0 0 20 20/3

2s 0 1 1 1 0 1 0 11 11

0 2s 0 12* 4 1 0 0 1 48 4

jz 0 0 0 0 0 0 0z

j 12 8 5 0 0 0