线性规划和单纯形方法详解演示文稿

线性规划和单纯形方法详解演示文稿1当前1页，总共102页。（优选）线性规划和单纯形方法2当前2页，总共102页。一、实例例1生产计划问题Step1:明确问题，设定决策变量设I、II两种产品的产量分别为x1,x2

。Step2:确定约束条件产品

I

II资源限量设备

1

2

8台时原料A

4

0

16公斤原料B

0

4

12公斤利润

2

3问应如何安排生产使该厂获利最多？3当前3页，总共102页。说明：OBJ表示Objective;

s.t.表示Subjectto

Step3:给出目标函数Step4:整理数学模型4当前4页，总共102页。例2

现要做100套钢架，每套需2.9米、2.1米和1.5米的元钢各一根。已知原料长7.4米，问如何下料，使余料最少？设I,II,III,IV,V分别代表五种不同的原料用量方案,x1,x2,

x3,x4,x5分别代表采用各方案下料的元钢的根数。方案根数2.9米2.1米1.5米合计余料I

x11037.40IIx22017.30.1IIIx30227.20.2IVx41207.10.3Vx50136.60.8解：5当前5页，总共102页。6当前6页，总共102页。LP(LinearProgramming)是数学规划的一个重要分支，数学规划着重解决资源的优化配置，一般可以表达成以下两个问题中的一个：（1）当资源给定时，要求完成的任务最多；（2）当任务给定时，要求为完成任务所消耗的资源最少。若上述问题的目标﹑约束都能表达成变量的线性关系，则这类优化问题称LP问题。LP是一种解决在线性约束条件下追求最大或最小的线性目标函数的方法。7当前7页，总共102页。

目标函数用决策变量的线性函数来表示。按问题的不同，要求目标函数实现最大化和最小化。

每一个问题变量都用一组决策变量（x1,x2,…,xn）表示某一方案，这组决策变量的值代表一个具体方案，这些变量是非负且连续的。存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。结论：线性规划是研究在一组线性不等式或线性等式约束下，使得某一线性目标函数取最大或最小的极值问题。二、线性规划问题（LP问题）的共同特征8当前8页，总共102页。Max(Min)Z=c1x1+c2x2+…+cnxn(1)

a11x1+a12x2+…+a1nxn

≤(=,≥)b1a21x1+a22x2+…+a2nxn

≤

(=,≥)b2

s.t.

……(2)am1x1+am2x2+…+amnxn

≤

(=,≥)bmxj≥0,j=1,2,…，n(3)(1)—目标函数；(2)约束条件；(3)决策变量非负n－变量个数；m－约束行数；cj－价值系数；bi－右端项或限额系数；aij－技术系数；xj—决策变量线性规划模型的一般形式为：9当前9页，总共102页。线性规划模型的紧缩形式n－变量个数；m－约束行数；cj－价值系数；bi－右端项或限额系数；aij－技术系数；xj—决策变量10当前10页，总共102页。练习题：是否为线性规划模型？11当前11页，总共102页。1.线性不等式的几何意义—半平面作出LP问题的可行域作出目标函数的等值线移动等值线到可行域边界得到最优点2.图解法步骤三、两变量线性规划问题的图解法12当前12页，总共102页。4x1=164x2=12x1+2x2=8x1x248Q1

4Q4

30例1Q2(4,2)Z=2x1+3x2做目标函数2x1+3x2的等值线，与阴影部分的边界相交于Q2(4,2)点，表明最优生产计划为：生产I产品4件，生产II产品2件。Q313当前13页，总共102页。目标函数z=ax1+bx2的值递增的方向与系数a、b有关a>0,b>0a<0,b>0X1X2a<0,b<0a>0,b<0z=ax1+bx2目标函数等值线：ax1+bx2=k移项x2=-a/bx1+k/b目标函数等值线在纵轴上的截距为k/b14当前14页，总共102页。例4Z=3615当前15页，总共102页。例用图解法求解线性规划问题4x1=164x2=12x1+2x2=8x1x248Q14Q430Q2(4,2)Z=2x1+4x2当Z值由小变大时，将与Q2Q3重合Q2Q3上任意一点都是最优解有无穷多最优解（多重解）Q3(2,3)16当前16页，总共102页。例用图解法求解线性规划问题可行域无界—无界解（“无有限最优解”或“最优解无界”）约束条件过分宽松注意：可行域不闭合不一定就会出现无界解，这要看目标函数的性质。若目标函数是min，则有最优解。无论有无最优解，一定有可行解。x2x1x1-x2=1B(2,1)A(1,0)-x1+2x2=0017当前17页，总共102页。例用图解法求解线性规划问题可行域无界—唯一最优解X*=(1,0)，对应于点Ax2x1x1-x2=1B(2,1)A(1,0)-x1+2x2=0018当前18页，总共102页。例用图解法求解线性规划问题可行域无界—无穷多最优解对应于点B沿着OB向右上方发出的射线上的所有点x2x1x1-x2=1B(2,1)A(1,0)-x1+2x2=0019当前19页，总共102页。例用图解法求解线性规划问题

无可行解（可行域为空）x14x1=164x2=12x1+2x2=8x248Q14Q430-2-2x1+x2=4

无最优解20当前20页，总共102页。3.图解法的作用能解决少量问题揭示了线性规划问题的若干规律解的类型可行域类型唯一最优解无穷多最优解最优解无界（无有限最优解）无解（不存在可行域）非空有界无界空集规律1：21当前21页，总共102页。规律2：线性规划问题的可行域为凸集线性规划问题凸集的顶点个数是有限的最优解可在凸集的某顶点处达到22当前22页，总共102页。小结：图解法的基本步骤：1．在直角坐标系作出可行域S的区域（一般是一个凸多边形）2．令目标函数值取一个已知的常数k，作等值线：c1x1+c2x2=k3．对于max问题，让目标函数值k由小变大，即让等值线进行平移，若它与可行域S最后交于一个点（一般是S的一个顶点），则该点就是所求的最优点，若与S的一条边界重合，此时边界线上的点均是最优点4．将最优点所在的两条边界线所代表的方程联立求解，即得最优解X*，把最优解X*带入目标函数，得最优值Z*=CX*注意：若是求目标函数最小值，等值线向反方向移动23当前23页，总共102页。四、线性规划问题的标准型1.标准型（1）目标函数：max（2）约束条件：等式（3）变量约束：非负xj0（4）资源限量：非负bi0标准型的构成要素24当前24页，总共102页。2.线性规划标准型的紧缩形式25当前25页，总共102页。3.线性规划标准型的向量和矩阵表达式矩阵式:MaxZ=CTXs.t.AX=b

X≥0

n向量式:MaxZ=∑cjxj

j=1

ns.t.∑Pjxj=b

j=1

xj≥0,j=1,2,...,n26当前26页，总共102页。4.所有LP问题均可化为标准型（1）最小转换成最大y1=f(x)y2=-f(x)xyx*y1*y2*27当前27页，总共102页。（2）不等式约束条件转换成等式约束条件（3）变量约束转换（4）把bi0转换成bi028当前28页，总共102页。例5

化标准型可化为1.处理决策变量

2.处理约束条件右端

常数项

3.约束条件不等式

4.处理目标函数29当前29页，总共102页。例6

化标准型1.处理决策变量

2.处理约束条件右端

常数项

3.约束条件不等式

4.处理目标函数30当前30页，总共102页。MaxZ’=x1+2x’2+3x4-3x5+0x6+0x7s.t.x1-x’2+x4-x5+x6=7

x1+x’2+x4

-x5-x7=2-3x1-x’2+3x4-3x5=5x’2≥0,xj≥0,j=1,4,5,6,7

MaxZ’=x1+2x’2+3(x4-x5)+0x6+0x7s.t.x1-x’2+(x4-x5)

+x6=7

x1+x’2+(x4

-x5)

-x7=2-3x1-x’2+3(x4-x5)=5x’2≥0,xj≥0,j=1,4,5,6,7

最终结果中间结果31当前31页，总共102页。课堂练习32当前32页，总共102页。五、标准型LP问题解的概念33当前33页，总共102页。（1）（2）（3）约束系数矩阵：x1x2x3x4x5例：34当前34页，总共102页。约束系数矩阵：可能的基矩阵是A中任意三个列的组合，共10个。35当前35页，总共102页。令B==(P1,P2,…,Pm

)

且|B|0

，则称Pj(j=1,2,…,m)

为基向量。与基向量Pj对应的变量xj称为基变量，记为XB=(x1,x2,…,xm

)T，其余的变量称为非基变量，记为XN

=(xm+1,xm+2,…,xn

)T

。36当前36页，总共102页。37当前37页，总共102页。38当前38页，总共102页。B1=(P1,P2)：基令：XB1=(x1,x2)x1=0，

x2=2X=(0,2,0,0)XB1=(0,2)对应于B1的基解为39当前39页，总共102页。线性规划标准型问题解的关系约束方程的解空间基解可行解非可行解基可行解40当前40页，总共102页。例7

MaxZ=2x1+3x2

s.t.x1+2x2≤84x1≤164x2≤12

x1,x2

≥0

六、可行解、基解和基可行解举例非基变量基变量图中的点x4,x5x1=4x2=3x3=-2A基解x3,x5x1=2x2=3x4=8B基可行解x3,x4x1=4x2=2x5=4C基可行解x2,x4x1=4x3=4x5=12D基可行解x2,x3x1=8x4=-16x5=12E基解x1,x5x2=3x3=2x4=16F基可行解x1,x3x2=4x4=16x5=-4G基解x1,x2x3=8x4=16x5=12H基可行解4x1=164x2=12x1+2x2=8x1x20Z=2x1+3x2ABCDEFGH标准型41当前41页，总共102页。例842当前42页，总共102页。第二节LP问题的基本理论一、基本概念43当前43页，总共102页。判断以下图形哪些是凸集，哪些不是凸集？返回44当前44页，总共102页。定理1

LP问题的可行域为一凸集。二、基本定理45当前45页，总共102页。引理线性规划问题的可行解X=(x1,x2,…,xn)T是基可行解的充要条件为X的正分量所对应的系数列向量是线性独立的。46当前46页，总共102页。定理2

线性规划问题的基可行解对应于可行域的顶点。（即：若X是LP问题的可行解，则“X是LP问题的基可行解”等价于“X是LP问题可行域顶点”）设X是基可行解，则其对应的向量组a1,a2,…,am线性无关(m<n)当j>m时，有xj=xj(1)=xj(2)=0.47当前47页，总共102页。48当前48页，总共102页。49当前49页，总共102页。50当前50页，总共102页。定理3

若可行域有界，则LP问题的目标函数一定可以在其可行域的顶点上达到最优。引理若S是有界凸集，则任何一点X∈S可表示为S的顶点的凸组合。51当前51页，总共102页。

线性规划问题的可行域是凸集(定理1)；凸集的顶点对应于基可行解(定理2)，基可行解(顶点)的个数是有限的；若线性规划有最优解，必在可行域某顶点上达到(定理3)。因此,我们可以在有限个基可行解中寻找最优解。由线性代数知，对标准形LP问题，用枚举法可以求出所有基解，再通过观察找出其中的可行解（基可行解），进而找出最优解。但如果变量和方程较多，比如m=50，n=100，所有基解有可能达1029个，即使计算机每秒能求解1亿个这样的方程组，也需要30万亿年！因此，必须寻求有效的算法。为加快计算速度，算法必须具有两个功能，一是每得到一个解，就来检验是否已经最优，若是停止。二是若不是最优，要保证下一步得到的解不劣于当前解。这就是线性规划的单纯形法。

52当前52页，总共102页。第三节单纯形法基本思想检验解的最优性结束Y旋转运算（消元运算）确定另一个基本可行解N化LP问题为标准型，确定一个初始基本可行解化LP问题为标准型，从可行域的某个基可行解（一个顶点）开始，转换到另一个基可行解（另一个顶点），并使目标函数值得到改善，如此反复，从而求得问题的最优解。其实质是逐步迭代（逼近）法。53当前53页，总共102页。一、确定初始基可行解MaxZ=CXs.t.AX=b

X≥0我们首先介绍求初始基可行解的方法。1.若给定问题标准化后（且

）系数矩阵A中存在m个线性无关的单位列向量，则以这m个单位列向量构成的单位子矩阵作为初始基B，则，其余xj=0是基可行解。2.大M法（人工变量法）54当前54页，总共102页。以x2为主元素以x1为主元素例

2x1+x2+2x3=10(1)3x1+3x2+x3=6(2)

x1+1/2x2+x3=5(1)’0x1+3/2x2-2x3=-9(2)’(1)/2,(2)-(1)’×3

x1+0x2+5/3x3=8(1)’’0x1+x2-4/3x3=-6(2)’’(2)’×2/3,(1)’-(2)’’/2二、旋转运算55当前55页，总共102页。三、检验数的意义结论：如果LP问题通过单纯形法迭代到某步时，所有检验数≤0,则该LP问题已得到最优解。MaxZ=CXs.t.AX=b

X≥0若cj-CBB-1Pj=σj≤0,则Z≤Z0,Z0即为最优解.(基变量的检验数必为0)令A=(B,N),X=XB

,C=(CB,CN)

XN由AX=b(B,N)XB=b

BXB+NXN=b

B-1BXB+B-1NXN=B-1b

XN

XB=B-1b－B-1NXN(2)将(2)式代入目标函数得Z=CX=(CB,CN)XB=CBXB+CNXN=CB(B-1b-B-1NXN)+CNXN

XN

=CBB-1b+(CN-CBB-1N)XN=Z0+∑(cj-CBB-1Pj)xj

xj为非基变量56当前56页，总共102页。单纯形法举例化为标准型57当前57页，总共102页。约束方程的系数矩阵对应于B的变量x3，x4，x5为基变量，（1）将（1）代入目标函数后得到z=0+2x1+3x2，

令非基变量x1=x2=0.得到z=0，及一个基可行解X(0)=(0,0,8,16,12)T58当前58页，总共102页。x2=3，x5为换出变量（3）将（3）代入目标函数后得到z=9+2x1－3/4x5，

令非基变量x1=x5=0.得到z=9，及一个基可行解

X(1)=(0,3,2,16,0)T当将x2定为换入变量后，必须从x3，x4，x5中确定一个换出变量，并保证x3，x4，x5≥0，

当x1=0时，由（1）式得到

（2）用高斯消元法，将x2的系数列向量变换为单位列向量，得到59当前59页，总共102页。这时目标函数的表达式是z=14－1.5x3－0.125x4，当将x1定为换入变量后，继续利用上述方法确定换出变量，继续迭代，再得到一个基可行解X(2)=(2,3,0,8,0)T再经过一次迭代，再得到一个基可行解X(3)=(4,2,0,0,4)T4x1=164x2=12x1+2x2=8x1x248Q14Q430Q2(4,2)Z=2x1+3x2Q360当前60页，总共102页。对于线性规划问题：MaxZ=CTX

AX=b，X≥0，可用如下三个判别定理来判别线性规划问题是否已经获得最优解或为无界解。判别定理1

设X为线性规划的一个基可行解，且对于一切j∈J（J为非基变量的下标集）有σj≤0，则X为线性规划的最优解。判别定理2

设X为线性规划的一个基可行解，且对于一切j∈J（J为非基变量的下标集）有σj≤0，同时有某个非基变量的检验数σk=0(k∈J)，则该线性规划有无穷多最优解。判别定理3

设X为线性规划的一个基可行解，若有σk>0(k∈J)，且pk≤0，即aik≤0（i=1,…,m），则该线性规划问题具有无界解（无最优解）。61当前61页，总共102页。一、步骤Step1.化LP问题为标准型,建立初始单纯形表;Step2.若所有检验数≤0,则最优解已达到。否则,计算

,选取σk所对应的变量xk为换入变量（进基变量）;—最大σ（检验数）规则Step3.计算

,选取θl所对应的变量xl为换出变量（出基变量）;—最小比值规则Step4.以alk为主元素进行旋转运算,转Step2;第四节单纯形法的步骤62当前62页，总共102页。cj

CBXBb

x1x2

…

xm

xm+1…

xn

σj

基可行解：

x1=b1,x2=b2,…,xm=bm,xm+1=xm+2=…=xn=01.初始单纯形表c1c2…

cm

cm+1…cnc1x1

c2

x2∶

∶

cm

xmb1

b2

∶bm10…0a1,m+1…

a1n01…0a2,m+1…

a2n∶∶

…

∶

∶

…∶00…1am,m+1…

amn00…0σm+1…

σn-CBTB-1b63当前63页，总共102页。对于上述单纯形表：（1）一个基对应一个单纯形表，且单纯形表中必须有一个初始单位基。（2）从单纯形表中，可立即得到一个基可行解：

x1=b1,x2=b2,…,xm=bm,xm+1=xm+2=…=xn=0（3）用检验数的计算公式很容易计算检验数，并可根据三个判别定理判别上述基可行解是否为最优解或线性规划问题无最优解。64当前64页，总共102页。2.换入变量（进基变量）的选择cj

c1c2…

cmcm+1…ck…cnθ

CBXBb

x1x2

…

xm

xm+1…xk

…

xn

c1x1

c2

x2∶

∶

cm

xmb1

b2

∶bm

10…0a1,m+1…

a1k

…

a1n01…0a2,m+1…

a2k

…

a2n∶∶

…

∶

∶

…∶…∶00…1am,m+1…amk

…amnσj

-CBTB-1b

00…0σm+1…σk…σn选取

所对应的变量xk为换入变量。65当前65页，总共102页。3.换出变量（出基变量）的选择cj

c1…

cl

…

cmcm+1…ck…cnθ

CBXBb

x1…xl

…

xm

xm+1…xk

…

xn

c1x1

∶∶cl

xl∶

∶

cm

xmb1∶bl

∶bm

1…0…0a1,m+1…

a1k

…

a1n∶…∶

…

∶

∶

…∶…∶0…1…0al,m+1…

alk

…

aln∶…∶

…

∶

∶

…∶…∶0…0…1am,m+1…

amk

…amnθ1∶θl∶θmσj

-CBTB-1b

0…0…0σm+1…σk…σn选取

所对应的变量xl为换出变量。66当前66页，总共102页。4.旋转运算cj

c1…

cl

…

cmcm+1…ck…cnθ

CBXBb

x1…xl

…

xm

xm+1…xk

…

xn

c1x1

∶∶cl

xl∶

∶

cm

xmb1∶bl

∶bm

1…0…0a1,m+1…

a1k

…

a1n∶…∶

…

∶

∶

…∶…∶0…1…0al,m+1…

[alk]

…

aln∶…∶

…

∶

∶

…∶…∶0…0…1am,m+1…

amk

…amnσj

ck

xkbl/alk0…1/alk…0al,m+1/alk…1…aln/alkb1’1…-a1k/alk…0a1,m+1’…

0

…

a1n’bm’0…-amk/alk…1am,m+1’…

0

…

amn’67当前67页，总共102页。二、实例化为标准型68当前68页，总共102页。单纯形表算法cj

CBXBb

x1x2x3x4x5

σj

以[4]为主元素进行旋转运算，x2为换入变量，x5为换出变量cj

23000

CBXBb

x1x2x3x4x50x3

0x4

3x2

2163

[1]010-1/2240010401001/4-σj

-9

2000-3/4以[1]为主元素进行运算，x1为换入变量，x3为换出变量0x30x40x523000

81612

12100400100[4]001

2300004-369当前69页，总共102页。cj

23000

CBXBb

x1x2x3x4x52x1

0x4

3x2

283

1010-1/2-00-41[2]401001/412σj

-13

00-201/4以[2]为主元素进行运算，x5为换入变量，x4为换出变量cj

23000

CBXBb

x1x2x3x4x52x1

0x5

3x2

442

1001/4000-21/21011/2-1/80σj

-14

00-3/2-1/80此时达到最优解：X*=(4,2)T,MaxZ=14。70当前70页，总共102页。4x1=164x2=12x1+2x2=8x1x2484O三、单纯形表与图解法的对应关系X1=(0,0)T,Z1=0X2=(0,3)T,Z2=9X3=(2,3)T,Z3=13X4=(4,2)T,Z4=14Q1Q2QQ3基可行解基可行解迭代

顶点相邻的顶点迭代

图解法：单纯形表算法：71当前71页，总共102页。对于极小化问题，其最优解的判定定理和进基变量的选取和极大化问题刚好相反，如下所示：判别定理1

设X为线性规划的一个基可行解，且对于一切j∈J（J为非基变量的下标集）有σj≥0，则X为线性规划的最优解。判别定理2

设X为线性规划的一个基可行解，且对于一切j∈J（J为非基变量的下标集）有σj≥0，同时有某个非基变量的检验数σk=0(k∈J)，则该线性规划有无穷多最优解。判别定理3

设X为线性规划的一个基可行解，若有σk<0(k∈J)，且pk≤0，即aik≤0（i=1,…,m），则该线性规划问题具有无界解（无最优解）。在进基可行解的转换过程中，进基变量的选取原则是：min{σj

|σj<0}=σk，则可以确定xk为换入变量。出基变量的选取原则不变。72当前72页，总共102页。一、人工变量法第五节LP问题的进一步讨论1.大M法2.两阶段法(了解)73当前73页，总共102页。人工变量法（大M法）MaxZ=CXs.t.AX=b

X≥0

