transportation_problem_using_NorthWestRule.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Transportation Problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Balancing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "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": {},
   "source": [
    "supply less than demand"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([40, 30, 10], [30, 50], [[3, 4], [2, 4], [3, 1]])"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "supply = [40, 30]\n",
    "demand = [30, 50]\n",
    "costs = [\n",
    "    [3, 4],\n",
    "    [2, 4]\n",
    "]\n",
    "penalties = [3, 1]\n",
    "get_balanced_tp(supply, demand, costs, penalties)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "demand less than supply"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([40, 30], [30, 30, 10], [[3, 4], [2, 4], [0, 0]])"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "supply = [40, 30]\n",
    "demand = [30, 30]\n",
    "costs = [\n",
    "    [3, 4],\n",
    "    [2, 4]\n",
    "]\n",
    "get_balanced_tp(supply, demand, costs, penalties)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## North West Corner Method"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "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": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "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": {},
   "source": [
    "## Transportation Simplex Method"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "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": 8,
   "metadata": {},
   "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": 9,
   "metadata": {},
   "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": 10,
   "metadata": {},
   "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": 11,
   "metadata": {},
   "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": 12,
   "metadata": {},
   "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": 13,
   "metadata": {},
   "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": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def transportation_simplex_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": 15,
   "metadata": {},
   "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": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[30.  0.  0.  0.]\n",
      " [ 0.  0. 30. 40.]\n",
      " [10. 30. 10.  0.]]\n",
      "total cost:  680.0\n"
     ]
    }
   ],
   "source": [
    "costs = [\n",
    "    [ 2, 2, 2, 1],\n",
    "    [10, 8, 5, 4],\n",
    "    [ 7, 6, 6, 8]\n",
    "]\n",
    "supply = [30, 70, 50]\n",
    "demand = [40, 30, 40, 40]\n",
    "solution = transportation_simplex_method(supply, demand, costs)\n",
    "print(solution)\n",
    "print('total cost: ', get_total_cost(costs, solution))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 0., 10.,  0.],\n",
       "       [60., 10., 10.],\n",
       "       [15.,  0.,  0.],\n",
       "       [ 0.,  0., 40.]])"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "transportation_simplex_method(\n",
    "    [10, 80, 15, 40],\n",
    "    [75, 20, 50],\n",
    "    [\n",
    "        [5, 1, 7],\n",
    "        [6, 4, 6],\n",
    "        [3, 2, 5],\n",
    "        [5, 3, 2]\n",
    "    ]\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0., 0., 0.],\n",
       "       [0., 0., 0.],\n",
       "       [0., 0., 0.],\n",
       "       [0., 0., 0.]])"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "transportation_simplex_method(\n",
    "    [0, 0, 0, 0],\n",
    "    [0, 0, 0],\n",
    "    [\n",
    "        [0, 0, 0],\n",
    "        [0, 0, 0],\n",
    "        [0, 0, 0],\n",
    "        [0, 0, 0]\n",
    "    ]\n",
    ")"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}