第7讲线性规划与单纯形法

本章要求：◎掌握线性规划的数学模型及其建模步骤．◎掌握线性规划的图解法．◎认识线性规划的标准型，掌握转化为标准

型的方法．◎掌握单纯形法与单纯形表；掌握人工变量

方法的使用．当前1页，总共156页。线性规划（LinearProgramming．简记为LP）是管理科学研究方法的一个重要部分，是管理科学研究方法中研究较早，发展较快，理论上比较成熟和应用上极为广泛的一个部分，它已成为帮助各级管理人员进行决策的一种十分重要的工具．传统的管理只注重定性分析，已远远不能适应当今社会发展的需要．现代化管理要求采用定性分析和定量分析相结合的方法，一切管理工作要力求做到定量化、最优化，于是就产生了各种各样的管理优化技术．在诸多的管理优化技术中，线性规划是目前最常用而又最为成功的一种．当前2页，总共156页。其原因有三：一是应用广泛．管理工作中的大量优化问题可以用线性规划的模型来表达；二是模型较为简单，容易建立，容易学习和掌握；三是求解方法和理论基础较为成熟．1939年前苏联数学家康托洛维奇（L．V．Kantrovich）在《生产组织与计划中的数学方法》一书中，首次提出了线性规划问题，成为最早研究这方面的问题学者．当前3页，总共156页。线性规划是数学规划问题中的一种．以后我们会看到，还有所谓整数规划、非线性规划等．这里的规划（Programming）是指计划的意思．在规划前面冠以“线性”二字，则是因为这类规划问题的数学模型是线性的数学表达式．一个实际问题的数学模型，是依据客观规律，对该问题中我们所关心的那些变量进行科学的分析后所得出的反映这些量之间本质联系的数学关系式．但一般说来，我们在工业、农业、交通运输、国防等方面所遇到的实际问题是很复杂的，它们涉及的因素很多，要想建立包罗各种因素的数学模型，不仅不可能（因有的数量关系根本无法弄清楚），也没有必要．当前4页，总共156页。到1947年，美国学者丹捷格（）提出了线性规划问题的一般解法——单纯形法，为线性规划的理论发展奠定了基础，尤其是1979年哈奇安首次提出求解线性规划问题的一个多项式算法——椭球算法．1984年卡玛卡（N.Karmarkar）提出了解线性规划问题的一个更为有效的一种新的内点算法，使得线性规划的理论发展趋于成熟．60多年来，随着电子计算机的发展，线性规划已广泛应用于工业、农业、商业、交通运输、经济管理和国防等各个领域，成为现代化管理的有力工具之一．当前5页，总共156页。§2.1什么是线性规划当前6页，总共156页。一个可行的办法是择其主要者，加以讨论之．虽然，一般说来，模型粗一点，它不太精确，而模型细一点，对实际事物的描述要准确一些，但后者带来的问题是：或者在理论上难以处理，或者在计算时工作量太大，耗费昂贵．所以，应根据实际问题的具体情况，抓住主要矛盾，来建立既能保证精确度要求，又尽量简单的数学模型．实际的线性规划问题一般都很复杂，为了使读者易于掌握建立线性规划模型的方法，开始我们所选的例子都经过了大大简化，只要弄懂了这些简单的模型，今后遇到较为复杂的问题也就有办法了．当前7页，总共156页。在生产实践中，任何一个企业可供利用的资源（如人力、物力、财力等）是有限的。如何运用现有的资源安排生产，使产值最大或利润最高；或者，对于给定的任务，如何统筹安排以便消耗最少的资源．这是一个问题的两个方面，就是寻找在一定条件下，使某个指标达到最优的问题。根据实际问题的要求，可以建立线性规划问题数学模型来解决这类问题，而建立线性规划数学模型则是用线性规划解决问题时最基本的步骤．线性规划问题由目标函数、约束条件以及变量的非负约束三部分组成．下面我们通过管理实践中的两个具体实例来说明这类问题，并建立它们的数学模型．当前8页，总共156页。

产品单位消耗原料AB原料限制（吨）钢124铁408橡胶046单位产品利润（万元）23一、线性规划问题的具体实例例2.1生产计划问题某工厂计划在下一个生产周期内用钢、铁、橡胶三种原料生产A、B两种产品，其有关资料见表2.1.问该工厂在下一周期内应如何安排生产计划，使得既能充分利用现有原料，又使总利润最大？当前9页，总共156页。解：这里所说的生产计划问题是指要制定出两种产品的产量．显然，可行的生产计划是很多的，比如可以只生产A型产品，也可只生产B型产品，也可两种产品都生产．通常一个企业的生产中有多种不同的产品组合，而每一种产品组合又有大量的不同的数量组合．每个这样的组合都是一个生产计划．要从这许许多多个（有时甚至是无穷多个）生产计划中确定出哪个是最优的（既是企业获利最多的），这是个非常困难的问题，传统的经济分析方法在此无能为力．现在我们我们看看这里是怎样解决这个问题的．当前10页，总共156页。第一步，选定决策变量，即决策人可控制的因素．确定合适的决策变量是能否成功地建立数学模型的关键．本例中，可令决策变量x1

,x2

分别表示下一生产周期A、B两种产品的产量．第二步，确定问题的目标，即决策人用来评价问题的不同方案优劣的标准．这种目标总是决策变量的函数，称为目标函数．本例中，用来表示总利润，目标函数就是使总利润达到最大．我们用“Max”（是“maximize”的省略写）表示“最大”，于是得到目标函数当前11页，总共156页。第三步，根据选定决策变量给出限制条件，称为约束条件．是用来描述完成目标，决策变量受到各种限制的等式或不等式．本例中，为了完成目标总利润最大，根据选定决策变量，由于原料钢、铁、橡胶都是有限的，故决策变量x1

,x2

必须满足下列条件：当前12页，总共156页。另外，根据实际问题的需要和计算方面的考虑，还对决策变量x1

,x2

加上非负限制，即

综上所述，我们将例2.1的实际问题用数学模型描述成：求x1,x2使得

其中，“s.t.”是“subjectto（受约束于）”的省写．这类问题通常称为生产计划问题．当前13页，总共156页。

产品单位消耗原料B1,B2,…,Bn

原料限制（吨）A1A2⋮Ama11a12…a1na21a22…a2n⋮⋮⋮am1am2…amnb1b2⋮bm单位利润（万元）c1c2…cn而“生产计划问题”的一般提法是：

