Problemas Clásicos de Modelado

Cubrir requerimientos al mínimo costo

El problema de la dieta elige cantidades $x_j\ge 0$ de cada alimento $j$ para minimizar el costo cumpliendo requerimientos nutricionales mínimos. Es el LP continuo por excelencia. La restricción característica es la de cobertura: cada nutriente $i$ debe alcanzar su mínimo $r_i$.

Donde $a_{ij}$ = aporte del nutriente $i$ por unidad del alimento $j$, $c_j$ = costo del alimento $j$, $r_i$ = requerimiento mínimo del nutriente $i$. El mismo esqueleto sirve para mezclas (combustibles, aleaciones): minimizar costo cumpliendo especificaciones.

El balance de inventario: la estrella de la I1

Cuando el problema tiene periodos ($t=1,\dots ,T$), aparece la restricción más importante de la I1: el balance de inventario. Con $I_t$ = inventario al final del periodo $t$, $P_t$ = producción y $d_t$ = demanda:

"Lo que había + lo que produzco = lo que despacho + lo que queda". Es una conservación: el flujo entra y sale de cada periodo. Se define un inventario inicial $I_0$ (dato) y muchas veces se acota o fija $I_T$.

Extensiones típicas

• Capacidad de producción: $P_t\le C_t$.
• Costo de almacenar: sumar $h_t{I}_t$ en la FO (penaliza guardar).
• Ventanas de tiempo / no solapar tareas: binarias que activan periodos.
• Flujo de caja: un balance análogo pero con dinero en vez de unidades.

Elegir un subconjunto bajo una capacidad

La mochila (knapsack) elige un subconjunto de ítems para maximizar valor sin exceder una capacidad. Variable binaria $x_i\in \{0,1\}$ = "llevo el ítem $i$". Con valor $v_i$, peso $w_i$ y capacidad $W$:

Es un ILP (variables binarias). El patrón "elegir un subconjunto óptimo bajo un presupuesto/capacidad" reaparece en selección de proyectos, portafolios y cobertura. La integralidad lo lleva a resolverse con Branch & Bound.

Encender/apagar + cuánto producir

El unit commitment (producción eléctrica) decide qué plantas encender (binaria $y_{it}$) y cuánto producir en cada una (continua $p_{it}$). Es un MILP clásico: mezcla el interruptor binario con la cantidad continua vía big-M.

Si $y_{it}=0$, la planta está apagada y $p_{it}=0$; si $y_{it}=1$, produce entre su mínimo técnico ${\underline{P}}_i$ y su máximo ${\overline{P}}_i$. La FO suma costo fijo de encendido ($f_i{y}_{it}$) + costo variable ($c_i{p}_{it}$), y una restricción de satisfacer la demanda total por periodo.

Planificación de turnos

Cubrir la demanda de personal de cada periodo con la menor cantidad de trabajadores, respetando reglas laborales (horas máximas, días libres). En turnos cíclicos, un trabajador que entra en el turno $t$ cubre varios periodos consecutivos, así que la demanda del periodo $t$ se cubre sumando los turnos que "pasan por" $t$.

Dónde abrir y a quién sirve cada centro

El problema de localización (facility location) decide qué centros abrir (binaria $y_i$) y qué cliente atiende cada centro (variable $x_{ij}$), minimizando costo de apertura + costo de servicio/distancia. Es un MILP que combina costo fijo con asignación.

Las dos restricciones características

(1) Cada cliente asignado a exactamente un centro:

(2) Solo puedo asignar a un centro abierto (acoplamiento binaria-asignación):