多目標規劃 前言 3.1 基本概念 3.2 多目標單形法 3.3 妥協規劃法 3.4 案例研討
前言 多準則決策視為一較廣泛的概念,包括了多目標規劃(multiple objective programming)與多屬性決策(multiple attribute decision making)兩種決策分析方法。 目標規劃與多屬性決策的差異,大致可歸納如下: 多屬性決策所評估的可行方案是有限個,而且這些方案在事先是已知的;多目標規劃是利用數學式子來表示所有的可行方案,有無限多個且事先是未知的。 屬性是決策者評估方案的基礎,多屬性決策中,常需瞭解決策者偏好,訂出各屬性相對權重,以便篩選出最佳的方案;多目標規劃則是透過數學模式的求解,得出一組可接受的可行方案。 Chapter 3 多目標規劃
3.1 基本概念 多目標規劃是數學規劃的一種。 考慮下列包含兩個目標式的多目標規劃問題 例 (3.2) Chapter 3 多目標規劃
3.2 多目標單形法 多目標單形法(multiobjective simplex method, MSM)是多目標線性規劃最主要求解方法,源自於一般教科書常見的單目標線性規劃問題的單形法(simplex method),旨在尋找可行解區域中的角點,直到所有效率解均被找到為止。 Chapter 3 多目標規劃
將各限制式加入差額變數(slack variable),並以差額變數做為初始基變數。 例 下面例子,說明多目標單形法的求解過程 (3.4) (其中x1, x2 0 ) 將各限制式加入差額變數(slack variable),並以差額變數做為初始基變數。 (3.5) (其中x1, x2, x3, x4, x5 0) Chapter 3 多目標規劃
表中 zij 的計算公式為 在例中, 同理, Chapter 3 多目標規劃
設 ,則基變數 xr 可被選為退出基底的變數,也就 是 xr 由基變數轉變成非基變數。目標函數的變化為 當 設 ,則基變數 xr 可被選為退出基底的變數,也就 是 xr 由基變數轉變成非基變數。目標函數的變化為 本例選擇 x2 進入基底 x2 可做為退出基底變數。經由列運算,可得到下面單形表 Chapter 3 多目標規劃
x3, x5 均可選為退出基底的變數;今選擇 x3 退出基底,再利用列運算,得到下表 Chapter 3 多目標規劃
3.3 妥協規劃法 1/4 妥協規劃(compromise programming)解法,是以距離概念為基礎,其目的是在尋找與理想解(ideal solution)距離最近的效率解,稱之為妥協解(compromise solution)。 x 與 x* 的直線距離 兩點之間距離予以一般化,x 與 x* 之間的距離 wi 是第 i 座標中附加在距離的權重,0 < wi < 1,且 Chapter 3 多目標規劃
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 多目標規劃
例 考慮下列多目標規劃問題 (3.6) Chapter 3 多目標規劃
由妥協規劃法可求得妥協解 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 多目標規劃
3.4 案例研討 1/7 發電機組:核能、火力、水力三大類。 期望能: 目標函數 降低購煤成本,以直接降低發電成本。 3.4 案例研討 1/7 發電機組:核能、火力、水力三大類。 期望能: 降低購煤成本,以直接降低發電成本。 有效控制煤質,提升鍋爐效率,使排放物合於環保要求。 目標函數 購煤成本最小化 機組效率最佳化 Chapter 3 多目標規劃
3.4 案例研討 2/7 限制條件 合約量提運條件 煤源地區分配比例限制 第 i 煤區合約量上限 第 i 煤區合約量下限 3.4 案例研討 2/7 限制條件 合約量提運條件 煤源地區分配比例限制 第 i 煤區合約量上限 第 i 煤區合約量下限 Chapter 3 多目標規劃
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 多目標規劃
3.4 案例研討 4/7 環保要求 不混拌電廠限制 各煤源地區煤值,都要單獨合於電廠鍋爐要求,Xij = 0 3.4 案例研討 4/7 環保要求 不混拌電廠限制 (j =1, 2, 3分別為林口#1、林口#2、深澳電廠機組。) 各煤源地區煤值,都要單獨合於電廠鍋爐要求,Xij = 0 Chapter 3 多目標規劃
3.4 案例研討 5/7 各煤合約至港口之最低運量限制 大林埔港 台中港 供應煤質與機組效率煤質之差量 Chapter 3 多目標規劃
Chapter 3 多目標規劃
狀況 I 為購煤成本最小化的解,其目標值(f1, f2) = (386107, 329851)。 狀況 II 為機組效率最佳化的解,其目標值(f1, f2) = (390005, 217533)。狀況 III 與狀況 IV 分別是 p = 1 及 p = 時的妥協解。 狀況 III 的目標值(f1, f2) = (387714, 217533);其中 f2 的值與狀況 II 相同,而且 f1 值僅比狀況 I 多出US1,607千元,顯示狀況 III 的解優於狀況 II。 狀況 IV 的目標值(f1, f2) = (386524, 229529),其 f1 值僅比狀況 I 多一點, f2 值也較狀況II稍高,似乎也是一個不錯的效率解。 決策者若認為購煤成本是較重要的考慮因素,狀況 III 可做為採行方案。 若以機組效率較為重要時,則狀況 III 為決策方案。 Chapter 3 多目標規劃