第一章线性规划与单纯形法

天津大学老教授协会2011考研辅导运筹学辅导§1线性规划模型第一章线性规划例1.1生产计划问题（资源利用问题）

胜利家具厂生产桌子和椅子两种家具。桌子售价50元/个，椅子销售价格30元/个，生产桌子和椅子要求需要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每个月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？解：将一个实际问题转化为线性规划模型有以下几个步骤：解：将一个实际问题转化为线性规划模型有以下几个步骤：1．确定决策变量：x1=生产桌子的数量

x2=生产椅子的数量解：将一个实际问题转化为线性规划模型有以下几个步骤：1．确定决策变量：x1=生产桌子的数量

x2=生产椅子的数量2．确定目标函数：家具厂的目标是销售收入最大

maxz=50x1+30x2解：将一个实际问题转化为线性规划模型有以下几个步骤：1．确定决策变量：x1=生产桌子的数量

x2=生产椅子的数量2．确定目标函数：家具厂的目标是销售收入最大

maxz=50x1+30x23．确定约束条件：

4x1+3x2

120（木工工时限制）

2x1+x2

50（油漆工工时限制）解：将一个实际问题转化为线性规划模型有以下几个步骤：1．确定决策变量：x1=生产桌子的数量

x2=生产椅子的数量2．确定目标函数：家具厂的目标是销售收入最大

maxz=50x1+30x23．确定约束条件：

4x1+3x2

120（木工工时限制）

2x1+x2

50（油漆工工时限制）4．变量取值限制：

一般情况，决策变量只取正值（非负值）

x1

0,x2

0解：将一个实际问题转化为线性规划模型有以下几个步骤：1．确定决策变量：x1=生产桌子的数量

x2=生产椅子的数量2．确定目标函数：家具厂的目标是销售收入最大

maxz=50x1+30x23．确定约束条件：

4x1+3x2

120（木工工时限制）

2x1+x2

50（油漆工工时限制）4．变量取值限制：

一般情况，决策变量只取正值（非负值）

x1

0,x2

0数学模型

maxS=50x1+30x2s.t.4x1+3x2

1202x1+x2

50x1,x2

0线性规划数学模型三要素：

决策变量、约束条件、目标函数

线性规划模型的三要素3.约束条件：为实现优化目标需受到的限制，用决策变量的等式或不等式表示；1.决策变量：需决策的量，即待求的未知数；2.目标函数：需优化的量，即欲达的目标，用决策变量的表达式表示；建立线性规划问题的数学模型的例子例1.2营养配餐问题假定一个成年人每天需要从食物中获得3000千卡的热量、55克蛋白质和800毫克的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量和营养成分和市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小？食品名称热量（千卡）蛋白质（克）钙（毫克）价格（元)猪肉10005040014鸡蛋800602006大米900203003白菜200105002各种食物的营养成分表解：设xj为第j种食品每天的购入量，则配餐问题的线性规划模型为：

minS=14x1+6x2+3x3+2x4s.t.1000x1+800x2+900x3+200x4

300050x1+60x2+20x3+10x4

55400x1+200x2+300x3+500x4

800x1，x2，

x3，x4

0线性规划问题的一般形式：Max(Min)S=c1x1+c2x2+…..+cnxns.t.a11x1+a12x2+….+a1nxn

(=,

)b1a21x1+a22x2+….+a2nxn

(=,

)b2

….am1x1+am2x2+….+amnxn

(=,

)bmx1,x2….xn

0§2线性规划问题图解法图解法是用画图的方式求解线性规划的一种方法。它虽然只能用于解二维（两个变量）的问题，但其主要作用并不在于求解，而是在于能够直观地说明线性规划解的一些重要性质。§2线性规划问题图解法（1）满足约束条件的变量的值，称为可行解。§2线性规划问题图解法（1）满足约束条件的变量的值，称为可行解。（2）使目标函数取得最优值的可行解，称为最优解。§2线性规划问题图解法（1）满足约束条件的变量的值，称为可行解。（2）使目标函数取得最优值的可行解，称为最优解。例1.1的数学模型

