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