Simplex Standard
H
{
"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
}
À propos de cet Algorithme
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. Example being:
maximize z: 3x1 + 4x2
s.t.: 5*x1+ 4*x2<=15
...
Here a sample problem is solved: Maximize P = 20x1 + 10x2 + 15x3
Subject to:
3x1 + 2x2 + 5x3 ≤ 55
2x1 + x2 + x3 ≤ 26
x1 + x2 + 3x3 ≤ 30
5x1 + 2x2 + 4x3 ≤ 57
x1 , x2 , x3 ≥ 0
import numpy as npEnter data for the simplex:
num_vars = None # 3 here
cost_vector = None #[20 10 15]
num_consts = None # 4
A = None #[[3 2 5],[2 1 1], [1 1 3],[5 2 4]]
b = None #[55 26 30 57]print("Enter the Linear programming data in standard form: ")
num_vars = int(input('Number of variables: '))
cost_vector = input('Coefficients of the decision variables in cost function: ')
cost_vector = cost_vector.split(' ')
cost_vector = [int(i) for i in cost_vector]
cost_vector = np.array(cost_vector)
num_consts = int(input('Number of constraints: '))
print("Inequality constraints data: ")
print('Enter the matrix of coefficients: ')
A = np.zeros((num_consts,num_vars))
for i in range(num_consts):
print("Constraint: "+str(i+1))
x = input("Coefficients: ")
x = x.split(' ')
x = [float(k) for k in x]
for j in range(num_vars):
A[i][j] = x[j]
b = input("Enter the RHS: ")
b = b.split(' ')
b = [float(k) for k in b]Enter the Linear programming data in standard form:
Number of variables: 3
Coefficients of the decision variables in cost function: 20 10 15
Number of constraints: 4
Inequality constraints data:
Enter the matrix of coefficients:
Constraint: 1
Coefficients: 3 2 5
Constraint: 2
Coefficients: 2 1 1
Constraint: 3
Coefficients: 1 1 3
Constraint: 4
Coefficients: 5 2 4
Enter the RHS: 55 26 30 57
A_ = A.copy()
b_ = b.copy()Enter again from here on the same data:
A = A_.copy()
b = b_.copy()num_le = num_consts
num_eq = 0
num_ge = 0
v_slack = []
A_slacks = np.zeros((num_consts,num_consts))
v_artificial = []
A_surplus = np.zeros((num_consts,num_ge))
v_bounds = []
for i in range(num_consts):
s = '<='
if s=='<=':
v_slack.append(b[i])
A_slacks[i][len(v_slack)-1] = 1
elif s=='>=':
v_slack.append(0)
A_slacks[i][len(v_slack)-1] = -1
v_artificial.append(b[i])
A_surplus[i][len(v_artificial)-1] = 1
else:
v_artificial.append(b[i])
A_surplus[i][len(v_artificial)-1] = 1
v_bounds.append(b[i])
A = np.hstack([A,A_slacks,A_surplus])
vari = []
vari_ar = []
vari_slack = []
vari_nb = []
variables = []
for i in range(len(A[0])):
variables.append('x'+str(i+1))
vari.append('x'+str(i+1))
if i < num_vars:
vari_nb.append('x'+str(i+1))
elif i< num_vars + len(v_slack):
vari_slack.append('x'+str(i+1))
else:
vari_ar.append('x'+str(i+1))
all_vars = {}v_a = 0*cost_vector
v_ar = None
x = np.hstack([v_a,v_slack,v_artificial])
for v,val in zip(variables,x):
all_vars[v] = val
if len(v_artificial)==0:
v_ar = []
else:
if type_problem == 1:
v_ar = -9999*np.ones(len(v_artificial))
else:
v_ar = 9999*np.ones(len(v_artificial))
Cj = np.hstack([cost_vector,0*np.array(v_slack),v_ar])
Ci = []
tab1 = []
Vb = []
Q = v_bounds
struct2_curr_values = np.zeros(len(Q))
struct2_var_base = ['' for _ in range(len(Q))]
for i in range(len(Q)):
tab1.append('|')
struct2_curr_values = Q[i]
ind = np.where(x==Q[i])
ind = ind[0]
ind = ind[0]
struct2_var_base[i] = variables[ind]
Vb.append(struct2_var_base[i])
Ci.append(Cj[ind])Ci = np.array(Ci)
Z = sum(np.multiply(Ci,Q))
Zj = np.zeros(len(Cj))
for i in range(len(Cj)):
Zj[i] = sum(np.multiply(Ci,A[:,i]))
vars_at_moment = struct2_var_base.copy()def get_row(vec):
k = ''
for i in vec:
k+= '{0:>10}'.format(round(i,3))
return kprint("=========LP in standard form:=========")
print("variables: ",vari)
print("Activity variables: ",vari_nb)
print("Slack variables: ",vari_slack)
print("Artificial variables: ",vari_ar)
print("======Iteration: 0======")
print("Initializing variables: ",vari)
print("Activity variables: ",[all_vars[v] for v in vari_nb])
print("Slack variables: ",vari_slack,[all_vars[v] for v in vari_slack])
print("Artificial variables: ",v_ar)
print('=======================================================================================================')
print("Variables: ",get_row(np.arange(start=1,stop=len(A[0,:])+1,step = 1 )))
print("Cj: ",get_row(Cj))
print("Basic |Value |RHS")
for i in range(num_consts):
print('|',"{0:>10}".format(vars_at_moment[i]),'|',"{0:>10}".format(Ci[i]),'|',"{0:>10}".format(round(Q[i],3)),'|',get_row(A[i]),'|')
print('=======================================================================================================')
print('Zj: ',get_row(Zj))
print('Cj-Zj: ',get_row(Cj-Zj))
print('Z: ',round(Z,3))=========LP in standard form:=========
variables: ['x1', 'x2', 'x3', 'x4', 'x5', 'x6', 'x7']
Activity variables: ['x1', 'x2', 'x3']
Slack variables: ['x4', 'x5', 'x6', 'x7']
Artificial variables: []
======Iteration: 0======
Initializing variables: ['x1', 'x2', 'x3', 'x4', 'x5', 'x6', 'x7']
Activity variables: [0.0, 0.0, 0.0]
Slack variables: ['x4', 'x5', 'x6', 'x7'] [55.0, 26.0, 30.0, 57.0]
Artificial variables: []
=======================================================================================================
Variables: 1 2 3 4 5 6 7
Cj: 20.0 10.0 15.0 0.0 0.0 0.0 0.0
Basic |Value |RHS
| x4 | 0.0 | 55.0 | 3.0 2.0 5.0 1.0 0.0 0.0 0.0 |
| x5 | 0.0 | 26.0 | 2.0 1.0 1.0 0.0 1.0 0.0 0.0 |
| x6 | 0.0 | 30.0 | 1.0 1.0 3.0 0.0 0.0 1.0 0.0 |
| x7 | 0.0 | 57.0 | 5.0 2.0 4.0 0.0 0.0 0.0 1.0 |
=======================================================================================================
Zj: 0.0 0.0 0.0 0.0 0.0 0.0 0.0
Cj-Zj: 20.0 10.0 15.0 0.0 0.0 0.0 0.0
Z: 0.0
iterNum = 1
while iterNum<=10:
iterNum+=1
type_problem = 1
if type_problem == 1:
num = max(Cj-Zj)
index = np.where((Cj-Zj)==num)
index = index[0][0]
v_enter = variables[index]
else:
num = min(Cj-Zj)
index = np.where((Cj-Zj)==num)
index = index[0][0]
v_enter = variables[index]
b = A[:,index]
k = -1
d = 10000
for i in range(len(Q)):
if b[i]>0:
div = Q[i]/b[i]
if d>=div:
d = div
k = i
if k == -1:
print('Solution is infinty ')
break
else:
num2 = k
v_leave = struct2_var_base[num2]
struct2_var_base[num2] = v_enter
pivot = A[num2,index]
Ci[num2] = Cj[index]
A[num2,:] = A[num2,:]/pivot
Q[num2] = Q[num2]/pivot
#Row operations:
for i in range(num_consts):
if i!= num2:
Q[i] = Q[i] - A[i,index]*Q[num2]
A[i,:] = A[i,:] - A[i,index]*A[num2,:]
Z = sum(np.multiply(Ci,Q))
for i in range(len(A[0,:])):
Zj[i] = sum(np.multiply(A[:,i],Ci))
vars_at_moment = []
for i in range(num_consts):
vars_at_moment.append(struct2_var_base[i])
print('=====Iteration',iterNum,'=======')
print('Enter: ',v_enter)
print('Leave: ',v_leave)
print('Pivot: ',round(pivot,3))
print('========')
print('=======================================================================================================')
print("Variables: ",get_row(np.arange(start=1,stop=len(A[0,:])+1,step = 1 )))
print("Cj: ",get_row(Cj))
print("Basic |Value |RHS")
for i in range(num_consts):
print('|',"{0:>10}".format(vars_at_moment[i]),'|',"{0:>10}".format(Ci[i]),'|',"{0:>10}".format(round(Q[i],3)),'|',get_row(A[i]),'|')
print('=======================================================================================================')
print('Zj: ',get_row(Zj))
print('Cj-Zj: ',get_row(Cj-Zj))
print('Z: ',round(Z,3))
if type_problem ==1:
temp = max(Cj-Zj)
if temp<=0:
break
else:
temp = min(Cj-Zj)
if temp>=0:
break
=====Iteration 2 =======
Enter: x1
Leave: x7
Pivot: 5.0
========
=======================================================================================================
Variables: 1 2 3 4 5 6 7
Cj: 20.0 10.0 15.0 0.0 0.0 0.0 0.0
Basic |Value |RHS
| x4 | 0.0 | 20.8 | 0.0 0.8 2.6 1.0 0.0 0.0 -0.6 |
| x5 | 0.0 | 3.2 | 0.0 0.2 -0.6 0.0 1.0 0.0 -0.4 |
| x6 | 0.0 | 18.6 | 0.0 0.6 2.2 0.0 0.0 1.0 -0.2 |
| x1 | 20.0 | 11.4 | 1.0 0.4 0.8 0.0 0.0 0.0 0.2 |
=======================================================================================================
Zj: 20.0 8.0 16.0 0.0 0.0 0.0 4.0
Cj-Zj: 0.0 2.0 -1.0 0.0 0.0 0.0 -4.0
Z: 228.0
=====Iteration 3 =======
Enter: x2
Leave: x5
Pivot: 0.2
========
=======================================================================================================
Variables: 1 2 3 4 5 6 7
Cj: 20.0 10.0 15.0 0.0 0.0 0.0 0.0
Basic |Value |RHS
| x4 | 0.0 | 8.0 | 0.0 0.0 5.0 1.0 -4.0 0.0 1.0 |
| x2 | 10.0 | 16.0 | 0.0 1.0 -3.0 0.0 5.0 0.0 -2.0 |
| x6 | 0.0 | 9.0 | 0.0 0.0 4.0 0.0 -3.0 1.0 1.0 |
| x1 | 20.0 | 5.0 | 1.0 0.0 2.0 0.0 -2.0 0.0 1.0 |
=======================================================================================================
Zj: 20.0 10.0 10.0 0.0 10.0 0.0 0.0
Cj-Zj: 0.0 0.0 5.0 0.0 -10.0 0.0 0.0
Z: 260.0
=====Iteration 4 =======
Enter: x3
Leave: x4
Pivot: 5.0
========
=======================================================================================================
Variables: 1 2 3 4 5 6 7
Cj: 20.0 10.0 15.0 0.0 0.0 0.0 0.0
Basic |Value |RHS
| x3 | 15.0 | 1.6 | 0.0 0.0 1.0 0.2 -0.8 0.0 0.2 |
| x2 | 10.0 | 20.8 | 0.0 1.0 0.0 0.6 2.6 0.0 -1.4 |
| x6 | 0.0 | 2.6 | 0.0 0.0 0.0 -0.8 0.2 1.0 0.2 |
| x1 | 20.0 | 1.8 | 1.0 0.0 0.0 -0.4 -0.4 0.0 0.6 |
=======================================================================================================
Zj: 20.0 10.0 15.0 1.0 6.0 0.0 1.0
Cj-Zj: 0.0 0.0 0.0 -1.0 -6.0 0.0 -1.0
Z: 268.0
