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

一、方法簡(jiǎn)述

對(duì)于一個(gè)線性規(guī)劃問題的標(biāo)準(zhǔn)形式

(1)

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

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

線性規(guī)劃問題的標(biāo)準(zhǔn)形式如(1)所示。

第1步。建立如下初始旋轉(zhuǎn)迭代表格

表1

Cjc1c2…cnb

CBXBx1x2…xn

a11a12…a1nb1

a21a22…a2nb2

……………

am1am2…amnbm

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

第3步。考察所有正數(shù)項(xiàng)aij,利用最小比值規(guī)則，計(jì)算出以此確定主元素atk，作旋

轉(zhuǎn)迭代運(yùn)算得到如下表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公務(wù)員之家，全國公務(wù)員共同天地

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

1.2最小比值旋轉(zhuǎn)迭代法的幾點(diǎn)說明

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

2.如果有相同的最小比值θ≠0，在確定atk時(shí)，應(yīng)取所對(duì)應(yīng)的ck中較大的那個(gè)。

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

4.如果通過最小比值旋轉(zhuǎn)迭代法進(jìn)行后得到明顯的可行基In，則再利用量小比值法確定的那個(gè)tk，其所對(duì)應(yīng)XB中的出基變量xt應(yīng)是最先進(jìn)入的。

二、應(yīng)用實(shí)列

對(duì)文［1］中提出的線性規(guī)化問題應(yīng)用實(shí)例用最小比值旋轉(zhuǎn)迭代法求解。

MaxL=800x1+=650x2

將此規(guī)化問題化成標(biāo)準(zhǔn)形式

MaxL=800x1+650x2

建立表格計(jì)算

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

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

用單純形法求的結(jié)果完全一致。

三、結(jié)束語

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