導語：經(jīng)濟管理論文-最小比值旋轉迭代法在生產(chǎn)計劃中的應用一文來源于網(wǎng)友上傳，不代表本站觀點，若需要原創(chuàng)文章可咨詢客服老師，歡迎參考。

一、方法簡述

對于一個線性規(guī)劃問題的標準形式

(1)

我們通常利用單純形法求解，但單純形法需要在一個基本可行解的情況下進行，且當基本可行解出現(xiàn)退化時，還可能產(chǎn)生循環(huán)現(xiàn)象。在《數(shù)理統(tǒng)計與管理》97年第11期趙學慧等提出用枚舉法求解，但此方法對于約束條件個數(shù)和變量個數(shù)很大時，其計算量是相當大的，且此文中的應用實例的最優(yōu)解x1=162,x2=135是錯的，很容易驗證此解不滿足第3個約束條件20x1+8x24000。最小值旋轉迭代法是利用單純形法的原理求最優(yōu)解，但此方法能有效克服上述兩種方法的不足，且簡單易行，計算量比一般方法更小。

1.1用最小值旋轉迭代法求最優(yōu)解的方法與步驟

線性規(guī)劃問題的標準形式如(1)所示。

第1步。建立如下初始旋轉迭代表格

表1

Cjc1c2…cnb

CBXBx1x2…xn

a11a12…a1nb1

a21a22…a2nb2

……………

am1am2…amnbm

第2步。若在表1中，存在一行，比如說第t行，對于所有Ijn,有atj0且bt≠0，此時原問題無可行解，停止計算。

第3步?？疾焖姓龜?shù)項aij,利用最小比值規(guī)則，計算出以此確定主元素atk，作旋

轉迭代運算得到如下表2，并在表2中的XB和CB的下方分別填上xk和ck。

表2

Cjc1c2…ck…cnb

CBXBx1x2…xk…xn

1112…0…1n1

2122…0…2n2

…………………

ckxkt1t2…I…tnt

…………………

m1m2…0…mnm公務員之家，全國公務員共同天地

第4步。如果還沒有得到一個明顯的可行基In,則考察除XB下方所出現(xiàn)的基變量所在行以外的所有正數(shù)ij,轉入第2步。如果已得到一個明顯的可行基In，則按照單純形法計算檢驗數(shù)的方法計算檢驗數(shù)ζj=CBj-cj(j=1,…，n)(此處j是此時表中xj所對應的系數(shù)列向量)，若所有的ζ0，則停止，已找到最優(yōu)解

1.2最小比值旋轉迭代法的幾點說明

1.如b中的元素有兩個或者兩個以上為0時，在利用最小比值法確定atk時，應取b中所有零元素所在行中最大的那個正數(shù)。

2.如果有相同的最小比值θ≠0，在確定atk時，應取所對應的ck中較大的那個。

3.如果表中xi所對應的列向量中有單位列向量εi=(0，…，0，1，0，…，0)T時，則確定的atk不能是單位列向量εi中的元素1。

4.如果通過最小比值旋轉迭代法進行后得到明顯的可行基In，則再利用量小比值法確定的那個tk，其所對應XB中的出基變量xt應是最先進入的。

二、應用實列

對文［1］中提出的線性規(guī)化問題應用實例用最小比值旋轉迭代法求解。

MaxL=800x1+=650x2

將此規(guī)化問題化成標準形式

MaxL=800x1+650x2

建立表格計算

Cj8006500000b

CBXBx1x2x3x4x5x6

0x36510001500

0x42045010010000

0x520800104000

11000-10

0x30-110061500

0x40250102010000

0x50-12001204000

800x111000-10

ζ0150000-800

Cj8006500000b

CBXBx1x2x3x4x5x6

0x30100300

0x403701-106000

0x60001200

800x11000200

ζ0-33000400

650x20100

0x40010

0x60001

800x11000

ζ0000

由于檢驗ζ≥0(j=1，…，6)，故原問題有最優(yōu)解效益指標L達到最大為，這與

用單純形法求的結果完全一致。

三、結束語

實例的計算步驟與結果向人們充分顯示了最小比值旋轉迭代法的公務員之家，全國公務員共同天地簡便性與可信度，從制定生產(chǎn)計劃的過程來看，用最小比值旋轉迭代法比用單純形法和枚舉法要簡單的多，且作者通過大量求解線性規(guī)劃問題及線性規(guī)劃教材中的Beale例子，都說明此方法是簡單易行的，可見最小比值旋轉迭代法在生產(chǎn)管理系統(tǒng)有廣泛的使用價值。