Este proyecto implementa una aplicación interactiva en consola (usando la librería Textual) para resolver problemas de Programación Lineal (PL) mediante tres métodos fundamentales:
- Algoritmo Simplex (primal)
- Conversión a problema Dual
- Algoritmo Dual Simplex
El objetivo es proporcionar una herramienta visual y educativa para entender el proceso iterativo de estos métodos, mostrando el tableau paso a paso, la función objetivo, las restricciones y la solución actual.
El sistema está desarrollado en Python y modularizado en distintas carpetas para mantener una arquitectura clara, flexible y ampliable.
El sistema sigue una arquitectura modular basada en componentes, donde cada parte cumple un rol específico:
📦 ProyectoPL/
├── App.py # Punto de entrada principal (menú de selección de método)
├── MicroModulos.py # Widgets reutilizables de la interfaz (restricciones, FO, tabla, solución)
├── Parser.py # Analizador de expresiones matemáticas (restricciones y FO)
├── Simplex/
│ ├── Simplex.py # Pantalla del algoritmo Simplex paso a paso
│ ├── SimplexTCSS.py # Estilos CSS para la interfaz Simplex
│ └── SolverSimplex.py # Implementación del solver Simplex (Two-Phase)
├── Dual/
│ ├── Dual.py # Conversor de problema Primal a Dual (interfaz)
│ └── DualConversor.py # Lógica de conversión entre formas Primal y Dual
├── DualSimplex/
│ ├── DualSimplex.py # Pantalla del algoritmo Dual Simplex
│ └── SolverDualSimplex.py # Implementación del solver Dual Simplex
└── assets/ # (Opcional) Archivos CSS o recursos adicionales
El flujo principal parte del archivo App.py, desde donde el usuario elige el método a utilizar.
Contiene el menú principal de la aplicación. Utiliza textual.app.App para renderizar una interfaz interactiva con botones que permiten al usuario elegir entre los tres métodos principales.
Fragmento destacado:
class MenuPrincipal(App):
def compose(self):
yield Header()
yield Footer()
with Vertical(id="menu"):
yield Static("Seleccione el método a utilizar:", id="tituloMenu")
yield Button("Algoritmo Simplex", id="botonSimplex")
yield Button("Conversión Dual", id="botonDual")
yield Button("Algoritmo Simplex Dual", id="botonAlgDual")Cada botón abre una pantalla distinta (SimplexApp, DualApp, DualSimplexApp).
Define una serie de widgets personalizados que estructuran la interfaz. Estos componentes son reutilizados en todas las pantallas (Simplex, Dual, Dual Simplex):
WidgetFuncionObjetivo: permite ingresar y validar la función objetivo.WidgetRestricciones: administra las restricciones (agregar, eliminar, validar).WidgetSolucion: muestra el estado actual de la solución.WidgetTablaIteraciones: renderiza el tableau Simplex en formato tabular.
Ejemplo:
class WidgetFuncionObjetivo(Container):
def on_input_submitted(self, event: Input.Submitted):
self.funcion_objetivo = event.value.strip()
Parser.Parsear(self.funcion_objetivo + "<=0") # validación sintácticaEstos widgets gestionan la reactividad de la interfaz y notifican al usuario sobre errores o cambios.
Implementa el analizador de expresiones utilizado para interpretar la función objetivo y las restricciones.
- Soporta hasta 10 variables (
x1,x2, ...x10). - Permite expresiones con o sin asterisco (
3x1o3*x1). - Devuelve un diccionario con coeficientes, operador y constante.
Salida ejemplo:
Parsear("3x1 + 2x2 <= 10")
# → {'coef': [3.0, 2.0, 0, ...], 'operador': '<=', 'constante': 10.0}Este módulo es usado por todos los solvers y conversores para estandarizar las entradas del usuario.
Pantalla interactiva del Método Simplex paso a paso. Permite:
- Ingresar la FO y las restricciones.
- Ejecutar iteraciones manuales.
- Visualizar el tableau actualizado.
- Mostrar mensajes de estado (fase I, fase II, óptimo, ilimitado, infactible).
Implementa el algoritmo Simplex paso a paso, con soporte para dos fases (manejo de variables artificiales).
Incluye métodos internos para:
- Inicializar el modelo (
initialize) - Calcular soluciones actuales (
_compute_current_solution) - Calcular costos reducidos y elegir variables entrantes/salientes
- Ejecutar pivotaciones (
iterate_one)
Ejemplo de inicialización:
solver = SimplexSolver()
solver.initialize("Max", "3x1 + 5x2", ["x1 + 2x2 <= 6", "3x1 + 2x2 <= 12"])El solver devuelve snapshots con el tableau actual y el valor de Z, utilizados por WidgetTablaIteraciones para la visualización.
Define estilos CSS aplicados a los paneles del Simplex (PanelIzquierdo, PanelDerecho).
Interfaz para la conversión de un problema Primal a su forma Dual. Permite ingresar una función objetivo y restricciones, y muestra el problema dual generado.
Contiene la lógica matemática de conversión Primal ↔ Dual.
Flujo general:
- Parsea la FO y las restricciones.
- Calcula la transpuesta de la matriz
A(intercambiando roles de variables y restricciones). - Genera la nueva función objetivo y las condiciones de signo.
Ejemplo:
conversor = DualConversor()
resultado = conversor.Convertir("3x1 + 5x2", ["x1 + 2x2 <= 8", "x1 + x2 <= 6"], "Max")Resultado:
Modo: Min
Función Objetivo Dual: Min W = 8*y1 + 6*y2
Restricciones:
y1 + y2 >= 3
2*y1 + y2 >= 5
Condiciones:
y1 >= 0
y2 >= 0
Pantalla interactiva del Método Dual Simplex. Combina componentes de entrada (WidgetFuncionObjetivo, WidgetRestricciones) con un panel para el problema dual convertido y una tabla de iteraciones.
Permite:
- Convertir un problema primal a dual (Ctrl+C)
- Ejecutar iteraciones del Dual Simplex (Ctrl+I)
- Mostrar el tableau y la solución en cada paso.
Implementa el Algoritmo Dual Simplex, que mantiene la optimalidad dual y busca factibilidad primal.
Pasos clave:
- Selección de variable saliente: la más negativa (infactible)
- Selección de variable entrante por razón dual mínima
- Pivotación y actualización del tableau
Fragmento:
leaving_row, leaving_var = self._choose_leaving_dual(xB)
entering = self._choose_entering_dual(B_inv, leaving_row, r)
self.basis[leaving_row] = entering- Maximiza o minimiza una FO sujeta a restricciones lineales.
- Maneja desigualdades de tipo
<=,>=,=mediante variables de holgura y artificiales. - Soporta Fase I y II para garantizar factibilidad inicial.
- Transforma un problema primal
Max Z = c^T xen su dualMin W = b^T y. - Intercambia los papeles de restricciones y variables.
- Genera condiciones de signo según el tipo de desigualdad del problema original.
- Mantiene optimalidad dual y busca factibilidad primal.
- Ideal para resolver problemas donde el Simplex tradicional falla al iniciar en una solución factible.
- El usuario ejecuta
App.py. - Selecciona el método desde el menú principal.
- Ingresa la función objetivo y las restricciones.
- El sistema valida la entrada usando
Parser.py. - El solver correspondiente (
SolverSimplexoSolverDualSimplex) procesa una iteración. - El resultado (tableau y valores de variables) se muestra mediante los widgets definidos en
MicroModulos.py.
El sistema usa Textual, una librería moderna para crear interfaces TUI (Text-based User Interfaces). Esto permite presentar la información en paneles, botones y tablas dentro de la terminal.
Cada pantalla hereda de Screen y usa compose() para definir su estructura visual.
Ejemplo:
with Horizontal(id="PanelPrincipal"):
with Vertical(id="PanelIzquierdo"):
yield WidgetFuncionObjetivo(id="FuncionObjetivo")
yield WidgetRestricciones(id="Restricciones")Ejemplo Simplex:
Función objetivo: Max Z = 3x1 + 5x2
Restricciones:
x1 + 2x2 <= 6
3x1 + 2x2 <= 12
x1, x2 >= 0
Pasos:
- Ingresar los datos.
- Presionar Ctrl+I para iterar.
- Observar el tableau actualizado y el valor de Z.
Salida esperada:
Z = 24
x1 = 0
x2 = 3
Estado: óptimo
El proyecto ofrece una herramienta completa para el análisis interactivo de Programación Lineal, integrando algoritmos clásicos con una interfaz amigable y modular.
El diseño del código permite extenderlo para nuevos métodos (como Big-M o Transporte) sin modificar la estructura central.
- Hillier, F. S., & Lieberman, G. J. (2010). Introduction to Operations Research.
- Winston, W. L. (2004). Operations Research: Applications and Algorithms.
- Documentación oficial de Textual.