运筹学第二单纯形法及进一步讨论

关于运筹学第二单纯形法及进一步讨论2第二章线性规划

单纯形法

人工变量法退化问题检验数的几种表现形式单纯形法总结第2页,共62页，星期六，2024年，5月军事运筹学3(一)﹑单纯形法的基本思路3.1单纯形法思路：首先求出一个顶点(基可行解)，并判断是否是最优解，如果是求解结束，如果不是就进行下一步；第二步转换到另一个顶点(另一个基可行解)，并判断是否是最优解，如果是求解结束，如果不是就重复进行第二步，直至目标函数达到最优。具体工作：(1)如何求出初始基可行解？(2)如何判断一个基可行解是否是最优？(3)如何从一基可行解转换到另一更优的基可行解？第3页,共62页，星期六，2024年，5月军事运筹学4(二)﹑单纯形法的求解方法1.确定初始基可行解，只要找出初始可行基。(1)

直接观察法：从系数矩阵A

中直接观察出一个初始基3.1单纯形法第4页,共62页，星期六，2024年，5月军事运筹学5（2）化标准型法

如果所有约束条件都是“≤”形式的不等式，则可以利用化标准型的方法，在每个约束条件的左端加上一个松弛变量。重新对xj及aij进行编号，可得下列方程组：从中可得单位矩阵第5页,共62页，星期六，2024年，5月军事运筹学6（2）化标准型法以B作为可行基。将(2.3)移项得令xm+1=…=xn=0则

xi

=bi

(i=1，2，…m)又因bi≥0(标准型中规定)，则得一初始基可行解X=(b1,b2,…,bm,0,…,0)T第6页,共62页，星期六，2024年，5月军事运筹学7（3）人工变量法

当所有约束条件都是“≥”形式的不等式或等式约束时，如果不存在单位矩阵，就采用人工变量法:①对不等式约束左端减去一个非负的剩余变量，再加上一个非负的人工变量；②对等式约束左端再加上一个非负的人工变量。这样就可以得到一个单位矩阵，即总能得到一个初始可行基。第7页,共62页，星期六，2024年，5月军事运筹学8（3）人工变量法设线性规划问题的约束条件是分别对各约束方程加人工变量xn+1,xn+2,…,xn+m可得第8页,共62页，星期六，2024年，5月军事运筹学9以xn+1，…﹐

xn+m为基变量，可得到一个单位矩阵令x1=x2=…=

xn

=0，可得(2.6)式的一个初始基可行解X(0)=(0，0，…，0，b1，b2，…，bm)T

以此基可行解为起始点转换到(2.5)的基可行解。（3）人工变量法第9页,共62页，星期六，2024年，5月军事运筹学102.最优性检验与解的判别线性规划问题的求解结果唯一最优解无穷多最优解无界解无可行解如何判别？第10页,共62页，星期六，2024年，5月军事运筹学112.最优性检验与解的判别线性规划问题的求解结果唯一最优解无穷多最优解无界解无可行解如何判别？

由上述初始基可行解确定的讨论，可知约束方程组变成下面的形式：第11页,共62页，星期六，2024年，5月军事运筹学12

由初始基可行解开始进行从一个基可行解到另一个更优基可行解的求解过程中，每一次求基可行解时，约束方程组都化成上述形式。为了便于讨论，把它记成一般形式。转换迭代过程中的一般形式为：第12页,共62页，星期六，2024年，5月军事运筹学13

由初始基可行解开始进行从一个基可行解到另一个更优基可行解的求解过程中，每一次求基可行解时，约束方程组都化成上述形式。为了便于讨论，把它记成一般形式。把(2.7)式代入目标函数中可得第13页,共62页，星期六，2024年，5月军事运筹学14令于是再令则第14页,共62页，星期六，2024年，5月军事运筹学15

假设X(0)=(b1′,b2′,…,bm′,0,…,0)T

