simplex.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "def simplex(of,basis,tableau,opt):\n",
    "    # Get the number of rows and columns in the tableau:\n",
    "    n_rows = tableau.shape[0]\n",
    "    n_cols = tableau.shape[1]\n",
    "    if opt =='MIN':\n",
    "        # Start the simplex algorithm:\n",
    "        # Compute zj-cj. If cj - zj >= 0 for all columns then current \n",
    "        # solution is optimal solution.\n",
    "        check = of - np.sum(np.reshape(of[list(basis)],(n_rows,1)) * tableau[:,0:n_cols-1],axis=0)\n",
    "    else:\n",
    "        # Start the simplex algorithm:\n",
    "        # Compute cj-zj. If zj - cj >= 0 for all columns then current\n",
    "        # solution is optimal solution.\n",
    "        check = np.sum(np.reshape(of[list(basis)],(n_rows,1)) *tableau[:,0:n_cols-1],axis=0) - of\n",
    "    count = 0\n",
    "    while ~np.all(check >=0):\n",
    "        print(check)\n",
    "        # Determine the pivot column:\n",
    "        # The pivot column is the column corresponding to \n",
    "        # minimum zj-cj.\n",
    "        pivot_col = np.argmin(check)\n",
    "        # Determine the positive elements in the pivot column.\n",
    "        # If there are no positive elements in the pivot column  \n",
    "        # then the optimal solution is unbounded.\n",
    "        positive_rows = np.where(tableau[:,pivot_col] > 0)[0]\n",
    "        if positive_rows.size == 0:\n",
    "            print('Unbounded Solution!')\n",
    "            break\n",
    "        # Determine the pivot row:\n",
    "        #min-ration test\n",
    "        divide=(tableau[positive_rows,n_cols-1]\n",
    "            /tableau[positive_rows,pivot_col])\n",
    "        pivot_row = positive_rows[np.where(divide \n",
    "            == divide.min())[0][-1]]\n",
    "        # Update the basis:\n",
    "        basis[pivot_row] = pivot_col\n",
    "        # Perform gaussian elimination to make pivot element one and\n",
    "        # elements above and below it zero:\n",
    "        tableau[pivot_row,:]=(tableau[pivot_row,:]\n",
    "            /tableau[pivot_row,pivot_col])\n",
    "        for row in range(n_rows):\n",
    "            if row != pivot_row:\n",
    "                tableau[row,:] = (tableau[row,:] \n",
    "                    - tableau[row,pivot_col]*tableau[pivot_row,:])\n",
    "        if opt =='MIN':\n",
    "            check = of - np.sum(np.reshape(of[list(basis)],(n_rows,1)) * tableau[:,0:n_cols-1],axis=0)\n",
    "        else:\n",
    "            check = np.sum(np.reshape(of[list(basis)],(n_rows,1)) *tableau[:,0:n_cols-1],axis=0) - of\n",
    "        count += 1\n",
    "        print('Step %d' % count)\n",
    "        print(tableau)\n",
    "    return basis,tableau\n",
    "\n",
    "def get_solution(of,basis,tableau):\n",
    "    # Get the no of columns in the tableau:\n",
    "    n_cols = tableau.shape[1]\n",
    "    # Get the optimal solution:\n",
    "    solution = np.zeros(of.size)\n",
    "    solution[list(basis)] = tableau[:,n_cols-1]\n",
    "    # Determine the optimal value:\n",
    "    value = np.sum(of[list(basis)] * tableau[:,n_cols-1])\n",
    "    return solution,value"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solve the following L.P.P. by Simplex Method.\n",
    "\n",
    "Maximize $z=4x_1+5x_2+9x_3+11x_4$ subject to\n",
    "$$\n",
    "\\begin{aligned}\n",
    "x_1+x_2+x_3+x_4 &\\leq 15,  \\\\\n",
    "7x_1 + 5x_2+3x_3+2x_4 &\\leq 120, \\\\\n",
    "3x_1+5x_2+10x_3+15x_4 &\\leq 100, \\\\\n",
    "x_1,x_2,x_3,x_4 &\\geq 0\n",
    "\\end{aligned}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "We can convert the problem into the standard form by adding slack variables $x_5,x_6$ and $x_7$. \n",
    "\n",
    "Maximize $z = 4x_1+5x_2+9x_3+11x_4+0x_5+0x_6+0x_7$ subject to\n",
    "$$\\begin{aligned}\n",
    "x_1+x_2+x_3+x_4+x_5 &= 15, \\\\\n",
    "7x_1+5x_2+3x_3+2x_4 +x_6 &= 120, \\\\\n",
    "3x_1+5x_2+10x_3+15x_4+x_7 &= 100, \\\\\n",
    "x_1,x_2,x_3,x_4,x_5,x_6,x_7 &\\geq 0\n",
    "\\end{aligned}$$\n",
    "\n",
    "We are now ready to solve the problem."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ -4.  -5.  -9. -11.   0.   0.   0.]\n",
      "Step 1\n",
      "[[ 8.00000000e-01  6.66666667e-01  3.33333333e-01  0.00000000e+00\n",
      "   1.00000000e+00  0.00000000e+00 -6.66666667e-02  8.33333333e+00]\n",
      " [ 6.60000000e+00  4.33333333e+00  1.66666667e+00  0.00000000e+00\n",
      "   0.00000000e+00  1.00000000e+00 -1.33333333e-01  1.06666667e+02]\n",
      " [ 2.00000000e-01  3.33333333e-01  6.66666667e-01  1.00000000e+00\n",
      "   0.00000000e+00  0.00000000e+00  6.66666667e-02  6.66666667e+00]]\n",
      "[-1.8        -1.33333333 -1.66666667  0.          0.          0.\n",
      "  0.73333333]\n",
      "Step 2\n",
      "[[ 1.          0.83333333  0.41666667  0.          1.25        0.\n",
      "  -0.08333333 10.41666667]\n",
      " [ 0.         -1.16666667 -1.08333333  0.         -8.25        1.\n",
      "   0.41666667 37.91666667]\n",
      " [ 0.          0.16666667  0.58333333  1.         -0.25        0.\n",
      "   0.08333333  4.58333333]]\n",
      "[ 0.          0.16666667 -0.91666667  0.          2.25        0.\n",
      "  0.58333333]\n",
      "Step 3\n",
      "[[ 1.          0.71428571  0.         -0.71428571  1.42857143  0.\n",
      "  -0.14285714  7.14285714]\n",
      " [ 0.         -0.85714286  0.          1.85714286 -8.71428571  1.\n",
      "   0.57142857 46.42857143]\n",
      " [ 0.          0.28571429  1.          1.71428571 -0.42857143  0.\n",
      "   0.14285714  7.85714286]]\n",
      "The final basis is:\n",
      "[0 5 2]\n",
      "solution\n",
      "X1 = 7.142857142857139\n",
      "X2 = 0.0\n",
      "X3 = 7.857142857142859\n",
      "X4 = 0.0\n",
      "X5 = 0.0\n",
      "X6 = 46.42857142857145\n",
      "X7 = 0.0\n",
      "Z= 99.28571428571429\n"
     ]
    }
   ],
   "source": [
    "def question1():\n",
    "    # Define the tableau:\n",
    "    tableau = np.array([\n",
    "        [1.0,1,1,1,1,0,0,15],\n",
    "        [7,5,3,2,0,1,0,120],\n",
    "        [3,5,10,15,0,0,1,100]\n",
    "    ])\n",
    "    # Define the objective function and the initial basis:\n",
    "    of = np.array([4,5,9,11,0,0,0])\n",
    "    #initial basis\n",
    "    basis = np.array([4,5,6])\n",
    "    # Run the simplex algorithm:\n",
    "    basis,tableau = simplex(of,basis,tableau,'MAX')\n",
    "    # Get the optimal soultion:\n",
    "    optimal_solution,optimal_value = get_solution(of,basis,tableau)\n",
    "    # Print the final tableau:\n",
    "    print('The final basis is:')\n",
    "    print(basis)\n",
    "    print('solution')\n",
    "    for i in range(len(optimal_solution)):\n",
    "        print('X%d'%(i+1),'=',optimal_solution[i])\n",
    "    print('Z=',optimal_value)\n",
    "question1()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 1. -3.  3.  0.  0.  0.]\n",
      "Step 1\n",
      "[[ 1.66666667  0.          4.66666667  1.          0.          0.33333333\n",
      "  10.33333333]\n",
      " [-6.33333333  0.         10.66666667  0.          1.          1.33333333\n",
      "  25.33333333]\n",
      " [-1.33333333  1.          2.66666667  0.          0.          0.33333333\n",
      "   3.33333333]]\n",
      "[-3.  0. 11.  0.  0.  1.]\n",
      "Step 2\n",
      "[[ 1.   0.   2.8  0.6  0.   0.2  6.2]\n",
      " [ 0.   0.  28.4  3.8  1.   2.6 64.6]\n",
      " [ 0.   1.   6.4  0.8  0.   0.6 11.6]]\n",
      "The final basis is:\n",
      "[0 4 1]\n",
      "solution\n",
      "X1 = 6.2\n",
      "X2 = 11.6\n",
      "X3 = 0.0\n",
      "X4 = 0.0\n",
      "X5 = 64.6\n",
      "X6 = 0.0\n",
      "Z= -28.599999999999998\n"
     ]
    }
   ],
   "source": [
    "def question2():\n",
    "    # Define the tableau:\n",
    "    tableau = np.array([\n",
    "        [3.0,-1,2,1,0,0,7],\n",
    "        [-1,-4,0,0,1,0,12],\n",
    "        [-4,3,8,0,0,1,10]\n",
    "    ])\n",
    "    # Define the objective function and the initial basis:\n",
    "    of = np.array([1,-3,3,0,0,0])\n",
    "    #initial basis\n",
    "    basis = np.array([3,4,5])\n",
    "    # Run the simplex algorithm:\n",
    "    basis,tableau = simplex(of,basis,tableau,'MIN')\n",
    "    # Get the optimal soultion:\n",
    "    optimal_solution,optimal_value = get_solution(of,basis,tableau)\n",
    "    # Print the final tableau:\n",
    "    print('The final basis is:')\n",
    "    print(basis)\n",
    "    print('solution')\n",
    "    for i in range(len(optimal_solution)):\n",
    "        print('X%d'%(i+1),'=',optimal_solution[i])\n",
    "    print('Z=',optimal_value)\n",
    "question2()"
   ]
  },
  {
   "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.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}