工程优化方法 第五章

线性规划就是一个线性函数在线性等式或不等式约束条件下的极值问题，是最简单的约束优化问题理论最为成熟、应用最为广泛的一种数学规划方法运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支广泛应用于军事作战、经济分析、经营管理和工程技术等方面为合理地利用有限的人力、物力、财力等资源作出最优决策，提供科学的依据。线性规划的概述当前第1页\共有177页\编于星期日\22点法国数学家傅里叶和瓦莱-普森分别于1832和1911年独立地提出线性规划的想法，但未引起注意。1939年苏联数学家康托罗维奇在《生产组织与计划中的数学方法》一书中提出线性规划问题，也未引起重视。1947年美国数学家G.B.丹齐格提出线性规划的一般数学模型和求解线性规划问题的通用方法--单纯形法，为这门学科奠定了基础。1947年美国数学家J.von诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力。1951年美国经济学家T.C.库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一起获1975年诺贝尔经济学奖。线性规划的发展当前第2页\共有177页\编于星期日\22点50年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法。例如1954年，C.莱姆基提出对偶单纯形法1954年，S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题1956年，A.塔克提出互补松弛定理1960年G.B.丹齐格和P.沃尔夫提出分解算法等1979年苏联数学家哈奇扬提出解线性规划问题的椭球算法，并证明它是多项式时间算法。

线性规划的发展当前第3页\共有177页\编于星期日\22点1984年美国贝尔电话实验室的印度数学家卡马卡提出解线性规划问题的新的多项式时间算法。用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。现已形成线性规划多项式算法理论。线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究。由于数字电子计算机的发展，出现了许多线性规划软件，lingo等，可以很方便地求解几千个变量的线性规划问题。线性规划的发展当前第4页\共有177页\编于星期日\22点线性规划通常解决下列两类问题：当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源(如资金、设备、原标材料、人工、时间等)去完成确定的任务或目标(2)在一定的资源条件限制下，如何组织安排生产获得最好的经济效益(如产品量最多、利润最大)线性规划问题的数学模型当前第5页\共有177页\编于星期日\22点例某企业计划生产甲、乙两种产品。这些产品分别要在A、

B、C、D四种不同的设备上加工。按工艺资料规定，单件产品在不同设备上加工所需要的台时如下表所示，企业决策者应如何安排生产计划，使企业总的利润最大？线性规划问题的应用当前第6页\共有177页\编于星期日\22点解：设x1、x2分别为甲、乙两种产品的产量，则数学模型为：线性规划问题的应用当前第7页\共有177页\编于星期日\22点第五章线性规划本章主要内容：§1线性规划的简介和应用举例§2线性规划的数学模型及图解法§3线性规划的基本概念和基本性质§4单纯形法§5线性规划的对偶理论与对偶单纯形法当前第8页\共有177页\编于星期日\22点目标函数：约束条件：线性规划数学模型的一般形式线性规划问题的数学模型当前第9页\共有177页\编于星期日\22点线性规划问题的数学模型

线性规划的数学模型由三个要素构成决策变量Decisionvariables目标函数Objectivefunction约束条件Constraints当前第10页\共有177页\编于星期日\22点目标函数：约束条件：线性规划问题的数学模型其特征是：(1)问题的目标函数是多个决策变量的线性函数，通常是求最大值或最小值；(2)问题的约束条件是一组多个决策变量的线性不等式或等式。

怎样辨别一个模型是线性规划模型？

从线性规划数学模型的一般形式看当前第11页\共有177页\编于星期日\22点

线性规划问题可能有各种不同的形式。目标函数有实现最大化也有实现最小化的;

约束条件可以是“”、“”、“=”。决策变量有时有非负限制有时没有。为便于今后讨论，我们规定线性规划问题的标准形为：线性规划问题的标准形bi

0(i=1,2,···,m)当前第12页\共有177页\编于星期日\22点线性规划标准形的矩阵形式记c=(c1,c2,···,cn)T

x=(x1,x2,···,xn)T

b=(b1,b2,···,bm)T

A=(aij)m*n线性规划的标准形的其它形式也可写作称A=(aij)m*n是约束方程组的系数矩阵当前第13页\共有177页\编于星期日\22点线性规划标准形的向量形式记c=(c1,c2,···,cn)T,

x=(x1,x2,···,xn)T

b=(b1,b2,···,bm)T

Pj=(a1j,a2j,···,amj)T

j=1,2,···,n

