運(yùn)籌學(xué)-運(yùn)輸問(wèn)題的表上作業(yè)法(名校講義)

1、第十講 運(yùn)輸問(wèn)題的表上作業(yè)法,1 運(yùn)輸問(wèn)題事例 2 運(yùn)輸問(wèn)題的一般形式 3 表上作業(yè)法,1 運(yùn)輸問(wèn)題事例 （1）,已知，有4個(gè)產(chǎn)地（源點(diǎn)）生產(chǎn)的產(chǎn)品需銷(xiāo)售到4個(gè)需求地（目 的地或匯點(diǎn)），其源點(diǎn)產(chǎn)量和目的地需求量見(jiàn)表1-5。 表1-5 運(yùn)輸問(wèn)題的需求量及產(chǎn)量,其源點(diǎn)到目的地的單位產(chǎn)品的運(yùn)費(fèi)價(jià)格見(jiàn)圖1-7。,1 運(yùn)輸問(wèn)題事例 （2）,24 18 12 36,22 28 17 23,圖1-7 運(yùn)輸費(fèi)用矩陣 表格旁邊數(shù)字為產(chǎn)量和需要求量,2 運(yùn)輸問(wèn)題的一般形式,ri源i產(chǎn)量， aj目的地j的需求量。,3 表上作業(yè)法 （1）,與單純形表格法一樣，該法亦分兩步進(jìn)行： 求出初始基礎(chǔ)可行解 求出最優(yōu)解 1 用

2、最小元素法求出滿(mǎn)意的初始基礎(chǔ)可解 其方法是，按照費(fèi)用矩陣元素Cij增長(zhǎng)順序逐個(gè)選擇引入基 本解的變量xij，非退化情況下，每選擇1個(gè)，就必然排除1 個(gè)源點(diǎn)或目的地，最后一步可一次排除1個(gè)源點(diǎn)和1個(gè)目的 地，這樣便可得到一個(gè)初始基礎(chǔ)可行解。,3 表上作業(yè)法 （2）,以上例考察，觀察圖1-7。 mincij=c22=1。故優(yōu)先分配源2和目的地2之間的產(chǎn)品,圖1-8 最小元素法第1步,3 表上作業(yè)法 （3）,余下元素中，最小值為c32=2。,圖1-9 最小元素法第2步,依此類(lèi)推，最后獲初始基礎(chǔ)可行解示如圖1-10中。,3 表上作業(yè)法 （4）,圖1-10 初始基礎(chǔ)可行解,即基礎(chǔ)解為： x11=22，x

3、12=18，x33=12，x42=8，x43=5，x44=23。 此時(shí)總費(fèi)用為225。,3 表上作業(yè)法 （5）,2求出最優(yōu)解 這有兩種方法：閉回路法和位勢(shì)法。 閉回路法，其思路是令表中空格（即非基礎(chǔ)解），對(duì)應(yīng)的變量由0增加d單位，然后在保持產(chǎn)品供求平衡（即滿(mǎn)足約束條件）情況下，使基礎(chǔ)解參與變動(dòng)，看其費(fèi)有如何變化，若費(fèi)用減少，則該非基變量可進(jìn)入基，否則，加以排除，其思路與單純形法一致。 現(xiàn)繼上圖繼續(xù)改進(jìn)基礎(chǔ)解，直至達(dá)優(yōu)。 i) 參見(jiàn)圖1-11，分析非基變量x32增加d單位以后，其它基礎(chǔ)解及費(fèi)用變化。,3 表上作業(yè)法 （6）,2求出最優(yōu)解,圖1-11 回路法原理,3 表上作業(yè)法 （7）,為使供求平

4、衡，必須符合： x32+dx42dx43+dx33d 變動(dòng)后，費(fèi)用增加值為：8d5d+4d2d=5d，即費(fèi)用增加，x32不能進(jìn)基，為比較，把增加1個(gè)單位產(chǎn)品所引起的費(fèi)用增加值填入相應(yīng)的非基變量表格內(nèi)，這又稱(chēng)檢驗(yàn)值。 注意，在用回路法求解每個(gè)非基變量檢驗(yàn)值時(shí)，在根據(jù)供求平衡尋找閉合回路過(guò)程中，其回路轉(zhuǎn)折點(diǎn)必須是基礎(chǔ)解！ 例如，分析非基解 x31x11x12x42x43x33x31。,3 表上作業(yè)法 （8）,對(duì)每個(gè)非基變量計(jì)算后，將其檢驗(yàn)值填入圖1-12中。,圖1-12 回路法計(jì)算結(jié)果 其中： 內(nèi)表示費(fèi)用元素 內(nèi)表示檢驗(yàn)值 表內(nèi)其它值為基礎(chǔ)解。,3 表上作業(yè)法 （9）,ii) 觀察表格，或檢驗(yàn)值全

