Teoría del todo

Parte II · Estructuras

Optimización: elegir lo mejor entre lo posible

en cursoÚltima actualización: 8 de noviembre de 2026 · Primera versión del capítulo

Se construye sobre: Derivada e integral, Algoritmos y complejidad

Casi todas las decisiones que tomo tienen la misma forma, aunque no lo parezca. Quiero lo mejor de algo (más ganancia, menos tiempo, menos material, más puntos) y no puedo tenerlo todo, porque hay límites: la plata, las horas, lo que cabe en el carro, las reglas del juego. Elegir lo mejor entre lo posible tiene nombre en matemáticas: optimización. Y es, probablemente, la rama que más se usa sin que nadie la nombre.

Este capítulo recorre las tres ideas que más me han servido: la derivada que se vuelve cero en la cima, la programación lineal que busca en las esquinas, y la programación dinámica, que parte un problema grande en pedazos que se resuelven una sola vez. Al final las tres se encuentran en un sitio inesperado: una mesa de Rummikub.

Tres ingredientes

Todo problema de optimización, por complicado que sea, se arma con lo mismo. Unas variables de decisión, lo que yo controlo: cuántas bandejas hornear, por dónde ir, cuánto invertir en cada cosa. Una función objetivo, el número que quiero hacer grande o pequeño. Y unas restricciones, que separan lo posible de lo imposible. En símbolos:

Se lee: entre todos los del conjunto de opciones permitidas, encuentra el que hace más grande a . Minimizar es lo mismo con el signo cambiado: hacer mínimo el costo es hacer máximo el costo negativo. Lo que de verdad distingue a un problema de otro es la forma de y de : si son curvas suaves, si son rectas, si las variables pueden tomar cualquier valor o solo números enteros. De eso depende que el problema se resuelva en un segundo o que no lo resuelva nadie.

En la cima, la pendiente es cero

La primera herramienta la encontró Pierre de Fermat hacia 1636, antes de que existiera el cálculo con ese nombre. Si una curva suave sube y luego baja, en el punto más alto no está subiendo ni bajando: su derivada vale cero. Buscar el máximo se convierte en resolver una ecuación.

Retrato al óleo de Pierre de Fermat, un hombre de pelo largo y canoso con toga oscura y cuello blanco ancho de magistrado
Pierre de Fermat era abogado y juez en Toulouse; la matemática la hacía en sus ratos libres. Su método para encontrar máximos y mínimos es de la década de 1630, medio siglo antes de Newton y Leibniz.Foto: Autor desconocido · Dominio público · Wikimedia Commons

El ejemplo que más me gusta es una lata de atún. Quiero que guarde un volumen fijo gastando la menor cantidad posible de lámina. Si el radio es y la altura , el volumen es , así que la altura queda amarrada al radio: . La lámina es la de las dos tapas más la del costado:

Una lata muy flaca gasta mucho costado; una muy ancha, muchas tapas. En algún punto intermedio está el mínimo, y ahí la pendiente es cero:

La lata óptima es tan alta como ancha: la altura igual al diámetro. Para una lata de atún de 170 cm³ eso da unos 3 cm de radio y 6 de alto, con 170 cm² de lámina. Mejor verlo moverse:

Juega · una lata de 170 cm³ con la menor lámina posible
11,0 cm de ancho · 1,8 de alto23456radio (cm)350
  • tapas
  • costado
  • lámina total
  • pendiente

Lámina: 251,9 cm² (190,1 de tapas y 61,8 de costado). Pendiente: 57,9.

La pendiente es positiva: achicar el radio ahorra lámina. La lata está muy ancha y gasta en tapas.

Arrastra el radio de un extremo al otro y mira las dos curvas punteadas: las tapas crecen con el cuadrado del radio y el costado baja como su inverso. La lámina total, la suma, tiene un valle, y la rayita negra que toca la curva es la derivada: inclinada hacia abajo a la izquierda del valle, hacia arriba a la derecha, y plana justo en el fondo. Un detalle que no se ve en la fórmula pero sí en los números: en el óptimo el costado gasta exactamente el doble que las dos tapas juntas.