maxS=50x1+30x2s.t.4x1+3x2

1202x1+x2

50x1,x2

0x2504030201010203040x14x1+3x2

120由4x1+3x2

120x1

0x2

0围成的区域x2504030201010203040x12x1+x2

50由2x1+x2

50x1

0x2

0围成的区域x2504030201010203040x12x1+x2

504x1+3x2

120可行域同时满足：2x1+x2

504x1+3x2

120x1

0x2

0的区域——可行域x2504030201010203040x1可行域O（0，0）Q1（25，0）Q2（15，20）Q3（0，40）可行域是由约束条件围成的区域，该区域内的每一点都是可行解，它的全体组成问题的解集合。该问题的可行域是由O，Q1，Q2，Q3作为顶点的凸多边形x2504030201010203040x1可行域目标函数是以S作为参数的一组平行线x2=

S/30-（5/3）x1x2504030201010203040x1可行域当S值不断增加时，该直线x2=

S/30-（5/3）x1沿着其法线方向向右上方移动。x2504030201010203040x1可行域当该直线移到Q2点时，S（目标函数）值达到最大：MaxS=50*15+30*20=1350此时最优解=（15，20）Q2（15，20）二个重要结论：满足约束条件的可行域一般都构成凸多边形。这一事实可以推广到更多变量的场合。二个重要结论：满足约束条件的可行域一般都构成凸多边形。这一事实可以推广到更多变量的场合。最优解必定能在凸多边形的某一个顶点上取得，这一事实也可以推广到更多变量的场合。解的讨论：最优解是唯一解；解的讨论：最优解是唯一解；无穷多组最优解：例1.1的目标函数由

maxS=50x1+30x2变成：

maxS=40x1+30x2s.t.4x1+3x2

1202x1+x2

50x1,x2

0x2504030201010203040x1可行域目标函数是同约束条件：4x1+3x2

120平行的直线x2=

S/30-（4/3）x1x2504030201010203040x1可行域当S的值增加时，目标函数同约束条件：4x1+3x2

120重合，Q1与Q2之间都是最优解。Q1（25，0）Q2（15，20）解的讨论：无界解：例：maxS=x1+x2s.t.-2x1+x2

40x1-x2

20x1,x2

0x2504030201010203040x1该可行域无界，目标函数值可增加到无穷大，称这种情况为无界解或无最优解。解的讨论：无可行解：例：maxS=2x1+3x2s.t.x1+2x2

8x1

4x2

3-2x1+x2

4x1,x2

0该问题可行域为空集，即无可行解，也不存在最优解。解的情况：有可行解⊙有唯一最优解⊙有无穷最优解⊙无最优解无可行解§3线性规划问题的标准形式MaxS=c1x1+c2x2+…..+cnxns.t.a11x1+a12x2+….+a1nxn=b1a21x1+a22x2+….+a2nxn=b2

….am1x1+am2x2+….+amnxn=bmx1,x2….xn

0其中：bi

0(i=1,2,….m)线性规划问标准形的向量形式线性规划标准型的矩阵形式Max

S=CX

s.t.

AX=bX

0

a11a12….a1nb1A=a21a22….a2nb

=

b2…….am1am2….amn

bn

c1x10c2x20C=X=0=……………..

cn

xn0如何将一般问题化为标准型：若目标函数是求最小值MinS=CX令S’=-S,则

MaxS’=-CX如何将一般问题化为标准型：若目标函数是求最小值MinS=CX令S’=-S,则

MaxS’=-CX若约束条件是不等式如何将一般问题化为标准型：若目标函数是求最小值MinS=CX令S’=-S,则

MaxS’=-CX若约束条件是不等式若约束条件是“

”不等式

n

aijxj

+si=bij=1

si

0是非负的松驰变量如何将一般问题化为标准型：若约束条件是“

”不等式

n

aijxj

-si

=bi

j=1

si

