作業研究 第五章 運輸與指派問題 林吉仁 著 高立圖書公司出版.

Slides:



Advertisements
Similar presentations
如何制定运动处方 一、学习提示与要点 二、运动处方概念及原理 三、健身运动处方的内容 四、运动处方示例.
Advertisements

不定積分 不定積分的概念 不定積分的定義 16 不定積分的概念 16.1 不定積分的概念 以下是一些常用的積分公式。
大綱 1. 三角函數的導函數. 2. 反三角函數的導函數. 3. 對數函數的導函數. 4. 指數函數的導函數.
變數與函數 大綱 : 對應關係 函數 函數值 顧震宇 台灣數位學習科技股份有限公司. 對應關係 蛋餅飯糰土司漢堡咖啡奶茶 25 元 30 元 25 元 35 元 25 元 20 元 顧震宇 老師 台灣數位學習科技股份有限公司 變數與函數 下表是早餐店價格表的一部分: 蛋餅 飯糰 土司 漢堡 咖啡 奶茶.
第十章 分 配 理 論 INDEX 第一節 所得分配的基本概念 第二節 生產要素的需求 第三節 分配的邊際生產力理論
中二數學 第五章 : 二元一次方程 二元一次方程的圖像.
獨占與管制 張清溪 / 台大經濟系.
第四章 數列與級數 4-1 等差數列與級數 4-2 等比數列與級數 4-3 無窮等比級數 下一頁 總目錄.
絕對不等式 課堂練習2 (算幾不等式).
5.1 自然對數函數:微分 5.2 自然對數函數:積分 5.3 反函數 5.4 指數函數:微分與積分 5.5 一般底數的指數函數和應用 5.6 反三角函數:微分 5.7 反三角函數:積分 5.8 雙曲函數.
物流运输管理.
LINGO.
Linear Programming: Introduction and Duality
第2章 线性规划与单纯形法 第3章 对偶理论与灵敏度分析 第4章 运输问题 第5章 目标规划
Chapter 2 線性規劃.
作業研究 第九章 專案管理 林吉仁 著 高立圖書公司出版.
Chap5 Graph.
Chapter 4 網路模型 Network Models.
4B冊 認識公倍數和最小公倍數 公倍數和最小公倍數的關係.
9.1 直線之方程 附加例題 1 附加例題 2 附加例題 3 附加例題 4 © 文達出版 (香港 )有限公司.
Chapter 7 運輸問題與指派問題.
元素替换法 ——行列式按行(列)展开(推论)
(Circular Linked Lists)
第3章 整数线性规划 3.1 整数规划问题举例 3.2 割平面法.
以下這個謎題無法透過宮摒除法完成解題。 但可透過「區塊宮摒除法」或「行列摒除法」完成 By TTHsieh
Python Final Project 組員:楊承叡、謝谷松.
1.3 在整除性問題之應用 附加例題 3 © 文達出版 (香港 )有限公司.
Chap3 Linked List 鏈結串列.
第一章 直角坐標系 1-1 數系的發展.
網路遊戲版 幸福農場168號.
Ch2多項式函數 2-2 多項式的運算與應用 影音錄製:陳清海老師 資料提供:龍騰文化事業股份有限公司.
Ch2多項式函數 2-2 多項式的運算與應用 影音錄製:陳清海老師 資料提供:龍騰文化事業股份有限公司.
作業研究 第五章 運輸與指派問題 林吉仁 著 高立圖書公司出版.
15.3 極大與極小 附加例題 5 附加例題 6 © 文達出版 (香港 )有限公司.
基本電學 資訊科杜文淵老師.
學習單元:N6 數的性質 學習單位:N6-3 用短除法求H.C.F. 和 L.C.M. 學習重點 : 1. 複習因數分解法求
15.5 最大值和最小值 的問題 附加例題 9 附加例題 10 © 文達出版 (香港 )有限公司.
Definition of Trace Function
线 性 代 数 厦门大学线性代数教学组 2019年4月24日6时8分 / 45.
小學四年級數學科 8.最大公因數.
第八章補充 運輸模型.
挑戰C++程式語言 ──第8章 進一步談字元與字串
圓的定義 在平面上,與一定點等距的所有點所形成的圖形稱為圓。定點稱為圓心,圓心至圓上任意一點的距離稱為半徑,「圓」指的是曲線部分的圖形,故圓心並不在圓上.
蕭志明 老師 Algorithm(演算法) Ext:6779
蕭志明 老師 Algorithm(演算法) /FB:
運輸與指派問題 Transportation and Assignment Problems
反矩陣與行列式 東海大學物理系‧數值分析.
第3章 运 输 问 题 3 内容提要  运输问题模型的特点  产销平衡运输问题的表上作业法  产销不平衡运输问题的转化
例題 1. 多項式的排列 1-2 多項式及其加減法 將多項式 按下列方式排列: (1) 降冪排列:______________________ (2) 升冪排列:______________________ 排列 降冪:次數由高至低 升冪;次數由低至高.
Chapter 9 慣性矩 9-1 面積慣性矩 9-2 平行軸原理 9-3 組合面積之慣性矩 9-4 迴轉半徑 9-5 質量慣性矩
10328: Coin Toss ★★★☆☆ 題組:Problem Set Archive with Online Judge
1757: Secret Chamber at Mount Rushmore
13194: DPA Number II ★★☆☆☆ 題組:Problem Set Archive with Online Judge
10599: Robots(II) ★★★★☆ 題組:Problem Set Archive with Online Judge
非負矩陣分解法介紹 報告者:李建德.
線性規劃的其他演算法 Special Simplex Method
2.1 一元一次不等式 定 義 設a、b為兩個實數。.
第十三章 彩色影像處理.
在直角坐標平面上兩點之間 的距離及平面圖形的面積
All Sources Shortest Path The Floyd-Warshall Algorithm
ABAP Basic Concept (2) 運算子 控制式與迴圈 Subroutines Event Block
10303: How Many Trees? ★★☆☆☆ 題組:Contest Archive with Online Judge
Chapter 4 Multi-Threads (多執行緒).
11621 : Small Factors ★★☆☆☆ 題組:Problem Set Archive with Online Judge
17.1 相關係數 判定係數:迴歸平方和除以總平方和 相關係數 判定係數:迴歸平方和除以總平方和.
ABC ( )已知 ,則下列哪些是x6-7x5-8x4 的因 式?(複選) (A) x+1 (B) 2x+2 (C) x3(x+1)
Chapter 16 動態規劃.
第三章 比與比例式 3-1 比例式 3-2 連比例 3-3 正比與反比.
ABAP Basic Concept (2) 運算子 控制式與迴圈 Subroutines Event Block
Presentation transcript:

作業研究 第五章 運輸與指派問題 林吉仁 著 高立圖書公司出版

5-1運輸問題 運輸問題是特殊結構的線性規劃問題。但一般並不採用線性規劃單體法來求解,而有其他更有效率的演算法。 林吉仁著 5-1運輸問題 運輸問題是特殊結構的線性規劃問題。但一般並不採用線性規劃單體法來求解,而有其他更有效率的演算法。 若有數個供給點以及數個需求點,而欲分配各供給點之供給量以滿足各需求點的需求量,而且使運輸總成本最小,即是所謂的「運輸問題」(Transportation Problem)

林吉仁著 標準運輸問題 (供需平衡) 有 m +n 1 個為基變數方格

林吉仁著 運輸問題之線性規劃模式 若ai、bj均為整數,必有xij均為整數最佳解

5-1-2 運輸單體法 求解運輸問題多採運輸單體法,直接在表格上運算。 運輸簡算法的解法邏輯是起始規則、運算規則、停止規則。 林吉仁著 5-1-2 運輸單體法 求解運輸問題多採運輸單體法,直接在表格上運算。 運輸簡算法的解法邏輯是起始規則、運算規則、停止規則。 起始規則:介紹 (1)西北角法;(2)最小成本法;(3)佛格法 運算規則與停止規則:介紹 (1)階石法,(2)修正分配法(MODI法) 運輸單體法最常採佛格法搭配MODI法

起始規則之「西北角法」 西北角法是求運輸問題起始解最簡單的方法,但因未將單位成本納入考慮,所得結果通常較差。 林吉仁著 起始規則之「西北角法」 西北角法是求運輸問題起始解最簡單的方法,但因未將單位成本納入考慮,所得結果通常較差。 西北角法利用運輸單體表中西北角方格的最大分配量來求出起始解。自 x11 方格開始  若 min(S1 , D1)= S1,令 x11 = S1,刪去第一列,並以 D1x11 為第一行的剩餘需求量。若 min(S1 , D1)= S1,令 x11 = S1,刪去第一列,並以 D1x11 為第一行的剩餘需求量。  若 min(S1 , D1)= D1,令 x11 = D1,刪去第一行,並以 S1  x11 為第一列的剩餘供給量。

