khushpatel2002/Optimization

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