Operation Research-Program (1).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "06e4900e",
   "metadata": {},
   "source": [
    "# 1. Simplex Method"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "fec30737",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "solution:  [3.0, 1.4999999999999998, 0, 0, 2.5000000000000004, 0.5000000000000002, 0]\n",
      "Solution = > \n",
      "19.5\n"
     ]
    }
   ],
   "source": [
    "c = [4, 5, 0, 0, 0, 0]\n",
    "A = [\n",
    "    [6, 4, 1, 0, 0, 0],\n",
    "    [1, 2, 0, 1, 0, 0],\n",
    "    [-1, 1, 0, 0, 1, 0],\n",
    "    [0 , 1, 0, 0, 0, 1],\n",
    "]\n",
    "b = [24, 6, 1, 2]\n",
    "\n",
    "import numpy as np\n",
    "def to_tableau(c, A, b):\n",
    "    xb = [eq + [x] for eq, x in zip(A, b)]\n",
    "    z = c + [0]\n",
    "    return xb + [z]\n",
    "def can_be_improved(tableau):\n",
    "    z = tableau[-1]\n",
    "    return any(x > 0 for x in z[:-1])\n",
    "import math\n",
    "\n",
    "def get_pivot_position(tableau):\n",
    "    z = tableau[-1]\n",
    "    column = next(i for i, x in enumerate(z[:-1]) if x > 0)\n",
    "    \n",
    "    restrictions = []\n",
    "    for eq in tableau[:-1]:\n",
    "        el = eq[column]\n",
    "        restrictions.append(math.inf if el <= 0 else eq[-1] / el)\n",
    "\n",
    "    row = restrictions.index(min(restrictions))\n",
    "    return row, column\n",
    "def pivot_step(tableau, pivot_position):\n",
    "    new_tableau = [[] for eq in tableau]\n",
    "    \n",
    "    i, j = pivot_position\n",
    "    pivot_value = tableau[i][j]\n",
    "    new_tableau[i] = np.array(tableau[i]) / pivot_value\n",
    "    \n",
    "    for eq_i, eq in enumerate(tableau):\n",
    "        if eq_i != i:\n",
    "            multiplier = np.array(new_tableau[i]) * tableau[eq_i][j]\n",
    "            new_tableau[eq_i] = np.array(tableau[eq_i]) - multiplier\n",
    "   \n",
    "    return new_tableau\n",
    "def is_basic(column):\n",
    "    return sum(column) == 1 and len([c for c in column if c == 0]) == len(column) - 1\n",
    "\n",
    "def get_solution(tableau):\n",
    "    columns = np.array(tableau).T\n",
    "    solutions = []\n",
    "    for column in columns:\n",
    "        solution = 0\n",
    "        if is_basic(column):\n",
    "            one_index = column.tolist().index(1)\n",
    "            solution = columns[-1][one_index]\n",
    "        solutions.append(solution)\n",
    "        \n",
    "    return solutions\n",
    "def simplex(c, A, b):\n",
    "    tableau = to_tableau(c, A, b)\n",
    "\n",
    "    while can_be_improved(tableau):\n",
    "        pivot_position = get_pivot_position(tableau)\n",
    "        tableau = pivot_step(tableau, pivot_position)\n",
    "\n",
    "    return get_solution(tableau)\n",
    "\n",
    "solution = simplex(c, A, b)\n",
    "print('solution: ', solution)\n",
    "\n",
    "print(\"Solution = > \")\n",
    "print(solution[0]*c[0] + solution[1]*c[1])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8473cc61",
   "metadata": {},
   "source": [
    "# 2. N/W Corner Method"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "6153479f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[((0, 0), 4), ((1, 0), 0), ((1, 1), 4), ((1, 2), 1), ((2, 2), 3), ((3, 2), 1), ((3, 3), 3), ((3, 4), 2), ((3, 5), 3)]\n"
     ]
    }
   ],
   "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\n",
    "supply = [4, 5, 3, 9]\n",
    "demand = [4, 4, 5, 3, 2, 3]\n",
    "bfs = north_west_corner(supply, demand)\n",
    "print(bfs)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "a60166dd",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Enter m:2\n",
      "Enter n:3\n",
      "Enter all costs in one line\n",
      "1 2 3 4 5 6\n",
      "\n",
      " The costs are:\n",
      " [[1 2 3]\n",
      " [4 5 6]]\n",
      "\n",
      "\n",
      "Enter the supply values : 1 2\n",
      "\n",
      "\n",
      "Enter the demand values : 1 2\n",
      "\n",
      "\n",
      "[((0, 0), 1), ((1, 0), 0), ((1, 1), 2)]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "((1, 0), 0)"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "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",
    "\n",
    "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\n",
    "\n",
    "bfs = north_west_corner(supply, demand)\n",
    "print(bfs)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c7ad1268",
   "metadata": {},
   "source": [
    "# 3. VAM Method"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "83c1ec87",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Enter m:4\n",
      "Enter n:4\n",
      "Enter all costs in one line\n",
      "5 1 3 3 3 3 5 4 6 4 4 3 4 -1 4 2\n",
      "\n",
      " The costs are:\n",
      " [[ 5  1  3  3]\n",
      " [ 3  3  5  4]\n",
      " [ 6  4  4  3]\n",
      " [ 4 -1  4  2]]\n",
      "\n",
      "\n",
      "Enter the supply values : 34 15 12 19\n",
      "\n",
      "\n",
      "Enter the demand values : 21 25 17 17\n",
      "\n",
      "\n",
      "\n",
      " The initial bfs is:\n",
      " [[21, 13, 0, 0], [0, 12, 3, 0], [0, 0, 12, 0], [0, 0, 2, 17]]\n",
      "total bfs cost is:  259\n",
      "\n",
      "\n",
      "\n",
      " The optimal solution is:\n",
      " [[ 6.  6. 17.  5.]\n",
      " [15.  0.  0.  0.]\n",
      " [ 0.  0.  0. 12.]\n",
      " [ 0. 19.  0.  0.]]\n",
      "total optimal cost:  164.0\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "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\n",
    "\n",
    "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\n",
    "\n",
    "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\n",
    "\n",
    "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\n",
    "\n",
    "def can_be_improved(ws):\n",
    "    for p, v in ws:\n",
    "        if v > 0: return True\n",
    "    return False\n",
    "\n",
    "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]\n",
    "\n",
    "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\n",
    "\n",
    "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])\n",
    "\n",
    "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\n",
    "\n",
    "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\n",
    "\n",
    "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\n",
    "\n",
    "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": "markdown",
   "id": "103789e3",
   "metadata": {},
   "source": [
    "# 4. Disjkstra's Algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "0d5b7ff1",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Distance of  a  from source vertex:  0\n",
      "Distance of  b  from source vertex:  7\n",
      "Distance of  c  from source vertex:  10\n",
      "Distance of  d  from source vertex:  16\n",
      "Distance of  e  from source vertex:  34\n",
      "Distance of  f  from source vertex:  27\n",
      "Distance of  g  from source vertex:  41\n",
      "Distance of  h  from source vertex:  42\n",
      "Distance of  i  from source vertex:  44\n",
      "44\n"
     ]
    }
   ],
   "source": [
    "import sys\n",
    "vertices = [[0, 1, 1, 0, 0, 0, 0, 0, 0],\n",
    "            [1, 0, 0, 1, 1, 0, 0, 0, 0],\n",
    "            [1, 0, 0, 1, 0, 0, 1, 0, 0],\n",
    "            [0, 1, 1, 0, 0, 1, 0, 0, 0],\n",
    "            [0, 1, 0, 0, 0, 0, 0, 1, 0],\n",
    "            [0, 0, 0, 1, 0, 0, 0, 1, 1],\n",
    "            [0, 0, 1, 0, 0, 0, 0, 0, 1],\n",
    "            [0, 0, 0, 0, 1, 1, 0, 0, 1],\n",
    "            [0, 0, 0, 0, 0, 1, 1, 1, 0]]\n",
    "\n",
    "edges = [[0, 7, 10, 0, 0, 0, 0, 0, 0],\n",
    "            [7, 0, 0, 9, 27, 0, 0, 0, 0],\n",
    "            [10, 0, 0, 8, 0, 0, 31, 0, 0],\n",
    "            [0, 9, 8, 0, 0, 11, 0, 0, 0],\n",
    "            [0, 27, 0, 0, 0, 0, 0, 15, 0],\n",
    "            [0, 0, 0, 11, 0, 0, 0, 15, 17],\n",
    "            [0, 0, 31, 0, 0, 0, 0, 0, 32],\n",
    "            [0, 0, 0, 0, 15, 15, 0, 0, 21],\n",
    "            [0, 0, 0, 0, 0, 17, 32, 21, 0]]\n",
    "\n",
    "def to_be_visited():\n",
    "    global visited_and_distance\n",
    "    v = -10\n",
    "    for index in range(num_of_vertices):\n",
    "        if visited_and_distance[index][0] == 0 \\\n",
    "            and (v < 0 or visited_and_distance[index][1] <=\n",
    "                 visited_and_distance[v][1]):\n",
    "            v = index\n",
    "    return v\n",
    "\n",
    "\n",
    "num_of_vertices = len(vertices[0])\n",
    "\n",
    "visited_and_distance = [[0, 0]]\n",
    "for i in range(num_of_vertices-1):\n",
    "    visited_and_distance.append([0, sys.maxsize])\n",
    "\n",
    "for vertex in range(num_of_vertices):\n",
    "\n",
    "    to_visit = to_be_visited()\n",
    "    for neighbor_index in range(num_of_vertices):\n",
    "\n",
    "        if vertices[to_visit][neighbor_index] == 1 and \\\n",
    "                visited_and_distance[neighbor_index][0] == 0:\n",
    "            new_distance = visited_and_distance[to_visit][1] \\\n",
    "                + edges[to_visit][neighbor_index]\n",
    "            if visited_and_distance[neighbor_index][1] > new_distance:\n",
    "                visited_and_distance[neighbor_index][1] = new_distance\n",
    "        \n",
    "        visited_and_distance[to_visit][0] = 1\n",
    "\n",
    "i = 0\n",
    "j = 0\n",
    "\n",
    "for distance in visited_and_distance:\n",
    "    \n",
    "    print(\"Distance of \", chr(ord('a') + i),\n",
    "          \" from source vertex: \", distance[1])\n",
    "    \n",
    "    i = i + 1\n",
    "    j = j + i\n",
    "\n",
    "j = j - 1\n",
    "    \n",
    "print(j)    "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7b045639",
   "metadata": {},
   "source": [
    "# 5. Floyd Algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "8212e4cc",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0  3  10  8  12   \n",
      "3  0  11  5  9   \n",
      "10  11  0  6  10   \n",
      "8  5  6  0  4   \n",
      "12  9  10  4  0   \n"
     ]
    }
   ],
   "source": [
    "nV = 5\n",
    "INF = 999\n",
    "\n",
    "def floyd_warshall(G):\n",
    "    distance = list(map(lambda i: list(map(lambda j: j, i)), G))\n",
    "\n",
    "    for k in range(nV):\n",
    "        for i in range(nV):\n",
    "            for j in range(nV):\n",
    "                distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])\n",
    "    print_solution(distance)\n",
    "\n",
    "def print_solution(distance):\n",
    "    for i in range(nV):\n",
    "        for j in range(nV):\n",
    "            if(distance[i][j] == INF):\n",
    "                print(\"INF\", end=\" \")\n",
    "            else:\n",
    "                print(distance[i][j], end=\"  \")\n",
    "        print(\" \")\n",
    "\n",
    "\n",
    "G = [[0, 3, 10, INF, INF],\n",
    "         [3, 0, INF, 5, INF],\n",
    "         [10, INF, 0, 6, 15],\n",
    "         [INF, 5, 6, 0, 4],\n",
    "         [INF, INF, INF, 4, 0]]\n",
    "\n",
    "floyd_warshall(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "837dba66",
   "metadata": {},
   "outputs": [],
   "source": [
    "def initialise(V):\n",
    "    global dis, Next\n",
    "    for i in range(V):\n",
    "        for j in range(V):\n",
    "            dis[i][j] = graph[i][j]\n",
    "            if (graph[i][j] == INF):\n",
    "                Next[i][j] = -1\n",
    "            else:\n",
    "                Next[i][j] = j\n",
    "                \n",
    "def constructPath(u, v):\n",
    "    global graph, Next    \n",
    "    if (Next[u][v] == -1):\n",
    "        return {}\n",
    "    path = [u]\n",
    "    while (u != v):\n",
    "        u = Next[u][v]\n",
    "        path.append(u)\n",
    "    return path\n",
    "\n",
    "def floydWarshall(V):\n",
    "    global dist, Next\n",
    "    for k in range(V):\n",
    "        for i in range(V):\n",
    "            for j in range(V):\n",
    "                if (dis[i][k] == INF or dis[k][j] == INF):\n",
    "                    continue\n",
    "                if (dis[i][j] > dis[i][k] + dis[k][j]):\n",
    "                    dis[i][j] = dis[i][k] + dis[k][j]\n",
    "                    Next[i][j] = Next[i][k]\n",
    "                    \n",
    "def printPath(path):\n",
    "    n = len(path)\n",
    "    for i in range(n - 1):\n",
    "        print(path[i], end=\" -> \")\n",
    "    print (path[n - 1])\n",
    "    \n",
    "if __name__ == '__main__':\n",
    "    MAXM,INF = 100,10**7\n",
    "    dis = [[-1 for i in range(MAXM)] for i in range(MAXM)]\n",
    "    Next = [[-1 for i in range(MAXM)] for i in range(MAXM)]\n",
    "    V = 4\n",
    "    graph = [ [ 0, 3, INF, 7 ],\n",
    "            [ 8, 0, 2, INF ],\n",
    "            [ 5, INF, 0, 1 ],\n",
    "            [ 2, INF, INF, 0 ] ]\n",
    "    \n",
    "    initialise(V)\n",
    "    floydWarshall(V)\n",
    "    path = []\n",
    "\n",
    "    print(\"Shortest path from 1 to 3: \", end = \"\")\n",
    "    path = constructPath(1, 3)\n",
    "    printPath(path)\n",
    " \n",
    "    # Path from node 0 to 2\n",
    "    print(\"Shortest path from 0 to 2: \", end = \"\")\n",
    "    path = constructPath(0, 2)\n",
    "    printPath(path)\n",
    " \n",
    "    # Path from node 3 to 2\n",
    "    print(\"Shortest path from 3 to 2: \", end = \"\")\n",
    "    path = constructPath(3, 2)\n",
    "    printPath(path)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "53a36211",
   "metadata": {},
   "source": [
    "# 6. Prim's Algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "1bf274eb",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Edge : Weight\n",
      "\n",
      "0-1:9\n",
      "1-3:19\n",
      "3-4:31\n",
      "3-2:51\n"
     ]
    }
   ],
   "source": [
    "INF = 9999999\n",
    "V = 5\n",
    "G = [[0, 9, 75, 0, 0],\n",
    "     [9, 0, 95, 19, 42],\n",
    "     [75, 95, 0, 51, 66],\n",
    "     [0, 19, 51, 0, 31],\n",
    "     [0, 42, 66, 31, 0]]\n",
    "selected = [0, 0, 0, 0, 0]\n",
    "no_edge = 0\n",
    "selected[0] = True\n",
    "print(\"Edge : Weight\\n\")\n",
    "while (no_edge < V - 1):\n",
    "    minimum = INF\n",
    "    x = 0\n",
    "    y = 0\n",
    "    for i in range(V):\n",
    "        if selected[i]:\n",
    "            for j in range(V):\n",
    "                if ((not selected[j]) and G[i][j]):  \n",
    "                    if minimum > G[i][j]:\n",
    "                        minimum = G[i][j]\n",
    "                        x = i\n",
    "                        y = j\n",
    "    print(str(x) + \"-\" + str(y) + \":\" + str(G[x][y]))\n",
    "    selected[y] = True\n",
    "    no_edge += 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5d051dd4",
   "metadata": {},
   "source": [
    "# 7. Kruskal's Algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "9cdc6059",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 - 2: 2\n",
      "2 - 5: 2\n",
      "2 - 3: 3\n",
      "3 - 4: 3\n",
      "0 - 1: 4\n"
     ]
    }
   ],
   "source": [
    "class Graph:\n",
    "    def __init__(self, vertices):\n",
    "        self.V = vertices\n",
    "        self.graph = []\n",
    "\n",
    "    def add_edge(self, u, v, w):\n",
    "        self.graph.append([u, v, w])\n",
    "\n",
    "    def find(self, parent, i):\n",
    "        if parent[i] == i:\n",
    "            return i\n",
    "        return self.find(parent, parent[i])\n",
    "\n",
    "    def apply_union(self, parent, rank, x, y):\n",
    "        xroot = self.find(parent, x)\n",
    "        yroot = self.find(parent, y)\n",
    "        if rank[xroot] < rank[yroot]:\n",
    "            parent[xroot] = yroot\n",
    "        elif rank[xroot] > rank[yroot]:\n",
    "            parent[yroot] = xroot\n",
    "        else:\n",
    "            parent[yroot] = xroot\n",
    "            rank[xroot] += 1\n",
    "\n",
    "    def kruskal_algo(self):\n",
    "        result = []\n",
    "        i, e = 0, 0\n",
    "        self.graph = sorted(self.graph, key=lambda item: item[2])\n",
    "        parent = []\n",
    "        rank = []\n",
    "        for node in range(self.V):\n",
    "            parent.append(node)\n",
    "            rank.append(0)\n",
    "        while e < self.V - 1:\n",
    "            u, v, w = self.graph[i]\n",
    "            i = i + 1\n",
    "            x = self.find(parent, u)\n",
    "            y = self.find(parent, v)\n",
    "            if x != y:\n",
    "                e = e + 1\n",
    "                result.append([u, v, w])\n",
    "                self.apply_union(parent, rank, x, y)\n",
    "        for u, v, weight in result:\n",
    "            print(\"%d - %d: %d\" % (u, v, weight))\n",
    "\n",
    "\n",
    "g = Graph(6)\n",
    "g.add_edge(0, 1, 4)\n",
    "g.add_edge(0, 2, 4)\n",
    "g.add_edge(1, 2, 2)\n",
    "g.add_edge(1, 0, 4)\n",
    "g.add_edge(2, 0, 4)\n",
    "g.add_edge(2, 1, 2)\n",
    "g.add_edge(2, 3, 3)\n",
    "g.add_edge(2, 5, 2)\n",
    "g.add_edge(2, 4, 4)\n",
    "g.add_edge(3, 2, 3)\n",
    "g.add_edge(3, 4, 3)\n",
    "g.add_edge(4, 2, 4)\n",
    "g.add_edge(4, 3, 3)\n",
    "g.add_edge(5, 2, 2)\n",
    "g.add_edge(5, 4, 3)\n",
    "g.kruskal_algo()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "55285ab7",
   "metadata": {},
   "source": [
    "# 8. CPM"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "51d70d41",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The current critical path is: ['B', 'E', 'G', 'H']\n",
      "--------------------------------------------------\n",
      "The value of the CPM is: 19 days\n"
     ]
    }
   ],
   "source": [
    "import pandas as pd\n",
    "import datetime\n",
    "\n",
    "import matplotlib.pyplot as plt\n",
    "import networkx as nx\n",
    "from criticalpath import Node\n",
    "\n",
    "# set up the tasks:\n",
    "tasks = [(\"A\", {\"Duration\": 2}), \n",
    "         (\"B\", {\"Duration\": 4}), \n",
    "         (\"C\", {\"Duration\": 3}), \n",
    "         (\"D\", {\"Duration\": 1}), \n",
    "         (\"E\", {\"Duration\": 6}),\n",
    "         (\"F\", {\"Duration\": 5}),\n",
    "         (\"G\", {\"Duration\": 7}),\n",
    "         (\"H\", {\"Duration\": 2})]\n",
    "\n",
    "dependencies = [(\"A\", \"D\"), \n",
    "                (\"B\", \"E\"), \n",
    "                (\"C\", \"F\"),\n",
    "                (\"D\", \"G\"), \n",
    "                (\"E\", \"G\"),\n",
    "                (\"G\", \"H\"),\n",
    "                (\"F\", \"H\")]\n",
    "\n",
    "proj = Node('Project')\n",
    "for t in tasks:\n",
    "    proj.add(Node(t[0], duration=t[1][\"Duration\"]))\n",
    "for d in dependencies:\n",
    "    proj.link(d[0],d[1])\n",
    "proj.update_all()\n",
    "crit_path = [str(n) for n in proj.get_critical_path()]\n",
    "proj_duration = proj.duration\n",
    "\n",
    "print(f\"The current critical path is: {crit_path}\")\n",
    "print(\"-\"*50)\n",
    "print(f\"The value of the CPM is: {proj_duration} days\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0af0ce73",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "080274bd",
   "metadata": {},
   "source": [
    "# 9. PERT"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "0c273f31",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "initialize a graph:\n",
      "add activity to project:\n",
      "print activity:\n",
      "Activity Name: j, Duration: 16\n",
      "critical path:\n",
      "[start, j, end]\n",
      "maximum shorting times:\n",
      "{start: 4, j: 7, end: 1}\n",
      "slack time in descending order:\n",
      "[(f, 10), (d, 9), (e, 9), (a, 8), (b, 8), (c, 8)]\n",
      "sum of slack times:\n",
      "52\n",
      "iterate over all the activities with iterator:\n",
      "Activity Name: start, Duration: 5\n",
      "Activity Name: a, Duration: 2\n",
      "Activity Name: b, Duration: 3\n",
      "Activity Name: c, Duration: 3\n",
      "Activity Name: d, Duration: 4\n",
      "Activity Name: e, Duration: 3\n",
      "Activity Name: f, Duration: 6\n",
      "Activity Name: end, Duration: 2\n",
      "Activity Name: j, Duration: 16\n",
      "isolated activities:\n",
      "[]\n",
      "print pert:\n",
      "Activities:\n",
      "Activity Name: start, Duration: 5\n",
      "Activity Name: a, Duration: 2\n",
      "Activity Name: b, Duration: 3\n",
      "Activity Name: c, Duration: 3\n",
      "Activity Name: d, Duration: 4\n",
      "Activity Name: e, Duration: 3\n",
      "Activity Name: f, Duration: 6\n",
      "Activity Name: end, Duration: 2\n",
      "Activity Name: j, Duration: 16\n",
      "Connections:\n",
      "{start: [a, d, f, j], a: [b], b: [c], c: [end], d: [e], e: [end], f: [end], end: [], j: [end]}\n",
      "Project Duration:\n",
      "23\n"
     ]
    }
   ],
   "source": [
    "import math\n",
    "import logging\n",
    "\n",
    "logging.basicConfig(filename='logger.log', level=logging.INFO, format='%(name)s - %(levelname)s - %(message)s')\n",
    "\n",
    "class Activity:\n",
    "    def __init__(self, name, duration):\n",
    "        logging.info(\"new activity has been created, name: \" + name + \", duration: \" + str(duration))\n",
    "        self.name = str(name).lower()\n",
    "        self.duration = duration\n",
    "\n",
    "    # str method for activity\n",
    "    def __str__(self):\n",
    "        logging.info(\"str method called for '\" + self.name + \"' activity\")\n",
    "        return \"Activity Name: \" + self.name + \", Duration: \" + str(self.duration)\n",
    "\n",
    "\n",
    "    def __repr__(self):\n",
    "        logging.info(\"repr method called for '\" + self.name + \"' activity\")\n",
    "        return self.name\n",
    "\n",
    "class Pert:\n",
    "    def __init__(self, graph={}):\n",
    "        logging.info(\"new pert: '\" + repr(self) + \"' has been created, graph: \" + str(graph))\n",
    "        self.forward_dict = graph   \n",
    "        self.backward_dict = {}     \n",
    "        self.info_dict = {}         \n",
    "        self.start_activity = Activity\n",
    "        self.end_activity = Activity\n",
    "        self.reset_initial_graph()  \n",
    "        self.generate_info()       \n",
    "\n",
    "    def __str__(self):\n",
    "        logging.info(\"str method called for '\" + repr(self) + \"' pert\")\n",
    "        iterator = iter(self)\n",
    "        graph_str = 'Activities:\\n'\n",
    "        for activity in iterator:\n",
    "            graph_str += str(activity) + '\\n'\n",
    "        return (graph_str + 'Connections:\\n' \n",
    "            + str(self.forward_dict)\n",
    "            + '\\nProject Duration:\\n' \n",
    "            + str(self.info_dict[self.end_activity]['ef']))\n",
    "\n",
    "    def __iter__(self):\n",
    "        logging.info(\"new iterator for '\" + repr(self) + \"' pert\")\n",
    "        return iter(self.forward_dict)\n",
    "\n",
    "    def reset_initial_graph(self):\n",
    "        logging.info(\"'reset_initial_graph' method has been called for '\" + repr(self) + \"' pert\")\n",
    "        for activity in self.forward_dict:\n",
    "            self.backward_dict[activity] = []\n",
    "        for activity in self.forward_dict:\n",
    "            if activity.name == \"start\":\n",
    "                self.start_activity = activity\n",
    "            if activity.name == \"end\":\n",
    "                self.end_activity = activity\n",
    "            for node in self.forward_dict[activity]:\n",
    "                self.backward_dict[node].append(activity)\n",
    "        self.reset_info()\n",
    "\n",
    "    def reset_info(self):\n",
    "        logging.info(\"'reset_info' method has been called for '\" + repr(self) + \"' pert\")\n",
    "        for activity in self.forward_dict:\n",
    "            self.info_dict[activity] = {\n",
    "                \"duration\": activity.duration, \n",
    "                \"es\": 0, \"ef\": 0, \"ls\": 0, \"lf\": math.inf, \n",
    "                \"slack\": 0}\n",
    "\n",
    "    def generate_info(self):\n",
    "        logging.info(\"'generate_info' method has been called for '\" + repr(self) + \"' pert\")\n",
    "        if self.forward_dict == {}:\n",
    "            return\n",
    "        self.info_dict[self.start_activity][\"ef\"] = self.info_dict[self.start_activity][\"duration\"]\n",
    "        self.start_to_end_scan(self.start_activity)\n",
    "        self.info_dict[self.end_activity][\"lf\"] = self.info_dict[self.end_activity][\"ef\"]\n",
    "        self.info_dict[self.end_activity][\"ls\"] = self.info_dict[self.end_activity][\"lf\"] - self.info_dict[self.end_activity][\"duration\"]\n",
    "        self.end_to_start_scan(self.end_activity)\n",
    "        self.clatulate_slack()\n",
    "        self.generate_info_for_isolated()\n",
    "\n",
    "    def start_to_end_scan(self, activity):\n",
    "        logging.info(\"'start_to_end_scan' method has been called for '\" + repr(self) + \"' pert\")\n",
    "        for node in self.forward_dict[activity]:\n",
    "            if self.info_dict[activity][\"ef\"] > self.info_dict[node][\"es\"]:\n",
    "                self.info_dict[node][\"es\"] = self.info_dict[activity][\"ef\"]\n",
    "                self.info_dict[node][\"ef\"] = self.info_dict[node][\"es\"] + self.info_dict[node][\"duration\"]\n",
    "            self.start_to_end_scan(node)\n",
    "\n",
    "    def end_to_start_scan(self, activity):\n",
    "        logging.info(\"'end_to_start_scan' method has been called for '\" + repr(self) + \"' pert\")\n",
    "        for node in self.backward_dict[activity]:\n",
    "            if (self.info_dict[node][\"lf\"] > self.info_dict[activity][\"ls\"]):\n",
    "                self.info_dict[node][\"lf\"] = self.info_dict[activity][\"ls\"]\n",
    "                self.info_dict[node][\"ls\"] = (self.info_dict[node][\"lf\"] - self.info_dict[node][\"duration\"])\n",
    "            self.end_to_start_scan(node)\n",
    "\n",
    "    def clatulate_slack(self):\n",
    "        logging.info(\"'clatulate_slack' method has been called for '\" + repr(self) + \"' pert\")\n",
    "        for activity in self.forward_dict:\n",
    "            self.info_dict[activity][\"slack\"] = self.info_dict[activity][\"lf\"] - self.info_dict[activity][\"ef\"]\n",
    "\n",
    "    def generate_info_for_isolated(self):\n",
    "        logging.info(\"'generate_info_for_isolated' method has been called for '\" + repr(self) + \"' pert\")\n",
    "        isolated = self.find_isolated()\n",
    "        for activity in isolated:\n",
    "            self.info_dict[activity][\"ef\"] = self.info_dict[activity][\"es\"] + self.info_dict[activity][\"duration\"]\n",
    "            self.info_dict[activity][\"lf\"] = self.info_dict[self.end_activity][\"lf\"]\n",
    "            self.info_dict[activity][\"ls\"] = self.info_dict[activity][\"lf\"] - self.info_dict[activity][\"duration\"]\n",
    "            self.info_dict[activity][\"slack\"] = self.info_dict[activity][\"lf\"] - self.info_dict[activity][\"ef\"]\n",
    "\n",
    "    def add_activity(self, activity, in_connections=[], out_connections=[]):\n",
    "        logging.info(\"'add_activity' method has been called for '\" + repr(self) + \"' pert\")\n",
    "        if activity in self.forward_dict:\n",
    "            return\n",
    "        self.forward_dict[activity] = out_connections\n",
    "        self.backward_dict[activity] = in_connections\n",
    "        if in_connections != []:\n",
    "            for node in in_connections:\n",
    "                if self.forward_dict[node] is None:\n",
    "                    self.forward_dict[node] = []\n",
    "                self.forward_dict[node] += [activity]\n",
    "        if out_connections != []:\n",
    "            for node in out_connections:\n",
    "                if self.backward_dict[node] is None:\n",
    "                    self.backward_dict[node] = []\n",
    "                self.backward_dict[node] += [activity]\n",
    "        self.info_dict[activity] = {\n",
    "            \"duration\": activity.duration, \n",
    "            \"es\": 0, \"ef\": 0, \"ls\": 0, \"lf\": math.inf, \n",
    "            \"slack\": 0}\n",
    "        self.reset_info()\n",
    "        self.generate_info()\n",
    "\n",
    "    def find_isolated(self):\n",
    "        logging.info(\"'find_isolated' method has been called for '\" + repr(self) + \"' pert\")\n",
    "        isolated = list(self.info_dict)\n",
    "        for activity in self.forward_dict:\n",
    "            if self.forward_dict[activity] != [] and activity in isolated:\n",
    "                isolated.remove(activity)\n",
    "        for activity in self.backward_dict:\n",
    "            if self.backward_dict[activity] != [] and activity in isolated:\n",
    "                isolated.remove(activity)\n",
    "        return isolated\n",
    "    \n",
    "    def get_slack_for_each_activity(self):\n",
    "        logging.info(\"'get_slack_for_each_activity' method has been called for '\" + repr(self) + \"' pert\")\n",
    "        slacks = {activity: self.info_dict[activity][\"slack\"] for activity in self.info_dict if self.info_dict[activity][\"slack\"] != 0}\n",
    "        return sorted(slacks.items(), key=lambda kv: kv[1], reverse=True)\n",
    "    \n",
    "    def get_sum_of_slacks(self):\n",
    "        logging.info(\"'get_sum_of_slacks' method has been called for '\" + repr(self) + \"' pert\")\n",
    "        slacks = [kv[1] for kv in self.get_slack_for_each_activity()]\n",
    "        return sum(slacks)\n",
    "\n",
    "    def get_critical_path(self):\n",
    "        logging.info(\"'get_critical_path' method has been called for '\" + repr(self) + \"' pert\")\n",
    "        activity = self.start_activity\n",
    "        path = [activity]\n",
    "        while activity != self.end_activity :\n",
    "            for node in self.forward_dict[activity]:\n",
    "                if self.info_dict[node][\"slack\"] == 0:\n",
    "                    activity = node\n",
    "            path += [activity]\n",
    "        return path\n",
    "\n",
    "    def get_critical_path_with_length(self):\n",
    "        logging.info(\"'get_critical_path_with_length' method has been called for '\" + repr(self) + \"' pert\")\n",
    "        return {activity: activity.duration for activity in self.get_critical_path()}\n",
    "    \n",
    "    def shorten_critical_path(self):\n",
    "        logging.info(\"'shorten_critical_path' method has been called for '\" + repr(self) + \"' pert\")\n",
    "        critical_path = self.get_critical_path()\n",
    "        max_decrease_to_activities = {activity: activity.duration - 1 for activity in critical_path}\n",
    "        for i in range(0,  len(critical_path), 1):\n",
    "            for j in range(2, len(critical_path) - i, 1):\n",
    "                for path in self.get_all_alternative_paths(critical_path[i], critical_path[i + j]):\n",
    "                    for activity in critical_path[i + 1 : i + j : 1]:\n",
    "                        if path[1] not in critical_path and max_decrease_to_activities[activity] >= self.info_dict[path[1]][\"slack\"]:\n",
    "                            max_decrease_to_activities[activity] = self.info_dict[path[1]][\"slack\"] - 1\n",
    "        return max_decrease_to_activities\n",
    "\n",
    "    def get_all_alternative_paths(self, start_activity, end_activity, path=[]):\n",
    "        logging.info(\"'get_all_alternative_paths' method has been called for '\" + repr(self) + \"' pert\")\n",
    "        one_path = path + [start_activity]\n",
    "        if start_activity == end_activity:\n",
    "            return [one_path]\n",
    "        if start_activity not in self.info_dict:\n",
    "            return []\n",
    "        paths = []\n",
    "        for activity in self.forward_dict[start_activity]:\n",
    "            paths += self.get_all_alternative_paths(activity, end_activity, one_path)\n",
    "        return paths\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    start = Activity(\"start\", 5)\n",
    "    a = Activity(\"a\", 2)\n",
    "    b = Activity(\"b\", 3)\n",
    "    c = Activity(\"c\", 3)\n",
    "    d = Activity(\"d\", 4)\n",
    "    e = Activity(\"e\", 3)\n",
    "    f = Activity(\"f\", 6)\n",
    "    end = Activity(\"end\", 2)\n",
    "    graph = {start: [a, d, f], a: [b], b: [c], c: [end], d: [e], e: [end], f:[end], end:[]}\n",
    "    \n",
    "    print(\"initialize a graph:\")\n",
    "    pert = Pert(graph)\n",
    "    \n",
    "    j = Activity(\"j\", 16)\n",
    "    print(\"add activity to project:\")\n",
    "    pert.add_activity(j, [start], [end])\n",
    "    \n",
    "    print(\"print activity:\")\n",
    "    print(j)\n",
    "    print(\"critical path:\")\n",
    "    print(pert.get_critical_path())\n",
    "    \n",
    "    print(\"maximum shorting times:\")\n",
    "    print(pert.shorten_critical_path())\n",
    "    \n",
    "    print(\"slack time in descending order:\")\n",
    "    print(pert.get_slack_for_each_activity())\n",
    "    \n",
    "    print(\"sum of slack times:\")\n",
    "    print(pert.get_sum_of_slacks())\n",
    "    \n",
    "    print(\"iterate over all the activities with iterator:\")\n",
    "    for activity in iter(pert):\n",
    "        print(activity)\n",
    "        \n",
    "    print(\"isolated activities:\")\n",
    "    print(pert.find_isolated())\n",
    "    print(\"print pert:\")\n",
    "    print(pert)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e02ae7a9",
   "metadata": {},
   "source": [
    "# 10. Assignment Problem"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "3d03ae4b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Total cost = 265.0\n",
      "\n",
      "Worker 0 assigned to task 3. Cost: 70\n",
      "Worker 1 assigned to task 2. Cost: 55\n",
      "Worker 2 assigned to task 1. Cost: 95\n",
      "Worker 3 assigned to task 0. Cost: 45\n"
     ]
    }
   ],
   "source": [
    "from ortools.linear_solver import pywraplp\n",
    "\n",
    "\n",
    "def main():\n",
    "    costs = [\n",
    "        [90, 80, 75, 70],\n",
    "        [35, 85, 55, 65],\n",
    "        [125, 95, 90, 95],\n",
    "        [45, 110, 95, 115],\n",
    "        [50, 100, 90, 100],\n",
    "    ]\n",
    "    num_workers = len(costs)\n",
    "    num_tasks = len(costs[0])\n",
    "    solver = pywraplp.Solver.CreateSolver('SCIP')\n",
    "    x = {}\n",
    "    for i in range(num_workers):\n",
    "        for j in range(num_tasks):\n",
    "            x[i, j] = solver.IntVar(0, 1, '')\n",
    "\n",
    "    for i in range(num_workers):\n",
    "        solver.Add(solver.Sum([x[i, j] for j in range(num_tasks)]) <= 1)\n",
    "\n",
    "    for j in range(num_tasks):\n",
    "        solver.Add(solver.Sum([x[i, j] for i in range(num_workers)]) == 1)\n",
    "\n",
    "    objective_terms = []\n",
    "    for i in range(num_workers):\n",
    "        for j in range(num_tasks):\n",
    "            objective_terms.append(costs[i][j] * x[i, j])\n",
    "    solver.Minimize(solver.Sum(objective_terms))\n",
    "\n",
    "    status = solver.Solve()\n",
    "\n",
    "    if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE:\n",
    "        print(f'Total cost = {solver.Objective().Value()}\\n')\n",
    "        for i in range(num_workers):\n",
    "            for j in range(num_tasks):\n",
    "                if x[i, j].solution_value() > 0.5:\n",
    "                    print(f'Worker {i} assigned to task {j}.' +\n",
    "                          f' Cost: {costs[i][j]}')\n",
    "    else:\n",
    "        print('No solution found.')\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    main()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5ca13db6",
   "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.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}