文库发布：线性规划

第一章线性规划与单纯形法线性规划（LP）特点：历史悠久、理论成熟、应用广泛研究的问题：

1.在人财物一定的条件下，如何合理安排使用取得最好的经济效益

2.任务已定，如何安排计划，使人财物最省

1939前苏联科学家康脱诺维奇（KouTopobuz）首先提出，著“生产组织与计划中的数学方法”解乘数法

1947年美军事顾问Dantijig提出“线性规划单纯形法”并为此当选美国科学院院士，在1992年又写“最佳资源利用的经济计算”

1975年在获诺贝尔奖（经济奖）的32人中有13人研究LP问题线性规划数学模型例一、生产计划问题某厂计划生产Ⅰ、Ⅱ两种产品，生产单位产品需要的设备台时、原材料消耗量及所获得的利润见下表，如何计划安排，获利最多(把给定条件列成表达式——建立模型)

ⅠⅡ设备原材料A4016Kg

128台时原材料B0412Kg利润23设生产两种产品的数量分别为X1，X2利润Maxz=2X1+

3X2约束条件X1+

2

X2≦84X1

≦164

X2≦12X1，

X2≧0例二、混合问题（营养师配方）补品（添加剂）求最低成本的混合方案成分原料

ABC单位成本1410226125317164253812148单位补品维生素最低含量数学模型设单位添加剂使用第I种原料的数量为XiMinz=2X1+

5X2+6X3+

8X44X1+

6X2+X3+

2X4≥12X1+

X2+7X3+

5X4≥142X2+X3+

3X4≥8X1，

X2，X3，X4≥0※决策变量：决策者控制的因素（X1，X2，……Xn

）非负条件※约束条件：约束决策变量取值（线性等式或不等式）※目标函数：Z=f（X1，X2，……Xn

）决策变量的线性函数，求Z的极值LP数学模型:有变量,有影响变量取值的约束条件,有要达到的目标LP数学模型一般表达式目标函数Maxz（Minz）=C1X1+C2X2+……CnXna11X1+a12X2+……a1nXn≤（=≥）b1a21X1+a22X2+……a2nXn≤（=≥）b2

……

am1X1+am2X2+……amnXn≤（=≥）bm非负条件X1，X2，……Xn≥0线性规划数学模型特点：约束条件例3合理下料问题有一批某种型号的圆钢，长8米，需裁取2.5米的毛坯100根，长1.3米的毛坯200根，如何下料，既满足需求，用料又最省？据经验列出所有可能搭配方案毛坯型号下料件数方案需要根数2.51001.3200Ⅰ30余料0.5Ⅱ220.4Ⅲ140.3Ⅳ060.2设Xj为第j种方案所用原材料的根数，则该问题的数学模型为MinZ=X1+X2+X3+X43X1+2X2+X3≥1002X2+4X3+6X4≥200X1，X2，X3，X4≥0上面问题也可以料头最小为目标毛坯型号下料件数方案需要根数2.51001.3200Ⅰ30余料0.5Ⅱ220.4Ⅲ140.3Ⅳ060.2MinZ=0.5X1+0.4X2+0.3X3+0.2X43X1+2X2+X3=1002X2+4X3+6X4=200X1，X2，X3，X4≥0例4、运输问题123库存量

A21350

B22430

C34210仓库工厂需求量

401535设i—仓库，j—加工厂Xij—表示从第i个仓库运至第j个加工厂的数量AX11X12X13把仓库棉花运至加工厂，怎样运输，费用最小？（下表为单位运价表）BC123X11+X12+X13=50X21+X22+X23=30X31+X32+X33=10X11+X21+X31=40X12+X22+X32=15X13+X23+X33=35Xij≥0，i=1，2，3； j=1，2，3MinZ=2X11+X12+3X13

+2X21+2X22+4X23

+3X31+

4X32+2X33i=1，2，3j=1，2，3123库存量

A21350

B22430

C34210仓库工厂需求量

401535设Cij为仓库i至工厂j的单位运价；

ai

为第i个仓库库存量；

bj

为第j个工厂需求量。500万m3200万m3工厂一，2万m3污水工厂二，1.4万m3污水例5[教材的例2]某河流附近有2个化工厂，流经工厂1的河流流量为每天500万m3

，两个工厂之间有一条流量为每天200万m3支流，工厂1每天排放污水2万m3，工厂2每天排放污水1.4万m3，从工厂1排出的污水流到工厂2以前，有20％自然净化，一厂处理污水成本1000元/万m3，二厂处理污水成本800元/万m3，根据环保要求污水含量不大于0.2％，每厂各处理多少污水，使总费用最低。分析问题①决策变量:各厂污水处理量

②约束条件：各段河流的污水含量满足环保要求，要反映出各段河流的污水量、各段河流的流量、处理能力与污水排放量的关系③目标：处理成本最小500万m3200万m3工厂一,2万m3污水工厂二,1.4万m3污水设各厂污水处理量分别为X1、X2MinZ=1000X1+800X2（2-X1）/5000.2[0.8(2-X1)+(1.4–X2)]/(500+200)0.2X12

,X21.4

X1

,X201.变量之间是线性关系2.问题的目标可用数值指标表达3.达到目标的方案有多种4.有影响的若干约束条件建立线性规划数学模型必须具备的条件：线性规划数学模型的标准型一、一般型

Maxz（Minz）=C1X1+C2X2+……+CnXna11X1+a12X2+……+a1nXn≤（=≥）b1a21X1+a22X2+……+a2nXn≤（=≥）b2

……

am1X1+am2X2+……+amnXn≤（=≥）bmX1，X2，……，

Xn≥0二、标准型

Maxz=C1X1+C2X2+……+CnXna11X1+a12X2……+a1nXn=b1a21X1+a22X2+……+a2nXn=b2

……am1X1+am2X2+……+amnXn=bmX1，X2，……，

Xn≥0▲目标函数求最大值▲所有约束为严格等式▲所有决策变量Xj≥0▲约束条件右端bi≥0线性规划数学模型标准形式的其它表示方法1.简略型

MaxZ=∑CjXj∑aijXj=bii=1，2，……，mXj≥0标准型特征：标准型的一般形式Maxz=C1X1+C2X2+……+CnXna11X1+a12X2+……a1nXn=b1a21X1+a22X2+……a2nXn=b2

……am1X1+am2X2+……amnXn=bm

X1，X2，……，

Xn≥0标准型的一般形式Maxz=C1X1+C2X2+……+CnXna11X1+a12X2+……a1nXn=b1a21X1+a22X2+……a2nXn=b2

……am1X1+am2X2+……amnXn=bm

X1，X2，……，

Xn≥0定义价值向量C=(C1,C2,…,Cn)决策变量向量X=系数列向量Pj=资源向量b=Maxz=CXXj≥02.向量型Maxz=CXXj≥0系数矩阵A=3.矩阵型标准型的一般形式Maxz=C1X1+C2X2+……+CnXna11X1+a12X2+……a1nXn=b1a21X1+a22X2+……a2nXn=b2

……am1X1+am2X2+……amnXn=bm

X1，X2，……，

Xn≥0Maxz=CXAX=bXj≥01.约束条件2.目标函数3.变量有如下几种情况1.“≤”→“=”不等式左端加上非负松弛变量（资源的剩余量）如例1中X1+2X2≤8→X1+2X2

+X3=82.“≥”→“=”不等式左端减去非负松弛（剩余）变量（超指标量）如例2：4X1+

6X2+X3+

2X4≥12→4X1+

6X2+X3+

2X4–X5

=12三、化标准型3.“Min”→“Max”目标函数两侧同乘“-1”MinZ=CX→Max（-Z）=-CX，令Z′=-Z则MaxZ′=-CXZZ-0≤X1+6≤16令X1′=X1+60≤X1′≤16原模型变为X1′+X2≤11X1′≤16X1′，X2≥0例：X1+X2≤5①-6≤X1≤10②X2≥0③方法：②两侧同加6，得若Xj为自由变量→非负变量方法：Xj=Xj′-Xj〞（Xj′，Xj〞≥0）4.变量无非负要求→有非负要求

两边乘“-1”，则-bi≥0例：化标准型MinZ=-X1+2X2-3X3X1+X2+X3≤7X1-X2+X3≥2

X1，X2≥0，X3无约束Max（-Z）=X1-2X2+3X3X1+X2+X3

+X4=7X1-X2+X3-

X5=2X1，X2

，X4，X5≥0，X3无约束Max（Z′）=X1-2X2+3X3′-3X3〞X1+X2+X3′-X3〞+X4=7X1-X2+X3′-X3〞-

