Leo Yeh's Blog

SAS 優化研究 (8)

教學目標

初步了解運輸問題之優化模型程式碼應用的基本概念。

重點概念

首先運輸問題是企業管理者經常會遇到特殊形式的線性規劃,所謂運輸問題主要是指由數個供應點將物品運送至數個需求點的問題,並且我們針對運輸問題有基本假設為運送的貨物為同質,也就是代表無論起點與終點的貨物相同,無論運貨數量多少,每單位運輸成本都相同,每個起點與每個終點之間的運輸路線只有一條路線。

接著針對運輸問題給定一組資料,請參考下表,其中包括供應點的價值和需求點的價值,以及單位運輸成本,並且運輸問題主要是確定從每個起點運輸到每個目的地的數量,目標是以最低的供應成本滿足需求。

Boston Newark Toronto Supply
Chicago 40 25 15 200
Detroit 30 15 10 150
Demand 50 150 100

再來我們將能夠透過 OPTMODEL 程序撰寫優化模型程式碼解決運輸問題,並且其中決策變數主要是從每個起點到每個目的地的運送量,此時我們能夠使用索引集和參數陣列的方法比起使用命名變數的方法更直觀表達。請注意決策變數必須在使用之前進行宣告,除了決策變數之外,像是穩含變數和參數陣列也必須在使之前進行宣告。

優化模型程式碼 (線性)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
proc optmodel;
set ORIGINS = /Chicago Detroit/;
set DESTINATIONS = /Boston Newark Toronto/;
num supply {ORIGINS} = [200 150];
num demand {DESTINATIONS} = [50 150 100];
num unit_cost {ORIGINS, DESTINATIONS} =
[40 25 15 30 15 10];
var NumShip {ORIGINS, DESTINATIONS} >= 0;
impvar FlowOut {i in ORIGINS} =
sum {j in DESTINATIONS} NumShip[i,j];
impvar FlowIn {j in DESTINATIONS} =
sum {i in ORIGINS} NumShip[i,j];
con Supply_con {i in ORIGINS}:
FlowOut[i] <= supply[i];
con Demand_con {j in DESTINATIONS}:
FlowIn[j] >= demand[j];
min TotalCost = sum {i in ORIGINS, j in DESTINATIONS}
unit_cost[i,j] * NumShip[i,j];
expand;
solve;
print NumShip;
quit;

優化模型選項

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Var NumShip[Chicago,Boston] >= 0                                                                                                    
Var NumShip[Chicago,Newark] >= 0
Var NumShip[Chicago,Toronto] >= 0
Var NumShip[Detroit,Boston] >= 0
Var NumShip[Detroit,Newark] >= 0
Var NumShip[Detroit,Toronto] >= 0
Impvar FlowOut[Chicago] = NumShip[Chicago,Boston] + NumShip[Chicago,Newark] + NumShip[Chicago,Toronto]
Impvar FlowOut[Detroit] = NumShip[Detroit,Boston] + NumShip[Detroit,Newark] + NumShip[Detroit,Toronto]
Impvar FlowIn[Boston] = NumShip[Chicago,Boston] + NumShip[Detroit,Boston]
Impvar FlowIn[Newark] = NumShip[Chicago,Newark] + NumShip[Detroit,Newark]
Impvar FlowIn[Toronto] = NumShip[Chicago,Toronto] + NumShip[Detroit,Toronto]
Minimize TotalCost=40*NumShip[Chicago,Boston] + 25*NumShip[Chicago,Newark] + 15*NumShip[Chicago,Toronto] + 30*
NumShip[Detroit,Boston] + 15*NumShip[Detroit,Newark] + 10*NumShip[Detroit,Toronto]
Constraint Supply_con[Chicago]: FlowOut[Chicago] <= 200
Constraint Supply_con[Detroit]: FlowOut[Detroit] <= 150
Constraint Demand_con[Boston]: FlowIn[Boston] >= 50
Constraint Demand_con[Newark]: FlowIn[Newark] >= 150
Constraint Demand_con[Toronto]: FlowIn[Toronto] >= 100

問題摘要

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

解法摘要

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

優化模型結果

Numship Boston Newark Toronto
Chicago 50 0 100
Detroit 0 150 0

優化模型日誌

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
NOTE: 問題產生將使用 4 個執行緒。
NOTE: 問題有 6 個變數 (0 個無限制, 0 個固定)。
NOTE: 問題使用 5 個隱含變數。
NOTE: 問題有 5 個線性限制 (2 個 LE、0 個 EQ、3 個 GE、0 個範圍)。
NOTE: 問題有 12 個線性限制係數。
NOTE: 問題有 0 個非線性限制 (0 個 LE、0 個 EQ、0 個 GE、0 個範圍)。
NOTE: 已停用線性問題的 OPTMODEL 預解器。
NOTE: 問題為純網路執行個體。建議使用 ALGORITHM=NETWORK 選項求解此結構的問題。
NOTE: 已套用 LP 預解器值 AUTOMATIC。
NOTE: LP 預解器時間為 0.01 秒。
NOTE: LP 預解器已移除 0 個變數及 0 個限制。
NOTE: LP 預解器已移除 0 個限制係數。
NOTE: 預解的問題有 6 個變數、5 個限制和 12 個限制係數。
NOTE: 已呼叫 LP 求解器。
NOTE: 使用對偶單形演算法。
目標
階段反覆運算 值 時間
D 2 1 0.000000E+00 0
D 2 6 5.750000E+03 0
NOTE: Optimal.
NOTE: Objective = 5750.
NOTE: 對偶單形求解時間為 0.01 秒。
NOTE: PROCEDURE OPTMODEL used (Total process time):
real time 0.23 seconds
cpu time 0.17 seconds

最後當我們執行優化模型程式碼之後將會輸出以上的結果,從結果中我們將能夠了解如果要以最低的供應成本滿足需求,則從芝加哥需要分別傳輸 50 個貨物至波斯頓和傳輸 100 個貨物至多倫多,以及從底特律傳輸 150 個貨物至波斯頓。此外運輸問題更能夠解決不同領域型的問題,像是網路運輸問題、最大流量問題、最短路徑問題、任務分配問題、生產規劃問題、… 等,只要是將供應點稱為來源,需求點稱為目的,則皆能夠以上述的優化模型程式碼來解決問題。

相關資源

⬅️ Go back