第二章线性规划的标准型与单纯形法2

运筹学的概况最优化模型教学计划与方法考试与要求参考文献

绪

论当前1页，总共121页。运筹学的由来与发展运筹学的性质与特点

运筹学的主要内容运筹学的发展趋势运筹学的学科地位运

筹

学

概

况当前2页，总共121页。名称的由来

OperationResearch运筹帷幄“史记”运作研究发展历程

运筹学的由来与发展二战以前萌芽二战期间产生五六十年代发展七八十年代成熟当前3页，总共121页。引入数学方法解决实际问题

--定性与定量方法结合系统与整体性--从全局考察问题应用性--源于实践、为了实践、服务于实践交叉学科--涉及经济、管理、数学、工程和系统等多学科开放性--不断产生新的问题和学科分支多分支--问题的复杂和多样性运筹学的性质与特点当前4页，总共121页。线性规划数学规划非线性规划整数规划动态规划学科内容多目标规划双层规划组合优化最优计数问题网络优化排序问题统筹图随机优化对策论排队论库存论决策分析可靠性分析运筹学的主要内容当前5页，总共121页。成熟的学科分支向纵深发展新的研究领域产生与新的技术结合与其他学科的结合加强传统优化观念不断变化运筹学的发展趋势当前6页，总共121页。1在数学学科中的地位运筹数学1在系统科学中的地位系统工程1在管理科学中的地位管理与运筹学1与经济学的关系问题与方法1与工程科学的关系方法与应用1与计算机科学的关系核心算法与工具基础理论应用理论应用技术运筹学运筹学的学科地位当前7页，总共121页。教学计划

数学规划以线性规划和整数规划及动态规划为讲授重点，组合优化部分主要讲图与网络优化，而随机优化讲授排队论部分作为选讲内容。教学方法

以授课为主，讲课中主要培养用最优化方法解决实际问题的能力。教学计划与方法当前8页，总共121页。考核内容及方式

理论方法—期末考试

60%

理论方法—期中考试20%

平时成绩20%考试与要求当前9页，总共121页。韩伯棠，管理运筹学，

高等教育出版社，北京，2000年徐光辉等，运筹学手册，

科学出版社，北京，1999年胡运权等，运筹学教程，

清华出版社，北京，1998年刘家壮，王建方，网络最优化，

华中工学院出版社，武汉，1987年管梅谷，郑汉鼎，线性规划，

山东科学技术出版社，济南，1983年参考资料当前10页，总共121页。运筹学OperationsResearchChapter2线性规划LinearProgramming2.1LP的数学模型

MathematicalModelofLP2.2图解法

GraphicalMethod2.3标准型

StandardformofLP2.4基本概念

BasicConcepts2.5单纯形法

SimplexMethod当前11页，总共121页。2.1数学模型

MathematicalModel当前12页，总共121页。问题的提出：

在生产管理的经营活动中，通常需要对“有限的资源”寻求“最佳”的利用或分配方式。有限资源：劳动力、原材料、设备或资金等最佳：有一个标准或目标，使利润达到最大或成本达到最小。有限资源的合理配置有两类问题：如何合理的使用有限的资源，使生产经营的效益达到最大；在生产或经营的任务确定的条件下，合理的组织生产，安排经营活动，使所消耗的资源数最少。当前13页，总共121页。

与规划问题有关的数学模型总有两部分组成：约束条件：反映了有限资源对生产经营活动的种种约束，或者生产经营必须完成的任务；目标函数：反映生产经营者在有限资源条件下希望达到的生产或经营的目标。当前14页，总共121页。例１

某制药厂生产甲、乙两种药品，生产这两种药品要消耗某种维生素。生产每吨药品所需要的维生素量，所占用的设备时间，以及该厂每周可提供的资源总量如下表所示：

已知该厂生产每吨甲、乙药品的利润分别为5万元和2万元。但根据市场需求调查的结果，甲药品每周的产量不应超过4吨。问该厂应如何安排两种药品的产量才能使每周获得的利润最大？当前15页，总共121页。

定义x1为生产甲种药品的计划产量数，x2为生产乙种药品的计划产量数。目标：使总利润Z=5x1+2x2

极大化约束：每周资源总量的限制，30x1+20x2≤160

5x1+x2≤15甲种药品每周产量不应超过4吨的限制

x1≤4计划生产数不可能是负数，x1≥0x2≥0当前16页，总共121页。数学模型为

s.t.

（subjectto)(suchthat)这是一个如何合理的使用有限的资源，使生产经营的效益达到最大的数学规划问题。在满足一组约束条件的限制下，寻求决策变量x1，x2的决策值，使目标函数达到最大值。当前17页，总共121页。例２