分配 x11 後,在剩下的方格中,仿上面的運算,反覆進行西北角方格數量的分配,直到無剩餘方格為止,即可得一可行起始基解。 林吉仁著 分配 x11 後,在剩下的方格中,仿上面的運算,反覆進行西北角方格數量的分配,直到無剩餘方格為止,即可得一可行起始基解。 設 Si、Dj 分別代表剩餘供給量與剩餘需求量,當 min(Si , Dj)= Si= Dj 時;表示將有退化解 產生,為了避免少了一個基變數方格,雖填入最大分配量後,列、行的剩餘量均為0,但勿同時將對應列、行均刪去,應該僅刪去列或僅刪去行。又當 min(Si , Dj)= 0 時,仍須填入0表示該方格的 ( 退化 ) 分配量,以區別基變數方格與非基變數方格。

林吉仁著 例題5-1

解: ∵ 本題 m = 3 , n = 4,∴ 應有 m +n 1= 6 個基變數方格。 林吉仁著 解: ∵ 本題 m = 3 , n = 4,∴ 應有 m +n 1= 6 個基變數方格。 以下我們將以打叉 () 代表刪去該列 ( 或行 )

林吉仁著

林吉仁著

林吉仁著

快速「西北角法」 自 x11 方格開始; (1)若已無剩餘供給量時,往下移一方格; (2)若是已無剩餘需求量,往右移一方格。 記憶: 林吉仁著 快速「西北角法」 自 x11 方格開始; (1)若已無剩餘供給量時,往下移一方格; (2)若是已無剩餘需求量,往右移一方格。 記憶: 列無剩餘,重找一列 → 下移; 行無剩餘,重找一行 → 右移 當遇有退化解時,處理方式同前所述

林吉仁著 例題5-2 以下是以西北角法求得退化運輸問題之起始解 (單位成本省略)的問題與解答,請自行參考練習

起始規則之「最小成本法 」 最小成本法 (Least cost rule) 所選的基變數方格是 ( 未刪去 ) 方格中的單位成本最小方格。 林吉仁著 起始規則之「最小成本法 」 最小成本法 (Least cost rule) 所選的基變數方格是 ( 未刪去 ) 方格中的單位成本最小方格。 如果最小成本方格不只一個可任取其一 當遇有退化解產生時,理論上可任選刪去列或行,但通常是刪去成本較高者 其他處理方式均同西北角法 最小成本法因考慮了單位成本,通常可獲得比西北角法更好的起始解,即總運輸成本較小

林吉仁著 例題5-3

林吉仁著 解:

林吉仁著

林吉仁著

起始規則之「佛格法」 佛格法 (VAM) 又稱差額法 林吉仁著 起始規則之「佛格法」 佛格法 (VAM) 又稱差額法 佛格法是先算出每列、每行未刪去方格中最小的兩單位成本的差額,然後選出具最大差額的列(或行),以該列(或行)的最小成本方格為基變數方格,分配其量,刪去該列(或行)。反覆進行 當末尾僅存一列( 或行 )的方格時,則採最小成本法。當最大差額不只一個,可任取其一。 退化解的處理亦同西北角法、最小成本法

林吉仁著 例題5-4

林吉仁著 解:

林吉仁著

林吉仁著

林吉仁著 運算規則與停止規則 之「階石法」 1. 每一非基變數恰對應一條閉回路。閉回路是指。由非基變數方格出發,踩著基變數方格(階石),並以階石為轉角點,沿水平─鉛直─水平─ 鉛直…的線段前進,回到原來的非基變數方格 2. 每一非基變數方格也對應一個邊際成本Qij。而Qij是閉回路上正負相間單位成本的和。 即 Qij = cij cij*+ci’j*  …

3. 求出所有非基變數方格的Qij 4. 若所有Qij0則已達最佳解,否則到步驟 5. 林吉仁著 3. 求出所有非基變數方格的Qij 4. 若所有Qij0則已達最佳解,否則到步驟 5. 5. 以Qij最小值方格為調入變數,並求出其閉回路,再設定調出變數與分配調整值,而修正分配得到一組新而更佳的基解。回到步驟 2. =min(xij*,…) ;(i,j*)閉回路奇數步方格