某厂计划在下一个生产周期内用A1,A2,…,Am种原料去生产B1,B2,…,Bn种产品，已知其现有原料的数量和单位产品的原料消耗及其单位产品的利润见表2.2所示：

问该工厂应如何安排生产计划，使得既能充分利用现有原料，又能使总利润最大？当前14页，总共156页。设决策变量xj表示下一个周期产品Bj(j=1,2,…,n)

的产量，则此问题的数学模型可归结为：求xj(j=1,2,…,n)，使得当前15页，总共156页。

食物含量成份甲乙最低需求量（两）A10．100．151．00A21．700．757．50A31．101．3010．00食物单价（元）21．5例2.2食物搭配问题某人每天食甲、乙两种食物（如猪肉、鸡蛋），这两种食物含A1,A2,A3三种营养成分（如维生素、脂肪和蛋白质），已知这两种食物所含三种营养成分的含量（mg），人体每天对这三种营养成分的需求量及这两种食物的单价（元/两）如表2.3所示，问此人对这两种食物各食用多少，才能既满足营养需要又使总花费用最省？当前16页，总共156页。解：设决策变量x1

,x2分别表示此人对甲、乙两种食物的食用量，这必须要求此人一天的食用花费尽可能的最省，即目标函数为：

同时，为了营养需要，变量x1,x2

必须满足下列约束条件：当前17页，总共156页。设决策变量xj(j=1,2,…,n)分别表示此人对这n种食物的食用量，则问题的线性规划模型表示为：求xj(j=1,2,…,n)，使得当前18页，总共156页。综合以上，其数学模型表示为这类问题通常称为食物搭配问题．当前19页，总共156页。具备以上三个共同特点的数学模型称为线性规划模型，相应的问题叫做线性规划问题．以后我们把“线性规划”简写“LP”，它是LinearProgramming的缩写．简单地说，线性规划问题就是求一个线性目标函数在一组线性约束条件下的极值问题，线性规划的数学模型分一般形式和标准形式两种，下面分别介绍，并讨论它们之间的转化．当前20页，总共156页。而“食物搭配问题”的一般提法是：某人每天食用n种食物B1,B2,…,Bn，这n种食物中含A1,A2,…,Amm种营养成分，已知这n种食物中所含m种营养成分的含量、人体每天对这m种营养成分的需求量及这m种食物的单价（元/两）如表2.4所示，问此人对这m种食物各食用多少，才能既满足需要又使总费用最省？

食物含量成份B1,B2,…,Bn

最低需求量（两）A1A2⋮Ama11a12…a1na21a22…a2n⋮⋮⋮am1am2…amnb1b2⋮bm食物单元（元）c1c2…cn当前21页，总共156页。

二、线性规划问题的数学模型上面我们从经济管理领域中建立了两个实际问题的数学模型，这两个问题虽然具体意义各不相同，但从数学模型来看，它们却有一些共同的特点，主要表现在：第一，求一组决策变量(decisionvariables)xj(j=1,2,…,n)，一般这些变量取值是非负的；第二，确定决策变量可能受到的约束，称为约束条件（constraints），它们可以用决策变量的线性等式或不等式来表示；第三，在满足约束条件的前提下，使某个函数值达到最大（如利润、收益等）或最小（如成本、运价、消费等），这种函数称为目标函数(objectivefunction)，它是决策变量的线性函数．当前22页，总共156页。1.线性规划问题的一般形式由以上两个例子，我们可以归纳出线性规划问题的一般形式是：求一组决策变量xj(j=1,2,…,n)使得(2.1)其中cj,aij,bi(i=1,2,…,n)均为已知实常数．式(2.1)称为目标函数，式(2.2)和(2.3)称为约束条件,特别称式(2.3)为非负约束条件．当前23页，总共156页。在线性规划问题中，目标函数是变量的线性函数，约束条件是变量的线性不等式．例如以下的问题就不是线性规划问题：当前24页，总共156页。

2.线性规划问题的标准形式为了便于讨论一般解法，常将线性规划问题的约束条件归结为一组方程和一组非负限制条件，并且对目标函数统一成求最大值，称之为线性规划问题的标准形式：(2.4)(LP)并且假设bi≥0(i=1,2,…,m)

，并简称为(LP)问题．(LP)问题还可以用以下几种形式来表示：当前25页，总共156页。(1)简记形式(2)矩阵形式当前26页，总共156页。

(3)向量形式

其中A=(aij)m×n,C=(c1,C2,…,Cn)，为行向量，X=(x1,x2,…,xn)T为列向量，b=(b1,b2,…,bm)T为列向量．当前27页，总共156页。我们称为约束条件的系数矩阵，简称为约束矩阵，经济上又称为技术矩阵；cj(j=1,2,…,n)为目标函数的系数，又称为价值系数，为价值向量；bi(i=1,2,…,m)为第i个约束条件的右端常数，b为右端向量，经济上又称为资源向量；xj(j=1,2,…,n)为决策变量，X为决策向量；pj(j=1,2,…,n)

为A的第j列向量．线性规划问题的标准形式具有如下特征：（1）目标函数为求极大值问题；（2）所有的约束条件（除非负约束条件外）都是等式，且右端常数均为非负；（3）所有的决策变量均非负．当前28页，总共156页。为了使得我们的讨论能够抓住最主要的内容，而不致被一些次要的枝节问题搅乱视线，我们在这里对标准形式的(LP)问题做如下假设：①秩r(A)=m，且m<n．这就是说，方程组(2.5)中的包含的m个方程式都是彼此独立的，没有多余方程，且方程个数小于未知量个数．这种情况最为常见．若r(A)<m，则说明(2.5)中有多余方程．这时应先去掉多余方程，然后再行求解．②b≥0，即一切bi≥0(i=1,2,…,m)(若有某个bi<0，则可将bi<0所在方程的两边乘以-1)．当前29页，总共156页。今后，我们将在以上假设条件下去讨论标准形式的(LP)问题．对于各种非标准形式的线性规划问题，我们总可以通过以下的变换，将其转化为标准形式．

3.线性规划问题的非标准形转化为标准形将非标准形的线性规划模型转化为标准形，一般要经过以下几步工作：（1）目标函数的转化若目标函数为求极小值，即为由于MinZ=-Mzx(-Z)，从而将目标函数转化成当前30页，总共156页。（2）约束条件的转化约束方程为不等式时，当约束条件为“≤”时，则在其左边加一个非负变量，将不等式转化为等式．这些被加入的非负变量称为松弛变量（slackvariables）；当约束条件为“≥”时，则在其左边减去一个非负变量，也称为松弛变量（或叫剩余变量），将不等式变成等式．由于加进的松弛变量，其物理意义是未被充分利用的资源或处于闲置的资源，因而不能带来价值或利润，故它们在目标函数里的系数定为零．如果约束条件右端的常数项为负数，则将约束条件两边同乘-1，从而将右端常数项变为正数．当前31页，总共156页。（3）决策变量的转化若存在某个决策变量xk≤

0，则可令xk=-x’k，从而用x’k

取代xk，且满足x’k≥

0．如果某决策变量xk为无约束变量，即变量xk取≥

0或≤

0皆可，为了满足标准型对变量的非负要求，可令xk=x’k-x”k

，其中x’k≥

0，x”k≥

0，将其代入模型即可．当前32页，总共156页。例2.3将下列线性规划问题化为标准型解：分下面几步进行：

（1）由于x2≤0，可令x’2=-x2≥0代入(2.16)、(2.17)、(2.18)、(2.19)；（2）由于x3无约束，可令x3=x’3-x”3(x’3≥0,x”3≥0)代入(2.16)、(2.17)、(2.18)、(2.19)中的x3均替换成x’3-x”3；当前33页，总共156页。（3）在式(2.17)的左边加一个非负的松弛变量x4；（4）在式(2.18)的左边减一个非负的松弛变量x5；（5）对式(2.19)两边同乘-1；（6）令Z’=-Z，并将目标函数中各变量的系数均变成其相反数，从而将目标函数转为MaxZ’；（7）令松弛变量在目标函数中的价值系数为零．经过以上变换，得该问题的标准形为：当前34页，总共156页。§2.2求解线性规划问题

的基本原理当前35页，总共156页。阐述这个问题之前，我们先来介绍两个基本概念．对于线性规划问题的标准形定义2.1在(LP)问题中，凡满足所有约束条件（2.11）和（2.12）的解X=(x1,x2,…,xn)T称为(LP)问题可行解（FeasibleSolution），所有可行解的集合称为可行域（FeasibleRegion）（或可行解集），记作S={X|AX=b,X≥

0}．当前36页，总共156页。定义2.2设(LP)问题的可行域为S，若存在X*∈S,使得对于任意的X∈S，都有CX*≥CX,则称X*为(LP)问题的最优解，相应的目标函数值称为最优值，记作Z*，即Z*=CX*．对于给定的(LP)问题，若存在最优解，则称它有解，否则称之为无解．将(LP)问题的每一个可行解代入目标函数Z的表达式中，就可以得到的一个相应的值．一般说来，不同的X对应于不同的Z．求解线性规划问题的根本任务就是要在全部可行解中找出使目标函数取最大或最小（统称最优值）的那个（或那些）可行解，即最优解．当前37页，总共156页。因为在约束方程组中，m<n，故在一般情况下，可行解集D及其边界都是无穷点集，相应地，也就有无穷多个值．要从这无穷多个值中找出一个最大的或最小的，一般来说是不可能的．然而，值得庆幸的是，由于(LP)问题的结构特殊，其可行解集具有一些“很好”的性质（后面将给出），从而实现一个从无限到有限的转化，即从对无穷多个函数值的比较，转化为只需考虑有限多个函数值的情形．下面，我们先从图解法来领会上述思想．当前38页，总共156页。一、图解法对于只有两个变量的线性规划问题，我们可以用在二维直角坐标平面上作图的方法求解，这种方法称为图解法．图解法比较简单、直观，对所给问题也无需化成标准形．图解法的步骤可概括为：在平面上建立直角坐标系；图示约束条件，找出可行域；作出目标函数线；寻找最优解．下面通过实例来说明图解法．当前39页，总共156页。例2.4用图解法求解例2.1．例2.1的数学模型是：解：画出坐标系．以变量x1为横坐标轴，x2为纵坐标轴作平面直角坐标系，并适当选取单位坐标长度．约束条件（2.25）规定了变量只能在第一象限取值，所以绘图时第一象限占较大版面．当前40页，总共156页。图示约束条件，找出可行域．约束条件（2.22）是一个不等式，代表的是以直线x1+2x2=4为边界的左下方的平面，同理分析（2.23）、（2.24）后，加上（2.25），则满足所有约束条件的解（即可行解）组成的区域为多边形OQ4Q3Q2Q1，这一区域称之为可行域，见图2.1，可行域用阴影表示．图2.1当前41页，总共156页。作出目标函数等值线．目标函数Z=2x1+3x2中，z是待定的值，随z的变化，x2=-3/2x1+1/2z是以z为参数、斜率为-3/2的一族平行线，当z值由小变大时，得一族平行线，即目标函数等值线．直线x2=-2/3x1+1/3z(z为参数)沿其法线方向向右上方移动时，离O点越远，z值越大．确定最优解．因最优解是可行域中使目标函数值达到最大的点，因此x1、x2的取值范围只能从凸多边形OQ1Q2Q3Q4中去寻找．当前42页，总共156页。从图2.1中可以看出，当代表目标函数的那条直线由O点开始向右上方移动时，的值逐渐增大，一直移动到当目标函数直线与约束条件包围成的凸多边形相切时为止，切点就是最优解的点．本例中目标函数直线与凸多边形的切点是Q2，该点坐标为．于是可得Z*=2×2+3×1=7．这说明该企业的最优生产计划方案是：生产产品A为2吨，生产B产品为1吨，可使最大总利润达7万元．当前43页，总共156页。由例2.4可以看出，线性规划问题的最优解将出现在可行域的一个顶点上，这是线性规划问题有唯一最优解的情况．但对于一般线性规划问题，求解结果还可能出现以下几种情况：1．唯一解．如例2.4得到的最优解(2,1)就是唯一解．2．多重解．如果将例2.4的目标函数改变为Maxz=2x1+4x2，则目标函数的直线族恰好与约束条件x1+x2≤4的边界线平行．当目标函数向优化方向移动时，与可行域相切的不是一个点，而是在整个线段Q2Q3上相切（见图2.2）．这时线段Q2Q3上的任意点都使z取得相同的最大值，即该线性规划问题有无穷多最优解，也称为有多重解．当前44页，总共156页。这些点都是最优解．(2.26)图2.2图2.2中，Q2