某化工厂根据一项合同要求为用户生产一种用甲、乙两种原料混合配制而成的特种产品。已知甲、乙两种原料都含有A、B、C三种化学成分，两种原料分别所含三种化学成分的百分比含量，以及按合同规定的产品中三种化学成分的最低含量如下表所示：已知甲、乙两种原料的成本分别是每公斤3元和2元，厂方希望总成本达到最小，问如何配置该产品？化学成分当前18页，总共121页。定义x1，x2分别为每公斤产品中甲，乙两种原料的数量，目标：使总成本Z=3x1+2x2

极小化约束：配料平衡条件，x1+x2=1产品中A、B、C三种化学成分的最低含量

12x1+3x2≥4

2x1+3x2≥2

3x1+15x2≥5非负性条件x1≥0,x2≥0化学成分当前19页，总共121页。数学模型：

s.t.

这是一个原料配制问题，是在生产任务确定的条件下，合理的组织生产，使所消耗的资源数最少的数学规划问题。满足一组约束条件的同时，寻求变量x1和x2的值使目标函数取得最小值。化学成分当前20页，总共121页。1．解决问题的目标函数是多个决策变量的线性函数，通常是求最大值或最小值；2．解决问题的约束条件是一组多个决策变量的线性不等式或等式。线性规划数学模型的特征：线性规划数学模型的三要素：决策变量(Decisionvariables);

目标函数(Objectivefunction);约束条件(Constraints);建立一个问题的线性规划模型的一般步骤：确定决策变量；(2)确定目标函数；(3)确定约束条件；(4)确定变量是否有非负约束。2.1线性规划的数学模型MathematicalModelofLP当前21页，总共121页。2.1.2线性规划的一般模型一般地，假设线性规划数学模型中,有m个约束,有n个决策变量xj(j=1,2…,n)，目标函数的变量系数用cj表示,

cj称为价值系数。约束条件的变量系数用aij表示，aij称为工艺系数。约束条件右端的常数用bi表示，bi称为资源限量。则线性规划数学模型的一般表达式可写成2.1线性规划的数学模型MathematicalModelofLP当前22页，总共121页。在实际中一般xj≥0,但有时xj≤0或xj无符号限制。为了书写方便，上式也可写成：

2.1线性规划的数学模型MathematicalModelofLP当前23页，总共121页。2.2图解法

GraphicalMethod当前24页，总共121页。图解法的步骤：1.在直角坐标系中画出可行解集：分别画出满足每个约束包括变量非负要求的区域，其交集就是可行解集，或称可行域；；2.绘制目标函数图形：先过原点作一条矢量指向点(c1,c2)，矢量的方向就是目标函数值增加的方向，称为梯度方向，再作一条与矢量垂直的直线，这条直线就是目标函数图形；3.求最优解：依据目标函数求最大或最小移动目标函数直线，直线与可行域相交的点对应的坐标就是最优解。一般地，先将目标函数直线放在可行域中：若要求最大值，则将目标函数直线沿着矢量方向移动；若要求最小值，则将目标函数直线沿着矢量的反方向移动。2.2图解法TheGraphicalMethod当前25页，总共121页。x1x2O1020304010203040(3,4)(15,10)最优解X=(15,10)最优值Z=85例1.42.2图解法TheGraphicalMethod当前26页，总共121页。246x1x2246最优解X=(3,1)最优值Z=5(3,1)minZ=x1+2x2例2.5(1,2)2.2图解法TheGraphicalMethod当前27页，总共121页。246x1x2246X（2）＝（3,1）X（1）＝（1,3）(5,5)minZ=5x1+5x2例2.6有无穷多个最优解即具有多重解,通解为

0≤α≤1

当α=0.5时Ｘ=(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2)2.2图解法TheGraphicalMethod当前28页，总共121页。246x1x2246(1,2)无界解(无最优解)maxZ=x1+2x2例1.72.2图解法TheGraphicalMethod当前29页，总共121页。x1x2O10203040102030405050无可行解，从而无最优解。maxZ=10x1+x2例2.82.2图解法TheGraphicalMethod当前30页，总共121页。由以上例题可知，线性规划的解有4种形式：

1.有惟一最优解(例1.4、例1.5)2.有多重解(例1.6)3.有无界解(例1.7)4.无可行解(例1.8)1、2情形为有最优解3、4情形为无最优解2.2图解法TheGraphicalMethod当前31页，总共121页。4.通过图解法了解线性规划有几种解的形式；5.作图的关键有三点：

