Python_code.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/EjenY-Poltavchiny/Transport-problem/blob/main/Python_code.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "NHuzYPZPcxqg"
      },
      "source": [
        "# Transportation Problem (method of potentials)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "oPV1udhAcxql"
      },
      "source": [
        "## Balancing"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "FZ3_QN0Wcxqm"
      },
      "outputs": [],
      "source": [
        "import numpy as np\n",
        "import time"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "dLPtkmGTcxqo"
      },
      "outputs": [],
      "source": [
        "def get_balanced_tp(supply, demand, costs, penalties = None):\n",
        "    total_supply = sum(supply)\n",
        "    total_demand = sum(demand)\n",
        "    \n",
        "    if total_supply < total_demand:\n",
        "        if penalties is None:\n",
        "            raise Exception('Supply less than demand, penalties required')\n",
        "        new_supply = supply + [total_demand - total_supply]\n",
        "        new_costs = costs + [penalties]\n",
        "        return new_supply, demand, new_costs\n",
        "    if total_supply > total_demand:\n",
        "        new_demand = demand + [total_supply - total_demand]\n",
        "        new_costs = costs + [[0 for _ in demand]]\n",
        "        return supply, new_demand, new_costs\n",
        "    return supply, demand, costs"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "fvDMkba9cxqp"
      },
      "source": [
        "## North West Corner Method"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "QHMxhqrwcxqq"
      },
      "outputs": [],
      "source": [
        "def north_west_corner(supply, demand):\n",
        "    supply_copy = supply.copy()\n",
        "    demand_copy = demand.copy()\n",
        "    i = 0\n",
        "    j = 0\n",
        "    bfs = []\n",
        "    while len(bfs) < len(supply) + len(demand) - 1:\n",
        "        s = supply_copy[i]\n",
        "        d = demand_copy[j]\n",
        "        v = min(s, d)\n",
        "        supply_copy[i] -= v\n",
        "        demand_copy[j] -= v\n",
        "        bfs.append(((i, j), v))\n",
        "        if supply_copy[i] == 0 and i < len(supply) - 1:\n",
        "            i += 1\n",
        "        elif demand_copy[j] == 0 and j < len(demand) - 1:\n",
        "            j += 1\n",
        "    return bfs"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "rhWl1RZZcxqr",
        "outputId": "e241eeb2-a8e4-43a5-b5d1-ae97f67c387a"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[((0, 0), 30), ((1, 0), 10), ((1, 1), 30), ((1, 2), 30), ((2, 2), 10), ((2, 3), 40)]\n"
          ]
        }
      ],
      "source": [
        "supply = [30, 70, 50]\n",
        "demand = [40, 30, 40, 40]\n",
        "bfs = north_west_corner(supply, demand)\n",
        "print(bfs)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "c6ZkTxLXcxqs"
      },
      "source": [
        "## Transportation Method of potentials"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "rH5fK0lXcxqt"
      },
      "outputs": [],
      "source": [
        "def get_us_and_vs(bfs, costs):\n",
        "    us = [None] * len(costs)\n",
        "    vs = [None] * len(costs[0])\n",
        "    us[0] = 0\n",
        "    bfs_copy = bfs.copy()\n",
        "    while len(bfs_copy) > 0:\n",
        "        for index, bv in enumerate(bfs_copy):\n",
        "            i, j = bv[0]\n",
        "            if us[i] is None and vs[j] is None: continue\n",
        "                \n",
        "            cost = costs[i][j]\n",
        "            if us[i] is None:\n",
        "                us[i] = cost - vs[j]\n",
        "            else: \n",
        "                vs[j] = cost - us[i]\n",
        "            bfs_copy.pop(index)\n",
        "            break\n",
        "            \n",
        "    return us, vs      "
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "OJ0K4YBrcxqu"
      },
      "outputs": [],
      "source": [
        "def get_ws(bfs, costs, us, vs):\n",
        "    ws = []\n",
        "    for i, row in enumerate(costs):\n",
        "        for j, cost in enumerate(row):\n",
        "            non_basic = all([p[0] != i or p[1] != j for p, v in bfs])\n",
        "            if non_basic:\n",
        "                ws.append(((i, j), us[i] + vs[j] - cost))\n",
        "    \n",
        "    return ws"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "UY0cDhrDcxqu"
      },
      "outputs": [],
      "source": [
        "def can_be_improved(ws):\n",
        "    for p, v in ws:\n",
        "        if v > 0: return True\n",
        "    return False"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "mKMCdfA5cxqv"
      },
      "outputs": [],
      "source": [
        "def get_entering_variable_position(ws):\n",
        "    ws_copy = ws.copy()\n",
        "    ws_copy.sort(key=lambda w: w[1])\n",
        "    return ws_copy[-1][0]"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "ZTHzpxEDcxqv"
      },
      "outputs": [],
      "source": [
        "def get_possible_next_nodes(loop, not_visited):\n",
        "    last_node = loop[-1]\n",
        "    nodes_in_row = [n for n in not_visited if n[0] == last_node[0]]\n",
        "    nodes_in_column = [n for n in not_visited if n[1] == last_node[1]]\n",
        "    if len(loop) < 2:\n",
        "        return nodes_in_row + nodes_in_column\n",
        "    else:\n",
        "        prev_node = loop[-2]\n",
        "        row_move = prev_node[0] == last_node[0]\n",
        "        if row_move: return nodes_in_column\n",
        "        return nodes_in_row"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "AilIRUvgcxqv"
      },
      "outputs": [],
      "source": [
        "def get_loop(bv_positions, ev_position):\n",
        "    def inner(loop):\n",
        "        if len(loop) > 3:\n",
        "            can_be_closed = len(get_possible_next_nodes(loop, [ev_position])) == 1\n",
        "            if can_be_closed: return loop\n",
        "        \n",
        "        not_visited = list(set(bv_positions) - set(loop))\n",
        "        possible_next_nodes = get_possible_next_nodes(loop, not_visited)\n",
        "        for next_node in possible_next_nodes:\n",
        "            new_loop = inner(loop + [next_node])\n",
        "            if new_loop: return new_loop\n",
        "    \n",
        "    return inner([ev_position])"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "iBuwetZ8cxqw"
      },
      "outputs": [],
      "source": [
        "def loop_pivoting(bfs, loop):\n",
        "    even_cells = loop[0::2]\n",
        "    odd_cells = loop[1::2]\n",
        "    get_bv = lambda pos: next(v for p, v in bfs if p == pos)\n",
        "    leaving_position = sorted(odd_cells, key=get_bv)[0]\n",
        "    leaving_value = get_bv(leaving_position)\n",
        "    \n",
        "    new_bfs = []\n",
        "    for p, v in [bv for bv in bfs if bv[0] != leaving_position] + [(loop[0], 0)]:\n",
        "        if p in even_cells:\n",
        "            v += leaving_value\n",
        "        elif p in odd_cells:\n",
        "            v -= leaving_value\n",
        "        new_bfs.append((p, v))\n",
        "        \n",
        "    return new_bfs"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "gGxyh494cxqw"
      },
      "outputs": [],
      "source": [
        "def potential_method(supply, demand, costs, penalties = None):\n",
        "    balanced_supply, balanced_demand, balanced_costs = get_balanced_tp(\n",
        "        supply, demand, costs\n",
        "    )\n",
        "    def inner(bfs):\n",
        "        us, vs = get_us_and_vs(bfs, balanced_costs)\n",
        "        ws = get_ws(bfs, balanced_costs, us, vs)\n",
        "        if can_be_improved(ws):\n",
        "            ev_position = get_entering_variable_position(ws)\n",
        "            loop = get_loop([p for p, v in bfs], ev_position)\n",
        "            return inner(loop_pivoting(bfs, loop))\n",
        "        return bfs\n",
        "    \n",
        "    basic_variables = inner(north_west_corner(balanced_supply, balanced_demand))\n",
        "    solution = np.zeros((len(costs), len(costs[0])))\n",
        "    for (i, j), v in basic_variables:\n",
        "        solution[i][j] = v\n",
        "\n",
        "    return solution"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "dyH3fWUKcxqw"
      },
      "outputs": [],
      "source": [
        "def get_total_cost(costs, solution):\n",
        "    total_cost = 0\n",
        "    for i, row in enumerate(costs):\n",
        "        for j, cost in enumerate(row):\n",
        "            total_cost += cost * solution[i][j]\n",
        "    return total_cost"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "TofWr53pcxqx"
      },
      "source": [
        "### Проверка работы на примере из кнгиги \"Выпуклый анализ\" К.Ю. Осипенко"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "tFcUBLE1cxqx",
        "outputId": "1b8995f2-51c3-4952-a883-aa69d5d0ac1c"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[[10.  0.  0.  0.]\n",
            " [25.  0. 42. 13.]\n",
            " [ 5. 15.  0.  0.]]\n",
            "total cost:  374.0\n"
          ]
        }
      ],
      "source": [
        "costs = [\n",
        "    [ 2, 1, 5, 11],\n",
        "    [ 4, 3, 4, 2],\n",
        "    [ 6, 2, 7, 8]\n",
        "]\n",
        "supply = [10, 80, 20]\n",
        "demand = [40, 15, 42, 13]\n",
        "solution = potential_method(supply, demand, costs)\n",
        "print(solution)\n",
        "print('total cost: ', get_total_cost(costs, solution))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "h5MEd8TTcxqx"
      },
      "source": [
        "### Собственные данные и подсчёт времени"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "ZdUL3X6Ccxqx",
        "outputId": "9b34a9fd-1a3a-45b2-ed1d-de1b82616f05"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[[ 0.  0.  0.  0.  0.  0. 13.  0.  0.]\n",
            " [ 0.  0.  0.  0.  0.  0.  7.  0.  0.]\n",
            " [ 0.  0.  0.  0.  0.  0. 14.  0.  0.]\n",
            " [ 0.  0.  0.  0.  0. 10.  0.  0.  0.]\n",
            " [ 0.  2.  0.  6.  3.  2.  2.  0.  0.]\n",
            " [ 3.  0.  3.  0.  0.  0.  0.  0.  7.]\n",
            " [ 0.  0.  0.  0.  0.  0.  0.  9.  0.]\n",
            " [ 0.  0.  0.  0.  0.  0.  0. 15.  0.]\n",
            " [ 0.  7.  0.  0.  0.  0.  0.  0.  5.]]\n",
            "total cost:  12447.2514\n"
          ]
        }
      ],
      "source": [
        "costs = np.array([\n",
        "[ 16, 19, 15, 21, 24, 44, 34, 56, 19],\n",
        "[ 15, 17, 14, 19, 21, 31, 32, 62, 22],\n",
        "[ 15, 17, 13, 19, 20, 26, 42, 61, 22],\n",
        "[ 22, 24, 21, 20, 15, 21, 53, 44, 23],\n",
        "[ 15, 14, 18, 8, 11, 32, 54, 37, 16],\n",
        "[ 6, 6, 8, 13, 12, 37, 46, 43, 6],\n",
        "[ 26, 22, 30, 20, 25, 47, 79, 22, 23],\n",
        "[ 15, 13, 30, 11, 19, 58, 67, 32, 16],\n",
        "[ 15, 10, 18, 17, 22, 46, 56, 49, 10]\n",
        "])\n",
        "supply = [13, 7, 14, 10, 15, 13, 9, 15, 12]\n",
        "demand = [3, 9, 3, 6, 3, 12, 36, 24, 12]\n",
        "solution = potential_method(supply, demand, costs)\n",
        "print(solution)\n",
        "print('total cost: ', get_total_cost(costs, solution)*4.7382)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "yLvRf-izcxqy"
      },
      "source": [
        "# Transportation Problem (Simplex method)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "JOv5UZymcxqy"
      },
      "source": [
        "#### Для реализования симплекс метода нам нужна каноническая формулировка транспортной задачи как ЗЛП."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "oQu4VPuWcxqy"
      },
      "outputs": [],
      "source": [
        "import numpy as np\n",
        "from scipy.optimize import linprog\n",
        "import warnings\n",
        "warnings.filterwarnings('ignore')"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "I5onqgSXcxqy"
      },
      "outputs": [],
      "source": [
        "# Функция возвращает матрицу системы ограничений\n",
        "def prepare(a, b):\n",
        "    m = len(a)\n",
        "    n = len(b)\n",
        "    h = np.diag(np.ones(n))\n",
        "    v = np.zeros((m, n))\n",
        "    v[0] = 1\n",
        "    for i in range(1, m):\n",
        "        h = np.hstack((h, np.diag(np.ones(n))))\n",
        "        k = np.zeros((m, n))\n",
        "        k[i]=1\n",
        "        v = np.hstack((v, k))\n",
        "    return np.vstack((h, v)).astype(int), np.hstack((b,a))"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "TnLsOfy_cxqz",
        "outputId": "7e2a23f8-ea14-485f-d83a-b142ceb09a3d"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "A: \n",
            " [[1 0 0 0 1 0 0 0 1 0 0 0]\n",
            " [0 1 0 0 0 1 0 0 0 1 0 0]\n",
            " [0 0 1 0 0 0 1 0 0 0 1 0]\n",
            " [0 0 0 1 0 0 0 1 0 0 0 1]\n",
            " [1 1 1 1 0 0 0 0 0 0 0 0]\n",
            " [0 0 0 0 1 1 1 1 0 0 0 0]\n",
            " [0 0 0 0 0 0 0 0 1 1 1 1]]\n",
            "b: \n",
            " [40 15 42 13 10 80 20]\n"
          ]
        }
      ],
      "source": [
        "costs = np.array ([\n",
        "    [ 2, 1, 5, 11],\n",
        "    [ 4, 3, 4, 2],\n",
        "    [ 6, 2, 7, 8]\n",
        "])\n",
        "supply = [10, 80, 20]\n",
        "demand = [40, 15, 42, 13]\n",
        "A = prepare(supply, demand)[0]\n",
        "b = prepare(supply, demand)[1]\n",
        "print('A: \\n', A)\n",
        "print('b: \\n', b)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "i3S3f0locxqz",
        "outputId": "360c438e-5295-4b74-fb81-7852c9ca284c"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "c =  [[ 2  1  5 11  4  3  4  2  6  2  7  8]]\n"
          ]
        }
      ],
      "source": [
        "# А также нам нужно переделать матрицу затрат в строку\n",
        "c = costs.reshape(1, -1)\n",
        "print('c = ', c)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "-9n5EJwgcxq0"
      },
      "outputs": [],
      "source": [
        "def smplx(supply, demand, costs):\n",
        "    a = np.copy(supply)\n",
        "    b = np.copy(demand)\n",
        "    c = np.copy(costs)\n",
        "    # Проверяем условие замкнутости:\n",
        "    if a.sum() > b.sum():\n",
        "        b = np.hstack((b, [a.sum() - b.sum()]))\n",
        "        c = np.hstack((c, np.zeros(len(a)).reshape(-1, 1)))\n",
        "    elif a.sum() < b.sum():\n",
        "        a = np.hstack((a, [b.sum() - a.sum()]))\n",
        "        c = np.vstack((c, np.zeros(len(b))))\n",
        "        \n",
        "    m = len(a)\n",
        "    n = len(b)\n",
        "    A_eq, b_eq = prepare(a, b)\n",
        "    \n",
        "    res = linprog(c.reshape(1, -1), A_eq=A_eq, b_eq=b_eq, bounds=(0, None), method='simplex')\n",
        "    return res.x.astype(int).reshape(m, n), res.fun.astype(int) # возращаем матрицу x и целевую функцию"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "kMqgwTtXcxq0"
      },
      "source": [
        "### Проверка работы на примере из кнгиги \"Выпуклый анализ\" К.Ю. Осипенко"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "z8H-WDVJcxq0",
        "outputId": "1effb94c-6df1-4d2c-fa5d-5eecef8c72b8"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Optimal transpotation plan: \n",
            " [[10  0  0  0]\n",
            " [25  0 42 13]\n",
            " [ 5 15  0  0]]\n",
            "Total cost:  374\n",
            "\n"
          ]
        }
      ],
      "source": [
        "costs = np.array ([\n",
        "    [ 2, 1, 5, 11],\n",
        "    [ 4, 3, 4, 2],\n",
        "    [ 6, 2, 7, 8]\n",
        "])\n",
        "supply = [10, 80, 20]\n",
        "demand = [40, 15, 42, 13]\n",
        "\n",
        "x_opt, total_cost = smplx(supply, demand, costs)\n",
        "print('Optimal transpotation plan: \\n', x_opt)\n",
        "print('Total cost: ', total_cost)\n",
        "print()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "U1WHUvqtcxq1"
      },
      "source": [
        "### Собственные данные и подсчёт времени\n",
        "\n",
        "В качестве данных для транспортной задачи выбрана следующая ситуация.\n",
        "На 22 мая есть расписания поездов и самолётов, прибывающих в Москву в промежуток времени 9:50 - 10:15. Будем рассматривать автопарки \"Такси Ритм\" в Москве. Количество подаваемх машин расчитать сложно, но будем считать, что компания готова выделить примерно 10% от всех машин (объяснение далее). По статистике собранной Яндексом примерно 8% заказов уходят этой компании. Более того 10% от всех поездок на такси происходят из аэропортов и вокзалов (ответ на вопрос, почему компания выделяет 10%). Зная среднее количество поездок каждые пол-часа, приходящихся на этого перевозчика, можем примерно расчитать количество заказов из каждого (самого используемого по статистике) вокзала/аэропорта. Наша задача отправить в эти вокзалы/аэропорты определённое количество машин, при этом уменьшив общую стоимость затрат на поездку одного водителя. Рассчитываем расстояние до пунктов. Смотрим стоимость бензина и средний расход легквого автомобиля. Получаем соотношение киллометров в рубли. Понятно, что данные будут получены с некоторой погрешностью, но в каком-то смысле такой план подачи машин будет, быть может не самым, но всё же оптимальным."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "fDDIF2d_cxq2",
        "outputId": "5f1a13ee-f413-4527-a27d-8fc920886405",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[[ 0.  0.  0.  0.  0.  0. 13.  0.  0.]\n",
            " [ 0.  0.  0.  0.  0.  0.  7.  0.  0.]\n",
            " [ 0.  0.  0.  0.  0.  0. 14.  0.  0.]\n",
            " [ 0.  0.  0.  0.  0. 10.  0.  0.  0.]\n",
            " [ 0.  2.  0.  6.  3.  2.  2.  0.  0.]\n",
            " [ 3.  0.  3.  0.  0.  0.  0.  0.  7.]\n",
            " [ 0.  0.  0.  0.  0.  0.  0.  9.  0.]\n",
            " [ 0.  0.  0.  0.  0.  0.  0. 15.  0.]\n",
            " [ 0.  7.  0.  0.  0.  0.  0.  0.  5.]]\n",
            "total cost:  12447.2514\n"
          ]
        }
      ],
      "source": [
        "from statistics import mean\n",
        "costs = np.array([\n",
        "[ 16, 19, 15, 21, 24, 44, 34, 56, 19],\n",
        "[ 15, 17, 14, 19, 21, 31, 32, 62, 22],\n",
        "[ 15, 17, 13, 19, 20, 26, 42, 61, 22],\n",
        "[ 22, 24, 21, 20, 15, 21, 53, 44, 23],\n",
        "[ 15, 14, 18, 8, 11, 32, 54, 37, 16],\n",
        "[ 6, 6, 8, 13, 12, 37, 46, 43, 6],\n",
        "[ 26, 22, 30, 20, 25, 47, 79, 22, 23],\n",
        "[ 15, 13, 30, 11, 19, 58, 67, 32, 16],\n",
        "[ 15, 10, 18, 17, 22, 46, 56, 49, 10]\n",
        "])\n",
        "supply = [13, 7, 14, 10, 15, 13, 9, 15, 12]\n",
        "demand = [3, 9, 3, 6, 3, 12, 36, 24, 12]\n",
        "solution = potential_method(supply, demand, costs)\n",
        "print(solution)\n",
        "print('total cost: ', get_total_cost(costs, solution)*4.7382)\n"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "%%timeit\n",
        "smplx(supply, demand, costs)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "K-U1f1Fjerqb",
        "outputId": "1ae53431-a35c-4b7a-d197-f3f359ed3d03"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "10 loops, best of 5: 45.4 ms per loop\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "%%timeit\n",
        "potential_method(supply, demand, costs)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "eTkroiD1dUUf",
        "outputId": "ff5d8cbc-2e55-4389-8684-6b05b17c6cf6"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "100 loops, best of 5: 6.21 ms per loop\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "We can notice the superiority of the potential method over the simplex method by almost 10 times. "
      ],
      "metadata": {
        "id": "da6UWowefGvX"
      }
    },
    {
      "cell_type": "code",
      "source": [
        ""
      ],
      "metadata": {
        "id": "Dc1XyUPWfHbx"
      },
      "execution_count": null,
      "outputs": []
    }
  ],
  "metadata": {
    "kernelspec": {
      "display_name": "Python 3 (ipykernel)",
      "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.9.7"
    },
    "colab": {
      "name": "Transport_problem_code(Poltavtsev).ipynb\"",
      "provenance": [],
      "include_colab_link": true
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}