若给定问题标准化后（b≥0）系数矩阵中不存在m个线性无关的单位列向量，则在某些约束条件的左端加一个非负变量Xn+i(人工变量)使得变化后的系数矩阵中恰有m个线性无关的单位列向量，并且在目标函数中减去这些人工变量与M的乘积（M是相当大正数）。对于变化后的问题，取这m个单位列向量构成的单位子矩阵为初始基，该基对应的解一定是基可行解。74当前74页，总共102页。1.大M法加入人工变量xn+1,xn+2,…,xn+m问题A问题B75当前75页，总共102页。1.大M法（M为任意大的正数）加入人工变量x6,x7加入松弛变量x4和剩余变量x576当前76页，总共102页。1)人工变量的识别2)目标函数的处理3)计算(单纯形法)77当前77页，总共102页。cj-31100MMθiCBXBbx1x2x3x4x5x6x70x4111-21100011Mx63-4120-1103/2Mx71-20100011σj-3+6M1-M1-3M0M000x4103-20100-1-Mx610100-11-211x31-2010001-σj-11-M00M03M-1注意：本例是求最小值，所以用所有来判别目标函数是否实现了最小化。因而换入变量xk的选取标准为78当前78页，总共102页。结果得:X*=(4,1,9,0,0,0,0)Z*=-2cj-31100MMCBXBbx1x2x3x4x5x6x70x4123001-22-541x210100-11-2-1x31-2010001-σj-10001M-1M+1-3x141001/3-2/32/3-5/31x210100-11-21x390012/3-4/34/3-7/3σj0001/31/3M-1/3M-2/3（接上表）79当前79页，总共102页。1.大M法例用单纯形法（大M法）求解下列线性规划加入松弛变量x3,剩余变量x4，人工变量x580当前80页，总共102页。用单纯形法计算，其过程如下表所示：Cj3200-MCBXBbx1x2x3x4x50x322[1]100-Mx512340-11σj12M3+3M2+4M0-M02x2221100-Mx54-50-4-11σj-4+4M-1-5M0-2-4M-M0虽然检验数均小于等于0，但基变量中含有非零的人工变量x5=4，所以原问题无可行解81当前81页，总共102页。1.大M法

大M法的几点结论（1）问题B要实现极大化，必须将人工变量从基变量中换出，否则目标函数不可能实现最优；（2）若在求解问题B的过程中，已将人工变量从基变量中换出，则已得到问题A的一个基可行解，可继续求解，以获得问题A的最优解；（3）若求解问题B已得到最优解，但最优解的基变量中含有不为零的人工变量，则问题A无可行解；（4）若求解问题B已得到最优解，且最优解的基变量中不含有人工变量，则问题B的最优解就是问题A的最优解。82当前82页，总共102页。两阶段法(将LP问题分成两个阶段来考虑)

第I阶段:

不考虑原问题是否存在可行解，给原LP问题加入人工变量，并构造仅含人工变量的目标函数和要求最小化；然后用单纯形法求解，若得W=0，则进行第二阶段计算，否则无可行解。

第II阶段：将第一阶段得到的最终表除去人工变量，将目标函数行的系数换为原问题的系数，作为第二阶段的初始表。83当前83页，总共102页。加入松弛变量x4;剩余变量x5;人工变量x6,x7用单纯形法求解第一阶段的结果得：84当前84页，总共102页。cj0000011CBXBbx1x2x3x4x5x6x70x4111-211000111x63-4120-1103/21x71-20100011σj6-1-301000x4103-20100-1-1x610100-11-210x31-2010001-σj0-1001030x4123001-22-540x210100-11-2-0x31-2010000-σj0000011此时，达到第一阶段的最优解，W=085当前85页，总共102页。cj-31100θiCBXBbx1x2x3x4x50x4123001-241X210100-1-1x31-20100-σj-10001-3x141001/3-2/31x210100-11x390012/3-4/3σj0001/31/3由于人工变量x6=x7=0,所以(0,1,1,12,0)T是该线性规划问题的基可行解。于是转入第二阶段运算：此时达到该LP问题的最优解：x1=4,x2=1,x3=9;目标函数值Z=-2。86当前86页，总共102页。1.存在两个以上相同的最大正检验数。选择任何变量（对应最大正检验数）作为进基变量。2.存在两个以上相同的最小比值。在下一次迭代中就有一个或几个基变量等于零。二、单纯形法中存在的问题如果在一个基本可行解的基变量中至少有一个分量为0，则称此基本可行解是退化的基本可行解，这样的线性规划问题称为退化的线性规划问题。87当前87页，总共102页。cj

3/4-201/2-60

00CBXBbx1x2x3x4x5x6x70x501/4-8-191000x601/2-12-1/230100x71001000103/4-201/2-600088当前88页，总共102页。cj

3/4-201/2-6000CBXBbx1x2x3x4x5x6x73/4x101-32-4364000x60043/2-150100x710010001σj0047/221-300选取x1为换入变量；选取下标最小的x5为换出变量