Resolver un sistema te dice qué valores son posibles; optimizar obliga a decidir cuál de los posibles conviene más.
La programación lineal traduce una decisión con recursos limitados a variables, restricciones y una función objetivo. El algoritmo Simplex recorre soluciones básicas factibles mediante pivotes hasta identificar una solución óptima bajo las condiciones del modelo.
📷 Antes de comenzar
Una empresa dispone de horas de máquina y materia prima limitadas y quiere maximizar la utilidad. ¿Qué elemento adicional necesita un modelo de programación lineal además de las restricciones?
Objetivo didáctico
Al terminar esta lección podrás formular un problema de programación lineal, convertirlo a una forma operable, interpretar geométricamente sus soluciones y aplicar los pasos básicos del algoritmo Simplex para resolver una versión de optimización del caso construido durante el proyecto.
Introducción
En la lección anterior resolviste un sistema lineal derivado de tu caso. Ese sistema buscaba valores que satisficieran ciertas ecuaciones. Ahora añadiremos una decisión: entre todas las soluciones permitidas por un conjunto de restricciones, ¿cuál produce el mayor beneficio o el menor costo?
La programación lineal sirve cuando las variables, la función objetivo y las restricciones pueden expresarse mediante relaciones lineales. El modelo no “descubre” por sí solo qué significa una buena decisión; esa parte la define quien formula el problema al elegir la función objetivo y las restricciones.
Para estudiantes que inician la ingeniería, conviene separar tres capas. Primero se formula el problema en lenguaje del caso. Después se transforma a una representación matemática operable. Finalmente se ejecuta el algoritmo y se interpreta el resultado. Saltar directamente a una tabla de Simplex suele convertir el procedimiento en una serie de movimientos sin significado.
Desarrollo del tema
Problemas de programación lineal: variables, objetivo y restricciones
Un problema de programación lineal parte de variables de decisión: cantidades que el modelo puede elegir. Si una empresa decide cuántas unidades producir de dos productos, esas cantidades pueden representarse mediante x₁ y x₂. El significado debe escribirse antes que las ecuaciones.
La función objetivo asigna un valor a cada decisión factible. Puede expresar utilidad, costo, tiempo, desperdicio u otra cantidad lineal que quieras maximizar o minimizar. Por ejemplo, si cada unidad del producto A aporta 5 unidades de utilidad y cada unidad de B aporta 3, una función objetivo posible sería maximizar 5x₁+3x₂.
Las restricciones describen los límites del problema: capacidad, presupuesto, tiempo o disponibilidad. También suelen aparecer condiciones de no negatividad cuando las variables representan cantidades que no tienen sentido como valores negativos.
La primera comprobación es semántica: cada coeficiente debe conservar sus unidades y su significado. Una ecuación puede estar bien escrita desde el punto de vista algebraico y representar mal el problema si mezcla cantidades incompatibles.
💡 Solución factible
Asignación de valores a las variables de decisión que satisface simultáneamente todas las restricciones del modelo. El algoritmo solo debe comparar soluciones que permanezcan dentro de la región factible.
Aplica: toma una restricción real de tu caso —tiempo, memoria, capacidad, costo o cantidad disponible— y conviértela en una desigualdad lineal. Después explica qué representa cada coeficiente y qué unidad conserva.
Forma estándar y forma de holgura
Los textos de programación lineal utilizan distintas convenciones para la forma estándar. Por eso no basta memorizar una plantilla: debes verificar qué convención adopta la fuente o el algoritmo que estés usando. En esta lección trabajaremos con problemas de maximización con variables no negativas y restricciones lineales que pueden transformarse mediante variables de holgura.
La guía original de esta asignatura usa la expresión “forma distensionada”. La literatura consultada utiliza de manera estándar forma de holgura —slack form— para la representación que introduce variables adicionales destinadas a convertir restricciones apropiadas en igualdades. En adelante se usa “forma de holgura” y se conserva el término de la guía solo como equivalencia documental.
Si una restricción tiene la forma 2x₁+x₂≤10, puedes introducir una variable de holgura s no negativa y escribir 2x₁+x₂+s=10. La variable s representa recurso disponible que no fue utilizado. Si s vale cero, la restricción está activa en esa solución.
Esta transformación prepara una base inicial sencilla en ciertos problemas. Las variables originales suelen empezar como no básicas y las de holgura como básicas, siempre que el punto inicial resultante sea factible.
🔄 Simulador de estados
Recorre el algoritmo como una sucesión de estados. El objetivo es identificar qué cambia y qué debe conservarse.
Prueba tú: toma dos restricciones de tu modelo y añade variables de holgura cuando corresponda. Interpreta el valor de cada holgura como una cantidad del caso, no solo como una letra nueva.
Interpretación geométrica y dualidad
Cuando un problema tiene dos variables, cada restricción lineal delimita una región del plano. La intersección de todas las restricciones forma la región factible. En problemas lineales acotados con solución óptima, el óptimo puede encontrarse en un vértice de esa región.
Esta interpretación ayuda a entender el Simplex: el algoritmo no revisa todos los puntos posibles. Se desplaza entre soluciones básicas factibles asociadas con vértices, buscando mejorar el valor de la función objetivo de acuerdo con una regla de pivote.
La dualidad asocia a un problema lineal otro problema relacionado. En una lectura introductoria, el primal pregunta cómo asignar recursos para lograr un objetivo, mientras el dual puede interpretarse como una manera de asignar valores a las restricciones o recursos para establecer una cota sobre el objetivo.
No necesitas demostrar el teorema de dualidad en esta lección. Sí debes reconocer que primal y dual describen el mismo problema desde perspectivas complementarias y que, bajo condiciones apropiadas, sus valores óptimos se relacionan de manera precisa.
Tabla 1: Tres representaciones que conviene distinguir antes de ejecutar Simplex.
| Representación | Qué conserva | Para qué se usa |
|---|---|---|
| Forma estándar | Objetivo y restricciones bajo una convención explícita. | Normalizar el modelo antes del algoritmo. |
| Forma de holgura | Equivalencia de las restricciones al introducir holguras. | Construir una base y expresar cambios de variables básicas. |
| Problema dual | Una perspectiva complementaria sobre restricciones y objetivo. | Interpretar cotas, precios implícitos y optimalidad. |
Nota: síntesis didáctica basada en Vanderbei y Chvátal.
Decide: dibuja una versión de dos variables de tu modelo si es posible. Identifica al menos dos vértices factibles y evalúa la función objetivo en ellos. Usa el dibujo para anticipar qué debería buscar el algoritmo.
Pivotaje, inicialización y cuerpo del algoritmo Simplex
El pivotaje cambia qué variables son básicas y cuáles no básicas. En términos geométricos, puede mover la solución desde un vértice factible hacia otro vértice adyacente. La variable que entra a la base se elige porque puede mejorar el objetivo; la variable que sale se determina para no violar la factibilidad.
En un problema introductorio con una base inicial evidente, puedes iniciar con las variables de decisión en cero y las holguras iguales a los recursos disponibles. Esta estrategia solo funciona si ese punto satisface las restricciones. Cuando no existe una base factible inmediata se requieren procedimientos de inicialización más generales.
El cuerpo del algoritmo repite una lógica: comprobar si existe una dirección de mejora; elegir variable entrante; determinar cuánto puede aumentar sin violar restricciones; elegir variable saliente; pivotar; y repetir. Lo importante no es memorizar una tabla sino conservar equivalencia, factibilidad y mejora del objetivo.
El Simplex tiene un comportamiento excelente en muchos problemas prácticos aunque su peor caso teórico puede ser exponencial. Para esta asignatura, esa observación sirve para distinguir entre “un algoritmo que funciona bien en la práctica” y “un algoritmo con garantía polinomial en el peor caso”, sin profundizar todavía en análisis de complejidad.
⏭ Revelador secuencial
Avanza una decisión a la vez y comprueba qué información necesitas antes de pivotar.
📷 Control de comprensión
Durante una iteración de Simplex, ¿qué condición debe proteger la elección de la variable que sale de la base?
Aplica: en un ejemplo pequeño de dos variables, ejecuta un pivote e identifica con palabras qué variable entra, cuál sale y qué restricción limita el movimiento. Comprueba que la nueva solución siga siendo factible antes de continuar.
Conclusión
Programar linealmente significa traducir una decisión a variables, objetivo y restricciones coherentes. La forma de holgura introduce variables que representan recurso no utilizado; la geometría ayuda a entender las soluciones básicas; la dualidad ofrece una perspectiva complementaria; y el Simplex cambia de base mediante pivotes que conservan factibilidad mientras buscan mejorar el objetivo.
La última lección retomará todas las entidades y relaciones construidas hasta ahora para representarlas como grafos o árboles. Esa representación permitirá estudiar vecindad, conectividad y recorridos, y servirá como cierre integrador del proyecto.
🔭 Para seguir aprendiendo
- ¿Qué elementos de tu caso pueden convertirse en nodos y qué relación concreta justificaría dibujar una arista entre dos de ellos?
Actividad de aprendizaje autónoma
Etapa 7 · Formula y resuelve una versión de optimización del caso. Retoma las variables y restricciones acumuladas en E5–E6. Selecciona una decisión del mismo caso que pueda expresarse mediante una función objetivo lineal y restricciones lineales.
- De dónde vienes. Explica qué variables, ecuaciones o restricciones de E5–E6 reutilizas y qué ajuste necesitas para convertirlas en un problema de optimización.
- Formula. Define las variables de decisión, su significado y unidades; escribe la función objetivo y las restricciones de factibilidad.
- Transforma. Expresa el problema bajo una convención estándar y construye la forma de holgura cuando corresponda.
- Resuelve. Ejecuta el procedimiento Simplex en un caso pequeño y documenta al menos un pivote con variable entrante, variable saliente y criterio de factibilidad.
- Interpreta. Traduce la solución óptima al lenguaje del caso y señala qué restricciones quedan activas o con holgura.
- Qué decides. Justifica qué cantidad optimizas y por qué esa función objetivo representa mejor el problema que una alternativa razonable.
- Qué documentas. Registra fuentes y cualquier consulta a inteligencia artificial, especificando qué propuesta aceptaste o descartaste y cómo verificaste el resultado.
🗂 Planifica tu etapa
✔ Evidencia de logro
- Trazabilidad desde E5–E6 hasta el modelo de programación lineal.
- Variables, función objetivo, restricciones y no negatividad correctamente declaradas.
- Transformación a forma operable y al menos un pivote Simplex documentado.
- Interpretación de la solución y de la holgura de las restricciones.
- Justificación de la función objetivo y revisión argumentada de la etapa anterior.
- Registro de fuentes y contraste de cualquier consulta a sistemas de inteligencia artificial.
Si una solución tiene el mejor valor numérico pero la función objetivo no representa realmente la prioridad de tu caso, ¿puede considerarse una buena decisión de ingeniería? Explica qué parte del modelo revisarías.
Referencias bibliográficas
- Chvátal, V. (1983). Linear programming. Macmillan.
- Vanderbei, R. J. (2020). Linear programming: Foundations and extensions (5th ed.). Springer.