第四章-運(yùn)籌學(xué)運(yùn)輸問(wèn)題

第四章運(yùn)輸問(wèn)題 第四章運(yùn)輸問(wèn)題 第1節(jié)運(yùn)輸問(wèn)題的數(shù)學(xué)模型第2節(jié)表上作業(yè)法第3節(jié)產(chǎn)銷不平衡的運(yùn)輸問(wèn)題及其求解方法第4節(jié)應(yīng)用問(wèn)題舉例 第1節(jié)運(yùn)輸問(wèn)題的數(shù)學(xué)模型 一 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題屬于線性規(guī)劃問(wèn)題 因?yàn)槠浼s束方程組的系數(shù)矩陣A具有特殊的結(jié)構(gòu) 所以專門介紹一種比單純形法更簡(jiǎn)便的求解方法 以節(jié)約計(jì)算時(shí)間和費(fèi)用 第1節(jié)運(yùn)輸問(wèn)題的數(shù)學(xué)模型 例1 某公司經(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à)如下表所示 問(wèn)該公司應(yīng)如何調(diào)運(yùn)產(chǎn)品 在滿足各銷點(diǎn)的需要量的前提下 使總運(yùn)費(fèi)為最少 二表合一 第1節(jié)運(yùn)輸問(wèn)題的數(shù)學(xué)模型 二 運(yùn)輸問(wèn)題的數(shù)學(xué)模型已知有m個(gè)生產(chǎn)地點(diǎn) 簡(jiǎn)稱產(chǎn)地 可供應(yīng)某種物資 其供應(yīng)量 產(chǎn)量 分別為 有n個(gè)銷售地點(diǎn) 簡(jiǎn)稱銷地 其需要量 銷量 分別為 從到運(yùn)輸單位物資的運(yùn)價(jià) 單位運(yùn)價(jià) 為 將這些數(shù)據(jù)表示在如下頁(yè)的兩個(gè)表中 問(wèn)應(yīng)如何調(diào)運(yùn) 在滿足各銷地銷量的情況下 使總的運(yùn)費(fèi)支出最少 第1節(jié)運(yùn)輸問(wèn)題的數(shù)學(xué)模型 產(chǎn)銷平衡表兩個(gè)表合二為一 單位運(yùn)價(jià)表 第1節(jié)運(yùn)輸問(wèn)題的數(shù)學(xué)模型 產(chǎn)銷平衡表單位運(yùn)價(jià)表 二表合一 第1節(jié)運(yùn)輸問(wèn)題的數(shù)學(xué)模型 例1 解 設(shè)xij為第i加工廠向第j銷售點(diǎn)的甲產(chǎn)品的供應(yīng)量 cij表示第i加工廠向第j銷售點(diǎn)供應(yīng)甲產(chǎn)品的單位運(yùn)費(fèi) 第1節(jié)運(yùn)輸問(wèn)題的數(shù)學(xué)模型 產(chǎn)銷平衡運(yùn)輸問(wèn)題的數(shù)學(xué)模型 設(shè)xij表示從產(chǎn)地Ai運(yùn)往銷地Bj的產(chǎn)品數(shù)量 對(duì)偶問(wèn)題 第1節(jié)運(yùn)輸問(wèn)題的數(shù)學(xué)模型 特征 1 決策變量 m n 2 約束方程 m n 都是等式約束 3 目標(biāo)函數(shù) 最小化 第1節(jié)運(yùn)輸問(wèn)題的數(shù)學(xué)模型 系數(shù)矩陣A 基變量數(shù)目 解的類型 第1節(jié)運(yùn)輸問(wèn)題的數(shù)學(xué)模型 4 約束方程組系數(shù)矩陣A A中只有數(shù)字0或1 A的每一列只有兩個(gè)非零元素1 第1節(jié)運(yùn)輸問(wèn)題的數(shù)學(xué)模型 6 基變量 m n 1 7 對(duì)于產(chǎn)銷平衡的運(yùn)輸問(wèn)題必有可行解和最優(yōu)解 第2節(jié)表上作業(yè)法 一 表上作業(yè)法的解題思路表上作業(yè)法的實(shí)質(zhì)是單純形法在求解運(yùn)輸問(wèn)題時(shí)的一種簡(jiǎn)化方法 屬于單純形法 又稱為運(yùn)輸單純形法 第2節(jié)表上作業(yè)法 二 表上作業(yè)法的特點(diǎn)表上作業(yè)法是一種迭代法用表上作業(yè)法求解運(yùn)輸問(wèn)題 直接在表上進(jìn)行 不必寫出數(shù)學(xué)模型 第2節(jié)表上作業(yè)法 三 表上作業(yè)法的解題步驟 一 找出初始基可行解 在產(chǎn)銷平衡表上找出 m n 1 個(gè)數(shù)字格 形成初始產(chǎn)銷平衡表方法 二 求非基變量檢驗(yàn)數(shù) 計(jì)算初始產(chǎn)銷平衡表中空格的檢驗(yàn)數(shù) 判別是否達(dá)到最優(yōu)解 如果已達(dá)到 停止計(jì)算 否則轉(zhuǎn)入3方法 三 確定換入變量和換出變量 找出新的基可行解方法 閉回路調(diào)整法 四 重復(fù) 二 三 直到求出最優(yōu)解說(shuō)明 以例1為例解釋表上作業(yè)法的解題步驟 第2節(jié)表上作業(yè)法 產(chǎn)銷平衡表單位運(yùn)價(jià)表 二表合一 最小元素法確定初始解 伏格爾法確定初始解 第2節(jié)表上作業(yè)法 表上作業(yè)法解題步驟 一 確定初始基可行解方法一 最小元素法1 基本思路從運(yùn)費(fèi)上考慮 優(yōu)先安排單位運(yùn)價(jià)最小的產(chǎn)地和銷地之間的運(yùn)輸業(yè)務(wù) 最大限度地滿足其產(chǎn)銷量 從而實(shí)現(xiàn) 就近供應(yīng) 第2節(jié)表上作業(yè)法 例2 用最小元素法找出例1的初始基可行解 第2節(jié)表上作業(yè)法 例2 解 初始產(chǎn)銷平衡表 閉回路法求檢驗(yàn)數(shù) 位勢(shì)法求檢驗(yàn)數(shù) 第2節(jié)表上作業(yè)法 2 求解步驟第一 從單位運(yùn)價(jià)表中找出最小運(yùn)價(jià) 有兩個(gè)或兩個(gè)以上的最小單位運(yùn)價(jià) 則任選其一 比較產(chǎn)量和銷量 產(chǎn)量 銷量 則劃去該運(yùn)價(jià)所在列 產(chǎn)量 銷量 則劃去該運(yùn)價(jià)所在行 并在初始產(chǎn)銷平衡表上填上相應(yīng)的數(shù)字 第二 從單位運(yùn)價(jià)表中未被劃去的運(yùn)價(jià)中再找最小運(yùn)價(jià) 重復(fù)第一 第二 直到單位運(yùn)價(jià)表中所有運(yùn)價(jià)都被劃去 并找出 m n 1 個(gè)數(shù)字格 第2節(jié)表上作業(yè)法 3 小結(jié) 1 在初始產(chǎn)銷平衡表上每填入一個(gè)數(shù)字 在單位運(yùn)價(jià)表上就劃去一行或一列 當(dāng)表中只剩一個(gè)元素時(shí) 在初始產(chǎn)銷平衡表上填數(shù)字時(shí) 在單位運(yùn)價(jià)表上同時(shí)劃去一行和一列 2 在單位運(yùn)價(jià)表上共劃去 m n 條直線 相當(dāng)于單位運(yùn)價(jià)表上所有cij都被劃去兩次 3 在初始產(chǎn)銷平衡表上填了 m n 1 個(gè)數(shù)字格 每行數(shù)字之和 該行產(chǎn)量 每列數(shù)字之和 該列銷量 第2節(jié)表上作業(yè)法 例3 用最小元素法求出下述運(yùn)輸問(wèn)題的初始基可行解 表上作業(yè)法求解例3 第2節(jié)表上作業(yè)法 例3 解 初始基可行解 出現(xiàn)退化解 第2節(jié)表上作業(yè)法 例4 判斷下表給出的運(yùn)輸方案能否作為用 最小元素法 求解出的初始基可行解 第2節(jié)表上作業(yè)法 表上作業(yè)法解題步驟 一 確定初始基可行解方法二 伏格爾法1 基本思路按某一最小單位運(yùn)價(jià)優(yōu)先安排物品調(diào)運(yùn)時(shí) 可能導(dǎo)致其他產(chǎn)銷點(diǎn)不得不采用很高的單位運(yùn)價(jià)進(jìn)行運(yùn)輸 從而使整個(gè)運(yùn)輸費(fèi)用增加 對(duì)每一個(gè)產(chǎn)地或銷地 找出最小單位運(yùn)價(jià)和次小單位運(yùn)價(jià) 求二者之差 若差值不大 當(dāng)不能按最小單位運(yùn)價(jià)安排運(yùn)輸時(shí)造成的運(yùn)費(fèi)損失不大 反之 若二者之差很大 不按最小單位運(yùn)價(jià)組織運(yùn)輸就會(huì)造成很大損失 所以應(yīng)盡量按最小單位運(yùn)價(jià)安排運(yùn)輸 第2節(jié)表上作業(yè)法 例5 用伏格爾法找出例1的初始基可行解 第2節(jié)表上作業(yè)法 例5 解 初始產(chǎn)銷平衡表 閉回路法求檢驗(yàn)數(shù) 位勢(shì)法求檢驗(yàn)數(shù) 第2節(jié)表上作業(yè)法 2 求解步驟第一 在單位運(yùn)價(jià)表中分別計(jì)算各行和各列的最小運(yùn)價(jià)與次小運(yùn)價(jià)的差額 并填在該表的最右列和最下行 第二 從行或列差額中選出最大者 有兩個(gè)或兩個(gè)以上的最大差額 則選擇差額所在行 或列 中的最小單位運(yùn)價(jià) 選擇它所在行或列中的最小運(yùn)價(jià) 按照最小元素法確定初始基可行解 第三 對(duì)單位運(yùn)價(jià)表中未被劃去的運(yùn)價(jià)再計(jì)算各行和各列的最小運(yùn)價(jià)與次小運(yùn)價(jià)的差額 并仍填入該表的最右列和最下行 重復(fù)第二 三 直至給出初始基可行解為止 即找出 m n 1 個(gè)數(shù)字格 第2節(jié)表上作業(yè)法 3 小結(jié) 1 伏格爾法和最小元素法僅在確定產(chǎn)銷關(guān)系的原則上不同 其余步驟都相同 伏格爾法是在最小元素法的基礎(chǔ)上改進(jìn)的一種方法 2 伏格爾法給出的初始基可行解比用最小元素法給出的初始基可行解更接近最優(yōu)解 伏格爾法給出的解的目標(biāo)函數(shù)值比最小元素法給出的解的目標(biāo)函數(shù)值小 3 伏格爾法得出的初始基可行解常作為運(yùn)輸問(wèn)題最優(yōu)解的近似解 作業(yè)4 1 作業(yè)4 1 1 用最小元素法找出下述運(yùn)輸問(wèn)題的初始基可行解 2 找出下述運(yùn)輸問(wèn)題的近似最優(yōu)解 其中M為任意大正數(shù) 表示含義為從A4到B4不存在運(yùn)輸路線 第2節(jié)表上作業(yè)法 表上作業(yè)法解題步驟 二 求檢驗(yàn)數(shù) 判別最優(yōu)解基本思路計(jì)算空格 非基變量 的檢驗(yàn)數(shù) 運(yùn)輸問(wèn)題的目標(biāo)函數(shù)要求實(shí)現(xiàn)最小化 當(dāng)所有檢驗(yàn)數(shù) 0時(shí) 所得的解是最優(yōu)解 否則要進(jìn)行解的改進(jìn) 第2節(jié)表上作業(yè)法 表上作業(yè)法解題步驟 二 求檢驗(yàn)數(shù) 判別最優(yōu)解方法一 閉回路法例6 用閉回路法求例2所得的初始基可行解的檢驗(yàn)數(shù) 第2節(jié)表上作業(yè)法 例6 解 檢驗(yàn)數(shù)表 第2節(jié)表上作業(yè)法 1 檢驗(yàn)數(shù)的含義檢驗(yàn)數(shù)表示變化的運(yùn)費(fèi) 即 若某空格 Ai Bj 的檢驗(yàn)數(shù) 0 表示將該空格變?yōu)閿?shù)字格使運(yùn)輸費(fèi)用減少 則當(dāng)前這個(gè)解不是最優(yōu)解 反之 若所有空格的檢驗(yàn)數(shù)都 0 表示不管怎樣變換 都使運(yùn)輸費(fèi)用增加 則目標(biāo)函數(shù)已無(wú)法改進(jìn) 當(dāng)前這個(gè)解就是最優(yōu)解 第2節(jié)表上作業(yè)法 2 求解步驟第一 在初始產(chǎn)銷平衡表上 從每一空格出發(fā)找一條閉回路 以某空格為起點(diǎn) 用水平或垂直線向前畫 碰到一數(shù)字格轉(zhuǎn)90 有些情況下也可以不改變方向 然后繼續(xù)前進(jìn) 直到回到起始空格為止 第二 在一閉回路上 令某空格取值為 1 表示增加的運(yùn)量 然后變化相應(yīng)數(shù)字格的值 并計(jì)算該閉回路上運(yùn)費(fèi)的變化值 即為該空格的檢驗(yàn)數(shù) 填入檢驗(yàn)數(shù)表 第2節(jié)表上作業(yè)法 例7 用閉回路法求例5所得的初始基可行解的檢驗(yàn)數(shù) 第2節(jié)表上作業(yè)法 例7 解 檢驗(yàn)數(shù)表 第2節(jié)表上作業(yè)法 3 小結(jié) 1 閉回路的頂點(diǎn) 除出發(fā)點(diǎn)為空格外 其他均為數(shù)字格 2 每個(gè)空格唯一存在一條閉回路 3 對(duì)于產(chǎn)銷點(diǎn)過(guò)多的運(yùn)輸問(wèn)題 空格的數(shù)目很大 計(jì)算檢驗(yàn)數(shù)很繁瑣 第2節(jié)表上作業(yè)法 表上作業(yè)法解題步驟 二 求檢驗(yàn)數(shù) 判別最優(yōu)解方法二 位勢(shì)法1 基本思路 第2節(jié)表上作業(yè)法 原問(wèn)題對(duì)偶問(wèn)題 第2節(jié)表上作業(yè)法 2 求解步驟第一 仿照初始產(chǎn)銷平衡表做一個(gè)表 在對(duì)應(yīng)的數(shù)字格處填入單位運(yùn)價(jià)cij 第二 在表的最右列和最下行分別增加一列ui和一行vj 使表中的單位運(yùn)價(jià)等于它所在行和列的ui與vj之和 求出所有的ui和vj 并填寫在表中 第三 計(jì)算各空格的檢驗(yàn)數(shù) 填入檢驗(yàn)數(shù)表 第2節(jié)表上作業(yè)法 例8 用位勢(shì)法求例2所得的初始基可行解的檢驗(yàn)數(shù) 第2節(jié)表上作業(yè)法 例8 解 檢驗(yàn)數(shù)表 第2節(jié)表上作業(yè)法 例9 用位勢(shì)法求例5所得的初始基可行解的檢驗(yàn)數(shù) 第2節(jié)表上作業(yè)法 例9 解 檢驗(yàn)數(shù)表 第2節(jié)表上作業(yè)法 2 小結(jié)當(dāng)運(yùn)輸問(wèn)題的產(chǎn)地和銷地很多時(shí) 空格的數(shù)目很大 采用位勢(shì)法計(jì)算檢驗(yàn)數(shù)簡(jiǎn)便 第2節(jié)表上作業(yè)法 三 確定換入和換出變量 找出新的基可行解 直至求出最優(yōu)解方法 閉回路調(diào)整法1 基本思想在初始產(chǎn)銷平衡表中 選取檢驗(yàn)數(shù)為負(fù)的所有空格中的最小者作為換入格 以對(duì)應(yīng)空格為出發(fā)點(diǎn)畫出閉回路 在經(jīng)過(guò)的數(shù)字格中選擇 1 的最小者 對(duì)應(yīng)的數(shù)字格為換出格 然后對(duì)閉回路上各頂點(diǎn)的數(shù)據(jù)進(jìn)行調(diào)整 得到另一個(gè)更好的基可行解 第2節(jié)表上作業(yè)法 2 求解步驟第一 確定換入格 在初始產(chǎn)銷平衡表上 最小的負(fù)檢驗(yàn)數(shù)所在的空格為換入格 有兩個(gè)或兩個(gè)以上的最小者 則任選其一 并以此空格為出發(fā)點(diǎn) 作一閉回路 第二 確定換出格 選擇閉回路上標(biāo)記為 1 的數(shù)字格中的最小者 記做 則該數(shù)字格為換出格 第三 調(diào)整 將閉回路上標(biāo)記為 1 的數(shù)字格 加 標(biāo)記為 1 的數(shù)字格 減 得到新的基可行解 第四 采用閉回路法或位勢(shì)法求空格的檢驗(yàn)數(shù) 若所有檢驗(yàn)數(shù)都 0 則獲得最優(yōu)解 否則重復(fù)第一 第三 直至求出最優(yōu)解 表上作業(yè)法求解例1 第2節(jié)表上作業(yè)法 最優(yōu)解檢驗(yàn)數(shù)表z 85 無(wú)窮多 多重 最優(yōu)解 第2節(jié)表上作業(yè)法 例10 用表上作業(yè)法求解例3 第2節(jié)表上作業(yè)法 最優(yōu)解檢驗(yàn)數(shù)表z 61 唯一最優(yōu)解 第2節(jié)表上作業(yè)法 四 表上作業(yè)法的解1 唯一最優(yōu)解所有空格 非基變量 的檢驗(yàn)數(shù)大于0 該運(yùn)輸問(wèn)題有唯一最優(yōu)解 第2節(jié)表上作業(yè)法 最優(yōu)解檢驗(yàn)數(shù)表z 61 例3最優(yōu)解的情況 第2節(jié)表上作業(yè)法 2 無(wú)窮多 多重 最優(yōu)解某個(gè)空格 非基變量 的檢驗(yàn)數(shù)為0時(shí) 該運(yùn)輸問(wèn)題有無(wú)窮多 多重 最優(yōu)解 在已求得一個(gè)最優(yōu)解的表中 以這樣的空格出發(fā)做閉回路重新進(jìn)行調(diào)整 得到另一個(gè)最優(yōu)解 第2節(jié)表上作業(yè)法 例1最優(yōu)解的情況無(wú)窮多最優(yōu)解檢驗(yàn)數(shù)表z 85 第2節(jié)表上作業(yè)法 例1最優(yōu)解的情況無(wú)窮多最優(yōu)解檢驗(yàn)數(shù)表z 85 第2節(jié)表上作業(yè)法 3 退化解某個(gè)數(shù)字格 基變量 為0時(shí) 該運(yùn)輸問(wèn)題為退化解 退化解出現(xiàn)的情況 確定初始解的各供需關(guān)系時(shí) 若在某格填入某數(shù)字后 出現(xiàn)該處的供應(yīng)量與需求量相等 用閉回路調(diào)整法調(diào)整時(shí) 在閉回路上出現(xiàn)兩個(gè)或兩個(gè)以上的具有 1 標(biāo)記的相等的最小值 第2節(jié)表上作業(yè)法 例11 已知某初始產(chǎn)銷平衡表 如下表 空格A2B4格的檢驗(yàn)數(shù) 0 其余空格的檢驗(yàn)數(shù)均 0 試確定換入 換出格 求出新的基可行解 第2節(jié)表上作業(yè)法 例11 解 下一個(gè)基可行解 第2節(jié)表上作業(yè)法 五 表上作業(yè)法計(jì)算步驟框圖 第2節(jié)表上作業(yè)法 例12 已知三個(gè)產(chǎn)地A1 A2 A3 四個(gè)銷地B1 B2 B3 B4的產(chǎn)銷量即單位運(yùn)價(jià)如下表所示 求使總運(yùn)費(fèi)最少的調(diào)運(yùn)方案 第2節(jié)表上作業(yè)法 例12 解 無(wú)窮多最優(yōu)解 退化解z 6000 作業(yè)4 2 作業(yè)4 2 用表上作業(yè)法求解下列運(yùn)輸問(wèn)題的最優(yōu)解 1 要求采用伏格爾法 位勢(shì)法求解2 要求采用伏格爾法 閉回路法求解 第3節(jié)產(chǎn)銷不平衡的運(yùn)輸問(wèn)題及其求解方法 一 求解思路總產(chǎn)量不等于總銷量 為使用表上作業(yè)法求解 將產(chǎn)銷不平衡運(yùn)輸問(wèn)題轉(zhuǎn)化為產(chǎn)銷平衡運(yùn)輸問(wèn)題 第3節(jié)產(chǎn)銷不平衡的運(yùn)輸問(wèn)題及其求解方法 二 求解方法1 總產(chǎn)量 總銷量 第3節(jié)產(chǎn)銷不平衡的運(yùn)輸問(wèn)題及其求解方法 數(shù)學(xué)模型 第3節(jié)產(chǎn)銷不平衡的運(yùn)輸問(wèn)題及其求解方法 解題思路 為借助于產(chǎn)銷平衡的表上作業(yè)法求解 增加一個(gè)假想的銷地Bn 1 由于實(shí)際上它不存在 因而由產(chǎn)地Ai i 1 2 m 調(diào)運(yùn)到這個(gè)假想銷地的物品數(shù)量xi n 1 就是就地存貯在Ai的物品數(shù)量 就地存貯的物品未經(jīng)運(yùn)輸 所以其單位運(yùn)價(jià)ci n 1 0 i 1 2 m 第3節(jié)產(chǎn)銷不平衡的運(yùn)輸問(wèn)題及其求解方法 第3節(jié)產(chǎn)銷不平衡的運(yùn)輸問(wèn)題及其求解方法 數(shù)學(xué)模型 第3節(jié)產(chǎn)銷不平衡的運(yùn)輸問(wèn)題及其求解方法 數(shù)學(xué)模型變化 第3節(jié)產(chǎn)銷不平衡的運(yùn)輸問(wèn)題及其求解方法 2 總產(chǎn)量 總銷量 第3節(jié)產(chǎn)銷不平衡的運(yùn)輸問(wèn)題及其求解方法 數(shù)學(xué)模型 第3節(jié)產(chǎn)銷不平衡的運(yùn)輸問(wèn)題及其求解方法 解題思路 為借助于產(chǎn)銷平衡的表上作業(yè)法求解 增加一個(gè)假想的產(chǎn)地Am 1 由于實(shí)際上它不存在 因而由它發(fā)往各個(gè)銷地的物品數(shù)量xm 1 j j 1 2 n 就是各銷地Bj所需物品的欠缺額 欠缺的物品未經(jīng)運(yùn)輸 所以其單位運(yùn)價(jià)cm 1 j 0 j 1 2 n 第3節(jié)產(chǎn)銷不平衡的運(yùn)輸問(wèn)題及其求解方法 第3節(jié)產(chǎn)銷不平衡的運(yùn)輸問(wèn)題及其求解方法 數(shù)學(xué)模型 第3節(jié)產(chǎn)銷不平衡的運(yùn)輸問(wèn)題及其求解方法 數(shù)學(xué)模型變化 第3節(jié)產(chǎn)銷不平衡的運(yùn)輸問(wèn)題及其求解方法 例13 用表上作業(yè)法求解下述運(yùn)輸問(wèn)題的最優(yōu)解 第3節(jié)產(chǎn)銷不平衡的運(yùn)輸問(wèn)題及其求解方法 例13 解 產(chǎn)銷不平衡 產(chǎn)銷平衡 第3節(jié)產(chǎn)銷不平衡的運(yùn)輸問(wèn)題及其求解方法 無(wú)窮多最優(yōu)解z 35 第3節(jié)產(chǎn)銷不平衡的運(yùn)輸問(wèn)題及其求解方法 小結(jié)采用最小元素法或伏格爾法求初始基可行解時(shí) 由于虛擬產(chǎn)地或銷地不存在 所以盡管二者的單位運(yùn)價(jià)ci n 1 0或