Objetivos didácticos
¿Y cuando el problema tiene tantas variables que ya no se puede dibujar? Este laboratorio continúa donde termina Optimización lineal: allí el óptimo se encontraba mirando la región factible, y aquí se construye la maquinaria que lo encuentra sin verla — el método símplex — y después se le da la vuelta al problema entero para llegar a los precios sombra y al problema dual. El mismo taller de mesas y sillas atraviesa las 23 primeras salas, y siempre acaba dando 36 €; la última aplica todo a un problema completo de tres productos, como los de examen. Pensado para Universidad.
Qué se aprende
- Repasar qué es un problema de optimización lineal, qué es la región factible y por qué el óptimo está siempre en un vértice (sala 1).
- Dar la vuelta a un problema para que encaje en el método: minimizar como maximizar, y ≥ como ≤ (salas 2 y 5).
- Poner un problema en forma estándar con variables de holgura y de exceso, y distinguir variables básicas de no básicas (salas 3, 4 y 6).
- Entender por qué no sirve probar todos los vértices: su número crece de forma exponencial con el tamaño del problema (sala 7).
- Montar la tabla del símplex a partir de un enunciado y leerla: qué hay en cada fila, en cada columna y en la fila Z (sala 8).
- Elegir la columna que entra y la fila que sale, y ver lo que eso significa sobre el dibujo: un salto de un vértice a su vecino (salas 9 y 10).
- Aplicar el método de Gauss-Jordan a la tabla, primero viéndolo cálculo a cálculo y después haciéndolo entero, fila a fila (salas 11 y 13), decidiendo antes por su cuenta quién entra y quién sale (sala 12).
- Ver el símplex como lo que es —un paseo por los vértices que nunca retrocede— y comprobar que el mismo método funciona igual sobre un poliedro de tres variables (salas 14 y 15).
- Resolver un problema completo de principio a fin sin ayuda (sala 16).
- Interpretar los precios sombra: cuánto vale una unidad más de cada recurso y hasta dónde vale (sala 17).
- Construir el problema dual, entender su sentido económico y comprobar que su solución ya estaba en la tabla final del símplex (salas 18 a 23).
- Contestar los apartados de análisis de un problema completo leyendo la tabla final: holguras y recursos agotados, precios sombra, dualidad fuerte, si conviene comprar un recurso, y por qué un producto no se fabrica y a partir de qué beneficio compensaría (sala 24).
Ideas matemáticas clave
- Toda restricción
≤se convierte en igualdad sumando una variable de holgura; toda≥, restando un exceso. Ninguna de esas variables puede ser negativa. - En forma estándar hay más variables que grados de libertad: en cada vértice, tantas variables como variables originales valen cero. Ésas son las no básicas; las demás forman la base.
- Cada iteración del símplex cambia la base: una variable entra (la de coeficiente más negativo en la fila Z) y otra sale (la de razón mínima). En el cruce de esa fila con esa columna está el pivote.
- El símplex no prueba todos los vértices: camina de uno a otro mejorando siempre, y por eso termina. Como la región es convexa, un vértice mejor que todos sus vecinos es el mejor de todos — no hay máximos locales que no sean globales.
- La fila Z de la tabla final no solo da el óptimo: sus coeficientes bajo las holguras son los precios sombra de los recursos, y son también la solución del dual.
- El problema dual se construye con reglas mecánicas: una variable dual por restricción, una restricción dual por variable, máximo por mínimo, y la matriz de coeficientes traspuesta. Los términos independientes y los coeficientes del objetivo intercambian su papel.
- Dualidad débil: cualquier solución factible del primal vale menos que cualquier solución factible del dual. Dualidad fuerte: en el óptimo coinciden. Holgura complementaria: si un recurso sobra su precio es 0, y si su precio es positivo ese recurso está agotado.
- Bajo una variable no básica, la fila Z final da su coste reducido: lo que valen a precio sombra los recursos que consume una unidad, menos lo que deja. Es lo que bajaría Z por cada unidad forzada, y esa variable empieza a compensar cuando su coeficiente en el objetivo sube en esa cantidad. Que una variable entre en la base en una iteración no garantiza que esté en el óptimo.
Antes de empezar
Conviene haber hecho Optimización lineal, o al menos saber dibujar una región factible y encontrar el óptimo mirando el dibujo: la sala 1 lo repasa deprisa, pero no lo enseña desde cero.
Contenidos por salas
Sala 1 · Lo que hace falta saber
Repaso rápido de lo que trae el laboratorio anterior, con enlace directo a él por si hace falta hacerlo antes: las tres piezas de un problema lineal (variables de decisión, función objetivo y restricciones), el taller de mesas y sillas que va a atravesar todo el laboratorio y su región factible dibujada, con el óptimo en (2, 6) y Z = 36.
Tareas para el alumno
- Identificar cuál de cuatro problemas no es lineal.
- Definir qué es la región factible y qué forma puede tener.
- Recordar dónde se alcanza siempre el óptimo y cuánto vale en el taller.
Sala 2 · Darle la vuelta al problema
El método que viene solo sabe maximizar y solo entiende ≤. Se ven las dos vueltas de tuerca que dejan cualquier problema listo: minimizar W es maximizar −W (el punto óptimo no se mueve, solo cambia el signo del valor), y una restricción ≥ se convierte en ≤ multiplicando por −1.
Tareas para el alumno
- Convertir un problema de minimizar en uno de maximizar y decir cuánto vale el nuevo óptimo.
- Cambiar el sentido de una desigualdad y comprobar qué pasa con los coeficientes.
Sala 3 · La holgura tiene nombre
El hueco que queda arriba de cada barra de recurso —ya visto en el laboratorio anterior— recibe su nombre: variable de holgura. Las barras se mueven con el punto y cada una enseña su holgura como un número, h₁, h₂ y h₃.
Tareas para el alumno
- Calcular la holgura de cada recurso en un plan concreto.
- Reconocer qué significa que una holgura valga 0.
Sala 4 · La forma estándar
Una máquina no entiende un ≤: solo sabe resolver igualdades. Cada restricción se convierte en igualdad sumándole su propia variable de holgura, y se exige que todas las variables —también las holguras— sean ≥ 0. El taller entero queda escrito en forma estándar.
Tareas para el alumno
- Escribir la forma estándar de una restricción concreta.
- Decir cuántas variables tiene el problema una vez añadidas las holguras.
Sala 5 · Estandarizar un problema de minimización
El caso incómodo: un problema de dieta con restricciones ≥. El hueco no se puede sumar —quedaría en el lado equivocado—, así que se resta una variable de exceso; y como al restar el origen deja de servir de arranque, aparecen las variables artificiales.
Tareas para el alumno
- Convertir una restricción ≥ en igualdad con exceso.
- Explicar por qué hace falta una variable artificial y qué papel juega.
Sala 6 · Cinco diales, dos manos
El taller tiene 5 variables (x, y, h₁, h₂, h₃) pero solo 2 grados de libertad: en cuanto se fijan x e y, las tres holguras quedan determinadas. Arrastrando el punto se ven moverse los cinco diales a la vez, y en cada vértice hay exactamente dos variables valiendo 0 —las no básicas— frente a las tres que forman la base.
Tareas para el alumno
- Arrastrar el punto y observar cómo se mueven los cinco valores a la vez.
- Contar cuántas variables valen 0 en un vértice y decir cuáles forman la base.
Sala 7 · ¿Y si las probamos todas?
La idea obvia —mirar todas las esquinas— se tumba con un deslizador: el número de soluciones básicas es el número combinatorio C(n+m, m), y pasa de 10 a más de cien mil billones al crecer el problema, con el tiempo de cálculo al lado. Después de eso aparece Dantzig y el método símplex, con su idea de caminar de vértice en vértice.
Tareas para el alumno
- Calcular cuántos vértices hay que probar para n = 4 y m = 3.
- Estimar por órdenes de magnitud el caso n = m = 25.
- Explicar por qué basta con parar cuando ningún vecino mejora.
Sala 8 · La tabla del símplex
El enunciado del taller, formalizado con todos los coeficientes a la vista, y su tabla al lado: una fila por restricción, una columna por variable, la fila Z abajo con los coeficientes del objetivo cambiados de signo y la columna de la derecha con los términos independientes. Los coeficientes de las variables principales van en azul en el enunciado y en la tabla, para que se vea que son los mismos números; las holguras forman la matriz identidad.
Tareas para el alumno
- Decir qué representa la última columna de la tabla.
- Leer el valor de Z en la tabla inicial.
- Montar entera la tabla de un problema nuevo, con sus 15 casillas.
Sala 9 · ¿Quién entra?
La fila Z dice cuánto crece el beneficio por cada unidad de cada variable, y por eso entra la columna con el coeficiente más negativo. Se explica además qué significa que una variable entre y otra salga de la base. Dos botones hacen caminar el punto durante dos segundos desde el origen hasta el vértice vecino, con la recta de nivel siguiéndolo y una barra de beneficio subiendo.
Tareas para el alumno
- Elegir qué columna entra en la tabla inicial del taller.
- Calcular cuánto crece Z por cada unidad de y.
- Calcular cuánto sube el beneficio al llegar al vértice (0, 6).
Sala 10 · ¿Hasta dónde puedes avanzar?
El test de la razón mínima, con las dos razones en color —naranja la fila que sale, azul la que no— en el texto y en las mismas casillas de la tabla. Las barras de holgura se llenan mientras el punto avanza y la que llega al límite enseña que su holgura vale 0. En el cruce de la fila que sale con la columna que entra está el pivote, marcado con un anillo.
Tareas para el alumno
- Decidir qué variable saldría si entrase la columna de x.
- Explicar qué pasaría tomando la razón mayor en vez de la menor.
Sala 11 · Método de Gauss
Los tres pasos de Gauss-Jordan, primero explicados con una animación sobre un ejemplo pequeño y ajeno al taller: cada paso espera cuatro segundos para que dé tiempo a leerlo y luego escribe una línea por casilla con la cuenta entera, rellenando la tabla a la vez. Al pulsar «Lo entiendo» la explicación desaparece y el alumno hace la primera iteración del taller guiado: señalar el pivote, dividir su fila y eliminar las demás, una por paso.
Tareas para el alumno
- Ver el método entero, cálculo a cálculo, y pulsar «Lo entiendo».
- Señalar el pivote pinchando en la tabla.
- Dividir la fila del pivote y completar cada una de las demás filas.
Sala 12 · La segunda iteración: ¿quién entra y quién sale?
Aquí ya no se le da nada hecho: con la tabla girada delante, el alumno decide él solo la segunda iteración aplicando las dos reglas. Al terminar, el punto salta de (0, 6) a (2, 6) en una animación de dos segundos con el beneficio subiendo de 30 a 36.
Tareas para el alumno
- Elegir la columna que entra mirando la fila Z.
- Calcular las dos razones que compiten.
- Decidir qué variable sale de la base.
Sala 13 · Termina la segunda iteración
El mismo giro guiado de la sala 11, ahora con pivote 3 y con fracciones de verdad, que hay que escribir con barra y sin decimales. Al acabar, la fila Z se queda sin números negativos: el símplex para y la tabla dice x = 2, y = 6, Z = 36. Se apunta de paso a los 0, 3, 1 de las holguras como anticipo del bloque de precios sombra.
Tareas para el alumno
- Señalar el pivote de la segunda iteración.
- Dividir la fila del pivote escribiendo las fracciones.
- Completar las filas restantes y la fila Z.
Sala 14 · El paseo por las esquinas
Las dos iteraciones juntas: el recorrido (0,0) → (0,6) → (2,6) sobre el dibujo, con la tabla de cada parada al lado y un termómetro del beneficio que sube 0 → 30 → 36. La idea que se quiere dejar clara es que Z nunca baja y que los vértices son finitos, así que el método tiene que parar.
Tareas para el alumno
- Explicar por qué el símplex termina siempre.
- Justificar por qué no puede quedarse en un máximo local peor que el global.
Sala 15 · Con tres variables
El mismo método sobre un poliedro de tres variables que se puede girar con el ratón, con los ejes x, y, z dibujados con punta de flecha desde el vértice (0,0,0) y la tabla del símplex siempre al lado. El recorrido completo —dos aristas— se anima solo, con el termómetro de Z subiendo a la vez que el punto camina.
Tareas para el alumno
- Ver el recorrido completo sobre el poliedro y girar la figura.
- Decir qué le pasaría a Z al moverse desde el óptimo a un vecino no visitado.
- Identificar qué variables salieron de la base y cuáles entraron.
Sala 16 · El símplex de principio a fin
Última parada del método: una fábrica con max Z = 45x + 60y sujeta a 4x + 6y ≤ 150 y 8x + 3y ≤ 144, elegida a propósito para que el óptimo no sea entero y no valga tantear. El alumno decide qué columna entra y qué fila sale en las dos iteraciones que hacen falta.
Tareas para el alumno
- Elegir columna entrante y fila saliente en la primera iteración.
- Repetir en la segunda y leer el óptimo en la tabla final.
Sala 17 · ¿Cuánto vale una hora más?
Tres deslizadores estiran una a una las capacidades del taller y una gráfica por recurso enseña cómo responde el beneficio: la pendiente de esa línea es el precio sombra. Al lado, la tabla final del símplex recalculada en vivo, con la fila Z bajo las holguras marcada en rojo — que es donde estaban los precios sombra desde el principio.
Tareas para el alumno
- Calcular cuánto vale Z si el tapizado pasa de 6 a 7 horas.
- Comparar los precios sombra de los tres recursos y explicar por qué uno vale 0.
- Localizar los tres precios sombra dentro de la tabla final.
Sala 18 · La receta del objetivo
Cada restricción apunta en una dirección propia —(1,0), (0,1) y (3,2)— y el objetivo (3,5) también. La pregunta del dual es cuánto de cada dirección hay que sumar para reconstruir el objetivo: tres deslizadores mueven tres flechas encadenadas punta con cola hasta cerrar la suma sobre el objetivo.
Tareas para el alumno
- Mover las tres flechas hasta reconstruir el objetivo.
- Calcular y₂ e y₃ cuando y₁ = 0.
- Interpretar qué significa que un multiplicador salga 0.
Sala 19 · El dual, en dinero
El sentido económico de la dualidad: el primal es el taller que produce y el dual es alguien que quiere comprarle los recursos al precio más bajo que el taller aceptaría. De ahí salen las restricciones ≥ (nadie vende por menos de lo que gana produciendo). Los dos problemas aparecen uno al lado del otro, con las capacidades en azul y los beneficios en rojo, y debajo las dos matrices de coeficientes: la del dual es la del primal traspuesta.
Tareas para el alumno
- Interpretar en dinero qué significa y₂ = 3.
- Identificar de quién es el problema dual del de una tienda que compra jamón a tres proveedores.
- Decidir si conviene vender una unidad de tapizado a 2 €.
Sala 20 · El problema dual
Las reglas mecánicas de la dualización, con el primal y el dual escritos uno al lado del otro y todos los coeficientes a la vista, 1 y 0 incluidos. Al pasar el ratón por un número se enciende su pareja exacta en el otro problema: el término independiente 4 con el 4 del objetivo dual, el 1 de 1x con el 1 de 1y₁, y la etiqueta de una restricción con toda la columna de su variable dual.
Tareas para el alumno
- Decir con qué se corresponden las variables del primal.
- Leer un coeficiente concreto de la función objetivo del dual.
- Elegir, entre cuatro opciones, el dual de un problema nuevo.
Sala 21 · Construye tú el dual
El reto grande del bloque: dualizar por etapas un problema que no es el taller —una pastelería con tres restricciones y dos variables, para que los dos recuentos no coincidan—. El dual se va escribiendo solo en el recuadro de la derecha conforme se acierta cada etapa, hasta quedar entero.
Tareas para el alumno
- Decir qué aspecto tendrá el dual antes de calcular nada.
- Contar cuántas variables y cuántas restricciones tendrá.
- Escribir los coeficientes del objetivo y los de las dos restricciones.
Sala 22 · Variables libres y signos
Qué hacer cuando una variable puede ser negativa: el truco x = x⁺ − x⁻ con las dos partes ≥ 0. Y la tabla de correspondencias de signo entre los dos problemas —restricción ≤ ↔ variable ≥ 0, restricción = ↔ variable libre, y al revés—, con la razón de fondo: lo que aprieta por un solo lado da un precio que no puede ser negativo.
Tareas para el alumno
- Decir en qué se convierte una igualdad del primal dentro del dual.
- Elegir el signo correcto del truco de la variable libre.
- Repartir un valor negativo entre x⁺ y x⁻.
Sala 23 · Los dos se encuentran
Cierre del laboratorio: dualidad débil, dualidad fuerte y holgura complementaria, cada una explicada aparte, con una lectura de mercado (el precio sombra es el precio en el que al taller le da igual vender que producir). Un gráfico animado enseña la cota dual bajando y el plan primal subiendo hasta cerrar el hueco en 36, con las barras de holgura siguiendo al plan mientras avanza.
Tareas para el alumno
- Ver cerrarse el hueco entre las dos cotas.
- Decir a partir de qué precio compensa vender una unidad de tapizado.
- Explicar qué significa que la diferencia entre las dos cotas llegue a 0.
- Deducir cuánto vale el precio sombra de un recurso que sobra.
Sala 24 · Lo que cuenta la tabla final
Los apartados que siguen a «resuélvelo con el símplex» en un problema de examen, con un problema completo de tres productos y tres recursos (una fábrica de juguetes: max 4x₁ + 5x₂ + 9x₃). Primero se recorren las tres iteraciones; en la primera entra x₃, que vuelve a salir en la tercera. Con la tabla final siempre a la vista se leen las holguras (qué recursos se agotan y cuántas horas sobran, comprobándolo en las restricciones), los precios sombra, la dualidad fuerte (W = Z = 72) y si conviene comprar horas sueltas a un precio dado. El último bloque explica por qué el producto que más deja no se fabrica: el número de la fila Z bajo x₃ es su coste reducido, lo que valen a precio sombra los recursos que consume menos lo que deja, y de ahí sale el beneficio a partir del cual compensaría. Un deslizador de c₃ lo comprueba resolviendo el problema de nuevo. Cierra con un resumen de cómo se contesta cada apartado.
Tareas para el alumno
- Leer las holguras en la tabla final y comprobarlas sustituyendo el plan óptimo en una restricción.
- Leer los precios sombra y comprobar la dualidad fuerte calculando el objetivo dual.
- Decidir qué compras de horas sueltas aumentan el beneficio comparando con el precio sombra.
- Explicar por qué una variable que entró en la base puede no estar en el óptimo.
- Usar el coste reducido para calcular el beneficio con una unidad forzada y el umbral a partir del cual compensa fabricar.
Salas para proyectar
Las más vistosas para mostrar y discutir en clase.