最小比值旋轉迭代法在生產計劃中的應用

時間：2022-10-09 02:50:35 經濟管理畢業論文我要投稿

相關推薦

最小比值旋轉迭代法在生產計劃中的應用

　　摘　要　本文通過用最小比值旋轉迭代法制定生產計劃的實例，向管理人員介紹計算性規劃最優解的一種簡單而易行的方法。

最小比值旋轉迭代法在生產計劃中的應用

　　關鍵詞：最小比值旋轉迭代法，生產計劃。

　　一、方法簡述

　　對于一個線性規劃問題的標準形式

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

　　1.1　用最小值旋轉迭代法求最優解的方法與步驟

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

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

　　表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，此時原問題無可行解，停止計算。

　　第3步。考察所有正數項aij,利用最小比值規則，計算出以此確定主元素atk，作旋

　　轉迭代運算得到如下表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下方所出現的基變量所在行以外的所有正數ij,轉入第2步。如果已得到一個明顯的可行基In，則按照單純形法計算檢驗數的方法計算檢驗數ζj=CBj-cj(j=1,…，n)(此處j是此時表中xj所對應的系數列向量)，若所有的ζ0，則停止，已找到最優解

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

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

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

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

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

　　二、應用實列

　　對文[1]中提出的線性規化問題應用實例用最小比值旋轉迭代法求解。

　　Max L=800x1+=650x2

　　將此規化問題化成標準形式

　　Max L=800x1+650x2

　　建立表格計算

　　Cj 800 650 0 0 0 0 b