和Q3

的坐标分别是(2,1)、(1,3/2)，则Q2Q3

连线上的一切点可表示成当前45页，总共156页。3．无界解．如果将例2.4的约束条件进行修改后成如下线性规划模型当前46页，总共156页。则此时可行域可伸展到无穷远处，即z的取值可以一直增大到无穷大（见图2.3）．这种情况下问题的最优解无界，称为取得无界解．产生无界解的原因是在建立实际问题的数学模型时，可能遗漏了某些必要的资源约束条件．图2.3当前47页，总共156页。4．无可行解．考察如下线性规划模型用图解法求解时，可以看出不存在满足所有约束条件的公共区域（可行域），见图2.4，我们称这种情况为线性规划问题无可行解．产生无可行解的原因是模型中存在相互之间矛盾的约束条件．图2.4当前48页，总共156页。通过用图解法求解只有两个变量的(LP)问题，我们可以获得某些解一般(LP)问题的重要规律，主要有以下三点：第一，关于解的存在性问题．在求解线性规划问题时，解的情况有：唯一解、多重解、无界解、无可行解四种情况．何时有解？何时无解？何时有多重解？何时无可行解？这些问题在我们学习了单纯形法以后，大体上可以得到解决；第二，关于可行解集的结构问题．从二维情形可见，可行解集的图形它总是向外凸的．这种无论在线性规划的有界集情形，还是无界集情形所表现出来的可行解集的凸性是线性规划的一个基本特性；当前49页，总共156页。第三，关于最优解的获得方法问题．如果线性规划问题有唯一最优解，则其最优解一定在可行域的某个“顶点”得到．如果线性规划问题存在多重最优解，则有两个顶点及其连线上的一切点均取得最优解．第一点已很显然，对于第二、第三点，下面将给出证明．当前50页，总共156页。

二、关于线性规划问题求解的一些基本定理要从无穷多个可行解中找出最优解来，是一件非常困难的工作．此问题的解决建立在一系列重要定理的基础上．我们将从上节获得的几何启示出发，逐步展开这些基本定理．这样，读者便能从中更好地领会到单纯形法产生的整个思路．首先，我们介绍两个基本概念．当前51页，总共156页。定义2.3设E⊂R2．若中任意两点x(1)和x(2)的连线上的一切点仍属于E，即若x(1)∈E,x(2)∈E

，就必有x=αx(1)+(1-α)x(2)∈E(其中0≤α≤1)，则称E为凸集（convexpoint-set）．例如三角形、矩形、四面体、实心圆、实心球等都是凸集，而圆环、圆周不是凸集．图2.5中点集D，E是凸集，F，G不是凸集．图2.5当前52页，总共156页。定义2.4若对于凸集E中的点，不存在经E中两个相异的点x(1)和x(2)

，使下式成立：则称x为E的极点（extremepoint）或顶点．如三角形、矩形、四面体的顶点，圆周上的一切点都是这些图形各自的极点．图2.5中D的边界点都是极点，E的5个顶点也都是极点．现在我们来讨论求解LP问题的一系列基本定理．在本节今后对LP问题作一般性的理论分析中，我们都假定LP问题为标准形式，这点以后不再声明．当前53页，总共156页。约束方程Ax=b可改写成如下形式：其中，称xj为的系数列向量．定理2.1线性规划问题的可行解集（若非空）是凸集．证：按凸集定义，要证可行解集S中任意两点x(1)

和x(2)

连线上的一切点当前54页，总共156页。

仍属于S，亦即要证x仍为可行解．一方面，因x(1)≥0，x(2)≥0，且0≤α≤1，所以，显然有x≥0，即

x满足非负条件．另一方面，由于Ax(1)=b,Ax(2)=b

故有即x满足约束方程．综上，x仍为可行解，证毕．当前55页，总共156页。从前面的图解法中，我们看到极点在求解LP问题中的重要作用，故有必要对其进行仔细研究．下面几个定理就是关于极点的有关结论，但是由于下面几个定理的证明稍微有点复杂，为使读者首先能集中精力掌握求解LP问题的主要思路，此处只叙述这些定理，而将证明放在本章的最后一节．读者在熟悉了单纯形法的具体做法后，再去学习这些证明，将会很受启发．当前56页，总共156页。引理2.1设x∈S,(i)若x=0，则它一定是S的极点．(ii)若x≠0，则它为S之极点的充要条件是x的正分量所对应的系数列向量线性无关．定理2.2若可行解集非空，则其极点所组成的集合也一定是非空．换句话说，只要存在可行解，就一定存在极点．定理2.3极点的个数是有限的．定理2.4若线性规划问题有最优解，则最优解一定可以在极点中找到．或者说，若目标函数有最优值，则最优值必至少在一极点上达到．当前57页，总共156页。这些定理之说以极为重要，之说以被称之为基本定理，是因为它们回答了我们所关心的一系列重大问题．定理2.1回答的是：“LP问题的可行解集具有什么样的几何特征？”答曰：是个凸集．既然是凸集，便可谈及极点．那么，什么样的点才能称为极点？引理2.1解决了这一问题．接着要问：“怎样的可行解集才能有极点呢？”定理2.2做了回答：只要s≠Φ它就有极点．这一定理指出了极点存在的普遍性．当前58页，总共156页。进一步要问：“极点的个数有多少呢？”定理2.3的回答是：有限个．这一回答虽不具体，却是原则性的，联系定理2.4便可知其意义重大．最后一个定理（定理2.4）解决的是“极点与最优解究竟有何关系？”答曰：极点中就有最优解．因此，我们要想找出最优解，只需考察各个极点（它们是有限个）即可，而不必在整个可行解集或其边界所包含的无穷多个点中一一检查了．为了给出寻找极点的具体方法，我们再从求解方程组的角度讨论几个概念．当前59页，总共156页。

