Simplex_Method_With_Python.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "LdEQhcG2F_bH"
      },
      "source": [
        "#Input Step"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "background_save": true,
          "base_uri": "https://localhost:8080/"
        },
        "id": "_jc9wha0GDPf",
        "outputId": "98f596ed-abc0-4797-a08a-23d8857adec2"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "*****Linear Problem Optimization********\n",
            " ---Written by A.Ebrahimi---\n",
            "\n",
            " Variables= 2 \t \t Constraints= 3\n",
            "Please enter the coefficient x_ 1 In Zero Line\n",
            "Please enter the coefficient x_ 2 In Zero Line\n",
            "Specify the type of constraint 1\n",
            "Please enter the coefficient x_ 1 In constraint 1\n",
            "Please enter the coefficient x_ 2 In constraint 1\n",
            "Please Enter RHS in Constraint 1\n",
            "Specify the type of constraint 2\n",
            "Please enter the coefficient x_ 1 In constraint 2\n"
          ]
        }
      ],
      "source": [
        "import pandas as pd\n",
        "import numpy as np\n",
        "import math as math\n",
        "import sympy as sp\n",
        "\n",
        "MM=9999\n",
        "Colm=[]\n",
        "Row=[\"Z\"]\n",
        "print(\"*****Linear Problem Optimization********\\n ---Written by A.Ebrahimi---\")\n",
        "Mode=int(input(\"Please Choose Your Mode ..1_Max 2_Min\"))\n",
        "Urs=int(input(\"Do you have Urs Varialbe? 1-No 2-Yes\"))\n",
        "if Urs==2:\n",
        "  print(\"!!!!!!!!!!!!!Please Enter the Urs variable manually!!!!!!!!!!\")\n",
        "Sol=int(input(\"Do you have (Equal) or (Greater than or Equal) Constraint in Your Problem ? 1.No 2.Yes\"))\n",
        "V=int(input(\"***Please Enter the Number of Variables ***\\n\"))\n",
        "C=int(input(\"***Please Enter the Number of Constraints ***\\n\"))\n",
        "\n",
        "print(\"\\n Variables=\",V,\"\\t \\t Constraints=\",C)\n",
        "con=[]\n",
        "Added=[]\n",
        "ZZ=[]\n",
        "#Problem Printing\n",
        "Zeroline=[\"Z =\"]\n",
        "Printcc=[]\n",
        "counter1=1\n",
        "for i in range(0,C+1):\n",
        "  if i==0:\n",
        "    for k in range(1,V+1):\n",
        "      print(\"Please enter the coefficient x_\",k,\"In Zero Line\")\n",
        "      Z=float(input())\n",
        "      ZZ.append(Z)\n",
        "      Colm=Colm+[\"x_\"+str(counter1)]\n",
        "      if Z>0:\n",
        "        Zeroline.append(\"+\"+str(Z)+\" \"+\"x\"+str(counter1))\n",
        "      elif Z<0:\n",
        "        Zeroline.append(str(Z)+\" \"+\"x\"+str(counter1))\n",
        "      counter1=counter1+1\n",
        "    ZZ.append(0)\n",
        "    Added.append(ZZ)\n",
        "  else:\n",
        "    if Sol==2:\n",
        "      print(\"Specify the type of constraint\",i)\n",
        "      Type=int(input(\"1_(Less than or equal) <= \\n2_(equal)= \\n3_(Greater than or equal)>= \\n\"))\n",
        "      con.append(Type) #con is for type of constraint\n",
        "    else:\n",
        "      Type=1\n",
        "      con.append(Type)\n",
        "    Addx=[]\n",
        "    Printc=[]\n",
        "    for j in range(0,V+1):\n",
        "      if j==V:\n",
        "        print(\"Please Enter RHS in Constraint\",i)\n",
        "        Xin=float(input())\n",
        "        Addx.append(Xin)\n",
        "        if Type==1:\n",
        "          Printc.append(\"<=\"+str(Xin))\n",
        "        elif Type==2:\n",
        "          Printc.append(\"=\"+str(Xin))\n",
        "        elif Type==3:\n",
        "          Printc.append(\">=\"+str(Xin))\n",
        "      else:\n",
        "        print(\"Please enter the coefficient x_\",j+1,\"In constraint\",i)\n",
        "        Xin=float(input())\n",
        "        Addx.append(Xin)\n",
        "        if Xin<0:\n",
        "          Printc.append(str(Xin)+\" \"+\"x\"+str(j+1))\n",
        "        elif Xin>0:\n",
        "          Printc.append(\"+\"+str(Xin)+\" \"+\"x\"+str(j+1))\n",
        "    Added.append(Addx)\n",
        "    Printcc=Printcc+[Printc]\n",
        "RHS=[]\n",
        "for i in range(0,len(Added)):\n",
        "  RHS.append(Added[i][-1])\n",
        "  Added[i].pop(-1)\n",
        "counter2=1\n",
        "counter3=1\n",
        "for i in range(1,len(con)+1):\n",
        "  if con[i-1]==1: #Less than or equal Constraint\n",
        "    Row=Row+[\"S_\"+str(counter2)]\n",
        "    Colm=Colm+[\"s_\"+str(counter2)]\n",
        "    counter2=counter2+1\n",
        "    for j in range(0,len(Added)):\n",
        "      if j != i:\n",
        "        Added[j].append(0)\n",
        "      else:\n",
        "        Added[j].append(1)\n",
        "\n",
        "  elif con[i-1]==2: #Equal Constraint\n",
        "    Colm=Colm+[\"R_\"+str(counter3)]\n",
        "    Row=Row+[\"R_\"+str(counter3)]\n",
        "    counter3=counter3+1    \n",
        "    for jj in range(0,len(Added)):\n",
        "      if jj == 0:\n",
        "        if Mode==1: #maximize\n",
        "          Added[jj].append(-MM)\n",
        "        elif Mode==2:#minimize\n",
        "          Added[jj].append(MM)\n",
        "      elif jj==i:\n",
        "        Added[jj].append(1)\n",
        "      elif (jj !=0 and jj !=i):\n",
        "        Added[jj].append(0)\n",
        "  elif con[i-1]==3: #Greater than or equal Constraint\n",
        "    Colm=Colm+[\"s_\"+str(counter2)]\n",
        "    Colm=Colm+[\"R_\"+str(counter3)]\n",
        "    Row=Row+[\"R_\"+str(counter3)]\n",
        "    counter2=counter2+1\n",
        "    counter3=counter3+1\n",
        "    for jjj in range(0,len(Added)):\n",
        "      if jjj==0:\n",
        "        if Mode==1:\n",
        "          Added[jjj].append(0)\n",
        "          Added[jjj].append(-MM)\n",
        "        elif Mode==2:\n",
        "          Added[jjj].append(0)\n",
        "          Added[jjj].append(MM)\n",
        "      elif jjj==i:\n",
        "        Added[jjj].append(-1)\n",
        "        Added[jjj].append(1)\n",
        "      elif (jjj != 0 and jjj != i):\n",
        "        Added[jjj].append(0)\n",
        "        Added[jjj].append(0)\n",
        "for i in range(len(RHS)):\n",
        "  Added[i].append(RHS[i])\n",
        "Added=np.array(Added)\n",
        "\n",
        "if Mode==1: #maximize\n",
        "  Added[0]=-1*(Added[0])\n",
        "Added=np.array(Added).tolist()\n",
        "A=Added\n",
        "   \n",
        "\n",
        "        \n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "1uaVmsxrfD_2"
      },
      "source": [
        "#Simplex Method( Just Less than or equal Constraint )\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "9NYs-CLZfKOw"
      },
      "outputs": [],
      "source": [
        "if Sol==1:\n",
        "  print(\"*-*-*-*-*-*-*-*(Problem)*-*-*-*-*-*-*\")\n",
        "  print(*Zeroline, sep=' ')\n",
        "  print(\"Subject to:\")\n",
        "  for i in range(0,len(Printcc)):\n",
        "    print(*Printcc[i], sep=' ')  \n",
        "  print(\"*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\")\n",
        "  A=np.array(A,dtype=float)\n",
        "\n",
        "  print(\"------------------(Table: 1 )----------------\")\n",
        "  print(pd.DataFrame(A, index=Row,columns=Colm+[\"RHS\"]))\n",
        "  xz=2 #(xz=Counter for Table Number)\n",
        "  #___________________________________________________________________#\n",
        "  MA=0 #MA:Multi Answer Sign\n",
        "  while min(A[0,:-1])<0 or MA==1:\n",
        "    if MA != 1:\n",
        "      k=np.argmin(A[0,:-1])\n",
        "    test=[]\n",
        "    for i in range (1,A.shape[0]):\n",
        "      if (A[i,k]<0) or (A[i,k]==0):\n",
        "        test.append(math.inf)\n",
        "        continue\n",
        "      else:\n",
        "        test.append(A[i,-1]/A[i,k])\n",
        "    test=np.array(test)\n",
        "#Degeneracy and Unbonded Testing Step\n",
        "    s=0\n",
        "    for i in test:\n",
        "      if i == min(test[0:]):\n",
        "        s=s+1\n",
        "    if s>1 and min(test)!= math.inf:\n",
        "      print(\"***************(We have degeneracy in This Table)*********************\")\n",
        "    elif min(test)==math.inf:\n",
        "      print(\"***************(We are unbonded in This Table)************************\")\n",
        "      break\n",
        "    n=np.argmin(test[0:])+1\n",
        "    PashneRow  = np.divide(A[n], A[n][k])\n",
        "    A=np.array(A).tolist()\n",
        "    print(\"***************************\")\n",
        "    print(Colm[k],\"In \\t\",Row[n],\"Out\")\n",
        "    print(\"***************************\")\n",
        "    Row[n]=Colm[k]     #Replace column instead of row for Print\n",
        "    for j in range(len(A)):\n",
        "      Newrow=[] \n",
        "      if j==n:\n",
        "        A[n]  = np.divide(A[n], A[n][k])\n",
        "        continue\n",
        "      else:\n",
        "        Newrow=PashneRow\n",
        "        Newrow=Newrow*(-1)\n",
        "        Newrow=Newrow*A[j][k]\n",
        "        Newrow=list(Newrow)\n",
        "        added=np.add(Newrow,A[j])\n",
        "        A[j]=list(added)\n",
        "\n",
        "    A=np.array(A,dtype=float)\n",
        "\n",
        "    print(\"--------------- (Table:\",xz,\")------------------\")\n",
        "    print(pd.DataFrame(A, index=Row,columns=Colm+[\"RHS\"]))\n",
        "    xz=xz+1\n",
        "    MA=0\n",
        "    if Urs !=2:\n",
        "      for i in range(0,V):\n",
        "        if A[0][i]==0 and Colm[i] not in Row:\n",
        "          k=i\n",
        "          MA=1\n",
        "          print(\"*****We have multiple answers!!!!*****\")\n",
        "  Righth=round(A[0][-1],3)\n",
        "  if Mode==1 and (min(test)!=math.inf):\n",
        "    print(\"^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\")\n",
        "    print(\"Your Optimal Z value is =\",Righth)\n",
        "    print(\"^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\")\n",
        "  elif Mode==2 and (min(test)==math.inf):\n",
        "    print(\"^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\")\n",
        "    print(\"Your Optimal Z value is =\",-1*Righth)\n",
        "    print(\"^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\")\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "hWzNubXk8ZJe"
      },
      "source": [
        "#Big M method"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "XyWvbifR8afn"
      },
      "outputs": [],
      "source": [
        "if Sol==2:\n",
        "  print(\"*-*-*-*-*-*-*-*(Problem)*-*-*-*-*-*-*\")\n",
        "  print(*Zeroline, sep=' ')\n",
        "  print(\"Subject to:\")\n",
        "  for i in range(0,len(Printcc)):\n",
        "    print(*Printcc[i], sep=' ')  \n",
        "  print(\"*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*\")\n",
        "  pd.set_option('display.max_columns', None)\n",
        "  pd.set_option('display.max_rows', None)\n",
        "  MM=9999\n",
        "  Mdisplay=sp.symbols(\"M\")\n",
        "\n",
        "  A=np.array(A,dtype=float)\n",
        "  Zero=[]\n",
        "  for i in range(len(A[0])):\n",
        "    if (A[0][i] != MM):\n",
        "      Zero.append(A[0][i])\n",
        "    else:\n",
        "      Zero.append(Mdisplay)\n",
        "  B=np.delete(A,0,axis=0)\n",
        "  B=np.array(B).tolist()\n",
        "  AA=[]\n",
        "  AA.append(Zero)\n",
        "  for i in range(len(B)):\n",
        "    AA.append(B[i])\n",
        "  # A(For calculations) & AA(For Display)\n",
        "\n",
        "  print(\"------------------(Table: 1 )----------------\")\n",
        "  print(pd.DataFrame(AA, index=Row,columns=Colm+[\"RHS\"]))\n",
        "\n",
        "  Mcolm=[]\n",
        "  Mrow=[]\n",
        "  for i in range(len(A[0])):\n",
        "    if (A[0][i]==MM):\n",
        "      Mcolm.append(i)\n",
        "  for i in range(1,len(A)):\n",
        "    for j in Mcolm:\n",
        "      if A[i][j]==1:\n",
        "        Mrow.append(i)\n",
        "  Mrow=np.array(Mrow)\n",
        "#...q means for Display Like: rowq(For Display) row(For Calculations)\n",
        "#Prepare the First Table\n",
        "  row=[]\n",
        "  rowq=[]\n",
        "  for i in Mrow:\n",
        "    row=-MM*(A[i])\n",
        "    rowq = [element*-Mdisplay for element in AA[i]]\n",
        "    A[0]=np.add(row,A[0])\n",
        "    AA[0]=np.add(rowq,AA[0])\n",
        "    row=[]\n",
        "  print(\"------------------(Table: 2 )----------------\")\n",
        "  print(pd.DataFrame(AA, index=Row,columns=Colm+[\"RHS\"]))\n",
        "  xz=3 #(xz=Counter for Table Number)\n",
        "#___________________________________________________________________#\n",
        "  MA=0\n",
        "  while min(A[0,:-1])<0 or MA==1:\n",
        "    if MA !=1:\n",
        "      k=np.argmin(A[0,:-1])\n",
        "    test=[]\n",
        "    for i in range (1,A.shape[0]):\n",
        "      if (A[i,k]<0) or (A[i,k]==0):\n",
        "        test.append(math.inf)\n",
        "        continue\n",
        "      else:\n",
        "        test.append(A[i,-1]/A[i,k])\n",
        "    test=np.array(test)\n",
        "#Degeneracy and Unbonded Testing Step\n",
        "    s=0\n",
        "    for i in test:\n",
        "      if i == min(test[0:]):\n",
        "        s=s+1\n",
        "    if s>1 and min(test)!= math.inf:\n",
        "      print(\"***************(We have degeneracy in This Table)*********************\")\n",
        "    elif min(test)==math.inf:\n",
        "      print(\"***************(We are unbonded in This Table)************************\")\n",
        "      break\n",
        "    n=int(np.argmin(test[0:]))+1\n",
        "    PashneRow  = np.divide(A[n], A[n][k])\n",
        "    PashneRowq = np.divide(AA[n], AA[n][k])\n",
        "    A=np.array(A).tolist()\n",
        "    AA=np.array(AA).tolist()\n",
        "    print(\"***************************\")\n",
        "    print(Colm[k],\"In \\t\",Row[n],\"Out\")\n",
        "    print(\"***************************\")\n",
        "    Row[n]=Colm[k]     #Replace column instead of row for Print\n",
        "    for j in range(len(A)):\n",
        "      Newrow=[] \n",
        "      if j==n:\n",
        "        A[n]  = np.divide(A[n], A[n][k])\n",
        "        AA[n]=np.divide(AA[n], AA[n][k],dtype=float)\n",
        "        continue\n",
        "      else:\n",
        "        Newrow=PashneRow\n",
        "        Newrowq=PashneRowq\n",
        "        Newrow=Newrow*(-1)\n",
        "        Newrowq=Newrowq*(-1)\n",
        "        Newrow=Newrow*A[j][k]\n",
        "        Newrowq=Newrowq*AA[j][k]\n",
        "        Newrow=list(Newrow)\n",
        "        Newrowq=list(Newrowq)\n",
        "        added=np.add(Newrow,A[j])\n",
        "        addedq=np.add(Newrowq,AA[j])\n",
        "        A[j]=list(added)\n",
        "        AA[j]=list(addedq)\n",
        "    A=np.array(A,dtype=float)\n",
        "    limiti=0\n",
        "    for i in range(0,len(A[0])):\n",
        "      limiti=sp.limit(AA[0][i],Mdisplay,0)\n",
        "      if math.isclose(limiti,A[0][i]):\n",
        "        AA[0][i]=A[0][i]\n",
        " \n",
        "    print(\"--------------- (Table:\",xz,\")------------------\")\n",
        "    print(pd.DataFrame(AA, index=Row,columns=Colm+[\"RHS\"]))\n",
        "    xz=xz+1\n",
        "#Multi Answer Checking Step\n",
        "    MA=0\n",
        "    if Urs !=2:\n",
        "      for i in range(0,V):\n",
        "        if A[0][i]==0 and Colm[i] not in Row:\n",
        "          k=i\n",
        "          MA=1\n",
        "          print(\"*****We have multiple answers!!!!*****\")\n",
        "  Righth=round(A[0][-1],3)\n",
        "  if Mode==1 and min(test)!=math.inf:\n",
        "    print(\"^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\")\n",
        "    print(\"Your Optimal Z value is =\",Righth)\n",
        "    print(\"^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\")\n",
        "  elif Mode==2 and min(test)!=math.inf:\n",
        "    print(\"^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\")\n",
        "    print(\"Your Optimal Z value is =\",-1*Righth)\n",
        "    print(\"^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\")\n",
        "\n",
        "#Infeasible Test::\n",
        "  Row=str(Row)\n",
        "  if (Row.find(\"R_\") != -1):\n",
        "    print(\"---------------------Infeasible Answer----------------------\")\n"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}