{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# PuLPを使ってみる"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"特に実装すべきアルゴリズムはなかったが、せっかくなのでpythonで線形計画問題を解くためのパッケージ(?)である**PuLP**を使って実際に線形計画問題を解く方法を調べてみた。\n",
"\n",
"[参考にしたサイト](http://qiita.com/Tsutomu-KKE@github/items/070ca9cb37c6b2b492f0)\n",
"\n",
"インストール方法は、\n",
"```\n",
"sudo pip install pulp\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"from pulp import *"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"$$\\max 100x + 100y$$\n",
"\n",
"$$ s.t. \\\\ x + 2y \\leq 16 $$\n",
"\n",
"$$ x + y \\leq 18 $$"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"4.0 6.0\n"
]
}
],
"source": [
"m = LpProblem(sense=LpMaximize) # 数理モデル\n",
"x = LpVariable('x', lowBound=0) # 変数\n",
"y = LpVariable('y', lowBound=0)\n",
"m += 100 * x + 100 * y # 目的関数\n",
"m += x + 2 * y <= 16 #制約1\n",
"m += 3 * x + y <= 18 # 制約2\n",
"m.solve() # ソルバー実行\n",
"print(value(x), value(y))"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"100*x + 100*y\n"
]
}
],
"source": [
"print(m.objective)"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"collapsed": false,
"scrolled": true
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"1000.0\n"
]
}
],
"source": [
"print(value(m.objective))"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"status = m.solve()"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Optimal\n"
]
}
],
"source": [
"print (LpStatus[status])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# PuLP with pandas"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"輸送最適化問題を解く（参考サイトに問題の詳細あり）"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"import numpy as np, pandas as pd\n",
"from itertools import product\n",
"from pulp import *\n",
"\n",
"np.random.seed(1)\n",
"nw, nf = 3, 4\n",
"pr = list(product(range(nw),range(nf)))\n",
"supply = np.random.randint(30, 50, nw)\n",
"demand = np.random.randint(20, 40, nf)\n",
"cost = np.random.randint(10, 20, (nw,nf))"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"{(0, 0): 28.0,\n",
" (0, 1): 7.0,\n",
" (1, 2): 31.0,\n",
" (1, 3): 5.0,\n",
" (2, 1): 22.0,\n",
" (2, 3): 20.0}"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# pandasを使わずにモデリングすると\n",
"\n",
"m1 = LpProblem() # minimizing\n",
"v1 = {(i,j):LpVariable('v%d_%d'%(i,j), lowBound=0) for i,j in pr}\n",
"m1 += lpSum(cost[i][j] * v1[i,j] for i,j in pr) # objective function\n",
"for i in range(nw):\n",
" m1 += lpSum(v1[i,j] for j in range(nf)) <= supply[i]\n",
"for j in range(nf):\n",
" m1 += lpSum(v1[i,j] for i in range(nw)) >= demand[j]\n",
"m1.solve()\n",
"{k:value(x) for k,x in v1.items() if value(x) > 0}"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"{(0, 0): v0_0,\n",
" (0, 1): v0_1,\n",
" (0, 2): v0_2,\n",
" (0, 3): v0_3,\n",
" (1, 0): v1_0,\n",
" (1, 1): v1_1,\n",
" (1, 2): v1_2,\n",
" (1, 3): v1_3,\n",
" (2, 0): v2_0,\n",
" (2, 1): v2_1,\n",
" (2, 2): v2_2,\n",
" (2, 3): v2_3}"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"v1"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"v1_1"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"v1[1,1]"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"dict_items([((0, 1), v0_1), ((1, 2), v1_2), ((0, 0), v0_0), ((1, 1), v1_1), ((2, 1), v2_1), ((0, 2), v0_2), ((2, 0), v2_0), ((1, 3), v1_3), ((2, 3), v2_3), ((2, 2), v2_2), ((1, 0), v1_0), ((0, 3), v0_3)])"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"v1.items()"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/plain": [
"0.0"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"value(v1[1,1])"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/html": [
"<div>\n",
"<table border=\"1\" class=\"dataframe\">\n",
" <thead>\n",
" <tr style=\"text-align: right;\">\n",
" <th></th>\n",
" <th>warehouse</th>\n",
" <th>factory</th>\n",
" <th>cost</th>\n",
" </tr>\n",
" </thead>\n",
" <tbody>\n",
" <tr>\n",
" <th>0</th>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>10</td>\n",
" </tr>\n",
" <tr>\n",
" <th>1</th>\n",
" <td>0</td>\n",
" <td>1</td>\n",
" <td>10</td>\n",
" </tr>\n",
" <tr>\n",
" <th>2</th>\n",
" <td>0</td>\n",
" <td>2</td>\n",
" <td>11</td>\n",
" </tr>\n",
" </tbody>\n",
"</table>\n",
"</div>"
],
"text/plain": [
" warehouse factory cost\n",
"0 0 0 10\n",
"1 0 1 10\n",
"2 0 2 11"
]
},
"execution_count": 20,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# pandasを使ってモデリング\n",
"a = pd.DataFrame([(i,j) for i, j in pr], columns=['warehouse', 'factory'])\n",
"a['cost'] = cost.flatten()\n",
"a[:3]"
]
},
{
"cell_type": "code",
"execution_count": 31,
"metadata": {
"collapsed": false
},
"outputs": [
{
"data": {
"text/html": [
"<div>\n",
"<table border=\"1\" class=\"dataframe\">\n",
" <thead>\n",
" <tr style=\"text-align: right;\">\n",
" <th></th>\n",
" <th>warehouse</th>\n",
" <th>factory</th>\n",
" <th>cost</th>\n",
" <th>Var</th>\n",
" <th>Val</th>\n",
" </tr>\n",
" </thead>\n",
" <tbody>\n",
" <tr>\n",
" <th>0</th>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>10</td>\n",
" <td>v0</td>\n",
" <td>28.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>1</th>\n",
" <td>0</td>\n",
" <td>1</td>\n",
" <td>10</td>\n",
" <td>v1</td>\n",
" <td>7.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>6</th>\n",
" <td>1</td>\n",
" <td>2</td>\n",
" <td>12</td>\n",
" <td>v6</td>\n",
" <td>31.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>7</th>\n",
" <td>1</td>\n",
" <td>3</td>\n",
" <td>14</td>\n",
" <td>v7</td>\n",
" <td>5.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>9</th>\n",
" <td>2</td>\n",
" <td>1</td>\n",
" <td>12</td>\n",
" <td>v9</td>\n",
" <td>22.0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>11</th>\n",
" <td>2</td>\n",
" <td>3</td>\n",
" <td>12</td>\n",
" <td>v11</td>\n",
" <td>20.0</td>\n",
" </tr>\n",
" </tbody>\n",
"</table>\n",
"</div>"
],
"text/plain": [
" warehouse factory cost Var Val\n",
"0 0 0 10 v0 28.0\n",
"1 0 1 10 v1 7.0\n",
"6 1 2 12 v6 31.0\n",
"7 1 3 14 v7 5.0\n",
"9 2 1 12 v9 22.0\n",
"11 2 3 12 v11 20.0"
]
},
"execution_count": 31,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"m2 = LpProblem()\n",
"a['Var'] = [LpVariable('v%d'%i, lowBound=0) for i in a.index]\n",
"m2 += lpDot(a.cost, a.Var)\n",
"for k, v in a.groupby('warehouse'):\n",
" m2 += lpSum(v.Var) <= supply[k]\n",
"for k, v in a.groupby('factory'):\n",
" m2 += lpSum(v.Var) >= demand[k]\n",
"m2.solve()\n",
"a['Val'] = a.Var.apply(value)\n",
"a[a.Val > 0]"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {
"collapsed": true
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"0\n",
"1\n",
"2\n",
"3\n",
"4\n",
"5\n",
"6\n",
"7\n",
"8\n",
"9\n",
"10\n",
"11\n"
]
}
],
"source": [
"for i in a.index:\n",
" print (i)"
]
},
{
"cell_type": "code",
"execution_count": 32,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"0\n",
"0 v0\n",
"1 v1\n",
"2 v2\n",
"3 v3\n",
"Name: Var, dtype: object\n",
"1\n",
"4 v4\n",
"5 v5\n",
"6 v6\n",
"7 v7\n",
"Name: Var, dtype: object\n",
"2\n",
"8 v8\n",
"9 v9\n",
"10 v10\n",
"11 v11\n",
"Name: Var, dtype: object\n"
]
}
],
"source": [
"for k, v in a.groupby('warehouse'):\n",
" print (k)\n",
" print (v.Var)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
}
],
"metadata": {
"anaconda-cloud": {},
"kernelspec": {
"display_name": "Python [conda root]",
"language": "python",
"name": "conda-root-py"
},
"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.5.2"
},
"toc": {
"nav_menu": {
"height": "48px",
"width": "252px"
},
"navigate_menu": true,
"number_sections": true,
"sideBar": true,
"threshold": 4,
"toc_cell": false,
"toc_section_display": "block",
"toc_window_display": false
}
},
"nbformat": 4,
"nbformat_minor": 1
}