邏輯限制

Python 的供應鏈分析

Aaren Stubberfield

Supply Chain Analytics Mgr.

範例問題

最大載重 20,000 磅

Product	Weight (lbs)	Profitability ($US)
A	12,800	77,878
B	10,900	82,713
C	11,400	82,728
D	2,100	68,423
E	11,300	84,119
F	2,300	77,765

在不超過重量上限下，選擇最賺的產品運送
決策變數：
- X$_{i}$ = 若選產品 _i_ 為 1，否則為 0
目標：
- 最大化 z = $\sum$ Profitability$_{i}$X$_{i}$
限制：
- $\sum$ Weight$_{i}$X$_{i}$ < 20,0000

prod = ['A', 'B', 'C', 'D', 'E', 'F']
weight = {'A':12800, 'B':10900, 'C':11400, 'D':2100, 'E':11300, 'F':2300}
prof = {'A':77878, 'B':82713, 'C':82728, 'D':68423, 'E':84119, 'F':77765}

# Initialize Class
model = LpProblem("Loading Truck Problem", LpMaximize)

# Define Decision Variables
x = LpVariable.dicts('ship_', prod, cat='Binary')

# Define Objective
model += lpSum([prof[i]*x[i] for i in prod])

# Define Constraint
model += lpSum([weight[i]*x[i] for i in prod]) <= 20000

# Solve Model
model.solve()
for i in prod: print("{} status {}".format(i, x[i].varValue))

範例結果

最大載重 20,000 磅

Product	Ship or Not
A	No
B	No
C	No
D	Yes
E	Yes
F	Yes

結果

Profitability: $230,307
Weight of Products: 15,700 lbs

邏輯限制範例 1

產品 E 與產品 D 擇一選擇，且不可同時選。

X$_{E}$ = 若選產品 _i_ 為 1，否則為 0
X$_{D}$ = 若選產品 _i_ 為 1，否則為 0
限制
- X$_{E}$ + X$_{D}$ ≤ 1

程式碼範例－邏輯限制範例 1

model += x['E'] + x['D'] <= 1

prod = ['A', 'B', 'C', 'D', 'E', 'F']
weight = {'A':12800, 'B':10900, 'C':11400, 
          'D':2100, 'E':11300, 'F':2300}
prof = {'A':77878, 'B':82713, 'C':82728, 
        'D':68423, 'E':84119, 'F':77765}

# Initialize Class
model = LpProblem("Loading Truck Problem",
                   LpMaximize)

# Define Decision Variables
x = LpVariable.dicts('ship_', prod, 
                      cat='Binary')

# Define Objective
model += lpSum([prof[i]*x[i] for i in prod])

# Define Constraint
model += 
  lpSum([weight[i]*x[i] for i in prod]) <= 20000
model += x['E'] + x['D'] <= 1

# Solve Model
model.solve()
for i in prod:
  print("{} status {}".format(i, x[i].varValue))

邏輯限制 1 範例結果

最大載重 20,000 磅

Product	Ship or Not
A	No
B	No
C	Yes
D	Yes
E	No
F	Yes

結果

Profitability: $228,916
Weight of Products: 15,800 lbs

邏輯限制範例 2

若選產品 D，則產品 B 也必須選。

X$_{D}$ = 若選產品 _i_ 為 1，否則為 0
X$_{B}$ = 若選產品 _i_ 為 1，否則為 0
限制
- X$_{D}$ ≤ X$_{B}$

程式碼範例－邏輯限制範例 2

model += x['D'] <= x['B']

prod = ['A', 'B', 'C', 'D', 'E', 'F']
weight = {'A':12800, 'B':10900, 'C':11400, 
          'D':2100, 'E':11300, 'F':2300}
prof = {'A':77878, 'B':82713, 'C':82728, 
        'D':68423, 'E':84119, 'F':77765}

# Initialize Class
model = LpProblem("Loading Truck Problem", 
                   LpMaximize)

# Define Decision Variables
x = LpVariable.dicts('ship_', prod,
                      cat='Binary')

# Define Objective
model += lpSum([prof[i]*x[i] for i in prod])

# Define Constraint
model += 
 lpSum([weight[i]*x[i] for i in prod]) <= 20000
model += x['D'] <= x['B']

# Solve Model
model.solve()
for i in prod:
  print("{} status {}".format(i, x[i].varValue))

邏輯限制 2 範例結果

最大載重 20,000 磅

Product	Ship or Not
A	No
B	Yes
C	No
D	Yes
E	No
F	Yes

結果

Profitability: $228,901
Weight of Products: 15,300 lbs

其他邏輯限制

Logical Constraint	Constraint
若選擇項目 _i_，則也要選擇項目 _j_。	x$_{i}$ - x$_{j}$ ≤ 0
項目 _i_ 與項目 _j_ 擇一，但不可同時選。	x$_{i}$ + x$_{j}$ = 1
若選擇項目 _i_，則不得選擇項目 _j_。	x$_{i}$ - x$_{j}$ ≤ 1
若未選擇項目 _i_，則不得選擇項目 _j_。	-x$_{i}$ + x$_{j}$ ≤ 0
在 _i_、_j_、_k_ 中至多選一個。	x$_{i}$ + x$_{j}$ + x$_{k}$ ≤ 1

¹ James Orlin、Ebrahim Nasrabadi。15.053 Optimization Methods in Management Science。2013 年春季。Massachusetts Institute of Technology: MIT OpenCourseWare。授權：Creative Commons BY-NC-SA。

小結

複習了邏輯限制的範例
列出其他邏輯限制的對照表

換你了！

Python 的供應鏈分析