【正文】 第三章 運(yùn)輸問(wèn)題 第三章 特殊的線性規(guī)劃 —— 運(yùn)輸問(wèn)題 ? 模型及其特點(diǎn) ?求解思路及相關(guān)理論 ?求解方法 —— 表上作業(yè)法 ? 運(yùn)輸問(wèn)題的推廣 ? 產(chǎn)銷不平衡的運(yùn)輸問(wèn)題 ? 轉(zhuǎn)運(yùn)問(wèn)題 第三章 運(yùn)輸問(wèn)題 運(yùn)輸問(wèn)題模型與性質(zhì) 一 、 運(yùn)輸問(wèn)題的數(shù)學(xué)模型 運(yùn)輸問(wèn)題的一般提法： 人們?cè)趶氖律a(chǎn)活動(dòng)中 ， 不可避免地要進(jìn)行物資調(diào)運(yùn)工作 。 如某時(shí)期內(nèi)將生產(chǎn)基地的煤 、 鋼鐵 、 糧食等各類物資 ， 分別運(yùn)到需要這些物資的地區(qū) ， 根據(jù)各地的生產(chǎn)量和需要量及各地之間的運(yùn)輸費(fèi)用 ， 如何制定一個(gè)運(yùn)輸方案 ， 使總的運(yùn)輸費(fèi)用最小 。 這樣的問(wèn)題稱為運(yùn)輸問(wèn)題 。 第三章 運(yùn)輸問(wèn)題 單位 根據(jù)具體問(wèn)題選擇確定 。 表 31 有關(guān)信息 單位 運(yùn)價(jià) 銷 或運(yùn)距 地產(chǎn)地 B1 B2 … Bn 產(chǎn) 量 A1 A2 ┆ Am c11 c12 … c1 n c21 c22 … c2n … … … cm1 cm2 … cm n a1 a2 ┆ am 銷 量 b1 b2 … bn ?????njjmii ba11第三章 運(yùn)輸問(wèn)題 運(yùn)輸問(wèn)題的數(shù)學(xué)模型 【 例 1】 如 圖 31所示的網(wǎng)絡(luò)圖，有 A1， A2，A3三個(gè)產(chǎn)糧區(qū)，可供應(yīng)糧食分別為 10， 8，5（萬(wàn)噸），現(xiàn)將糧食運(yùn)往 B1， B2， B3， B4四個(gè)地區(qū)，其需要量分別為 5， 7， 8， 3（萬(wàn)噸）。產(chǎn)糧地到需求地（銷地）的運(yùn)價(jià)（元 /噸）如 表 32所示，問(wèn)如何安排一個(gè)運(yùn)輸計(jì)劃，使總的運(yùn)輸費(fèi)用最少。 第三章 運(yùn)輸問(wèn)題 需求地 產(chǎn)地 B1 B2 B3 B4 供給量 A1 3 2 6 3 10 A2 5 3 8 2 8 A3 4 1 2 9 5 需要量 5 7 8 3 合計(jì)23 表 32產(chǎn)銷平衡表 圖 31 第三章 運(yùn)輸問(wèn)題 【 解 】 設(shè) xij (i=1,2,3； j=1,2,3,4)為 i個(gè)產(chǎn)糧地運(yùn)往第 j個(gè)需求地的運(yùn)量 (萬(wàn)噸 )，這樣得到下列運(yùn)輸問(wèn)題的數(shù)學(xué)模型： (1)使總的運(yùn)輸費(fèi)用最小，則目標(biāo)函數(shù)為 343332312423222114131211 92428353623m i n xxxxxxxxxxxxZ ????????????實(shí)際總運(yùn)費(fèi)等于 Z乘以 10000。 （ 2）各產(chǎn)糧地的供給量與運(yùn)出量的平衡方程 第三章 運(yùn)輸問(wèn)題 （ 3）供給各需求地的供給量與需要量的平衡方程 （ 4）糧食的運(yùn)量應(yīng)大于或等于零（非負(fù)要求），即 有些問(wèn)題表面上與運(yùn)輸問(wèn)題沒(méi)有多大關(guān)系，其模型的數(shù)學(xué) 結(jié)構(gòu)與例 1運(yùn)輸問(wèn)題模型形式相同，我們把這類模型都稱為 運(yùn)輸模型。 第三章 運(yùn)輸問(wèn)題 不失一般性 . 設(shè)有 m個(gè)產(chǎn)點(diǎn) Ai, i=1,2,…,m. 可供應(yīng)某種物資 ,其供應(yīng)量 (產(chǎn)量 )分別為 ai , i=1,2,…,m. 有 n個(gè)銷地 Bj , j=1,2,…,n. 其需要量分別為 bj, j=1,2,…,n. 從 Ai到 Bj運(yùn)輸單位物資的運(yùn)價(jià)為cij, 上述數(shù)據(jù)可匯總于 產(chǎn)銷表 和 單位運(yùn)價(jià)表 中 .問(wèn)如何安排調(diào)運(yùn)方案使總運(yùn)費(fèi)最小 . 第三章 運(yùn)輸問(wèn)題 銷地 產(chǎn)地 1 2 … n 產(chǎn)量 1 2 … m a1 a2 … am 銷量 b1 b2 … b n 表 33 產(chǎn)銷平衡表 銷地 產(chǎn)地 1 2 … n 1 2 … m c11 c12 … c 1n c21 c22 … c 2n … cm1 cm2 … c mn 表 34 單位運(yùn)價(jià)表 第三章 運(yùn)輸問(wèn)題 【 解 】 設(shè) xij為從產(chǎn)地 Ai運(yùn)往銷地 Bj的物資數(shù)量 （ i=1， … m； j=1， … n） ， 由于從Ai運(yùn)出的物資總量應(yīng)等于 Ai的產(chǎn)量 ai， 因此 xij應(yīng)滿足： miaxnjiij ,2,11?????第三章 運(yùn)輸問(wèn)題 同理，運(yùn)到 Bj的物資總量應(yīng)該等于 Bj的銷量 bj，所以 xij還應(yīng)滿足： 總運(yùn)費(fèi)為： ????mijij njbx1,1 ?? ?? ??minjijijxcz1 1第三章 運(yùn)輸問(wèn)題 運(yùn)輸問(wèn)題的數(shù)學(xué)模型 ???????????????????? ???? ?njmixnjbxmiaxtsxcM i n Zijmijijnjiijminjijij,1。,1,0,1,1..111 1????（ 31） ?????????? ?? ?minjji ba1 1產(chǎn)銷平衡條件第三章 運(yùn)輸問(wèn)題 二、運(yùn)輸問(wèn)題的特點(diǎn) 1． 約束方程組的系數(shù)矩陣具有特殊的結(jié)構(gòu) 寫(xiě)出式 （ 31） 的系數(shù)矩陣 A， 形式如下： mnmmnn xxxxxxxxx ??????? ,,,。, 212222111211????????????????????????????????111111111111111111????????????m行 n行 第三章 運(yùn)輸問(wèn)題 ? 矩陣的元素均為 1或 0； ? 每一列只有兩個(gè)元素為 1，其余元素均為 0； ? 列向量 Pij =(0,… ， 0， 1， 0， …,0,1,0,…0) T，其中兩個(gè)元素 1分別處于第 i行和第 m+j行。 ? 將該矩陣分塊，特點(diǎn)是： 前 m行構(gòu)成 m個(gè)m n階矩陣 ，而且 第 k個(gè)矩陣只有第 k行元素全為 1，其余元素全為 0（ k=1， … ， m） ； 后 n行構(gòu)成 m個(gè) n階單位陣 。 第三章 運(yùn)輸問(wèn)題 ?????????????????????????00100100???ijijPx 的列向量i m+j jmi ee ????????????????????00100??ie其中 第三章 運(yùn)輸問(wèn)題 m + n 1 寫(xiě)出增廣矩陣 ?????????????????????????????????nmbbbaaaA1111111111111111112121????????????????mnmmnn xxxxxxxxx ??????? ,,,。, 212222111211第三章 運(yùn)輸問(wèn)題 證明系數(shù)矩陣 A及其增廣矩陣的秩都是 m+n1 ? 前 m行相加之和減去后 n行相加之和結(jié)果是零向量，說(shuō)明 m+n個(gè)行向量線性相關(guān)，因此 的秩小于 m+n； ？ AA因此 的秩恰好等于 m+n1，又 D本身就含于A中，故 A的秩也等于 m+n1 ? 由 的第二至 m+n行和前 n列及 對(duì)應(yīng)的列交叉處元素構(gòu)成 m+n1階方陣 D 非奇異； ？ A13121 , mxxx ?第三章 運(yùn)輸問(wèn)題 ?????????????????????????????????nmbbbaaaA1111111111111111112121????????????????mnmmnn xxxxxxxxx ??????? ,,,。, 212222111211第三章 運(yùn)輸問(wèn)題 01011111111111111??????????mD ）（按第一列展開(kāi)可以證明 ： m+n個(gè)約束方程中的任意 m+n1個(gè)都是線性無(wú)關(guān)的 。 第三章 運(yùn)輸問(wèn)題 三、運(yùn)輸問(wèn)題的求解方法 (1)、單純形法（為什么？） (2)、表上作業(yè)法 由于問(wèn)題的特殊形式而采用的更簡(jiǎn)潔、更方便的方法 第三章 運(yùn)輸問(wèn)題 一、運(yùn)輸問(wèn)題的表上作業(yè)法 :先設(shè)法給出一個(gè)初始方案 ,然后根據(jù)確定的判別準(zhǔn)則對(duì)初始方案進(jìn)行檢查、調(diào)整、改進(jìn)，直至求出最優(yōu)方案 (表上作業(yè)法和單純形法的求解思想完全一致，但是具體作法更加簡(jiǎn)捷 )。 第三章 運(yùn)輸問(wèn)題 (1)找出初始基本可行解 (初始調(diào)運(yùn)方案 ).常用的方法有最小元素法、元素差額法（ Vogel近似法）、左上角法。 (2)求檢驗(yàn)數(shù)并判斷是否得到最優(yōu)解，常用求檢驗(yàn)的方法有閉回路法和位勢(shì)法，假設(shè)目標(biāo)函數(shù)取最小，當(dāng)非基變量的檢驗(yàn)數(shù) σ ij全都非負(fù)時(shí)得到最優(yōu)解（對(duì)于 max Z有 σ ij≤0時(shí)最優(yōu)），若存在檢驗(yàn)數(shù) σ lk0，說(shuō)明還沒(méi)有達(dá)到最優(yōu)，轉(zhuǎn)第三步。 (3)確定換入變量和換出變量 ,找到新的基本可行解 .在表上用閉回路法調(diào)整 (運(yùn)量 ). (4)重復(fù) (2),(3),直到得到最優(yōu)解為止 . 第三章 運(yùn)輸問(wèn)題 ?表上作業(yè)法是單純形法在求解運(yùn)輸問(wèn)題的一種簡(jiǎn)便方法。 ?單純形法與表上作業(yè)法的關(guān)系： （ 1）找出初始基可行解 （ 2）求各非基變量的檢驗(yàn)數(shù) （ 3）判斷是否最優(yōu)解 計(jì)算表中空格檢驗(yàn)數(shù) 表上給出 m+n1個(gè)數(shù)字格 判斷方法相同 第三章 運(yùn)輸問(wèn)題 換基： （ 4）確定換入變量和換出變量找出新的基可行解。 （ 5）重復(fù)（ 2）、（ 3）直至求出最優(yōu)解。 表上調(diào)整（閉回路調(diào)整） （運(yùn)輸問(wèn)題必有最優(yōu)解） 停止 最優(yōu)解 ？ 是 否 第三章 運(yùn)輸問(wèn)題 . 例 2. 某公司經(jīng)銷甲產(chǎn)品 .它下設(shè)三個(gè)加工廠 .每日的產(chǎn)量分別是 :A1為 7噸 ,A2為 4噸 ,A3為 9噸 .該公司把這些產(chǎn)品分別運(yùn)往四個(gè)銷售點(diǎn) .各銷售點(diǎn)每日銷量為 :B1為 3噸 ,B2為 6噸 ,B3為 5噸 ,B4為 6噸 .已知從各工廠到各銷售點(diǎn)的單位產(chǎn)品的運(yùn)價(jià)見(jiàn) 表 35所示 .問(wèn)該公司應(yīng)如何調(diào)運(yùn)產(chǎn)品 ,在滿足各銷售點(diǎn)的需要量的前提下 ,使總運(yùn)費(fèi)最少 . 第三章 運(yùn)輸問(wèn)題 表 35信息表 3 11 1