0是非负的松驰变量如何将一般问题化为标准型：若约束条件右面的某一常数项bi<0这时只要在bi相对应的约束方程两边乘上-1。如何将一般问题化为标准型：若约束条件右面的某一常数项bi<0这时只要在bi相对应的约束方程两边乘上-1。若变量xj无非负限制引进两个非负变量xj’

xj”

0令xj=

xj’-xj”（可正可负）如何将一般问题化为标准型：若约束条件右面的某一常数项bi<0这时只要在bi相对应的约束方程两边乘上-1。若变量xj无非负限制引进两个非负变量xj’

xj”>=0令xj=

xj’-xj”（可正可负）任何形式的线性规划总可以化成标准型例1.3将下列问题化成标准型:MinS=-x1+2x2-3x3s.t.x1+x2+x3

7x1-x2+x3

2-3x1+x2+2x3=5x1,x2

0x3无非负限制MaxS=x1-2x2+3x3’-3x3”s.t.x1+x2+x3’-x3”+x4=7x1-x2+x3’-x3”-x5=2-3x1+x2+2x3’-2x3”=5x1,x2,x3’,x3”,x4,x5

0§4

单纯形方法一线性规划问题解的概念线性规划标准型的矩阵形式：

MaxS=CX（1-9）

s.t.AX=b（1-10）

X

0（1-11）

a11a12….a1nb1A=a21a22….a2nb

=

b2………am1am2….amn

bn

c1x10c2x20C=X=0=……………..

cn

xn0解、可行解、最优解⊙满足约束条件（1-10）的X，称为线性规划问题的解。解、可行解、最优解⊙满足约束条件（1-10）的X，称为线性规划问题的解。⊙满足约束条件（1-10）与（1-11）的X，称为线性规划的问题可行解。解、可行解、最优解⊙满足约束条件（1-10）的X，称为线性规划问题的解。⊙满足约束条件（1-10）与（1-11）的X，称为线性规划的问题可行解。⊙满足目标函数（1-9）的可行解X，称为线性规划的问题最优解。基、基向量、基变量⊙设r(A)=m,并且B是A的m阶非奇异的子矩阵（det(B)

0),则称矩阵

B为线性规划问题的一个基。基、基向量、基变量⊙设r(A)=m,并且B是A的m阶非奇异的子矩阵（det(B)<>0),则称矩阵

B为线性规划问题的一个基。⊙矩阵B=（P1，P2….Pm)，其列向量

Pj

称为对应基B的基向量。基、基向量、基变量⊙设r(A)=m,并且B是A的m阶非奇异的子矩阵（det(B)<>0),则称矩阵

B为线性规划问题的一个基。⊙矩阵B=（P1，P2….Pm)，其列向量

Pj称为对应基B的基向量。⊙与基向量Pj

相对应的变量xj就称为基变量，其余的就称为非基变量。基解.基可行解.可行基⊙对于某一特定的基B，非基变量取

0值的解，称为基解。基解.基可行解.可行基⊙对于某一特定的基B，非基变量取

0值的解，称为基解。⊙满足非负约束条件的基解，称为基可行解。基解.基可行解.可行基⊙对于某一特定的基B，非基变量取

0值的解，称为基解。⊙满足非负约束条件的基解，称为基可行解。⊙与基可行解对应的基，称为可行基。为了理解基解.基可行解.最优解的概念，用下列例子说明：例1.4：maxS=2x1+3x2（1-12）

s.t.-2x1+3x2

6（1-13-1）

3x1-2x2

6（1-13-2）

x1+x2

4（1-13-3）

x1,x2

0（1-14）将其划为标准形式：例1.4：maxS=2x1+3x2（1-12）

s.t.-2x1+3x2+s1=6（1-13-1）

3x1-2x2+s2=6（1-13-2）

x1+x2+s3=4（1-13-3）

x1,x2

0,si

0,(i=1,2,3)

（1-14）

x243211234x1O-1-1-2-2-3-3-2x1+3x2=63x1-2

x2=6x1+x2=4AQ1Q2Q3Q4Bx243211234x1O-1-1-2-2-3-3-2x1+3x2<=63x1-2