El botón de bajar hace lo que haría un computador que no sabe despejar ecuaciones: mira la pendiente donde está y da un paso en contra, más largo cuanto más inclinada. Donde la curva es empinada avanza rápido; cerca del fondo, casi no se mueve. En una o dos docenas de pasos llega, desde cualquier lado.

Las latas de verdad casi nunca son así, y no porque la cuenta esté mal. Las tapas son más gruesas que el costado, hay que apilarlas y al mercadeo le gustan ciertas formas. Sube el costo de las tapas en la simulación y verás que la lata óptima se estira: si la lámina de las tapas vale el doble, la cuenta da una altura de cuatro radios. Esa es la lección más importante de la optimización: el óptimo depende de qué pusiste en la función objetivo. Si olvidas un costo, la matemática lo olvida contigo.

Con muchas variables la idea es la misma. En lugar de una pendiente hay un gradiente, un vector con la pendiente en cada dirección, y en la cima todas sus componentes son cero. Cuando el sistema de ecuaciones es imposible de resolver a mano se hace lo que hacen las redes neuronales con sus millones de perillas: dar pasitos en la dirección en que la función mejora, el descenso de gradiente.

Hay una trampa. Que la pendiente sea cero dice que estás en una cima, no que estés en la más alta. Puede ser un cerrito con una montaña al lado (un óptimo local), o ni siquiera una cima, sino un punto de silla. Hay una familia de problemas donde esa trampa no existe: los convexos, cuya forma es la de un tazón, donde cualquier fondo que encuentres es el fondo. Buena parte del arte consiste en reconocer cuándo un problema es convexo, o en reformularlo para que lo sea.

La panadería

Ahora un problema de otra clase. Una panadería pequeña hace bandejas de pandebono y de almojábanas. Cada bandeja de pandebono deja 5.000 pesos de ganancia y cada una de almojábanas, 4.000. Pero el horno solo está libre 12 horas a la semana, y el queso alcanza para 14 kilos. Una bandeja de pandebono ocupa 2 horas de horno y gasta 4 kilos de queso; una de almojábanas, 3 horas y 2 kilos. ¿Cuántas de cada una conviene hacer?

Con bandejas de pandebono y de almojábanas, en miles de pesos:

Todo es lineal: la ganancia y las restricciones son sumas de variables multiplicadas por números, sin cuadrados ni productos entre ellas. Eso es un problema de programación lineal. (La palabra “programación” aquí no tiene que ver con computadores: viene del inglés militar de los años cuarenta, donde un program era un plan de actividades.)

Cada restricción parte el plano en dos con una recta, y los planes permitidos son los que quedan del lado bueno de todas. Eso forma un polígono. La ganancia, por su lado, se dibuja como rectas paralelas: todos los planes que dejan 15.000 pesos están en una, todos los que dejan 20.000 en otra un poco más arriba. Optimizar es empujar esa recta lo más lejos posible sin salirse del polígono.

Juega · cuántas bandejas hornear
012345012345pandebono →↑ almojábanas
  • horno: 2x + 3y ≤ 12 horas
  • queso: 4x + 2y ≤ 14 kilos
  • ganancia igual

Mejor plan: 2,25 bandejas de pandebono y 2,5 de almojábanas, con $21.250 de ganancia.

Una hora más de horno valdría $750; un kilo más de queso, $875.

La recta se escapa por una esquina: 2,25 bandejas de pandebono y 2,5 de almojábanas, con 21.250 pesos. Mueve las ganancias y verás que el óptimo salta de esquina en esquina, pero nunca se queda en el medio del polígono. Eso no es casualidad, es el teorema central de la programación lineal: si hay un óptimo, hay uno en una esquina. La razón cabe en una frase: si estás en el interior o en medio de un lado, siempre puedes moverte en alguna dirección sin perder ganancia hasta toparte con una esquina.