线性规划的标准形的其它形式当前第14页\共有177页\编于星期日\22点线性规划标准形的向量形式记c=(c1,c2,···,cn)T

x=(x1,x2,···,xn)Tb=(b1,b2,···,bm)T

Ai=(ai1,ai2,···,ain)

i=1,2,···,m线性规划的标准形的其它形式当前第15页\共有177页\编于星期日\22点

一般情况下

,为正整数,分别表示约束条件的个数和决策变量的个数,为价值向量,

为决策向量,通常

为已知常数。

实际上，具体问题的线性规划数学模型是各式各样的,需要把它们化成标准型,并借助于标准型的求解方法进行求解。称m为线性规划的阶数,称n为线性规划的维数。线性规划的标准形当前第16页\共有177页\编于星期日\22点

（1）目标函数求最小值；（2）决策变量非负；（3）约束条件都是等式；（4）常数项（右端向量）非负线性规划标准形的特点当前第17页\共有177页\编于星期日\22点如何化成标准形若要求目标函数是:maxz=cTx,

只需将目标函数的最大值变换为求目标函数的最小值,即maxz=min

(-z)。令zˊ=-z,于是得到：

min

zˊ=-cTx。

目标函数的转换当前第18页\共有177页\编于星期日\22点

若约束方程组为不等式约束条件为“”形式的不等式,则在“”号的左边加入非负的松弛变量;把原“”形的不等式变为等式;

约束方程的转换：由不等式转换为等式称为松弛变量相应的松弛变量在目标函数中的价值系数取值为0。如何化成标准形当前第19页\共有177页\编于星期日\22点

约束条件为“”形式的不等式,则可在“”号的左端减去一个非负的剩余变量。

约束方程的转换：由不等式转换为等式称为剩余变量相应的剩余变量在目标函数中的价值系数取值为0。如何化成标准形当前第20页\共有177页\编于星期日\22点

若存在取值无约束的变量，可令

其中：

变量的转换若，可令，显然如何化成标准形当前第21页\共有177页\编于星期日\22点例1:

试将如下线性规划问题化成标准形任何形式的线性规划问题都可以化成标准形。现举例如下：如何化成标准形当前第22页\共有177页\编于星期日\22点解：令x3=x4-x5,x4,x50,

(1)式左端加上非负松弛变量x6

,(2)式左端减去非负剩余变量x7,则可将上述线性规划问题化成如下的标准形:如何化成标准形当前第23页\共有177页\编于星期日\22点例2:

化为标准形。

maxz=2x1+3x2s.t.2x1+2x2≤12

x1+2x2≤84x2≤124x1≤16

x1,x2≥0

解：引进4个新的非负变x3,x4,x5,x6使不等式变为等式,标准形为：minzˊ

=-2x1-3x2+0·x3+0·x4+0·x5+0·x6

s.t.2x1+2x2+x3=12

x1+2x2+x4=184x2+x5=124x1+x6=16

x1,x2,x3,x4,x5,x6≥0如何化成标准型当前第24页\共有177页\编于星期日\22点线性规划问题求解线性规划问题，就是从满足约束条件(2)的方程组中找出一个解，使目标函数(1)达到最大值（或者最小值）。线性规划的图解法线性规划的基本概念当前第25页\共有177页\编于星期日\22点线性规划的图解法线性规划的基本概念

可行解(FeasibleSolution)----任一满足约束条件的一组决策变量的数值；

可行域(FeasibleRegion)----所有可行解组成的集合，也称为可行解集；

目标函数等值线(Objectivefunctionline)----位于同一直线上的点，具有相同的目标函数值。当前第26页\共有177页\编于星期日\22点例3

用图解法求解线性规划问题线性规划的图解法

对于简单的线性规划问题---只有两个决策变量的线性规划问题,我们通过图解法可以对它进行求解。当前第27页\共有177页\编于星期日\22点求图解法的步骤：建立坐标系，将约束条件在图上表示确立可行域绘制目标函数的等值线族，确定目标函数增大和减小的方向确定最优解：当求目标函数的最大值时，沿着目标函数值增大的方向平移等值线，当平移直线刚要离开可行域时的“最后交点”，即为最优解(既满足约束，又使目标函数值最大的点)。当求目标函数的最小值时，沿着目标函数值减小的方向平移等值线，当平移直线刚要离开可行域时的“最后交点”，即为最优解(既满足约束，又使目标函数值最大的点)。线性规划的图解法当前第28页\共有177页\编于星期日\22点x1x2ox1-1.9x2=3.8(≤)x1+1.9x2=3.8(≥)x1-1.9x2=-3.8(≥)x1+1.9x2=11.4(≤)4=2X1+X2