X5=2X1，X2，X3′,X3〞，X4，X5≥05.“bi≤0”→“bi“≥0图解法对线性规划数学模型

MaxZ=CX①AX=b②X≥0③

定义1：满足约束条件

②③的解称为线性规划问题的可行解定义2：满足①的可行解为线性规划问题的最优解图解法步骤：例：Maxz=2X1+

3X2X1+

2

X2≦8①4X1

≦16②4

X2≦12③X1，

X2≧0④（模型不需化成标准型）1.建立直角坐标系，确定可行域（找出满足4个约束条件的边界线）012345678123456x2

X1≥0X2≥0第一象限

X1+

2

X2≤8

先作X1+

2

X2=8（两点式）⑴⑵⑶B(42)2.求最优解z=2X1+

3X2（或X2=-2/3X1+

1/3Z）Z取不同值代表斜率相同的一簇平行线例6=2X1+

3X2，该直线上所有点目标值均为6，故称等值线。作出2X1+

3X2=6直线（特殊点（3,0）（0,2））上下平移该直线（往上移Z增加），在刚刚离开可行域时，得到最优解BOACD﹒例2：Max

z=2X1+

4X2X1+

2

X2≦8①4X1

≦16②4

X2≦12③X1，

X2≧0有无穷多最优解（BC线段上）012345678123456x2

⑴⑵⑶B(42)OACD例3：Maxz=2X1+

4X22X1+

X2≧

8①-2X1+

X2≦2②X1，

X2≧0③﹢﹢﹢﹢﹢﹢224468X1X2①②无有限最优解（无界解）例4：Maxz=3X1+

2X2-X1-

X2≧

1①X1，

X2≧0无可行解练习：Minz=2X1+3X2X1+

2

X2≧4①2X1+

X2≧4②X1-

2X2≧

-4③X1，

X2，

X3≧0﹢﹢﹢﹢﹢﹢224468X1X2①②③﹒总结有解无解唯一解无穷多解无有限最优解无可行解几点结论：①若线性规划问题有可行解，则可行域是一个凸多边形。(不可能出现右图情况),可行域有可能有界，也可能无界。②若线性规划问题有最优解，则最优解一定可以在可行域的顶点得到。最优解可能只对应一个顶点（唯一解），也可能对应可行域一个边（无穷多解）。③若可行域无界，也可能存在最优解。线性规划解的情况线性规划解的性质复习

1.线性组合设P1,P2,……,Pm为m个n维向量,若存在一组K1,K2,……Km,使向量b=K1P1+K2P2+……+

KmPm,则称向量b可由P1P2……Pm线性组合

2.线性相关：设P1，P2

，……

，Pm为m个n维向量，若存在一组不全为零的数使得K1P1+K2P2+……+KmPm=0成立，则称向量组P1，P2……Pm线性相关，否则为线性无关。

3.向量组的秩向量组的极大线性无关组所含向量的个数

4.基：在n维向量空间存在一组向量，如果该向量组线性无关，且每一个n维向量都可由该向量组线性组合表示出来，则这组向量称为n维空间的一个基。如n维基本向量组e（1）

e（2）

……e（n）

是n维向量空间的一个基.例P=23=210+301=2e（1）+3e（2）例P=423=4100+2010=4e（1）

+2e（2）

+3e（3）001+3对线性规划问题Maxz=C1X1+C2X2+……+CnXna11X1+a12X2+……a1nXn=b1a21X1+a22X2+……a2nXn=b2

……am1X1+am2X2+……amnXn=bmX1，X2，……Xn≥0系数矩阵A=p1p2……pmpm+1……pna11a12

……a1ma1m+1……a1na21a22

……a2ma2m+1……a2n…………am1am2

……ammamm+1……amn基：设A为线性规划约束方程中m×n维系数矩阵(n>m)，其秩为m（即A中不等于零的子式的最大阶数或A中极大线性无关组所含向量的个数）在A中任取m个线性无关的列向量组成一个m×m的非奇异子矩阵B（∣B∣≠0），则称B为LP的一个基。A=a11a12

……a1ma1m+1……a1na21a22

……a2ma2m+1……a2n…………am1am2

……ammamm+1……amnm列Bn-m列N基的个数最多为Cnm（有限个）例：Maxz=3X1+