林吉仁著 例題5-5

林吉仁著 解:

林吉仁著 例題5-6 請以例題5-3的基解為起始(重列如下),以階石法求出該問題的最佳解

林吉仁著 解:

林吉仁著 解:

運算規則與停止規則 之「MODI法」 1. 已得起始解(利用佛格法)。 2. 以 ui+vj=cij 求出所有ui 、vj 值 林吉仁著 運算規則與停止規則 之「MODI法」 1. 已得起始解(利用佛格法)。 2. 以 ui+vj=cij 求出所有ui 、vj 值 3. 以Qij=cijui vj求出所有非基變數方格的Qij 4. 若所有Qij0則已達最佳解,否則到步驟 5. 5. 以Qij最小值方格為調入變數,並求出其閉回路,再設定調出變數與分配調整值,而修正分配得到一組新而更佳的基解。回到步驟 2.

林吉仁著 例題5-7

林吉仁著 解:

林吉仁著

林吉仁著

林吉仁著

5-1-3特殊運輸問題 運輸問題的各種特殊情形之處理 退化解:指有基變數為0,影響求解效率 林吉仁著 5-1-3特殊運輸問題 運輸問題的各種特殊情形之處理 退化解:指有基變數為0,影響求解效率 多重最佳解:Qij0單一最佳解;  Qij0多重最佳解 限制運送:令該cij= M ()

林吉仁著 5-1-3-4最大化問題 當運輸問題中的單位成本 cij 換成單位利潤 pij 時,就成了最大化問題了。求解最大化問題只要先將 pij改成pij,即可按一般運輸單體法加以求解。

林吉仁著 例題5-8

林吉仁著 解: 因目標為最大化,先將各單位利潤 pij 乘上負號 (其餘解題過程請見課本)

5-1-3-5不平衡運輸問題 當總供給量與總需求量不相等時,稱為不平衡運輸問題 林吉仁著 5-1-3-5不平衡運輸問題 當總供給量與總需求量不相等時,稱為不平衡運輸問題 求解時,總供給量大於總需求量  ,虛設一個需求量  的終點;總需求量大於總供給量  ,虛設一個供給量  的起點 多虛設出的方格單位運輸成本一般為0。若不欲某些方格有分配量,可令其單位成本為 M 以一般運輸單體法加以求解即可 虛設起點所供給的量,表供應不足;虛設終點的量,表供應過剩

林吉仁著 例題5-9

解: 林吉仁著

林吉仁著

林吉仁著

林吉仁著 例題5-10 彈性需求量問題

解: 林吉仁著

林吉仁著 例題5-11應用運輸問題解生產排程 某製鞋廠預測未來三個月的需求量如下:第一個月需求量200,第二個月需求量310,第三個月需求量240。在正常工時下每雙鞋的成本為7元,加工工時下每雙鞋的成本為11元,而每個月正常工時的生產上限是200雙鞋子,加工工時的生產上限是100雙鞋子。又每雙鞋子每個月的庫存成本是2元。請利用平衡運輸模式描述此問題 ( 不須求解 ),使得滿足未來三個月的需求量下,總成本最小。

林吉仁著 解:

5-1-3-8 轉運問題 轉運問題(Transshipment Problem)是運輸問題的擴充。 林吉仁著 5-1-3-8 轉運問題 轉運問題(Transshipment Problem)是運輸問題的擴充。 在運輸問題節點只單純有貨物流出(供給)、或只有貨物流入(需求),但如果節點既有貨物流出、也有貨物流入,此節點稱為轉運點,而問題變成轉運問題了。 沒有供給量,沒有需求量的轉運點稱為純轉運點。

建構轉運問題模式 建立轉運供需表的步驟如下: 1. 建立平衡的運輸供需表,令 。 2. 增設扮演起點角色的點於列;增設扮演終點角色的點於行。 林吉仁著 建構轉運問題模式 建立轉運供需表的步驟如下: 1. 建立平衡的運輸供需表,令 。 2. 增設扮演起點角色的點於列;增設扮演終點角色的點於行。 3. 填入各路徑的單位成本。本站到本站的單位成本為 0。 4. 可供轉運的起點供給量加T;可供轉運的終點需求量也加T ;而所有新增的點其量 ( 無論是供給量或需求量 ) 均為T 。   建立了轉運供需表即可視為運輸問題加以求解。