三、基、基解和基可行解设一般线性规划问题的标准形为考察由约束方程的系数矩阵A的全部列向量构成的向量组P={p1,p2,…,pn}．因r(A)=m，所以，P的极大无关组含有m个线性无关的向量．由引理2.1，可知中的线性无关向量对确定极点起很重要的作用．为此，引进如下的定义．当前60页，总共156页。定义2.5在问题(LP)中，约束方程组（2.28）的系数矩阵A的任意一个m×m阶的非奇异的子方阵B（即|B|≠0又称满秩矩阵），称为线性规划问题的一个基（basis）或基矩阵（basismatrix）．这就是说，基矩阵B是由矩阵A中任一m个线性无关的列向量组成，不失一般性，可设当前61页，总共156页。并称pi(i=1,2,…,m)为基向量，与基向量pi相应的变量xi(i=1,2,…,m)为基变量；不在B中的列向量pj(j=m+1,…,n)我们称为非基向量，与非基向量pj相应的变量xj(j=m+1,…,n)为非基变量．并记非基向量则系数矩阵A可以写成分块形式(2.30)当前62页，总共156页。将基变量和非基变量组成的向量分别记为

则向量X也可以写成分块形式(2.31)再将式（2.30）和（2.31）代入约束方程组（2.28）,得即又因为B是非奇异方阵，所以B-1存在，将上式两边同乘B-1，移项后得(2.32)当前63页，总共156页。这里可将XN看作一组自由变量（又称独立变量），给它们任意一组值，则由上式（2.32）可得对应的XB的一组值，于是便是约束方程（2.28）的一个解。特别地，令时，则，我们把约束方程组的这种特殊形式的解(2.33)称为基解，具体定义如下：当前64页，总共156页。定义2.6在约束方程（2.28）中，对于任意选定的基B，令所有的非基变量等于零，即XN=0，得到的解（2.33）称为相应的基B的基解（basicsolution）．因为基B是A的一个m×m阶的非奇异方阵，即它的列是从A的n列中选出的线性无关的m列，其选法最多共有

种，故基的个数最多是个，于是一个线性规划问题的基解最多也是个．当前65页，总共156页。基解满足约束方程组（2.28），但不一定满足非负约束条件（2.29），于是又有下面的定义．定义2.7在基解（2.33）中，若XB=B-1b≥

0，则称此基解称为一基个可行解（basicfeasiblesolution）．这时对应的基B称为可行基（feasiblebasic）．显然，一个线性规划问题的基可行解的个数最多也不会超过个．当前66页，总共156页。另外，由于矩阵A的秩为m，故对于选定的可行基B，基变量共有m个，非基变量共有n-m个，对应的基可行解中非零分量的个数至多为m个，如果非零分量个数等于m(即所有基变量取值均为正)，则称该基可行解为非退化的基可行解

（nondegenertionbasicfeasiblesolution）；

如果非零分量个数小于(即存在取零值的基变量)，则称该基可行解为退化的基可行解（degenertionbasicfeasiblesolution）．当前67页，总共156页。根据以上的分析，我们不加证明地给出以下定理：定理2.5线性规划的基可行解就是可行域的极点．由此可知，前面关于极点的许多结果都可以转到基可行解上来，比如我们有：只要存在可行解，就一定存在基可行解；基可行解的个数是有限的；若LP问题有最优解，则最优解一定可以在基可行解中找到．当前68页，总共156页。结合前面的定理来说，我们有如下重要结论：LP问题如果有最优解，则最优解必可在基可行解中找到，而基可行解的个数是有限的．因此，我们只需要在有限多个基可行解中去寻找最优解．下一节将讲到的单纯形法，就是根据这些原理构思出来的．当前69页，总共156页。§2.3线性规划的单纯形法当前70页，总共156页。线性规划的单纯形法（SimplexAlgorithm）是求解线性规划问题的基本方法之一，这是美国学者丹捷格(G．B．Dantzig)于1947年提出来的，1953年又对其进行改进，成为改进单纯形法．1954年，贝尔(Beale)提出了对偶单纯形法，使其单纯形法更为完善．大量的实际应用表明，这是一种行之有效的方法．从上面的讨论可知，若线性规划问题有最优解，则一定可以在基可行解上达到，单纯形法就是建立在这个理论基础上的．它的基本思想是：首先从可行域中找到一个基可行解，然后判断它是否为最优解，若是则停止计算；当前71页，总共156页。否则，就找一个更好的基可行解，再进行检验，如此反复经过有限次迭代，直到找到最优解，或者判定它无界（即无有限最优解）为止．下面，我们通过一个计算实例来说明单纯形法的基本原理．一、单纯形法的基本原理例2.5求解例2.1．当前72页，总共156页。解：先引入松弛变量x3,x4,x5将问题化成标准形：(2.34)第一步：找出初始可行基，确定初始基可行解．约束方程（2.35）的系数矩阵当前73页，总共156页。其中(P3,P4,P5)为一单位矩阵，因而(P3,P4,P5)构成一个基，记作同时确定x3,x4,x5为初始基变量，x1,x2为初始非基变量．分别用，表示．将式（2.35）变换后可得(2.37)当前74页，总共156页。为使目标函数值增加得快一些，可选择正系数中最大的那个非基变量为进基（我们后面将这一规则称为“σ规则”）．由于max{2,3}=3是非基变量x2的系数，因此确定x2为进基．但基变量的个数是一定的（等于系数矩阵A的秩m），于是还要确定从原基变量x3,x4,x5中哪一个换出来作为非基变量（称为“岀基”）．为此我们进行如下分析．当前75页，总共156页。