20=2X1+X2

17.2=2X1+X2

11=2X1+X2

Lo：0=2x1+x2

（7.6，2）DmaxZminZ此点是唯一最优解，且最优目标函数值

maxZ=17.2可行域线性规划的图解法建立坐标系，将约束条件在图上表示确立可行域确定最优解：沿着目标函数值增大的方向平移等值线，当平移直线刚要离开可行域时的“最后交点”时，“最后交点”即为最优解。绘制目标函数的等值线族，确定目标函数增大和减小的方向当前第29页\共有177页\编于星期日\22点x1x2ox1-1.9x2=3.8(≤)x1+1.9x2=3.8(≥)x1-1.9x2=-3.8(≥)x1+1.9x2=11.4(≤)（7.6，2）DL0：0=3x1+5.7x2

maxZ（3.8，4）34.2=3x1+5.7x2

蓝色线段上的所有点都是最优解这种情形为有无穷多最优解，但是最优目标函数值maxZ=34.2是唯一的。可行域线性规划的图解法绘制目标函数的等值线族，确定目标函数增大和减小的方向确定最优解：沿着目标函数值增大的方向平移等值线，当平移直线刚要离开可行域时的“最后交点”时，“最后交点”即为最优解。当前第30页\共有177页\编于星期日\22点246x1x2246无界解(无最优解)例4x1+x2=4(≥)x1+3x2=6(≥)3x1+x2=6(≥)maxZminZ线性规划的图解法确定最优解：沿着函数值增大的方向平移等值线，与可行域时的“最后交点”为最优解。绘制目标函数的等值线族，确定目标函数增大和减小的方向当前第31页\共有177页\编于星期日\22点x1x2O10203040102030405050无可行解(即无最优解)例5线性规划的图解法当前第32页\共有177页\编于星期日\22点

图解法简单、直观，便于初学者窥探线性规划基本原理和几何意义。通过图解法了解线性规划有几种解的形式(唯一最优解；无穷多最优解；无界解；无可行解)

作图的关键有三点：

(1)可行域要画正确

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

(3)目标函数的直线怎样平行移动线性规划的图解法当前第33页\共有177页\编于星期日\22点x1x2o（7.6，2）D可行域可行域是凸多边形可行域是凸多边形，有界集当前第34页\共有177页\编于星期日\22点246x1x2246x1+x2=4(≥)x1+3x2=6(≥)3x1+x2=6(≥)可行域是凸多边形但无界可行域是凸多边形当前第35页\共有177页\编于星期日\22点x1x2O10203040102030405050可行域是空集可行域是空集当前第36页\共有177页\编于星期日\22点x1x2o17.2=2x1+x2

Lo：0=2x1+x2

（7.6，2）DmaxZminZ此点是唯一最优解可行域线性规划的最优解若存在，定在可行域的某顶点最优解唯一，最优解在可行域的一个顶点当前第37页\共有177页\编于星期日\22点x1x2o（7.6，2）DL0：0=3x1+5.7x2

maxZ（3.8，4）34.2=3x1+5.7x2

蓝色线段上的所有点都是最优解这种情形为有无穷多最优解可行域

若在两个顶点同时得到最优解，则在这两点的连线上的任一点都是最优解。线性规划的最优解若存在，定在可行域的某顶点最优解在可行域的某顶点当前第38页\共有177页\编于星期日\22点246x1x2246无界解(无最优解)x1+x2=4(≥)x1+3x2=6(≥)3x1+x2=6(≥)maxZminZ可行域无界，最优解无界无最优解（可行域无界）当前第39页\共有177页\编于星期日\22点x1x2O10203040102030405050无可行解(即无最优解)无最优解（无可行解）可行域是空集，无最优解当前第40页\共有177页\编于星期日\22点

（1）线性规划的所有可行解构成的可行域一般是凸多边形，有些可行域是无界的；（2）若存在最优解，则一定在可行域的某顶点得到；（3）若在两个顶点上同时得到最优解，则在这两点的连线上的任一点都是最优解。（4）若可行域无界，则可能发生最优解无界的情况；（5）若可行域是空集，此时无最优解。由图解法可看到当前第41页\共有177页\编于星期日\22点

