第四章-運籌學運輸問題

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