(1)可行解区域要画正确；

(2)目标函数增加的方向不能画错；

(3)目标函数的直线怎样平行移动。下一节：线性规划的标准型2.2图解法TheGraphicalMethod1.什么是线性规划，掌握线性规划在管理中的几个应用例子；2.线性规划数学模型的组成及其特征；3.线性规划数学模型的一般表达式。当前32页，总共121页。2.3线性规划的标准型StandardformofLP当前33页，总共121页。在用单纯法求解线性规划问题时，为了讨论问题方便，需将线性规划模型化为统一的标准形式。2.3线性规划的标准型StandardformofLP线性规划问题的标准型为:1．目标函数求最大值（或求最小值）2．约束条件都为等式方程3．变量xj非负4．常数bi非负当前34页，总共121页。max(或min)Z=c1x1+c2x2+…+cnxn2.3线性规划的标准型StandardformofLP注：本教材默认标准型中目标函数是

max当前35页，总共121页。或写成下列形式：

或用矩阵形式2.3线性规划的标准型StandardformofLP当前36页，总共121页。通常X记为：

,称Ａ为约束方程的系数矩阵，m是约束方程的个数，n是决策变量的个数，一般情况m≤n，且r(Ａ)＝m。其中:2.3线性规划的标准型StandardformofLP当前37页，总共121页。一般形式线性规划模型的标准化准则:（前提bi

≥0

）5.xj≤0令xj

=－x'j,x'j≥0

当前38页，总共121页。【例1】将下列线性规划化为标准型

【分析】(１)因为x3无符号要求，即x3可取正值也可取负值，标准型中要求变量非负，所以令2.3线性规划的标准型StandardformofLP当前39页，总共121页。

(3)第二个约束条件是“≥”号，在“≥”号左端减去剩余变量(surplusvariable)x5，x5≥0，也称松驰变量；2.3线性规划的标准型StandardformofLP(2)第一个约束条件是“≤”号，在“≤”号左端加入松驰变量

(slackvariable)x4，x4≥0,化为等式；(4)第三个约束条件是“≤”号且常数项为负数，因此在“≤”左边加入松驰变量x6，x6≥0，同时两边乘以－1。

(5)目标函数是最小值，为了化为求最大值，令Z′=－Z,得到maxZ′=－Z，即当Z达到最小值时Z′达到最大值。当前40页，总共121页。综合起来得到下列标准型2.3线性规划的标准型StandardformofLP当前41页，总共121页。当某个约束是绝对值不等式时，将绝对值不等式化为两个不等式，再化为等式，例如约束将其化为两个不等式

再加入松驰变量化为等式。

2.3线性规划的标准型StandardformofLP当前42页，总共121页。2.4线性规划的有关概念BasicConceptsofLP当前43页，总共121页。

设线性规划的标准型

maxZ=CX(2.1)AX=b(2.2)X≥0(2.3)式中A是m×n矩阵，m≤n并且r(A)=m，显然A中至少有一个m×m子矩阵B，使得r(B)=m。2.4基本概念BasicConcepts

基

(basis)：A中m×m子矩阵B并且有r(B)=m，则称B是线性规划的一个基(或基矩阵basismatrix)。注：基矩阵B必为非奇异矩阵即|B|≠0。当m=n时，基矩阵惟一，当m<n时，基矩阵就可能有多个，但数目不超过当前44页，总共121页。【例2】线性规划

求所有基矩阵。

【解】约束方程的系数矩阵为2×5矩阵

2.4基本概念BasicConcepts

当前45页，总共121页。容易看出r(A)=2，2阶子矩阵有C52=10个，其中第1列与第3列构成的2阶矩阵不是一个基，基矩阵只有9个，即当前46页，总共121页。当确定某一矩阵为基矩阵时，则基矩阵对应的列向量称为基向量(basicvector)，其余列向量称为非基向量;

基向量对应的变量称为基变量(basicvariable)，非基向量对应的变量称为非基变量；在上例中B2的基向量是A中的第一列和第四列，其余列向量是非基向量，x1、x4是基变量，x2、x3、x5是非基变量。基变量、非基变量是针对某一确定基而言的，不同的基对应的基变量和非基变量也不同。2.4基本概念BasicConcepts

当前47页，总共121页。

可行解(feasiblesolution):

满足式(2.2)及(2.3)的解X=（x1,x2…,xn)T称为可行解；基本可行解(basic

feasiblesolution):若基本解是可行解则称为是基本可行解（也称基可行解）。基本解(basicsolution):对某一确定的基B，令非基变量等于零，利用式(2.2)解出基变量，则这组解称为基Ｂ的基本解。最优解(optimalsolution):满足式(1.1)的可行解称为最优解，即使得目标函数达到最大值的可行解就是最优解；非可行解(infeasiblesolution)