令x1=x2=0可得初始基可行解这个基可行解表示的经济意义是：工厂没有安排生产产品A和B，三种资源也没有被利用，此时，工厂的利润指标Z(0)=0．那么这个解是不是最优解呢？第二步：最优性检验．将式（2.37）代入目标函数式（2.34）内可得(2.38)当前76页，总共156页。从式（2.38）可知，首先，目标函数中不含基变量x3,x4,x5；其次，非基变量x1,x2的系数都是正数，如果将其中一个变量，例如x1（或x2）由非基变量换为基变量（称为“进基”），则x1（或x2）的取值可以由零变成正值，就会使目标函数的值增大．从而可以断定初始基可行解x(0)并不是最优解．从经济意义上讲，安排生产产品A（或B），都可以使工厂的利润指标增加．所以，只要不含基变量的目标函数的表达式（2.38）中有非基变量的系数为正，就表示目标函数值还有改进可能．当前77页，总共156页。第三步：换基迭代．当确定了x2作为进基之后，必须要从x3,x4,x5中换出一个作为出基，并保证其余的均为非负．由于x1仍为非基变量，令x1=0，则式（2.37）变成(2.38)分析式（2.38）可知，只有当x2的取值不超过min(4/2,-,6/4)=3/2时，才能满足非负条件．当x2=3/2时，最小比值6/4对应的基变量x5=0．即x5由基变量变成了非基变量，也就是用x2去替换x5．这一过程称为“换基”（我们后面将这一规则称为“θ规则”）．当前78页，总共156页。从经济意义上讲，由于每生产一件产品B，需要耗掉钢、铁、橡胶三种原料数分别为2吨，0吨，4吨，当确定生产产品B的产量为3/2件时，则需要消耗钢、铁、橡胶三种原料数分别为3吨，0吨，6吨，这说明原料橡胶已全部用完．因此，由这些原料中的薄弱环节橡胶的供应量确定了产品B的产量不超过3/2件．这充分体现了岀基的选择兼顾各种限制条件的思想，所以又称为最小比值法则．经过上述换基以后，新的基变量，新的非基变量为．将当前的基变量x3,x4,x2用非基变量x1,x5表示．即将（2.35）式中的x5与x2的位置对调后，可得当前79页，总共156页。式（2.39）可变换成(2.39)(2.40)令x1=x5=0可得将（2.40）代入式（2.34）可得(2.41)当前80页，总共156页。从式（2.41）中可知，由于x1前的系数为2>0，所以X(1)

仍不是最优解．且在目标函数（2.41）中，只有非基变量x1的值增加才可以使目标函数值Z增加，选择非基变量x1为进基，另一个非基变量x5=0保持不变，则式（2.40）变成(2.42)分析式（2.42）可知，只有当x1的取值不超过min{1/1,8/4,-}=1时，才能满足非负条件．此时最小比值1/1对应的基变量为x3，这就决定了用x1去替换x3

，将式（2.40）中的x1与x3的位置对调后，可得当前81页，总共156页。令x3=x5=0可得(2.43)将式（2.43）代入式（2.34）可得(2.44)由（2.44）式可知，x5前的系数为1/4>0，继续进行“换基”得新的基可行解当前82页，总共156页。而此时目标函数的表达式是(2.45)

由于（2.45）式中所有非基变量x3,x4

的系数都是负数，则表示X(3)已是最优解．最优解中x1=2,x2=1表示A产品生产2个单位，B产品生产1个单位．x3=0,x4=0,x5=2表示原料钢没有富余，原料铁已没有富余，原料橡胶有富余量2单位．在（2.45）式中，令x3=x4=0,，可得z=7，表示按照最佳生产方案生产可获最大利润为7万元．

对照图解法，可以很清楚地了解利用单纯形算法求解线性规划问题所获得的结果．初始基可行解X(0)=(0,0,4,8,6)T相当于图2.2中的原点O(0,0)；当前83页，总共156页。X(1)=(0,3/2,1,8,0)T相当于Q4=(0,3/2)；

X(2)=(1,3/2,0,4,0)T

相当于Q3=(1,3/2)；

X(3)=(2,1,0,0,2)T

相当于Q2=(2,1)．从初始基可行解X(0)开始迭代，依次得到X(1)

、X(2)

、X(3)

，这相当于图2.2中的目标函数平移时，从O点开始，首先碰到Q4，然后碰到Q3，最后到达Q2．当前84页，总共156页。

二、最优性检验与解的判别一般而言，对已化成标准型式的线性规划问题，只要从系数矩阵中能直接观察到一个单位矩阵，则即可得到一个初始基可行解，如果不能直接找到单位矩阵，则可通过添加人工变量来求解，这一方法将在本章下一节中讨论．得到初始基可行解后，要检验一下是否是最优解．如果是，则停止迭代；如果不是，则要继续迭代．每次迭代后，都要检验一下是否是最优解，进一步还要判断属于解的哪一种情况，为此，需要建立对解的判别准则．当前85页，总共156页。将式（2.46）代入目标函数(2.46)可得(2.47)一般情况下，经过迭代后，有当前86页，总共156页。令，式（2.47）变换成再令σj=cj-zj(j=m+1,m+2,…,n)，代入式（2.48）可得(2.48)(2.49)

由于判别基可行解是否为最优解，是看其对应的目标函数中非基变量xj

前的系数σj是否均满足σj≤0(j=m+1,…,n)，因而我们将σj称为检验数．根据σj判别各种解的准则是：当前87页，总共156页。（1）最优解及唯一解判别准则：若

X*=(b1’,b2’,…,bm’,0,…,0)T为对应于基B的一个基可行解，且对应于一切j=m+1,…,n有σj≤0，则X*为最优解．如果对一切j=m+1,…,n均有σj<0，则X*为唯一解．（2）多重解判别准则：若

X*=(b1’,b2’,…,bm’,0,…,0)T为对应于基B的一个基可行解，对应于一切j=m+1,…,n均有σj≤0

，且σj中至少有一个非基变量的σx满足σj=0

，则该线性规划问题有多重解．当前88页，总共156页。（3）无界解判别准则：若

X(0)=(b1’,b2’,…,bm’,0,…,0)T为一基可行解，且存在一个σk>0

，并且对i=1,2,…,m有a’i,k≤

0

，那么该线性规划问题具有无界解．（4）无可行解的判别将在本章下节进行讨论．

当前89页，总共156页。

三、单纯形列表算法

（1）找出初始可行基，确定初始基可行解，建立初始单纯形表．

（2）检查对应于非基变量的检验数

，若所有σj≤0，且存在可行解（判别方法在下节中给出），则已得到最优解，停止计算．如果在所有σj>0的σj

中，有一个σK

对应于xK

的系数列向量PK≤0，即对i=1,2,…,m

，均有a’i,K≤0，则此问题有无界解，停止计算；否则转（3）．当前90页，总共156页。（3）进行基变换．换入变量的确定采取σ

规则．令则选择xK

作为换入变量．换出变量的确定采取θ

规则．令这里a’iK

为换入变量xK

的系数列向量中的元素．选择xi

为换出变量．当前91页，总共156页。（4）将a’iK

作为主元素进行旋转运算（即用高斯消去法进行迭代运算），把xK

所对应的列向量从而得到一个新的基可行解，重复（2）~（4），直到终止．当前92页，总共156页。前面利用单纯形法的基本原理求解线性规划问题，其计算过程显得比较繁琐，现在我们介绍一种单纯形的列表算法，这一方法可以直观而清楚地表明计算过程．对标准形的线性规划问题