X22X1+

3

X2+

X3=4①3X1+

X2+

X4=5②X1，

X2≧0③A=3103101从A中任取m=2个线性无关的列向量组成一个基，不妨设基B=（P3，P4）则N=（P1，P2）组成基的向量P3，P4称为基向量，其余向量P1，P2称为非基向量；基向量P3、P4对应的变量X3、

X4为基变量，其余变量X1、X2为非基变量。令方程组中非基变量X1=X2=0，解方程组得基变量X3=4，X4=5，则解X=（0，0，4，5）T为一基本解基本解：设B为线性规划的一个基，若令方程中非基变量都等于零，所得方程组的解，称为方程组AX=b关于基B的基本解由于基的个数最多为Cnm，因此基本解的个数有限（P1P2P3P4）n=4，m=2，秩m=2，基的个数为C42=63103101基基向量非基向量基变量非基变量基本解（P1P2)P1P2

P3P4X1,

X2X3,X4

(11/7,2/7,0,0)T（P1P3)

P1P3

P2P4X1,

X3X2,X4

(5/3,0,2/3,0)T（P1P4)

P1P4

P2P3X1,

X4X2,X3

(2,0,0,-1)T（P2P3)P2P3P1P4……

(0,5,-11,0)T（P2P4)……(0,4/3,0,11/3)T（P3P4)

P3P4

P1P2X3,

X4X1,X2

(0,0,4,5)TX=(11/7,2/7,0,0)T满足非负条件，既是基本解又是可行解，称为基本可行解，对应的基为可行基（即满足非负条件的基本解为基本可行解，基本可行解非零分量都是正分量，其个数小于或等于m）X=(2,0,0,-1)T不满足非负条件，是基本解不是可行解（P1P2P3P4）该模型约束方程

2X1+

3

X2+

X3=4①3X1+

X2+

X4=5②系数矩阵A=基的个数=C42=6上例：Maxz=3X1+

X22X1+

3

X2≤4①3X1+

X2≤5②X1，

X2≧0③基本解X(X1,

X2X3,

X4)T

A：(11/7,2/7,0,0)TB：(5/3,0,2/3,0)TC：(2,0,0,-1)TD：(0,5,-11,0)TE：(0,4/3

,0,11/3)TF：(

0,0

,4,5)T基本可行解A、B、E、F最优解A、B线性规划问题解的几何意义⑴0

12312x2

