Solucionador de Programación Lineal

Solucionador de Programación Lineal

El Solucionador de Programación Lineal es una calculadora en línea que encuentra el máximo o mínimo de una función objetivo lineal sujeta a un sistema de desigualdades o igualdades lineales. Utiliza el método simplex (variante de la Gran M) para que las restricciones <=, >= y = puedan mezclarse libremente, y para problemas de 2 variables dibuja un gráfico interactivo de la región factible con cada vértice y el óptimo resaltados.

¿Qué es la Programación Lineal?

Un problema de programación lineal (PL) plantea:

El conjunto de puntos que satisfacen cada restricción se llama región factible, un poliedro convexo. El Teorema Fundamental de la Programación Lineal establece que si la PL tiene un óptimo finito, este se alcanza en un vértice (punto extremo) de este poliedro. Es por eso que el método simplex —que camina de vértice en vértice— es tan eficaz.

Cómo funciona el método simplex

Comenzando desde un vértice factible, el método simplex mejora repetidamente el objetivo pivotando hacia un vértice vecino con un mejor valor. La mecánica:

1. Forma estándar: convierte la PL a máx c^Tx sujeto a Ax = b, x ≥ 0. Para restricciones <=, añade variables de holgura; para >=, resta un excedente y añade una artificial con una gran penalización −M; para igualdades, añade una artificial.
2. Tabla inicial: la base consiste en variables de holgura y artificiales, lo que da un vértice inicial obvio.
3. Variable de entrada: elija la variable no básica con el costo reducido positivo más grande \( c_j - z_j \). Si no existe tal variable, la solución actual es óptima.
4. Variable de salida: de la columna de entrada, realice la prueba de razón mínima — divida el RHS de cada fila por su entrada positiva en la columna de entrada y elija la fila con la razón más pequeña. Si no existe ninguna entrada positiva, la PL es no acotada.
5. Pivote: use la eliminación gaussiana para hacer que la columna de entrada sea un vector unitario, con un 1 en la fila de salida.
6. Repita hasta que se cumpla el criterio de parada.

Si alguna variable artificial permanece en la base con un valor positivo al terminar, la PL original es no factible.

Método gráfico (para 2 variables)

Para problemas de dos variables, la región factible es un polígono convexo 2D. Dado que el óptimo siempre está en un vértice, enumerar cada vértice y evaluar el objetivo allí es suficiente para resolver el problema. Esta calculadora realiza esa enumeración intersectando cada par de límites de restricción, conservando solo las intersecciones que satisfacen todas las demás restricciones y ordenándolas en sentido antihorario para la visualización.

Sintaxis de entrada

Escriba el objetivo en la primera línea, luego una restricción por línea. Los nombres de las variables pueden ser cualquier identificador (x, y, x1, beneficio…). Los operadores son <=, >= y =. La no negatividad se puede escribir como x, y >= 0 como atajo.

Las líneas en blanco y los comentarios que comienzan con # se ignoran. El solucionador acepta hasta 8 variables de decisión y 20 restricciones.

Ejemplo resuelto

Considere un taller de muebles que fabrica mesas y sillas. Cada mesa genera \\$3 de beneficio y requiere 1 unidad de madera y 2 unidades de mano de obra. Cada silla genera \\$5 de beneficio y requiere 1 unidad de madera, 1 unidad de mano de obra y 3 unidades de barniz. Disponible: 10 de madera, 16 de mano de obra, 18 de barniz. Con x = mesas e y = sillas, la PL es:

La región factible es un pentágono. Evaluando Z en cada vértice:

Por lo tanto, el taller debe fabricar 6 mesas y 4 sillas para un beneficio máximo de \\$38. Las restricciones de madera y mano de obra son activas (equivalen a su RHS en el óptimo); el barniz tiene una holgura de 0 (también activa en este caso), lo que significa que los tres recursos se agotan.

Problemas comunes y qué detecta el solucionador

Aplicaciones

• Mix de productos y planificación de producción — cuántos de cada producto fabricar para obtener el máximo beneficio bajo límites de recursos.
• Problemas de dieta y mezcla — minimizar el costo de una dieta o alimento que aún cumpla con los mínimos nutricionales.
• Transporte y asignación — minimizar los costos de envío cuando la oferta y la demanda deben equilibrarse.
• Optimización de cartera — maximizar el rendimiento esperado bajo restricciones de riesgo o exposición (linealizadas).
• Flujo de red — el flujo máximo y el flujo de costo mínimo se reducen a PL con matrices de coeficientes totalmente unimodulares.
• Programación de horarios — cuadrantes de personal con requisitos de turno y límites de horas totales.

Cómo usar esta calculadora

1. Escriba su PL en el cuadro de texto. La primera línea debe comenzar con Maximize o Minimize. Cada línea siguiente es una restricción, una por línea.
2. Use el atajo x, y >= 0 para declarar la no negatividad de todas las variables enumeradas a la vez.
3. Haga clic en Resolver problema de PL. El solucionador informa el valor óptimo Z, los valores óptimos de cada variable de decisión, una lista de restricciones activas y, para PL de 2 variables, un gráfico interactivo de la región factible.
4. Pase el cursor por un vértice en el gráfico para ver sus coordenadas y el valor Z. El óptimo está resaltado con una estrella.
5. Revise las tablas simplex para ver cada pivote y rastrear cómo el método mejora Z. La columna de entrada se resalta en ámbar; la fila de salida en rojo.

Preguntas frecuentes

¿Qué es un problema de programación lineal?

