En el módulo anterior aprendimos a analizar: expresar costes, calcularlos y apoyarnos en las estructuras de datos adecuadas. A partir de aquí, Rutalia cambia de pregunta. Ya no quiere saber cuánto cuesta una operación, sino cuál es la mejor decisión posible: ¿cuántas horas de furgoneta y cuántas de bicicleta eléctrica contrato mañana para entregar el máximo de paquetes sin pasarme de presupuesto? La programación lineal (PL) es la herramienta más antigua, más estudiada y más usada en la industria para responder este tipo de preguntas, y es la puerta de entrada natural a todo el módulo de optimización: nos obliga a pensar en términos de variables de decisión, función objetivo y restricciones, un vocabulario que reutilizaremos en cada lección que viene.

1. De analizar a decidir: qué es un problema de optimización
2. Formulación de un programa lineal
3. La región factible: intuición geométrica con un ejemplo resoluble a mano
4. El método símplex, a vista de pájaro
5. Resolución práctica con scipy.optimize.linprog
6. Programación lineal entera: cuando las variables no se pueden partir

Todo problema de optimización, sea lineal o no, se compone de tres piezas:

• Variables de decisión: los números que nosotros controlamos. En Rutalia: cuántas horas de furgoneta contratar, cuántos paquetes asignar a cada repartidor, qué ruta seguir.
• Función objetivo: una fórmula que, dadas unas variables de decisión, devuelve un número que queremos maximizar (paquetes entregados, ingresos) o minimizar (kilómetros, coste, emisiones).
• Restricciones: las condiciones que una solución debe cumplir para ser válida: presupuesto máximo, horas de personal disponibles, capacidad de carga.

Una asignación de valores a las variables que cumple todas las restricciones se llama solución factible. La mejor solución factible según la función objetivo es la solución óptima. Optimizar es, literalmente, buscar el mejor punto dentro del conjunto de soluciones factibles.

Un problema es de programación lineal cuando la función objetivo y todas las restricciones son lineales: sumas de variables multiplicadas por constantes, sin productos entre variables, sin cuadrados, sin funciones raras. 3x + 5y es lineal; x·y o x² no lo son. Esta limitación, que parece severa, resulta enormemente productiva: los problemas lineales se resuelven de forma exacta y rapidísima incluso con millones de variables, algo que veremos que no ocurre con los problemas combinatorios de las próximas lecciones.

Formular bien es el 80 % del trabajo. Veamos el problema concreto de Rutalia para el turno de mañana:

• Una hora de furgoneta entrega de media 30 paquetes y cuesta 25 € (combustible + conductor).
• Una hora de bicicleta eléctrica entrega de media 15 paquetes y cuesta 10 €.
• El presupuesto del turno es de 400 €.
• Entre todos los repartidores disponibles se pueden cubrir como máximo 25 horas de trabajo.
• Solo hay furgonetas para cubrir 12 horas de furgoneta como máximo.

Traducción paso a paso:

1. Variables: x = horas de furgoneta, y = horas de bici. (Por ahora aceptamos valores fraccionarios: 10,5 horas es una asignación válida.)
2. Objetivo: maximizar Z = 30x + 15y (paquetes entregados).
3. Restricciones:
   • Presupuesto: 25x + 10y ≤ 400
   • Personal: x + y ≤ 25
   • Flota: x ≤ 12
   • No negatividad: x ≥ 0, y ≥ 0 (no existen horas negativas; parece obvio, pero hay que declararlo).

El programa lineal completo queda así:

Observa que cada línea es una desigualdad lineal. Si el enunciado nos pidiera algo como "el rendimiento de la furgoneta cae un 2 % por cada hora acumulada", la relación dejaría de ser lineal y necesitaríamos otras técnicas.

Con dos variables podemos dibujar el problema. Cada restricción es una recta que divide el plano en dos mitades; la región factible es la intersección de todas las mitades válidas: un polígono convexo.