Esa observación convierte un problema con infinitas opciones en uno con un número finito de candidatas. En el plano son cuatro y se revisan a ojo. Con mil variables y mil restricciones, el número de esquinas es astronómico, pero hay un método para no visitarlas todas.

Dantzig y el símplex

En 1947, George Dantzig trabajaba planeando la logística de la Fuerza Aérea de Estados Unidos, que era exactamente esto en gigante: cuántos aviones, hombres y repuestos mover a dónde. Su idea, el método símplex, es caminar por las aristas del polígono (en muchas dimensiones, un poliedro): parte de una esquina, mira las vecinas, pasa a una que mejore la ganancia, y repite. Cuando ninguna vecina mejora, ya llegó, porque en un problema lineal no hay cerritos falsos: el polígono es convexo y la función es una recta, así que el óptimo local es el global.

Fotografía en blanco y negro de George Dantzig, con gafas y bigote, estrechando la mano del presidente Gerald Ford en una ceremonia, con una bandera de Estados Unidos al fondo
George Dantzig recibe la Medalla Nacional de Ciencia de manos del presidente Gerald Ford, en 1976. La foto lleva la firma de Ford.Foto: Oficina Fotográfica de la Casa Blanca · Dominio público · Wikimedia Commons

Dantzig tenía historia con los problemas difíciles. De estudiante, en 1939, llegó tarde a una clase de estadística de Jerzy Neyman, copió dos problemas del tablero creyendo que eran tarea y los resolvió unos días después. Eran dos problemas abiertos. Y no fue el primero con la idea de la programación lineal: en 1939, en Leningrado, Leonid Kantorovich la había planteado para organizar una fábrica de madera contrachapada, pero su trabajo quedó casi desconocido en Occidente. Kantorovich compartió en 1975 el premio de economía en memoria de Nobel con Tjalling Koopmans, por la teoría de la asignación óptima de recursos. Dantzig, para sorpresa de muchos, quedó por fuera.

Retrato en blanco y negro de Leonid Kantorovich, un hombre mayor con gafas de marco metálico, de perfil tres cuartos
Leonid Kantorovich en 1975, el año de su premio. Llegó a la programación lineal tratando de repartir el trabajo entre las máquinas de una fábrica de contrachapado.Foto: Andréi Bogdánov · CC BY 3.0 · Wikimedia Commons

Hay una sutileza que me parece hermosa. En la práctica el símplex es rapidísimo, pero en 1972 Victor Klee y George Minty construyeron un poliedro retorcido, un cubo aplastado, en el que el método visita todas las esquinas, y son . O sea: el método que resuelve a diario problemas con millones de variables es, en el peor caso, exponencial. La pregunta de si la programación lineal se podía resolver siempre en tiempo polinomial (en el sentido de algoritmos y complejidad) la contestó Leonid Khachiyan en 1979, con un método que encierra el óptimo en elipsoides cada vez más pequeños. Era polinomial pero lento en la práctica. En 1984 Narendra Karmarkar presentó otro que cruza por el interior del poliedro en lugar de caminar por el borde, y que sí compite con el símplex. Hoy los programas usan los dos.

Lo que vale una hora más de horno

El óptimo trae un regalo escondido. Pregúntale al modelo qué pasaría si el horno estuviera libre una hora más: la ganancia óptima sube 750 pesos. Si hubiera un kilo más de queso, sube 875. Esos números se llaman precios sombra, y responden la pregunta que cualquier dueño de negocio se hace: ¿cuánto estaría dispuesto a pagar por un poquito más de cada recurso? Si alguien me alquila una hora de horno a 600 pesos, me conviene; a 900, no.

Y hay algo más profundo. Si a cada recurso le pones su precio sombra y sumas lo que vale todo lo que tienes,

da exactamente la ganancia óptima. Ese es el teorema de dualidad: cada problema lineal tiene un gemelo, el de ponerle precio a los recursos, y los dos tienen el mismo valor. John von Neumann se lo señaló a Dantzig en su primera reunión, en 1947, porque venía de pensar lo mismo en la teoría de juegos. Para mí es de las ideas que unen la matemática con la economía: el valor de un recurso escaso no es lo que costó, sino lo que permite ganar en el margen.

