Skip to content

Instantly share code, notes, and snippets.

@hotchpotch

hotchpotch/python-6.ipynb Secret

Created June 27, 2022 10:40
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save hotchpotch/f97f42928782daef9a2ca442d9341802 to your computer and use it in GitHub Desktop.
Save hotchpotch/f97f42928782daef9a2ca442d9341802 to your computer and use it in GitHub Desktop.
Download ZIP
Pythonではじめる数理最適化 6章問題を解く.ipynb
Display the source blob
Display the rendered blob
Raw
python-6.ipynb
{
"nbformat": 4,
"nbformat_minor": 0,
"metadata": {
"colab": {
"name": "Pythonではじめる数理最適化 6章問題を解く.ipynb",
"provenance": [],
"collapsed_sections": [],
"authorship_tag": "ABX9TyM5FsLvHptzFt+0BhkGuN9U",
"include_colab_link": true
},
"kernelspec": {
"name": "python3",
"display_name": "Python 3"
},
"language_info": {
"name": "python"
}
},
"cells": [
{
"cell_type": "markdown",
"metadata": {
"id": "view-in-github",
"colab_type": "text"
},
"source": [
"<a href=\"https://colab.research.google.com/gist/hotchpotch/f97f42928782daef9a2ca442d9341802/python-6.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
]
},
{
"cell_type": "markdown",
"source": [
"# Pythonではじめる数理最適化 6章の問題を解く\n",
"\n",
"1. 各学生は1つの車に割当\n",
"2. 各車は定員より多く乗れない\n",
"3. 各車にドライバーは1人以上\n",
"4. 各車に各学年の学生を1人以上\n",
"5. 各車に男性を一人以上\n",
"6. 各車に女性を一人以上\n",
"\n",
"最小化・最大化制約は無し"
],
"metadata": {
"id": "S9OJLdBdt8re"
}
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"id": "y0J-HqLpWxfX"
},
"outputs": [],
"source": [
"import pandas as pd\n"
]
},
{
"cell_type": "code",
"source": [
"!git clone https://github.com/ohmsha/PyOptBook/ PyOptBook\n"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "tzJxRoO9W22j",
"outputId": "aca5c77e-fd6c-4061-8246-fd8aef4c4d5d"
},
"execution_count": 2,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"Cloning into 'PyOptBook'...\n",
"remote: Enumerating objects: 141, done.\u001b[K\n",
"remote: Counting objects: 100% (65/65), done.\u001b[K\n",
"remote: Compressing objects: 100% (35/35), done.\u001b[K\n",
"remote: Total 141 (delta 48), reused 30 (delta 30), pack-reused 76\u001b[K\n",
"Receiving objects: 100% (141/141), 1.99 MiB | 5.17 MiB/s, done.\n",
"Resolving deltas: 100% (65/65), done.\n"
]
}
]
},
{
"cell_type": "code",
"source": [
"!pip install pulp"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "MeQ29tkGXNID",
"outputId": "915e2186-0826-4e74-8323-17e428606184"
},
"execution_count": 3,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"Looking in indexes: https://pypi.org/simple, https://us-python.pkg.dev/colab-wheels/public/simple/\n",
"Collecting pulp\n",
" Downloading PuLP-2.6.0-py3-none-any.whl (14.2 MB)\n",
"\u001b[K |████████████████████████████████| 14.2 MB 6.8 MB/s \n",
"\u001b[?25hInstalling collected packages: pulp\n",
"Successfully installed pulp-2.6.0\n"
]
}
]
},
{
"cell_type": "code",
"source": [
"import pulp\n"
],
"metadata": {
"id": "IMP_eYAXW7gM"
},
"execution_count": 4,
"outputs": []
},
{
"cell_type": "code",
"source": [
"!ls PyOptBook/6.api/resource/"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "r8OvYXqcXX6-",
"outputId": "5abf4aea-2b07-44df-f4cf-03ec73fc6859"
},
"execution_count": 5,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"cars.csv students.csv\n"
]
}
]
},
{
"cell_type": "code",
"source": [
"cars = pd.read_csv('PyOptBook/6.api/resource/cars.csv')\n",
"students = pd.read_csv('PyOptBook/6.api/resource/students.csv')"
],
"metadata": {
"id": "AuVLZ09nXhq4"
},
"execution_count": 6,
"outputs": []
},
{
"cell_type": "code",
"source": [
"cars.head()"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/",
"height": 206
},
"id": "4cvg9yiUXrHj",
"outputId": "364d467d-6624-40b6-b7ad-46c9e7c1b9bc"
},
"execution_count": 7,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
" car_id capacity\n",
"0 0 6\n",
"1 1 6\n",
"2 2 5\n",
"3 3 4\n",
"4 4 5"
],
"text/html": [
"\n",
" <div id=\"df-9cb24611-542b-4a7f-8cf3-c77f6d2e1d40\">\n",
" <div class=\"colab-df-container\">\n",
" <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>car_id</th>\n",
" <th>capacity</th>\n",
" </tr>\n",
" </thead>\n",
" <tbody>\n",
" <tr>\n",
" <th>0</th>\n",
" <td>0</td>\n",
" <td>6</td>\n",
" </tr>\n",
" <tr>\n",
" <th>1</th>\n",
" <td>1</td>\n",
" <td>6</td>\n",
" </tr>\n",
" <tr>\n",
" <th>2</th>\n",
" <td>2</td>\n",
" <td>5</td>\n",
" </tr>\n",
" <tr>\n",
" <th>3</th>\n",
" <td>3</td>\n",
" <td>4</td>\n",
" </tr>\n",
" <tr>\n",
" <th>4</th>\n",
" <td>4</td>\n",
" <td>5</td>\n",
" </tr>\n",
" </tbody>\n",
"</table>\n",
"</div>\n",
" <button class=\"colab-df-convert\" onclick=\"convertToInteractive('df-9cb24611-542b-4a7f-8cf3-c77f6d2e1d40')\"\n",
" title=\"Convert this dataframe to an interactive table.\"\n",
" style=\"display:none;\">\n",
" \n",
" <svg xmlns=\"http://www.w3.org/2000/svg\" height=\"24px\"viewBox=\"0 0 24 24\"\n",
" width=\"24px\">\n",
" <path d=\"M0 0h24v24H0V0z\" fill=\"none\"/>\n",
" <path d=\"M18.56 5.44l.94 2.06.94-2.06 2.06-.94-2.06-.94-.94-2.06-.94 2.06-2.06.94zm-11 1L8.5 8.5l.94-2.06 2.06-.94-2.06-.94L8.5 2.5l-.94 2.06-2.06.94zm10 10l.94 2.06.94-2.06 2.06-.94-2.06-.94-.94-2.06-.94 2.06-2.06.94z\"/><path d=\"M17.41 7.96l-1.37-1.37c-.4-.4-.92-.59-1.43-.59-.52 0-1.04.2-1.43.59L10.3 9.45l-7.72 7.72c-.78.78-.78 2.05 0 2.83L4 21.41c.39.39.9.59 1.41.59.51 0 1.02-.2 1.41-.59l7.78-7.78 2.81-2.81c.8-.78.8-2.07 0-2.86zM5.41 20L4 18.59l7.72-7.72 1.47 1.35L5.41 20z\"/>\n",
" </svg>\n",
" </button>\n",
" \n",
" <style>\n",
" .colab-df-container {\n",
" display:flex;\n",
" flex-wrap:wrap;\n",
" gap: 12px;\n",
" }\n",
"\n",
" .colab-df-convert {\n",
" background-color: #E8F0FE;\n",
" border: none;\n",
" border-radius: 50%;\n",
" cursor: pointer;\n",
" display: none;\n",
" fill: #1967D2;\n",
" height: 32px;\n",
" padding: 0 0 0 0;\n",
" width: 32px;\n",
" }\n",
"\n",
" .colab-df-convert:hover {\n",
" background-color: #E2EBFA;\n",
" box-shadow: 0px 1px 2px rgba(60, 64, 67, 0.3), 0px 1px 3px 1px rgba(60, 64, 67, 0.15);\n",
" fill: #174EA6;\n",
" }\n",
"\n",
" [theme=dark] .colab-df-convert {\n",
" background-color: #3B4455;\n",
" fill: #D2E3FC;\n",
" }\n",
"\n",
" [theme=dark] .colab-df-convert:hover {\n",
" background-color: #434B5C;\n",
" box-shadow: 0px 1px 3px 1px rgba(0, 0, 0, 0.15);\n",
" filter: drop-shadow(0px 1px 2px rgba(0, 0, 0, 0.3));\n",
" fill: #FFFFFF;\n",
" }\n",
" </style>\n",
"\n",
" <script>\n",
" const buttonEl =\n",
" document.querySelector('#df-9cb24611-542b-4a7f-8cf3-c77f6d2e1d40 button.colab-df-convert');\n",
" buttonEl.style.display =\n",
" google.colab.kernel.accessAllowed ? 'block' : 'none';\n",
"\n",
" async function convertToInteractive(key) {\n",
" const element = document.querySelector('#df-9cb24611-542b-4a7f-8cf3-c77f6d2e1d40');\n",
" const dataTable =\n",
" await google.colab.kernel.invokeFunction('convertToInteractive',\n",
" [key], {});\n",
" if (!dataTable) return;\n",
"\n",
" const docLinkHtml = 'Like what you see? Visit the ' +\n",
" '<a target=\"_blank\" href=https://colab.research.google.com/notebooks/data_table.ipynb>data table notebook</a>'\n",
" + ' to learn more about interactive tables.';\n",
" element.innerHTML = '';\n",
" dataTable['output_type'] = 'display_data';\n",
" await google.colab.output.renderOutput(dataTable, element);\n",
" const docLink = document.createElement('div');\n",
" docLink.innerHTML = docLinkHtml;\n",
" element.appendChild(docLink);\n",
" }\n",
" </script>\n",
" </div>\n",
" </div>\n",
" "
]
},
"metadata": {},
"execution_count": 7
}
]
},
{
"cell_type": "code",
"source": [
"students"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/",
"height": 802
},
"id": "c0YH7s12Xs2c",
"outputId": "6fbf4763-53be-42bd-c3b7-05e61a7fd394"
},
"execution_count": 8,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
" student_id license gender grade\n",
"0 0 0 0 1\n",
"1 1 1 1 2\n",
"2 2 1 0 3\n",
"3 3 1 1 4\n",
"4 4 0 1 1\n",
"5 5 0 1 2\n",
"6 6 0 0 3\n",
"7 7 0 1 4\n",
"8 8 1 1 1\n",
"9 9 1 0 2\n",
"10 10 1 1 3\n",
"11 11 0 1 4\n",
"12 12 1 1 1\n",
"13 13 1 0 2\n",
"14 14 1 0 3\n",
"15 15 1 0 4\n",
"16 16 1 1 1\n",
"17 17 1 0 2\n",
"18 18 0 1 3\n",
"19 19 1 0 4\n",
"20 20 1 1 1\n",
"21 21 0 0 2\n",
"22 22 1 1 3\n",
"23 23 1 1 4"
],
"text/html": [
"\n",
" <div id=\"df-cda70044-471c-4531-af6a-4842d7348286\">\n",
" <div class=\"colab-df-container\">\n",
" <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>student_id</th>\n",
" <th>license</th>\n",
" <th>gender</th>\n",
" <th>grade</th>\n",
" </tr>\n",
" </thead>\n",
" <tbody>\n",
" <tr>\n",
" <th>0</th>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>1</td>\n",
" </tr>\n",
" <tr>\n",
" <th>1</th>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" <td>2</td>\n",
" </tr>\n",
" <tr>\n",
" <th>2</th>\n",
" <td>2</td>\n",
" <td>1</td>\n",
" <td>0</td>\n",
" <td>3</td>\n",
" </tr>\n",
" <tr>\n",
" <th>3</th>\n",
" <td>3</td>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" <td>4</td>\n",
" </tr>\n",
" <tr>\n",
" <th>4</th>\n",
" <td>4</td>\n",
" <td>0</td>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" </tr>\n",
" <tr>\n",
" <th>5</th>\n",
" <td>5</td>\n",
" <td>0</td>\n",
" <td>1</td>\n",
" <td>2</td>\n",
" </tr>\n",
" <tr>\n",
" <th>6</th>\n",
" <td>6</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>3</td>\n",
" </tr>\n",
" <tr>\n",
" <th>7</th>\n",
" <td>7</td>\n",
" <td>0</td>\n",
" <td>1</td>\n",
" <td>4</td>\n",
" </tr>\n",
" <tr>\n",
" <th>8</th>\n",
" <td>8</td>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" </tr>\n",
" <tr>\n",
" <th>9</th>\n",
" <td>9</td>\n",
" <td>1</td>\n",
" <td>0</td>\n",
" <td>2</td>\n",
" </tr>\n",
" <tr>\n",
" <th>10</th>\n",
" <td>10</td>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" <td>3</td>\n",
" </tr>\n",
" <tr>\n",
" <th>11</th>\n",
" <td>11</td>\n",
" <td>0</td>\n",
" <td>1</td>\n",
" <td>4</td>\n",
" </tr>\n",
" <tr>\n",
" <th>12</th>\n",
" <td>12</td>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" </tr>\n",
" <tr>\n",
" <th>13</th>\n",
" <td>13</td>\n",
" <td>1</td>\n",
" <td>0</td>\n",
" <td>2</td>\n",
" </tr>\n",
" <tr>\n",
" <th>14</th>\n",
" <td>14</td>\n",
" <td>1</td>\n",
" <td>0</td>\n",
" <td>3</td>\n",
" </tr>\n",
" <tr>\n",
" <th>15</th>\n",
" <td>15</td>\n",
" <td>1</td>\n",
" <td>0</td>\n",
" <td>4</td>\n",
" </tr>\n",
" <tr>\n",
" <th>16</th>\n",
" <td>16</td>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" </tr>\n",
" <tr>\n",
" <th>17</th>\n",
" <td>17</td>\n",
" <td>1</td>\n",
" <td>0</td>\n",
" <td>2</td>\n",
" </tr>\n",
" <tr>\n",
" <th>18</th>\n",
" <td>18</td>\n",
" <td>0</td>\n",
" <td>1</td>\n",
" <td>3</td>\n",
" </tr>\n",
" <tr>\n",
" <th>19</th>\n",
" <td>19</td>\n",
" <td>1</td>\n",
" <td>0</td>\n",
" <td>4</td>\n",
" </tr>\n",
" <tr>\n",
" <th>20</th>\n",
" <td>20</td>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" </tr>\n",
" <tr>\n",
" <th>21</th>\n",
" <td>21</td>\n",
" <td>0</td>\n",
" <td>0</td>\n",
" <td>2</td>\n",
" </tr>\n",
" <tr>\n",
" <th>22</th>\n",
" <td>22</td>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" <td>3</td>\n",
" </tr>\n",
" <tr>\n",
" <th>23</th>\n",
" <td>23</td>\n",
" <td>1</td>\n",
" <td>1</td>\n",
" <td>4</td>\n",
" </tr>\n",
" </tbody>\n",
"</table>\n",
"</div>\n",
" <button class=\"colab-df-convert\" onclick=\"convertToInteractive('df-cda70044-471c-4531-af6a-4842d7348286')\"\n",
" title=\"Convert this dataframe to an interactive table.\"\n",
" style=\"display:none;\">\n",
" \n",
" <svg xmlns=\"http://www.w3.org/2000/svg\" height=\"24px\"viewBox=\"0 0 24 24\"\n",
" width=\"24px\">\n",
" <path d=\"M0 0h24v24H0V0z\" fill=\"none\"/>\n",
" <path d=\"M18.56 5.44l.94 2.06.94-2.06 2.06-.94-2.06-.94-.94-2.06-.94 2.06-2.06.94zm-11 1L8.5 8.5l.94-2.06 2.06-.94-2.06-.94L8.5 2.5l-.94 2.06-2.06.94zm10 10l.94 2.06.94-2.06 2.06-.94-2.06-.94-.94-2.06-.94 2.06-2.06.94z\"/><path d=\"M17.41 7.96l-1.37-1.37c-.4-.4-.92-.59-1.43-.59-.52 0-1.04.2-1.43.59L10.3 9.45l-7.72 7.72c-.78.78-.78 2.05 0 2.83L4 21.41c.39.39.9.59 1.41.59.51 0 1.02-.2 1.41-.59l7.78-7.78 2.81-2.81c.8-.78.8-2.07 0-2.86zM5.41 20L4 18.59l7.72-7.72 1.47 1.35L5.41 20z\"/>\n",
" </svg>\n",
" </button>\n",
" \n",
" <style>\n",
" .colab-df-container {\n",
" display:flex;\n",
" flex-wrap:wrap;\n",
" gap: 12px;\n",
" }\n",
"\n",
" .colab-df-convert {\n",
" background-color: #E8F0FE;\n",
" border: none;\n",
" border-radius: 50%;\n",
" cursor: pointer;\n",
" display: none;\n",
" fill: #1967D2;\n",
" height: 32px;\n",
" padding: 0 0 0 0;\n",
" width: 32px;\n",
" }\n",
"\n",
" .colab-df-convert:hover {\n",
" background-color: #E2EBFA;\n",
" box-shadow: 0px 1px 2px rgba(60, 64, 67, 0.3), 0px 1px 3px 1px rgba(60, 64, 67, 0.15);\n",
" fill: #174EA6;\n",
" }\n",
"\n",
" [theme=dark] .colab-df-convert {\n",
" background-color: #3B4455;\n",
" fill: #D2E3FC;\n",
" }\n",
"\n",
" [theme=dark] .colab-df-convert:hover {\n",
" background-color: #434B5C;\n",
" box-shadow: 0px 1px 3px 1px rgba(0, 0, 0, 0.15);\n",
" filter: drop-shadow(0px 1px 2px rgba(0, 0, 0, 0.3));\n",
" fill: #FFFFFF;\n",
" }\n",
" </style>\n",
"\n",
" <script>\n",
" const buttonEl =\n",
" document.querySelector('#df-cda70044-471c-4531-af6a-4842d7348286 button.colab-df-convert');\n",
" buttonEl.style.display =\n",
" google.colab.kernel.accessAllowed ? 'block' : 'none';\n",
"\n",
" async function convertToInteractive(key) {\n",
" const element = document.querySelector('#df-cda70044-471c-4531-af6a-4842d7348286');\n",
" const dataTable =\n",
" await google.colab.kernel.invokeFunction('convertToInteractive',\n",
" [key], {});\n",
" if (!dataTable) return;\n",
"\n",
" const docLinkHtml = 'Like what you see? Visit the ' +\n",
" '<a target=\"_blank\" href=https://colab.research.google.com/notebooks/data_table.ipynb>data table notebook</a>'\n",
" + ' to learn more about interactive tables.';\n",
" element.innerHTML = '';\n",
" dataTable['output_type'] = 'display_data';\n",
" await google.colab.output.renderOutput(dataTable, element);\n",
" const docLink = document.createElement('div');\n",
" docLink.innerHTML = docLinkHtml;\n",
" element.appendChild(docLink);\n",
" }\n",
" </script>\n",
" </div>\n",
" </div>\n",
" "
]
},
"metadata": {},
"execution_count": 8
}
]
},
{
"cell_type": "code",
"source": [
"cars.capacity.sum()"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "M2bCTkS1Y5lH",
"outputId": "317494d4-a2d5-434f-b31c-ff4c3ff8234d"
},
"execution_count": 9,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"31"
]
},
"metadata": {},
"execution_count": 9
}
]
},
{
"cell_type": "code",
"source": [
"len(students)"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "pAyUoqP7Y-i4",
"outputId": "3c4ac32b-ae1b-4857-9355-5aafffe3905a"
},
"execution_count": 10,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"24"
]
},
"metadata": {},
"execution_count": 10
}
]
},
{
"cell_type": "code",
"source": [
"len(cars)"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "uCHXWcXWZAMG",
"outputId": "9c47f8e0-e3de-4942-b76a-8ed432b60805"
},
"execution_count": 11,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"6"
]
},
"metadata": {},
"execution_count": 11
}
]
},
{
"cell_type": "code",
"source": [
"students.license.value_counts()"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "0GaDqZ2LZCx5",
"outputId": "4ad9ead1-8416-464a-99e8-2a4cb31c9da0"
},
"execution_count": 12,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"1 16\n",
"0 8\n",
"Name: license, dtype: int64"
]
},
"metadata": {},
"execution_count": 12
}
]
},
{
"cell_type": "code",
"source": [
"students.gender.value_counts()"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "yrbwcB3wZJgc",
"outputId": "5e2d68a4-1149-47c8-9eb4-5c06efd07b7e"
},
"execution_count": 13,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"1 14\n",
"0 10\n",
"Name: gender, dtype: int64"
]
},
"metadata": {},
"execution_count": 13
}
]
},
{
"cell_type": "code",
"source": [
"students.grade.value_counts()"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "Pfj4gL-MZLKT",
"outputId": "998275af-1d83-489b-b7d5-aaf4fb5abd27"
},
"execution_count": 14,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"1 6\n",
"2 6\n",
"3 6\n",
"4 6\n",
"Name: grade, dtype: int64"
]
},
"metadata": {},
"execution_count": 14
}
]
},
{
"cell_type": "code",
"source": [
""
],
"metadata": {
"id": "-S_7zI_UZttY"
},
"execution_count": 14,
"outputs": []
},
{
"cell_type": "code",
"source": [
"S = students.student_id.tolist()\n",
"C = cars.car_id.tolist()\n",
"S,C"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "sNf9h-BxZ5lp",
"outputId": "96e2e0e0-be48-428a-8310-dc84b80d2caa"
},
"execution_count": 15,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"([0,\n",
" 1,\n",
" 2,\n",
" 3,\n",
" 4,\n",
" 5,\n",
" 6,\n",
" 7,\n",
" 8,\n",
" 9,\n",
" 10,\n",
" 11,\n",
" 12,\n",
" 13,\n",
" 14,\n",
" 15,\n",
" 16,\n",
" 17,\n",
" 18,\n",
" 19,\n",
" 20,\n",
" 21,\n",
" 22,\n",
" 23],\n",
" [0, 1, 2, 3, 4, 5])"
]
},
"metadata": {},
"execution_count": 15
}
]
},
{
"cell_type": "code",
"source": [
"# 生徒と車の組み合わせのtuple\n",
"import itertools\n",
"SC = [(s, c) for s in S for c in C]\n",
"len(SC)"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "jeGHlVyfaOLh",
"outputId": "0b7af556-34aa-4f4f-a252-a40fa6e81b09"
},
"execution_count": 16,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"144"
]
},
"metadata": {},
"execution_count": 16
}
]
},
{
"cell_type": "code",
"source": [
"x = pulp.LpVariable.dicts('x', SC, cat='Binary')"
],
"metadata": {
"id": "yd99appYbRG6"
},
"execution_count": 17,
"outputs": []
},
{
"cell_type": "code",
"source": [
"x.__class__"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "VWIH7DVOiD1l",
"outputId": "3773d59b-b367-419c-b412-fec67f2ae8f8"
},
"execution_count": 18,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"dict"
]
},
"metadata": {},
"execution_count": 18
}
]
},
{
"cell_type": "code",
"source": [
"list(x.items())[0:3]\n"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "bJItPYi7iN9M",
"outputId": "71e20ba6-fe1d-4aca-fb18-b467539d217d"
},
"execution_count": 19,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"[((0, 0), x_(0,_0)), ((0, 1), x_(0,_1)), ((0, 2), x_(0,_2))]"
]
},
"metadata": {},
"execution_count": 19
}
]
},
{
"cell_type": "code",
"source": [
"prob = pulp.LpProblem('prob6', pulp.LpMaximize)\n",
"x = pulp.LpVariable.dicts('x', SC, cat='Binary')\n",
"\n",
"# 1. 各学生は1つの車に割当\n",
"for s in S:\n",
" prob += pulp.lpSum([x[s,c] for c in C]) == 1\n",
"\n",
"# 2. 各車は定員より多く乗れない\n",
"for (c, capacity) in cars[['car_id', 'capacity']].values:\n",
" prob += pulp.lpSum([x[s,c] for s in S]) <= capacity\n",
"\n",
"# 3. 各車にドライバーは1人以上\n",
"for c in C:\n",
" target_sids = students[students.license == 1]['student_id'].values\n",
" prob += pulp.lpSum([x[s,c] for s in target_sids]) >= 1\n",
"\n",
"# 4. 各車に各学年の学生を1人以上\n",
"for c in C:\n",
" for grade, grade_sids in students.groupby('grade')['student_id']:\n",
" prob += pulp.lpSum([x[s,c] for s in grade_sids]) >= 1\n",
"\n",
"# 5. 各車に男性を一人以上\n",
"for c in C:\n",
" target_sids = students[students.gender == 0]['student_id'].values\n",
" prob += pulp.lpSum([x[s,c] for s in target_sids]) >= 1\n",
"\n",
"# 6. 各車に女性を一人以上\n",
"for c in C:\n",
" target_sids = students[students.gender == 1]['student_id'].values\n",
" prob += pulp.lpSum([x[s,c] for s in target_sids]) >= 1\n"
],
"metadata": {
"id": "TSJ2R0UaiXTQ"
},
"execution_count": 20,
"outputs": []
},
{
"cell_type": "code",
"source": [
"status = prob.solve()\n",
"print(pulp.LpStatus[status])\n",
"\n",
"cars_students = {}\n",
"for c in C:\n",
" cars_students[c] = [s for s in S if x[s,c].value() == 1]\n",
"cars_students"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "KEhvDBgijKN6",
"outputId": "78b77c63-7517-4ce8-ba60-77a10a42ea9f"
},
"execution_count": 21,
"outputs": [
{
"output_type": "stream",
"name": "stdout",
"text": [
"Optimal\n"
]
},
{
"output_type": "execute_result",
"data": {
"text/plain": [
"{0: [6, 7, 8, 9],\n",
" 1: [4, 18, 21, 23],\n",
" 2: [5, 19, 20, 22],\n",
" 3: [3, 10, 13, 16],\n",
" 4: [0, 2, 11, 17],\n",
" 5: [1, 12, 14, 15]}"
]
},
"metadata": {},
"execution_count": 21
}
]
},
{
"cell_type": "code",
"source": [
"import itertools\n",
"def check_results(results):\n",
" # 1. 各学生は1つの車に割当\n",
" values = list(itertools.chain.from_iterable(results.values()))\n",
" assert(len(values) == len(set(values)))\n",
"\n",
" # 2. 各車は定員より多く乗れない\n",
" for (c, capacity) in cars[['car_id', 'capacity']].values:\n",
" assert(len(results[c]) <= capacity)\n",
"\n",
" # 3. 各車にドライバーは1人以上\n",
" for c in C:\n",
" ids = results[c]\n",
" target_df = students[students.student_id.isin(ids)]\n",
" assert(len(target_df[target_df.license == 1] >= 1))\n",
"\n",
" # 4. 各車に各学年の学生を1人以上\n",
" for c in C:\n",
" ids = results[c]\n",
" target_df = students[students.student_id.isin(ids)]\n",
" for grade in students.grade.unique().tolist():\n",
" assert(len(target_df[target_df.grade == grade] >= 1))\n",
"\n",
" # 5. 各車に男性を一人以上\n",
" for c in C:\n",
" ids = results[c]\n",
" target_df = students[students.student_id.isin(ids)]\n",
" assert(len(target_df[target_df.gender == 0] >= 1))\n",
"\n",
" # 6. 各車に女性を一人以上\n",
" for c in C:\n",
" ids = results[c]\n",
" target_df = students[students.student_id.isin(ids)]\n",
" assert(len(target_df[target_df.gender == 1] >= 1))\n",
" \n",
" return True\n",
"\n",
"check_results(cars_students)"
],
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "7mIl1qOgm2sp",
"outputId": "b62edaa7-2a29-4414-8750-cf740e231b5e"
},
"execution_count": 22,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"True"
]
},
"metadata": {},
"execution_count": 22
}
]
}
]
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment