Spaces:
Runtime error
Runtime error
File size: 5,500 Bytes
e4806d5 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 |
import numpy as np
from ast_parser.parser import EquationKind # Assuming EquationKind is imported from another module
class Solver:
"""Solver takes in the equations which have been parsed from the input,
it converts them to matrix arrays and applies the matrix operations on
them.
Args:
objective_functions (list of Equation objects): List of objective functions.
constraints (list of Equation objects): List of constraint equations.
"""
def __init__(self, objective_functions, constraints):
# Extract objective function variables and negate their coefficients
self.objective_functions = objective_functions[0].variables
self.objective_functions.pop('Z')
self.constraints = []
for i, _ in enumerate(constraints):
self.constraints.append(constraints[i])
# Negate coefficients of objective function for maximization
for key in self.objective_functions:
self.objective_functions[key] *= -1
# Add slack variables to constraints if necessary
for temp_dict in constraints:
for key in self.objective_functions.keys():
if key not in temp_dict.variables:
temp_dict.variables[key] = 0
slack = len(self.constraints)
i = 0
for _, constraint in enumerate(self.constraints):
if constraint.kind == EquationKind.LEQ:
constraint.variables["s_" + str(i)] = 1.0
self.objective_functions["s_" + str(i)] = 0
i += 1
while i < slack:
constraint.variables["s_" + str(i)] = 1.0
self.objective_functions["s_" + str(i)] = 0
i += 1
self.A, self.B, self.C = self.convert_to_matrices()
def get_results(self):
objective_values, solution, variable_names = self.advanced_simplex(self.A, self.B, self.C)
variable_names = list(variable_names.values())
results_str = "The vector of decision variables is : \n"
for i in range(len(objective_values)):
results_str+= f"{variable_names[i]} : {round(objective_values[i, 0], 2)}\n"
results_str+= "The optimal solution is {}\n".format(solution)
return results_str
def convert_to_matrices(self):
"""Converts objective functions and constraints to matrices.
Returns:
A (numpy.ndarray): Coefficients matrix for constraints.
B (numpy.ndarray): Right-hand side matrix for constraints.
C (numpy.ndarray): Coefficients matrix for objective function.
"""
num_constraints = len(self.constraints)
num_variables = len(self.objective_functions)
A = np.zeros((num_constraints, num_variables))
C = np.zeros((1, num_variables))
B = np.zeros((num_constraints, 1))
for i, constraint in enumerate(self.constraints):
for variable_name, coefficient in constraint.variables.items():
j = list(self.objective_functions.keys()).index(variable_name)
A[i, j] = coefficient
for variable_name, coefficient in self.objective_functions.items():
j = list(self.objective_functions.keys()).index(variable_name)
C[0, j] = coefficient
B[i, 0] = constraint.bound
return A, B, C
def advanced_simplex(self, A, b, C):
"""Performs the advanced simplex algorithm to find the optimal solution.
Args:
A (numpy.ndarray): Coefficients matrix for constraints.
b (numpy.ndarray): Right-hand side matrix for constraints.
C (numpy.ndarray): Coefficients matrix for objective function.
Returns:
objective_values (numpy.ndarray): The values of the objective function variables.
solution (float): The optimal solution value.
"""
n, m = A.shape
B = np.eye(n)
C_B = np.zeros((1, n))
count = 0
variable_names = list(self.objective_functions.keys())[-n:]
variable_names = {key: value for key, value in zip(range(n), variable_names)}
prev_solution = float('inf')
while True:
count += 1
B_inverse = np.around(np.linalg.inv(B), decimals=2)
for row in B_inverse:
for value in row:
if value == -0:
value = 0
X_B = np.matmul(B_inverse, b)
P_table = np.round(np.matmul(B_inverse, A), 2)
objective_values = np.matmul(C_B, P_table) - C
solution = np.round(np.matmul(C_B, X_B), 2)
if abs(prev_solution - solution) < 0.0001:
return X_B, solution, variable_names
entering_var_idx = np.argmin(objective_values)
ratios = []
for i in range(n):
if P_table[i, entering_var_idx] > 0:
ratios.append(X_B[i, 0] / P_table[i, entering_var_idx])
else:
ratios.append(np.inf)
exiting_var_idx = np.argmin(ratios)
temp_list = list(self.objective_functions.keys())
variable_names[exiting_var_idx] = temp_list[entering_var_idx]
B[:, exiting_var_idx] = A[:, entering_var_idx]
C_B[:, exiting_var_idx] = C[:, entering_var_idx]
prev_solution = solution |