不妨设m×m阶的非奇异方阵B

是(LP)问题的一个基，为讨论方便，不妨假设A=(B，N)，则方程组（2.51）可等价地变换为当前93页，总共156页。由于B

是非奇异方阵，故B-1

存在，有XB+B-1NXN=B-1b

，移项得(2.53)再将目标函数（2.50）作相应的变换，将它用非基变量来表示当前94页，总共156页。则(LP)问题又可等价地写成：我们称式（2.54）~（2.56）为问题(LP)对应于基B

的典式．当前95页，总共156页。在式（2.53）中令XN=0

（即全部非基变量取值为零），则得XB=B-1b

，当XB=B-1b≥0时，

就是初始基

B

对应的初始基可行解．令

σN=CN-CBB-1N,显然，σN

就是非基变量XN

的检验数．这样，我们可以根据(LP)问题的典式列出一张初始表，称为初始单纯形表．见表2.5.当前96页，总共156页。表2.5C

→CB

CNCBXBbXBXNCBXBB-1bIB-1NZ-CBB0CN-CBB-1N当前97页，总共156页。又因为并记其中，于是，表2.5还可简化为表2.6.当前98页，总共156页。表2.6C

→CCBXBbXCBXBB-1bB-1AZ-CBBC

-CBB-1A表2.5的具体表示形式为表2.7.当前99页，总共156页。Cj

→C

1…C

mC

m+1…C

nθiCBXBbx1…xmxm+1…xnc1x1b11…0a1,m+1…a1nθ1c2x2b20…0a2,m+1…a2nθ2…………………………cmxmbm0…1am,m+1…amnθmCj–Zj0…0…表2.7当前100页，总共156页。其中：XB

列为基变量，这里是x1,x2,…,xm

；CB

列中为基变量的价值系数，这里是c1,c2,…,cm

；它们随基变量改变而改变，并与基变量相对应；b

列中为约束方程组右端的常数；cj

行中为所有变量的价值系数c1,c2,…,cn

；θi

列的数字是在确定换入变量后，按θ

规则计算的相应的θ

值；最后一行称为检验数行，对应各非基变量xj

的检验数是

，即cj-zj=σj(j=m+1,…,n)表2.7称为初始单纯形表，每迭代一次构造一个新单纯形表．当前101页，总共156页。现在我们结合例题来说明如何利用单纯形列表算法求解线性规划问题．解：（1）根据例2.1的标准形，取松弛变量x3,x4,x5

为基变量，它对应的单位矩阵为初始基．这时可以得到一个初始基可行解

X(0)=(0,0,4,8,6)T

，将相关数字填入表中，得到初始单纯形表，见表2.8．当前102页，总共156页。表2.8中的左上角的Cj

是表示目标函数中各变量的价值系数，在表的CB

列中，填入初始基变量的价值系数，它们都是0，检验数行各非基变量的检验数为当前103页，总共156页。（2）因σ1=2,σ2=3,都大于零，且P1、P2

、

的坐标有正分量存在，转入下一步．（3）因为max(σ1,σ2)=max(2,3)=3，所以x2

为换入变量．因为3/2对应x5

这一行，所以x5

为换出变量.当前104页，总共156页。（4）以

x5

所在行与

x2

所在列的交叉元素[4]为主元素，进行旋转运算，即将P2

变换为(0,0,1)T

，在XB

列中将x5

替换为x2

，得到新表2.9．当前105页，总共156页。b

列的数字是x3=1,x4=8,x2=3/2.于是得到新的基可行解x(1)=(0,3/2,1,8,0)T

.目标函数的取值Z=9/2

．（5）检查表2.9中的所有

σj

，因为

σ1

为2，说明

x1

应为换入变量，重复（2）~（4）的计算步骤，得表2.10．当前106页，总共156页。当前107页，总共156页。（6）表2.10最后一行的所有检验数都已为负或零，这表示目标函数已不可能再增大，于是得到最优解X*=X(3)=(2,1,0,0,2)T

，目标函数值Z*=7．当前108页，总共156页。§2.4人工变量法当前109页，总共156页。前面所举的单纯形法的例子中，化为标准形后约束条件的系数矩阵中含有单位矩阵，以此作初始可行基，使求初始基可行解和建立初始单纯形表都十分方便．但对所有约束条件是“≥”形式的不等式及等式约束情况，添加松弛变量后，尚不能构造单位矩阵，这时，我们采用人造基方法，即对不等式约束减去一个非负的剩余变量后，再加上一个非负的人工变量；对于等式约束直接加上一个非负的人工变量，总能得到一个单位矩阵，这些变量没有实际意义，纯粹是出于一种处理方法的需要，故称它们为人工变量法（artificialvariables）．当前110页，总共156页。设线性规划问题为在约束条件

中，分别给每一个约束方程加入一个非负的人工变量xn+1,…,xn+m

，得到当前111页，总共156页。以xn+1,…,xn+m

为基变量，并可得到一个m×m阶的单位矩阵，令非基变量x1,…,xn

为零，便可得到一个初始基可行解X(0)=(0,0,…0,b1,b2,…,bm)T

．当前112页，总共156页。因为人工变量是后加入到原约束条件中的虚拟变量，要求将它们从基变量中逐个替换出来．若经过基的变换，基变量中不再含有非零的人工变量，这表示原问题有解；若在最终单纯形表中当所有检验数cj-zj≤0，而在基变量中还有某个非零人工变量，这表示无可行解．下面我们来介绍人工变量法的两种方法——大M

法和两阶段法.当前113页，总共156页。

一、大M法在一个线性规划问题的约束条件中加进人工变量后，要求人工变量对目标函数取值不受影响，为此假定人工变量在目标函数中的系数为（-M）（M

为任意大的正数），这样目标函数要实现最大化时，必须把人工变量从基变量中换出，否则目标函数不可能实现最大化．根据以上分析，作辅助问题：当前114页，总共156页。再对(LP’)问题用单纯形法求解即可．(LP’)和(LP)有如下的关系：定理2.6若(LP’)有最优解(x1*,…,x*n+m)T