5、部0，已達(dá)最優(yōu)勝，結(jié)束。 否則，選取最負(fù)的檢驗(yàn)值所對(duì)的非基變量，令其進(jìn)基。圖1-12中，x13的檢驗(yàn)值為最負(fù)，故令x13進(jìn)基，應(yīng)使x13盡量大，但又必須使其它變量非負(fù)。觀察x13變化規(guī)律：x13x12x42x43。 應(yīng)取下降變量中的最小值作為x13的值。此時(shí)minx12 ，x43=min2，5=2。故令x13=2則x12=0，x42=10，x43=3。 將圖1-12修正后，再求出當(dāng)前非變量的檢驗(yàn)值，示如圖1-13。 非基礎(chǔ)解的檢驗(yàn)數(shù)合為正，故獲最成解，總費(fèi)用為249。,3 表上作業(yè)法 （10）,圖1-13 回路法所得最優(yōu)表格,3 表上作業(yè)法 （11）, 位勢(shì)法（簡(jiǎn)捷法） 該法對(duì)運(yùn)輸費(fèi)用矩陣表格

6、每次可確定一組“行值”和“列值”。確定原則為使得每個(gè)基礎(chǔ)變量之費(fèi)用cij等于相應(yīng)得行、列值之和，根據(jù)該原則求出行列值之后，用這些值再去求解每個(gè)非基本變量的檢驗(yàn)數(shù)。 結(jié)合本例闡述該步驟：（見(jiàn)圖1-14）,3 表上作業(yè)法 （12）,圖1-14 用位勢(shì)法求解實(shí)例,3 表上作業(yè)法 （13）,i) 令si，tj分別為行值和列值 求解方程：si+tj=cij xijB基集 從方程知，共有m+n1個(gè)方程和m+n個(gè)未知量。由于我們感興趣的是相對(duì)值，故可令任一個(gè)行值或列值等于某個(gè)固定值，例如令t1=0，即可求出各行、列值，可見(jiàn)“行”“列”值不是唯一的。 對(duì)于本例，令t1=0后， 解聯(lián)立方程：,3 表上作業(yè)法 （

7、14）,ii)根據(jù)已得的si，tj值求出非基礎(chǔ)的檢驗(yàn)值（或成本變動(dòng)值）ij： ij =cij(si+tj) 例如：圖1-14中，13=c13(s1+t3)5(3+5)=-3 若130,則可進(jìn)入基，根據(jù)此法求出所有非基本變量對(duì)應(yīng)的檢驗(yàn)值（成本變動(dòng)值）后，選取minij (ij 0)所對(duì)應(yīng)的變量進(jìn)入基礎(chǔ)解。圖1-14中得知，13=-3為最小值，令x13進(jìn)基，采用回路法找出應(yīng)離開(kāi)的基變量，重新調(diào)整后，仍按上述步驟反復(fù)運(yùn)算，最后得出最優(yōu)解。 現(xiàn)在看位勢(shì)法的對(duì)偶解釋?zhuān)?結(jié)合本例，示如表1-6中。,3 表上作業(yè)法 （15）,表1-6 位勢(shì)法的對(duì)偶解釋,x11+x12+x13+x14 =24 x21+x22

8、+x23+x24 =18 x31+x32+x43+x44 =12 x41+x42+x43+x44 =36 x11 +x21 + x31 + x41 =22 x12 +x22 +x32 +x42 =28 x13 +x23 +x33 +x43 =17 x14 +x24 +x34 +x44 =23,(r1)s1 (r2)s2 (r3)s3 (r4)s4 (a1)t1 (a2)t2 (a3)t3 (a4)t4,c11 c12 c13 c14 . c44,3 表上作業(yè)法 （16）,表1-6列出了本例的供求關(guān)系的8個(gè)約束方程。 （由于 ，故只有7個(gè)獨(dú)立約束方程）。 該規(guī)劃的對(duì)偶約束必為：,3 表上作業(yè)法 （17）,顯然，si，tj即是對(duì)偶問(wèn)題的對(duì)偶變量y。共8個(gè)對(duì)偶變量， 每次送代時(shí)有7個(gè)基礎(chǔ)解變量，可寫(xiě)出7平衡方程式： si + tj =