【正文】 運輸方式有：產(chǎn)地 ? 轉(zhuǎn)運站、轉(zhuǎn)運站 ? 銷地、產(chǎn)地 ? 產(chǎn)地、產(chǎn)地 ? 銷地、銷地 ? 轉(zhuǎn)運站、銷地 ? 產(chǎn)地等 。 1 2 3 4 產(chǎn)量 A 1 6 1 3 22 17 50 B 14 1 3 19 15 60 C 19 20 23 50 最低需要量 30 70 0 10 最高需要量 50 70 30 不限 Page 102 of 9 102 解：根據(jù)題意，作出產(chǎn)銷平衡與運價表 :最低要求必須滿足，因此把相應(yīng)的虛設(shè)產(chǎn)地運費取為 M ，而最高要求與最低要求的差允許按需要安排，因此把相應(yīng)的虛設(shè)產(chǎn)地運費取為 0 。 Page 98 of 9 B1 B2 B3 B4 B5 產(chǎn)量 A1 10 15 20 20 40 50 A2 20 40 15 30 30 100 A3 30 35 40 55 25 130 A4 0 M 0 0 0 20 需求 25 115 60 30 70 平衡 建立產(chǎn)銷平衡的運輸費用表為 例 :石家莊北方研究院有一、二、三，三個區(qū)。 最優(yōu)值 ： f* = 3 2+3 5+1 1+8 3+4 6+5 3 = 85 Page 80 of 9 80 作業(yè) ： 習題 —2,3(1) Page 81 of 9 81 我們已經(jīng)介紹過，可以通過增加虛設(shè)產(chǎn)地或銷地（加、減松弛變量）把問題轉(zhuǎn)換成產(chǎn)銷平衡問題，下面分別來討論。在這種情況下 ， 應(yīng)該對基本可行解進行調(diào)整 ， 即找到一個新的基本可行解使目標函數(shù)值下降 ， 這一過程通常稱為 換基(或主元變換 )過程 。 Page 60 of 9 60 如果規(guī)定作為起始頂點的非基變量為第 1 個頂點 ， 閉回路的其他頂點依次為第 2 個頂點 、 第 3 個頂點 …… 那么就有 ?ij = (閉回路上的奇數(shù)次頂點單位運費之和 ) (閉回路上的偶數(shù)次頂點單位運費之和 ) 其中 ij 為非基變量的下角指標 。因此， 對每一個非基變量可以找到而且只能找到唯一的一個閉回路。 當填上一個數(shù)后 行、列同時飽和時 ，也應(yīng)任意劃去一行（列），在保留的列（行）中沒被劃去的格內(nèi)標一個 0（ 目的是保證有m+n1個基變量 ） ,然后劃去該列（行）。若某行（列）的產(chǎn)量（銷量）已滿足，則把該行（列）的其他格劃去。 一般的方法步驟如下： 一、初始基本可行解的確定 Page 31 of 9 31 (1)在運輸問題求解 作業(yè)數(shù)據(jù)表 中 任選一個單元格 xij ( Ai 行 Bj 列交叉位置上的格 ),令 xij = min { ai , bj } 即從 Ai 向 Bj 運最大量 (使行或列在允許的范圍內(nèi)盡量飽和 ， 即使一個約束方程得以滿足 ),填入 xij 的相應(yīng)位置； Page 32 of 9 32 (2)從 ai 和 bj 中分別減去 xij 的值 ，修正為新的 ai 和 bj 即調(diào)整 Ai 的擁有量及 Bj 的需求量； (3)若 ai = 0， 則劃去對應(yīng)的行 （ 已經(jīng)把擁有的量全部運走 ） ， 若 bj = 0 則劃去對應(yīng)的列 （ 已經(jīng)把需要的量全部運來 ） ， 且每次只劃去一行或一列 （ 即每次要去掉且只去掉一個約束 ） ； Page 33 of 9 33 (4)當最終的運輸量選定時 ， 其所在行 、列同時滿足 ， 此時要同時劃去一行和一列 。 運輸問題的基變量 Page 22 of 9 22 定義 在表 44的決策變量格中，凡是能夠排列成下列形式的 xab ,xac ,xdc ,xde ,… ,xst ,xsb (47) 或 xab ,xcb ,xcd ,xed ,… ,xst ,xat (48) 其中 ， a,d,… ,s 各不相同； b,c,… ,t 各不相同 ， 我們稱之為變量集合的 一個閉回路 ， 并將式 （ 47） 、 式 （ 48） 中的變量稱為這個 閉回路的頂點 。 Page 15 of 9 15 運輸問題是一種特殊的線性規(guī)劃問題 ， 在求解時依然可以采用單純形法的思路 ，如圖 41所示 。 Page 4 of 9 4 例 :某公司從三個產(chǎn)地 A A2， A3將物品運往四個銷地 B B B B4 ，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如下表所示，問：應(yīng)如何調(diào)運可使總運輸費用最小？ B1 B2 B3 B4 產(chǎn)量 A1 3 11 3 10 7 A2 1 9 2 8 4 A3 7 4 10 5 9 銷量 3 6 5 6 20 （產(chǎn)銷平衡） Page 5 of 9 5 解： 產(chǎn)銷平衡問題： 總產(chǎn)量 = 總銷量 設(shè) xij 為從產(chǎn)地 Ai運往銷地 Bj的運輸量，得到下列運輸量表： B1 B2 B3 B4 產(chǎn)量 A1 x11 x12 x13 x14 7 A2 X21 X22 X23 X24 4 A3 X31 X32 X33 X34 9 銷量 3 6 5 6 20 （產(chǎn)銷平衡） Page 6 of 9 6 1 1 1 2 1 3 1 4 2 1 2 22 3 2 4 3 1 3 2 3 3 3 4m in 3 1 1 3 1 0 92 8 7 4 1 0 5f x x x x x xx x x x x x? ? ? ? ? ?? ? ? ? ? ?12 13 1421 22 23 2431 32 33 3421 3112 22 3213 23 3314111124 34. . 74936560 ( 1 , 2 , 3 。 產(chǎn)銷平衡 Page 11 of 9 11 表 43 運輸問題變量表 銷地 產(chǎn)地 B1 B2 … Bn 產(chǎn)量 A1 A2 ┇ Am x11 x12 … x1n x21 x22 … x2n ┇ ┇ ┇ xm1 xm2 … xmn s1 s2 ┇ sm 銷量 d1 d2 … dn 產(chǎn)銷平衡 m n Min f = ? ? cij xij i=1 j=1 n . ? xij = si i = 1,2,…, m (45) j =1 m ? xij = dj j = 1,2,…, n (46) i =1 xij ≥ 0 (i=1,2,…, m。 1 2 1 1 1 2 1 , 1, , , ,n n m n nx x x x x x ?， ， ，1 1 1 2 1 2 1 2 2 2 1 2, , , , , , , , , , , ,n n m m m nP P P P P P P P Pm個 n個 m*n Page 20 of 9 1 1 1 1110111?故 r(A)=m+n－ 1所以運輸問題有 m+n－ 1個基變量 。 推論 產(chǎn)銷平衡運輸問題 的 m + n 1 個 變量構(gòu)成基變量的充分必要條件是它 不含閉回路 。 下面分別舉例予以說明 。如此進行下去，直至得到一個基本可行解。 閉回路法 Page 55 of 9 55 這個過程就是尋找一個以非基變量 x24 為起始頂點的閉回路 —— {x24 ， x14 ，x13 ， x23 }， 這個閉回路的其他頂點均為基變量 (對應(yīng)著填上數(shù)字的格 )。 故也稱這個綜合影響為該非基變量對應(yīng)的 檢驗數(shù) 。 Page 64 of 9 64 由于有 m + n 個變量 （ ui , vj ）， m + n 1 個方程（基變量個數(shù)）， 故有一個自由變量，位勢不唯一 。 Page 72 of 9 銷地 產(chǎn)地 B1 B2 B3 B4 產(chǎn)量 A1 3 [1] 11 [2] 3 4 10 3 7 A2 1 3 9 [1] 2 1 8 [1] 4 A3 7 [10] 4 6 10 [12] 5 3 9 銷量 3 6 5 6 20(產(chǎn)銷平衡 ) 表 411 初始基本可行解及檢驗數(shù) 0 ??3 ??4 ??1 ?? Page 73 of 9 73 B1 B2 B3 B4 產(chǎn)量 ai A1 3 [ ] 11 [ ] 3 5 10 2 7 A2 1 3 9 [ ] 2 [ ] 8 1 4 A3 7 [ ] 4 6 10 [ ] 5 3 9 銷量 bj 3 6 5 6 20 選擇 ，則調(diào)整為 1? ? Page 74 of 9 vj ui B1 B2 B3 B4 產(chǎn)量 ai A1 3 11 3 5 10 2 7 A2 1 3 9 2 8 1 4 A3 7 4 6 10 5 3 9 銷量bj 3 6 5 6 20 3 3 10 0 [ 0] 9 2 5 [ 2] [ 2] [ 1] [ 9] [ 12] Page 75 of 9 ?ij ≥ 0，得到 最優(yōu)解 x13 = 5,x14 = 2,x21 = 3,x24 = 1, x32