线性规划问题的单纯形法求解(第3讲)

线性规划问题的单纯形法求解《运筹学》第三讲2011.03.01内容提要线性规划问题解的概念线性规划问题的几何意义线性规划问题的单纯形求解1.线性规划问题解的概念标准型可行解：满足约束条件的解称为可行解。最优解：使目标函数达到最大值的可行解称为最优解。njmijxibnjjxijatSnjjxjcz,,2,1;,2,101.1max基：若B是矩阵A中m×m阶非奇异子矩阵（|B|≠0），则B是线性规划问题的一个基。不妨设：),...,(,...,..............,...,11111mmmmmPPaaaaBjPjXjX,j=1，2，…,m——基向量。，j=1，2，…,m——基变量。,j=m+1,…,n——非基变量。线性规划问题解的概念线性规划问题解的概念为了进一步讨论线性规划问题的解，下面研究约束方程的求解问题。假设该方程组系数矩阵A的秩为m,因mn,故它有无穷多个解。假设前m个变量的系数列向量是线性独立的。约束方程组可写成：nmnnmmmmmmmmmmxaaxaabbxaaxaa.....................11111111111线性规划问题解的概念上式的一个基是mPPPmmamamamaaaB,2,12111211设XB是对应于这个基的基变量XB=(x1,x2,…,xm)T现若令的非基变量xm+1=xm+2=…=xn=0，并用高斯消去法，可以求出一个解X=(x1,x2,…,xm,0,…,0)T这个解的非零分量的数目不大于方程的个数m,称为基解。于是，由一个基可以求出一个基解。基可行解：满足非负条件的基解，称为基可行解。于是基可行解的非零分量的数目也不大于m,并且都是非负的。可行基：对应于基可行解的基，称为可行基。例0,,,,1241648200032max54321524132154321xxxxxxxxxxxxxxxxxz基、基变量、非基变量、基向量、非基向量、基解、基可行解、可行基100010040004121,,,,54321PPPPPA54321,,,,PPPPP54321,,,,xxxxx例0400041211B321,,PPP行列式0160000160040004121||1B基变量非基变量基向量非基向量321,,xxx54,xx321,,PPP54,PP对应于基B1的基解X1124164825241321xxxxxxx)0,0,2,3,4(1X非基可行解例1000100012B543,,PPP行列式01000001100010001||2B基变量非基变量基变量非基变量543,,xxx21,xx543,,PPP21,PP对应于基B2的基解X2124164825241321xxxxxxx)12,16,8,0,0(2X基可行解线性规划解的关系图非可行解可行解基可行解基解线性规划问题解的概念最优解？2.线性规划问题的几何意义基本概念凸集：为凸集。K），则1α0（，KXα）1（Xα连线上的一切点KX，KX对维欧氏空间的一点集，n是k设）2（）1（）2（）1（线性规划问题的几何意义顶点:若K是凸集，X∈K；若X不能用不同的两点的线性组合表示为：则X为K的一个顶点。KXKX)2()1(和)10()1()2()1(XXX凸集线性规划问题的几何意义顶点定理1:若线性规划问题存在可行域,则其可行域:是凸集.基本定理证明:)0,XbAXXD0,,0,,,)2()2()1()1()2()1()2()1(XbAXXbAXXXDXDX则有：设：线性规划问题的几何意义bbbAXAXXXAAXXX)1()1())1((0)2()1()2()1(代入约束条件，有：将显然，1)(0)1()2()1()2()1(XXXXXX：连线上的任意一点，则和为令只要验证X在D中即可是凸集。因此，DDX,引理：线性规划问题的可行解X为基可行解的充要条件是X的正分量对应的系数列向量是线性独立的。•定理3：若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。•定理2：线性规划问题的基可行解X对应于可行域D的顶点。证明：反证法。分两步。几点结论：线性规划问题的可行域是凸集。若线性规划问题有最优解，一定存在一个基可行解是最优解。基可行解与可行域的顶点一一对应，可行域有有限多个顶点。最优解必在顶点上得到。单纯形法单纯形法求解步骤：1、找一个基可行解作为X0初始解最容易得到的可行基是标准型线性规划的系数矩阵的单位矩阵。2、求检验数，检验X0是否为最优解（１）求检验数将约束方程组的基变量的系数矩阵化为单位矩阵；通过代入或加减乘除消元法将目标函数中的基变量消去，则非基变量的系数即为检验数．（２）最优解的判别当检验数全部小于或等于0时，该基可行解为最优解,求解可结束.当存在正的检验数时,该基可行解就不是最优解,就要换到一个新的(与X0相邻的)基可行解（X1）．3、换基（迭代）(1)确定进基变量:凡是检验数大于0的非基变量都可进基;但一般选择最大的检验数对应的变量进基。(2)按最小比原则确定出基变量，就可得一新的（更接近于最优解的）基可行解（X1），对（X1）重复２－３的过程就可在有限步得到最优解，或判断出无最优解。求解下列的线性规划maxz=2x1+3x2+0x3+0x4+0x5x1+2x2+x3=84x1+x4=161.124x2+x5=12x1,x2,x3,x4,x5≥0解：1、求一个初始基可行解100400100400121),,,,(54321PPPPPA可以看到x3,x4,x5的系数列向量组成一个单位矩阵，是约束方程组的一个可行基。100,010,001543PPP这些向量构成一个可行解基，对应的基可行解为x0=（0，0，8，16，12），基100010001),,(5430PPPB对应于基B0的变量x3,x4,x5为基变量。为求检验数，将约束方程组的基变量的系数矩阵化为单位矩阵可以得到x3+x1+2x2=8x4+4x1=16x5+4x2=12或x3=8-x1-2x2x4=16-4x1x5=12-4x2将上式代入目标函数z=2x1+3x2+0x3+0x4+0x5得到z=0+2x1+3x2。于是非基变量x1，x2的系数就为检验数，分别为2，3。2、求对应于X0的检验数最优性判别从目标函数可以看出，该基可行解X0=(0,0,8,16,12,)对应的目标值为0，但是非基变量x1,x2的系数为正，因此只要增加x1或x2的值，（最大化的）目标函数就可以增加。只要有正的检验数，该基可行解就不会是最优解，只有当全部的检验数都小于或等于零时，对应的基可行解才为最优解。3、换基（1）确定进基变量凡是检验数大于0的非基变量都可进基;但一般选择最大的检验数对应的变量进基。由于x2的系数为正，显然当x2增大，则目标函数z的值也增大。当x2定为换入变量后，必须从x3,x4,x5中换出一个，并保证其余的变量都是非负，即x3,x4,x5≥0。（2）确定出基变量由于在下一个基可行解中，x1仍然为非基变量，x1=0，此时，得到x3=8-2x2≥0x4=16≥0x5=12-4x2≥0从上式可以看出，x2的最大值只有选择x2=min(8/2,-，12/4)=3，才能使上式都成立。当x2=3时，基变量x5=0，这就决定用x2去替换x5。因此x5为出基变量。为了求得以x3,x4,x2为基变量的一个基可行解和相应的检验数，需将x2与x5的位置对换。得到X3+2x2=8-x1(1)x4=16-4x1(2)4x2=12-x5(3)用消元法，得：x3=2-x1+1/2x5(1)‘x4=16-4x1(2)‘x2=3-1/4x5(3)‘再将上式代入目标函数得到z=9+2x1-3/4x5令非基变量x1=x5=0，得到另一个基可行解X(1)=(0,3,2,16,0)T。将基可行解X(1)的值代入目标函数得z=9.从目标函数中可看出,非基变量x1,x5检验数分别为2，-3/4。X(1)不是最优解。再换基，得到另一个基可行解X(2)=(2,3,0,8,0)。仍不是最优解，继续迭代。最后得到：X(3)=(4,2,0,0,4)。此时目标函数z=14-3/2x3-1/8x4。得最优解。初始基可行解的确定为了确定初始基可行解，首先找出初始可行基，其方法如下：线性规划问题0max11jnjjjnjjjxbxPxcz从Pj(j=1,2,…,n)中一般能直接观察到存在一个初始可行基1000010000100001),,,(21mPPPB以B作为可行基。移项得x1=b1-a1,m+1xm+1-…-a1nxnx2=b2-a2,m+1xm+1-…-a2nxn……xm=bm-am,m+1xm+1-…-amnxn令xm+1=xm+2=…=xn=0,可得xi=bi(i=1,2,…,m)又因bj≥0，所以得到一个初始基可行解X=(x1,x2,…,xm,0,…,0)T=(b1,b2,…,bm,0,…,0)T最优性检验与解的判别线性规划问题的求解结果可能出现唯一最优解、无穷多最优解、无界解和无可行解四种情况，为此需要建立对解的判别准则。一般情况下，经过迭代后（1.23）式变为(i=1,2,…,m)jnmjijiixabx1将上式式代入目标函数，整理后得nmjjjmiiijmiijinmjjmiiixbcxaccbcz11111)(令（j=m+1,…,n）于是再令（j=m+1,…,n）则miiibcz10miijijacz1jjnmjjxzczz)(10jjjzcjnmjjxzz101、最优解的判别定理：若X(0)=(0,…,0)T为对应于基B的一个基可行解，且对于一切j=m+1,…,n有σj≤0，则X(0)为最优解，称σj为检验数。2、无穷多最优解判别定理：若X(0)=(0,…,0)T为一个基可行解，对于一切j=m+1,…,n有σj≤0，又存在某个非基变量xm+j的检验数σm+k=0,则线性规划问题有无穷多最优解。3、无界解判别定理:若X(0)=(0,…,0)T为一个基可行解，有一个非基变量xm+k的检验数σm+k0,并且对i=1,2,…,m有ai,m+k≤0,那么该线性规划问题具有无界解（或称无最优解）,,,21mbbb基变换1、换入变量的确定：由前面的分析看到，当某些σj0时，xj增加则目标函数还可以增大，这时要将某个非基变量xj换到基变量中去（称为换入变量）。若有两个以上的σj0，那么选哪个非基变量作为换入变量呢？为了使目标函数值增加最快，从直观上一般选σj0中的大者（可以任意选或按最小下标选）即max(σj0)=σk则对应的xk为换入变量。实际上换一次基将使目标函数值改进σkθ。换出变量确定klmlkimkimiikmkmmmmkmkmkmkmabaabxabxxabxxabx'''''''2''221''1100...................00minkmkmxZZ0