，则当x*n+1=…=x*n+m=0时，((x1*,…,xn*)T

即为(LP)之最优解；否则(LP)无可行解．

（证明从略）当前115页，总共156页。例2.7用单纯形法求解线性规划问题解：在上述问题的约束条件中加入松驰变量x4,x5

,，人工变量x6,x7

,，得到当前116页，总共156页。其中M

是一个任意大的正数．解：在上述问题的约束条件中加入松驰变量x4,x5

，人工变量x6,x7

，得到当前117页，总共156页。该模型中构成单位矩阵的变量x4,x6,x7

为基变量，令非基变量x1,x2,x3,x5

等于零，即得到初始基可行解X(0)=(0,0,0,4,0,1,9)T

，并列出初始单纯形表．在单纯形法迭代运算中，M

可当作一个数学符号一起参加运算．检验数中含

M

符号的，当M的系数为正时，该检验数为正，当

M

的系数为负时，该项检验数为负．例2.7中添加人工变量后，用单纯形法求解的过程见表2.11．当前118页，总共156页。(下页续表)当前119页，总共156页。最后可得：X*=(0,5/2,3/2,0,0,0,0)T,MaxZ=-3×0+1×3/2=3/2

。当前120页，总共156页。

二、两阶段法由于在大M

法中引入了一个很大的正数M

，因此在计算机求解时，可能会产生较大的舍入误差，故实际问题中常采用两阶段法．这种方法是将加入人工变量后的线性规划问题分为两个阶段来求解.下面我们仍就标准形(LP)问题进行讨论．设线性规划问题为当前121页，总共156页。第一阶段：令辅助问题中的目标函数仅为各人工变量的负值之和，即作辅助问题：显然xn+1,…,xn+m

可以作为辅助问题(LP”)的一个初始基变量．因f有上界，且可行解集是闭集，故f

的最优值f*

必然存在，且f≤0

．当前122页，总共156页。定理2.7(LP)

有可行解的充分必要条件是(LP”)的最优值f*=0．（证明略）在具体解题时，用得较多的是下述推论：推论若f*<0，则(LP)无可行解；若

f*=0，则(LP)有可行解．第二阶段：从第一阶段所求得的初始可行基和初始基可行解出发，继续求解原(LP)

问题，得到原(LP)问题的最优基和最优解．当f*=0时，分两种情形考虑：情形一，若(LP”)的最优基B”中不含人工变量，则B”

即为(LP)的一个可行基；情形二，若B”

中含有人工变量，此时情况较为复杂，下面我们通过例题来说明其解法．当前123页，总共156页。例2.8用两阶段法解上面的例2.7.解：引进松弛变量x4,x5≥0

，得到当前124页，总共156页。增加人工变量

x6,x7≥0，构造辅助问题，并进入第一阶段求解．当前125页，总共156页。用单纯形法求解，得到第一阶段问题的计算表,见下表2.12.当前126页，总共156页。最优解X*=(1,3,0,0,0,0,0)T

，最优值f=0.第一阶段最后一张最优表说明找到了原问题的一组基可行解，将它作为初始基可行解，求原问题的最优解即第二阶段问题为当前127页，总共156页。从表2.12中的最后一张表出发，将表2.12中的人工变量

x6

、x7

所在的列除去，将目标函数的系数替换为MaxZ=-3x1+x3

中的系数，再继续用单纯形法计算，求解过程见表2.13.当前128页，总共156页。-3当前129页，总共156页。检验数σj≤0

，最优解为：X*=(0,5/2,3/2,0,0,0,0)T

，最优值Z*=3/2.不难看出，上面两种计算方法的每一步迭代的结果类似，最后结果相同．在第二阶段计算时，初始表中的检验数不能引用第一阶段最优表的检验数，必须换成原问题的检验数，用代入法或公式计算．另外即使第一阶段最优值为零，只能说明原问题有可行解，第二阶段问题不一定有最优解，即原问题可能无界．当前130页，总共156页。前面我们已经给出了唯一解、多重解、无界解的判别准则，在学习了人工变量法之后，我们就可以给出无可行解的判别准则．无可行解的判别准则：当线性规划问题中添加人工变量后，用人工变量法求解，如果迭代到某单纯形表已满足所有非基变量的σj≤0，但基变量中仍含有非零的人工变量,则该线性规划问题无可行解．前面我们已经学习了求解线性规划问题的几种方法，掌握了这些方法之后，我们就可以解决任意型的线性规划模型了．现在我们对前面的内容做一个简单的小结，并给出几个需要进一步说明的问题．当前131页，总共156页。

（1）对给定的线性规划问题应首先化为标准形式，选取或构造一个单位矩阵作为基，求出初始基可行解并列出初始单纯形表．对各种类型线性规划问题如何化为标准形式及如何选取初始基变量可参见表2.14．当前132页，总共156页。当前133页，总共156页。当前134页，总共156页。（2）线性规划的求解过程可用如下框图表示：图2.6单纯形法计算步骤框图当前135页，总共156页。

（3）目标函数为取极小化解的最优性判别，只需将原来要求检验数σj≤0

改成σj≥0

即可．

（4）按θ

规则来确定换出变量时如果存在两个相同的最小比值θi

，则在下一轮单纯形表的基可行解中即有可能出现一个或多个基变量等于零的退化解．退化解的原因是模型中存在多余的约束，使多个基可行解对应同一顶点．当存在退化解时，就有可能出现迭代计算的循环，从而永远迭代不到最优解．为此，1974年勃兰德（Bland）提出了一个简便而有效的原则：当前136页，总共156页。第一，当存在多个σj>0时，始终选择下标最小的变量作为换入变量；第二，当计算

θ

值出现两个以上相同的最小比值时，始终选取下标最小的变量作为换出变量．当前137页，总共156页。§2.5案例分析当前138页，总共156页。【案例2.1】合理下料问题．现要做100套钢架，每套由长2.8m、2.2m和1.8m的元钢各一根组成，已知原材料长6.0m，问应如何下料，可以使原材料最省？当前139页，总共156页。解：由于要裁成的三种元钢的总长度是2.8m+2.2m+1.8m=6.8m，超过了原材料6m的长度．因此，我们容易实现的裁法是：在原材料上分别裁下2.8m、2.2m的元钢各一根，这样要100根原材料才能裁到100根2.8m、2.2m的元钢．再来考虑如何裁得1.8m的元钢，由于一根原材料可以裁得3根1.8m的元钢，这样要裁得100根1.8m的元钢，就需要原材料34根．采取上述裁法需134原材料方可裁得2.8m、2.2m、1