[經(jīng)管營銷]2運輸問題-文庫吧資料
2025-01-25 16:50本頁面
【正文】 ij ( i , j )?基變量指標(biāo)集 ，相繼確定 ui 、 vj 。, vn 為列位勢。稱 u1 , 方程組 （ ） 共有 m+n 未知數(shù)和 m+n1個方程 。, um , v1 , 下面介紹一 種較為簡便的方法 ——位勢法 。 表 2—11 空 格 閉 回 路 檢驗數(shù) (A1 , B1) (1,1)? (1,3)? (2,3)? (2,1)?(1,1) 1 (A1 , B2) (1,2)? (1,4)? (3,4)? (3,2)?(1,2) 2 (A2 , B2) (2,2)? (2,3)? (1,3)? (1,4)? (3,4)? (3,2)? (2,2) 1 (A2 , B4) (2,4)? (2,3)? (3,3)? (1,4)?(2,4) 1 (A3 , B1) (3,1)? (3,4)? (1,4)? (1,3)? (2,3)? (2,1)? (3,1) 10 (A3 , B3) (3,3)? (3,4)? (1,4)? (1,3)? (3,3) 12 2. 方法二： 位勢法 用閉回路法求檢驗數(shù)時，需要給每一空格找一條閉 回路。 表 2—10 銷地 產(chǎn)地 B1 B2 B3 B4 產(chǎn)量 A1 3 （ +1） 4 3 （ 1） 3 7 A2 3 1 （ 1） 1 2 （ +1） 4 A3 6 3 9 銷量 3 6 5 6 按以上所述，就可以找出 所有空格的檢驗數(shù)，見 如下表 2—11。 可見這一調(diào)整方案使運費增加了： (+1)?3 + (1) ?3 + (+1)?2 + (1) ?1 = 1 (元 ) 這表明若這樣調(diào)整運輸方式將增加運費。 閉回路計算檢驗數(shù)的經(jīng)濟解釋為：在已給出初始解的 表 2—7中，可以從任一空格出發(fā)，如從 (A1 , B1) 出發(fā)，若 讓 A1 的產(chǎn)品調(diào) 1 噸給 B1 ， 為了保持產(chǎn)銷平衡，就要依次 作調(diào)整：在 (A1 , B3) 處減少 1 噸， (A2 , B3) 處增加 1 噸， (A2 , B1) 處減少 1 噸，即構(gòu)成了以 (A1 , B1) 空格為起點， 其它為有數(shù)字的格的閉回路。 直到回到起始空格處為止。 1. 閉回路法 在給出調(diào)運方案的計算表上，如表 2—9，從每一空格 出發(fā)，找一條閉回路。因運輸 問題的目標(biāo)函數(shù)是要求實現(xiàn)最小化，所以當(dāng)所有的非基 變量檢驗數(shù)全都 ? 0 時為最優(yōu)解。本例用伏格爾方法給 出的初始解，這個方案的總運費為 85元。 由以上可見：伏格爾方法同最小元素法除在確定供求 關(guān)系的原則上不同外，其余步驟相同，因而給出的初始調(diào)運方案也是基可行解。重復(fù)第一、二步的工作，直到給出初始解為止。在產(chǎn)銷平衡表的 ( A3 , B2 ) 空格處填 入 6。B2 列中最小元素為 4（即 A3 行），可確定 A3 產(chǎn)品優(yōu)先供應(yīng) B2 。同時在 單位運價表中劃去一行或一列。如此可得表 2—8： 銷地 產(chǎn)地 B1 B2 B3 B4 行差額 A1 3 11 3 10 0 A2 1 9 2 8 1 A3 7 4 10 5 1 列差額 2 5 1 3 表 2—8 第二步：從行差額和列差額中選出最大者，選擇它所在 的行或列中的最小元素。我們還是用例 1 來說明伏 格爾法的具體實施過程，步驟如下： 第一步：在單位運價表中增加一行和一列，列的格位置 相應(yīng)填入該行的次小運費與最小運費之差，我們稱之為 行差額。這就有一個差額，差額越大，說明不能按最小 運費調(diào)運時，運費增加就越多。 2. 方法二、 伏格爾法 ： 最小元素法的缺點是，為了節(jié)省一處的費用，有時造成在其它地方要花多幾倍的運費。為了使有數(shù)字的格不減少， ( 有數(shù)字的格的總數(shù)應(yīng)為 m + n –1個 )可以在空格 ( A1, B1 ) 、 ( A1, B3 ) 、 ( A2, B4 ) 、 ( A3, B4 )中任選一個格添加一個 “ 0”；同樣，這個添加的“ 0”格當(dāng) 作基變量，取值為 0。為了 使調(diào)運方案中有數(shù)字的格仍為（ m + n –1） 個，需要在同 時劃去的行或列的任一空格位置添上一個“ 0”，這個“ 0” 表示該變量是基變量，只不過它取值為 0，即此時的調(diào)運 方案是一個退化的基可行解。 應(yīng)當(dāng)注意的是，在用最小元素法確定初始基可行解 的時候，有可能出現(xiàn)以下的兩種特殊情況： 當(dāng)在中間步驟的未劃去的單位運價表中尋找最小元 素時，發(fā)現(xiàn)該元素所在行的剩余產(chǎn)量等于該元素所在列 的剩余銷售量。 如此，一步步進行下去，直到單位運價表中所有元素 都劃去為止，最終在產(chǎn)銷平衡表上就可以得到一個初始 調(diào)運方案。 銷地 產(chǎn)地 B1 B2 B3 B4 產(chǎn)量 A1 4 3 7 A2 3 1 4 A3 6 3 9 銷量 3 6 5 6 5 10 4 7 A3 8 2 9 1 A2 10 3 11 3 A1 B4 B3 B2 B1 表 2—7 第三步 : 從上述第二步所得的單位運價表未劃去的元素中 找出最小元素為 3。 由于 A2 每天生產(chǎn) 4噸， B1 每天只需要 3噸，即 A2 除每日能滿足 B1 的需要外還余 1噸。 表 2—5 5 10 4 7 A3 8 2 9 1 A2 10 3 11 3 A1 B4 B3 B2 B1 銷地 產(chǎn)地 3 6 5 6 7 4 9 產(chǎn)量 銷量 表 2—6 單位：噸 銷地 產(chǎn)地 B1 B2 B3 B4 產(chǎn)量 A1 7 A2 4 A3 9 銷量 3 6 5 6 解：先畫出這個問題的產(chǎn)銷平衡表 2—6。已知 從各工廠到各銷售點的單位產(chǎn)品的運價如表 2—5所示。舉例如下： 例 2：某公司經(jīng)銷甲產(chǎn)品，它下設(shè)三個加工廠，每日 的產(chǎn)量分別為： A1—7噸、 A2—4噸、 A3—9噸。 確定初始基可行解 確定初始基可行解即首先給出初始的調(diào)運方案， 方法很多，我們只介紹其中的兩種方法： 1. 方法一、 最小元素法： 最小元素法的基本思想就是 就近供應(yīng) 。 （ 4）重復(fù)（ 2）、（ 3）步，直到求得最優(yōu)解為止。只是具體計算和術(shù)語有所不同，可歸納為： （ 1） 找出初始基可行解 ，即在 (m?n) 產(chǎn)銷平衡表上給出m+n1個有數(shù)字的格，這些有數(shù)字的格不能構(gòu)成閉回路，且 行和等于產(chǎn)量，列和等于銷售量 ； （ 2） 求各非基變量的檢驗
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1