运筹学单纯形法

1、（1）化成标准型：Max3x1+5x2+0S1+0S2+0S3s.t.x1+S1=42x2+S2=123x1+2x2+S3=18x1,x2,S1,S2,S3>=0迭代次数基变量CB(Ci)X1X2S1S2S3b比值bi/aij350000S10101004---S20020101212/2S30320011818/2Zj00000Z=Z0=0*4+0*12+0*18=0σj=Cj-Zj350001S101010044/1X250101/206---S30300-1166/3Zj0505/20Z=Z0=0*4+5*6+0*6=30σj=Cj-Zj300-5/202S100011/3-1/32X250101/206X13100-1/31/32Zj3503/21Z=Z0=0*2+5*6+3*2=36σj=Cj-Zj000-3/2-1唯一最优解为X1=2，X2=6，S1=2，S2=0，S3=0最优值为Z=36（2）化成标准型：Max2x1-x2+x3+0S1+0S2+0S3s.t.3x1+x2+x3+S1=60x1-x2+2x3+S2=10x1+x2-x3+S3=20x1,x2,x3,S1,S2,S3>=0迭代次数基变量CB(Ci)X1X2X3S1S2S3b比值bi/aij2-110000S103111006060/3S201-120101010/1S3011-10012020/1Zj000000Z=Z0=0*60+0*10+0*20=0σj=Cj-Zj2-110001S1004-51-303030/4X121-120101010/-1S3002-30-111010/2Zj2-24020Z=Z0=0*30+2*10+0*10=20σj=Cj-Zj01-30-202S100011-1-210X12101/201/21/215X2-101-3/20-1/21/25Zj2-15/203/21/2Z=Z0=0*10+2*15+(-1)*5=25σj=Cj-Zj00-3/20-3/2-1/2唯一最优解为X1=15，X2=5，X3=0，S1=10，S2=0，S3=0最优值为Z=25（3）化成标准型：Max6x1+2x2+10x3+8x4+0S1+0S2+0S3s.t.5x1+6x2-4x3-4x4+S1=203x1-3x2+2x3+8x4+S2=254x1-2x2+x3+3x4+S3=10x1,x2,x3,x4,S1,S2,S3>=0迭代次数基变量CB(Ci)X1X2X3X4S1S2S3b比值bi/aij621080000S1056-4-41002020/-4S203-3280102525/2S304-2130011010/1Zj0000000Z=Z0=0*60+0*10+0*20=0σj=Cj-Zj621080001S1021-2081046060/-2S20-510201-255/1X3104-2130011010/-2Zj40-2010300010Z=Z0=0*60+0*5+10*10=100σj=Cj-Zj-34180-2200-102S101100121207070/11X22-510201-255/-5X310-601702-32020/-6Zj-7021074022-34Z=Z0=0*70+2*5+10*20=210σj=Cj-Zj7600-660-22343X1610012/111/112/11070/11X2201082/115/1121/11-2405/11X310001149/116/1134/11-3640/11Zj62101726/1176/11394/11-34σj=Cj-Zj000-1638/11-76/11-394/1134此线性规划问题有无界解。2、（1）化成标准型：Max4X1+5X2+X3+0S1+0S2-MA1-MA2s.t.3x1+2x2+x3-S1+A1=182x1+x2+S2=4x1+x2-x3+A2=5x1,x2,x3,S1,S2,A1,A2>=0迭代次数基变量CBX1X2X3S1S2A1A2b比值45100-M-M0A1-M321-10101818/3S20210010044/2A2-M11-1000155/1zj-4M-3M0M-M-M0Z=-23M4+4M5+3M1-MM0-M1A1-M01/21-1-3/2101224X1411/2001/20024A2-M01/2-10-1/20136zj42-M0M2+2M-M-M-15M+803+M1-M-2-2M002A1-M-101-1-2101010X2521001004----A2-M-10-10-1011-1zj10+2M50M5+3M-M-MZ=20-6-2M01-M-5-3M003X31-101-1-21010X2521001004A2-M-200-1-31111zj9+2M51-1+M3+3M1-M-M-5-2M001-M-3-3M-10因为此时A2为11不为零，所以此线性规划问题无可行解。（2）化成标准型：Max2x1+x2+x3+0S1+0S2+0S3-MAs.t.4x1+2x2+2x3-S1+A=42x1+4x2+S2=204x1+8x2+2x3+S3=16x1,x2,x3,S1,S2,S3,A>=0迭代次数基变量CBX1X2X3S1S2S3Ab比值211000-M0A-M422-100144/4S2024001002020/2S3048200101616/4zj-4M-2M-2MM00-MZ=-4M2+4M1+2M1+2M-M0001X1211/21/2-1/4001/41-4S2003-11/210-1/21836S30060101-11212/1zj211-1/2001/220001/200-M-1/22X12121/2001/4048S2000-101-1/2012-12S10060101-112---zj241001/20Z=80-3000-1/2-M此时最优解为X1=4，X2=0，X3=0，S1=12，S2=12，S3=0，A=0。最优值为Z=8。因为X3检验数为0，所以此线性规划问题有无穷多最优解。再迭代一次证明：3X31241001/208S20240010020S10060