import numpy as np from tabulate import tabulate import gradio as gr from maths.operations_research.utils import parse_matrix from maths.operations_research.utils import parse_vector def simplex_solver_with_steps(c, A, b, bounds): """ Solve LP using simplex method and display full tableau at each step Parameters: - c: Objective coefficients (for maximizing c'x) - A: Constraint coefficients matrix - b: Right-hand side of constraints - bounds: Variable bounds as [(lower_1, upper_1), (lower_2, upper_2), ...] Returns: - x: Optimal solution - optimal_value: Optimal objective value - steps_log: List of strings detailing each step """ steps_log = [] steps_log.append("\n--- Starting Simplex Method ---") steps_log.append(f"Objective: Maximize {' + '.join([f'{c[i]}x_{i}' for i in range(len(c))])}") steps_log.append(f"Constraints:") for i in range(len(b)): constraint_str = ' + '.join([f"{A[i,j]}x_{j}" for j in range(A.shape[1])]) steps_log.append(f" {constraint_str} <= {b[i]}") # Convert problem to standard form (for tableau method) # First handle bounds by adding necessary constraints A_with_bounds = A.copy() b_with_bounds = b.copy() for i, (lb, ub) in enumerate(bounds): if lb is not None and lb > 0: # For variables with lower bounds > 0, we'll substitute x_i = x_i' + lb # This affects all constraints where x_i appears for j in range(A.shape[0]): b_with_bounds[j] -= A[j, i] * lb # Number of variables and constraints n_vars = len(c) n_constraints = A.shape[0] # Add slack variables to create standard form # The tableau will have: [objective row | RHS] # [-------------|----] # [constraints | RHS] # Initial tableau: # First row is -c (negative of objective coefficients) and 0s for slack variables, then 0 (for max) # The rest are constraint coefficients, then identity matrix for slack variables, then RHS tableau = np.zeros((n_constraints + 1, n_vars + n_constraints + 1)) # Set the objective row (negated for maximization) tableau[0, :n_vars] = -c # Set the constraint coefficients tableau[1:, :n_vars] = A_with_bounds # Set the slack variable coefficients (identity matrix) for i in range(n_constraints): tableau[i + 1, n_vars + i] = 1 # Set the RHS tableau[1:, -1] = b_with_bounds # Base and non-base variables base_vars = list(range(n_vars, n_vars + n_constraints)) # Slack variables are initially basic # Function to print current tableau def print_tableau(tableau, base_vars, steps_log_func): headers = [f"x_{j}" for j in range(n_vars)] + [f"s_{j}" for j in range(n_constraints)] + ["RHS"] rows = [] row_labels = ["z"] + [f"eq_{i}" for i in range(n_constraints)] for i, row in enumerate(tableau): rows.append([row_labels[i]] + [f"{val:.3f}" for val in row]) steps_log_func.append("\nCurrent Tableau:") steps_log_func.append(tabulate(rows, headers=headers, tablefmt="grid")) steps_log_func.append(f"Basic variables: {[f'x_{v}' if v < n_vars else f's_{v-n_vars}' for v in base_vars]}") # Print initial tableau steps_log.append("\nInitial tableau:") print_tableau(tableau, base_vars, steps_log) # Main simplex loop iteration = 0 max_iterations = 100 # Prevent infinite loops while iteration < max_iterations: iteration += 1 steps_log.append(f"\n--- Iteration {iteration} ---") # Find the entering variable (most negative coefficient in objective row for maximization) entering_col = np.argmin(tableau[0, :-1]) if tableau[0, entering_col] >= -1e-10: # Small negative numbers due to floating-point errors steps_log.append("Optimal solution reached - no negative coefficients in objective row") break steps_log.append(f"Entering variable: {'x_' + str(entering_col) if entering_col < n_vars else 's_' + str(entering_col - n_vars)}") # Find the leaving variable using min ratio test ratios = [] for i in range(1, n_constraints + 1): if tableau[i, entering_col] <= 0: ratios.append(np.inf) # Avoid division by zero or negative else: ratios.append(tableau[i, -1] / tableau[i, entering_col]) if all(r == np.inf for r in ratios): steps_log.append("Unbounded solution - no leaving variable found") return steps_log, None, float('inf') # Problem is unbounded # Find the row with minimum ratio leaving_row = np.argmin(ratios) + 1 # +1 because we skip the objective row leaving_var = base_vars[leaving_row - 1] steps_log.append(f"Leaving variable: {'x_' + str(leaving_var) if leaving_var < n_vars else 's_' + str(leaving_var - n_vars)}") steps_log.append(f"Pivot element: {tableau[leaving_row, entering_col]:.3f} at row {leaving_row}, column {entering_col}") # Perform pivot operation # First, normalize the pivot row pivot = tableau[leaving_row, entering_col] tableau[leaving_row] = tableau[leaving_row] / pivot # Update other rows for i in range(tableau.shape[0]): if i != leaving_row: factor = tableau[i, entering_col] tableau[i] = tableau[i] - factor * tableau[leaving_row] # Update basic variables base_vars[leaving_row - 1] = entering_col # Print updated tableau steps_log.append("\nAfter pivot:") print_tableau(tableau, base_vars, steps_log) if iteration == max_iterations: steps_log.append("Max iterations reached without convergence") return steps_log, None, None # Extract solution x = np.zeros(n_vars) for i, var in enumerate(base_vars): if var < n_vars: # If it's an original variable and not a slack x[var] = tableau[i + 1, -1] # Account for variable substitutions (if lower bounds were applied) for i, (lb, _) in enumerate(bounds): if lb is not None and lb > 0: x[i] += lb # Calculate objective value optimal_value = np.dot(c, x) steps_log.append("\n--- Simplex Method Complete ---") steps_log.append(f"Optimal solution found: {x}") steps_log.append(f"Optimal objective value: {optimal_value}") return steps_log, x, optimal_value # Gradio interface def parse_input_list(s): # Helper to parse comma/space/semicolon separated numbers return [float(x) for x in s.replace(';', ' ').replace(',', ' ').split() if x.strip()] def parse_matrix(s): # Helper to parse matrix input as rows separated by newlines, columns by comma/space return np.array([parse_input_list(row) for row in s.strip().split('\n') if row.strip()]) def parse_bounds(s): # Helper to parse bounds as (lower, upper) per variable, e.g. "0, None\n0, None" bounds = [] for row in s.strip().split('\n'): parts = row.replace('None', 'None').replace('none', 'None').split(',') lb = float(parts[0]) if parts[0].strip().lower() != 'none' else None ub = float(parts[1]) if len(parts) > 1 and parts[1].strip().lower() != 'none' else None bounds.append((lb, ub)) return bounds def gradio_simplex(c_str, A_str, b_str, bounds_str): try: c = parse_input_list(c_str) A = parse_matrix(A_str) b = parse_input_list(b_str) bounds = parse_bounds(bounds_str) steps_log, x, optimal_value = simplex_solver_with_steps(c, A, b, bounds) steps = '\n'.join(steps_log) if x is not None: solution = f"Optimal solution: {x}\nOptimal value: {optimal_value}" else: solution = "No optimal solution found." return steps, solution except Exception as e: return f"Error: {e}", "" with gr.Blocks() as demo: gr.Markdown(""" # Simplex Solver with Steps (Gradio) Enter your LP problem below. All inputs are required. - **Objective coefficients (c):** e.g. `3, 2` - **Constraint matrix (A):** one row per line, e.g. `1, 2`\n`2, 1` - **RHS vector (b):** e.g. `6, 8` - **Bounds:** one row per variable, lower and upper bound separated by comma, e.g. `0, None`\n`0, None` """) c_in = gr.Textbox(label="Objective coefficients (c)", value="3, 2") A_in = gr.Textbox(label="Constraint matrix (A)", value="1, 2\n2, 1") b_in = gr.Textbox(label="RHS vector (b)", value="6, 8") bounds_in = gr.Textbox(label="Bounds", value="0, None\n0, None") btn = gr.Button("Solve") steps_out = gr.Textbox(label="Simplex Steps", lines=20) sol_out = gr.Textbox(label="Solution") btn.click(gradio_simplex, inputs=[c_in, A_in, b_in, bounds_in], outputs=[steps_out, sol_out]) def main(): demo.launch() if __name__ == "__main__": main() def run_simplex_solver_interface(c_str, A_str, b_str, bounds_str): """ Wrapper function to connect simplex_solver_with_steps with Gradio interface. """ current_log_list = ["Initializing Simplex Solver (with Steps) Interface..."] c = parse_vector(c_str) if not c: current_log_list.append("Error: Objective coefficients (c) could not be parsed or are empty.") return "Error parsing c", "Error parsing c", "\n".join(current_log_list) A = parse_matrix(A_str) if A.size == 0: current_log_list.append("Error: Constraint matrix (A) could not be parsed or is empty.") return "Error parsing A", "Error parsing A", "\n".join(current_log_list) b = parse_vector(b_str) if not b: current_log_list.append("Error: Constraint bounds (b) could not be parsed or are empty.") return "Error parsing b", "Error parsing b", "\n".join(current_log_list) variable_bounds = parse_bounds(bounds_str) # This returns a list of tuples or [] # parse_bounds includes gr.Warning on failure and returns [] if bounds_str and not variable_bounds: # If input was given but parsing failed current_log_list.append("Error: Variable bounds string could not be parsed. Please check format.") # parse_bounds already issues a gr.Warning return "Error parsing var_bounds", "Error parsing var_bounds", "\n".join(current_log_list) # Dimensional validation if A.shape[0] != len(b): current_log_list.append(f"Dimension mismatch: Number of rows in A ({A.shape[0]}) must equal length of b ({len(b)}).") return "Dimension Error", "Dimension Error", "\n".join(current_log_list) if A.shape[1] != len(c): current_log_list.append(f"Dimension mismatch: Number of columns in A ({A.shape[1]}) must equal length of c ({len(c)}).") return "Dimension Error", "Dimension Error", "\n".join(current_log_list) if variable_bounds and len(variable_bounds) != len(c): current_log_list.append(f"Dimension mismatch: Number of variable bounds pairs ({len(variable_bounds)}) must equal number of objective coefficients ({len(c)}).") return "Dimension Error", "Dimension Error", "\n".join(current_log_list) # If bounds_str is empty, parse_bounds returns [], which is fine for the solver if it expects default non-negativity or specific handling. # The simplex_solver_with_steps expects a list of tuples, and an empty list if no specific bounds beyond non-negativity are implied by problem setup. # For this solver, bounds are crucial. If not provided, we should create default non-negative bounds. if not variable_bounds: variable_bounds = [(0, None) for _ in range(len(c))] current_log_list.append("Defaulting to non-negative bounds for all variables as no specific bounds were provided.") current_log_list.append("Inputs parsed and validated successfully.") try: # Ensure inputs are NumPy arrays as expected by some solvers (though this one might be flexible) np_c = np.array(c) np_b = np.array(b) # Call the solver # simplex_solver_with_steps returns: steps_log, x, optimal_value steps_log, x_solution, opt_val = simplex_solver_with_steps(np_c, A, np_b, variable_bounds) current_log_list.extend(steps_log) # steps_log is already a list of strings solution_str = "N/A" objective_str = "N/A" if x_solution is not None: solution_str = ", ".join([f"{val:.3f}" for val in x_solution]) else: # Check specific messages in log if solution is None if any("Unbounded solution" in msg for msg in steps_log): solution_str = "Unbounded solution" elif any("infeasible" in msg.lower() for msg in steps_log): # More general infeasibility check solution_str = "Infeasible solution" if opt_val is not None: if opt_val == float('inf') or opt_val == float('-inf'): objective_str = str(opt_val) else: objective_str = f"{opt_val:.3f}" return solution_str, objective_str, "\n".join(current_log_list) except Exception as e: gr.Error(f"An error occurred during solving with Simplex Method: {e}") current_log_list.append(f"Runtime error in Simplex Method: {e}") return "Solver error", "Solver error", "\n".join(current_log_list) simplex_solver_interface = gr.Interface( fn=run_simplex_solver_interface, inputs=[ gr.Textbox(label="Objective Coefficients (c)", info="Comma-separated for maximization problem, e.g., 3,5"), gr.Textbox(label="Constraint Matrix (A)", info="Rows separated by ';', elements by ',', e.g., 1,0;0,2;3,2. Assumes Ax <= b."), gr.Textbox(label="Constraint RHS (b)", info="Comma-separated, e.g., 4,12,18"), gr.Textbox(label="Variable Bounds (L,U) per variable", info="Pairs like L1,U1; L2,U2;... Use 'None' for no bound. E.g., '0,None;0,10'. If empty, defaults to non-negative for all variables (0,None).") ], outputs=[ gr.Textbox(label="Optimal Solution (x)"), gr.Textbox(label="Optimal Objective Value"), gr.Textbox(label="Solver Steps and Tableaus", lines=20, interactive=False) ], title="Simplex Method Solver (with Tableau Steps)", description="Solves Linear Programs (maximization, Ax <= b) using the Simplex method and displays detailed tableau iterations. Assumes variables are non-negative if bounds not specified.", examples=[ [ # Classic example from many textbooks (e.g., Taha, Operations Research) "3,5", # c (Max Z = 3x1 + 5x2) "1,0;0,2;3,2", # A "4,12,18", # b "0,None;0,None" # x1 >=0, x2 >=0 (explicitly stating non-negativity) ], [ # Another common example "5,4", # c (Max Z = 5x1 + 4x2) "6,4;1,2; -1,1;0,1", # A "24,6,1,2", #b "0,None;0,None" # x1,x2 >=0 ], [ # Example that might be unbounded if not careful or show interesting steps "1,1", "1,-1;-1,1", "1,1", "0,None;0,None" # x1-x2 <=1, -x1+x2 <=1 ] ], flagging_mode="manual" )