是一个基可行解，则有下列判断定理：1.最优解：如果对一切j=m+1，…，n有σj≤0，则X(0)为最优解(注意，这里是针对目标函数求极大而言的)。2.无穷多最优解：如果对一切j=m+1，…，n

有σj≤0，又存在σm+k=0，则线性规划问题有无穷多最优解。3.无界解：如果有一个σm+k﹥0，且对i=1,…,m有ai,m+k≤0，则线性规划问题有无界解(无最优解)。第15页,共62页，星期六，2024年，5月163.基变换基变换：在单纯形法求解中，如果得到了某一个基可行解，并判断了它不是最优解，就要从该基变换成另一个更优的基并求出新的基可行解。方法：第一步确定换入非基变量；第二步确定换出基变量；第三步将所确定的一对变量对应的系数列向量对换得到新的基，求出新的基可行解。第16页,共62页，星期六，2024年，5月军事运筹学17(1)换入变量的确定再看(2.8)式其中

当某些σj＞0时，xj

增加会使目标函数值增加，我们就要从中确定一个非基变量xj换到基变量中。方法：把σj值最大者所对应的变量换入。即若则对应的变量xk为换入变量,这样的迭代速度最快。第17页,共62页，星期六，2024年，5月军事运筹学18(2)换出变量的确定设B＝(p1,p2,…,pm)是一个基，与之对应的基可行解为X(0)=(x1(0),x2(0),…,xm(0)

,0,…,0

)T

。pm+1,pm+2,…,pm+t,…,pn为非基向量。设确定pm+t

为换入非基向量。于是其中βim+t为一组不全为0的数(j=1，…，m)。第18页,共62页，星期六，2024年，5月军事运筹学19不妨设θ为一正数，则有恒等式

或根据(2.9)可如下确定换出变量：令确定xl为换出变量。注意：①pj

(j=1，…，m,j≠l)，pm+t

线性无关；②存在基可行解。第19页,共62页，星期六，2024年，5月军事运筹学20注意：①pj

(j=1，…，m,j≠l)，pm+t

线性无关；②存在基可行解。①：假设pj

(j=1，…，m,j≠l)，pm+t

线性相关，则存在不全为0的数αj使得又因所以有这说明p1,p2,…,pm线性相关。矛盾由构成的X(1)是一个基可行解。②第20页,共62页，星期六，2024年，5月军事运筹学214﹒基变换的系数矩阵法以下列形式的约束方程组进行讨论。m×m单位矩阵是基，

x1,x2,…,xm是基变量。可得基可行解X(0)=(b1,b2,…,bm,0,…,0)T。第21页,共62页，星期六，2024年，5月军事运筹学22

如果X(0)不是最优，则需作基变换。设xk为确定的换入变量，显然θ为在迭代过程中θ可表示为于是可确定xl为换出变量。

下面就要把xk，xl所对应的向量pk=(a1k,a2k,…,amk)T

和pl=(0,…,1,…,0)T

进行交换，并且要把pk变为单位向量。

我们将通过系数矩阵的增广矩阵进行初等变换来实现。第22页,共62页，星期六，2024年，5月23(2.10)式的增广矩阵为第23页,共62页，星期六，2024年，5月军事运筹学24交换步骤：①将(2.11)式中第l行除以alk

；②将(2.11)式中xk列的各元素，除了alk

变换为1以外，其它都应变为0。第i

行(i≠l)的变换是：将用(第

i行)－(经过①变换以后的第l

行乘以aik)。第24页,共62页，星期六，2024年，5月军事运筹学25经过变换以后系数矩阵各元素的变换关系式：第25页,共62页，星期六，2024年，5月军事运筹学26经过变换后的新增广矩阵为：1…-a1k／alk…0

a1m+1′…0…a1n

′

0…+1／alk…0alm+1′…1…aln′·················0…-amk／alk…1amm+1′…0…amn′

(3.12)················x1…xl…xm

xm+1…xk…xnbb1′bl′bm′﹒﹒新的基可行解：

