Capital Budgeting Problem#
이강우 & 김정자. (2012). EXCEL 2010 경영과학. 한경사, 397.
| Investment targets | NPV (net present value) |
Investment amount | |||
|---|---|---|---|---|---|
| First year | Second year | Third year | Fourth year | ||
| 1 | 30 | 20 | 25 | 25 | 20 |
| 2 | 10 | 10 | 20 | 15 | 10 |
| 3 | 15 | 15 | 30 | 20 | 5 |
| 4 | 12 | 10 | 15 | 10 | 15 |
| 5 | 35 | 25 | 30 | 30 | 25 |
| Capital by year | 70 | 90 | 80 | 60 | |
자본예산문제는 투자대상의 선택문제이므로 결정변수 $X_{j}$를 다음과 같이 이진변수로 정의하자.
\[\begin{split}X_{j} =
\begin{cases}
1, \; \text{if investment target $j$ is selected }(j=1,2,3)\\
0, \; \text{otherwise}
\end{cases}\end{split}\]
import os
import sys
# Add the parent directory for importing custom library
sys.path.append('../')
from pulp import *
from ortools.utils import output
n = 5
year = 4
npv = [30, 10, 15, 12, 35]
amount = [
[20, 25, 25, 20],
[10, 20, 15, 10],
[15, 30, 20, 5],
[10, 15, 10, 15],
[25, 30, 30, 25]
]
capital = [70, 90, 80, 60]
prob = LpProblem('Capital Budgeting Problem', LpMaximize)
indexs = [(i) for i in range(n)]
x = LpVariable.dicts('X', indexs, lowBound=0, cat='Binary')
prob += lpSum([npv[i]*x[i] for i in range(n)])
for j in range(year):
prob += lpSum([amount[i][j]*x[i] for i in range(n)]) <= capital[j]
prob.solve()
output(prob)
---------------------------------------------------------------------------
ModuleNotFoundError Traceback (most recent call last)
Cell In[2], line 1
----> 1 from pulp import *
2 from ortools.utils import output
4 n = 5
ModuleNotFoundError: No module named 'pulp'
Multiple choice constraint#
5개의 투자대상 $X_{j}$중에서 3개의 투자대상을 선택하는 제약식, 이를 선다형 제약식(multiple choice constraint)라고 한다.
from pulp import *
from ortools.utils import output
n = 5
year = 4
npv = [30, 10, 15, 12, 35]
amount = [
[20, 25, 25, 20],
[10, 20, 15, 10],
[15, 30, 20, 5],
[10, 15, 10, 15],
[25, 30, 30, 25]
]
capital = [70, 90, 80, 60]
# Define problem
prob = LpProblem('Capital Budgeting Problem', LpMaximize)
indexs = [(i) for i in range(n)]
x = LpVariable.dicts('X', indexs, lowBound=0, cat='Binary')
# Set objective function
prob += lpSum([npv[i]*x[i] for i in range(n)])
# Set constraint
for j in range(year):
prob += lpSum([amount[i][j]*x[i] for i in range(n)]) <= capital[j]
# Added multiple choice constraint
prob += lpSum([x[i] for i in range(n)]) == 3
prob.solve()
output(prob)
Status: Optimal
Objective value: 80.0
Variables Values
----------- --------
X_0 1
X_1 0
X_2 1
X_3 0
X_4 1
Statistics:
- Number of variables: 5
- Number of constraints: 5
- Solve time: 0.007s
Multiple choice constraint#
5개의 투자대상 $X_{j}$중에서 3개 이내의 투자대상을 선택하는 제약식
from pulp import *
from ortools.utils import output
n = 5
year = 4
npv = [30, 10, 15, 12, 35]
amount = [
[20, 25, 25, 20],
[10, 20, 15, 10],
[15, 30, 20, 5],
[10, 15, 10, 15],
[25, 30, 30, 25]
]
capital = [70, 90, 80, 60]
# Define problem
prob = LpProblem('Capital Budgeting Problem', LpMaximize)
indexs = [(i) for i in range(n)]
x = LpVariable.dicts('X', indexs, lowBound=0, cat='Binary')
# Set objective function
prob += lpSum([npv[i]*x[i] for i in range(n)])
# Set constraint
for j in range(year):
prob += lpSum([amount[i][j]*x[i] for i in range(n)]) <= capital[j]
# Added multiple choice constraint
prob += lpSum([x[i] for i in range(n)]) <= 3
prob.solve()
output(prob)
Status: Optimal
Objective value: 80.0
Variables Values
----------- --------
X_0 1
X_1 0
X_2 1
X_3 0
X_4 1
Statistics:
- Number of variables: 5
- Number of constraints: 5
- Solve time: 0.007s
Conditional constraint#
만일 투자대상 1($X_{1}$)이 선택되면 투자대상 2($X_{2}$)도 선택되어야 한다는 조건부 선택제약식, 위 제약식은 투자대상 2($X_{2}$)가 선택되더라도 투자대상 1($X_{1}$)이 선택된다는 보장이 없으므로 위 제약식을 조건 부 제약식(conditional constraint)이라고 한다.
from pulp import *
from ortools.utils import output
n = 5
year = 4
npv = [30, 10, 15, 12, 35]
amount = [
[20, 25, 25, 20],
[10, 20, 15, 10],
[15, 30, 20, 5],
[10, 15, 10, 15],
[25, 30, 30, 25]
]
capital = [70, 90, 80, 60]
# Define problem
prob = LpProblem('Capital Budgeting Problem', LpMaximize)
indexs = [(i) for i in range(n)]
x = LpVariable.dicts('X', indexs, lowBound=0, cat='Binary')
# Set objective function
prob += lpSum([npv[i]*x[i] for i in range(n)])
# Set constraint
for j in range(year):
prob += lpSum([amount[i][j]*x[i] for i in range(n)]) <= capital[j]
# Added multiple choice constraint
prob += x[0] - x[1] <= 0
prob.solve()
output(prob)
Status: Optimal
Objective value: 75.0
Variables Values
----------- --------
X_0 1
X_1 1
X_2 0
X_3 0
X_4 1
Statistics:
- Number of variables: 5
- Number of constraints: 5
- Solve time: 0.008s
Corequisite constraint#
투자대상 1($X_{1}$)과 투자대상 2($X_{2}$)가 동시에 선택되거나 동시에 선택되지 않는 제약식, 이를 동시요구 제약식(corequisite constraint)이라고 한다.
from pulp import *
from ortools.utils import output
n = 5
year = 4
npv = [30, 10, 15, 12, 35]
amount = [
[20, 25, 25, 20],
[10, 20, 15, 10],
[15, 30, 20, 5],
[10, 15, 10, 15],
[25, 30, 30, 25]
]
capital = [70, 90, 80, 60]
# Define problem
prob = LpProblem('Capital Budgeting Problem', LpMaximize)
indexs = [(i) for i in range(n)]
x = LpVariable.dicts('X', indexs, lowBound=0, cat='Binary')
# Set objective function
prob += lpSum([npv[i]*x[i] for i in range(n)])
# Set constraint
for j in range(year):
prob += lpSum([amount[i][j]*x[i] for i in range(n)]) <= capital[j]
# Added multiple choice constraint
prob += x[0] - x[1] == 0
prob.solve()
output(prob)
Status: Optimal
Objective value: 75.0
Variables Values
----------- --------
X_0 1
X_1 1
X_2 0
X_3 0
X_4 1
Statistics:
- Number of variables: 5
- Number of constraints: 5
- Solve time: 0.007s
투자대상 1($X_{1}$)과 투자대상 2($X_{2}$) 중에서 반드시 1개의 투자대상만을 선택해야 한다는 양자택일형 제약식
from pulp import *
from ortools.utils import output
n = 5
year = 4
npv = [30, 10, 15, 12, 35]
amount = [
[20, 25, 25, 20],
[10, 20, 15, 10],
[15, 30, 20, 5],
[10, 15, 10, 15],
[25, 30, 30, 25]
]
capital = [70, 90, 80, 60]
# Define problem
prob = LpProblem('Capital Budgeting Problem', LpMaximize)
indexs = [(i) for i in range(n)]
x = LpVariable.dicts('X', indexs, lowBound=0, cat='Binary')
# Set objective function
prob += lpSum([npv[i]*x[i] for i in range(n)])
# Set constraint
for j in range(year):
prob += lpSum([amount[i][j]*x[i] for i in range(n)]) <= capital[j]
# Added multiple choice constraint
prob += x[0] + x[1] == 1
prob.solve()
output(prob)
Status: Optimal
Objective value: 80.0
Variables Values
----------- --------
X_0 1
X_1 0
X_2 1
X_3 0
X_4 1
Statistics:
- Number of variables: 5
- Number of constraints: 5
- Solve time: 0.007s
Mutually exclusive constraint#
투자대상 1($X_{1}$)과 투자대상 2($X_{2}$) 동시에 선택될 수 없다는 제약식, 이는 2개의 투자대상이 전혀 선택되지 않을 수도 있고 선택된다면 꼭 1개가 선택되는 경우이다. 이와 같은 제약식을 상호배타적 제약식(mutually exclusive constraint)이라고 한다.
from pulp import *
from ortools.utils import output
n = 5
year = 4
npv = [30, 10, 15, 12, 35]
amount = [
[20, 25, 25, 20],
[10, 20, 15, 10],
[15, 30, 20, 5],
[10, 15, 10, 15],
[25, 30, 30, 25]
]
capital = [70, 90, 80, 60]
# Define problem
prob = LpProblem('Capital Budgeting Problem', LpMaximize)
indexs = [(i) for i in range(n)]
x = LpVariable.dicts('X', indexs, lowBound=0, cat='Binary')
# Set objective function
prob += lpSum([npv[i]*x[i] for i in range(n)])
# Set constraint
for j in range(year):
prob += lpSum([amount[i][j]*x[i] for i in range(n)]) <= capital[j]
# Added multiple choice constraint
prob += x[0] + x[1] <= 1
prob.solve()
output(prob)
Status: Optimal
Objective value: 80.0
Variables Values
----------- --------
x_0 1
x_1 0
x_2 1
x_3 0
x_4 1
Statistics:
- Number of variables: 5
- Number of constraints: 5
- Solve time: 0.029s
다음은 4개의 제약식 중에서 1개의 제약식만을 선택하는 제약식,
from pulp import *
from ortools.utils import output
n = 5
year = 4
npv = [30, 10, 15, 12, 35]
amount = [
[20, 25, 25, 20],
[10, 20, 15, 10],
[15, 30, 20, 5],
[10, 15, 10, 15],
[25, 30, 30, 25]
]
capital = [70, 90, 80, 60]
M = 1000
# Define problem
prob = LpProblem('Capital Budgeting Problem', LpMaximize)
x1 = LpVariable('X1', lowBound=0, cat='Binary')
x2 = LpVariable('X2', lowBound=0, cat='Binary')
x3 = LpVariable('X3', lowBound=0, cat='Binary')
y = LpVariable('Y', lowBound=0, cat='Binary')
# Set objective function
prob += 30*x1 + 10*x2 + 15*x3
# Set constraint
prob += 20*x1 + 10*x2 + 15*x3 <= 70 + y * M
prob += 25*x1 + 20*x2 + 30*x3 <= 90 + (1 - y) * M
prob.solve()
output(prob)
Status: Optimal
Objective value: 55.0
Variables Values
----------- --------
X1 1
X2 1
X3 1
Y 0
Statistics:
- Number of variables: 4
- Number of constraints: 2
- Solve time: 0.025s
$m$개의 제약식 중에서 $k$개를 선택하는 제약식(단, $k
from pulp import *
from ortools.utils import output
n = 5
year = 4
npv = [30, 10, 15, 12, 35]
amount = [
[20, 25, 25, 20],
[10, 20, 15, 10],
[15, 30, 20, 5],
[10, 15, 10, 15],
[25, 30, 30, 25]
]
capital = [70, 90, 80, 60]
M = 1000
# Define problem
prob = LpProblem('Capital Budgeting Problem', LpMaximize)
indexs = [(i) for i in range(n)]
x = LpVariable.dicts('X', indexs, lowBound=0, cat='Binary')
y = LpVariable.dicts('Y', [i for i in range(n)], lowBound=0, cat='Binary')
# Set objective function
prob += lpSum([npv[i]*x[i] for i in range(n)])
# Set constraint
for j in range(year):
prob += lpSum([amount[i][j]*x[i] for i in range(n)]) <= capital[j]
prob.solve()
output(prob)
Status: Optimal
Objective value: 80.0
Variables Values
----------- --------
X_0 1
X_1 0
X_2 1
X_3 0
X_4 1
Statistics:
- Number of variables: 5
- Number of constraints: 5
- Solve time: 0.029s