多目標規劃 前言 3.1　基本概念 3.2　多目標單形法 3.3　妥協規劃法 3.4　案例研討.

Presentation on theme: "多目標規劃 前言 3.1　基本概念 3.2　多目標單形法 3.3　妥協規劃法 3.4　案例研討."— Presentation transcript:

1

2 多目標規劃 前言 3.1　基本概念 3.2　多目標單形法 3.3　妥協規劃法 3.4　案例研討

3 前言 多準則決策視為一較廣泛的概念，包括了多目標規劃(multiple objective programming)與多屬性決策(multiple attribute decision making)兩種決策分析方法。 目標規劃與多屬性決策的差異，大致可歸納如下： 多屬性決策所評估的可行方案是有限個，而且這些方案在事先是已知的；多目標規劃是利用數學式子來表示所有的可行方案，有無限多個且事先是未知的。 屬性是決策者評估方案的基礎，多屬性決策中，常需瞭解決策者偏好，訂出各屬性相對權重，以便篩選出最佳的方案；多目標規劃則是透過數學模式的求解，得出一組可接受的可行方案。 Chapter 3　多目標規劃

4 3.1 基本概念 多目標規劃是數學規劃的一種。 考慮下列包含兩個目標式的多目標規劃問題 例 (3.2) Chapter 3　多目標規劃

5 3.2 多目標單形法 多目標單形法(multiobjective simplex method, MSM)是多目標線性規劃最主要求解方法，源自於一般教科書常見的單目標線性規劃問題的單形法(simplex method)，旨在尋找可行解區域中的角點，直到所有效率解均被找到為止。 Chapter 3　多目標規劃

6 將各限制式加入差額變數(slack variable)，並以差額變數做為初始基變數。
例 下面例子，說明多目標單形法的求解過程 (3.4) (其中x1, x2  0 ) 將各限制式加入差額變數(slack variable)，並以差額變數做為初始基變數。 (3.5) (其中x1, x2, x3, x4, x5  0) Chapter 3　多目標規劃

7 表中 zij 的計算公式為 在例中， 同理， Chapter 3　多目標規劃

8 設 ，則基變數 xr 可被選為退出基底的變數，也就 是 xr 由基變數轉變成非基變數。目標函數的變化為
當 設　　　，則基變數 xr 可被選為退出基底的變數，也就 是 xr 由基變數轉變成非基變數。目標函數的變化為 本例選擇 x2 進入基底 x2 可做為退出基底變數。經由列運算，可得到下面單形表 Chapter 3　多目標規劃

9 x3, x5 均可選為退出基底的變數；今選擇 x3 退出基底，再利用列運算，得到下表
Chapter 3　多目標規劃

10 3.3 妥協規劃法 1/4 妥協規劃(compromise programming)解法，是以距離概念為基礎，其目的是在尋找與理想解(ideal solution)距離最近的效率解，稱之為妥協解(compromise solution)。 x 與 x* 的直線距離 兩點之間距離予以一般化，x 與 x* 之間的距離 wi 是第 i 座標中附加在距離的權重，0 < wi < 1，且　　 Chapter 3　多目標規劃

11 3.3 妥協規劃法 2/4 當 p = 1 時， 當 p = 2 時，即為一般的直線距離。 當 p =  時，
3.3　妥協規劃法 2/4 當 p = 1 時， 當 p = 2 時，即為一般的直線距離。 當 p =  時，　　　　　　　　 wi 是對應於第 i 目標函數的權重，　是第 i 目標函數最佳解對應的目標值，p是{1,2,,}中任一數值。 Chapter 3　多目標規劃

12 例 考慮下列多目標規劃問題 　　　　　　　　 (3.6) Chapter 3　多目標規劃

13 由妥協規劃法可求得妥協解 x = (4, 4), f1 (4, 4) = 12, f2 (4, 4) = 12。
f1極大化的最佳解 x1*=(6, 0)，　　　，f2 極大化的最佳解 x2*= (1, 4)，　　　，以及 f1 (8.33, 5.83)　= 30, f2 (8.33, 5.83) = 15，因此設定x* = (8.33, 5.83)為本題之理想解。 假設w1 = w2= 0.5, p = 1，則 由妥協規劃法可求得妥協解 x = (4, 4), f1 (4, 4) = 12, f2 (4, 4) = 12。 Chapter 3　多目標規劃

14 3.4 案例研討 1/7 發電機組：核能、火力、水力三大類。 期望能： 目標函數 降低購煤成本，以直接降低發電成本。
3.4 案例研討 1/7 發電機組：核能、火力、水力三大類。 期望能： 降低購煤成本，以直接降低發電成本。 有效控制煤質，提升鍋爐效率，使排放物合於環保要求。 目標函數 購煤成本最小化 機組效率最佳化 Chapter 3　多目標規劃

15 3.4 案例研討 2/7 限制條件 合約量提運條件 煤源地區分配比例限制 第 i 煤區合約量上限 第 i 煤區合約量下限
3.4 案例研討 2/7 限制條件 合約量提運條件 煤源地區分配比例限制 　第 i 煤區合約量上限 　第 i 煤區合約量下限 Chapter 3　多目標規劃

16 3.4 案例研討 3/7 鍋爐要求 1. 2. 3. 4. 5.若HGIi  HGIUj 或 HGIi  HGILj，則 Xij = 0
3.4 案例研討 3/7 鍋爐要求 1. 2. 3. 4. 5.若HGIi  HGIUj 或 HGIi  HGILj，則 Xij = 0 6.若H2Oi  H2OUj 或 H2Oi  H2OUj ，則 Xij = 0 Chapter 3　多目標規劃

17 3.4 案例研討 4/7 環保要求 不混拌電廠限制 各煤源地區煤值，都要單獨合於電廠鍋爐要求，Xij = 0
3.4 案例研討 4/7 環保要求 不混拌電廠限制 (j =1, 2, 3分別為林口#1、林口#2、深澳電廠機組。) 各煤源地區煤值，都要單獨合於電廠鍋爐要求，Xij = 0 Chapter 3　多目標規劃

18 3.4 案例研討 5/7 各煤合約至港口之最低運量限制 大林埔港 台中港 供應煤質與機組效率煤質之差量 Chapter 3　多目標規劃

19 Chapter 3　多目標規劃

20 狀況 I 為購煤成本最小化的解，其目標值(f1, f2) = (386107, 329851)。
狀況 II 為機組效率最佳化的解，其目標值(f1, f2) = (390005, )。狀況 III 與狀況 IV 分別是 p = 1 及 p =  時的妥協解。 狀況 III 的目標值(f1, f2) = (387714, )；其中 f2 的值與狀況 II 相同，而且 f1 值僅比狀況 I 多出US1,607千元，顯示狀況 III 的解優於狀況 II。 狀況 IV 的目標值(f1, f2) = (386524, )，其 f1 值僅比狀況 I 多一點， f2 值也較狀況II稍高，似乎也是一個不錯的效率解。 決策者若認為購煤成本是較重要的考慮因素，狀況 III 可做為採行方案。 若以機組效率較為重要時，則狀況 III 為決策方案。 Chapter 3　多目標規劃