由(2.12)式可知x1

，…，xk

，…，xm的系数列向量构成m×m单位矩阵，它是可行基。于是得到一个基可行解X(1)：X(1)=(b1′,…,bl-1′

,0,bl+1′…,bm′,0,…,bl′,0…,0)T把元素alk称为主元素，它所在的列称为主列，它所在的行称为主行。第26页,共62页，星期六，2024年，5月军事运筹学27(三)﹑单纯形法的计算步骤1.单纯形表

将约束方程组与目标函数组成n+1个变量，m+1个方程的方程组。

x1+a1m+1xm+1+…+a1nxn＝b1

x2+a2m+1xm+1+…+a2nxn＝b2·····················

xm+amm+1xm+1+…+amnxn＝bm－z+c1x1+c2x2+…+cmxm

+cm+1xm+1+…+cnxn＝001

0…0

a1m+1…a1n

001…0a2m+1…a2n·················000…1amm+1…amn

－z

x1

x2…xm

xm+1…xnbb1b2bm﹒1c1

c2…cm

cm+1…cn

0将上述方程组写成增广矩阵第27页,共62页，星期六，2024年，5月军事运筹学2801

0…0

a1m+1…a1n001…0a2m+1…a2n·················000…1amm+1…amn

－zx1x2…xmxm+1

…xnbb1b2bm﹒1c1c2…cmcm+1

…cn

0将上述方程组写成增广矩阵

将z看作不参与基变换的基变量，它与x1，x2，…，xm的系数构成一个基。采用初等行变换将c1

c2…cm

变换为零，使其对应的系数矩阵为单位矩阵。可得：01

0…0

a1m+1……………a1n

001…0a2m+1……………a2n·················000…1amm+1……………amn

－zx1x2…xmxm+1……………xnbb1b2bm﹒－∑cibi100…0cm+1－∑ciaim+1…cn

－∑ciain

m

i=1m

i=1m

i=1根据上述增广矩阵设计计算表：非基变量检验数σj

。第28页,共62页，星期六，2024年，5月军事运筹学29cjc1…cmcm+1…cnθiCBXBbx1…xmxm+1…xnc1c2·cmx1x2·xmb1b2·bm10·0…………00·1a1m+1a2m+1·amm+1…………a1na2n·amnθ1θ2·θm－zm－∑cibii=10…0cm+1－

m∑ciaim+1i=1cn－

m∑ciaini=1计算表1—1：XB列中填入基变量，这里是x1，x2，…，xm；CB列中填入基变量的价值系数，它们与基变量对应；b列中填入约束方程组右端的常数；

cj行中填入基变量的价值系数c1，c2，…cn；θi列中的数字是在确定换入变量后，按θ

规则计算后填入；最后一行称为检验数行，对应各非基变量。非基变量检验数σj

。第29页,共62页，星期六，2024年，5月军事运筹学302.计算步骤(1)找出初始可行基，确定初始基可行解，建立初始单纯形表。(2)检验各非基变量xj的检验数σj=cj－

i=1

m∑ciaij

，如果σj≤0，j=m+1，…，n；则已得到最优解，可停止计算。否则转入下一步。(3)存在σj﹥0，j=m+1，…，n

中，若存在某个σk对应xk的系数向量pk≤0，则问题无解，停止计算。否则，转入下一步。(4)根据max(σj﹥0)=σk

，确定xk为换入变量，按θ

规则计算

θ=min(——︱aik﹥0)

biaik=——

blalk可确定xl为换出变量。转下一步。(5)以alk为主元素进行迭代，把xk所对应的列向量pk=a1ka2kalkamk··0010··变换为第l

