Leo Yeh's Blog

SAS 優化研究 (5)

教學目標

初步了解 OPTMODEL 程序中不同目標函數類型之預設演算法和求解器的基本概念。

重點概念

首先作業研究的工具主要用於解決資源管理和計劃問題,在作業研究中的模型是物理件、概念或業務流程的表示,並且使用作業研究的工具涉及以下內容,分別為:

  1. 定義模型結構
  2. 收集模型資料
  3. 進行模型求解
  4. 解釋模型結果

而 SAS Optimization 主要包括通用優化過程,其將會利用 SAS Viya 分析提供基於雲端的分散式運算環境進行模型求解,求解會採用不同的求解器,分別為線性 (LP)、混合整數線性 (MILP)、二次 (QP)、非線性 (NLP)、… 等,同時分解演算法將能夠在線性和混合整數線性問題中使用不同類型的結構來減少求解時間,至於 OPTMODEL 程序則是建立優化模型和使用不同的求解器,然而在 OPTMODEL 程序中預設選擇優化演算法和求主要是會基於問題的特性,請參考下表。

目標函數類型 優化演算法 求解器
線性 對偶單形 (Dual Simplex) LP
混合整數線性 分支和切割 (Branch and Bound) MILP
二次 內點 (Interior Point) QP
非線性 內點 (Interior Point) NLP

針對線性目標函數類型問題的預設演算法為對偶單形演算法,求解器為 LP,程式執行結果主要會顯示問題摘要和解法摘要。

優化模型程式碼 (線性)

1
2
3
4
5
6
7
8
9
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;

print x y;
quit;

問題摘要

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

解法摘要

項目
求解器 LP
演算法 對偶單形
目標函數 z
解決方案狀態 最佳
目標值 1782
原始不可解性 5.684342E-14
對偶不可解性 1.776357E-15
界限不可解性 0
反覆運算 4
預解時間 0.00
解決時間 0.01

優化模型結果

x y
63 54

接著針對混合整數線性目標函數類型問題的預設演算法為對偶單形演算法,求解器為 MILP,程式執行結果主要會顯示問題摘要和解法摘要。

優化模型程式碼 (混合整數線性)

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

print x y;
quit;

問題摘要

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

解法摘要

項目
求解器 MILP
演算法 分支和切割
目標函數 z
解決方案狀態 最佳
目標值 1782
相對間隙 0
絕對間隙 0
原始不可解性 0
界限不可解性 0
整數不可解性 0
最佳界限 1782
節點 1
發現的解決方案 4
反覆運算 5
預解時間 0.01
解決時間 0.01

優化模型結果

x y
63 54

再來針對二次目標函數類型問題的預設演算法為內點演算法,求解器為 QP,程式執行結果主要會顯示問題摘要和解法摘要。

優化模型程式碼 (二次)

1
2
3
4
5
6
proc optmodel;
var x >= 0, y <= 1;
min z = x**2 - x - 2*y - x*y + y**2;

solve;
print x y;
quit;

問題摘要

項目
目標原理 最小化
目標函數 z
目標類型 二次
變數數目 2
有上限 1
有下限 1
有下限和上限 0
可用 0
固定 0
限制數目 0
限制係數 0
Hessian 對角元素 2
低於對角的 Hessian 元素 1

解法摘要

項目
求解器 QP
演算法 內點
目標函數 z
解決方案狀態 最佳
目標值 -0.25
原始不可解性 0
對偶不可解性 0
界限不可解性 1.2127214E-9
對偶間隙 0
互補性 0
反覆運算 4
預解時間 0.00
解決時間 0.02

優化模型結果

x y
0.5 0

最後針對非線性目標函數類型問題的預設演算法為內點演算法,求解器為 NLP,程式執行結果主要會顯示問題摘要和解法摘要。

優化模型程式碼 (非線性)

1
2
3
4
5
6
proc optmodel;
var x ,y;
min z = (y-x**2)**2 + (1-x)**2;
solve;
print x y;
quit;

問題摘要

項目
目標原理 最小化
目標函數 z
目標類型 非線性
變數數目 2
有上限 0
有下限 0
有下限和上限 0
可用 2
固定 0
限制數目 0

解法摘要

項目
求解器 NLP
演算法 內點
目標函數 z
解決方案狀態 最佳
目標值 2.962209E-15
最適性誤差 8.9089584E-8
不可解性 0
反覆運算 5
預解時間 0.00
解決時間 0.00

優化模型結果

x y
1 1

總結基本的優化問題主要是在該函數的變數限制之情況下最小化或最大化目標函數,目標函數和限制可以是線性或非線性的,其中限制可以是綁定限制,等式限制、不等式限制或整數限制,並且優化問題主要根據變數所限制的值集 (實數、整數、二進位或組合) 、限制條件和目標函數類型 (線性、混合整數線性、二次或非線性) 以數學形式表達優化問題,以及透過 OPTMODEL 程序撰寫針對優化問題進行模型求解的數學程式。

相關資源

⬅️ Go back