无界解

(unboundedsolution)2.4基本概念BasicConcepts

当前48页，总共121页。显然，只要基本解中的基变量的解满足式(2.3)的非负要求，那么这个基本解就是基本可行解。

在上例中，对Ｂ１来说，x1,x2是基变量，x3,x4，x5是非基变量，令x3=x4=x5=0，则式(2.2)为

因|B1|≠０，由克莱姆法则知，x1、x2有惟一解x1＝2/5,x2=1,从而基本解为2.4基本概念BasicConcepts

当前49页，总共121页。对B2来说，x1,x4,为基变量，令非变量x2,x3,x5为零，由式(2.2)得

，x4=4，则基本解为反之，可行解不一定是基本可行解，如满足式(2.2)~(2.3)，但不是任何基矩阵的基本解。在中x1<0,不是可行解，因此也不是基本可行解。

当前50页，总共121页。可行基:

基可行解对应的基称为可行基；最优基:基本最优解对应的基称为最优基；如上述B3就是最优基，最优基肯定是可行基。2.4基本概念BasicConcepts

基本最优解:

最优解是基本解称为基本最优解。例如满足式(2.1)~(2.3)是最优解,又是B3的基本解,因此它是基本最优解。注：当最优解惟一时，最优解亦是基本最优解，当最优解不惟一时，则最优解不一定是基本最优解。当前51页，总共121页。基本最优解、最优解、基本可行解、基本解、可行解的关系:基本最优解基本可行解可行解最优解基本解2.4基本概念BasicConcepts

当前52页，总共121页。凸集(Convexset):设K是n维空间Rn的一个点集，对任意两点

时，则称K为凸集。

就是以X(1)、X(2)为端点的线段方程,点X的位置由α的值确定,当α=0时,X=X(2),当α=1时X=X(1)。凸组合(Convexcombination)

:设是Rn中的点，若存在使得成立，称X为的凸组合。2.4基本概念BasicConcepts

当前53页，总共121页。极点(Extremepoint)::