Un problema de programación lineal (PL) busca el máximo o mínimo de una función objetivo lineal sobre un conjunto de variables de decisión que satisfacen un sistema de desigualdades o igualdades lineales. El conjunto factible es un poliedro convexo, y el óptimo siempre se alcanza en uno de sus vértices — el hecho clave que explota el método simplex.

¿Cómo funciona el método simplex?

El método simplex recorre los vértices del poliedro factible. Cada paso (un "pivote") intercambia una variable en la base por otra, moviéndose a un vértice vecino con un objetivo estrictamente mejor. El algoritmo se detiene cuando ningún pivote puede mejorar Z — el vértice actual es entonces el óptimo. Esta herramienta utiliza la variante de la Gran M para que se puedan mezclar restricciones <=, >= y =.

¿Qué es la región factible?

La región factible es el conjunto de todos los valores de las variables que satisfacen cada restricción simultáneamente. Para 2 variables es un polígono convexo 2D; para n variables es un poliedro n-dimensional. Un poliedro vacío significa que la PL es no factible; un poliedro que se extiende infinitamente en la dirección de mejora significa que la PL es no acotada.

¿Qué significa "no acotado" en programación lineal?

Una PL es no acotada cuando la región factible se estira hasta el infinito en una dirección donde el objetivo sigue mejorando. Por ejemplo, Maximizar x sujeto solo a x ≥ 0 no tiene un máximo finito. Las PL del mundo real que devuelven un resultado no acotado suelen revelar una restricción faltante, a menudo un límite superior en un recurso o variable.

¿Qué significa "óptimos alternativos"?

Los óptimos alternativos ocurren cuando más de un punto alcanza el mismo mejor valor objetivo. Geométricamente, el objetivo es paralelo a una arista activa del polígono, por lo que cada punto a lo largo de esa arista —y cada combinación convexa de sus extremos— es óptimo. El solucionador señala esto cuando cualquier variable de decisión no básica tiene un costo reducido de cero al finalizar.

¿Cuántas variables y restricciones acepta el solucionador?

Hasta 8 variables de decisión y 20 restricciones. El gráfico interactivo de la región factible se dibuja solo para problemas de 2 variables; con 3 o más variables seguirá obteniendo la solución simplex numérica completa, tablas paso a paso e informe de restricciones activas.

Lectura adicional

• Programación lineal — Wikipedia
• Algoritmo símplex — Wikipedia
• Método de la Gran M — Wikipedia
• Dualidad en optimización — Wikipedia

Operaciones matemáticas avanzadas:

• Calculadora de Matriz de Adyacencia Nuevo
• Calculadora de Antilogaritmo Popular
• Calculadora de funciones Beta
• Calculadora de Coeficientes Binomiales
• Calculadora de distribución binomial
• Calculadora Bit a Bit
• Simplificador de Álgebra Booleana Nuevo
• Calculadora del Teorema del Límite Central Popular
• Calculadora del Teorema Chino del Resto
• Calculadora de Combinación Popular
• Calculadora de Función de Error Complementaria
• Calculadora de Números Complejos Popular
• Calculadora de fracciones continuas
• Calculadora de Desarreglo (Subfactorial)
• Calculadora de Camino más Corto de Dijkstra
• Calculadora de Entropía
• Calculadora de función error
• Calculadora de la Función Totiente de Euler
• Calculadora de decaimiento exponencial
• Calculadora de Crecimiento Exponencial de Alta Precisión
• Calculadora de Integral Exponencial
• Calculadora de Exponentes (Alta Precisión)
• Calculadora del Algoritmo Euclidiano Extendido
• Calculadora de Factorial
• Calculadora de Función Gamma
• Calculadora de Proporción Áurea Popular
• Calculadora de Coloración de Grafos Nuevo
• Validador de secuencia de grados de grafo
• Calculadora de Orden en Teoría de Grupos Nuevo
• Calculadora de Media Vida
• Verificador de Camino Hamiltoniano Nuevo
• Calculadora de Inclusión-Exclusión Nuevo
• Solucionador de Mapa de Karnaugh (K-Map) Nuevo
• Solucionador de Programación Lineal Nuevo
• Calculadora de Estado Estacionario de Cadena de Markov
• Calculadora de Árbol de Expansión Mínimo
• Calculadora de Exponenciación Modular Nuevo
• Calculadora del Inverso Multiplicativo Modular
• Calculadora de Distribución Binomial Negativa Popular
• Calculadora de Flujo de Red (Flujo Máximo) Nuevo
• Calculadora de Tasa de Crecimiento Porcentual Popular
• Calculadora de Permutación Popular
• Calculadora de Permutaciones con Repetición Nuevo
• Calculadora del Principio del Palomar
• Verificador de Grafo Planar Nuevo
• Calculadora de Distribución de Poisson
• Calculadora de Raíces de Polinomios con Pasos Detallados
• Calculadora de Raíz Primitiva
• Calculadora de probabilidad
• Calculadora de Distribución de Probabilidad
• Calculadora de Proporciones
• Calculadora de Fórmula Cuadrática
• Calculadora de Anillos y Cuerpos Nuevo
• Calculadora de Redondeo Nuevo
• Calculadora Científica Popular
• Calculadora de notación científica Popular
• Calculadora de Teoría de Conjuntos
• Calculadora de Cifras Significativas Nuevo
• Solucionador del Problema del Matrimonio Estable Nuevo
• Calculadora de Números de Stirling
• Calculadora de Suma de Cubos
• Calculadora de suma de números enteros positivos
• Calculadora de Suma de Cuadrados
• Calculadora de Ordenación Topológica Nuevo
• Solucionador del Viajante de Comercio (TSP) Nuevo
• Generador de Tabla de Verdad
• Generador de Diagrama de Venn (3 Conjuntos)