x1⑵ABCDFE可行解：满足约束条件①②③的解为线性规划问题的可行解(可行域内各点）基本解：图中各约束线之间，约束线(或延长线)与坐标轴之间的交点A、B、C、D、E、F都是基本解基本可行解:可行域的各顶点A、B、E、F一、基本概念

1.凸集：给定一个点集K（n为欧氏空间）在集合内任取两点，如果连线上的点也在集合内，则K为凸集。即点集K,集合内任意两点X（1）∈K,X（2）∈K，若X（1）、X（2）连线上的点X=αX（1）+(1-α)X（2）∈K(0≤α≤1),则K为凸集。﹒﹒X（1）X（2）X﹒﹒﹒﹒X（1）X（2）X凸集非凸集非凸集线性规划问题的几何意义

2.凸组合：设X（1）、X（2）……X（k）为n维空间K个点，若存在一组数

1

2……

k且0≤

i≤1，∑

i=1使X=

1X（1）+

2X（2）+……

+

k

X（k）,则称X为X（1）、X（2）、……X（k）的凸组合。

3.极点：设K为凸集,有点X∈K,若X不能用K内不同两点X(1)、X(2)线性组合表示为X=

X（1）+（1-

）X（2）（0＜

＜1），即X不在X（1）、

X（2）连线上，则X为极点(顶点)。﹒﹒X（1）X凸集二、解的性质定理1：若线性规划问题存在可行域，则其可行域为凸集。证明：设LP问题可行域为D，D={X∣AX=b，X≥0}D内任意取两点X（1）∈D，X（2）∈D，

则X（1）、X（2）必然满足约束条件，即

AX（1）=b

，X（1）≥0AX（2）=b

，X（2）≥0X（1）、

X（2）连线上的点可表示为

X=

X（1）+（1-

）X（2）（0≤

≤1），∵，1-

≥0；X（1），X（2）≥0∴X≥0

而AX=A

X（1）+A（1-

）X（2）

=

b+（1-

）b=b∴X是可行解,即X∈D，因此D为凸

集引理1：线性规划问题的任一可行解为基可行解的充要条件是该可行解的正分量(非零分量)所对应的系数列向量是线性无关。证明：

必要性：即已知X是基本可行解，证明X的正分量对应的系数列向量线性无关由基本解的定义，X的正分量只能是基变量，其系数列向量线性无关

充分性：已知X的正分量所对应的系数列向量线性无关，证明X是基本可行解如果X的非零分量对应的系数列向量P1，P2……Pk线性无关，则k≤m

当k=m时，P1，P2……Pk刚好组成一个基，对应解一定是X，所以X为基本可行解当k＜m时,一定可以从其余的n-k个列向量中选出m-k个,与P1，P2……Pk构成极大线性无关组，刚好组成一个基,对应的唯一解恰为X,根据定义它是基本可行解

定理2：线性规划问题的基可行解对应于可行域顶点。反证法充分性：不是基本可行解不是可行域的顶点必要性：不是可行域的顶点不是基本可行解证明的思路基可行解正分量对应的系数列向量p1，p2……pm线性无关；

顶点不能用不同的两点连线表示。引理2：若可行域为有界凸集，则任何点X∈K都可表示为K的顶点的凸组合。p18例5定理3：LP问题有最优解,一定可在顶点上得到证明：设LP问题可行域D有K个顶点

X（1），X（2）

……X（k）最优解为X（0）,Z＊=CX（0）

，

若X（0）不是顶点,据引理2,X（0）可以表示为可行域D的顶点的凸组合,即X（0）=

1X(1)+

2X(2)……

k

X(k)0≤

i≤1，∑

i

=1CX（0）=C(

1X（1）+

2X（2）……

kX（k）)=

1CX（1）+

2CX（2）……+

k

CX（k）

设CX（m）=max{CX（1）,CX（2）,……,CX（k）}则

CX（0）≤CX（m）∑

i=

CX（m）①

而X（0）为最优解，由最优解性质CX（0）≥CX（m）②

由

①

②得

CX（0）=

CX（m）,因此CX（m）为最优解且又是顶点,即目标函数在顶点处达到最优线性规划问题解的性质：

1.可行解的集合是凸集，也可能是无界域

2.凸集非空，必有顶点（有限个）

3.每个基本可行解对应可行域的一个顶点

4.基本可行解的个数有限

5.线性规划问题若有最优解，一定可在顶点中找到

单纯形法的步骤

1.找出一个初始基本可行解

2.判断是否为最优解，若是则结束，否则进行下一步

3.求下一个基本可行解，使目标得以改善，返回2重复2，3，直到最优或判断无最优解为止。单纯形法引例

例：求下面LP问题的最优解

Maxz=2X1+3X2+0X3+0X4+0X5①X1+2X2+X3

=84X1+X4

=16②4X2+X5

=12X1,

X2,X3,X4,X5≧0③解：1.确定初始基本可行解A=140204100010001初始可行基B1=（P3,P4,P5）,X3,

X4,

X5—基变量X1,

X2—非基变量将基变量用非基变量表示由②得

X3=8-X1-

2X2

X4=16-4X1

④

X5=12-4X2

令X1,X2=0，得初始基本可行解

X（1）=(0,0,8,16,12)T,Z=02.最优解判断：④代入①中得

Z=0+2X1+3

X2

⑤X1↑→Z↑,X2↑→Z↑3.由一个基本可行解→另一基可行解（选进基变量和离基变量）

3＞2,选X2→进基变量,X2

从0↑,X1仍为非基变量X1=0，选X2进基,由④要保证解的可行性,须满足:X3=8-X1-

2X2≥0,X2≤8/2X4=16-4X1≥0X5=12-4

X2≥0,X2≤12/4X2≤Min{8/2,12/4},X2最大值为3当X2==Min{8/2,12/4}=3时,X5=0故选X5离基(即为保证解的可行性,选最小比值对应的基变量离基)，新基B2=（P3，P4，P2）基变量移至左侧X3+

2X2=8-X1⑤X4=16-4X1⑥

4X2

=12-X5

⑦初等变换⑦÷4，⑦×（-1/2）+

⑤，

X3=2-X1+1/2X5X4=16-4X1X2=3-1/4X5令X1=X5=0X（2）=（0,3,2,16,0）T,

Z（2）=9,将X3、X4

、X2代入目标函数①Z=2X1+3X2=9+2X1–3/4X5由于目标函数表达式中X1系数为正,说明X（2）不是最优解选X1进基，Min{2/1,16/4}=2

选X3离基，同理X（3）=（2,3,0,8,0）

……X（4）=（4,2,0,0,4）

Z=14-3/2X3–1/8X4X（1）=（0，0，8，16，12）TZ（1）=0对应O点X（2）=（0，3，2，16，0）TZ（2）=9对应D点X（3）=（2，3，0，8，0）Z（3）=13对应C点X（4）=（4，2，0，0，4）Z（4）=14对应B点012345678123456x2

⑴⑵⑶B(42)OACD﹒对上述过程总结如下1.先确定一个初始基本可行解2.将约束中的基变量用非基变量表示代入目标函数中，消除基变量（即用非基变量表示目标函数），其中非基变量Xj的系数

j称为检验数3.判断最优若目标函数中对于所有非基变量Xj均有

j≤0，则当前的基本可行解为最优解，结束；否则进行下一步4选进基变量若有非基变量Xk系数k≥0，则可选Xk为进基变量5.选离基变量X保证解的可行性，按方程右端常数与进基变量正分量的最小比值，确定离基变量，若不存在，即Xk可增至∞，则Z→∞，无有限最优解6.迭代得新的基本可行解，返回3单纯形法原理解决三个问题

1如何确定初始基本可行解2.最优解如何判别3.基本可行解的改进

一、初始基可行解的确定初始基可行解与初始可行基是对应的，找初始可行基的方法有：①若线性规划模型约束方程的系数矩阵中，存在一个m阶的单位矩阵，该单位矩阵所对应的系数列向量就是一个初始可行基。②若原线性规划模型的所有约束方程都是“≤”号的不等式，则引入的松弛变量的系数列向量就是一个初始可行基。

Maxz=2X1+3X2+0X3+0X4+0X5X1+2X2+X3

=8①4X1+X4

=16②4X2+X5

=12X1,

X2,X3,X4,X5≧0③

③非以上两种情况，应采用特殊的方法来确定初始可行基。(参见后面介绍)二、最优解判别：设模型已经标准化，对变量重新编号后,可表示为Maxz=C1X1+C2X2+…CmXm+Cm+1Xm+1+…

+CnXnX1+a1m+1Xm+1+……+a1nXn=b1X2+a2m+1Xm+1+……+a2nXn=b2

……

Xm

+amm+1Xm+1+……+ammXn=bmX1，X2，……，Xn≥0基B=（P1，P2，……,Pm）=I

约束方程又可表示为i=1，2，…

，mXi为基变量,Xj为非基变量用非基变量表示的目标函数表达式

其中j称为检验数，令非基变量Xj=0，目标函数Z=∑Cibi

最优解判断定理

1.对解X，若所有非基变量的检验数

j全≤0，则X为最优解

2.对解X，若存在

j全≤0，且某个非基变量的检验数

j

=0，则LP问题有无穷多最优解

3.对解X，若某个非基变量的检验数

m+k＞0且对应的列向量Pm+k=（a1m+k，a2m+k，…amm+k

）T≤0，则LP问题无有限最优解三.基变换①进基变量的确定——最大法则：选正检验数最大的非基变量进基②离基变量的确定——最小比值法则：各约束方程的右端常数和进基变量正系数的比值。当=minaim+k＞

0=bLaLm+k则选XL离基Max{

j∣

j＞0}=

m+k则选Xm+k进基四、迭代所谓迭代就是通过初等变换将进基向量变换成与离基向量相同的单位列向量的过程。单纯形表

一、单纯形表的建立

X1+

a1m+1Xm+1+……+a1nXn=b1X2+

a2m+1Xm+1+……+a2nXn=b2……

Xm

+

amm+1Xm+1+……+amm

Xn=bm-Z+C1X1+C2X2+……+CmXm

+

Cm+1Xm+1+……+CmXn=0增广矩阵

-ZX1X2……Xm

Xm+1……Xm

b010……0a1m+1……a1nb1

001……0a2m+1……a2nb2

000……1amm+1……amn

bm1C1C2……CmCmm+1……Cn

0

-ZX1X2……Xm

Xm+1……Xn

b010……0a1m+1……a1nb1

001……0a2m+1……a2nb2

……

……

000……1am+1……amn

bm

10

0

……0

Cm+1-∑Ciaim+1……Cn-∑Ciain

-∑Cibi

-ZX1X2……Xm

Xm+1……Xn

b010……0a1m+1……a1nb1

001……0a2m+1……a2nb2

……

……

000……1amm+1……amn

bm

1C1C2……CmCmm+1……Cn

0Cj-∑Ciaij表示变量Xj的检验数,根据上述增广矩阵设计单纯形表（见下页）增广矩阵对增广矩阵进行初等变换

X1X2…

…Xm

Xm+1…Xmk

…Xm

C1C2……CmCm+1…Cm+k…CnCBXBbX1X2

XmC1C2

Cmb1b2

bm10

001

0………………00

1a1m+1a2m+1

amm+1………a1m+ka2m+k

amm+k………a1na2n

amn-Z-∑Cibi

00……0

Cm+1-∑Ciaim+1

…Cm+k-∑Ciaim+k

…Cn

-∑Ciain

1.先填第2行所有变量、第2列XB列填所有的基变量2.第一行填各变量的价值系数Cj、第一列CB列填基变量对应的价值系数，第3列约束方程右端常数，右下填各约束方程变量系数3.最后一行填非基变量表示的目标函数中各变量系数，基变量系数为零，非基变量系数即检验数

j=Cj-∑Ciaij

刚好等于Xj的价值系数减去CB列各元素与Xj列各元素的对应乘积，列根据最小比值原则计算后填上，当aik≥0，i=bi/aik；当aik≤0，i=∞单纯形法步骤例:Maxz=2X1+

3X2X1+

2

X2+

X3=84X1+X4=164

X2+

X5=12X1，

X2≧01.化标准型，确定初始基、初始解，列初始表，其中X1X2X3X4X5

23000CBXBbX3X4X50

0

08

16

121

4

02

0

4*1

0

00

1

00

0

1

j

j=Cj-∑Ciaij

1=2-（0×1+0×4+0×0）=2

2=3-（0×2+0×0+0×4）=3230002最优解判别

1=2＞0，

1=3＞0表中解不是最优3.选进基变量、离基变量

Max{2，3}=3选X2进基，计算比值填入表中，选离基变量4-3Min{4，3}=3，X5离基4.迭代，建新表初等行变换，将进基向量中主元素(进基变量所在列与离基变量行的交叉元素)变为1，其余元素变为0X1X2X3X4X5

23000CBXBbX3X4X58

16

120

0

01

4

0

2

0

4*1

0

00

1

00

0

10230004-3X3

X4X20

0

3301001/4

164001021*010-1/2-92000-3/424-X1

X4X22

0

3301001/4

800-412*21010-1/2-1300-201/4………二、单纯形法的计算步骤

1.将LP问题化成标准型，确定初始基、初始解，列初始表

2.最优解判别检查各非基变量的检验数，若所有

j全≤0，则表中基本可行解为最优解，停止，否则进行下一步

3.在

j＞0中，若某正检验数所对应的系数分量全部小于等于零，则此问题无界，否则转入下一步；

4.确定进基变量、离基变量在

j＞0中选Max{

j∣

j＞0}=

k则选Xk进基，计算

=miniaikbaik

＞

0=blalk则选XL离基，比值填入列

5.迭代：建新表，原表XB列中Xl换成Xk

，

CB列中CL换成Ck，

初等变换，将进基向量主元素（进基变量与离基变量的交叉元素）变为1，其余元素变为06.计算检验数返回2，重复2-6几种特殊情况例2求解下列模型该模型的初始单纯形表及某步的单纯形表为：该模型的初始单纯形表及某步的单纯形表为：24000XBbX1X2X3X4X5X3X4X543810101*2100010001-Z024000……X3X2X123200101010021-2-101-Z-160000-2可以看出，已经得到最优解，但存在一个非基变量的检验数为零。若以该非基变量为进基变量，再迭代，将得到下面的单纯形表。24000XBbX1X2X3X4X5X3X2X12320010101002*1-2-101-160000-2X4X2X11240010101/2-1/21100-1/21/20-160000-2因此，该线性规划已经得到了两个最优解，那么这两点连线中的任一点都是最优解，即存在无穷多最优解。无穷多最优解的表示方法为：例对于下列单纯形表，分析其结果XBbX1X2X3X4X5X3X4X5438-10-1012100010001-Z025000根据无界解判别定理，该问题无有限最优解。

退化问题在采用单纯形法求解线性规划问题时，可能会出现循环迭代的情况，产生退化解。退化解:基本可行解中非零分量个数少于m,即有基变量取值为0的情况在确定离基变量时存在有两个以上相同的最小比值，或在确定进基变量时存在有两个以上相同的最大正系数值，会造成下一次迭代中有一个或几个基变量等于零，这就是退化解。

虽经过基变换，但目标函数值不变，此时不同的基却表示为同一顶点，其特例是永远达不到最优解。

1974年Bland提出了一种解决退化问题简便规则——勃兰特规则选进基变量,若有两个以上最大正检验数,选下标小的非基变量进基;选离基变量,若有两个以上最小比值，选一个下标小的先离基几点注意事项

1.检验数的计算（2种方法）

Xj的检验数

j=Cj-∑Ciaij

，即

j等于Xj的价值系数Cj减去CB列的各元素与Xj列各元素的对应乘积行变换方法计算初等变换将上一表中检验数行，进基变量检验数变为0。X1X2X3X4X5

23000CBXBbX3X4X58

16

120

0

01

4

0

2

0

4*1

0

00

1

00

0

1

j23000X3X4X20

0

330100¼

①

164001021*010-1/2

j2000-3/4-①×(-3)+②②

2.进基变量的选取对max问题叛别准则

j≤0，选正检验数最大的非基变量进基；若有两个以上最大正检验数选下标小的非基变量进基，得到一个退化的基本可行解

对min问题叛别准则

j≥0，从负检验数中选绝对值最大的，若Max{∣

j∣

j＜0}=

k，Xk进基

3.最小比值

=miniaikbaik

＞

0=blalk上式只有aik＞0才有意义，若所有aik全≤0，则为无界解；若有两个以上最小比值，选一个下标小的先离基，其余的仍为基变量，得到一个退化的基本可行解

4.无有限最优解迭代的任一步若有

k＞0，但所有aik全≤0，则LP问题有无界解，停止迭代

5.最优解是否唯一若所有非基变量检验数均为负，则有唯一最优解，否则若有某个非基变量Xj检验数等于

j=0，则有无穷多最优解，若选择Xj进基，目标函数不变，即新找到的基本可行解也是最优解

6.最优判别准则对最大值问题，若所有非基变量的检验数

j全≤0，则解X为最优解；对最小值问题，若所有非基变量的检验数

j全≥0，则解X为最优解。单纯形法是从一个初始基可行解开始的，如果在线性规划问题的系数矩阵中不存在一个m阶单位矩阵，即很难找到一个初始可行基怎么办？确定初始可行基的其它方法——人造基方法（人工变量法）

人工变量的引入对“≥”不等式约束：在等式左边减去一个非负的剩余变量，再加一个非负的人工变量对等式约束：在等式左边加一个非负的人工变量处理人工变量有两种方法：1.大M法2、两阶段法单纯形法的进一步讨论

1.大M法大M法也称惩罚法，即对最大化线性规划，在原来约束条件中增加人工变量，然后在目标函数中给人工变量一个-M系数（M是任意大的正数），作成下面问题

MaxZ=C1X1+C2X2+……+CnXn-MXn+1

-MXn+2

……-MXn+m

a11X1+a12X2+……+a1nXn

+Xn+1

=b1a21X1+a22X2+……+a2nXn

+Xn+2

=b2

……am1X1+am2X2+……+amnXn

+Xn+m

=bmX1，X2，……，Xn+m

≥0

用单纯形法求解上面模型，若最优解中人工变量取值均为0，则其最优解的前n个分量就构成原问题的最优解，其最优值就是原问题的最优值，若模型最优解中人工变量取值有不为0的，说明原问题无可行解MinZ=-3X1+X2+X3X1-2X2+X3≤11-4X1+X2+2X3≥3-2X1+X3=1X1，X2≥0MinZ=-3X1+X2+X3+MX6+MX7

X1-2X2+X3+X4=11-4X1+X2+2X3-X5+X6=3-2X1+X3+X7

=1X1，X2≥0X1X2X3

X4X5X6X7-31100MMCBXB