《线性规划问题的最优解》由会员分享，可在线阅读，更多相关《线性规划问题的最优解（10页珍藏版）》请在金锄头文库上搜索。
1、线性规划问题的最优解引言线性规划是运筹学的一个基本分支，其应用极其广泛，其作用以为越来越多的人所重视。线性规划主要就实际问题抽象成数学形式，即求一组变量的值，在满意肯定的约束条件下，是某个目标达到最小或最大，而这些约束条件用可以用一组线性不等式或线性方程来表示。而求得目标函数的最优解尤为重要，本文就线性规划问题的最优解求解方法作出阐述，并举出实例加以强化，同时也指出了线性规划问题应用于生产与运作管理的重要性。1线性规划问题的最优解研讨1.1线性规划问题的提出考虑下面的线性规划问题的标准型:目标函数：约束条件:(1)minZ=CXJAX=b|X0其中，C=(c,c，,c),X二(x,x，,x)T
2、,b=(b,b，,b)T,A二(a)阶矩阵。12n12n12mjmxn设B是A中m个线性无关的列向量构成的一个基，B二(a)阶矩阵，这样将矩ijmxm阵A分成两个部分，即A=(B,N),X=(X,X),C=(C,C),X,c为基B对应的非基BNBNBB变量和系数，X,X为N对应的非基变量和系数，这样将线性规划问题改写为：NNminZ=(C,C)BN约束条件:X_(B,N)BXLNXXbn0=b经过矩阵变换，得出关于基B的标准型如下:证明：0，由(7)式可知，对任意一组可行解X=(x,x，,x)T,Z=Ycx,jjj=1约束条件:将(5)(6)绽开为:约束条件:Z=区cb0iii=1minZ=C
3、BB-1+(CCB-1N)X(5)NBNfX+B-1NX=B-1bBN1X,X01BNB-1b=(b:,b，12,b)Tm(、aa.a1m+11m+21naa.aB-1N=2m+12m+22ntamm+1amm+2a/mnminZ=cb+iii=1j=m+1x+ax=biijjj=m+1x0ja=c一区cajjiiji=11.2最优解判别准则迟ca)xiijji=1,称a为检验数。准则一：若X=(bb2,b,0,0)T，为对应于基B的基本可行解，且对于12m切的j=m+1,m+2,n，a0，则X为线性规划问题的最优解。均有ZZ，0但X能使等式成立，即Z=Z0解。当g0,j=m+1,m+2,nj
4、有某一个g=0，设j0，则该线性规划问题有其次个最优的基本可行解。证明：构造一个行解m+1i=1,2,m依据9原则x=9m+1x=0j9=min1i0,j=m+1,m+2,n，有某一个g=0，对一切i=1,2,m，jj则该线性规划有无穷多个最优解。证明：构造一个新解X，由（8）-axLim+1m+1i=1,2,mxm+1xj由于a0，故x0,i=1,2,mim+1i将X代入原目标函数（4）得：由于：b=cm+1,Z=cb+(c-区iii=1,i丰Lm+1i=1im+1-ca.=0m+1ii=1im+1故:cbiii=1Z=cb+0ii=1,i丰LX仍为可行解，得到无穷多可行解，而目标函数仍为，
5、即X也是最优解。Z=cb=Zii0i=1以下举出一些实例，进一步说明线性规划最优解的详细求解方法:2.线性规划最优解的问题举例2.1图解法求解线性规划问题例5:求解下面的线性规划问题：maxZ=5一8x,6x+2x一3x一2x=0,14560,j=1,2,6.j明显X*=(x,x，,x)t=(0,0,20,0,0,0”是该线性规划问题(1)的一个最优解。26b因c=c=0，及0=min匚:a454ab0,i=1,2,3J=0,a1405=minb-L:aa50,i=1,2,3=鼻=0,a25i4可考虑如下线性规划问题:maxW=x+x5(2)x+2x-3x=00,j=1,2,4,5.vj易解得
6、线性规划问题(2)的最优解为X=(x,x,x,x)t=(0,0,0,0)t,W(X)=0,于1245是可得X*=(x,x，,x)T=(0,0,20,0,0,0)t是该线性规划问题(1)的唯一最优解。126例27：求解下面的线性规划问题:maxZ=5-x6x+x-2x-x=04560,j=1,2,6.ij明显X*=(x,x，,x)t=(0,20,0,0,0,0)t是该线性规划问题(1)的一个最优解。126因c=c=0，及0=mmi454ai4b:a40,i=1,2,3J=0,i4aa14b05=minL:aa50,i=1,2,3=吐=0,a25可考虑如下线性规划问题:1 maxW=x+x5(2)
7、x+x-2x=00,j=1,3,4,5.ij易解得线性规划问题(2)有无界解，X=(x,x,x,x)T=(0,3,2,1)T是该问题的一个可1345行解，W(X)=30,于是线性规划问题的最优解不唯一。只要取X*=(x,x,x)T126如下：x=0,x=3s;1 3x=25-s(4x2+42x1)0;2x=2s,x=s;45x=0.6那么X也是线性规划问题的最优解。例如，分别取s=0.5、0.25时，则(0,0,1.5,1,0.5,0)T和(0,12.5,0.75,0.5,0.25,0)t以及X*=(0,25,0,0,0,0)t都是该线性规划问题(1)的最优解，其中，(0,25,0,0,0,0
8、)t是一退化的基可行解，(0,0,1.5,1,0.5,0)t是一非退化的基可行解，而(0,12.5,0.75,0.5,0.25,0)t=1(0,0,1.5,1,0.5,0+(0,25,0,0,0,0是一可行解而不是基解。例3：要将两种大小不同的钢板结成A,B,C三种规格，每张钢板可同时截得三种规格的小钢板的块数乳下表所示：钢板类型规格类型A规格B规格C规格第一种钢板211其次种钢板123今需A,B,C三种规格的成品分别为15，18，27块，问：各截取这两种钢板多少张可得所需三种规格成品，且使得所用钢板张数最少?2x+y15x+2y18解：需要截得第一种钢板X张，其次种钢板Y张，则卜+3y27（
9、*）x0y0作出可行区域图如下：目标函数为z=x+y，经过可行区域内的整点且与原点最近的直线是x+y二12。它上面的整点有（0,12）、（1,11）、（2,10）、（3,9）、（4，8）、（5，7）、（6,6）、（7,5）、（8,4）、X（9,3）、（10,2）、（11,1）、（12,0），若逐一争论其是否在可行域内比较麻烦时，只需先推断点A（导害）四周的整数点是否满意条件，若满意条件，则再试四周的整数点；若不满意条件，则不需要再推断下去。故此题，我们只需先推断A点四周的整数点（3,9）、（4,8），分别代入（*）式，易得它们都满意条件。故我们还需推断（2,10）、（5,7）两点，代入（*）式
10、发觉它们都不满意条件，则其余点不需要再推断。所以该题的最优解为（3,9）、（4,8）。例4(3:maxS=5x+2x，约束条件为:12x31012x,x0J12采用图解法求解如下:此例中约束条件中存在和目标函数的系数成比例的约束条件，但是由于此约束条件在可行域的形成中没有发挥作用，所以此问题没有多个最优解。图解法是求解含有两个变量的线性规划问题的一种很直观和有效的方法，所以在作出问题的可行域时，则可依据这个必要条件，若可行域中没有与目标函数平行的边界线时，则可直接推断出此问题肯定没有多个最优解。2.2单纯型法求解线性规划问题例5M:求解问题：minZ=-x+2x23s.t.x-2x+x=212
11、30,j=1,2,3,4,5J/解：这里B=(A,A,A)是一个单位矩145阵，且b=(2,1,2)t0，故基B是可行基,x,x,x为基变量，x,x为非基变量,14523基B对应的基本可行解为：x=(2,0,0,1,2)t，其目标函数值Z=0方程组Ax=b已是典0式，得到第一张单纯性表如下：x1x2x3x4x5RHS01-2000x11-21002x401*-3101x01-10125留意，第0行的元素应是将目标函数Z=-x+2x化成等价的方程Z+x-2x=02323后的相应元素。故当前解不是最优解，亠列中有两个元素a,a均为正数，取22232=minx为进基变量，x为出基变量。进行旋转变换后得下表:24x1x2x3x4x5RHS001-10-1x110-5204x201-3101x5002*-111故转轴元为a22,它对应的基本可行解为x=(4,l,0,0,l)T，其目标函数值为Z=-1但:=10，仍不03是最优解，此时a33为转轴元，进行旋转变换后得下表:x1x2x3x4x5RHS000113222x100151222010135A2222x001111322213513它对应的基本可行解为x二（齐刖W，其目示函数值为Zo一2此时检验数向量
