Teaching objectives
And what about problems with so many variables that you cannot draw them any more? This lab picks up where Linear optimization ends: there the optimum was found by looking at the feasible region, and here we build the machinery that finds it without seeing it — the simplex method — and then turn the whole problem inside out to reach shadow prices and the dual problem. The same workshop of tables and chairs runs through all 23 rooms, and always ends at €36. Aimed at University level.
What you learn
- Recall what a linear optimization problem is, what the feasible region is, and why the optimum always sits at a vertex (room 1).
- Turn a problem around so it fits the method: minimizing as maximizing, and ≥ as ≤ (rooms 2 and 5).
- Put a problem in standard form with slack and surplus variables, and tell basic from non-basic variables (rooms 3, 4 and 6).
- Understand why testing every vertex is hopeless: their number grows exponentially with the size of the problem (room 7).
- Build the simplex tableau from a word problem and read it: what is in each row, each column and the Z row (room 8).
- Choose the entering column and the leaving row, and see what that means on the picture: a jump from a vertex to its neighbour (rooms 9 and 10).
- Apply the Gauss-Jordan step to the tableau, first watching it calculation by calculation and then doing it in full, row by row (rooms 11 and 13), having first decided who enters and who leaves (room 12).
- See the simplex method for what it is — a walk across vertices that never steps back — and check that it works exactly the same on a three-variable polyhedron (rooms 14 and 15).
- Solve a complete problem end to end, unaided (room 16).
- Interpret shadow prices: how much one more unit of each resource is worth, and how far that is worth it (room 17).
- Build the dual problem, understand its economic meaning, and check that its solution was already in the final simplex tableau (rooms 18 to 23).
Key mathematical ideas
- Every
≤constraint becomes an equality by adding a slack variable; every≥, by subtracting a surplus. None of those variables may be negative. - In standard form there are more variables than degrees of freedom: at each vertex, as many variables as there are original variables are zero. Those are the non-basic ones; the rest form the basis.
- Each simplex iteration changes the basis: one variable enters (the most negative coefficient in the Z row) and another leaves (the minimum ratio). Where that row crosses that column sits the pivot.
- The simplex method does not test every vertex: it walks from one to the next, always improving, and that is why it terminates. Since the region is convex, a vertex better than all its neighbours is the best of all — there are no local maxima that are not global.
- The Z row of the final tableau gives more than the optimum: its coefficients under the slacks are the shadow prices of the resources, and they are also the dual's solution.
- The dual problem is built by mechanical rules: one dual variable per constraint, one dual constraint per variable, max for min, and the coefficient matrix transposed. Right-hand sides and objective coefficients swap roles.
- Weak duality: any feasible primal solution is worth less than any feasible dual one. Strong duality: at the optimum they coincide. Complementary slackness: if a resource is left over its price is 0, and if its price is positive that resource is exhausted.
Before you start
It helps to have done Linear optimization, or at least to know how to draw a feasible region and find the optimum by looking at it: room 1 recaps that quickly, but it does not teach it from scratch.
Room-by-room contents
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.
Student tasks
- 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.
Student tasks
- 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₃.
Student tasks
- 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.
Student tasks
- 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.
Student tasks
- 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.
Student tasks
- 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.
Student tasks
- 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.
Student tasks
- 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.
Student tasks
- 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.
Student tasks
- 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.
Student tasks
- 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.
Student tasks
- 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.
Student tasks
- 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.
Student tasks
- 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.
Student tasks
- 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.
Student tasks
- 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.
Student tasks
- 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.
Student tasks
- 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.
Student tasks
- 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.
Student tasks
- 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.
Student tasks
- 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.
Student tasks
- 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.
Student tasks
- 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.
Rooms to project
The most striking ones to show and discuss in class.