Para nuestro problema, los vértices del polígono factible son:

¿Por qué basta con mirar los vértices? La función objetivo 30x + 15y = Z define, para cada valor de Z, una recta. Al aumentar Z, esa recta se desplaza paralelamente. El mayor Z alcanzable es el último instante en que la recta aún toca la región factible, y ese último contacto ocurre siempre en un vértice (o, en caso de empate, en una arista completa). Este es el teorema fundamental de la programación lineal: si existe óptimo finito, hay un vértice óptimo.

Comprobemos el vértice ganador a mano. Intersección de presupuesto y personal:

Decisión óptima: 10 horas de furgoneta y 15 de bici → 525 paquetes, gastando exactamente los 400 € y las 25 horas de personal. Fíjate en un detalle con contenido económico: la restricción de flota (x ≤ 12) no está saturada — comprar más furgonetas no mejoraría nada; contratar más personal o ampliar presupuesto, sí. Este tipo de lectura ("¿qué restricción me está frenando?") es una de las razones por las que la PL es tan valiosa para decidir.

Con 2 variables dibujamos; con 200.000 no. El método símplex (Dantzig, 1947) automatiza exactamente la intuición anterior:

1. Parte de un vértice factible cualquiera (por ejemplo, el origen).
2. Mira las aristas que salen de ese vértice y elige una por la que la función objetivo mejora.
3. Avanza por esa arista hasta el siguiente vértice.
4. Repite hasta que ningún vecino mejora: ese vértice es el óptimo.

En nuestro ejemplo, un recorrido posible sería (0,0) → (12,0) → (12,10) → (10,15), mejorando Z en cada salto (0 → 360 → 510 → 525). Como la región es convexa, un vértice sin vecinos mejores es un óptimo global, no solo local — no hay "valles" donde quedarse atrapado, a diferencia de lo que veremos con las metaheurísticas en 02-04.

Dos apuntes de complejidad, conectando con el módulo 1:

• En el peor caso teórico, símplex puede visitar un número exponencial de vértices (existen instancias patológicas construidas a propósito).
• En la práctica es casi siempre rapidísimo, y además existen algoritmos de punto interior con garantía polinómica. Para el ingeniero, el mensaje es: un PL con miles o millones de variables continuas es un problema resuelto; se lo pasas a un solver y punto.

No implementaremos símplex: es un algoritmo delicado de programar bien (degeneración, estabilidad numérica) y los solvers existentes llevan décadas de ingeniería encima. Nuestro trabajo es formular; el del solver, resolver.

scipy incluye un solver de PL de calidad industrial (HiGHS). Su convención: siempre minimiza y las desigualdades son de tipo ≤. Como queremos maximizar Z, minimizamos −Z (es el mismo problema con el signo cambiado).

Desglosemos lo que puede despistar la primera vez:

• c son los coeficientes del objetivo con el signo cambiado, porque linprog minimiza. Al final recuperamos el valor real con -res.fun.
• Cada fila de A_ub es una restricción ≤, y b_ub guarda su lado derecho en el mismo orden. La restricción x ≤ 12 se escribe como la fila [1, 0] (coeficiente 1 para x, 0 para y).
• bounds cubre la no negatividad; podríamos haberla metido en A_ub, pero es más claro (y más eficiente para el solver) declararla como cota.
• Comprueba siempre res.status: 0 es óptimo; 2 significa infactible (las restricciones se contradicen: por ejemplo, exigir 30 horas con 25 disponibles); 3 significa no acotado (te has olvidado una restricción y el objetivo puede crecer sin límite — casi siempre es un error de formulación, no una máquina de imprimir dinero).

Si mañana Rutalia añade motos (20 paquetes/h, 15 €/h), no hay que repensar nada: una variable más, una columna más en A_ub, y el mismo código resuelve el problema en milisegundos. Esa escalabilidad sin dolor es el gran regalo de la linealidad.