设K是凸集，，若X不能用K中两个不同的点的凸组合表示为<)10()1()2()1(<-+=aaaXXX则称X是K的一个极点或顶点。X是凸集K的极点，即X不可能是K中某一线段的内点，只能是K中某一线段的端点。O2.4基本概念BasicConcepts

当前54页，总共121页。【定理2.1】若线性规划可行解集K非空,则K是凸集。

【定理2.2】线性规划的可行解集合K的点X是极点的充要条件为X

是基本可行解。【定理2.3】若线性规划有最优解,则最优值一定可以在可行解集合的某个极点上达到,最优解就是极点的坐标向量。注：定理2.2刻划了可行解集的极点与基本可行解的对应关系，极点是基本可行解，反之，基本可行解一定是极点，但它们并非一一对应，有可能两个或几个基本可行解对应于同一极点(退化基本可行解时)。线性规划的基本定理2.4基本概念BasicConcepts

当前55页，总共121页。

定理2.3描述了最优解在可行解集中的位置，它也表明若线性规划问题有最优解，则必有基本最优解，且若最优解惟一，则最优解只能在某一极点上达到；若具有多重最优解，则最优解是某些极点的凸组合，从而最优解是可行解集的极点或界点，不可能是可行解集的内点。

若线性规划的可行解集非空且有界，则一定有最优解；若可行解集无界，则线性规划可能有最优解，也可能没有最优解；若线性规划具有无界解，则可行域一定无界。

定理2.2及2.3还给了我们一个启示，寻求最优解可不在无限个可行解中去找，而是去有限个基本可行解中去找。下一节将介绍一种有效地寻找最优解的方法。2.4基本概念BasicConcepts

当前56页，总共121页。2.5单纯形法SimplexMethod当前57页，总共121页。

考虑到如下线性规划问题

其中Ａ一个m×n矩阵，且秩为m，ｂ总可以被调整为一个m维非负列向量，Ｃ为n维行向量，Ｘ为n维列向量。根据线性规划基本定理：如果可行域Ｄ={Ｘ∈Ｒn/ＡＸ=ｂ，Ｘ≥0}非空有界，则Ｄ上的最优目标函数值Ｚ=ＣＸ一定可以在Ｄ的一个顶点上达到。这个重要的定理启发了Dantzig的单纯形法，即将寻优的目标集中在D的各个顶点上。单纯形法的一般原理

当前58页，总共121页。

Dantzig的单纯形法把寻优的目标集中在所有基本可行解（即可行域顶点）中。其基本思路是从一个初始的基本可行解出发，寻找一条达到最优基本可行解的最佳途径。单纯形法的一般步骤如下：（1）寻找一个初始的基本可行解。（2）检查现行的基本可行解是否最优，如果为最优，则停止迭代，已找到最优解，否则转一步。（3）移至目标函数值有所改善的另一个基本可行解，然后转到步骤（2）。当前59页，总共121页。确定初始的基本可行解

确定初始的基本可行解等价于确定初始的可行基，一旦初始的可行基确定了，那么对应的初始基本可行解也就唯一确定

为了讨论方便，不妨假设在标准型线性规划中，系数矩阵Ａ中前m个系数列向量恰好构成一个可行基，即Ａ=（ＢＮ），其中Ｂ=（Ｐ1，Ｐ2，…Ｐm）为基变量x1，x2，…xm的系数列向量构成的可行基，Ｎ=(Ｐm+1，Pm+2,…,Pn)为非基变量xm+1,xm+2,…,xn的系数列向量构成的矩阵。当前60页，总共121页。所以约束方程就可以表示为

用可行基Ｂ的逆阵Ｂ-1左乘等式两端，再通过移项可推得：若令所有非基变量,则基变量由此可得初始的基本可行解当前61页，总共121页。问题：要判断m个系数列向量是否恰好构成一个基并不是一件容易的事。基由系数矩阵Ａ中m个线性无关的系数列向量构成。但是要判断m个系数列向量是否线性无关并非易事。即使系数矩阵Ａ中找到了一个基B，也不能保证该基恰好是可行基。因为不能保证基变量ＸB=Ｂ-1b≥0。为了求得基本可行解，必须求基Ｂ的逆阵Ｂ-1。但是求逆阵Ｂ-1也是一件麻烦的事。结论：在线性规划标准化过程中应设法得到一个m阶单位矩阵I作为初始可行基Ｂ，当前62页，总共121页。若在化标准形式前，约束方程中有“≥”不等式，那么在化标准型时除了在方程式左端减去剩余变量使不等式变成等式以外，还必须在左端再加上一个非负新变量，称为人工变量．若在化标准形式前，约束方程中有等式方程，那么可以直接在等式左端添加人工变量。为了设法得到一个m阶单位矩阵I作为初始可行基Ｂ，可在性规划标准化过程中作如下处理：

若在化标准型前，m个约束方程都是“≤”的形式，那么在化标准型时只需在一个约束不等式左端都加上一个松弛变量xn+i(i=1,2,…,m)。当前63页，总共121页。判断现行的基本可行解是否最优

假如已求得一个基本可行解将这一基本可行解代入目标函数，可求得相应的目标函数值

其中分别表示基变量和非基变量所对应的价值系数子向量。当前64页，总共121页。

要判定是否已经达到最大值，只需将代入目标函数，使目标函数用非基变量表示，即：

其中称为非基变量ＸN的检验向量，它的各个分量称为检验数。若σN的每一个检验数均小于等于0，即σN≤0，那么现在的基本可行解就是最优解。当前65页，总共121页。定理1最优解判别定理对于线性规划问题若某个基本可行解所对应的检验向量，则这个基本可行解就是最优解。定理2

无穷多最优解判别定理若是一个基本可行解，所对应的检验向量，其中存在一个检验数σm+k=0，则线性规划问题有无穷多最优解。当前66页，总共121页。基本可行解的改进

如果现行的基本可行解Ｘ不是最优解，即在检验向量中存在正的检验数，则需在原基本可行解Ｘ的基础上寻找一个新的基本可行解，并使目标函数值有所改善。具体做法是：先从检验数为正的非基变量中确定一个换入变量，使它从非基变量变成基变量（将它的值从零增至正值），再从原来的基变量中确定一个换出变量，使它从基变量变成非基变量（将它的值从正值减至零）。由此可得一个新的基本可行解，由可知，这样的变换一定能使目标函数值有所增加。当前67页，总共121页。换入变量和换出变量的确定：换入变量的确定—最大增加原则假设检验向量，若其中有两个以上的检验数为正，那么为了使目标函数值增加得快些，通常要用“最大增加原则”，即选取最大正检验数所对应的非基变量为换入变量，即若

则选取对应的为换入变量，由于且为最大，因此当由零增至正值，可使目标函数值最大限度的增加。当前68页，总共121页。换出变量的确定—最小比值原则如果确定为换入变量，方程

其中为Ａ中与对应的系数列向量。现在需在中确定一个基变量为换出变量。当由零慢慢增加到某个值时，的非负性可能被打破。为保持解的可行性，可以按最小比值原则确定换出变量：若则选取对应的基变量为换出变量。当前69页，总共121页。

定理3无最优解判别定理若是一个基本可行解，有一个检验数，但是，则该线性规划问题无最优解。证：令，则得新的可行解将上式代入

因为,故当λ→+∞时，Z→+∞。当前70页，总共121页。用初等变换求改进了的基本可行解

假设Ｂ是线性规划的可行基，则令非基变量，则基变量。可得基本可行解。用逆阵左乘约束方程组的两端，等价于对方程组施以一系列的初等“行变换”。变换的结果是将系数矩阵Ａ中的可行基Ｂ变换成单位矩阵I，把非基变量系数列向量构成的矩阵Ｎ变换成，把资源向量b变换成。当前71页，总共121页。

且改进了的基本可行解只是在Ｘ的基变量的基础上用一个换入变量替代其中一个换出变量，其他的基变量仍然保持不变。这些基变量的系数列向量是单位矩阵I中的单位向量。为了求得改进的基本可行解，只需对增广矩阵施行初等行变换，将换入变量的系数列向量变换成换出变量所对应的单位向量即可。

由于行初等变换后的方程组与原约束方程组或同解当前72页，总共121页。例1解：(１)确定初始的基本可行解。，基变量，非基变量。当前73页，总共121页。(2)检验是否最优。检验向量

因为σ1=3，σ3=4均大于零，所以不是最优解。当前74页，总共121页。（3）基本可行解的改进①

选取换入变量因为max{3，4}=4，取x3为换入变量。②

选取换出变量且，选取x4为换出变量.当前75页，总共121页。（4）求改进了的基本可行解对约束方程组的增广矩阵施以初等行变换，使换入变量x3所对应的系数列向量变换成换出变量x4所对应的单位向量,注意保持基变量x5的系数列向量为单位向量不变。第一行除以２第二行减去第一行当前76页，总共121页。——————————————————————————可得改进的基本可行解。，基变量，非基变量。

基本可行解

目标函数值易见目标函数值比原来的Z=-1增加了，再转向步骤(2)当前77页，总共121页。（2）检验是否最优。检验向量

因为，所以仍不是最优解。当前78页，总共121页。（3）基本可行解的改进①

选取换入变量因为，取为换入变量。②

选取换出变量且，选取为换出变量.当前79页，总共121页。（4）求改进了的基本可行解对约束方程组的增广矩阵施以初等行变换，使换入变量所对应的系数列向量变换成换出变量所对应的单位向量

第二行乘以２/５第一行减以第二行的１/２倍当前80页，总共121页。——————————————————————————可得改进的基本可行解。，基变量，非基变量

基本可行解

目标函数值比Z=15增加了，再转向步骤(2)当前81页，总共121页。（2）检验是否最优。检验向量

因为所有检验数均小于零，所以是最优解，当前82页，总共121页。表格单纯形法

通过例１我们发现，在单纯形法的求解过程中，有下列重要指标：每一个基本可行解的检验向量根据检验向量可以确定所求得的基本可行解是否为最优解。如果不是最优又可以通过检验向量确定合适的换入变量。每一个基本可行解所对应的目标函数值通过目标函数值可以观察单纯形法的每次迭代是否能使目标函数值有效地增加，直至求得最优目标函数为止。

在单纯形法求解过程中，每一个基本可行解Ｘ都以某个经过初等行变换的约束方程组中的单位矩阵Ι为可行基。当Ｂ=Ｉ时，Ｂ-1=Ｉ，易知：当前83页，总共121页。

可将这些重要结论的计算设计成如下一个简单的表格，即单纯形表来完成：当前84页，总共121页。

例2试利用单纯形表求例1中的最优解解：

得初始的单纯形表：初始基本可行解，Z=-1，122108x4-130400-1Z341017x51x1x2x3x4x5bXBCBΘ523-11C当前85页，总共121页。

换入变量，换出变量，２为主元进行旋转变换基本可行解，Z=15，1/2111/204x331-40-2015Z5/230-1/213x51x1x2x3x4x5bXBCBΘ523-11C122108x4-130400-1Z341017x51x1x2x3x4x5bXBCBΘ523-11C8/27/1当前86页，总共121页。

最优解最优值

换入变量，换出变量，５/２为主元进行旋转变换4/1/21/2111/204x331-40-2015Z3/5/25/230-1/213x51x1x2x3x4x5bXBCBΘ523-11C02/513/5-1/517/5x330-26/50-9/5-2/581/5Z16/50-1/52/56/5x15x1x2x3x4x5bXBCBΘ523-11C当前87页，总共121页。例3用单纯形方法求解线性规划问题解：本题的目标函数是求极小化的线性函数，可以令则这两个线性规划问题具有相同的可行域和最优解，只是目标函数相差一个符号而已。

当前88页，总共121页。010103x220012-12x30-010103x224/1101004x303/1010103x40_101004x300000-18Z’100-212x11100-206Z’2/1100-212x50120000Z’8/2120018x50x1x2x3x4x5bXBCBΘ12000C最优解最优值2/23/1-当前89页，总共121页。

因为非基变量x4的检验数σ4=0，由无穷多最优解判别定理，本例的线性规划问题存在无穷多最优解。事实上若以x4为换入变量，以x3为换出变量，再进行一次迭代，可得以下单纯形表：最优解最优值最优解的一般表示式当前90页，总共121页。对于极小化的线性规划问题的处理：先化为标准型，即将极小化问题变换为极大化问题，然后利用单纯形方法求解．直接利用单纯形方法求解，但是检验是否最优的准则有所不同，即：若某个基本可行解的所有非基变量对应的检验数（而不是≤０），则基本可行解为最优解．否则采用最大减少原则（而非最大增加原则）来确定换入变量，即：若则选取对应的非基变量xm+k为换入变量．确定了换入变量以后，换出变量仍采用最小比值原则来确定。当前91页，总共121页。借助人工变量求初始的基本可行解

若约束方程组含有“≥”不等式，那么在化标准形时除了在方程式左端减去剩余变量，还必须在左端加上一个非负的人工变量。因为人工变量是在约束方程已为等式的基础上，人为的加上去的一个新变量，因此加入人工变量后的约束方程组与原约束方程组是不等价的。加上人工变量以后，线性规划的基本可行解不一定是原线性规划的问题的基本可行解。只有当基本可行解中所有人工变量都为取零值的非基变量时，该基本可行解对原线性规划才有意义。因为此时只需去掉基本可行解中的人工变量部分，剩余部分即为原线性规划的一个基本可行解．而这正是我们引入人工变量的主要目的。当前92页，总共121页。借助人工变量求初始的基本可行解

若约束方程组含有“≥”不等式，那么在化标准形时除了在方程式左端减去剩余变量，还必须在左端加上一个非负的人工变量。因为人工变量是在约束方程已为等式的基础上，人为的加上去的一个新变量，因此加入人工变量后的约束方程组与原约束方程组是不等价的。加上人工变量以后，线性规划的基本可行解不一定是原线性规划的问题的基本可行解。只有当基本可行解中所有人工变量都为取零值的非基变量时，该基本可行解对原线性规划才有意义。因为此时只需去掉基本可行解中的人工变量部分，剩余部分即为原线性规划的一个基本可行解．而这正是我们引入人工变量的主要目的。当前93页，总共121页。考虑线性规划问题：为了在约束方程组的系数矩阵中得到一个m阶单位矩阵作为初始可行基，在每个约束方程组的左端加上一个人工变量

可得到：

当前94页，总共121页。————————————————————————

添加了m个人工变量以后，在系数矩阵中得到一个m阶单位矩阵，以该单位矩阵对应的人工变量为基变量，即可得到一个初始的基本可行解这样的基本可行解对原线性规划没有意义的。但是我们可以从X(0)出发进行迭代，一旦所有的人工变量都从基变量迭代出来，变成只能取零值的非基变量，那么我们实际上已经求得了原线性规划问题的一个初始的基本可行解。此时可以把所有人工变量剔除，开始正式进入求原线性规划最优解的过程。当前95页，总共121页。大M法

大M法首先将线性规划问题化为标准型。如果约束方程组中包含有一个单位矩阵I，那么已经得到了一个初始可行基。否则在约束方程组的左边加上若干个非负的人工变量，使人工变量对应的系数列向量与其他变量的系数列向量共同构成一个单位矩阵。以单位矩阵为初始基，即可求得一个初始的基本可行解。为了求得原问题的初始基本可行解，必须尽快通过迭代过程把人工变量从基变量中替换出来成为非基变量。为此可以在目标函数中赋予人工变量一个绝对值很大的负系数-Ｍ。这样只要基变量中还存在人工变量，目标函数就不可能实现极大化。以后的计算与单纯形表解法相同，Ｍ只需认定是一个很大的正数即可。假如在单纯形最优表的基变量中还包含人工变量，则说明原问题无可行解。否则最优解中剔除人工变量的剩余部分即为原问题的初始基本可行解。当前96页，总共121页。例4用大M法求解下面的线性规划问题:解：首先将原问题化为标准型添加人工变量，并在目标函数中分别赋予-Ｍ

当前97页，总共121页。-01-1/2-1/201/21/23/2X2210-1/21/201/2-1/21/2X1-1--110-10011X221/220-1101-11X6-M1/1-110-10011X7-M2/111-100102X6-M001/23/20-1/2-M-3/2-M5/2Z001/21/21-1/2-1/23/2X501+2M0-M2+M00-2-2M2-MZ2/1100110-12X50-12+2M-M-M000-3MZ3/101001003X50X1X2X3X4X5X6X7bXBCBθ-12000-M-MC当前98页，总共121页。01001003X22100110-12X4011-100102X2220-1101-11X40-01-1/2-1/201/21/23/2X221/2/1/210-1/21/201/2-1/21/2X1-1-1000-2-M-M6Z-10101-101X30-30200-2-M-M4Z-10101-101X50001/23/20-1/2-M-3/2-M5/2Z3/2/1/2001/21/21-1/2-1/23/2X50X1X2X3X4X5X6X7bXBCBθ-12000-M-MC最优解最优值当前99页，总共121页。两阶段法

两阶段法引入人工变量的目的和原则与大M法相同，所不同的是处理人工变量的方法。两阶段法的步骤：求解一个辅助线性规划。目标函数取所有人工变量之和，并取极小化；约束条件为原问题中引入人工变量后包含一个单位矩阵的标准型的约束条件。如果辅助线性规划存在一个基本可行解，使目标函数的最小值等于零，则所有人工变量都已经“离基”。表明原问题已经得了一个初始的基本可行解，可转入第二阶段继续计算；否则说明原问题没有可行解，可停止计算。求原问题的最优解。在第一阶段已求得原问题的一个初始基本可行解的基础上，继续用单纯形法求原问题的最优解当前100页，总共121页。例5用两阶段法求解例4中的线性规划问题。解：首先将问题化为标准型添加人工变量x6,x7,并建立辅助线性规划如下：由于辅助线性规划的目标函数是极小化，因此最优解的判别准则应为：当前101页，总共121页。01-1/2-1/201/21/23/2X2010-1/21/201/2-1/21/2X10--110-10011X201/220-1101-11X611/1-110-10011X712/111-100102X6100000110W001/21/21-1/2-1/23/2X50-201-10021W2/1100110-12X500-2110003W3/101001003X50X1X2X3X4X5X6X7bXBCBθ0000011C辅助规划所有检验数：,原问题已得一个初始基本可行解，当前102页，总共121页。由上表可知，通过若干次旋转变换，原问题的约束方程组已变换成包含一个单位矩阵的约束方程组该约束方程组可作为第二阶段初始约束方程组，将目标函数则还原成原问题的目标函数，可继续利用单纯形表求解。当前103页，总共121页。-1000-26Z1001101001-10101231X4X2X3020-302004Z20-11011-100-10101121X4X2X5020001/23/205/2Z1/2/1/2-3/2/1/2

10-1/21/2001-1/2-1/21

001/21/211/23/23/2X1X2X5-120X1X2X3X4X5

bXBCBθ-12000

0C可得最优解，目标函数值maxZ=6，与用大M法的结果完全相同。当前104页，总共121页。单纯形表与线性规划问题的讨论

无可行解

通过大Ｍ法或两阶段法求初始的基本可行解。但是如果在大Ｍ法的最优单纯形表的基变量中仍含有人工变量，或者两阶段法的辅助线性规划的目标函数的极小值大于零，那么该线性规划就不存在可行解。人工变量的值不能取零，说明了原线性规划的数学模型的约束条件出现了相互矛盾的约束方程。此时线性规划问题的可行域为空集。当前105页，总共121页。例6求解下列线性规划问题解：首先将问题化为标准型令，则

故引入人工变量，并利用大M法求解当前106页，总共121页。C

-3-2-1000-M-M

CB

XB

b

X1X2X3X4X5X6X7X8

θ

0-M-M

X4X7X8

643

1111000010-10-101001-100-101

6/1-3/1

Z’

-7M

-6-4M

-15-M

-3+M-2+M-1-2M0-M-M00

0-M-2

X4X7x2

343

1021010-110-10-101001-100-101

3/14/1-

Z’

Z’

-3+M0-3-M0-M-202-M

-3-M-2

X1X7X2

313

1021010-100-3-1-1-1