Leo Yeh's Blog

SAS 優化研究 (6)

教學目標

初步了解線性優化問題中 Lagrangian 函式的基本概念。

重點概念

首先在線性優化問題中若滿足所有限制條件,則為可行的解決方案,而最佳解就是一種可行的解決方案,除了最佳解之外,還有在可行區域角落的值為極端值解,並且若線性優化問題無限制,那麼可行區域也必須是無限的,但是反過來並不總是如此。此外並非每個限制條件皆有助於決定可行區域的最佳解,但是我們要如何在問題的多個限制條件中找出有用的限制條件呢?此時我們就能夠透過 Lagrangian 函式將每個限制條件轉換為 lambda 參數,並且根據 lambda 參數值來判斷限制條件是否有助於決定可行區域中的最佳解。

接著 Lagrangian 函式主要提供決策變數值的框架模擬優化目標函數和符合限制條件,在通用的 Lagrangian 函式主要有兩個可能的向量值參數,決策變數為 X ,每個限制皆有一個 lambda 參數,同時也稱為 shadow price,Lagrangian 函式為 𝑳(𝒙,𝝀) = 𝑭(𝒙) + 𝝀[𝒃−𝑨(𝒙)],其中函數目標為 𝑭(𝒙) 和限制條件為 𝒃−𝑨(𝒙),且函數目標可能為線性函數和非線性函數。此外若有 m 個決策變數和 n 個限制條件,則相對 Lagrangian 函數中的參數將會有 m + n 個未知參數的 m + n 個方程式,設定偏導數 Lagrangian 函數等於 0 將符合 Kuhn-Tucker 條件,同時也是得到最佳解。

再來 Lagrangian 函數是優化目標函數的方法,其中每個限制條件對應一個 lambda 參數,若是限制條件不滿足,則 lambda 參數為 0,反之若是限制條件滿足,則 lambda 參數不為 0,代表一個單位增加將會對於目標函數帶來多少改變。如果以下述優化模型程式碼為例,則我們將能夠透過 Lagrangian 函數計算出最大值 z 的最佳解,其中主要有 2 個決策變數和 3 個限制條件,此時將會產生 5 個方程式和 5 個方程式的未知數,並且我們將 5 個方程式皆等於為 0,以利快速地推導出優化目標的 x 和 y 決策變數值,分別為 63 和 54。

優化模型程式碼 (線性)

1
2
3
4
5
6
7
8
9
10
proc optmodel;
var x >= 0, y >= 0;
max z = 12*x + 19*y;
con x + 3*y <= 225;
con x + y <= 117;
con 3*x + 4*y <= 420;
solve with lp / algorithm=ps;

print x y;
print _con_.dual;
quit;

問題摘要

項目
目標原理 最大化
目標函數 z
目標類型 線性
變數數目 2
有上限 0
有下限 2
有下限和上限 0
可用 0
固定 0
限制數目 3
線性 LE (<=) 3
線性 EQ (=) 0
線性 GE (>=) 0
線性範圍 0
限制係數 6

解法摘要

項目
求解器 LP
演算法 原始單點
目標函數 z
解決方案狀態 最佳
目標值 1782
原始不可解性 0
對偶不可解性 0
界限不可解性 0
反覆運算 3
預解時間 0.01
解決時間 0.02

優化模型結果

x y
63 54
[1] _CON_.DUAL
1 3.5
2 8.5
3 0.0

優化模型日誌

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
NOTE: 問題產生將使用 4 個執行緒。
NOTE: 問題有 2 個變數 (0 個無限制, 0 個固定)。
NOTE: 問題有 3 個線性限制 (3 個 LE、0 個 EQ、0 個 GE、0 個範圍)。
NOTE: 問題有 6 個線性限制係數。
NOTE: 問題有 0 個非線性限制 (0 個 LE、0 個 EQ、0 個 GE、0 個範圍)。
NOTE: 已套用 LP 預解器值 AUTOMATIC。
NOTE: LP 預解器時間為 0.01 秒。
NOTE: LP 預解器已移除 0 個變數及 0 個限制。
NOTE: LP 預解器已移除 0 個限制係數。
NOTE: 預解的問題有 2 個變數、3 個限制和 6 個限制係數。
NOTE: 已呼叫 LP 求解器。
NOTE: 使用原始單形演算法。
目標
階段反覆運算 值 時間
P 2 1 0.000000E+00 0
P 2 3 1.782000E+03 0
NOTE: Optimal.
NOTE: Objective = 1782.
NOTE: 原始單形求解時間為 0.01 秒。
NOTE: PROCEDURE OPTMODEL used (Total process time):
real time 0.08 seconds
cpu time 0.07 seconds

最後查看優化模型程式碼中的問題摘要將會發現問題主要為最大化線性目標函數,其中有 2 個有下限的決策變數,3 個線性小於等於的限制條件,6 個限制係數 (2×3)。並且查看解法摘要將會發現問題的解法主要為使用原始單點的 LP 求解器計算出目標函數符合所有限制條件的最佳解為 1782,其中解決時間為 0.02 秒。此外查看優化模型結果將會發現 2 個決策變數最佳解的值為 63 和 54,並且 CON.DUAL 選項則顯示不同條件的 lambda 參數值,第一個 lambda 參數為 3.5 和第二個 lambda 參數為 8.5,皆代表最佳解充分滿足第一個限制條件和第二個限制條件,至於第三個 lambda 參數為 0,則代表最佳解未充分滿足第三個限制條件,所以第一個限制條件和第二個限制條件將有助於決定可行區域中的最佳解,但是第三個限制條件將無助於決定可行區域中的最佳解。

總結在解決線性優化的問題時,我們能夠透過 Lagrangian 函式將每個限制條件轉換為 lambda 參數,並且根據 lambda 參數值來判斷限制條件是否有助於決定可行區域中的最佳解。

相關資源

⬅️ Go back