Nuestras "horas" admitían fracciones. Pero muchas decisiones de Rutalia son indivisibles: no se puede alquilar 2,5 furgonetas ni abrir 0,75 microalmacenes. Si exigimos que las variables sean enteras, el problema pasa a llamarse programación lineal entera (PLE o ILP), y cambia de naturaleza por completo.

La tentación obvia — "resuelvo el PL continuo y redondeo" — falla, y conviene ver un contraejemplo con números. Supón que Rutalia estudia cuántos contratos mensuales firmar de furgonetas grandes (x, aportan 13 puntos de capacidad) y pequeñas (y, aportan 8), con dos recursos limitados:

• Óptimo del PL continuo (ignorando la integridad): x = 2,5, y = 3,75, con valor 62,5.
• Redondeo al entero más cercano, (3, 4): infactible (viola x + 2y ≤ 10: da 11).
• Redondeo hacia abajo, (2, 3): factible, valor 50.
• Óptimo entero real: (2, 4), valor 58 — que no se obtiene redondeando el óptimo continuo en ninguna dirección.

Con 2 variables el error parece pequeño; con cientos, el redondeo puede violar restricciones en cadena o dejarse mucho valor por el camino. Geométricamente, la explicación es que el conjunto factible entero ya no es un polígono continuo sino una nube de puntos aislados, y el teorema del vértice óptimo deja de aplicar.

scipy también resuelve PLE (parámetro integrality, disponible con el método HiGHS):

¿Y por qué decimos que la PLE "es más dura"? Porque exigir integridad convierte un problema resoluble en tiempo polinómico en uno NP-duro: en el peor caso, no se conoce (y probablemente no exista) ningún algoritmo esencialmente mejor que explorar una cantidad exponencial de combinaciones. De hecho, muchos problemas combinatorios famosos — la mochila, el viajante — pueden escribirse como PLE. Los solvers modernos los atacan con una técnica llamada branch and bound, que estudiaremos a fondo en la lección 02-03; y cuando ni eso alcanza, entran las metaheurísticas de 02-04 y 02-05. Esa es exactamente la ruta que vamos a recorrer en este módulo.

• Olvidar la no negatividad. Sin x, y ≥ 0 el solver puede devolver "horas negativas" (¡o un problema no acotado!). Declara siempre las cotas naturales de cada variable.
• Confundir el sentido de la optimización. linprog minimiza. Si maximizas, niega los coeficientes de c y recuerda negar res.fun al leer el resultado. Es el despiste número uno.
• Mezclar unidades. Si el presupuesto está en euros y una fila de A_ub mezcla euros con horas, el modelo es basura silenciosa: resolverá "bien" un problema que no es el tuyo. Escribe las unidades de cada restricción en un comentario.
• No mirar res.status. Un modelo infactible o no acotado también "termina"; si usas res.x sin comprobar el estado, propagarás None o valores sin sentido.
• Redondear un PL continuo para obtener enteros. Como acabamos de ver, puede ser infactible o subóptimo. Si las variables son indivisibles, usa integrality (o modela con PLE directamente).
• Forzar linealidad donde no la hay. Si el coste por hora cambia con el volumen (descuentos por tramos), a veces se puede linealizar por tramos con variables extra; a veces no. Sé honesto con el modelo: un PL elegante de un problema equivocado no decide nada útil.
• Consejo: antes de programar, escribe el modelo en papel con el formato maximizar / sujeto a. Si no sabes escribirlo así, todavía no entiendes el problema — y scipy tampoco lo entenderá por ti.

1. Turno de tarde. Por la tarde el tráfico empeora: la furgoneta baja a 24 paquetes/hora (mismo coste, 25 €/h) y la bici mantiene 15 paquetes/hora a 10 €/h. Presupuesto: 300 €; horas de personal: 20; máximo de furgoneta: 8 horas. Formula el PL y resuélvelo gráficamente (enumera los vértices y evalúa el objetivo en cada uno).

