用对偶单纯形法求解线性规划问题.doc

=5x1+.-2x1+3x≥63x1-6x≥4Xj≥0(j=1,2)解:将问题转化为Maxz=-5x1--3x+x3=-6-3x1+6x+x4≥-4Xj≥0(j=1,2,3,4)其中,x3,x4为松弛变量,可以作为初始基变量,单纯形表见表4--17例4-7单纯形表Cj-6-3-40CBXBbX1X2X3X4迭代0次0X4-62[-3]100X5-4-36010-5-300CBXBbX1X2X3X4迭代1次-3X42-2/31-1/300X3-1610216-70-10在表4-17中,b=-16<0,而y≥0,:对偶单纯形法仍是求解原问题,它是适用于当原问题无可行基,,,只有人工变量法,,在原问题和对偶问题的最优解之间存在着密切的关系,可以根据这些关系,从求解原问题的最优单纯形表中,(p)为Minz=(LP)为Maxz=(D)为Maxz=(LP),得最优基B和最优单纯形表T(B)。对于(LP)来说,当j=n+i时,有Pj=-ei,cj=0从而,在最优单纯形表T(B)中,对于检验数,有(σn+1,σn+2…σn+m)=(cn++2…,cn+m)-CBB-1(Pn+1,Pn+2…,Pn+m)=-CBB-1(-I)于是,Y*=(σn+1,σn+2…σn+m)T。可见,在(LP)的最优单纯形表中,剩余变量对应的检验数就是对偶问题的最优解。同时,在最优单纯形表T(B)中,由于剩余变量对应的系数所以B-1=(-yn+1,-yn+2…-yn+m)求下列线性规划问题的对偶问题的最优解。Minz=6x1++2x≥203x1+2x≥50Xj≥0(j=1,2)解:将问题转化为Maxz=-6x1-.-x1—2x+x3=20-3x1-2x+x4=50Xj≥0(j=1,2,3,4)用对偶单纯形法求解如表表4-18例4-8单纯形表Cj-6-800CBXBbX1X2X3X4迭代0次-8X45/201-3/41/4-6X515101/2-