运筹学第四版清华大学出版社运筹学教材组单纯形法剖析

攻筹学(OperationsResearchChapter2线性规划与单纯形法O本章主要内容：§2.1线性规划问题及其数学模型§2.2线性规划问题的几何意义o§2.3单纯形法§2.4单纯形法的计算步骤§2.5单纯形法的进一步讨论§2.6应用举例Page3§2.3单纯形法§2.3单纯形法Page4•2.3.1举例•2.3.2初始基可行解的确定•2.3.3最优性检验与解的判断•2・3・4基变换•2.3.5迭代（旋转运算）§2.3单纯形法Page5单纯形法求解线性规划的思路：一般线性规划问题具有线性方程组的变量数大于方程个数，这时有不定的解。但可以从线性方程组中找出一个个的单纯形，每一个单纯形可以求得一组解，然后再判断该解使目标函数值是增大还是变小，决定下一步选择的单纯形。这就是迭代，直到目标函数实现最大值，或最小值为止。这样，问题就得到了最优解，先举一例来说明。_§2,3单纯形法p心234举例例2.6试以例2.1来讨论如何用单纯形法求解。maxz=2xt

+3x2

+Ox、+0x4+0x5x1

+2x2

-84x；

++x4=164x2+x5=12x'Oj=1,2,,5(2-11)(2-12)§2.3单纯形法Page7解：约束条件(2-12)式的系数矩阵为rl2100、A=(P{,P2,P3,P4JP5)=

40010l^o4001〉(1)从(2_12)式^3^5的系数构成的列向量11\:0，/>1，^5=0线性无关，构成一个基对应于B的变:x^x5为基变量。15-§2.3单纯形法Page8x3

=8-Xj-2xx5=12-4x2x}+2x，+x3

-84Xj+x4=16x4=16-4x)4x2+x5=12将(2-13)式代入目标函数(2-11)z=2xx

+3x2+0x3+0x4+0x.得z—

2xj+3x2(2-14)令非基变量X/=X2=0，得到一个基可行解Xw=(0,0,8，16，12)t，zo=0,(2-13)■B,.,_.§2.3单纯形法Page9•这个基可行解的经济含义：工厂没有安排生产产品I和n，资源都没有被利用，所以利润为•从(2-14)可以看到：非基变量的系数都是正数，因此将非基变量变换为基变量，目标函数的值就可能增大。从经济意义上讲，安排生产产品I或II，就可以使工厂的利润指标增加。所以只要在目标函数(2-14)的表达式中还存在有正系数的睡变量，这表示目标函数值还有增加的可能，就壽^要将非基变量与基变量进行对换。三I™—V§2.3单纯形法Page10(2)—般选择目标函数中正系数最大的那个非基变量为换入变量，将它换到基变量中，同时还要确定基变量中哪一个换出来成为非基变量o分析(2-14)式，当将定为换入变量后，必须从中确定一个换出变量，并保证其余的变量仍然非负，>0。当巧=0时，由(2-13)式得到x3

=8-2x2

>0=>Jx4=16

>0(2-15)x.=12-4x,>0之=8—xt

—2x2<x4=16-4xtx5

—12—4x2§2.3单纯形法p;_只有x2:min（8/2，_，12/4）:3时才能使（2-15）式成立。因当x2=3时，x5=0,x5为换出变量，即用jc2替换r5。以上数学描述说明，每生产一件产品II,需要用掉的各种资源数为（2，0，4）。由这些资源中的薄弱环节，就确定了产品n的产量。这里就是由原材料s的数量确定了产品n的I三了§2.3单纯形法Page12贝！为新的基变量，久，；^为非基变量。由(2-13)将基变量用非基变量表示出来。x3

=8—x,-2x2x3

+2x2=8-Xjx4

=16-4xx

(2-13)=>x4=16-4xtX-

=12-4x24x2=12-x^3=2-Xl+^5g=>一x4=16—4X((2-17)J'i1x，=3——x2

4s55^=i§2.3单纯形法Page13再将(2-17)式代入目标函数(2-14)式得到(2-18)令非基变fixy=X5=0,得到另一个基可行解z=9十145X(1)=(0,3,2，16,0)T，q-9从目标函数的表达式(2-18)可看到，非基变量的系数是正的，说明目标函数值还可以增大，~即X⑴还不是最优解。于是，再用上述方桜确定换入、换出变量，继续迭代。-Page14(3)令々为换入变量，当jrs=O时，由(2-17)式得到x,=2-X,0<x4

=16-4x)>0x，=3^0只有巧=側7/(2,12/4,

-)=3时才能使上式成立。因当X/=2时，x3=0,为换出变量，即用久替^^。则AAA为新的基变量，XhX^非基变量。由(2-17)将基变量用非基变量表示出来。Page15x2=3x，=32-x.+-x5x4=16-4Xj1—x:1x.=2-

x,+—x;132x4=8+4x)-2x514再将(2-19)式代入目标函数(2-18)式得到z=13-2x3+ix5

(2-20)4令非基变ix5=x5=o,得到另一个基可行解义(2)=(2,3,0,8,0)「，z2

=13.(2-19)Page16因当x5=4时，x^=0,久为换出变量，即用x5替换与。rm—则工介人为新的基变量，A而为非基变量。由(2-19)将基变量用非基变量表示出来。x2=3一产0只有x5=min(-，8/2,3/1/4)=4时才能使上式成立。(4)令x5为换介变量，争r3=0时，由(2-19)式得到x.=2+—x->01

2<x4

=8-2x5

>0Page1721)再将(2-21)式代、目标-数(2-20)式得到=14'2X3_gx4(2-22)令非基变fix?=x,=0,得到另一个基可行解=(4,2,0,0,0)',Z3=14.'=2-x3+^x54-去X4x4

=8+4x1-2x5A=4+2x3--x4(2-;1^2=3

--^5i11x，=2--x,+-xd[22384§2.3单纯形法Page18就必须支付附加费用。"目标!!_綻盘?器鵲11^冤!’产品I生产4件，产品n生产2件时，工厂可以通过上例，可将每步迭代得到的结果与图解法做一对比。§2.3单纯形法Page19•例1满足所有约束条件的可行域是髙维空间中的凸多面体(凸集)。该凸多面体上的顶点，就是基可行解。初始可行解x(")x(1)x(2)x(3),相于右图中O->Q4

->Q3Q2,尤⑻=(0,0,8，16，12f-^0(0,0)X⑴=(0,3,2，16,0)14仏(0,3)—込(2,3)X{3)=(4,2,0,0t0)'^02(4,2)§2.3单纯形法Page202.3.2初始基可行解的确定•为了确定初始基可行解，要首先找出初始可行基，其方法如下。-(1＞直接观察-(2)加松弛变量-(3)加非负的人工变量§2.3单纯形法Page21(1)直接观察对于标准形式的线性规划问题，可直接由系数矩阵通过直接观察，找出一个初始可行基<1B屯，P”…4)=§2.3单纯形法Page22（2＞加松弛变量：所有约束条件为的不等式，在每个约束条件的左端加上一个松弛变量化为标准型。经过整理，重新对~及〜（卜1、2,…,…j?）进行编号，则可得下列方程组，么为松弛变量）：=bth+a2mHxm+l+……+a2„x〃=b21G一■»«••漏•*•,,(2-23)x•+art

-++(zrtlxtJ=bQL--inmjn+im+\mnrnXj>o,j=l，2，."，n§2.3单纯形法于是，（2-23）中含有一个znX/n阶单位矩阵，初始可行基打即可取该单位矩阵。a…si…••・l…k将（2-22）式每个等式移项得=4气叫i^+i……A-=T_—,X2

—办2°2,m+lXw+l…a2f,X.,£~•*•••VVV•••■V**■.‘(2~24）广Y=h=GX

—囑*mmiif+1-…amXn-Tf§2.3单纯形法Page24(3)加非负的人工变量对所有约束条件为形式的不等式及等式约束情况，若不存在单位矩阵时，可采用人造基方法。-即对不等式约束，减去一个非负的剩余变量，再加上一个非负的人工变量；对于等式约束，再加上一个非负的人工变量这样，总能在新的约束条件系数构成的矩阵中得到一个单位矩阵。15-_§2.3单纯形法w233最优性检验与解的判别经过迭代后(2-24)式变成Xi=b;—

Zayxp(f=1,2,…w)(2-25)代入目标函数(2-20)式，整理后得hin»zjxj=

Hcixi+ZcjxjJ=lt=lmitwi=lj=m+1j=ffl+1§2.3单纯形法Page26mm»oi=lt=lj=m+lj=m+lmfimn=^^cibi

—+J}CjXj1=1mj=m+lj=m+ljifm

、=Ec+LcrZcXxj

(2-26)(=1J=/M+l\f=lJmm

专J7令%=公々;，、=公人，j=m十l，"，'zi=li=lL§2.3单纯形法Page27于是Z=z❶+2(c;~zj)

xj(2—27)令aj-cj-Zj(j=m+l9^^n)9z=z0

+Z(2-28)称为x;的检验数。j='"十|初始解x((,)=(4，/^"X，o，”.，o)，则此时有d)若幺0(J=讯+1，…，n)，z<z0;⑵若cr;>o(y=历+1，…，ft)，z>Z0,故是判断xw是否为最优解的关键。§2.3单纯形法Page28若X⑻=（《，心…人，0，...，0芦对应于基B的一个基可行解1.最优解的判定理若对于一切戶m+7，...，n，有（7yd），则X＜（"为最优解。2.无穷多最优解判别定理I若对于一切/=W+A...，《，有＜7^0，且存在某个非基变量的检验数＜7,^=0,则线性规划问题有无：穷多最优解，xw为其中一个最优解。"§2.3单纯形法Page293.无界解判别定理若存在某个（rm+k

>0,并且对m

有a‘i，n^O,那么该线性规划问题具有无界解（或称无最优解）。•其它情形-以上讨论都是针对标准型的，即求目标函数极大化时的情况。当要求目标函数极小化时，一种情况是t将其化为标准型。-如果不化为标准型，只需在上述1，2点中把agO改$为^0,第3点中将％+k>0改写为<^<0目_。-§2.3单纯形法Page30234基变换•若初始基可行解不是最优解及不能判别无界时，需要找一个新的基可行解。•具体做法是-从原可行解基中换一个列向量（当然要保证线性独立），得到一个新的可行基，称为基变换。为了换基，先要确定换入变量，再确定换出变量，让它们相应的系数列向量进行对换，就得到一个新的基可行解。Qa_4§2.3单纯形法Page31ijn+t,rn-k-tx:为换出变量。按最小比值确定0值，称为最小比值规则一6xf0)1.换入变量的确定选取max^(rz

>0^=o;对应的变量xA为换入变量。也可任意选择或者按照最小下标码选择。A,m+r>0=0=min2.换出变量的确定rx；o)§2.3单纯形法Page32233迭代（旋转运算）上述讨论的基可行解的转换方法是用向量方程描述的，在实际计算时不太方便，因此下面介绍系数矩阵法。考虑以下形式的约束方程组§2.3单纯形法Page33设^^,,...4为基变量，对应的系数矩阵是单位阵/,它是可行基。令非基变量W„+2,..人为零，即可得到一个基可行解。若它不是最优解，则要另找一个使目标函数值增大的基可行解。这时从非基变量中确定心为换入变量。显然这时0为(9=min—>0|=—f1

Jaik在迭代过程中0可表示为其中经过迭代后对应于么，么的元素值二§2.3单纯形法Page34按权规则确定T/为换出变量，的系数列向量分别为第Z个分量§2.3单纯形法为了使^与X,进行对换，须把巧变为单位向量，这可以通过(2-33)式系数矩阵的增广矩阵进行初等变换来实现。…A…X入mX••xk…Lb，1•♦……ah,t•1♦•a“料i…a汝…alnb,(2_-34)•••二1•_・amk••,amu§2.3单纯形法Page36变换的步骤是:(1)将增广矩阵(2-34)式中的第/行除以&，得到(2)将(2-34)式中a列的各元素，除叫变换为1以外，其他都应变换为零。其他行的变换是将(2_35)式乘以aik(i4X)后，从(2-34)式的第桁减去，得到新的第/行。§2.3单纯形法Page37由此可得到变换后系数矩阵