单纯形标准算法
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
}
关于此算法
这是一个使用单纯形法解决线性规划问题的笔记本。输入以标准 LPP 的形式提供，即目标应为最大化类型，所有约束应为 <= 类型。例如
最大化 z：3*x1 + 4*x2
s.t.: 5*x1+ 4*x2<=15
...
这里解决了一个示例问题：最大化 P = 20x1 + 10x2 + 15x3
约束条件
3x1 + 2x2 + 5x3 ≤ 55
2x1 + x2 + x3 ≤ 26
x1 + x2 + 3x3 ≤ 30
5x1 + 2x2 + 4x3 ≤ 57
x1 , x2 , x3 ≥ 0
import numpy as np输入单纯形数据
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()从这里重新输入相同的数据
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
