線性規(guī)劃的單純形法表格方法

1、線性規(guī)劃的單純形法表格方法Max. z=5xi+2x2+3x3 -x4 +x5s.t.x1+2x2+2x3 +x4=83x1+4x2+x3+x5 =7x盧0j=1,2,3,4,5表1Z中ch b的值C f523-11常數(shù)bj 基變量X1X2X3X4Y-1X1221088/2=41X53410177/1=7c.-z.30400Z=-1由表的中間行可求出基本可行解，令x1=x2=x3=0,由約束條件得x4=8,x5=7.表中最后一行分別為：z = Q 1 J8 = -8 + 7 = -1c -z = 5-Q1 JI5-(-1 + 3) = 331 13 Jc2-(-1二2 - (-2 + 4) =

2、 0c - z = 3-(-1 1/233二3 - (-2 +1) = 4因?yàn)镃j-Zj行中存在正值，所以當(dāng)前基本可行解不是最優(yōu)解。-%行中的4最大因而非基變量 x3使Z有最大的單位增量，把x3選作新的（換入）基變量。J為確定被換出的基變量，采用最小比值法。用X3列的值除以約束條件的常數(shù)（8/2=4, 7/1=7）。 第一行有最小比值，把它叫做旋轉(zhuǎn)行。第一行原來(lái)的基變量是X4，此時(shí)X4為換出基變量， 新的基變量為X3、X5。為此需要把表中X3對(duì)應(yīng)在約束條件中系數(shù)變?yōu)閱挝恢担?，0）。在 表1中：1）用2除旋轉(zhuǎn)行使X3系數(shù)為1； 2）用-1/2乘旋轉(zhuǎn)行加到第二行消去X3。Z中ch b 的值c f

3、523-11常數(shù)bj 基變量X1X2X3X4X53X31/2111/2044/(1/2)=81X55/230-1/2133/(5/2)=6/5c.-z.1-40-20Z=15c - z = 5-G 1/211 5/2)丁丁-1-（3 j：仰因?yàn)镃j-Zj行中仍存在正值，所以當(dāng)前基本可行解不是最優(yōu)解。Cj-Zj行中的1最大因而非基變 量X1使z有最大的單位增量，把X1選作新的（換入）基變量。J為確定被換出的基變量，采用最小比值法。用X1列的值除以約束條件的常數(shù)（4/（1/2）=8, 3/（5/2）=6/5）。第二行有最小比值，把它叫做旋轉(zhuǎn)行。第二行原來(lái)的基變量是X5，此時(shí)X5 為換出基變量，新的

4、基變量為X3、X。為此需要把表中X1對(duì)應(yīng)在約束條件中系數(shù)變?yōu)閱挝?值（0，1）。在表1中：1）用5/2除旋轉(zhuǎn)行使X系數(shù)為1； 2）用-1/5乘旋轉(zhuǎn)行加到第一行 消去X。Z中ch b的值c f523-11常數(shù)bJ 基變量X1X2X3X4X53X302/513/5-1/517/5516/50-1/52/56/5c.-z.0-26/50-9/5-2/5Z=81/5/ 2/5二2-3 6/5-26/5=51/5 + 30/5 = 81/5 c - z = 2-（3 5）1 1 6/5=-1 -4/5 = -9/5 c -z =1-G 5尸/j = 1-7/5= -2/53 3 2/5）c.-z.行中系數(shù)全為非正，說(shuō)明不可能再改進(jìn)目標(biāo)函數(shù)值