{ "cells": [ { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "Warning: Initial tableau is not dual feasible (objective row has negative coefficients).\n", "The standard Dual Simplex method might not apply directly or may require Phase I.\n", "--- Starting Dual Simplex Method ---\n", "\n", "--- Iteration 0 ---\n", " BV Z x1 x2 s1 s2 s3 RHS\n", "------------------------------------------------------------------------\n", " Z 1.000 1.000 -2.000 0.000 0.000 0.000 0.000\n", " s1 0.000 -5.000 -4.000 1.000 0.000 0.000 -20.000\n", " s2 0.000 1.000 5.000 0.000 1.000 0.000 10.000\n", " s3 0.000 -1.000 -5.000 0.000 0.000 1.000 -10.000\n", "------------------------------------------------------------------------\n", "\n", "Step: Select Pivot Row (Leaving Variable)\n", " RHS values (b): [-20. 10. -10.]\n", " Most negative RHS is -20.000 in Row 1 (Basic Var: s1).\n", " Leaving Variable: s1 (Row 1)\n", "\n", "Step: Select Pivot Column (Entering Variable) using Ratio Test\n", " Pivot Row (Row 1) coefficients (excluding Z, RHS): [-5. -4. 1. 0. 0.]\n", " Objective Row coefficients (excluding Z, RHS): [ 1. -2. 0. 0. 0.]\n", " Calculating ratios = ObjCoeff / abs(PivotRowCoeff) for PivotRowCoeff < 0:\n", " Var x1 (Col 1): Coeff=-5.000, ObjCoeff=1.000, Ratio = 1.000 / 5.000 = 0.200\n", " Var x2 (Col 2): Coeff=-4.000, ObjCoeff=-2.000, Ratio = -2.000 / 4.000 = -0.500\n", " Minimum ratio is -0.500 for variable x2 (Column 2).\n", " Entering Variable: x2 (Column 2)\n", "\n", "Step: Pivot Operation\n", " Pivot Element: -4.000 at (Row 1, Col 2)\n", " Normalizing Pivot Row 1 by dividing by -4.000\n", " Eliminating other entries in Pivot Column 2:\n", " Row 0 = Row 0 - (-2.000) * (New Row 1)\n", " Row 2 = Row 2 - (5.000) * (New Row 1)\n", " Row 3 = Row 3 - (-5.000) * (New Row 1)\n", " Updating Basic Variables: x2 replaces s1 in the basis for Row 1.\n", "\n", "--- Iteration 1 ---\n", " BV Z x1 x2 s1 s2 s3 RHS\n", "------------------------------------------------------------------------\n", " Z 1.000 3.500 0.000 -0.500 0.000 0.000 10.000\n", " x2 -0.000 1.250 1.000 -0.250 -0.000 -0.000 5.000\n", " s2 0.000 -5.250 0.000 1.250 1.000 0.000 -15.000\n", " s3 0.000 5.250 0.000 -1.250 0.000 1.000 15.000\n", "------------------------------------------------------------------------\n", "\n", "Step: Select Pivot Row (Leaving Variable)\n", " RHS values (b): [ 5. -15. 15.]\n", " Most negative RHS is -15.000 in Row 2 (Basic Var: s2).\n", " Leaving Variable: s2 (Row 2)\n", "\n", "Step: Select Pivot Column (Entering Variable) using Ratio Test\n", " Pivot Row (Row 2) coefficients (excluding Z, RHS): [-5.25 0. 1.25 1. 0. ]\n", " Objective Row coefficients (excluding Z, RHS): [ 3.5 0. -0.5 0. 0. ]\n", " Calculating ratios = ObjCoeff / abs(PivotRowCoeff) for PivotRowCoeff < 0:\n", " Var x1 (Col 1): Coeff=-5.250, ObjCoeff=3.500, Ratio = 3.500 / 5.250 = 0.667\n", " Minimum ratio is 0.667 for variable x1 (Column 1).\n", " Entering Variable: x1 (Column 1)\n", "\n", "Step: Pivot Operation\n", " Pivot Element: -5.250 at (Row 2, Col 1)\n", " Normalizing Pivot Row 2 by dividing by -5.250\n", " Eliminating other entries in Pivot Column 1:\n", " Row 0 = Row 0 - (3.500) * (New Row 2)\n", " Row 1 = Row 1 - (1.250) * (New Row 2)\n", " Row 3 = Row 3 - (5.250) * (New Row 2)\n", " Updating Basic Variables: x1 replaces s2 in the basis for Row 2.\n", "\n", "--- Iteration 2 ---\n", " BV Z x1 x2 s1 s2 s3 RHS\n", "------------------------------------------------------------------------\n", " Z 1.000 0.000 0.000 0.333 0.667 0.000 0.000\n", " x2 0.000 0.000 1.000 0.048 0.238 0.000 1.429\n", " x1 -0.000 1.000 -0.000 -0.238 -0.190 -0.000 2.857\n", " s3 0.000 0.000 0.000 0.000 1.000 1.000 0.000\n", "------------------------------------------------------------------------\n", "\n", "--- Optimal Solution Found ---\n", " All RHS values are non-negative.\n", "\n", "--- Final Solution ---\n", "\n", "--- Iteration Final ---\n", " BV Z x1 x2 s1 s2 s3 RHS\n", "------------------------------------------------------------------------\n", " Z 1.000 0.000 0.000 0.333 0.667 0.000 0.000\n", " x2 0.000 0.000 1.000 0.048 0.238 0.000 1.429\n", " x1 -0.000 1.000 -0.000 -0.238 -0.190 -0.000 2.857\n", " s3 0.000 0.000 0.000 0.000 1.000 1.000 0.000\n", "------------------------------------------------------------------------\n", "Optimal Objective Value (Max Z): 0.000000\n", "Optimal Variable Values:\n", " x1: 2.857143\n", " x2: 1.428571\n", "Slack/Surplus Variable Values:\n" ] } ], "source": [ "from functions.DualSimplexSolver import DualSimplexSolver\n", "if __name__ == \"__main__\":\n", " try:\n", " example_obj_type = 'max'\n", " example_c = [-1,2]\n", " example_A = [\n", " [5,4],\n", " [1,5],\n", " ]\n", " example_relations = ['>=', '=']\n", " example_b = [20,10]\n", "\n", " solver = DualSimplexSolver(example_obj_type, example_c, example_A, example_relations, example_b)\n", " solver.solve()\n", " except Exception as e:\n", " print(f\"\\nAn error occurred: {e}\")\n", " import traceback\n", " traceback.print_exc()" ] } ], "metadata": { "kernelspec": { "display_name": ".venv (3.13.2)", "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.13.2" } }, "nbformat": 4, "nbformat_minor": 2 }