transpotation_probelm_using_VAM.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_balanced(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": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "def vogel(supply, demand,costs):\n",
    "    supply_copy = supply.copy()\n",
    "    demand_copy = demand.copy()\n",
    "    m=len(supply)\n",
    "    n=len(demand)\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",
    "    cost=0\n",
    "    bfs_arr = [[0 for i in range(n)] for j in range(m)] \n",
    "    for item in bfs:\n",
    "        bfs_arr[item[0][0]][item[0][1]]=item[1]\n",
    "    print('\\n The initial bfs is:\\n',bfs_arr)\n",
    "    for item in bfs:\n",
    "        cost=cost+costs[item[0][0]][item[0][1]]*item[1]\n",
    "    print('total bfs cost is: ',cost)\n",
    "    return bfs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "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": 18,
   "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": 19,
   "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": 20,
   "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": 21,
   "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": 22,
   "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": 23,
   "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": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "def transportation_method(supply, demand, costs, penalties = None):\n",
    "    balanced_supply, balanced_demand, balanced_costs = get_balanced(\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(vogel(balanced_supply, balanced_demand,costs))\n",
    "    ans = np.zeros((len(costs), len(costs[0])))\n",
    "    for (i, j), v in basic_variables:\n",
    "        ans[i][j] = int(v)\n",
    "\n",
    "    return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_total_cost(costs, ans):\n",
    "    total_cost = 0\n",
    "    for i, row in enumerate(costs):\n",
    "        for j, cost in enumerate(row):\n",
    "            total_cost += cost * ans[i][j]\n",
    "    return total_cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Enter m:3\n",
      "Enter n:4\n",
      "Enter all costs in one line\n",
      "2 2 2 1 10 8 5 4 7 6 6 8\n",
      "\n",
      " The costs are:\n",
      " [[ 2  2  2  1]\n",
      " [10  8  5  4]\n",
      " [ 7  6  6  8]]\n",
      "\n",
      "\n",
      "Enter the supply values : 30 70 50\n",
      "\n",
      "\n",
      "Enter the demand values : 40 30 40 40\n",
      "\n",
      "\n",
      "\n",
      " The initial bfs is:\n",
      " [[30, 0, 0, 0], [10, 30, 30, 0], [0, 0, 10, 40]]\n",
      "total bfs cost is:  930\n",
      "\n",
      "\n",
      "\n",
      " The optimal solution is:\n",
      " [[30.  0.  0.  0.]\n",
      " [ 0.  0. 30. 40.]\n",
      " [10. 30. 10.  0.]]\n",
      "total optimal cost:  680.0\n"
     ]
    }
   ],
   "source": [
    "m=int(input(\"Enter m:\"))\n",
    "n=int(input(\"Enter n:\"))\n",
    "print(\"Enter all costs in one line\")\n",
    "entries = list(map(int, input().split()))  \n",
    "costs = np.array(entries).reshape(m, n)\n",
    "print('\\n The costs are:\\n',costs)\n",
    "print('\\n')\n",
    "supply = list(map(int,input(\"Enter the supply values : \").strip().split()))[:m]\n",
    "print('\\n')\n",
    "demand = list(map(int,input(\"Enter the demand values : \").strip().split()))[:n]\n",
    "print('\\n')\n",
    "ans = transportation_method(supply, demand, costs)\n",
    "print('\\n')\n",
    "print('\\n The optimal solution is:\\n',ans)\n",
    "print('total optimal cost: ', get_total_cost(costs, ans))"
   ]
  },
  {
   "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.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}