2. Tres modos de transporte. Añade motos al modelo original de la lección: 22 paquetes/h y 15 €/h, con un máximo de 10 horas de moto. El presupuesto sube a 500 € y el personal a 30 horas (furgoneta: máximo 12 h, como antes). Escribe el código linprog completo y obtén la asignación óptima. ¿Alguna restricción queda sin saturar?

3. ¿Por qué no redondear? Considera el PLE maximizar 5x + 4y sujeto a 6x + 4y ≤ 24, x + 2y ≤ 6, x, y ≥ 0 enteras. (a) Resuelve el PL continuo a mano (dos restricciones, dos variables). (b) Redondea el resultado y comprueba factibilidad. (c) Encuentra el óptimo entero por enumeración (hay pocos puntos factibles) y compara.

Ejercicio 1.

Vértices y valores: (0,0)→0; (8,0)→192; (8,10) (flota ∩ presupuesto: 25·8+10y=300 → y=10) → 342; presupuesto ∩ personal: 25x+10(20−x)=300 → 15x=100 → x=20/3≈6,67, y≈13,33 → 24·6,67+15·13,33 ≈ 360; (0,20)→300. Óptimo: x = 20/3 ≈ 6,67 horas de furgoneta y y = 40/3 ≈ 13,33 de bici, con 360 paquetes. Nota: sale fraccionario y es válido, porque las horas sí son divisibles. Compara con el turno de mañana: al empeorar el rendimiento de la furgoneta, el óptimo desplaza carga hacia las bicis y la restricción de flota deja de estar saturada.

Ejercicio 2.

Óptimo: 10 h de furgoneta, 10 h de bici y 10 h de moto → 670 paquetes. Verifica las restricciones con la solución devuelta (un assert de dos líneas evita decisiones basadas en una lectura errónea): presupuesto 25·10 + 10·10 + 15·10 = 500 ✔ saturado; personal 10+10+10 = 30 ✔ saturado; motos z = 10 ✔ saturada. La única restricción sin saturar es la flota de furgonetas (x = 10 < 12): con estos precios y rendimientos, comprar más furgonetas no aportaría nada; el cuello de botella son el presupuesto y el personal. Observa que el solver no llena la furgoneta hasta su tope aunque sea el modo que más paquetes entrega por hora: por euro gastado, la bici (1,5 paq/€) y la moto (≈1,47 paq/€) rinden más que la furgoneta (1,2 paq/€), y el presupuesto es escaso.

Ejercicio 3. (a) Continuo: intersección 6x+4y=24 y x+2y=6 → x = 3, y = 1,5, valor Z = 21. (b) Redondeos: (3,2) viola 6x+4y ≤ 24 (26 > 24); (3,1) es factible con Z = 19. (c) Enumerando los enteros factibles, el óptimo es (4,0) con Z = 20 (comprueba: 24 ≤ 24, 4 ≤ 6). Ni (3,1) ni ningún redondeo del óptimo continuo lo encuentra: hay que buscar entre los enteros, que es justo lo que hará branch and bound en 02-03.

Hemos dado el salto de analizar a decidir. La programación lineal nos ha enseñado el vocabulario de todo el módulo — variables de decisión, función objetivo, restricciones, región factible, óptimo — y nos ha dejado dos resultados prácticos: cuando el problema es lineal y continuo, un solver como linprog lo resuelve de forma exacta y casi instantánea (formular es nuestro trabajo; resolver, el suyo); y cuando las variables deben ser enteras, el problema se vuelve NP-duro y el redondeo no es un atajo válido. Justo ahí empieza la siguiente lección: la mayoría de las decisiones reales de Rutalia — qué paquetes cargo en esta furgoneta, en qué orden visito estas direcciones — son intrínsecamente discretas. Bienvenidos a la optimización combinatoria, donde el espacio de soluciones no es un polígono suave sino una explosión de combinaciones, y donde elegir bien el algoritmo marca la diferencia entre segundos y siglos.