淺析修正單純形法的計算

1、淺析修正單純形法的計算摘要：本文通過實(shí)例，對單純形法和修正單純形法進(jìn)行了具體的對 比分析，得出了在求解線性規(guī)劃問題時運(yùn)用修正單純形法明顯優(yōu)于 單純形法的結(jié)論。關(guān)鍵詞：單純形法 修正單純形法 對比 基矩 陣弓I言單純形法是求解優(yōu)化設(shè)計線性規(guī)劃問題行之有效的方法，在 線性規(guī)劃問題的求解上得到了廣泛的應(yīng)用。單純形法是利用單純 形表通過轉(zhuǎn)軸運(yùn)算最終獲得最優(yōu)解和目標(biāo)函數(shù)的極值，但一般要 列數(shù)個單純形表和進(jìn)行數(shù)次轉(zhuǎn)軸運(yùn)算，且要計算單純形表中的所 有元素,其計算量較大和較繁瑣。因此，人們在對單純形法進(jìn)行了 較深入的研究基礎(chǔ)上，推出了修正單純形法或稱改進(jìn)單純形法。1單純形法與修正單純形法算法對比分析下面就一具

2、體的線性規(guī)劃問題，分別用單純形法和修正單純形 法計算，然后做出對比分析。求解線性規(guī)劃問題min z = -7 x -12xs.9 x + 4 x4 x + 5 x3 x +10 x + x = 300X0（ j = 1，2，5）1.1單純形法運(yùn)用單純形表進(jìn)行運(yùn)算，即可得到該線性規(guī)劃問題的最優(yōu)解 和最優(yōu)值，具體運(yùn)算過程見表1,表2,表3所示。表1初始表解-7-120000-199ijcP.PP,PbP0 x19243140503603749003x450102002104004x31000130031430 f。）0000000-c f (a )-7-120000-19-17表2解-7-1200

3、00-199iJcPPPP一b-P-0 x17.82031405-0.4240248.430.7703x2.5001-0.5505320 -124x0.31000.13031.4100f (a, X-3.6-1200-1.2-360-376.8-c f J(a )-3.40001.2360357.8-77解-7-120000-199iJcPPPP,Pb0 x1020314-3.125 -0.248481.64-73x1000.4-0.22021.2-121x0100.120.162424.72-f (a, Y-7-120-13.6-0.52-428-448.88-c f J(a )0001.3

4、60.52428429.88-7720，經(jīng)過兩次運(yùn)算，得到該線性規(guī)劃問題的最優(yōu)解為X1% = 24，X3 = 84，X4 = X5 = 0，最優(yōu)值 z = -428。1.2修正單純形法(1)由問題的教學(xué)模型，寫出初始信息：P1P2P3P4P5-94100 -A =45010,c = -7 -12 0 0 0310001b = 360200300 t初始基方陣1 0 0_E = pp p =0 1 003450 0 11 0 0同時得E-1 = 0 1 0 00 0 1所以X =E0X3X4X5100360360E-1b =010200=2000_001 _300300c E-1 = 0 0E0

5、1 0 00 0 1 0 = 0 0 00 0 1(2)計算各非基本變量的相對價值系數(shù)，得r = c - c E-1 p = -7 - 09004=-745 =-1210L 廣 Cf - 0 (3)根據(jù)min尸=一7,r =一12= r，對應(yīng)非變量x，確定x為調(diào)入基本1222210 0_ 4-4_E-1 p =01 05=50200 11010變量的變量。同時計算(4)根據(jù)0規(guī)則，求.I 360 200 300 I 300 七-mn | 4- 11 = 10-=30 得到 s = 3，它所對應(yīng)的基本變量X5被確定為調(diào)出變量。于是得到新的基方陣E1 =P p p，相應(yīng)的 C =0 0 12(5)

6、計算新的基方陣的逆矩陣E1。因?yàn)閺那懊?3)(4 )步得到主元素為10,s=3,所以可以得到1 0r一1 .E-1E 0 -1 = 0 1L 010 0-0.4-0.5，所以0.110-0.4 -10-0.4 一360-240一E-1 =10010-0.50.1，x = E-1 x =氣1 E00010-0015200=5030c E-1 = 0E111 0 -0.41r0 -12 0 1 -0.5 = 00 -1.20 0 0.1用E1代替E-1重復(fù)以上步驟(2)-(5)。得到最優(yōu)解。最優(yōu)解為x = 20，x = 24， x = 84，x = x = 0。目標(biāo)函數(shù)的極小值為84z = c x

7、E =【0 -7 -12 20 = -428e22224由單純形法和修正單純形法的計算過程可得出如下幾點(diǎn)結(jié)論：修正單純形法和單純形法一樣，在進(jìn)行E=【p P . P烏到E =P % . P 匕的基方陣變換時，仍要確定進(jìn)行基本變量的變量七和離開基本變量七的判別和計算。因此, 規(guī)則和最速變化規(guī)則仍是修正單純形法應(yīng)遵循的基本原則；單純形法要計算單純形表中的所有元素，而修正單純形法只要 計算基矩陣的逆矩陣E-1和E-ib、E-1A、C - C e-1 A這三組數(shù)據(jù)。E E基方陣E求逆只需對其中的一列數(shù)據(jù)進(jìn)行計算，這可減少計算E的逆矩 陣的工作量。2結(jié)語由上述實(shí)例計算和對計算過程分析可知，修正單純形法的計 算量比單純形法的要小,且每次迭代時只存儲一個初等矩陣，存儲 量小。因此，修正單純形法是在計算機(jī)上求解線性規(guī)劃問題的實(shí)用 而有效的方法。參考文獻(xiàn)：徐成賢.修正單純形法的有效而穩(wěn)定的執(zhí)行方法J.西安交 通大學(xué)學(xué)報，1992,(04).郭強(qiáng).修正單純形法的計算量的注記J.運(yùn)籌與管理， 1999,(02).申