Cuando solo valen enteros

Hay un problema con la panadería: nadie hornea 2,25 bandejas. Si las bandejas tienen que ser enteras, la tentación es redondear el óptimo: 2 de pandebono y 3 de almojábanas. Prende el botón de bandejas enteras en la gráfica de arriba y mira dónde cae: fuera del polígono. Ese plan necesita 13 horas de horno y solo hay 12. Redondear hacia abajo, 2 y 2, sí cabe, y deja 18.000 pesos. Pero el mejor plan entero es otro, 3 de pandebono y 1 de almojábanas, con 19.000, y no queda pegado al óptimo continuo.

Esa es la programación entera, y el cambio parece inocente pero no lo es. Sin la libertad de usar fracciones, la región factible ya no es un polígono sino un puñado de puntos sueltos, y el argumento de las esquinas se cae. En 1972 Richard Karp incluyó la programación entera con variables de cero o uno en su lista de problemas NP-completos: si alguien encuentra un método siempre rápido para ella, resolvería de paso todos los problemas difíciles de esa lista. Nadie lo ha encontrado.

Lo que sí existe es una estrategia muy buena en la práctica, propuesta en 1960 por Ailsa Land y Alison Doig: ramificar y acotar. Resuelves el problema permitiendo fracciones, que es fácil. Si te da 2,25 bandejas, partes en dos casos: o son 2 o menos, o son 3 o más, y resuelves cada uno. Y la cota es el truco: el óptimo con fracciones nunca es peor que el entero, así que si una rama, aun con fracciones, no puede superar el mejor plan entero que ya tienes, la descartas sin explorarla. Con eso se arman los horarios de aviones y tripulaciones de los que hablé en logística, las rutas de camiones y los turnos de un hospital.

Partir el problema: programación dinámica

La tercera idea es de Richard Bellman, que en los años cincuenta trabajaba en la corporación RAND, un centro de investigación ligado a la Fuerza Aérea. Contó en su autobiografía que escogió el nombre programación dinámica por razones políticas: el secretario de Defensa de entonces detestaba la palabra “investigación” y más aún la palabra “matemática”, y “dinámica” le pareció un adjetivo imposible de usar en sentido negativo.

La idea es su principio de optimalidad: si el mejor camino de Pereira a Medellín pasa por Manizales, entonces el tramo de Manizales a Medellín es también el mejor camino entre esas dos ciudades. Si hubiera uno mejor, lo usarías y mejorarías el total. Eso permite resolver un problema grande guardando las respuestas de los problemas pequeños de los que está hecho, para no recalcularlas nunca. El algoritmo de Dijkstra de algoritmos y complejidad es, en el fondo, esto.

La programación dinámica funciona cuando el problema se puede recorrer en orden y lo que importa del pasado cabe en un “estado” pequeño. Si para decidir el paso siguiente necesitas recordar todo lo que hiciste, no ahorra nada. Si basta recordar poco, convierte lo exponencial en algo manejable. Ese contraste, que una buena descripción del estado vale más que un computador más rápido, es exactamente lo que pasa en el Rummikub: un problema que parecía de programación entera y resultó tener un estado diminuto.

Lo que me llevo

Cuando uno aprende a ver la optimización, la ve en todas partes. La luz que va de un punto a otro sigue el camino de menor tiempo, como notó Fermat. Un controlador escoge en cada instante la acción que mejor corrige el error. Un mercado, en sus mejores días, asigna recursos como si resolviera un programa lineal gigante, con precios que se parecen mucho a los precios sombra. Y entrenar una red neuronal es bajar una montaña con niebla.

Pero me quedo con la advertencia de la lata. El óptimo es exactamente tan bueno como la pregunta. Una función objetivo que solo cuenta la ganancia de esta semana, o la lámina y no el apilamiento, produce con precisión impecable la respuesta equivocada. Optimizar bien empieza mucho antes de la primera derivada: empieza por decidir qué es lo que de verdad quiero.