{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Capital Budgeting Problem\n", "\n", "**이강우 & 김정자. (2012). EXCEL 2010 경영과학. 한경사, 397.**\n", "\n", "

\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
Table 1. Example
Investment targetsNPV
(net present value)		Investment amount
First yearSecond yearThird yearFourth year
13020252520
21010201510
3151530205
41210151015
53525303025
Capital by year70908060
\n", "\n", "

자본예산문제는 투자대상의 선택문제이므로 결정변수 $X_{j}$를 다음과 같이 이진변수로 정의하자.

\n", "\n", "$$X_{j} = \n", "\\begin{cases}\n", " 1, \\; \\text{if investment target $j$ is selected }(j=1,2,3)\\\\\n", " 0, \\; \\text{otherwise}\n", "\\end{cases}$$\n", "\n", "

\n", "\n", "

\n", "\n", "

\n", "\n", "

" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "import os\n", "import sys\n", "\n", "# Add the parent directory for importing custom library\n", "sys.path.append('../')" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Status: Optimal\n", "Objective value: 80.0\n", "\n", "Variables Values\n", "----------- --------\n", "X_0 1\n", "X_1 0\n", "X_2 1\n", "X_3 0\n", "X_4 1\n", "\n", "Statistics:\n", "- Number of variables: 5\n", "- Number of constraints: 4\n", "- Solve time: 0.004s\n" ] } ], "source": [ "from pulp import *\n", "from ortools.utils import output\n", "\n", "n = 5\n", "year = 4\n", "\n", "npv = [30, 10, 15, 12, 35]\n", "\n", "amount = [\n", " [20, 25, 25, 20],\n", " [10, 20, 15, 10],\n", " [15, 30, 20, 5],\n", " [10, 15, 10, 15],\n", " [25, 30, 30, 25]\n", "]\n", "\n", "capital = [70, 90, 80, 60]\n", "\n", "prob = LpProblem('Capital Budgeting Problem', LpMaximize)\n", "\n", "indexs = [(i) for i in range(n)]\n", "\n", "x = LpVariable.dicts('X', indexs, lowBound=0, cat='Binary')\n", "\n", "prob += lpSum([npv[i]*x[i] for i in range(n)])\n", "\n", "for j in range(year):\n", " prob += lpSum([amount[i][j]*x[i] for i in range(n)]) <= capital[j]\n", " \n", "prob.solve()\n", "output(prob)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Multiple choice constraint\n", "\n", "

5개의 투자대상 $X_{j}$중에서 3개의 투자대상을 선택하는 제약식, 이를 선다형 제약식(multiple choice constraint)라고 한다.

" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Status: Optimal\n", "Objective value: 80.0\n", "\n", "Variables Values\n", "----------- --------\n", "X_0 1\n", "X_1 0\n", "X_2 1\n", "X_3 0\n", "X_4 1\n", "\n", "Statistics:\n", "- Number of variables: 5\n", "- Number of constraints: 5\n", "- Solve time: 0.007s\n" ] } ], "source": [ "from pulp import *\n", "from ortools.utils import output\n", "\n", "n = 5\n", "year = 4\n", "\n", "npv = [30, 10, 15, 12, 35]\n", "\n", "amount = [\n", " [20, 25, 25, 20],\n", " [10, 20, 15, 10],\n", " [15, 30, 20, 5],\n", " [10, 15, 10, 15],\n", " [25, 30, 30, 25]\n", "]\n", "\n", "capital = [70, 90, 80, 60]\n", "\n", "# Define problem\n", "prob = LpProblem('Capital Budgeting Problem', LpMaximize)\n", "\n", "indexs = [(i) for i in range(n)]\n", "\n", "x = LpVariable.dicts('X', indexs, lowBound=0, cat='Binary')\n", "\n", "# Set objective function\n", "prob += lpSum([npv[i]*x[i] for i in range(n)])\n", "\n", "# Set constraint\n", "for j in range(year):\n", " prob += lpSum([amount[i][j]*x[i] for i in range(n)]) <= capital[j]\n", " \n", "# Added multiple choice constraint\n", "prob += lpSum([x[i] for i in range(n)]) == 3\n", " \n", "prob.solve()\n", "output(prob)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Multiple choice constraint\n", "\n", "

5개의 투자대상 $X_{j}$중에서 3개 이내의 투자대상을 선택하는 제약식

" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Status: Optimal\n", "Objective value: 80.0\n", "\n", "Variables Values\n", "----------- --------\n", "X_0 1\n", "X_1 0\n", "X_2 1\n", "X_3 0\n", "X_4 1\n", "\n", "Statistics:\n", "- Number of variables: 5\n", "- Number of constraints: 5\n", "- Solve time: 0.007s\n" ] } ], "source": [ "from pulp import *\n", "from ortools.utils import output\n", "\n", "n = 5\n", "year = 4\n", "\n", "npv = [30, 10, 15, 12, 35]\n", "\n", "amount = [\n", " [20, 25, 25, 20],\n", " [10, 20, 15, 10],\n", " [15, 30, 20, 5],\n", " [10, 15, 10, 15],\n", " [25, 30, 30, 25]\n", "]\n", "\n", "capital = [70, 90, 80, 60]\n", "\n", "# Define problem\n", "prob = LpProblem('Capital Budgeting Problem', LpMaximize)\n", "\n", "indexs = [(i) for i in range(n)]\n", "\n", "x = LpVariable.dicts('X', indexs, lowBound=0, cat='Binary')\n", "\n", "# Set objective function\n", "prob += lpSum([npv[i]*x[i] for i in range(n)])\n", "\n", "# Set constraint\n", "for j in range(year):\n", " prob += lpSum([amount[i][j]*x[i] for i in range(n)]) <= capital[j]\n", " \n", "# Added multiple choice constraint\n", "prob += lpSum([x[i] for i in range(n)]) <= 3\n", " \n", "prob.solve()\n", "output(prob)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Conditional constraint\n", "\n", "

만일 투자대상 1($X_{1}$)이 선택되면 투자대상 2($X_{2}$)도 선택되어야 한다는 조건부 선택제약식, 위 제약식은 투자대상 2($X_{2}$)가 선택되더라도 투자대상 1($X_{1}$)이 선택된다는 보장이 없으므로 위 제약식을 조건 부 제약식(conditional constraint)이라고 한다.

" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Status: Optimal\n", "Objective value: 75.0\n", "\n", "Variables Values\n", "----------- --------\n", "X_0 1\n", "X_1 1\n", "X_2 0\n", "X_3 0\n", "X_4 1\n", "\n", "Statistics:\n", "- Number of variables: 5\n", "- Number of constraints: 5\n", "- Solve time: 0.008s\n" ] } ], "source": [ "from pulp import *\n", "from ortools.utils import output\n", "\n", "n = 5\n", "year = 4\n", "\n", "npv = [30, 10, 15, 12, 35]\n", "\n", "amount = [\n", " [20, 25, 25, 20],\n", " [10, 20, 15, 10],\n", " [15, 30, 20, 5],\n", " [10, 15, 10, 15],\n", " [25, 30, 30, 25]\n", "]\n", "\n", "capital = [70, 90, 80, 60]\n", "\n", "# Define problem\n", "prob = LpProblem('Capital Budgeting Problem', LpMaximize)\n", "\n", "indexs = [(i) for i in range(n)]\n", "\n", "x = LpVariable.dicts('X', indexs, lowBound=0, cat='Binary')\n", "\n", "# Set objective function\n", "prob += lpSum([npv[i]*x[i] for i in range(n)])\n", "\n", "# Set constraint\n", "for j in range(year):\n", " prob += lpSum([amount[i][j]*x[i] for i in range(n)]) <= capital[j]\n", " \n", "# Added multiple choice constraint\n", "prob += x[0] - x[1] <= 0\n", " \n", "prob.solve()\n", "output(prob)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Corequisite constraint\n", "\n", "

투자대상 1($X_{1}$)과 투자대상 2($X_{2}$)가 동시에 선택되거나 동시에 선택되지 않는 제약식, 이를 동시요구 제약식(corequisite constraint)이라고 한다.

" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Status: Optimal\n", "Objective value: 75.0\n", "\n", "Variables Values\n", "----------- --------\n", "X_0 1\n", "X_1 1\n", "X_2 0\n", "X_3 0\n", "X_4 1\n", "\n", "Statistics:\n", "- Number of variables: 5\n", "- Number of constraints: 5\n", "- Solve time: 0.007s\n" ] } ], "source": [ "from pulp import *\n", "from ortools.utils import output\n", "\n", "n = 5\n", "year = 4\n", "\n", "npv = [30, 10, 15, 12, 35]\n", "\n", "amount = [\n", " [20, 25, 25, 20],\n", " [10, 20, 15, 10],\n", " [15, 30, 20, 5],\n", " [10, 15, 10, 15],\n", " [25, 30, 30, 25]\n", "]\n", "\n", "capital = [70, 90, 80, 60]\n", "\n", "# Define problem\n", "prob = LpProblem('Capital Budgeting Problem', LpMaximize)\n", "\n", "indexs = [(i) for i in range(n)]\n", "\n", "x = LpVariable.dicts('X', indexs, lowBound=0, cat='Binary')\n", "\n", "# Set objective function\n", "prob += lpSum([npv[i]*x[i] for i in range(n)])\n", "\n", "# Set constraint\n", "for j in range(year):\n", " prob += lpSum([amount[i][j]*x[i] for i in range(n)]) <= capital[j]\n", " \n", "# Added multiple choice constraint\n", "prob += x[0] - x[1] == 0\n", " \n", "prob.solve()\n", "output(prob)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

투자대상 1($X_{1}$)과 투자대상 2($X_{2}$) 중에서 반드시 1개의 투자대상만을 선택해야 한다는 양자택일형 제약식

" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Status: Optimal\n", "Objective value: 80.0\n", "\n", "Variables Values\n", "----------- --------\n", "X_0 1\n", "X_1 0\n", "X_2 1\n", "X_3 0\n", "X_4 1\n", "\n", "Statistics:\n", "- Number of variables: 5\n", "- Number of constraints: 5\n", "- Solve time: 0.007s\n" ] } ], "source": [ "from pulp import *\n", "from ortools.utils import output\n", "\n", "n = 5\n", "year = 4\n", "\n", "npv = [30, 10, 15, 12, 35]\n", "\n", "amount = [\n", " [20, 25, 25, 20],\n", " [10, 20, 15, 10],\n", " [15, 30, 20, 5],\n", " [10, 15, 10, 15],\n", " [25, 30, 30, 25]\n", "]\n", "\n", "capital = [70, 90, 80, 60]\n", "\n", "# Define problem\n", "prob = LpProblem('Capital Budgeting Problem', LpMaximize)\n", "\n", "indexs = [(i) for i in range(n)]\n", "\n", "x = LpVariable.dicts('X', indexs, lowBound=0, cat='Binary')\n", "\n", "# Set objective function\n", "prob += lpSum([npv[i]*x[i] for i in range(n)])\n", "\n", "# Set constraint\n", "for j in range(year):\n", " prob += lpSum([amount[i][j]*x[i] for i in range(n)]) <= capital[j]\n", " \n", "# Added multiple choice constraint\n", "prob += x[0] + x[1] == 1\n", " \n", "prob.solve()\n", "output(prob)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Mutually exclusive constraint\n", "\n", "

투자대상 1($X_{1}$)과 투자대상 2($X_{2}$) 동시에 선택될 수 없다는 제약식, 이는 2개의 투자대상이 전혀 선택되지 않을 수도 있고 선택된다면 꼭 1개가 선택되는 경우이다. 이와 같은 제약식을 상호배타적 제약식(mutually exclusive constraint)이라고 한다.

" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Status: Optimal\n", "Objective value: 80.0\n", "\n", "Variables Values\n", "----------- --------\n", "x_0 1\n", "x_1 0\n", "x_2 1\n", "x_3 0\n", "x_4 1\n", "\n", "Statistics:\n", "- Number of variables: 5\n", "- Number of constraints: 5\n", "- Solve time: 0.029s\n" ] } ], "source": [ "from pulp import *\n", "from ortools.utils import output\n", "\n", "n = 5\n", "year = 4\n", "\n", "npv = [30, 10, 15, 12, 35]\n", "\n", "amount = [\n", " [20, 25, 25, 20],\n", " [10, 20, 15, 10],\n", " [15, 30, 20, 5],\n", " [10, 15, 10, 15],\n", " [25, 30, 30, 25]\n", "]\n", "\n", "capital = [70, 90, 80, 60]\n", "\n", "# Define problem\n", "prob = LpProblem('Capital Budgeting Problem', LpMaximize)\n", "\n", "indexs = [(i) for i in range(n)]\n", "\n", "x = LpVariable.dicts('X', indexs, lowBound=0, cat='Binary')\n", "\n", "# Set objective function\n", "prob += lpSum([npv[i]*x[i] for i in range(n)])\n", "\n", "# Set constraint\n", "for j in range(year):\n", " prob += lpSum([amount[i][j]*x[i] for i in range(n)]) <= capital[j]\n", " \n", "# Added multiple choice constraint\n", "prob += x[0] + x[1] <= 1\n", " \n", "prob.solve()\n", "output(prob)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

다음은 4개의 제약식 중에서 1개의 제약식만을 선택하는 제약식,

" ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Status: Optimal\n", "Objective value: 55.0\n", "\n", "Variables Values\n", "----------- --------\n", "X1 1\n", "X2 1\n", "X3 1\n", "Y 0\n", "\n", "Statistics:\n", "- Number of variables: 4\n", "- Number of constraints: 2\n", "- Solve time: 0.025s\n" ] } ], "source": [ "from pulp import *\n", "from ortools.utils import output\n", "\n", "n = 5\n", "year = 4\n", "\n", "npv = [30, 10, 15, 12, 35]\n", "\n", "amount = [\n", " [20, 25, 25, 20],\n", " [10, 20, 15, 10],\n", " [15, 30, 20, 5],\n", " [10, 15, 10, 15],\n", " [25, 30, 30, 25]\n", "]\n", "\n", "capital = [70, 90, 80, 60]\n", "\n", "M = 1000\n", "\n", "# Define problem\n", "prob = LpProblem('Capital Budgeting Problem', LpMaximize)\n", "\n", "x1 = LpVariable('X1', lowBound=0, cat='Binary')\n", "x2 = LpVariable('X2', lowBound=0, cat='Binary')\n", "x3 = LpVariable('X3', lowBound=0, cat='Binary')\n", "y = LpVariable('Y', lowBound=0, cat='Binary')\n", "\n", "# Set objective function\n", "prob += 30*x1 + 10*x2 + 15*x3\n", "\n", "# Set constraint\n", "prob += 20*x1 + 10*x2 + 15*x3 <= 70 + y * M\n", "prob += 25*x1 + 20*x2 + 30*x3 <= 90 + (1 - y) * M\n", "\n", "prob.solve()\n", "output(prob)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

$m$개의 제약식 중에서 $k$개를 선택하는 제약식(단, $k" ] }, { "cell_type": "code", "execution_count": 27, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Status: Optimal\n", "Objective value: 80.0\n", "\n", "Variables Values\n", "----------- --------\n", "X_0 1\n", "X_1 0\n", "X_2 1\n", "X_3 0\n", "X_4 1\n", "\n", "Statistics:\n", "- Number of variables: 5\n", "- Number of constraints: 5\n", "- Solve time: 0.029s\n" ] } ], "source": [ "from pulp import *\n", "from ortools.utils import output\n", "\n", "n = 5\n", "year = 4\n", "\n", "npv = [30, 10, 15, 12, 35]\n", "\n", "amount = [\n", " [20, 25, 25, 20],\n", " [10, 20, 15, 10],\n", " [15, 30, 20, 5],\n", " [10, 15, 10, 15],\n", " [25, 30, 30, 25]\n", "]\n", "\n", "capital = [70, 90, 80, 60]\n", "\n", "M = 1000\n", "\n", "# Define problem\n", "prob = LpProblem('Capital Budgeting Problem', LpMaximize)\n", "\n", "indexs = [(i) for i in range(n)]\n", "\n", "x = LpVariable.dicts('X', indexs, lowBound=0, cat='Binary')\n", "y = LpVariable.dicts('Y', [i for i in range(n)], lowBound=0, cat='Binary')\n", "\n", "# Set objective function\n", "prob += lpSum([npv[i]*x[i] for i in range(n)])\n", "\n", "# Set constraint\n", "for j in range(year):\n", " prob += lpSum([amount[i][j]*x[i] for i in range(n)]) <= capital[j]\n", " \n", "prob.solve()\n", "output(prob)" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.3" } }, "nbformat": 4, "nbformat_minor": 4 }