Leo Yeh's Blog

SAS 優化研究 (7)

教學目標

初步了解如何將在有限資源下以最有效率的生產方式為公司帶來最大化利潤定義為線性優化問題和求解過程的基本概念。

重點概念

首先定義線性優化問題必須確定決策變數的限制條件和函式目標,決策變數在某種意義上是最基本的優化模型元素,像是我們應該生產多少單位?限制條件為了透過數學公式解決線性優化問題,必須限制優化模型的選擇,像是花費會多少和投資報酬率。而在 OPTMODEL 程序中的預設線性演算法為對偶單形演算法 (Dual Simplex Algorithm),其中對偶單形演算法主要分為兩個階段,分別為:

  1. 階段一:嘗試找到滿足可行條件的解決方案,判斷 LP 求解器是否可行。
  2. 階段二:嘗試找到滿足最優條件的解決方案,判斷 LP 求解器是否無限。

當符合可行性和最優性,則 LP 求解器會有一個最佳解決方案,以及透過 EXPAND 敘述列出線性優化模型的選項,其中選項主要包括有變數 (var)、隱式變數 (impvar)、目標 (obj) 和限制 (con),預設為顯示全部。

接著我們將能夠執行以下優化模型程式碼解決家俱生產公司的生產優化問題,其中主要生產製造書桌、椅子、書櫃和床架,並且所有生產家俱皆需要不同的工時、金屬和木頭,請參考下表資訊。

工時 (Labor) 金屬 (Metal) 木頭 (Wood) 售價 (Price)
書桌 (Desks) 2 1 3 94
椅子 (Chairs) 1 1 3 79
書櫃 (Bookcases) 3 1 4 125
床架 (Badframes) 2 1 4 109
成本 (Cost) 14 20 11
資源 (Resource) 225 117 420

假設所有家俱皆能夠出售,此時家俱生產公司每天需要生產多少桌子、椅子、書櫃和床架才能夠達到淨利潤儘可能最大化,為了解決生產優化問題,則我們就能夠透過 OPTMODEL 程序撰寫優化模型程碼,其中根據決策變數和限制條件計算出最大化的目標函數。

優化模型程式碼 (線性)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
proc optmodel;
var Desks >= 0, Chairs >= 0, Bookcases >= 0, Bedframes >= 0;
con Labor: 2*Desks + 1*Chairs + 3*Bookcases + 2*Bedframes <= 225;
con Metal: 1*Desks + 1*Chairs + 1*Bookcases + 1*Bedframes <= 117;
con Wood: 3*Desks + 3*Chairs + 4*Bookcases + 4*Bedframes <= 420;
max NetProfit =

94*Desks + 79*Chairs + 125*Bookcases + 109*Bedframes
- (14 * (2*Desks + 1*Chairs + 3*Bookcases + 2*Bedframes)
+ 20 * (1*Desks + 1*Chairs + 1*Bookcases + 1*Bedframes)
+ 11 * (3*Desks + 3*Chairs + 4*Bookcases + 4*Bedframes));
expand;

solve;
print Desks Chairs Bookcases Bedframes;
quit;

優化模型選項

1
2
3
4
5
6
7
8
Var Desks >= 0                                                                                                                      
Var Chairs >= 0
Var Bookcases >= 0
Var Bedframes >= 0
Maximize NetProfit=13*Desks + 12*Chairs + 19*Bookcases + 17*Bedframes
Constraint Labor: 2*Desks + Chairs + 3*Bookcases + 2*Bedframes <= 225
Constraint Metal: Desks + Chairs + Bookcases + Bedframes <= 117
Constraint Wood: 3*Desks + 3*Chairs + 4*Bookcases + 4*Bedframes <= 420

問題摘要

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

解法摘要

項目
求解器 LP
演算法 對偶單形
目標函數 NetProfit
解決方案狀態 最佳
目標值 1827
原始不可解性 2.842171E-13
對偶不可解性 0
界限不可解性 0
反覆運算 6
預解時間 0.00
解決時間 0.01

優化模型結果

Desks Chairs Bookcases Bedframes
0 48 39 30

優化模型日誌

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

再來根據上述優化模型程式碼的問題主要求最大化利潤,至於利潤的公式為收益扣掉成本,所謂收益為售價乘上數量,但是我們僅有售價和成本,卻沒有數量,因為我們就是需要透過優化模型求出不同家俱所需的數量在有限資源的限制條件下達到最大化利潤目標,並且數量一定大於等於 0,所以我們就能夠根據此想法定義出決策變數、限制條件和目標函數。其中主要有四個決策變數,分別為 Desks、Chairs、Bookcases 和 Bedframes,因此當執行完成線性優化模型求解過程之後將會計算出四個決策變數的值,也就是代表不同家俱所需的數量,並且有三個限制條件,分別為 Labor、Metal 和 Wood,因此在執行線性優化模型求解過程中將會在符合三個限制條件的情況下找出可行區域,以及有一個最大化線性目標函數為 NetProfit = [Revenue] - [Cost],以利在可行區域中找出優化模型的最佳解。

決策變數

1
var Desks >= 0, Chairs >= 0, Bookcases >= 0, Bedframes >= 0;

限制條件

1
2
3
con Labor: 2*Desks + 1*Chairs + 3*Bookcases + 2*Bedframes <= 225;
con Metal: 1*Desks + 1*Chairs + 1*Bookcases + 1*Bedframes <= 117;
con Wood: 3*Desks + 3*Chairs + 4*Bookcases + 4*Bedframes <= 420;

目標函數

1
2
3
4
5
max NetProfit = 
94*Desks + 79*Chairs + 125*Bookcases + 109*Bedframes
- (14 * (2*Desks + 1*Chairs + 3*Bookcases + 2*Bedframes)
+ 20 * (1*Desks + 1*Chairs + 1*Bookcases + 1*Bedframes)
+ 11 * (3*Desks + 3*Chairs + 4*Bookcases + 4*Bedframes));

最後我們將會發若要利潤最大化,則在有限資源下建議先不要生產書桌,而是專門生產椅子,其次為床架,再來為書櫃,才能夠達到最大化利潤,當然現實情況可能會要求必須生產多少書桌、椅子、書櫃和床架不同家俱的最低數量,此時我們僅需要修改決策變數的條件式就能夠求解出符合不同家俱最低數量的最大化利潤。所以我們能夠以線性優化模型為基礎,更進一步思考如何在有限資源下以最有效率的生產方式為公司帶來最大化利潤。

相關資源

⬅️ Go back