x2<=6x1+x2<=4ABx243211234x1O-1-1-2-2-3-3-2x1+3x2<=63x1-2

x2<=6x1+x2<=4AQ1Q2Q3Q4Bx243211234x1O-1-1-2-2-3-33x1-2

x2

6x1+x2

4AQ1Q2Q3Q4B可行域-2x1+3x2

6本问题解的情况：基础解：点（O，A，B，Q1，Q2，Q3，Q4，P1，P2，P3）可行域：由点（O，Q1，Q2，Q3，Q4）围成的区域。基可行解：点（O，Q1，Q2，Q3，Q4）最优解：

Q3解的集合：非可行解可行解解的集合：基础解解的集合：可行解基础解基础可行解解的集合：可行解基础解基础最优解基础可行解两个基本概念：凸组合：

设x(1),x(2)…..x(k)是n维线性空间Rn中的k个点，若存在数u1,u2,….uk

且0<ui<1(i=1,2,…k),

ui=1,使得x=u1x(1)+u2x(2)+…..+

uk

x(k)成立，则称x为x(1),x(2)…..x(k)的凸组合。两个基本概念：顶点：设D是凸集,若D中的点x不能成为D中任何线段上的内点，则称x为凸集D的顶点。即：若D中的任意两点x(1),x(2)

，不存在数

（0<

<1）使得

x=

x(1)+(1-

)x(2)成立，则称x为凸集D的一个顶点。例1.9：多边形上的点是顶点圆周上的点都是顶点二线性规划的基本定理定理1-1

线性规划问题的可行域是凸集。（即连接线性规划问题任意两个可行解的线段上的点仍然是可行解。)证：设X1,X2是两个可行解，对于0<

<1由于AX=A(X1+

(1-)

X2)=AX1+

(1-)AX2=

b+(1-)b=b

所以X=X1+

(1-)

X2也是可行解，所以线性规划问题的可行域是凸集。定理1-2

线性规划问题的可行解x为基础可行解的充分必要条件是：x的非零分量所对应的系数矩阵A的列向量是线性无关。证：必要性设X=(x1,x2,…,xm,0,…,0)是基可行解，x1,x2,…,xm是基变量，其对应的向量P1,P2,…,Pm构成基，故P1,P2,…,Pm是线性无关。充分性设可行解X=(x1,x2,…,xk,0,…,0),xj>0,j=1,2,…,k,若P1,P2,…,Pk线性无关，则应有k≤m,当k=m时,则P1,P2,…,Pm

恰好构成一个基，从而X=(x1,x2,…,xm,0,…,0)为基可行解。当k<m时,则一定把P1,P2,…,Pk扩充成一个基，其对应的解为X=(x1,x2,…,xk,0,…,0),故X为基可行解。定理1-3

线性规划问题的可行解集D中的点x是顶点的充分必要条件是：x是基础可行解。定理1-3

线性规划问题的可行解集D中的点x是顶点的充分必要条件是：x是基础可行解。推论：可行解集D中的顶点个数是有限的。定理1-3

线性规划问题的可行解集D中的点x是顶点的充分必要条件是：x是基础可行解。推论：可行解集D中的顶点个数是有限的。推论：若可行解集D是有界的凸集，则D中任意一点x，都可表示成D的顶点的凸组合。定理1-4

若可行解集D有界，则线性规划问题的最优解，必定在D的顶点上达到。说明1：若可行解集D无界，则线性规划问题可能有最优解，也可能无最优解。若有最优解，也必在顶点上达到。说明2：有时目标函数也可能在多个顶点上达到最优值。这些顶点的凸组合也是最优值。（有无穷多最优解）三线性规划的单纯形方法单纯形方法基本思路：从可行域中某个基可行解（一个顶点）开始（称为初始基可行解）。如可能，从可行域中求出具有更优目标函数值的另一个基可行解（另一个顶点），以改进初始解。继续寻找更优的基础可行解，进一步改进目标函数值。当某一个基础可行解不能再改善时，该解就是最优解。例1-18：一个企业需要同一种原材料生产甲乙两种产品，它们的单位产品所需要的原材料的数量及所耗费的加工时间各不相同，从而获得的利润也不相同（如下表）。那么，该企业应如何安排生产计划，才能使获得的利润达到最大？解：数学模型

