【正文】 Page 1 of 9 1 第 4章 運(yùn)輸問題 Page 2 of 9 2 運(yùn)輸問題與有關(guān)概念 運(yùn)輸問題的求解 —表上作業(yè)法 運(yùn)輸問題應(yīng)用 —建模 本章內(nèi)容重點(diǎn) Page 3 of 9 3 運(yùn)輸問題模型及有關(guān)概念 問題的提出 一般的運(yùn)輸問題就是要解決把某種產(chǎn)品從若干個(gè)產(chǎn)地調(diào)運(yùn)到若干個(gè)銷地 ，在每個(gè)產(chǎn)地的供應(yīng)量與每個(gè)銷地的需求量已知 ， 并知道各地之間的運(yùn)輸單價(jià)的前提下 ， 如何確定一個(gè)使得總的運(yùn)輸費(fèi)用最小的方案 。 Page 4 of 9 4 例 :某公司從三個(gè)產(chǎn)地 A A2， A3將物品運(yùn)往四個(gè)銷地 B B B B4 ，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示，問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最??？ 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運(yùn)往銷地 Bj的運(yùn)輸量，得到下列運(yùn)輸量表： 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 。 1 , 2 , 3 , 4 )ijs t x x xx x x xx x x xxxx x xx x xx x xxixxj? ? ? ?? ? ? ?? ? ? ?? ? ?? ? ?? ? ?? ? ?? ? ?}產(chǎn)量 ( 3個(gè) ) }銷量（ 4個(gè)） Page 7 of 9 7 系數(shù)矩陣 1 1 1 1 0 0 0 0 0 0 0 00 0 0 0 1 1 1 1 0 0 0 000000000 11111 0 0 0 1 0 0 0 1 0 0 00 1 0 0 0 1 0 0 0 1 0 00 0 1 0 0 0 1 0 0 0 1 00 0 0 1 0 0 0 1 0 0 0 1??????????????11 12 13 14 21 12 23 24 31 32 33 34, , , , , , , , , , ,x x x x x x x x x x x x11 12 13 14 21 22 23 24 31 32 33 34, , , , , , , , , , ,P P P P P P P P P P P P Page 8 of 9 8 模型系數(shù)矩陣特征 m+n(3+4)行，分別表示各產(chǎn)地和銷地； m?n(3*4)列，分別表示各決策變量； 1，其余為 0，分別表示只有一個(gè)產(chǎn)地和一個(gè)銷地被使用。 Page 9 of 9 9 一般運(yùn)輸問題的提法： 假設(shè) A1, A2,… ,Am 表示某物資的 m個(gè)產(chǎn)地；B1,B2,… ,Bn 表示某物資的 n個(gè)銷地； si表示產(chǎn)地 Ai 的產(chǎn)量； dj 表示銷地 Bj 的銷量； cij 表示把物資從產(chǎn)地 Ai 運(yùn)往銷地 Bj 的單位運(yùn)價(jià) （ 表 43） 。 如果 s1 + s2 + … + sm = d1 + d2 + … + dn 則稱該運(yùn)輸問題為產(chǎn)銷平衡問題；否則 ， 稱產(chǎn)銷不平衡 。 一般運(yùn)輸問題的線性規(guī)劃模型及求解思路 Page 10 of 9 10 表 42 運(yùn)輸問題數(shù)據(jù)表 銷地 產(chǎn)地 B1 B2 … Bn 產(chǎn)量 A1 A2 ┇ Am c11 c12 … c1n c21 c22 … c2n ┇ ┇ ┇ ┇ cm1 cm2 … cmn s1 s2 ┇ sm 銷量 d1 d2 … dn 設(shè) xij 為從產(chǎn)地 Ai 運(yùn)往銷地 Bj 的運(yùn)輸量 ， 根據(jù)這個(gè)運(yùn)輸問題的要求 ， 可以建立運(yùn)輸變量表 （ 表 43） 。 產(chǎn)銷平衡 Page 11 of 9 11 表 43 運(yùn)輸問題變量表 銷地 產(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。j=1,2,…, n) 對于 產(chǎn)銷平衡 問題，可得到下列運(yùn)輸問題的模型： Page 13 of 9 13 在實(shí)際問題建模時(shí) ， 還會(huì)出現(xiàn)如下一些變化： （ 1） 有時(shí)目標(biāo)函數(shù)求最大 ， 如求利潤最大或營業(yè)額最大等； （ 2） 當(dāng)某些運(yùn)輸線路上的能力有限制時(shí) ，模型中可直接加入 （ 等式或不等式 ） 約束； (3)產(chǎn)銷不平衡的情況 。 當(dāng)銷量大于產(chǎn)量時(shí)可加入一個(gè)虛設(shè)的產(chǎn)地去生產(chǎn)不足的物資 ， 這相當(dāng)于在式 （ 42） 每一式中加上 1 個(gè)松弛變量 ， 共 m 個(gè)；當(dāng)產(chǎn)量大于銷量時(shí)可加入一個(gè)虛設(shè)的銷地去消化多余的物資 ， 這相當(dāng)于在式 （ 43） 每一式中加上 1 個(gè)松弛變量 ， 共 n 個(gè) 。 Page 15 of 9 15 運(yùn)輸問題是一種特殊的線性規(guī)劃問題 ， 在求解時(shí)依然可以采用單純形法的思路 ，如圖 41所示 。 由于運(yùn)輸規(guī)劃系數(shù)矩陣的特殊性 ， 如果直接使用線性規(guī)劃單純形法求解計(jì)算 ， 則無法利用這些有利條件 。 人們在分析運(yùn)輸規(guī)劃系數(shù)矩陣特征的基礎(chǔ)上建立了針對運(yùn)輸問題的表上作業(yè)法 。 下面主要討論 基本可行解 、 檢驗(yàn)數(shù)以及基的轉(zhuǎn)換 等問題 。 續(xù)下頁 Page 16 of 9 16 基本可行解 是否最優(yōu)解 結(jié)束 換基 是 否 圖 41 運(yùn)輸問題的求解思路 返回 轉(zhuǎn) 28頁 Page 17 of 9 17 考慮 產(chǎn)銷平衡問題 ， 由于我們關(guān)心的量均在表 42與表 43中 ， 因此考慮把表 42與表 43合成一個(gè)表 , 如下表 44 (下頁 ） 運(yùn)輸問題求解的有關(guān)概念 (產(chǎn)銷平衡 ) Page 18 of 9 18 銷地 產(chǎn)地 B1 B2 … Bn 產(chǎn)量 A1 c11 x11 c12 x12 … c1n x1n a1 A2 c21 x21 c22 x22 … c2n x2n a2 ┇ ┇ ┇ ┇ ┇ Am cm1 xm1 cm2 xm2 … cmn xmn am 銷量 b1 b2 … bn 銷地產(chǎn)地… 產(chǎn)量……┇ ┇ ┇…銷量 …銷地產(chǎn)地… 產(chǎn)量… s… s┇ ┇ ┇… s銷量 d d … d表 44 運(yùn)輸問題求解作業(yè)數(shù)據(jù)表 平衡 轉(zhuǎn) 31 Page 19 of 9 11 12 1 21 22 2 1 21 1 11 1 11 1 11 1 11 1 11 1 1n n m m m nx x x x x x x x xA ? 中任意 m+n階子式等于零，取第一行到 m+n－ 1行與 對應(yīng)的列（共 m+n1列）組成的 m+n－ 1階子式。 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個(gè) n個(gè) m*n Page 20 of 9 1 1 1 1110111?故 r(A)=m+n－ 1所以運(yùn)輸問題有 m+n－ 1個(gè)基變量 。 Page 21 of 9 21 運(yùn)輸問題的基變量共有 m + n 1 個(gè)， A的秩為 m + n 1。 怎樣找這 m + n 1 個(gè)基變量呢？ m + n 1 個(gè)基變量 不含閉回路。 運(yùn)輸問題的基變量 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 各不相同 ， 我們稱之為變量集合的 一個(gè)閉回路 ， 并將式 （ 47） 、 式 （ 48） 中的變量稱為這個(gè) 閉回路的頂點(diǎn) 。 閉回路 Page 23 of 9 23 例如 ， x13, x16, x36, x34, x24, x23 ； x23, x53, x55, x45, x41, x21 ； x11, x14, x34, x31等都是閉回路 。 若把閉回路的各變量格看作節(jié)點(diǎn) ， 在表中可以畫出如下形式的閉回路： 閉回路示意圖 Page 24 of 9 銷地 B1 B2 B3 B4 B5 B6 產(chǎn)量