other/Simplex_standard.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is a notebook to solve linear programming problem using the simmplex method. The inputs are supplied in the form of standard LPP that is the objective shooulf be of maximization type and all the constraints should be of <= type.\n",
    "Example being:\n",
    "\n",
    "maximize z: 3*x1 + 4*x2\n",
    "\n",
    "      s.t.: 5*x1+ 4*x2<=15\n",
    "      ...\n",
    "      \n",
    "Here a sample problem is solved:\n",
    "Maximize\tP\t=\t20x1\t+\t10x2\t+\t15x3\t\n",
    "\n",
    "\n",
    "Subject to: \n",
    "\n",
    "3x1\t+\t2x2\t+\t5x3\t≤\t55\n",
    "\n",
    "2x1\t+\tx2\t+\tx3\t≤\t26\n",
    "\n",
    "x1\t+\tx2\t+\t3x3\t≤\t30\n",
    "\n",
    "5x1\t+\t2x2\t+\t4x3\t≤\t57\n",
    "\n",
    "x1\t,\tx2\t,\tx3\t≥\t0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Enter data for the simplex:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "num_vars = None # 3 here\n",
    "cost_vector = None #[20 10 15]\n",
    "num_consts = None # 4\n",
    "A = None #[[3 2 5],[2 1 1], [1 1 3],[5 2 4]]\n",
    "b = None #[55 26 30 57]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Enter the Linear programming data in standard form: \n",
      "Number of variables: 3\n",
      "Coefficients of the decision variables in cost function: 20 10 15\n",
      "Number of constraints: 4\n",
      "Inequality constraints data: \n",
      "Enter the matrix of coefficients: \n",
      "Constraint: 1\n",
      "Coefficients: 3 2 5\n",
      "Constraint: 2\n",
      "Coefficients: 2 1 1\n",
      "Constraint: 3\n",
      "Coefficients: 1 1 3\n",
      "Constraint: 4\n",
      "Coefficients: 5 2 4\n",
      "Enter the RHS: 55 26 30 57\n"
     ]
    }
   ],
   "source": [
    "print(\"Enter the Linear programming data in standard form: \")\n",
    "num_vars = int(input('Number of variables: '))\n",
    "\n",
    "cost_vector = input('Coefficients of the decision variables in cost function: ')\n",
    "cost_vector = cost_vector.split(' ')\n",
    "cost_vector = [int(i) for i in cost_vector]\n",
    "cost_vector = np.array(cost_vector)\n",
    "\n",
    "num_consts = int(input('Number of constraints: '))\n",
    "print(\"Inequality constraints data: \")\n",
    "\n",
    "print('Enter the matrix of coefficients: ')\n",
    "\n",
    "A = np.zeros((num_consts,num_vars))\n",
    "\n",
    "for i in range(num_consts):\n",
    "    print(\"Constraint: \"+str(i+1))\n",
    "    x = input(\"Coefficients: \")\n",
    "    x = x.split(' ')\n",
    "    x = [float(k) for k in x]\n",
    "    for j in range(num_vars):\n",
    "        A[i][j] = x[j]\n",
    "\n",
    "\n",
    "b = input(\"Enter the RHS: \")\n",
    "b = b.split(' ')\n",
    "b = [float(k) for k in b]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "A_ = A.copy()\n",
    "b_ = b.copy()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Enter again from here on the same data:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = A_.copy()\n",
    "b = b_.copy()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "num_le = num_consts\n",
    "num_eq = 0\n",
    "num_ge = 0\n",
    "\n",
    "\n",
    "\n",
    "v_slack = []\n",
    "A_slacks = np.zeros((num_consts,num_consts))\n",
    "v_artificial = []\n",
    "A_surplus = np.zeros((num_consts,num_ge))\n",
    "v_bounds = []\n",
    "\n",
    "\n",
    "\n",
    "for i in  range(num_consts):\n",
    "    s = '<='\n",
    "\n",
    "    if s=='<=':\n",
    "        v_slack.append(b[i])\n",
    "        A_slacks[i][len(v_slack)-1] = 1\n",
    "    elif s=='>=':\n",
    "        v_slack.append(0)\n",
    "        A_slacks[i][len(v_slack)-1] = -1\n",
    "        v_artificial.append(b[i])\n",
    "        A_surplus[i][len(v_artificial)-1] = 1\n",
    "    else:\n",
    "        v_artificial.append(b[i])\n",
    "        A_surplus[i][len(v_artificial)-1] = 1\n",
    "    \n",
    "    v_bounds.append(b[i])\n",
    "\n",
    "\n",
    "A = np.hstack([A,A_slacks,A_surplus])\n",
    "\n",
    "vari = []\n",
    "vari_ar = []\n",
    "vari_slack = []\n",
    "vari_nb = []\n",
    "\n",
    "variables = []\n",
    "for i in  range(len(A[0])):\n",
    "    variables.append('x'+str(i+1))\n",
    "    vari.append('x'+str(i+1))\n",
    "    if i < num_vars:\n",
    "        vari_nb.append('x'+str(i+1))\n",
    "    elif i< num_vars + len(v_slack):\n",
    "        vari_slack.append('x'+str(i+1))\n",
    "    else:\n",
    "        vari_ar.append('x'+str(i+1))\n",
    "\n",
    "all_vars = {}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "v_a = 0*cost_vector\n",
    "v_ar = None\n",
    "\n",
    "x = np.hstack([v_a,v_slack,v_artificial])\n",
    "\n",
    "for v,val in zip(variables,x):\n",
    "    all_vars[v] = val\n",
    "\n",
    "\n",
    "if len(v_artificial)==0:\n",
    "    v_ar = []\n",
    "else:\n",
    "    if type_problem == 1:\n",
    "        v_ar = -9999*np.ones(len(v_artificial))\n",
    "    else:\n",
    "        v_ar = 9999*np.ones(len(v_artificial))\n",
    "\n",
    "Cj = np.hstack([cost_vector,0*np.array(v_slack),v_ar])\n",
    "Ci = []\n",
    "tab1 = []\n",
    "Vb = []\n",
    "Q = v_bounds\n",
    "\n",
    "struct2_curr_values = np.zeros(len(Q))\n",
    "struct2_var_base = ['' for _ in range(len(Q))]\n",
    "\n",
    "for i in range(len(Q)):\n",
    "    tab1.append('|')\n",
    "    struct2_curr_values = Q[i]\n",
    "    ind = np.where(x==Q[i])\n",
    "    ind = ind[0]\n",
    "    ind = ind[0]\n",
    "\n",
    "    struct2_var_base[i] = variables[ind]\n",
    "    Vb.append(struct2_var_base[i])\n",
    "    Ci.append(Cj[ind])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "Ci = np.array(Ci)\n",
    "\n",
    "Z = sum(np.multiply(Ci,Q))\n",
    "Zj = np.zeros(len(Cj))\n",
    "\n",
    "for i in range(len(Cj)):\n",
    "    Zj[i] = sum(np.multiply(Ci,A[:,i])) \n",
    "vars_at_moment = struct2_var_base.copy()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_row(vec):\n",
    "    k = ''\n",
    "    for i in vec:\n",
    "        k+= '{0:>10}'.format(round(i,3))\n",
    "    return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "=========LP in standard form:=========\n",
      "variables:  ['x1', 'x2', 'x3', 'x4', 'x5', 'x6', 'x7']\n",
      "Activity variables:  ['x1', 'x2', 'x3']\n",
      "Slack variables:  ['x4', 'x5', 'x6', 'x7']\n",
      "Artificial variables:  []\n",
      "======Iteration: 0======\n",
      "Initializing variables:  ['x1', 'x2', 'x3', 'x4', 'x5', 'x6', 'x7']\n",
      "Activity variables:  [0.0, 0.0, 0.0]\n",
      "Slack variables:  ['x4', 'x5', 'x6', 'x7'] [55.0, 26.0, 30.0, 57.0]\n",
      "Artificial variables:  []\n",
      "=======================================================================================================\n",
      "Variables:                                        1         2         3         4         5         6         7\n",
      "Cj:                                            20.0      10.0      15.0       0.0       0.0       0.0       0.0\n",
      "Basic        |Value       |RHS\n",
      "|         x4 |        0.0 |       55.0 |        3.0       2.0       5.0       1.0       0.0       0.0       0.0 |\n",
      "|         x5 |        0.0 |       26.0 |        2.0       1.0       1.0       0.0       1.0       0.0       0.0 |\n",
      "|         x6 |        0.0 |       30.0 |        1.0       1.0       3.0       0.0       0.0       1.0       0.0 |\n",
      "|         x7 |        0.0 |       57.0 |        5.0       2.0       4.0       0.0       0.0       0.0       1.0 |\n",
      "=======================================================================================================\n",
      "Zj:                                             0.0       0.0       0.0       0.0       0.0       0.0       0.0\n",
      "Cj-Zj:                                         20.0      10.0      15.0       0.0       0.0       0.0       0.0\n",
      "Z:  0.0\n"
     ]
    }
   ],
   "source": [
    "print(\"=========LP in standard form:=========\")\n",
    "\n",
    "print(\"variables: \",vari)\n",
    "print(\"Activity variables: \",vari_nb)\n",
    "print(\"Slack variables: \",vari_slack)\n",
    "print(\"Artificial variables: \",vari_ar)\n",
    "\n",
    "print(\"======Iteration: 0======\")\n",
    "print(\"Initializing variables: \",vari)\n",
    "print(\"Activity variables: \",[all_vars[v] for v in vari_nb])\n",
    "print(\"Slack variables: \",vari_slack,[all_vars[v] for v in vari_slack])\n",
    "print(\"Artificial variables: \",v_ar)\n",
    "print('=======================================================================================================')\n",
    "print(\"Variables:                              \",get_row(np.arange(start=1,stop=len(A[0,:])+1,step = 1 )))\n",
    "print(\"Cj:                                     \",get_row(Cj))\n",
    "print(\"Basic        |Value       |RHS\")\n",
    "for i in range(num_consts):\n",
    "    print('|',\"{0:>10}\".format(vars_at_moment[i]),'|',\"{0:>10}\".format(Ci[i]),'|',\"{0:>10}\".format(round(Q[i],3)),'|',get_row(A[i]),'|')\n",
    "\n",
    "print('=======================================================================================================')\n",
    "print('Zj:                                     ',get_row(Zj))\n",
    "print('Cj-Zj:                                  ',get_row(Cj-Zj))\n",
    "print('Z: ',round(Z,3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "iterNum = 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "=====Iteration 2 =======\n",
      "Enter:  x1\n",
      "Leave:  x7\n",
      "Pivot:  5.0\n",
      "========\n",
      "=======================================================================================================\n",
      "Variables:                                        1         2         3         4         5         6         7\n",
      "Cj:                                            20.0      10.0      15.0       0.0       0.0       0.0       0.0\n",
      "Basic        |Value       |RHS\n",
      "|         x4 |        0.0 |       20.8 |        0.0       0.8       2.6       1.0       0.0       0.0      -0.6 |\n",
      "|         x5 |        0.0 |        3.2 |        0.0       0.2      -0.6       0.0       1.0       0.0      -0.4 |\n",
      "|         x6 |        0.0 |       18.6 |        0.0       0.6       2.2       0.0       0.0       1.0      -0.2 |\n",
      "|         x1 |       20.0 |       11.4 |        1.0       0.4       0.8       0.0       0.0       0.0       0.2 |\n",
      "=======================================================================================================\n",
      "Zj:                                            20.0       8.0      16.0       0.0       0.0       0.0       4.0\n",
      "Cj-Zj:                                          0.0       2.0      -1.0       0.0       0.0       0.0      -4.0\n",
      "Z:  228.0\n",
      "=====Iteration 3 =======\n",
      "Enter:  x2\n",
      "Leave:  x5\n",
      "Pivot:  0.2\n",
      "========\n",
      "=======================================================================================================\n",
      "Variables:                                        1         2         3         4         5         6         7\n",
      "Cj:                                            20.0      10.0      15.0       0.0       0.0       0.0       0.0\n",
      "Basic        |Value       |RHS\n",
      "|         x4 |        0.0 |        8.0 |        0.0       0.0       5.0       1.0      -4.0       0.0       1.0 |\n",
      "|         x2 |       10.0 |       16.0 |        0.0       1.0      -3.0       0.0       5.0       0.0      -2.0 |\n",
      "|         x6 |        0.0 |        9.0 |        0.0       0.0       4.0       0.0      -3.0       1.0       1.0 |\n",
      "|         x1 |       20.0 |        5.0 |        1.0       0.0       2.0       0.0      -2.0       0.0       1.0 |\n",
      "=======================================================================================================\n",
      "Zj:                                            20.0      10.0      10.0       0.0      10.0       0.0       0.0\n",
      "Cj-Zj:                                          0.0       0.0       5.0       0.0     -10.0       0.0       0.0\n",
      "Z:  260.0\n",
      "=====Iteration 4 =======\n",
      "Enter:  x3\n",
      "Leave:  x4\n",
      "Pivot:  5.0\n",
      "========\n",
      "=======================================================================================================\n",
      "Variables:                                        1         2         3         4         5         6         7\n",
      "Cj:                                            20.0      10.0      15.0       0.0       0.0       0.0       0.0\n",
      "Basic        |Value       |RHS\n",
      "|         x3 |       15.0 |        1.6 |        0.0       0.0       1.0       0.2      -0.8       0.0       0.2 |\n",
      "|         x2 |       10.0 |       20.8 |        0.0       1.0       0.0       0.6       2.6       0.0      -1.4 |\n",
      "|         x6 |        0.0 |        2.6 |        0.0       0.0       0.0      -0.8       0.2       1.0       0.2 |\n",
      "|         x1 |       20.0 |        1.8 |        1.0       0.0       0.0      -0.4      -0.4       0.0       0.6 |\n",
      "=======================================================================================================\n",
      "Zj:                                            20.0      10.0      15.0       1.0       6.0       0.0       1.0\n",
      "Cj-Zj:                                          0.0       0.0       0.0      -1.0      -6.0       0.0      -1.0\n",
      "Z:  268.0\n"
     ]
    }
   ],
   "source": [
    "\n",
    "while iterNum<=10:\n",
    "    iterNum+=1\n",
    "    type_problem = 1\n",
    "    if type_problem == 1:\n",
    "        num = max(Cj-Zj)\n",
    "        index = np.where((Cj-Zj)==num)\n",
    "        index = index[0][0]\n",
    "        v_enter = variables[index]\n",
    "    else:\n",
    "        num = min(Cj-Zj)\n",
    "        index = np.where((Cj-Zj)==num)\n",
    "        index = index[0][0]\n",
    "        v_enter = variables[index]\n",
    "    \n",
    "    b = A[:,index]\n",
    "    k = -1\n",
    "    d = 10000\n",
    "    \n",
    "    for i in range(len(Q)):\n",
    "        if b[i]>0:\n",
    "            div = Q[i]/b[i]\n",
    "            if d>=div:\n",
    "                d = div\n",
    "                k = i\n",
    "    if k == -1:\n",
    "        print('Solution is infinty ')\n",
    "        break\n",
    "    else:\n",
    "        num2 = k\n",
    "    \n",
    "    v_leave = struct2_var_base[num2]\n",
    "    struct2_var_base[num2] = v_enter\n",
    "    pivot = A[num2,index]\n",
    "    Ci[num2] = Cj[index]\n",
    "    A[num2,:] = A[num2,:]/pivot\n",
    "    Q[num2] = Q[num2]/pivot\n",
    "    \n",
    "    #Row operations:\n",
    "    \n",
    "    for i in range(num_consts):\n",
    "        \n",
    "        if i!= num2:\n",
    "            Q[i] = Q[i] - A[i,index]*Q[num2]\n",
    "            A[i,:] = A[i,:] - A[i,index]*A[num2,:]\n",
    "    Z = sum(np.multiply(Ci,Q))\n",
    "    for i in  range(len(A[0,:])):\n",
    "        Zj[i] = sum(np.multiply(A[:,i],Ci))\n",
    "    \n",
    "    vars_at_moment = []\n",
    "    for i in range(num_consts):\n",
    "        vars_at_moment.append(struct2_var_base[i])\n",
    "    \n",
    "    print('=====Iteration',iterNum,'=======')\n",
    "    print('Enter: ',v_enter)\n",
    "    print('Leave: ',v_leave)\n",
    "    print('Pivot: ',round(pivot,3))\n",
    "    \n",
    "    print('========')\n",
    "\n",
    "    print('=======================================================================================================')\n",
    "    print(\"Variables:                              \",get_row(np.arange(start=1,stop=len(A[0,:])+1,step = 1 )))\n",
    "    print(\"Cj:                                     \",get_row(Cj))\n",
    "    print(\"Basic        |Value       |RHS\")\n",
    "    for i in range(num_consts):\n",
    "        print('|',\"{0:>10}\".format(vars_at_moment[i]),'|',\"{0:>10}\".format(Ci[i]),'|',\"{0:>10}\".format(round(Q[i],3)),'|',get_row(A[i]),'|')\n",
    "\n",
    "    print('=======================================================================================================')\n",
    "    print('Zj:                                     ',get_row(Zj))\n",
    "    print('Cj-Zj:                                  ',get_row(Cj-Zj))\n",
    "    print('Z: ',round(Z,3))\n",
    "    if type_problem ==1:\n",
    "        temp = max(Cj-Zj)\n",
    "        if temp<=0:\n",
    "            break\n",
    "    else:\n",
    "        temp = min(Cj-Zj)\n",
    "        if temp>=0:\n",
    "            break\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}