行将XB列中的xl换为xk，得到新的单纯形表。在得到最优解或确定无界解之前，重复(2)—(5)。第30页,共62页，星期六，2024年，5月军事运筹学313﹒举例例求下列线性规划问题的解maxz＝2x1+3x2x1＋2x2≤84x1≤164x2≤12x1﹐x2≥0maxz＝2x1+3x2+0x3+0x4+0x5x1＋2x2＋x3＝84x1＋x4＝164x2＋x5＝12x1﹐x2﹐x3﹐x4﹐x5≥0化标准型(1)确定初始基可行解：由标准型中的约束方程组可知变量x3，x4，x5

所对应的系数向量构成3×3单位矩阵为一基。可得初始基可行解

X(0)=(0，0，8，16，12)T据此生成单纯形表cj23000θiCBXBbx1x2x3x4x5000x3x4x58161214020[4]100010001－－z

000表1－1：σj23430第31页,共62页，星期六，2024年，5月军事运筹学32cj23000θiCBXBbx1x2x3x4x5003x3x4x22163[1]40001100010－1/201/4－－z

000表1－2：基可行解X(1)=(0，3，2，16，0)Tδj2-3/424-9cj23000θiCBXBbx1x2x3x4x5000x3x4x58161214020[4]100010001－－z

000表1－1：δj23430第32页,共62页，星期六，2024年，5月军事运筹学33cj23000θiCBXBbx1x2x3x4x5003x3x4x22163[1]40001100010－1/201/424－－z－9

2000－3/4基可行解

X(1)=(0，3，2，16，0)T表1－2：δjcj23000θiCBXBbx1x2x3x4x5203x1x4x22831000011－40010－1/2[2]1/4－－z

000表1－3：基可行解X(2)=(2，3，0，8，0)Tδj－21/4412－13第33页,共62页，星期六，2024年，5月军事运筹学34cj23000θiCBXBbx1x2x3x4x5203x1x4x22831000011－40010－1/2[2]1/4－412－z－13

00－201/4表1－3：基可行解

X(2)=(2，3，0，8，0)Tδjcj23000θiCBXBbx1x2x3x4x5203x1x5x24421000010－21/21/41/2－1/8010－z

000表1－4：最优解X(3)=(4，2，0，0，4)T

，z=14δj－3/2－1/8－14第34页,共62页，星期六，2024年，5月35单纯形法小结求解过程确定初始基可行解判断是否是最优解是，求解结束；（或者无最优解）否。确定换入换出变量基变换，得到新的可行基转入第二步，重复。第35页,共62页，星期六，2024年，5月36第二章线性规划

单纯形法人工变量法退化问题检验数的几种表现形式单纯形法总结第36页,共62页，星期六，2024年，5月军事运筹学373.2人工变量法（3.13）

在前面我们讲过由人工变量法构造初始可行基，若线性规划问题的约束条件为然后人为的加上变量xn+1，xn+2，…，xn+m后得到(3.14)第37页,共62页，星期六，2024年，5月军事运筹学383.2人工变量法

若人工变量≠0，(3.14)与(3.13)不等价，即对原LP问题的约束条件进行了“篡改”，不是希望的。但又需添加人工变量，得到初始可行基。

为保证它与原LP问题得到的最优解一致，需要将人工变量从基变量中逐个替换出来。若经过基变换后，基变量中不再含有非零的人工变量，这表示原问题有解；若在最终的表中当所有的检验数

0，但在其中还有某个非零人工变量，这表示无可行解。第38页,共62页，星期六，2024年，5月军事运筹学393.2人工变量法

在引入人工变量的同时修改目标函数，规定人工变量在目标函数中的系数为(－M)(M﹥0的大数)。即

这种方法叫大M法。作了上述变换之后，再用单纯形法把人工变量从基变量中转换出去，然后求原问题的最优解。3.2.1大M法第39页,共62页，星期六，2024年，5月军事运筹学403.2人工变量法例：用大M法求解如下线性规划问题第40页,共62页，星期六，2024年，5月军事运筹学413.2人工变量法解：在上述问题的约束条件中加入松弛变量、剩余变量和人工变量，得到其中M是一个任意大的正数。第41页,共62页，星期六，2024年，5月军事运筹学423.2人工变量法建立单纯形表：cj-31100MM