上述理论具有普遍意义，对于两个以上变量的线性规划问题都成立。图解法虽然直观、简便等优点，在变量多的情况下，即在多维的情况下，它就无能为力了。因此，需要介绍一种代数方法----单纯型法，为了以后介绍方便讨论，需要研究一下线性规划的简单性质和简单概念。由图解法可看到当前第42页\共有177页\编于星期日\22点第五章线性规划本章主要内容：§1线性规划的简介和应用举例§2线性规划的数学模型及图解法§3线性规划的基本概念和基本性质§4单纯形法§5线性规划的对偶理论与对偶单纯形法当前第43页\共有177页\编于星期日\22点可行解（或容许解）:

满足约束条件的解x=(x1,x2,···,xn)T

称为线性规划问题的可行解;可行域：所有可行解的集合称为可行解集或可行域。3.最优解:

使得目标函数取到最小值的可行解称为线性规划问题的最优可行解，简称为最优解或者解。

线性规划问题的标准形为：线性规划的基本概念当前第44页\共有177页\编于星期日\22点基:

假设A

是约束方程组的系数矩阵,其秩数为

m,B是矩阵A

中由m

列构成的非奇异子矩阵(B的行列式的值不为0），则称B是线性规划问题的一个基。

称Pj(j=1,2,···,m)为基向量,与基向量Pj

相对应的变量xj

(j=1,2,···,m)为基变量,否则称为非基变量。线性规划的基本概念矩阵B是由m

个线性无关的列向量组成,不失一般性,可假设:当前第45页\共有177页\编于星期日\22点

为了进一步讨论线性规划问题的解,研究Ax=b的求解问题。假设该方程组系数矩阵A

的秩为m,因m<n,所以它有无穷多个解。假设前m

个变量的系数列向量是线性无关的，这时Ax=b可改写为：线性规划的基本概念当前第46页\共有177页\编于星期日\22点方程组(2.1)的一个基是B=(P1,P2,···,Pm),

Pj=(a1j,···,amj)T,(j=1,2,···,m),设xB

是对应于这个基的基向量,即：

xB=(x1,x2,···,xm)T

5.基本解：

若令(2.1)式中的非基变量xm+1=···=xn=0,

求出一个解x=(x1,x2,···,xm,0,···,0)T,这个解的非0分量的数目不大于方程个数m,称x

为基本解。线性规划的基本概念当基本解中有一个或者一个以上的基变量是0时，称这个基本解是退化的基本解。当前第47页\共有177页\编于星期日\22点基本可行解:

满足非负约束条件的基本解称为基本可行解.

基本可行解的非0分量的数目不大于m,都是非负的。7.可行基:

对应于基本可行解的基称为可行基.

约束方程组Ax=b基本解的数目至多是Cnm

个.一般地讲,基本可行解的数目要小于基本解的数目,至多相等.

以上提到的几种解的概念,可用如下图来表示:基解可行解基本可行解线性规划的基本概念当前第48页\共有177页\编于星期日\22点例求解:约束方程的系数矩阵为2×5矩阵r(A)=2，2阶子矩阵有10个，其中基矩阵只有9个，即线性规划的基本概念的所有基矩阵。当前第49页\共有177页\编于星期日\22点线性规划的基本概念取定基,矩阵

相应的基变量是x1,x4,非基变量是x2,x3,x5,

在约束条件中令非基变量x2,x3,x5都取0，从中解出基变量

从而得到一个基本解不是可行解不是可行基当前第50页\共有177页\编于星期日\22点线性规划的基本概念取定基矩阵相应的基变量是x4,x5,非基变量是x1,x2,x3,

在约束条件中令非基变量x1,x2,x3,都取0，从中解出基变量

从而得到一个基本解可行解是可行基基本可行解当前第51页\共有177页\编于星期日\22点极点：设S是凸集，

,不存在S

中的另外两个点

和

，及

，使

,则称x是凸集S的极点，或称顶点。定理：设

，其秩为m,且

,,则x为凸集的一个顶点的充要条件是

x为的一个基本可行解。R是凸集

线性规划的基本性质阐明了基本可行解与可行域的顶点之间一一对应的关系当前第52页\共有177页\编于星期日\22点推论1：若线性规划的可行域R={x

|Ax=b,x

0}是非空的，则它至少有一个顶点。推论2:

若线性规划存在有限的最优解，则至少存在一个

R的顶点是有限最优解。推论3:

线性规划的可行域R有有限多个顶点。

线性规划的基本性质定理

(线性规划问题的基本定理)(1)

若线性规划问题存在可行解,则一定存在基本可行解;(2)

若线性规划问题存在最优解,则一定存在最优的基本可行解。基本可行解

R的顶点基本可行解

R的顶点基本可行解最多个线性规划问题若有最优解,必定在某顶点取到当前第53页\共有177页\编于星期日\22点根据以上讨论得到如下的结论：

结论1：线性规划的可行域是凸集,它可以是有界的,也可以是无界的区域;仅有有限个顶点。

结论2：线性规划的每一个基本可行解对应于可行域的一个顶点.若线性规划问题有最优解,必定可在某顶点取到。

结论3：如果一个线性规划存在多个最优解,那么至少有两个相邻的顶点处是线性规划的最优解。

结论4：如果有一个顶点处可行解的目标值比其它相邻顶点的可行解的目标值小的话，那么它就是最优解。

线性规划的基本性质当前第54页\共有177页\编于星期日\22点

可行域的顶点个数是有限的(不超过Cnm

个)，采用“枚举法”找出所有基本可行解，然后一一比较它们的目标函数值的大小，最终可以找到最优解。但当m、n

的数目相当大时，这种办法实际上是行不通的。因此，我们还要继续讨论一种方法，通过逐步迭代保证能逐步改进并最终求出最优解。

线性规划的基本性质当前第55页\共有177页\编于星期日\22点作业:P1575.15.2当前第56页\共有177页\编于星期日\22点极点：设S是凸集，

,不存在S

中的另外两个点

和

，及

，使

,则称x是凸集S的极点，或称顶点。定理1：设

，其秩为m,且

,,则x为凸集的一个顶点的充要条件是

x为的一个基本可行解。

线性规划的基本性质当前第57页\共有177页\编于星期日\22点Ox1x28060②④①90最优解Q2(75,15)Q1Q3Q4Q5Q6Q7Q8①②③③当前第58页\共有177页\编于星期日\22点推论1：若线性规划的可行域R={x

|Ax=b,x

0}是非空的，则它至少有一个顶点。推论2:

若线性规划存在有限的最优解，则至少存在一个

R的顶点是有限最优解。推论3:

线性规划的可行域R有有限多个顶点。

线性规划的基本性质定理2

(线性规划问题的基本定理)(1)

若线性规划问题存在可行解,则一定存在基本可行解;(2)

若线性规划问题存在最优解,则一定存在最优的基本可行解。基本可行解

R的顶点基本可行解

R的顶点基本可行解最多个线性规划问题若有最优解,必定在某顶点取到当前第59页\共有177页\编于星期日\22点

可行域的顶点个数是有限的(不超过Cnm

个)，采用“枚举法”找出所有基本可行解，然后一一比较它们的目标函数值的大小，最终可以找到最优解。但当m、n

的数目相当大时，这种办法实际上是行不通的。因此，我们还要继续讨论一种方法，通过逐步迭代保证能逐步改进并最终求出最优解。

线性规划的基本性质当前第60页\共有177页\编于星期日\22点61从定理1和2知，寻求最优解，就可从基本可行解（顶点）出发，在基本可行解（顶点）之间变换，如果L.P.有最优解，则最优解一定可在某一基本可行解（顶点）上得到。这个方法可用来求有任意多个变量的线性规划模型！Ox1x2Q2(75,15)60②③④④①最优解Q1Q3Q4Q5Q6Q7Q8当前第61页\共有177页\编于星期日\22点第五章线性规划本章主要内容：§1线性规划的简介和应用举例§2线性规划的数学模型及图解法§3线性规划的基本概念和基本性质§4单纯形法§5线性规划的对偶理论与对偶单纯形法当前第62页\共有177页\编于星期日\22点1947年,美国学者GeorgeDantzig(丹齐格)提出了求解线性规划的单纯形法,为线性规划的推广奠定了基础。从可行域的一个顶点(基本可行解)开始,转移到另一个顶点(另一个基本可行解);转移的条件是使目标函数值得到改善(逐步变优)当目标函数达到最优值时,问题也就得到了最优解。基本思想单纯形法当前第63页\共有177页\编于星期日\22点对于标准线性规划问题(简写为LP):A=(aij)mn,rank(A)=m

单纯形法的基本原理将A分解成[B,N],使B为基矩阵,N为非基矩阵

设求基本解基本可行解令xN=0是基本解。若当前第64页\共有177页\编于星期日\22点相应的目标函数值为记

现在分析如何从一个基本可行解x(0)出发，求一个改进的基本可行解x(1)

。单纯形法的基本原理假设已知一个基本可行解x(0)

若初始基本可行解x(0)不是最优解，找一个新的基本可行解。任意可行解xx?形式并保证是基本可行解x(1)

找改进的基本可行解：当前第65页\共有177页\编于星期日\22点设x是任意可行解，目标函数f在点x处的值为单纯形法的基本原理记是非基变量的指标集相应于矩阵A的分解A=[B,N],B称为基矩阵x可写为当前第66页\共有177页\编于星期日\22点对任意一个可行解处的目标函数值为单纯形法的基本原理其中是非基变量的下标集，以及xk就从非基变量变成了基变量式(1)中，如果则，x(0)是最优解；

如果则令xk由0变为正数时，f就在变小；(xk是进基变量)当前第67页\共有177页\编于星期日\22点对任意一个可行解处的目标函数值为单纯形法的基本原理xk就从非基变量变成了基变量(xk

是进基变量)根据（1）,当取值相同时，越大，目标函数下降越多，因此选择(进基变量)。

式(1)中，如果有多个则记令xk由0变为正数时，f在变小；当前第68页\共有177页\编于星期日\22点1.确定进基变量xk

假设记和是m维列向量，，把按分量写出，即单纯形法的基本原理取此时方程组的解变为对应的xk

就是进基变量

当由零变为正数后，函数值变小当前第69页\共有177页\编于星期日\22点新得到的点是

因为基变量个数总是为m,所以一个进基之后还必须有一个离基。下面我们来考虑如何选择离基变量。单纯形法的基本原理在新得到的点，目标函数值是基变量原则：保证新得到的点是基本可行解当前第70页\共有177页\编于星期日\22点原则：保证新得到的点是基本可行解当时，取任何正值时，总成立对某个i,当时，取任何正值时，总成立2.确定离基变量

单纯形法的基本原理而当时，为了保证取因此，为使，应令

取值后，原来的基变量就是离基变量，于是得到新的基本可行解当xk趋于正无穷时，目标函数值趋于负无穷，因此解无界当前第71页\共有177页\编于星期日\22点重复以上过程，可以进一步改进基本可行解，直到所有的时为止。单纯形法的基本原理基变量基变量非基变量非基变量初始的基本可行解改进的基本可行解目标函数值减小了进基变量的确定离基变量的确定f0

是最优值,当前的基本可行解是最优解当前第72页\共有177页\编于星期日\22点最优解判别定理

称为判别数或检验数。单纯形法的基本原理所有的就可以作为最优解的一个判别条件

若在极大化问题中,对于某个基本可行解,所有则这个基本可行解是最优解。

若在极小化问题中,对于某个基本可行解,所有则这个基本可行解是最优解。当前第73页\共有177页\编于星期日\22点步骤1：找出初始可行基B，由，求得，令，确定初始基本可行解。计算目标函数值。步骤2：对于所有非基变量，计算判别数,令若，则对于所有非基变量，对基变量的判别数总是零，停止计算，当前的基本可行解是最优解。否则，进行下一步。单纯形法的算法步骤称为单纯形乘子由，得到.当前第74页\共有177页\编于星期日\22点步骤3：由,得到,若，即的每一个分量均非正数，则停止计算，问题不存在有限最优解。否则，进行转步骤4。步骤4：确定下标r

为离基变量，为进基变量。用替换，得到新的基矩阵B,返回步骤1。注：对于极大化问题，可以给出类似的步骤，只是确定进基和离基变量的准则不同。对于极大化问题，应令单纯形法的算法步骤当前第75页\共有177页\编于星期日\22点以极小化问题为例每次迭代必出现下列三种情形之一(1).这时当前的基本可行解就是最优解。(2).这种情形下，我们知道取任何正数，总能得到可行解。所以当无限增大时，目标函数趋于负无穷，因此解无界。(3)，大于零。这时求出新的基本可行解，经迭代使目标函数下降。单纯形法的收敛性当前第76页\共有177页\编于星期日\22点

如果迭代过程中各个基本可行解都是非退化的，即基变量的取值都是正的，则各次迭代得到的基本可行解互不相同。由于基本可行解的个数有限，因此经有限次迭代一定可以达到最优解。收敛性定理：对于非退化问题，单纯形方法经有限次迭代或达到最优基本可行解，或得出无界的结论。

注：对于退化情形，可能出现循环迭代，我们在后面将要证明，如果最优解存在，只要采取一定的措施，也能做到有限步收敛。单纯形法的收敛性当前第77页\共有177页\编于星期日\22点使用表格形式的单纯形方法记，则标准形式等价于1.构造单纯形表标准形式的线性规划标准形式继续等价于当前第78页\共有177页\编于星期日\22点把约束方程的系数置于表中，就得到了所谓的单纯形表1列cBTB-1

bB-1b右端m行B-1NIm0xNxBfn-m列m列1列1行cBT

B-1N-cNT01目标函数值判别数基变量的值使用表格形式的单纯形方法1.构造单纯形表A中存在m阶的单位矩阵xBf当前第79页\共有177页\编于星期日\22点zk-ckymkyrky1k

……

zj-cj…zm+1–cm+10…0…0……ymj…ymm+11…0…0

……

…

……yrj…yrm+10…1…0

……

…

……y1j…y1m+10…0…1初始单纯形表……………………………………………………使用表格形式的单纯形方法1.构造单纯形表

xk是进基变量，是离基变量；主元把xk

所对应的列向量pk变成所对应的列向量，即是单位向量。把xk和

的位置对换，当前第80页\共有177页\编于星期日\22点zk-ckymkyrky1k

……

zj-cj…zm+1–cm+10…0…0……ymj…ymm+11…0…0

……

…

……yrj…yrm+10…1…0

……

…

……y1j…y1m+10…0…1……………………………………………………使用表格形式的单纯形方法2.高斯主元消去法主元将yrk

变为1，yik(

i≠r)以及zk–ck都变为0(yk

=B-1

pk

)把pk变成对应的单位向量？当前第81页\共有177页\编于星期日\22点对应的新的目标函数值即为：使用表格形式的单纯形方法2.高斯主元消去法以yrk

为主元素进行Gauss消元:将第r

行每个元素除以yrk

:将第r

行每个元素乘以–yik/yrk

加到第i行(i=1,···,m,

i≠r)将第r

行每个元素乘以–(zk–ck)

/yrk

加到检验数行当前第82页\共有177页\编于星期日\22点经过Gauss消元后，针对于新基B1

的基本可行解为：使用表格形式的单纯形方法2.高斯主元消去法当前第83页\共有177页\编于星期日\22点步骤3：在所有j>0,j∈RN

中，若有一个j

对应的系数列向量

yj0，则此问题没有有限最优解，停止计算，否则转步骤4；使用表格形式的单纯形方法3.单纯形表的单纯形法的算法步骤步骤1：找出初始可行基，确定初始基本可行解，建立初始单纯形表；步骤2：检查对应于非基变量的检验数j=zj-cj,j∈RN,若所有

j0,j∈RN,则已得到最优解,停止计算;否则转步骤3步骤4：根据max{j|j>0,j∈RN}=k,确定xk

为进基变量。当前第84页\共有177页\编于星期日\22点确定xr

为离基变量(即为新基的非基变量),转步骤6；步骤5：再根据步骤6：以yrk

为主元素进行Gauss消元，转步骤2。使用表格形式的单纯形方法3.单纯形表的单纯形法的算法步骤当前第85页\共有177页\编于星期日\22点例1.

利用单纯形算法求解如下的线性规划问题。解：

1.写出线性规划的标准型使用表格形式的单纯形方法3.单纯形表的算例A中存在4阶单位矩阵选取作为基变量，得到一个基本可行解当前第86页\共有177页\编于星期日\22点

2.max{1,

2}=3=2,所以x2为进基变量.3.p2的坐标有正分量存在，因为3与x6

那一行相对应，所以x6为离基变量；故x2对应列与x6对应行的相交处的4为主元素；xBx1x2x3x4x5

x6

221000120100400010040001x3x4x5x61281612

23c

-2-30000

64--30000

cB0000当前第87页\共有177页\编于星期日\22点4.

以“4”为主元素Gauss消去，进行行初等变换xBx1x2x3x4x5

x6

x3x4x5x2c

-2-30000

cB000-3

0100-1/26

20000-3/4324--010001/434000101610010-1/22这行除以4xBx1x2x3x4x5x6

221000120100400010040001x3x4x5x61281612

23c

-2-30000

64--30000

cB0000这行不变第4行的-1/2加到这行第4行的-1/2加到这行第4行的-3/4加到检验数行当前第88页\共有177页\编于星期日\22点

5.max{1}=2=1,所以x1为进基变量.6.p1的坐标有正分量存在，因为2与x4

那一行相对应，所以x4为离基变量；故x1对应列与x4对应行的相交处的1为主元素；当前第89页\共有177页\编于星期日\22点7.

以“1”为主元素Gauss消元，进行行初等变换xBx1x2x3x4x5

x6

x3x1x5x2c

-2-30000

cB0-20-30

01-201/22

000-201/44--412010001/43000-412810010-1/22第2行的-4倍加到该行xBx1x2x3x4x5x6

c

-2-30000

cB000-3第2行的-2倍加到该行第4行的-2加到检验数行x3x4x5x2

0100-1/26

20000-3/4010001/434000101610010-1/22324--这行不变这行不变退化现象：有两个或更多的相同时，在相同对应的变量中选择下标最大的那个基变量为离基变量当前第90页\共有177页\编于星期日\22点因为4与x3

，

x5那一行相对应，所以x5为离基变量;故x6对应列与x5对应行的相交处的2为主元素；

9.p6的坐标有正分量存在，

8.max{6}=1/4=6,所以x6为进基变量.当前第91页\共有177页\编于星期日\22点xBx1x2x3x4x5

x6

x3x1x5x2c

-2-30000

cB0-20-30

01-201/22

000-201/44--412010001/43000-412810010-1/22注：

这时出现了退化问题。即有两个或更多的相同时，在相同对应的变量中选择下标最大的那个基变量为换出变量；同时如果出现有两个或更多的检验数σ相同时，在相同σ

对应的变量中选择下标最小的那个基变量为进基变量，这样会避免出现“死循环”的现象。当前第92页\共有177页\编于星期日\22点10.

以“2”为主元素Gauss消元，进行行初等变换xBx1x2x3x4x5x6

x3x1x6x2c

-2-30000

cB0-20-30

01-1-1/400

000-3/2-1/800101/2-1/802000-21/21410001/404该行除以2xBx1x2x3x4x5

x6

c

-2-30000

cB0-20-3第3行的-1/4倍加到该行第3行的-1/8加到检验数行x3x1x5x20

01-201/22

000-201/4010001/43000-412810010-1/224--412第3行的1/4加到该行第3行的-1/8加到该行所有检验数都小于等于0，当前的基本可行解是最优解当前第93页\共有177页\编于星期日\22点xBx1x2x3x4x5

x6

x3x1x6x2c

-2-30000

cB0-20-30

01-1-1/400

000-3/2-1/800101/2-1/802000-21/21410001/404所有检验数都小于等于0，当前的基本可行解x=(4,2,0,0,0,4)T是最优解原问题的最优解是x=(4,2)T，最优值是f=2*4+3*2=14当前第94页\共有177页\编于星期日\22点例2.利用单纯形算法求解如下的线性规划问题。解：

1.化为标准型得到：A中存在3阶单位矩阵选取作为基变量，得到一个基本可行解当前第95页\共有177页\编于星期日\22点

2.max{2}=2=2,所以x2为进基变量.3.p2的坐标有正分量存在，因为2与x6

那一行相对应，所以x6为离基变量；故x2对应列与x6对应行的相交处的2为主元素；建立单纯形表xBx1

x2x3

x4x5

x6

x4x5x6c

1-21000

cB0001

1-210010-12-1-12-400142-14010810--2000当前第96页\共有177页\编于星期日\22点4.

以“2”为主元素进行Gauss消去，即进行行初等变换xBx1x2x3x4x5

x6

x4x5x6c

1-21000

cB0001

1-210010-12-1-12-400142-14010810--2000xBx1x2x3x4x5

x6

x4x5x2c

1-21000

cB00-23/2

0010-1/2800300-1-1/21-2001/223/202011/210--5--这行除以2第3行的1/2加到该行第3行的-1/2加到该行第3行的-1倍加到检验数行当前第97页\共有177页\编于星期日\22点

5.max{3}=3=3,所以x3

为进基变量.6.p3的坐标有正分量存在，因为5与x5

那一行相对应，所以x5为离基变量；故x3对应列与x5对应行的相交处的2为主元素；当前第98页\共有177页\编于星期日\22点7.

以“2”为主元素进行Gauss消去，即进行行初等变换xBx1x2x3x4x5x6

x4x5x2c

1-2