多目标单形法多目标单形法.PPTVIP

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