iCBXBbx1x2x3x4x5x6x70x4111-211000Mx63-4120-110Mx71-2010001

j000-3+6M1-M1-3MM1113/21第42页,共62页，星期六，2024年，5月军事运筹学433.2人工变量法单纯形表2：cj-31100MM

iCBXBbx1x2x3x4x5x6x70x4103-20100-1Mx610100-11-21x31-2010001

j000-11-M3M-1M1-1-第43页,共62页，星期六，2024年，5月军事运筹学443.2人工变量法单纯形表3：cj-31100MM

iCBXBbx1x2x3x4x5x6x70x4123001-22-51x210100-11-21x31-2010001

j000-1M-1M+1134--第44页,共62页，星期六，2024年，5月军事运筹学453.2人工变量法单纯形表4：cj-31100MM

iCBXBbx1x2x3x4x5x6x7-3x141001/3-2/32/3-5/31x210100-11-21x390012/3-4/34/3-7/3

j0001/3M-1/3M-2/31/32最优解X=(4,1,9,0,0,0,0)，Zmin=-2。第45页,共62页，星期六，2024年，5月军事运筹学463.2人工变量法3.2.2两阶段法用计算机求解含有人工变量的线性规划问题时，只能用很大的数代替M，这就可能造成计算上的错误。引入两阶段法求解。第46页,共62页，星期六，2024年，5月军事运筹学473.2人工变量法

第一阶段，不考虑原问题是否存在基可行解；给原线性规划问题加入人工变量，并构造仅含人工变量的目标函数和要求实现最小化。即

再利用单纯形法求解上述模型，若ω最优值为0，则原问题有解，可进行第二阶段计算。否则原问题无可行解。第47页,共62页，星期六，2024年，5月军事运筹学483.2人工变量法3.2.2两阶段法

第一阶段，不考虑原问题是否存在基可行解；给原线性规划问题加入人工变量，并构造仅含人工变量的目标函数和要求实现最小化。即

再利用单纯形法求解上述模型，若ω最优值为0，则原问题有解，可进行第二阶段计算。否则原问题无可行解。

第二阶段，将第一阶段计算得到的最终表，除去人工变量，将目标函数行的系数，换原问题的目标函数系数，作为第二阶段计算的初始表。

各阶段的计算方法与前面的单纯形法相同。第48页,共62页，星期六，2024年，5月军事运筹学493.2人工变量法3.2.2两阶段法例：用两阶段法求解线性规划问题第49页,共62页，星期六，2024年，5月军事运筹学503.2人工变量法解：添加人工变量，给出第一阶段的数学模型为第50页,共62页，星期六，2024年，5月军事运筹学513.2人工变量法用单纯形法求解得到的最后结果为：此时，得到的最优解为

=0，X=（0，1，1，12，0，0，0），它是原LP问题的基可行解，因此可以进行第二阶段的计算。cj0000011

iCBXBbx1x2x3x4x5x6x70x4123001-22-50x210100-11-20x31-201000000000011第51页,共62页，星期六，2024年，5月军事运筹学523.2人工变量法第二阶段的初始单纯形表为：cj0000011

iCBXBbx1x2x3x4x5x6x70x4123001-22-50x210100-11-20x31-2010000-31100011第52页,共62页，星期六，2024年，5月53第二章线性规划

单纯形法

人工变量法

退化问题检验数的几种表现形式单纯形法总结第53页,共62页，星期六，2024年，5月军事运筹学543.3退化问题(1)什么是退化？

当基解﹑基可行解﹑最优基可行解中有基变量为0时，即出现退化。

当出现退化时，可能出现计算过程的循环，便永远达不到最优解。第54页,共62页，星期六，2024年，5月军事运筹学553.3退化问题(2)勃兰特规则为了避免出现循环，勃兰特提出下面规则：①选取cj－zj﹥0中下标最小的非基变量xk为换入变量，即k=min(j|cj－z