Skip to content

Instantly share code, notes, and snippets.

@xpl

xpl/linear_programming_example.ipynb

Last active February 20, 2020 10:37
Show Gist options
  • Save xpl/ef3f6eff113e393ee56f7a24e2476d57 to your computer and use it in GitHub Desktop.
Save xpl/ef3f6eff113e393ee56f7a24e2476d57 to your computer and use it in GitHub Desktop.
Download ZIP
Display the source blob
Display the rendered blob
Raw
linear_programming_example.ipynb
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# An exercise in linear optimization (aka linear programming)"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [
{
"data": {
"application/javascript": [
"IPython.OutputArea.prototype._should_scroll = lines => false // prevents scrolling in dataframes"
],
"text/plain": [
"<IPython.core.display.Javascript object>"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"%%javascript\n",
"IPython.OutputArea.prototype._should_scroll = lines => false // prevents scrolling in dataframes"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"from ipynb.fs.defs.common import *\n",
"\n",
"from scipy.optimize import linprog\n",
"from scipy.spatial import distance"
]
},
{
"cell_type": "code",
"execution_count": 318,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"<div>\n",
"<style scoped>\n",
" .dataframe tbody tr th:only-of-type {\n",
" vertical-align: middle;\n",
" }\n",
"\n",
" .dataframe tbody tr th {\n",
" vertical-align: top;\n",
" }\n",
"\n",
" .dataframe thead th {\n",
" text-align: right;\n",
" }\n",
"</style>\n",
"<table border=\"1\" class=\"dataframe\">\n",
" <thead>\n",
" <tr style=\"text-align: right;\">\n",
" <th></th>\n",
" <th>x</th>\n",
" <th>y</th>\n",
" <th>supply</th>\n",
" </tr>\n",
" <tr>\n",
" <th>fact</th>\n",
" <th></th>\n",
" <th></th>\n",
" <th></th>\n",
" </tr>\n",
" </thead>\n",
" <tbody>\n",
" <tr>\n",
" <th>F_01</th>\n",
" <td>59.250276</td>\n",
" <td>59.871183</td>\n",
" <td>389</td>\n",
" </tr>\n",
" <tr>\n",
" <th>F_02</th>\n",
" <td>84.739320</td>\n",
" <td>14.179336</td>\n",
" <td>409</td>\n",
" </tr>\n",
" <tr>\n",
" <th>F_03</th>\n",
" <td>42.397937</td>\n",
" <td>42.474530</td>\n",
" <td>124</td>\n",
" </tr>\n",
" <tr>\n",
" <th>F_04</th>\n",
" <td>19.539202</td>\n",
" <td>13.714643</td>\n",
" <td>70</td>\n",
" </tr>\n",
" <tr>\n",
" <th>F_05</th>\n",
" <td>41.280669</td>\n",
" <td>37.860993</td>\n",
" <td>386</td>\n",
" </tr>\n",
" <tr>\n",
" <th>F_06</th>\n",
" <td>37.159066</td>\n",
" <td>41.353602</td>\n",
" <td>196</td>\n",
" </tr>\n",
" <tr>\n",
" <th>F_07</th>\n",
" <td>96.890453</td>\n",
" <td>64.420010</td>\n",
" <td>394</td>\n",
" </tr>\n",
" <tr>\n",
" <th>F_08</th>\n",
" <td>86.267499</td>\n",
" <td>81.662811</td>\n",
" <td>365</td>\n",
" </tr>\n",
" </tbody>\n",
"</table>\n",
"</div>"
],
"text/plain": [
" x y supply\n",
"fact \n",
"F_01 59.250276 59.871183 389\n",
"F_02 84.739320 14.179336 409\n",
"F_03 42.397937 42.474530 124\n",
"F_04 19.539202 13.714643 70\n",
"F_05 41.280669 37.860993 386\n",
"F_06 37.159066 41.353602 196\n",
"F_07 96.890453 64.420010 394\n",
"F_08 86.267499 81.662811 365"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/html": [
"<div>\n",
"<style scoped>\n",
" .dataframe tbody tr th:only-of-type {\n",
" vertical-align: middle;\n",
" }\n",
"\n",
" .dataframe tbody tr th {\n",
" vertical-align: top;\n",
" }\n",
"\n",
" .dataframe thead th {\n",
" text-align: right;\n",
" }\n",
"</style>\n",
"<table border=\"1\" class=\"dataframe\">\n",
" <thead>\n",
" <tr style=\"text-align: right;\">\n",
" <th></th>\n",
" <th>x</th>\n",
" <th>y</th>\n",
" <th>demand</th>\n",
" </tr>\n",
" <tr>\n",
" <th>shop</th>\n",
" <th></th>\n",
" <th></th>\n",
" <th></th>\n",
" </tr>\n",
" </thead>\n",
" <tbody>\n",
" <tr>\n",
" <th>S_01</th>\n",
" <td>13.490869</td>\n",
" <td>73.269974</td>\n",
" <td>200</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_02</th>\n",
" <td>85.435435</td>\n",
" <td>66.637250</td>\n",
" <td>20</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_03</th>\n",
" <td>28.578297</td>\n",
" <td>8.997380</td>\n",
" <td>320</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_04</th>\n",
" <td>31.324145</td>\n",
" <td>91.839907</td>\n",
" <td>360</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_05</th>\n",
" <td>40.338575</td>\n",
" <td>15.487028</td>\n",
" <td>360</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_06</th>\n",
" <td>41.642451</td>\n",
" <td>42.121572</td>\n",
" <td>120</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_07</th>\n",
" <td>53.983692</td>\n",
" <td>20.950457</td>\n",
" <td>360</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_08</th>\n",
" <td>75.761895</td>\n",
" <td>87.067552</td>\n",
" <td>60</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_09</th>\n",
" <td>81.836739</td>\n",
" <td>36.799647</td>\n",
" <td>80</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_10</th>\n",
" <td>54.260517</td>\n",
" <td>25.920108</td>\n",
" <td>100</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_11</th>\n",
" <td>67.918105</td>\n",
" <td>68.108601</td>\n",
" <td>340</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_12</th>\n",
" <td>92.200710</td>\n",
" <td>10.898110</td>\n",
" <td>360</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_13</th>\n",
" <td>19.966539</td>\n",
" <td>39.046271</td>\n",
" <td>60</td>\n",
" </tr>\n",
" </tbody>\n",
"</table>\n",
"</div>"
],
"text/plain": [
" x y demand\n",
"shop \n",
"S_01 13.490869 73.269974 200\n",
"S_02 85.435435 66.637250 20\n",
"S_03 28.578297 8.997380 320\n",
"S_04 31.324145 91.839907 360\n",
"S_05 40.338575 15.487028 360\n",
"S_06 41.642451 42.121572 120\n",
"S_07 53.983692 20.950457 360\n",
"S_08 75.761895 87.067552 60\n",
"S_09 81.836739 36.799647 80\n",
"S_10 54.260517 25.920108 100\n",
"S_11 67.918105 68.108601 340\n",
"S_12 92.200710 10.898110 360\n",
"S_13 19.966539 39.046271 60"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"# Supply and demand given in units per week\n",
"\n",
"factories = pd.DataFrame ([\n",
" ['F_01', 59.250276, 59.871183, 389],\n",
" ['F_02', 84.739320, 14.179336, 409],\n",
" ['F_03', 42.397937, 42.474530, 124],\n",
" ['F_04', 19.539202, 13.714643, 70],\n",
" ['F_05', 41.280669, 37.860993, 386],\n",
" ['F_06', 37.159066, 41.353602, 196],\n",
" ['F_07', 96.890453, 64.420010, 394],\n",
" ['F_08', 86.267499, 81.662811, 365],\n",
" \n",
"], columns=['fact', 'x', 'y', 'supply']).set_index ('fact')\n",
"\n",
"shops = pd.DataFrame ([\n",
" ['S_01', 13.490869, 73.269974, 200],\n",
" ['S_02', 85.435435, 66.637250, 20],\n",
" ['S_03', 28.578297, 8.997380, 320],\n",
" ['S_04', 31.324145, 91.839907, 360],\n",
" ['S_05', 40.338575, 15.487028, 360],\n",
" ['S_06', 41.642451, 42.121572, 120],\n",
" ['S_07', 53.983692, 20.950457, 360],\n",
" ['S_08', 75.761895, 87.067552, 60],\n",
" ['S_09', 81.836739, 36.799647, 80],\n",
" ['S_10', 54.260517, 25.920108, 100],\n",
" ['S_11', 67.918105, 68.108601, 340],\n",
" ['S_12', 92.200710, 10.898110, 360],\n",
" ['S_13', 19.966539, 39.046271, 60],\n",
" \n",
"], columns=['shop', 'x', 'y', 'demand']).set_index ('shop')\n",
"\n",
"unit_revenue = 1200\n",
"unit_production_cost = 200\n",
"unit_delivery_cost_per_km = 20\n",
"shop_rent_cost = 100000\n",
"\n",
"# Route units from factories to shops in a way that maximizes total revenue.\n",
"# You can close unprofitable shops. \n",
"\n",
"display (factories)\n",
"display (shops)\n",
"\n",
"N_facts = len (factories)\n",
"N_shops = len (shops)"
]
},
{
"cell_type": "code",
"execution_count": 327,
"metadata": {},
"outputs": [
{
"data": {
"text/markdown": [
"# Unit profits:"
],
"text/plain": [
"<IPython.core.display.Markdown object>"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/html": [
"<div>\n",
"<style scoped>\n",
" .dataframe tbody tr th:only-of-type {\n",
" vertical-align: middle;\n",
" }\n",
"\n",
" .dataframe tbody tr th {\n",
" vertical-align: top;\n",
" }\n",
"\n",
" .dataframe thead th {\n",
" text-align: right;\n",
" }\n",
"</style>\n",
"<table border=\"1\" class=\"dataframe\">\n",
" <thead>\n",
" <tr style=\"text-align: right;\">\n",
" <th>fact</th>\n",
" <th>F_01</th>\n",
" <th>F_02</th>\n",
" <th>F_03</th>\n",
" <th>F_04</th>\n",
" <th>F_05</th>\n",
" <th>F_06</th>\n",
" <th>F_07</th>\n",
" <th>F_08</th>\n",
" </tr>\n",
" <tr>\n",
" <th>shop</th>\n",
" <th></th>\n",
" <th></th>\n",
" <th></th>\n",
" <th></th>\n",
" <th></th>\n",
" <th></th>\n",
" <th></th>\n",
" <th></th>\n",
" </tr>\n",
" </thead>\n",
" <tbody>\n",
" <tr>\n",
" <th>S_01</th>\n",
" <td>46.385627</td>\n",
" <td>-851.274725</td>\n",
" <td>155.256737</td>\n",
" <td>-197.233441</td>\n",
" <td>99.762494</td>\n",
" <td>205.308022</td>\n",
" <td>-677.356548</td>\n",
" <td>-465.179523</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_02</th>\n",
" <td>459.096232</td>\n",
" <td>-49.250650</td>\n",
" <td>12.870166</td>\n",
" <td>-690.339120</td>\n",
" <td>-54.080894</td>\n",
" <td>-89.930394</td>\n",
" <td>766.647399</td>\n",
" <td>699.028364</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_03</th>\n",
" <td>-188.093284</td>\n",
" <td>-127.991697</td>\n",
" <td>275.651459</td>\n",
" <td>796.080596</td>\n",
" <td>369.299307</td>\n",
" <td>330.506251</td>\n",
" <td>-759.342897</td>\n",
" <td>-855.619453</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_04</th>\n",
" <td>151.031660</td>\n",
" <td>-885.136091</td>\n",
" <td>-11.843726</td>\n",
" <td>-580.182490</td>\n",
" <td>-97.789693</td>\n",
" <td>-16.447401</td>\n",
" <td>-421.378415</td>\n",
" <td>-117.559024</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_05</th>\n",
" <td>35.094689</td>\n",
" <td>111.600042</td>\n",
" <td>458.680783</td>\n",
" <td>582.504963</td>\n",
" <td>552.124191</td>\n",
" <td>478.774932</td>\n",
" <td>-495.667294</td>\n",
" <td>-611.049387</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_06</th>\n",
" <td>499.966324</td>\n",
" <td>-27.250441</td>\n",
" <td>983.322609</td>\n",
" <td>280.136893</td>\n",
" <td>914.481769</td>\n",
" <td>909.026336</td>\n",
" <td>-191.564025</td>\n",
" <td>-192.460396</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_07</th>\n",
" <td>214.491294</td>\n",
" <td>370.156612</td>\n",
" <td>511.117422</td>\n",
" <td>296.073897</td>\n",
" <td>576.995025</td>\n",
" <td>471.093065</td>\n",
" <td>-221.571476</td>\n",
" <td>-375.243124</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_08</th>\n",
" <td>363.674282</td>\n",
" <td>-468.779928</td>\n",
" <td>-113.856598</td>\n",
" <td>-848.419916</td>\n",
" <td>-201.705521</td>\n",
" <td>-196.652603</td>\n",
" <td>380.539873</td>\n",
" <td>763.712937</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_09</th>\n",
" <td>354.261947</td>\n",
" <td>543.884468</td>\n",
" <td>203.100157</td>\n",
" <td>-328.743847</td>\n",
" <td>188.600895</td>\n",
" <td>101.816729</td>\n",
" <td>370.874017</td>\n",
" <td>98.371447</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_10</th>\n",
" <td>313.684274</td>\n",
" <td>346.760944</td>\n",
" <td>592.682094</td>\n",
" <td>263.917643</td>\n",
" <td>647.261463</td>\n",
" <td>539.282141</td>\n",
" <td>-148.834870</td>\n",
" <td>-285.565375</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_11</th>\n",
" <td>760.846229</td>\n",
" <td>-129.835191</td>\n",
" <td>276.568021</td>\n",
" <td>-455.914959</td>\n",
" <td>193.905518</td>\n",
" <td>184.659960</td>\n",
" <td>415.875817</td>\n",
" <td>543.747057</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_12</th>\n",
" <td>-180.524117</td>\n",
" <td>836.980020</td>\n",
" <td>-179.387383</td>\n",
" <td>-454.321505</td>\n",
" <td>-152.362380</td>\n",
" <td>-258.112804</td>\n",
" <td>-74.539430</td>\n",
" <td>-420.259962</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_13</th>\n",
" <td>110.755612</td>\n",
" <td>-387.642262</td>\n",
" <td>546.162771</td>\n",
" <td>493.295355</td>\n",
" <td>573.058776</td>\n",
" <td>653.066715</td>\n",
" <td>-620.014219</td>\n",
" <td>-576.323162</td>\n",
" </tr>\n",
" </tbody>\n",
"</table>\n",
"</div>"
],
"text/plain": [
"fact F_01 F_02 F_03 F_04 F_05 F_06 \\\n",
"shop \n",
"S_01 46.385627 -851.274725 155.256737 -197.233441 99.762494 205.308022 \n",
"S_02 459.096232 -49.250650 12.870166 -690.339120 -54.080894 -89.930394 \n",
"S_03 -188.093284 -127.991697 275.651459 796.080596 369.299307 330.506251 \n",
"S_04 151.031660 -885.136091 -11.843726 -580.182490 -97.789693 -16.447401 \n",
"S_05 35.094689 111.600042 458.680783 582.504963 552.124191 478.774932 \n",
"S_06 499.966324 -27.250441 983.322609 280.136893 914.481769 909.026336 \n",
"S_07 214.491294 370.156612 511.117422 296.073897 576.995025 471.093065 \n",
"S_08 363.674282 -468.779928 -113.856598 -848.419916 -201.705521 -196.652603 \n",
"S_09 354.261947 543.884468 203.100157 -328.743847 188.600895 101.816729 \n",
"S_10 313.684274 346.760944 592.682094 263.917643 647.261463 539.282141 \n",
"S_11 760.846229 -129.835191 276.568021 -455.914959 193.905518 184.659960 \n",
"S_12 -180.524117 836.980020 -179.387383 -454.321505 -152.362380 -258.112804 \n",
"S_13 110.755612 -387.642262 546.162771 493.295355 573.058776 653.066715 \n",
"\n",
"fact F_07 F_08 \n",
"shop \n",
"S_01 -677.356548 -465.179523 \n",
"S_02 766.647399 699.028364 \n",
"S_03 -759.342897 -855.619453 \n",
"S_04 -421.378415 -117.559024 \n",
"S_05 -495.667294 -611.049387 \n",
"S_06 -191.564025 -192.460396 \n",
"S_07 -221.571476 -375.243124 \n",
"S_08 380.539873 763.712937 \n",
"S_09 370.874017 98.371447 \n",
"S_10 -148.834870 -285.565375 \n",
"S_11 415.875817 543.747057 \n",
"S_12 -74.539430 -420.259962 \n",
"S_13 -620.014219 -576.323162 "
]
},
"execution_count": 327,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"to_df = lambda arr: pd.DataFrame (arr, index=shops.index, columns=factories.index)\n",
"\n",
"factories_vs_shops = lambda fn: [[*(fn (f, s) for _, f in factories.iterrows ())] for _, s in shops.iterrows ()]\n",
"unit_delivery_cost = lambda f, s: (distance.euclidean ((f.x, f.y), (s.x, s.y)) * unit_delivery_cost_per_km)\n",
"unit_profit = lambda f, s: unit_revenue - (unit_production_cost + unit_delivery_cost (f, s))\n",
"unit_profits = factories_vs_shops (unit_profit)\n",
"\n",
"md ('# Unit profits:')\n",
"\n",
"to_df (unit_profits)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Naive brute-force units distribution"
]
},
{
"cell_type": "code",
"execution_count": 321,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"<div>\n",
"<style scoped>\n",
" .dataframe tbody tr th:only-of-type {\n",
" vertical-align: middle;\n",
" }\n",
"\n",
" .dataframe tbody tr th {\n",
" vertical-align: top;\n",
" }\n",
"\n",
" .dataframe thead th {\n",
" text-align: right;\n",
" }\n",
"</style>\n",
"<table border=\"1\" class=\"dataframe\">\n",
" <thead>\n",
" <tr style=\"text-align: right;\">\n",
" <th>fact</th>\n",
" <th>F_01</th>\n",
" <th>F_02</th>\n",
" <th>F_03</th>\n",
" <th>F_04</th>\n",
" <th>F_05</th>\n",
" <th>F_06</th>\n",
" <th>F_07</th>\n",
" <th>F_08</th>\n",
" <th>profit</th>\n",
" <th>rent</th>\n",
" <th>total</th>\n",
" </tr>\n",
" <tr>\n",
" <th>shop</th>\n",
" <th></th>\n",
" <th></th>\n",
" <th></th>\n",
" <th></th>\n",
" <th></th>\n",
" <th></th>\n",
" <th></th>\n",
" <th></th>\n",
" <th></th>\n",
" <th></th>\n",
" <th></th>\n",
" </tr>\n",
" </thead>\n",
" <tbody>\n",
" <tr>\n",
" <th>S_01</th>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>43</td>\n",
" <td></td>\n",
" <td>-29126.3</td>\n",
" <td>100000</td>\n",
" <td>-129126</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_02</th>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>20</td>\n",
" <td></td>\n",
" <td>15332.9</td>\n",
" <td>100000</td>\n",
" <td>-84667.1</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_03</th>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>70</td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>55725.6</td>\n",
" <td>100000</td>\n",
" <td>-44274.4</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_04</th>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>55</td>\n",
" <td>305</td>\n",
" <td>-59031.3</td>\n",
" <td>100000</td>\n",
" <td>-159031</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_05</th>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>136</td>\n",
" <td>224</td>\n",
" <td></td>\n",
" <td>-45916.1</td>\n",
" <td>100000</td>\n",
" <td>-145916</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_06</th>\n",
" <td></td>\n",
" <td></td>\n",
" <td>120</td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>117999</td>\n",
" <td>100000</td>\n",
" <td>17998.7</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_07</th>\n",
" <td>49</td>\n",
" <td></td>\n",
" <td>4</td>\n",
" <td></td>\n",
" <td>286</td>\n",
" <td></td>\n",
" <td>21</td>\n",
" <td></td>\n",
" <td>172922</td>\n",
" <td>100000</td>\n",
" <td>72922.1</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_08</th>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>60</td>\n",
" <td>45822.8</td>\n",
" <td>100000</td>\n",
" <td>-54177.2</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_09</th>\n",
" <td></td>\n",
" <td>49</td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>31</td>\n",
" <td></td>\n",
" <td>38147.4</td>\n",
" <td>100000</td>\n",
" <td>-61852.6</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_10</th>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>100</td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>64726.1</td>\n",
" <td>100000</td>\n",
" <td>-35273.9</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_11</th>\n",
" <td>340</td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>258688</td>\n",
" <td>100000</td>\n",
" <td>158688</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_12</th>\n",
" <td></td>\n",
" <td>360</td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>301313</td>\n",
" <td>100000</td>\n",
" <td>201313</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_13</th>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>60</td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>39184</td>\n",
" <td>100000</td>\n",
" <td>-60816</td>\n",
" </tr>\n",
" <tr>\n",
" <th></th>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" </tr>\n",
" <tr>\n",
" <th>total</th>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>975787</td>\n",
" <td>1.3e+06</td>\n",
" <td>-324213</td>\n",
" </tr>\n",
" </tbody>\n",
"</table>\n",
"</div>"
],
"text/plain": [
"fact F_01 F_02 F_03 F_04 F_05 F_06 F_07 F_08 profit rent total\n",
"shop \n",
"S_01 43 -29126.3 100000 -129126\n",
"S_02 20 15332.9 100000 -84667.1\n",
"S_03 70 55725.6 100000 -44274.4\n",
"S_04 55 305 -59031.3 100000 -159031\n",
"S_05 136 224 -45916.1 100000 -145916\n",
"S_06 120 117999 100000 17998.7\n",
"S_07 49 4 286 21 172922 100000 72922.1\n",
"S_08 60 45822.8 100000 -54177.2\n",
"S_09 49 31 38147.4 100000 -61852.6\n",
"S_10 100 64726.1 100000 -35273.9\n",
"S_11 340 258688 100000 158688\n",
"S_12 360 301313 100000 201313\n",
"S_13 60 39184 100000 -60816\n",
" \n",
"total 975787 1.3e+06 -324213"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"\u001b[35mGrand total: -324213.4236304104\u001b[0m\n"
]
}
],
"source": [
"max_supply = factories.supply.values\n",
"max_demand = shops.demand.values\n",
"\n",
"max_total_supply = np.sum (max_supply)\n",
"\n",
"def solve_naive ():\n",
" \n",
" # Start with zeroes\n",
" units = np.zeros ((N_shops, N_facts))\n",
"\n",
" # For each unit of supply, put it to where it seems most useful:\n",
" #\n",
" for i in range(0, max_total_supply):\n",
"\n",
" supply = np.sum (units, axis=0)\n",
" demand = np.sum (units, axis=1)\n",
"\n",
" best_loc = None\n",
"\n",
" for f in range(0, len (supply)):\n",
" if supply[f] < max_supply[f]:\n",
" for s in range (0, len (demand)):\n",
" if demand[s] < max_demand[s]:\n",
" if not best_loc or unit_profits[s][f] > unit_profits[best_loc[0]][best_loc[1]]:\n",
" best_loc = (s, f)\n",
" best_profit = unit_profits[s][f]\n",
"\n",
" s, f = best_loc\n",
" units[s][f] += 1\n",
" \n",
" return units\n",
"\n",
"def check_results (units, shops_open = np.ones (N_shops)):\n",
"\n",
" supply = np.sum (units, axis=0)\n",
" demand = np.sum (units, axis=1)\n",
" \n",
" df = to_df (units).replace (0.0, '')\n",
" \n",
" shop_profits = to_df (units * unit_profits).sum (axis=1)\n",
" \n",
" df['profit'] = shop_profits\n",
" df['rent'] = np.array (shops_open) * shop_rent_cost\n",
" df['total'] = shop_profits - df['rent']\n",
"\n",
" df.loc[''] = None\n",
" df.loc['total'] = df.sum (axis=0)\n",
" \n",
" display (df.fillna (''))\n",
" \n",
" grand_total = df['total']['total']\n",
" \n",
" cprint (f'Grand total: {grand_total}', 'magenta')\n",
" \n",
" # All supply should be used\n",
" assert (max_total_supply == np.sum (supply))\n",
"\n",
" # Supply & demand constraints should be satisfied!\n",
" assert (np.alltrue (np.round (supply) == max_supply) and np.alltrue (np.round (demand) <= max_demand))\n",
" \n",
"check_results (solve_naive ())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Meet `scipy.optimize.linprog`\n",
"\n",
"<img width=\"795\" alt=\"Screen Shot 2019-11-03 at 17 41 23\" src=\"https://user-images.githubusercontent.com/1707/68086864-2d7d9b00-fe61-11e9-8f93-b10123fdbc11.png\">"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Encoding our problem as `linprog` parameters\n",
"\n",
"So we need to find `min(c·x)`! Okay...\n",
"\n",
"- let `c` be our profit multipliers, negated (to make it a minimization, not maximization task)\n",
"- let `x` be our supply values (results)\n",
"\n",
"Then `c·x` would give the -profit which we want to minimize:\n",
"\n",
"```\n",
"c: x: c·x:\n",
"\n",
"S_01 F_01 -0.44 \n",
" F_02 -1.56 \n",
" F_03 -0.30 · 40 0 0 130 0 17 = -0.44*40 + -1.56*0 + -0.30*130 + ...\n",
"S_02 F_01 0.07 \n",
" F_02 -0.56\n",
" F_03 -0.48\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 322,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"shop fact\n",
"S_01 F_01 -46.385627\n",
" F_02 851.274725\n",
" F_03 -155.256737\n",
" F_04 197.233441\n",
" F_05 -99.762494\n",
" F_06 -205.308022\n",
" F_07 677.356548\n",
" F_08 465.179523\n",
"S_02 F_01 -459.096232\n",
" F_02 49.250650\n",
" F_03 -12.870166\n",
" F_04 690.339120\n",
"dtype: float64"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"# This will be our c-vector...\n",
"\n",
"unit_profits_vector = to_df (unit_profits).stack ()\n",
"\n",
"display (-unit_profits_vector[:12])\n",
"\n",
"c = -unit_profits_vector.values"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## What about the constraints (inequalities)? How to encode them?\n",
"\n",
"- That `A_ub · x <= b_ub` can definitely help with putting constraints on sums of various subsets of `x`\n",
"- And `lb <= x <= ub` can be used for setting min/max supply values per each shop, i.e. `0 <= x <= demand`, but that would be redundant, as `0 <= x` is the default, and the demand requirements are already encoded in `A_ub` and `b_ub`\n",
"\n",
"### Encoding the limitation that sum of supplies per factory <= factory's supply\n",
"\n",
"The matrix multiplication (aka dot product) `A_ub · x` can be used to produce a new vector containing multiple sums of arbitrary subsets of `x`:\n",
"\n",
"```\n",
"A_ub: x: A_ub · x: b_ub:\n",
"\n",
"1 0 0 1 0 0 s1__F1 s1__F1 + s2__F1 <= max_supply[0]\n",
"0 1 0 0 1 0 s1__F2 s1__F2 + s2__F2 <= max_supply[1]\n",
"0 0 1 0 0 1 s1__F3 s1__F3 + s2__F3 <= max_supply[2]\n",
" s2__F1 \n",
" s2__F2\n",
" s2__F3\n",
"```\n",
"\n",
"### Adding the limitation that sum of supplies per shop <= shop's demand\n",
"\n",
"Again, we can simply add more rows to `A_ub` and more components to `b_ub` encoding the needed constraint: \n",
"\n",
"```\n",
"A_ub: x: A_ub · x: b_ub:\n",
"\n",
"1 0 0 1 0 0 s1__F1 s1__F1 + s2__F1 <= max_supply[0]\n",
"0 1 0 0 1 0 s1__F2 s1__F2 + s2__F2 <= max_supply[1]\n",
"0 0 1 0 0 1 s1__F3 s1__F3 + s2__F3 <= max_supply[2]\n",
" +++ s2__F1\n",
"1 1 1 0 0 0 s2__F2 s1__F1 + s1__F2 + s1__F3 <= max_demand[0]\n",
"0 0 0 1 1 1 s2__F3 s2__F1 + s2__F2 + s2__F3 <= max_demand[1]\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 323,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"array([[1., 0., 0., 1., 0., 0.],\n",
" [0., 1., 0., 0., 1., 0.],\n",
" [0., 0., 1., 0., 0., 1.]])"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
"array([[1., 1., 1., 0., 0., 0.],\n",
" [0., 0., 0., 1., 1., 1.]])"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"Optimization terminated successfully.\n",
" Current function value: -1190121.117988\n",
" Iterations: 17\n",
"\u001b[31m\n",
"Supply used: 1781.0, all supply: 2333\u001b[0m\n"
]
}
],
"source": [
"# This is how we can build a matrix for A_ub, with example N_facts=3 and N_shops=2:\n",
"\n",
"display (np.tile (np.eye (3), 2))\n",
"display (np.repeat (np.eye (2), 3, axis=1))\n",
"\n",
"factory_supply_constraints = np.tile (np.eye (N_facts), N_shops)\n",
"shop_demand_constraints = np.repeat (np.eye (N_shops), N_facts, axis=1)\n",
"\n",
"result = linprog (c = c,\n",
" A_ub = np.vstack ((factory_supply_constraints, shop_demand_constraints)),\n",
" b_ub = np.hstack ((max_supply, max_demand)),\n",
" options = { 'disp': True, 'maxiter': 50000 }).x\n",
"\n",
"cprint (f'\\nSupply used: {np.sum (result)}, all supply: {max_supply.sum ()}', 'red')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Forcing it to use all the factories' supply\n",
"\n",
"There is a problem with the previous solution: it didn't use all the supply. For that, there is an additional strict equality constraint in `linprog` that can be set:\n",
"\n",
"- `A_eq · x <= b_eq`\n",
"\n",
"```\n",
"A_eq: x: A_eq · x: b_eq:\n",
"\n",
"1 0 0 1 0 0 s1__F1 s1__F1 + s2__F1 == max_supply[0]\n",
"0 1 0 0 1 0 s1__F2 s1__F2 + s2__F2 == max_supply[1]\n",
"0 0 1 0 0 1 s1__F3 s1__F3 + s2__F3 == max_supply[2]\n",
" s2__F1 \n",
" s2__F2\n",
" s2__F3\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 324,
"metadata": {
"scrolled": true
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Optimization terminated successfully.\n",
" Current function value: -1104041.869927\n",
" Iterations: 75\n"
]
},
{
"data": {
"text/html": [
"<div>\n",
"<style scoped>\n",
" .dataframe tbody tr th:only-of-type {\n",
" vertical-align: middle;\n",
" }\n",
"\n",
" .dataframe tbody tr th {\n",
" vertical-align: top;\n",
" }\n",
"\n",
" .dataframe thead th {\n",
" text-align: right;\n",
" }\n",
"</style>\n",
"<table border=\"1\" class=\"dataframe\">\n",
" <thead>\n",
" <tr style=\"text-align: right;\">\n",
" <th>fact</th>\n",
" <th>F_01</th>\n",
" <th>F_02</th>\n",
" <th>F_03</th>\n",
" <th>F_04</th>\n",
" <th>F_05</th>\n",
" <th>F_06</th>\n",
" <th>F_07</th>\n",
" <th>F_08</th>\n",
" <th>profit</th>\n",
" <th>rent</th>\n",
" <th>total</th>\n",
" </tr>\n",
" <tr>\n",
" <th>shop</th>\n",
" <th></th>\n",
" <th></th>\n",
" <th></th>\n",
" <th></th>\n",
" <th></th>\n",
" <th></th>\n",
" <th></th>\n",
" <th></th>\n",
" <th></th>\n",
" <th></th>\n",
" <th></th>\n",
" </tr>\n",
" </thead>\n",
" <tbody>\n",
" <tr>\n",
" <th>S_01</th>\n",
" <td>43</td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>1994.58</td>\n",
" <td>100000</td>\n",
" <td>-98005.4</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_02</th>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>20</td>\n",
" <td></td>\n",
" <td>15332.9</td>\n",
" <td>100000</td>\n",
" <td>-84667.1</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_03</th>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>70</td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>55725.6</td>\n",
" <td>100000</td>\n",
" <td>-44274.4</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_04</th>\n",
" <td>101</td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>259</td>\n",
" <td>-15193.6</td>\n",
" <td>100000</td>\n",
" <td>-115194</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_05</th>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>224</td>\n",
" <td>136</td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>188789</td>\n",
" <td>100000</td>\n",
" <td>88789.2</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_06</th>\n",
" <td></td>\n",
" <td></td>\n",
" <td>120</td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>117999</td>\n",
" <td>100000</td>\n",
" <td>17998.7</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_07</th>\n",
" <td>145</td>\n",
" <td>49</td>\n",
" <td>4</td>\n",
" <td></td>\n",
" <td>162</td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>144757</td>\n",
" <td>100000</td>\n",
" <td>44756.6</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_08</th>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>60</td>\n",
" <td>45822.8</td>\n",
" <td>100000</td>\n",
" <td>-54177.2</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_09</th>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>80</td>\n",
" <td></td>\n",
" <td>29669.9</td>\n",
" <td>100000</td>\n",
" <td>-70330.1</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_10</th>\n",
" <td>100</td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>31368.4</td>\n",
" <td>100000</td>\n",
" <td>-68631.6</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_11</th>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>294</td>\n",
" <td>46</td>\n",
" <td>147280</td>\n",
" <td>100000</td>\n",
" <td>47279.9</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_12</th>\n",
" <td></td>\n",
" <td>360</td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>301313</td>\n",
" <td>100000</td>\n",
" <td>201313</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_13</th>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>60</td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>39184</td>\n",
" <td>100000</td>\n",
" <td>-60816</td>\n",
" </tr>\n",
" <tr>\n",
" <th></th>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" </tr>\n",
" <tr>\n",
" <th>total</th>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>1.10404e+06</td>\n",
" <td>1.3e+06</td>\n",
" <td>-195958</td>\n",
" </tr>\n",
" </tbody>\n",
"</table>\n",
"</div>"
],
"text/plain": [
"fact F_01 F_02 F_03 F_04 F_05 F_06 F_07 F_08 profit rent total\n",
"shop \n",
"S_01 43 1994.58 100000 -98005.4\n",
"S_02 20 15332.9 100000 -84667.1\n",
"S_03 70 55725.6 100000 -44274.4\n",
"S_04 101 259 -15193.6 100000 -115194\n",
"S_05 224 136 188789 100000 88789.2\n",
"S_06 120 117999 100000 17998.7\n",
"S_07 145 49 4 162 144757 100000 44756.6\n",
"S_08 60 45822.8 100000 -54177.2\n",
"S_09 80 29669.9 100000 -70330.1\n",
"S_10 100 31368.4 100000 -68631.6\n",
"S_11 294 46 147280 100000 47279.9\n",
"S_12 360 301313 100000 201313\n",
"S_13 60 39184 100000 -60816\n",
" \n",
"total 1.10404e+06 1.3e+06 -195958"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"\u001b[35mGrand total: -195958.13007336503\u001b[0m\n"
]
}
],
"source": [
"result = linprog (c = c,\n",
" A_ub = shop_demand_constraints,\n",
" b_ub = max_demand,\n",
" A_eq = factory_supply_constraints,\n",
" b_eq = max_supply,\n",
" options = { 'disp': True, 'maxiter': 50000 }).x\n",
"\n",
"check_results (result.reshape (N_shops, N_facts))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Using Mixed Integer Programming to add binary open/closed constraints\n",
"\n",
"Classical linear optimization works only with continuous constraints. MIP adds binary and integer constraints. Unfortunately, scikit does not provide integer solvers, as MIP is fairly new area of optimization research.\n",
"\n",
"We will use `mip` library. The library's syntax is more humane and high-level than for `scipy`, we do not need to mess around with raw matrices and encoding sums as dot products — it provides a DSL for expression specification.\n",
"\n",
"This will allow us to investigate what happens if we close some unprofitable shops (thus stop paying rent for them) and reroute the supplies to other shops."
]
},
{
"cell_type": "code",
"execution_count": 325,
"metadata": {},
"outputs": [],
"source": [
"from mip.model import *"
]
},
{
"cell_type": "code",
"execution_count": 326,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"<OptimizationStatus.OPTIMAL: 0>"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
"133842.80279694987"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/html": [
"<div>\n",
"<style scoped>\n",
" .dataframe tbody tr th:only-of-type {\n",
" vertical-align: middle;\n",
" }\n",
"\n",
" .dataframe tbody tr th {\n",
" vertical-align: top;\n",
" }\n",
"\n",
" .dataframe thead th {\n",
" text-align: right;\n",
" }\n",
"</style>\n",
"<table border=\"1\" class=\"dataframe\">\n",
" <thead>\n",
" <tr style=\"text-align: right;\">\n",
" <th>fact</th>\n",
" <th>F_01</th>\n",
" <th>F_02</th>\n",
" <th>F_03</th>\n",
" <th>F_04</th>\n",
" <th>F_05</th>\n",
" <th>F_06</th>\n",
" <th>F_07</th>\n",
" <th>F_08</th>\n",
" <th>profit</th>\n",
" <th>rent</th>\n",
" <th>total</th>\n",
" </tr>\n",
" <tr>\n",
" <th>shop</th>\n",
" <th></th>\n",
" <th></th>\n",
" <th></th>\n",
" <th></th>\n",
" <th></th>\n",
" <th></th>\n",
" <th></th>\n",
" <th></th>\n",
" <th></th>\n",
" <th></th>\n",
" <th></th>\n",
" </tr>\n",
" </thead>\n",
" <tbody>\n",
" <tr>\n",
" <th>S_01</th>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_02</th>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_03</th>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>70</td>\n",
" <td>27</td>\n",
" <td>196</td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>130476</td>\n",
" <td>100000</td>\n",
" <td>30475.9</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_04</th>\n",
" <td>81</td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>279</td>\n",
" <td>-20565.4</td>\n",
" <td>100000</td>\n",
" <td>-120565</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_05</th>\n",
" <td></td>\n",
" <td></td>\n",
" <td>1</td>\n",
" <td></td>\n",
" <td>359</td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>198671</td>\n",
" <td>100000</td>\n",
" <td>98671.3</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_06</th>\n",
" <td></td>\n",
" <td></td>\n",
" <td>120</td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>117999</td>\n",
" <td>100000</td>\n",
" <td>17998.7</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_07</th>\n",
" <td>308</td>\n",
" <td>49</td>\n",
" <td>3</td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>85734.3</td>\n",
" <td>100000</td>\n",
" <td>-14265.7</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_08</th>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>60</td>\n",
" <td>45822.8</td>\n",
" <td>100000</td>\n",
" <td>-54177.2</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_09</th>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>80</td>\n",
" <td></td>\n",
" <td>29669.9</td>\n",
" <td>100000</td>\n",
" <td>-70330.1</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_10</th>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_11</th>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>314</td>\n",
" <td>26</td>\n",
" <td>144722</td>\n",
" <td>100000</td>\n",
" <td>44722.4</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_12</th>\n",
" <td></td>\n",
" <td>360</td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>301313</td>\n",
" <td>100000</td>\n",
" <td>201313</td>\n",
" </tr>\n",
" <tr>\n",
" <th>S_13</th>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" </tr>\n",
" <tr>\n",
" <th></th>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" </tr>\n",
" <tr>\n",
" <th>total</th>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td></td>\n",
" <td>1.03384e+06</td>\n",
" <td>900000</td>\n",
" <td>133843</td>\n",
" </tr>\n",
" </tbody>\n",
"</table>\n",
"</div>"
],
"text/plain": [
"fact F_01 F_02 F_03 F_04 F_05 F_06 F_07 F_08 profit rent total\n",
"shop \n",
"S_01 0 0 0\n",
"S_02 0 0 0\n",
"S_03 70 27 196 130476 100000 30475.9\n",
"S_04 81 279 -20565.4 100000 -120565\n",
"S_05 1 359 198671 100000 98671.3\n",
"S_06 120 117999 100000 17998.7\n",
"S_07 308 49 3 85734.3 100000 -14265.7\n",
"S_08 60 45822.8 100000 -54177.2\n",
"S_09 80 29669.9 100000 -70330.1\n",
"S_10 0 0 0\n",
"S_11 314 26 144722 100000 44722.4\n",
"S_12 360 301313 100000 201313\n",
"S_13 0 0 0\n",
" \n",
"total 1.03384e+06 900000 133843"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"\u001b[35mGrand total: 133842.8027969498\u001b[0m\n"
]
}
],
"source": [
"m = Model (sense=MAXIMIZE, solver_name=CBC)\n",
"\n",
"profits_coeffs = np.array ([[unit_profits[s][f] for f in range (N_facts)] for s in range (N_shops)]).flatten ()\n",
"\n",
"# N×M matrix of decision variables (shop-wise)\n",
"supplies_s = [[*(m.add_var (var_type=CONTINUOUS, lb=0) for _ in range (N_facts))] for _ in range (N_shops)]\n",
"supplies_f = np.transpose (supplies_s) # factory-wise\n",
"supplies = np.array (supplies_s).flatten () # all flat\n",
"\n",
"# Binary variables encoding shops open/closed state\n",
"shops_open = [m.add_var (var_type=BINARY) for _ in range (N_shops)]\n",
"\n",
"# Add linear constraints\n",
"for s in range (N_shops): m += xsum (supplies_s[s]) <= float (max_demand[s]) * shops_open[s]\n",
"for f in range (N_facts): m += xsum (supplies_f[f]) == float (max_supply[f])\n",
"\n",
"# Objective function (what we are optimizing)\n",
"m.objective = (xsum (supplies[i] * profits_coeffs[i] for i in range (len (supplies))) -\n",
" xsum (shops_open[i] * shop_rent_cost for i in range (N_shops)))\n",
"\n",
"# Run it!\n",
"display (m.optimize ())\n",
"display (m.objective_value)\n",
"\n",
"check_results (np.array ([v.x for v in supplies]).reshape (N_shops, N_facts),\n",
" [v.x for v in shops_open])"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
}
],
"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.6.5"
}
},
"nbformat": 4,
"nbformat_minor": 2
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment