Métodos de Programación Lineal

Herramienta educativa con visualización paso a paso de siete métodos de optimización

Desarrollado por José Miguel Herrera Gutiérrez para la profesora Bibiana Patricia Arias Villada
Investigación de Operaciones - Universidad Tecnológica de Pereira (UTP) - 2025

¿Qué es la Programación Lineal?

La programación lineal (PL) es una técnica matemática de optimización que permite encontrar la mejor solución (máximo o mínimo) de una función objetivo lineal, sujeta a un conjunto de restricciones lineales.

Componentes de un Problema de PL:
  • Variables de decisión: Cantidades a determinar (x₁, x₂, ..., xₙ)
  • Función objetivo: Expresión matemática a optimizar
  • Restricciones: Limitaciones del problema (desigualdades o ecuaciones)
  • No-negatividad: xᵢ ≥ 0 (cuando aplica)
Aplicaciones Prácticas:
  • Planificación de producción
  • Asignación de recursos
  • Optimización de rutas y logística
  • Gestión de inventarios
  • Planificación financiera
  • Mezcla de productos

Métodos de Resolución Implementados

Esta aplicación implementa siete algoritmos con visualización paso a paso para propósitos educativos

Método Gráfico

📊 Especialidad: Problemas con 2 variables

🎯 Características:

  • Representación visual de restricciones
  • Región factible en el plano
  • Evaluación de vértices
  • Gráfica interactiva generada

✅ Ventajas: Intuitivo, visual, ideal para aprendizaje

⚠️ Limitaciones: Solo funciona con 2 variables

Usar Método

Método Simplex

🚀 Especialidad: Problemas de n variables

🎯 Características:

  • Algoritmo iterativo eficiente
  • Tableau con variables slack/surplus
  • Identificación de pivotes
  • Operaciones de fila documentadas

✅ Ventajas: Escalable, sistemático, robusto

⚠️ Limitaciones: Requiere forma estándar inicial

Usar Método

Dual Simplex

🔄 Especialidad: Problemas duales y análisis

🎯 Características:

  • Comienza con solución dual factible
  • Selección de fila con RHS negativo
  • Cálculo de ratios zⱼ/aᵢⱼ
  • Ideal para restricciones ≥

✅ Ventajas: Análisis de sensibilidad, complementario

⚠️ Limitaciones: Requiere configuración específica

Usar Método

Dijkstra

🛣️ Especialidad: Camino más corto en grafos

🎯 Características:

  • Algoritmo de camino mínimo
  • Usa cola de prioridad (heap)
  • Visualización interactiva con Vis.js
  • Soporta grafos dirigidos/no dirigidos

✅ Ventajas: Eficiente O((V+E)log V), versátil

⚠️ Limitaciones: No funciona con pesos negativos

Usar Método

Kruskal

🌳 Especialidad: Árbol de expansión mínima

🎯 Características:

  • Algoritmo MST (Minimum Spanning Tree)
  • Usa estructura Union-Find
  • Doble visualización con Vis.js
  • Ordena aristas por peso

✅ Ventajas: O(E log E), conexión óptima

⚠️ Limitaciones: Solo grafos no dirigidos

Usar Método

Método Gráfico en Detalle

El método gráfico es la forma más intuitiva de resolver problemas de programación lineal, pero está limitado a dos variables de decisión (x₁ y x₂).

Procedimiento:
  1. Graficar restricciones: Cada desigualdad se representa como una línea en el plano cartesiano
  2. Identificar región factible: Área que satisface todas las restricciones simultáneamente
  3. Localizar vértices: Intersecciones de las rectas
  1. Evaluar función objetivo: Calcular Z en cada vértice
  2. Seleccionar óptimo: El vértice con mejor valor de Z
Teorema fundamental: Si existe una solución óptima finita, al menos uno de los vértices de la región factible es óptimo.
Casos de Uso Ideales:
  • Problemas de mezcla de dos productos
  • Asignación de dos recursos
  • Enseñanza y aprendizaje de PL
  • Validación de resultados de otros métodos

Método Simplex en Detalle

El método Simplex es el algoritmo estándar para resolver problemas de programación lineal con cualquier número de variables. Desarrollado por George Dantzig en 1947.

Fundamento Teórico:

El algoritmo se basa en el teorema de que si existe una solución óptima, se encuentra en un vértice del poliedro convexo definido por las restricciones. El método se mueve sistemáticamente de un vértice a otro adyacente, mejorando el valor de la función objetivo hasta alcanzar el óptimo.

Fases del Algoritmo:
  1. Forma estándar: Convertir restricciones ≤ en ecuaciones con variables slack
  2. Tableau inicial: Construir la matriz del sistema con solución básica factible
  3. Test de optimalidad: Verificar si todos los coeficientes de Z son ≤ 0 (max) o ≥ 0 (min)
  1. Seleccionar pivote: Columna (más negativa) y fila (ratio mínimo RHS/coef)
  2. Operaciones de fila: Hacer pivote = 1 y ceros en su columna
  3. Iterar: Repetir hasta alcanzar optimalidad
En esta aplicación: Cada iteración muestra el tableau completo con identificación de elementos pivote y documentación de las operaciones de fila realizadas.
Ventajas Principales:
  • Escalabilidad: Puede resolver problemas con cientos de variables
  • Eficiencia: Polinomial en la práctica (aunque exponencial en el peor caso)
  • Robustez: Maneja múltiples tipos de restricciones
  • Base teórica: Fundamentado matemáticamente
Aplicaciones Típicas:
  • Planificación de producción con múltiples productos
  • Problemas de transporte y asignación
  • Optimización de dietas y mezclas
  • Programación de personal y turnos

Método Dual Simplex en Detalle

El método Dual Simplex es una variante complementaria del Simplex que trabaja desde una solución dual factible hacia la factibilidad primal, manteniendo la optimalidad dual en cada iteración.

Dualidad en Programación Lineal:

Cada problema de PL (primal) tiene un problema asociado (dual). El método Dual Simplex es especialmente útil cuando:

  • El problema tiene muchas restricciones del tipo ≥ (minimización)
  • Se requiere análisis de sensibilidad
  • La solución inicial viola restricciones (RHS negativo)
Procedimiento Dual:
  1. Tableau inicial: Con optimalidad dual (Z row no negativa para min)
  2. Verificar factibilidad: ¿Todos los RHS ≥ 0?
  3. Fila saliente: Seleccionar la más negativa en RHS
  1. Columna entrante: Calcular ratios zⱼ/aᵢⱼ (solo aᵢⱼ < 0), elegir mínimo
  2. Pivot y actualizar: Operaciones de fila estándar
  3. Iterar: Hasta factibilidad primal
Diferencia clave: Mientras el Simplex selecciona la columna primero (entrante) y luego la fila (saliente), el Dual Simplex hace lo opuesto: primero la fila (más negativa) y luego la columna (por ratios duales).
Casos de Uso Especiales:
  • Post-optimización: Cuando se agregan restricciones a una solución óptima existente
  • Análisis de sensibilidad: Estudiar cambios en restricciones
  • Problemas de minimización: Con restricciones ≥ (forma natural)
  • Branch and Bound: En algoritmos de programación entera
En esta Aplicación:

Nuestra implementación muestra:

  • Identificación visual de filas con RHS negativo (highlighting rojo)
  • Cálculo explícito de ratios zⱼ/aᵢⱼ para selección de columna
  • Documentación completa de operaciones de fila
  • Convergencia paso a paso hacia factibilidad primal

Algoritmo de Dijkstra en Detalle

El algoritmo de Dijkstra encuentra el camino más corto desde un nodo origen a todos los demás nodos en un grafo con pesos no negativos. Desarrollado por Edsger W. Dijkstra en 1956.

Fundamento:

El algoritmo usa una estrategia greedy (voraz) que mantiene un conjunto de nodos visitados y actualiza iterativamente las distancias mínimas a los nodos no visitados, garantizando optimalidad cuando todos los pesos son no negativos.

Procedimiento:
  1. Inicialización: Distancia al origen = 0, resto = ∞
  2. Cola de prioridad: Usar heap para extraer nodo con distancia mínima
  3. Relajación: Actualizar distancias a vecinos no visitados
  1. Marcar visitado: El nodo actual no se revisará de nuevo
  2. Repetir: Hasta visitar todos los nodos alcanzables
  3. Reconstruir camino: Usar predecesores para obtener ruta óptima
Complejidad: O((V + E) log V) usando heap binario, donde V = vértices y E = aristas
Visualización Interactiva:

Esta aplicación utiliza Vis.js para mostrar el grafo de manera interactiva:

  • Nodos arrastrables y ajustables
  • Camino óptimo resaltado en azul y verde
  • Tabla de distancias a todos los nodos
  • Iteraciones detalladas mostrando nodos visitados/no visitados
Aplicaciones Reales:
  • GPS y navegación: Rutas óptimas en mapas
  • Redes de telecomunicaciones: Enrutamiento de paquetes
  • Logística: Rutas de distribución óptimas
  • Juegos: Pathfinding para personajes
  • Redes sociales: Grados de separación
  • Planificación urbana: Diseño de rutas de transporte

Algoritmo de Kruskal en Detalle

El algoritmo de Kruskal encuentra el Árbol de Expansión Mínima (MST) de un grafo conexo no dirigido, conectando todos los nodos con el menor costo total sin formar ciclos. Desarrollado por Joseph Kruskal en 1956.

Concepto de MST:

Un Minimum Spanning Tree es un subgrafo que:

  • Conecta todos los vértices del grafo original
  • Es un árbol (sin ciclos, con V-1 aristas)
  • Tiene la suma mínima de pesos de aristas
  • Es único si todos los pesos son diferentes
Procedimiento:
  1. Ordenar aristas: Por peso ascendente
  2. Inicializar Union-Find: Cada nodo en su propio conjunto
  3. Iterar aristas: En orden de peso
  1. Verificar ciclo: ¿Los extremos están en el mismo conjunto?
  2. Agregar arista: Si no forma ciclo, incluir en MST y unir conjuntos
  3. Terminar: Al tener V-1 aristas
Complejidad: O(E log E) donde E = número de aristas (dominado por ordenamiento)
Estructura Union-Find:

También llamada Disjoint Set Union (DSU), permite:

  • Find: Determinar a qué conjunto pertenece un elemento (con compresión de ruta)
  • Union: Unir dos conjuntos (con unión por rango/tamaño)
  • Detección de ciclos: Si find(u) == find(v), la arista (u,v) forma ciclo
  • Eficiencia: Operaciones casi constantes O(α(n)) ≈ O(1) en la práctica
Doble Visualización:

Esta aplicación muestra dos grafos con Vis.js:

  • MST final: Solo aristas seleccionadas (verde) con peso total
  • Grafo original: Todas las aristas con indicación de pertenencia al MST
  • Tabla de iteraciones: Aristas aceptadas/rechazadas con razón
  • Aristas ordenadas: Vista completa con estado de selección
Aplicaciones Reales:
  • Redes eléctricas: Cableado con costo mínimo
  • Telecomunicaciones: Tendido de fibra óptica
  • Redes de tuberías: Distribución de agua/gas
  • Diseño de circuitos: Conexiones PCB óptimas
  • Clustering: Análisis de datos y agrupamiento
  • Redes de transporte: Infraestructura vial mínima

Modelo de Transporte

Distribución óptima desde orígenes a destinos

El Modelo de Transporte es un caso especial de programación lineal que optimiza la distribución de un producto homogéneo desde múltiples orígenes (plantas, almacenes) a múltiples destinos (tiendas, ciudades), minimizando el costo total de transporte.

¿Cuándo usar cada método?
Esquina Noroeste
  • Solución rápida inicial
  • Fácil de entender y aplicar
  • No siempre es óptima
  • Buena para empezar otros métodos
Costo Mínimo
  • Prioriza costos bajos
  • Mejor solución que Noroeste
  • Lógica intuitiva: lo más barato primero
  • Rápido y eficiente
Vogel (VAM)
  • Mejor aproximación a óptimo
  • Usa penalizaciones inteligentes
  • Más complejo pero más preciso
  • Recomendado para uso profesional
Estructura del Problema
Formulación Matemática

Minimizar:

Z = Σᵢ Σⱼ cᵢⱼ × xᵢⱼ

Sujeto a:

Σⱼ xᵢⱼ = sᵢ (oferta del origen i) Σᵢ xᵢⱼ = dⱼ (demanda del destino j) xᵢⱼ ≥ 0
Variables del Modelo
  • xᵢⱼ: Cantidad transportada del origen i al destino j
  • cᵢⱼ: Costo unitario de transporte de i a j
  • sᵢ: Oferta disponible en el origen i
  • dⱼ: Demanda requerida en el destino j
  • m: Número de orígenes
  • n: Número de destinos
Comparación de los 3 Métodos
Característica Esquina Noroeste Costo Mínimo Vogel (VAM)
Complejidad ⭐ Baja ⭐⭐ Media ⭐⭐⭐ Alta
Calidad de Solución Básica Buena Excelente
Tiempo de Cálculo Muy rápido Rápido Moderado
Uso Recomendado Aprendizaje inicial Problemas simples Uso profesional
Ejemplo Práctico: Distribución de Energía

Problema: Una empresa energética tiene 4 plantas generadoras que deben abastecer la demanda eléctrica de 4 ciudades. Cada planta tiene capacidad limitada y cada ciudad tiene necesidades específicas. El costo de transporte por millón de KW varía según la ruta.

Ofertas (Plantas):
  • Planta 1: 80 millones KW
  • Planta 2: 30 millones KW
  • Planta 3: 60 millones KW
  • Planta 4: 45 millones KW
Demandas (Ciudades):
  • Cali: 70 millones KW
  • Bogotá: 40 millones KW
  • Medellín: 70 millones KW
  • Barranquilla: 35 millones KW

Objetivo: Determinar cuánta energía debe enviar cada planta a cada ciudad para minimizar el costo total de distribución.

Ventajas del Modelo de Transporte
Eficiente: Aprovecha la estructura especial del problema
Escalable: Funciona bien con muchos orígenes/destinos
Intuitivo: Fácil de entender y explicar
Aplicable: Usado en logística, manufactura, energía

Comparación de Métodos

Característica Gráfico Simplex Dual Simplex
Número de variables Exactamente 2 2 a n 2 a n
Complejidad visual Baja Media Media-Alta
Mejor para aprender ✅ Excelente ✅ Muy bueno ⚠️ Avanzado
Velocidad (problemas grandes) N/A Rápido Rápido
Tipo de restricciones ideal ≤, ≥, = ≤ (max), ≥ (min) ≥ (min), análisis
Visualización paso a paso ✅ Gráfica ✅ Tableau ✅ Tableau + ratios

Características de esta Aplicación

Enfoque Educativo:
  • Visualización paso a paso de cada iteración
  • Explicación de operaciones realizadas
  • Highlighting de elementos clave (pivotes, RHS negativo)
  • Interfaz intuitiva con colores distintivos
Implementación Técnica:
  • Backend: Flask + NumPy (algoritmos manuales)
  • Frontend: Bootstrap 5 + CSS personalizado
  • Gráficos: Matplotlib para método gráfico
  • Tipografía: Google Fonts (Poppins/Inter)
Sistema de Diseño:
  • Colores distintivos por método
  • Modo oscuro completo
  • Animaciones suaves
  • Diseño responsivo
Validaciones:
  • Parsing robusto de restricciones
  • Detección de problemas no factibles
  • Manejo de casos especiales
  • Mensajes de error informativos

Método Simplex Dos Fases

Solución especializada para restricciones complejas

¿Qué es el Método Dos Fases?

Una técnica avanzada del Simplex diseñada para problemas con restricciones ≥ o =, donde no existe una solución básica factible inicial obvia.

¿Cuándo usar este método?
Restricciones ≥

Cuando tienes restricciones de tipo "mayor o igual"

Restricciones =

Cuando existen restricciones de igualdad exacta

Restricciones Mixtas

Combinación de ≤, ≥ y = en el mismo problema

Las Dos Fases del Algoritmo
1

FASE I

Búsqueda de Factibilidad
  • Objetivo: Encontrar solución básica factible
  • Minimizar: W = Σ(artificiales)
  • Éxito: W = 0
  • Fracaso: W > 0 (infactible)
2

FASE II

Optimización del Objetivo
  • Objetivo: Optimizar función original
  • Optimizar: Z (MAX o MIN)
  • Base inicial: Solución de Fase I
  • Resultado: Solución óptima
Ejemplo Práctico
Problema Original 
Maximizar: Z = 3x₁ + 5x₂

Sujeto a:
  4x₁ + x₂ ≥ 4
  -x₁ + 2x₂ ≥ 2
  x₂ ≤ 3
  x₁, x₂ ≥ 0
Solución Encontrada
Fase I: W = 0 ✓ (Factible)
Fase II: x₁ = 4, x₂ = 3
Valor óptimo: Z = 27
¿Por qué Dos Fases y no Big M?
Ventajas del Método Dos Fases
  • Mayor precisión numérica
  • No depende de elegir M correctamente
  • Detección clara de infactibilidad
  • Ideal para implementación computacional
Método Big M
  • Una sola fase (más simple conceptualmente)
  • Requiere elegir M suficientemente grande
  • Puede tener problemas de precisión
  • Mejor para resolución manual
Situaciones Especiales
Problema Infactible

Si al finalizar Fase I resulta W > 0, el problema no tiene solución. Las restricciones son inconsistentes entre sí.

Problema No Acotado

Se detecta en Fase II cuando no existen ratios positivos para la columna entrante. La función objetivo puede crecer indefinidamente.

¿Listo para resolver tu problema de PL?

Método Gráfico Método Simplex Dual Simplex Simplex Dos Fases Modelo de Transporte Dijkstra Kruskal
Método Gráfico Método Simplex Dual Simplex Simplex Dos Fases Modelo de Transporte Dijkstra Kruskal

Información Académica

Universidad

Universidad Tecnológica de Pereira

UTP - Colombia
Materia

Investigación de Operaciones

Prof. Bibiana Patricia Arias Villada
Desarrollador

José Miguel Herrera Gutiérrez

Proyecto Investigacion De Operaciones 2025
Stack Tecnológico:
Python 3.13 Flask 3.1 NumPy Bootstrap 5 Matplotlib Vis.js 9.1.9
Algoritmos Implementados:
  • Método Gráfico con Matplotlib
  • Simplex Manual con Tableau
  • Dual Simplex con Ratios
  • Simplex Dos Fases con Artificiales
  • Modelo de Transporte (3 métodos)
  • Dijkstra con Visualización Vis.js
  • Kruskal MST con Union-Find
Volver al Inicio Ver Ejemplos