maxS=6x1+4x2s.t.2x1+3x2≤1004x1+2x2≤120x1,x2≥0解：引进松弛变量x3,x4≥0数学模型标准形式：

maxS=6x1+4x2

s.t.2x1+3x2+x3=1004x1+2x2+x4=120x1,x2,

x3,x4≥0

约束条件的增广矩阵为：

2310100（Ab)=4201120显然r(A)=r(Ab)=2<4,该问题有无穷多组解。令A=（P1，P2，P3，P4）=23104201X=（x1,x2,x3,x4)

A=（P1，P2，P3，P4）

=23104201X=（x1,x2,x3,x4)B=(P3，P4

）=1001P3，P4线性无关，x3,x4是基变量，x1,x2,是非基变量。

用非基变量表示的方程：

S=6x1+4x2x3=100-2x1-3x2(I)x4=120-4x1-2x2

称(I)为消去系统，若

b=(100,120)t≥

0则称为正消去系统。

令非基变量

(x1,

x2)t=(0，0)t

得基础可行解：

x(1)=(0,0,100,120)tS1=0

经济含义：不生产产品甲乙，利润为零。分析：S=6x1+4x2（分别增加单位产品甲、乙，目标函数分别减少6、4，即利润分别增加6百元、4百元。）增加单位产品对目标函数的贡献，这就是检验数的概念。

增加单位产品甲（x1）比乙对目标函数的贡献大（检验数最大），把非基变量x1换成基变量，称x1为进基变量，而把基变量x4换成非基变量，称x4为出基变量。（在选择出基变量时，一定保证消去系统为正消去系统）（最小比值原则）2x1+3x2+x3=100

4x1+2x2+x4=1202x2+x3-1/2x4=40

x1+1/2x2+1/4x4=30x3=40-2x2+1/2x4

x1=30-1/2x2-1/4x4

确定了进基变量x1

，出基变量x4

以后，得到新的消去系统：

S=180+x2-（3/2）x4x3=40-2x2+（1/2）x4x1=30-（1/2）x2-（1/4）x4(II)令新的非基变量（x2，x4）=（0，0）t得到新的基础可行解：x(2)=(30,0,40,0)tS2=180经济含义：生产甲产品30个，获得利润18000元。

这个方案比前方案好，但是否是最优？分析：S=180+x2-（3/2）x4非基变量x2系数仍为正数，确定x2为进基变量。在保证常数项非负的情况下，确定x3为出基变量。

2x2+x3-1/2x4=40x1+1/2x2+1/4x4=30x2+1/2x3-1/4x4=20x1-1/4x3+3/8x4=20x2=20-1/2x3+1/4x4

x1=20+1/4x3-1/8x4

将其带入目标函数得到新的消去系统：

S=200-（1/2）x3-（5/4）x4x1=20+（1/4）x3-（3/8）x4x2=20-（1/2）x3+（1/4）x4(III)令新的非基变量（x3,x4）t=（0,0）t得到新的基础可行解：x(3)=(20,20,0,0)tS3=200

经济含义：分别生产甲乙产品20个，可获得利润20000元。分析：S=200-（1/2）x3-（5/4）x4目标函数中的非基变量的系数无正数，S3=200是最优值，x(3)=(20,20,0,0)t是最优解。该企业分别生产甲乙产品20个，可获得最大利润20000元。上例给出单纯形法基本过程。为理解单纯形表的构造，把上面求解过程用矩阵来表示。-S+6x1-+4x2=02x1+3x2+x3=1004x1+2x2+x4=120对应的基可行解为（0，0，100，120），目标函数值为0。显然当x1增大时，目标函数值仍然可以增大，故此基可行解不是最优解。令x2=0,x1大于零，（即x1进基）当x1=30时，首先x4=0，所以x4出基。

-S+x2

-3/2x4=-1802x2+x3-1/2x4=40x1+1/2x2+1/4x4=30对应的基可行解为（30，0，40，0），目标函数值为180。显然当x2增大时，目标函数值仍然可以增大，故此基可行解不是最优解。令x4=0,x2大于零，（即x2进基）当x2=20时，首先x3=0，所以x3出基。S-(1/2)x3-(5/4)x4=-200x2+1/2x3-1/4x4=20x1-1/4x3+3/8x4=20对应的基可行解为（20，20，0，0），目标函数值为200。显然当x3,x4增大时，目标函数值不会增大，故此基可行解是最优解。单纯形法就是根据上面求解过程的矩阵形式，构造单纯形表进行求解。单纯形法计算步骤：步骤1

将LP化为标准形式,取得初始基可行解,步骤2(最优性检验),若σj≥0(j=1,2,…,n),则得到最优解，若否,转入第3步，步骤3(选择进基变量),选择最小负的σj

所在列对应的非基变量xj进基步骤4(利用最小比值原则选择出基变量),Cj6400CB基bx1x2x3x40x31000x4120

23104201检验数σj

64000x3406x130

021-1/211/201/4检验数σj

010-3/24x2206x120011/2-1/410-1/43/8检验数σj

00-1/2-5/4例1-20求解线性规划问题：minS=x1-3x2+

2x3+4x4s.t.2x1+4x3+x4=6-x1+x2+

3x3=5x1,

x2,

x3,

x4≥0解：问题已是标准型-S+x1-3x2+2x3+4x4=0A=20-41-1130取基B1=（P4，P2）=10=I01Cj1-324CB基bx1x2x3x44x462x25

20-41-1130检验数σj

1-3244x462x25

20-41-1130检验数σj

-100270-3x231x1810-21/20111/2检验数σj

0075例1-21求解线性规划问题：

minS=x1-x2s.t.-x1+x2≤

22x1-x2≤

2x1,

x2≥

0解：化标准型：

minS=x1-x2s.t.-x1+x2+x3=22x1-x2+x4=2x1,

x2,

x3,

x4≥

0Cj1-100CB基bx1x2x3x40x320x42

-11102-101检验数σj

1-100-1x220x44

-11101011检验数σj

0010-1x261x1401211011检验数σj

0010根据解的性质：最优解X=（0，2）t，

X=（4，6）t连线上的点仍是最优解：X=a(0,2)t+(1-a)(4,6)t

(0≤

a≤

1)本题有无穷多组最优解。例1-22求解线性规划问题：

maxS=2x1+x2s.t.x1-x2≥-52x1-5x2≤

10x1,

x2≥

0解：化标准型：

maxS=2x1+x2

s.t.-x1+x2+x3=52x1-5x2+x4=10x1,

x2,

x3,

x4≥0Cj2100CB基bx1x2x3x40x350x410

-11102-501检验数σj

21000x3102x15

0-3/211/21-5/201/2检验数σj

0601非基变量X2的检验数小于零，但X2所对应的系数向量:(-3/2,-5/2)t<0所以原问题无最优解.例1-23：求解下列线性规划问题

maxz=10x1+6x2+4x3

x1+x2+x3≤100

10x1+4x2+5x3≤600

2x1+2x2+6x3≤300

xj≥0（j=1,2,3）化为标准形式maxz=10x1+6x2+4x3+0x4+0x5+0x6x1+x2+x3+x4=10010x1+4x2+5x3+x5=6002x1+2x2+6x3+x6=600xj≥0（j=1,2,…,6）基B1=(P4,P5,P6),基变量x4,x5,x6对应的单纯形表T(B1)检验数中最大数10所在列的非基变量x1进基min{100/1,600/10,300/2}=600/1010所在行的基变量x5出基以10为基元，换基迭代得B2=(P1,P4,P6)，基变量x1,x4,x6Cj1064000CB基bx1x2x3x4x5x60x41000x56000x6300

1111001045010226001检验数σj

1064000Cj1064000CB基bx1x2x3x4x5x60x41000x56000x6300

1111001045010226001检验数σj

10640000x44010x1600x6180

03/51/21-1/10012/51/201/10006/550-1/51检验数σj

02-10-10检验数中有2,Z=60非最优解，2所对应的x2进基min{40/3/5,60/2/5,180/6/5}=40/(3/5)元素3/5所在行的基变量x4出基以3/5为主元换基迭代得B3=(P1,P2,P6),基变量x1,x2,x6Cj1064000CB基bx1x2x3x4x5x60x44010x1600x6180

03/51/21-1/10012/51/201/10006/550-1/51检验数σj

02-10-100x2200/310x1100/30x6100

015/65/3-1/60101/6-2/31/60004-201检验数σj

00-8/3-10/3-2/30因检验数全部为负，故最优解为x1=100/3,x2=200/3,x3=0最优值Z0=2200/3§5人工变量法用单纯形法求解线性规划，首先要有一个初始基可行解。在上一节中，约束都是小于等于，通过加入松弛变量化为标准形后，约束方程的系数矩阵中含有单位阵，单位阵可以作为初始基，并且很容易得到初始基可行解。但约束不是小于等于时，寻找初始基可行解比较困难。例如下面的例子。例1-24求解线性规划问题：

minf=4x1+x2s.t.3x1+x2=

34x1+3x2≥

6(1.5)x1+2x2≤

4x1,

x2≥

0将其化为标准型：

minf=4x1+x2s.t.3x1+x2=34x1+3x2-x3=

6(1.6)x1+2x2+x4=4x1,

x2,

x3,

x4≥

0

minf=4x1+x2s.t.3x1+x2=34x1+3x2-x3=

6(1.6)x1+2x2+x4=4x1,

x2,

x3,

x4≥

0对于上面的标准型的线性规划，寻找初始基可行解比较困难。为得到初始基可行解，在第一、二两个约束中加入两个称为人工变量的非负变量x5、

x6，得到

minf=4x1+x2

s.t.3x1+x2+x5=34x1+3x2-x3+x6=

6(1.7)x1+2x2+x4=4x1,

x2,

x3,

x4,

x5,

x6≥

0

minf=4x1+x2

s.t.3x1+x2+x5=34x1+3x2-x3+x6=

6(1.7)x1+2x2+x4=4x1,

x2,

x3,

x4,

x5,

x6≥

0我们很容易得到(1.7)的初始基可行解(0,0,0,4,3,6),但他不满足(1.6)。如果用单纯形法对(1.7)进行求解过程中，能将x5、

x6从基变量替换出，都变为非基变量，即

x5、

x6都取零，则(1.7)的解也满足(1.6)。下面介绍能将人工变量x5、

x6从基变量替换出的方法。

大M法将

(1.7)的目标函数中人工变量系数设置为充分大的正数M，变成如下的线性规划问题：

minf=4x1+x2+Mx5+Mx6

s.t.3x1+x2+x5=34x1+3x2-x3+x6=

6(1.8)x1+2x2+x4=4x1,

x2,

x3,

x4≥

0在用单纯形法对(1.8)进行求解过程中，其基可行解中，只有三个变量不为零。因此，只有x5、

x6都取零时，才可能达到最优，即将x5、

x6从基变量替换出，都变为非基变量。上例的大M法求解过程如下：Cj4100MMCB基bx1x2x3x4x5x6Mx53Mx660x44

31001043-1001120100检验数σj

4-7M1-4MM0004x1110x620x43

11/3001/3005/3-10-4/3105/301-1/30检验数σj

0-(1+5M)/3M0-(4-7M)/30Cj4100MMCB基bx1x2x3x4x5x64x51Mx620x43

11/3001/3005/3-10-4/3105/301-1/30检验数σj

0-(1+5M)/3M0-(4-7M)/304x13/51x26/50x41

101/503/5-1/501-3/50-4/53/500111-1检验数σj

00-1/50-8/5+M1/5+M4x12/51x29/50x31

100-1/52/500103/5-1/5000111-1检验