Simplex Standard
G
{
"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
}
