- 相關(guān)推薦
最小比值旋轉(zhuǎn)迭代法在生產(chǎn)計(jì)劃中的應(yīng)用
摘 要 本文通過用最小比值旋轉(zhuǎn)迭代法制定生產(chǎn)計(jì)劃的實(shí)例，向管理人員介紹計(jì)算性規(guī)劃最優(yōu)解的一種簡單而易行的方法。
關(guān)鍵詞：最小比值旋轉(zhuǎn)迭代法，生產(chǎn)計(jì)劃。
一、方法簡述
對于一個線性規(guī)劃問題的標(biāo)準(zhǔn)形式
(1)我們通常利用單純形法求解，但單純形法需要在一個基本可行解的情況下進(jìn)行，且當(dāng)基本可行解出現(xiàn)退化時，還可能產(chǎn)生循環(huán)現(xiàn)象。在《數(shù)理統(tǒng)計(jì)與管理》97年第11期趙學(xué)慧等提出用枚舉法求解，但此方法對于約束條件個數(shù)和變量個數(shù)很大時，其計(jì)算量是相當(dāng)大的，且此文中的應(yīng)用實(shí)例的最優(yōu)解x1=162,x2=135是錯的，很容易驗(yàn)證此解不滿足第3個約束條件20x1+8x24000。最小值旋轉(zhuǎn)迭代法是利用單純形法的原理求最優(yōu)解，但此方法能有效克服上述兩種方法的不足，且簡單易行，計(jì)算量比一般方法更小。
1.1 用最小值旋轉(zhuǎn)迭代法求最優(yōu)解的方法與步驟
線性規(guī)劃問題的標(biāo)準(zhǔn)形式如(1)所示。
第1步。建立如下初始旋轉(zhuǎn)迭代表格
表1
Cj c1 c2 … cn b
CB XB x1 x2 … xn
a11 a12 … a1n b1
a21 a22 … a2n b2
… … … … …
am1 am2 … amn bm
第2步。若在表1中，存在一行，比如說第t行，對于所有Ijn,有atj0且bt≠0，此時原問題無可行解，停止計(jì)算。
第3步。考察所有正數(shù)項(xiàng)aij,利用最小比值規(guī)則，計(jì)算出以此確定主元素atk，作旋
轉(zhuǎn)迭代運(yùn)算得到如下表2，并在表2中的XB和CB的下方分別填上xk和ck。
表2
Cj c1 c2 … ck … cn b
CB XB x1 x2 … xk … xn
11 12 … 0 … 1n 1
21 22 … 0 … 2n 2
… … … … … … …
ck xk t1 t2 … I … tn t
… … … … … … …
m1 m2 … 0 … mn m
第4步。如果還沒有得到一個明顯的可行基In,則考察除XB下方所出現(xiàn)的基變量所在行以外的所有正數(shù)ij,轉(zhuǎn)入第2步。如果已得到一個明顯的可行基In，則按照單純形法計(jì)算檢驗(yàn)數(shù)的方法計(jì)算檢驗(yàn)數(shù)ζj=CBj-cj(j=1,…，n)(此處j是此時表中xj所對應(yīng)的系數(shù)列向量)，若所有的ζ0，則停止，已找到最優(yōu)解
1.2 最小比值旋轉(zhuǎn)迭代法的幾點(diǎn)說明
1.如b中的元素有兩個或者兩個以上為0時，在利用最小比值法確定atk時，應(yīng)取b中所有零元素所在行中最大的那個正數(shù)。
2.如果有相同的最小比值θ≠0，在確定atk時，應(yīng)取所對應(yīng)的ck中較大的那個。
3.如果表中xi所對應(yīng)的列向量中有單位列向量εi=(0，…，0，1，0，…，0)T時，則確定的atk不能是單位列向量εi中的元素1。
4.如果通過最小比值旋轉(zhuǎn)迭代法進(jìn)行后得到明顯的可行基In，則再利用量小比值法確定的那個tk，其所對應(yīng)XB中的出基變量xt應(yīng)是最先進(jìn)入的。
二、應(yīng)用實(shí)列
對文[1]中提出的線性規(guī)化問題應(yīng)用實(shí)例用最小比值旋轉(zhuǎn)迭代法求解。
Max L=800x1+=650x2
將此規(guī)化問題化成標(biāo)準(zhǔn)形式
Max L=800x1+650x2
建立表格計(jì)算
Cj 800 650 0 0 0 0 b
CB XB x1 x2 x3 x4 x5 x6
0 x3 6 5 1 0 0 0 1500
0 x4 20 45 0 1 0 0 10000
0 x5 20 8 0 0 1 0 4000
1 1 0 0 0 -1 0
0 x3 0 -1 1 0 0 6 1500
0 x4 0 25 0 1 0 20 10000
0 x5 0 -12 0 0 1 20 4000
800 x1 1 1 0 0 0 -1 0
ζ 0 150 0 0 0 -800
Cj 800 650 0 0 0 0 b
CB XB x1 x2 x3 x4 x5 x6
0 x3 0 1 0 0 300
0 x4 0 37 0 1 -1 0 6000
0 x6 0 0 0 1 200
800 x1 1 0 0 0 200
ζ 0 -330 0 0 40 0
650 x2 0 1 0 0
0 x4 0 0 1 0
0 x6 0 0 0 1
800 x1 1 0 0 0
ζ 0 0 0 0
由于檢驗(yàn)ζ≥0(j=1，…，6)，故原問題有最優(yōu)解效益指標(biāo)L達(dá)到最大為，這與
用單純形法求的結(jié)果完全一致。
三、結(jié)束語
實(shí)例的計(jì)算步驟與結(jié)果向人們充分顯示了最小比值旋轉(zhuǎn)迭代法的簡便性與可信度，從制定生產(chǎn)計(jì)劃的過程來看，用最小比值旋轉(zhuǎn)迭代法比用單純形法和枚舉法要簡單的多，且作者通過大量求解線性規(guī)劃問題及線性規(guī)劃教材中的Beale例子，都說明此方法是簡單易行的，可見最小比值旋轉(zhuǎn)迭代法在生產(chǎn)管理系統(tǒng)有廣泛的使用價值。
參考文獻(xiàn)
[1] 趙學(xué)慧，趙瑛，枚舉法在制定生產(chǎn)計(jì)劃中的應(yīng)用，數(shù)理統(tǒng)計(jì)與管理，1997年第11期.
[2] 許建中，許紹吉，線性規(guī)劃，科學(xué)出版社，1990年.
【最小比值旋轉(zhuǎn)迭代法在生產(chǎn)計(jì)劃中的應(yīng)用】相關(guān)文章：
ERP在LNG工廠中的應(yīng)用10-05
中職計(jì)算機(jī)應(yīng)用基礎(chǔ)中的應(yīng)用論文10-09
油田化學(xué)的應(yīng)用和化學(xué)品中的應(yīng)用10-08
包裝件模擬運(yùn)輸旋轉(zhuǎn)振動測試的標(biāo)準(zhǔn)解讀及應(yīng)用分析10-05
淺析計(jì)算機(jī)應(yīng)用基礎(chǔ)教學(xué)中的應(yīng)用論文10-08
高職計(jì)算機(jī)應(yīng)用基礎(chǔ)教學(xué)中的應(yīng)用論文10-08