林吉仁著 例題5-12

林吉仁著 解: 列出轉運供需表並解得最佳解如下: ∴ 最低總運輸成本 391 並得下運輸簡圖

林吉仁著 運輸簡圖 (簡圖中不考慮表中本站至本站的運送量)

5-2指派問題 指派問題是特殊結構的LP問題、0-1規劃問題、運輸問題。 林吉仁著 5-2指派問題 指派問題是特殊結構的LP問題、0-1規劃問題、運輸問題。 假設有 n 件不同工作,n 位人員。而所謂指派問題 (Assignment Problem) 就是研究如何將 n 件工作以一對一方式分派給 n 位人員,而使得總成本最小 ( 或總利潤最大 ) 解指派問題常用匈牙利法

5-2-1匈牙利法(目標min) 匈牙利法步驟: 列出成本矩陣。若是利潤矩陣 ( 求 Max),則每一元素均乘負號 林吉仁著 5-2-1匈牙利法(目標min) 匈牙利法步驟: 列出成本矩陣。若是利潤矩陣 ( 求 Max),則每一元素均乘負號 檢查是否為方陣。若非方陣,適當地加入一 ( 或數 ) 列或行,以形成方陣 ( 設 nn)。而新加入元素值均為0,除非有不欲被指派的元素 成本方陣中,各列減該列最小值,接著又各行減該行最小值,得簡化方陣

利用簡化方陣中的0元素來分派,已指派的0元素以□框起來。指派時的原則有: 林吉仁著 利用簡化方陣中的0元素來分派,已指派的0元素以□框起來。指派時的原則有: 自僅 ( 剩 ) 有一個0的列或行開始,框起該0元素,並刪去該0的所在列與所在行。反覆進行。 若每一列、行均有一個以上的0元素,則自有 ( 剩 ) 最少0元素的列或行任框一個0,再回到 (1)。 指派時,作者建議應自第1列,第2列,… 最後一列,第1行,… 最後一行,反覆地、有系統地來找尋可指派的0元素。而這也正是可指派數的最大值。

若 p = n,則已達最佳解。並可對照原始成本矩陣求得最小總成本 若 p  n,則以最少直線數 ( 即 p 條直線 ) 劃去簡化方陣中所有0元素。所謂直線是指鉛直線與水平線,不包含斜線 找出“最少線數”劃去所有的0。步驟: (a)無 的列打勾 () (b)有打勾列,其0所在行打勾; (c)有打勾行,其 所在列打勾 (d)重覆 (b)、(c) 直到沒有新的打勾行、列為止 (e)沒有打勾的列劃橫線,有打勾的行劃縱線, 即得劃去所有0的最少線數 林吉仁著

※有時候,若不欲 (i, j) 元素被指派,只要將其成本設為大 M( 利潤設為 M ) 即可 林吉仁著 若未被劃去的元素中最小值為 a,則 (1)未被劃去者減 a (2)被劃一次者不變 (3)被劃兩次者加 a 可得新的簡化方陣,並回到步驟 4. ※有時候,若不欲 (i, j) 元素被指派,只要將其成本設為大 M( 利潤設為 M ) 即可

林吉仁著 例 5-13 假設有四位技工,四件欲在不同工作母機上加工的工件,因技工專長不同,完成各工件的所費成本亦不同,如下表。請分派每位技工恰加工一件工件,而使所費總成本最小

林吉仁著 解:

林吉仁著

林吉仁著

林吉仁著 例 5-14

林吉仁著 解:

林吉仁著 例題5-15 某房屋仲介業者手邊有六件案子 ( 六棟房屋 ),而有五位購屋者,各願購買一棟房子。每位購屋者對各棟房屋願意出的價格不同,所以仲介者賣房子給各購屋者的預期利潤也不同,如下表所示。問仲介者該如何來分派售屋案 ( 那棟房屋賣給那位購屋者 ),以使得總預期利潤最大?

林吉仁著 解:

林吉仁著

例題5-16 若游泳教練欲自5名選手中選出四名來參加400米混合四式接力。選手各泳式的成績如下表,請問教練該如何安排以使接力成績最佳。 林吉仁著 例題5-16 若游泳教練欲自5名選手中選出四名來參加400米混合四式接力。選手各泳式的成績如下表,請問教練該如何安排以使接力成績最佳。

林吉仁著 解:

林吉仁著