Optimización y decisiones bajo restricciones

Una actividad con mayor valor por tarea no siempre merece todos los recursos. Puede consumir en exceso un material escaso, dejar horas sin usar o desplazar otra actividad que, combinada con la primera, logra un resultado mejor. Para elegir hace falta comparar combinaciones completas, no sólo ordenar tareas por una cifra.

La optimización convierte esa comparación en un problema explícito. Describe las acciones admitidas, las consecuencias que se valoran y los límites que deben respetarse. Una solución óptima es la mejor según esa descripción. Si se omitió una condición decisiva o se eligió un criterio inadecuado, la exactitud matemática no corrige la decisión. El interés del método reside también en mostrar dónde se produce la compensación y qué cambio podría alterar la recomendación.

129.1. Objetivos, variables y restricciones#

Ejemplo construido. Un taller puede completar tareas de tipo A o B durante una jornada. Cada A requiere dos horas de trabajo y una unidad de material; cada B requiere tres horas y dos unidades. Hay dieciocho horas de trabajo disponibles, sumadas entre quienes trabajan, y diez unidades de material. Se asignan tres puntos de valor a cada A y cinco a cada B. Los puntos son una valoración del ejemplo, no una medida universal de utilidad.

Sean $x$ y $y$ los números de tareas A y B. El valor total es $3x+5y$. Las restricciones de trabajo y material son

con $x\ge 0$ e $y\ge 0$. Los coeficientes de la primera desigualdad representan horas por tarea; los de la segunda, material por tarea. Los lados derechos son capacidades disponibles. Las tareas son indivisibles, por lo que también debería exigirse que $x$ e $y$ sean enteros. Para estudiar la geometría se permitirá primero cualquier cantidad real no negativa; luego se comprobará la integridad del resultado.

Las variables de decisión son aquello que se elige: aquí, las cantidades de cada tarea. Los coeficientes y capacidades son parámetros del problema, tratados inicialmente como conocidos. La función objetivo asigna a cada decisión un valor que se desea maximizar o minimizar. Las restricciones describen las decisiones admisibles. Esta separación permite distinguir mejorar una elección de revisar los datos o los criterios que la definen. (Boyd y colaboradores, formulación de problemas de optimización).

Una condición de seguridad o un mínimo de servicio no tiene por qué incorporarse como otro término del objetivo. Puede fijarse como requisito que ninguna solución debe violar. Sustituir un requisito por una penalización significa admitir que cierta mejora del objetivo podría compensar su incumplimiento. Esa equivalencia necesita una decisión sustantiva; no procede automáticamente del uso de una fórmula.

Los límites también deben corresponder al funcionamiento real. Sumar dieciocho horas supone que se pueden distribuir sin conflictos adicionales de horario, especialidad o equipos. La disponibilidad total no garantiza que una secuencia concreta sea ejecutable. Una misma persona no puede realizar simultáneamente dos tareas; una operación puede requerir que otra termine antes. Si esas condiciones importan, deben figurar en el modelo y pueden cambiar su dificultad.

Un problema puede admitir muchas soluciones, una sola o ninguna. Si se exige completar al menos diez tareas A, serían necesarias veinte horas; el taller de dieciocho horas no podría satisfacerlo. La ausencia de una solución factible no se arregla buscando con más paciencia. Exige revisar qué requisito puede cambiar, incorporar recursos o reconocer incompatibilidad. Conviene conservar qué condición fue relajada: declarar éxito después de borrarla ocultaría el problema original.

129.2. Óptimos locales, globales y fronteras factibles#

El conjunto factible reúne todas las decisiones que satisfacen las restricciones. En el plano del taller, cada punto $(x,y)$ representa una combinación. La restricción de horas deja los puntos debajo de la recta $2x+3y=18$, y la de material los puntos debajo de $x+2y=10$. Junto con la no negatividad, forman un polígono con vértices $(0,0)$, $(9,0)$, $(6,2)$ y $(0,5)$.

El cruce $(6,2)$ se obtiene resolviendo ambas igualdades: seis tareas A y dos B consumen dieciocho horas y diez unidades. Su valor es veintiocho puntos. Nueve A producen veintisiete; cinco B, veinticinco. Una combinación usa mejor las capacidades porque el recurso que limita cada alternativa pura no es el mismo. Producir sólo B deja horas disponibles; producir sólo A deja una unidad de material.

Las rectas $3x+5y=c$ unen decisiones con igual valor $c$. Desplazarlas hacia valores crecientes permite ver dónde dejan de tocar el conjunto factible. En este caso, el último contacto ocurre en $(6,2)$. El dibujo orienta, pero una prueba algebraica elimina la necesidad de confiar en su precisión. Sumando las dos restricciones,

Toda decisión factible está acotada por veintiocho. Como $(6,2)$ lo alcanza, es un óptimo global: ninguna otra decisión admitida mejora el objetivo. La solución también es entera, por lo que el permiso provisional de usar fracciones no alteró aquí el óptimo del problema original. La cota y una decisión que la alcanza constituyen un certificado de optimalidad.

Un óptimo local sólo mejora o iguala las decisiones factibles suficientemente cercanas. En problemas no convexos, otra región puede ofrecer un resultado mejor. La cercanía debe definirse de acuerdo con las variables y operaciones posibles. En una selección discreta, no mejorar al cambiar una sola tarea no demuestra que sustituir dos o más tareas conjuntamente sea inútil.

La convexidad proporciona una garantía especial. Un conjunto es convexo si conserva todo el segmento entre dos de sus puntos. Para minimizar, una función convexa no supera, sobre ese segmento, la interpolación de los valores de sus extremos. Si existe un punto mejor que un supuesto mínimo local, moverse un poco hacia él seguiría siendo factible y reduciría el objetivo; eso contradice la optimalidad local. Por ello, en un problema de minimización con objetivo y conjunto factible convexos, todo mínimo local es global. Para maximizar se usa la propiedad correspondiente de concavidad. (Boyd, Vandenberghe y Nobel, convexidad y optimalidad).

Esta garantía no asegura que exista solución ni que sea única. Minimizar $z$ para $z>0$ permite valores cada vez más próximos a cero, pero no alcanzar cero. Minimizar $z$ sin límite inferior ni otras restricciones no tiene un valor mínimo finito. En cambio, una función continua sobre un conjunto factible no vacío, cerrado y acotado en un espacio de dimensión finita alcanza mínimo y máximo. Es una condición suficiente de existencia, no una condición necesaria de todos los problemas.

Una derivada nula tampoco resuelve cualquier optimización. Puede señalar un máximo, un mínimo o un punto que no sea ninguno; además, un óptimo restringido puede hallarse en la frontera. En el taller, el objetivo lineal no tiene un punto interior donde se anule su pendiente. El límite lo crean las restricciones. Buscar sólo ceros de derivadas ignoraría precisamente el mecanismo que decide el resultado.

129.3. Programación lineal, dinámica y heurísticas#

La programación lineal utiliza objetivos y restricciones lineales o afines con variables continuas. «Programación» significa aquí planificar matemáticamente, no sólo escribir código. Su forma matricial compacta organiza muchos recursos y actividades: si $\mathbf{z}$ reúne las cantidades, $A\mathbf{z}\le \mathbf{b}$ expresa capacidades y ${\mathbf{c}}^{\mathsf{T}}\mathbf{z}$ el objetivo. La matriz $A$ contiene los consumos por actividad, $\mathbf{b}$ las capacidades y $\mathbf{c}$ los valores por unidad de actividad; el superíndice $\mathsf{T}$ indica transposición para formar la suma ponderada. Cada fila de $A$ corresponde a una restricción; sus coeficientes deben conservar las unidades de esa fila.

Para un polígono factible no vacío y acotado, un objetivo lineal alcanza un óptimo en algún vértice. Si es paralelo a un borde que alcanza el valor óptimo, puede haber todo un segmento de óptimos. El taller muestra cómo examinar vértices en dos dimensiones, pero enumerar todas las esquinas deja de ser un procedimiento práctico al crecer el problema. Los métodos numéricos explotan estructura algebraica; aun así, deben comprobarse factibilidad, precisión y cualquier garantía que acompañe al resultado.

Exigir variables enteras cambia el conjunto. Resolver primero el problema continuo puede proporcionar una cota: al maximizar, permitir más decisiones no puede reducir el mejor valor. Pero redondear su solución no garantiza conservar factibilidad ni alcanzar el mejor entero. Si dos cantidades de unidades indivisibles deben sumar exactamente tres, redondear por separado $1,5$ y $1,5$ hacia dos viola esa igualdad. Una relajación ayuda a acotar o guiar la búsqueda; no sustituye la condición original. (Boyd, Vandenberghe y Nobel, relajaciones).

La programación dinámica organiza un problema mediante estados y subproblemas que se reutilizan. Su utilidad requiere que el estado conserve la información necesaria para las decisiones posteriores. El principio de optimalidad afirma que, después de una decisión, la continuación de una solución óptima debe ser óptima para el subproblema correspondiente. Si pudiera sustituirse por una continuación mejor sin alterar las condiciones relevantes, la solución completa no sería óptima. (Dimitri Bertsekas, principio de optimalidad y estados).

Ejemplo construido. Hay cuatro unidades de presupuesto y tres proyectos indivisibles. A cuesta tres y aporta cinco puntos; B y C cuestan dos y aportan tres puntos cada uno. Cada proyecto puede realizarse una sola vez y los valores se suman. Elegir el mayor valor por unidad de coste lleva primero a A, cuya razón es $5/3$, superior a $3/2$ de B o C. Queda una unidad que no alcanza para otro proyecto: valor cinco. Elegir B y C usa cuatro y aporta seis. La mejor razón individual ha producido una decisión inferior.

Para resolverlo sistemáticamente, sea $F(j,b)$ el mayor valor usando sólo los primeros $j$ proyectos y presupuesto entero disponible $b$. Sean $c_j$ y $v_j$ el coste y valor del proyecto $j$. Si cabe,

La primera opción omite el proyecto; la segunda lo incluye y deja un subproblema con menos presupuesto. Si $b<c_j$, sólo se usa la primera. Se parte de $F(0,b)=0$ para $b\ge 0$. Al considerar C con presupuesto cuatro, omitirlo da cinco; incluirlo da tres más $F(2,2)=3$, por lo que el resultado es seis. Guardar los valores evita recalcular las mismas combinaciones parciales.

La regla funciona porque los costes y valores son aditivos y el presupuesto restante, junto con qué proyectos siguen disponibles, determina el subproblema. Si B requiere haber completado A, o dos proyectos comparten un beneficio que no puede contarse dos veces, el estado y la recurrencia deben cambiar. Reducir la información del estado sin justificación puede hacer el cálculo rápido y equivocado. Tampoco toda programación dinámica es pequeña: el número de estados puede crecer mucho con las variables necesarias.

Una heurística busca buenas soluciones mediante reglas prácticas sin garantizar, en general, el mejor resultado. Ordenar por valor por coste es una de ellas en el problema indivisible anterior. Puede ser útil con límites de tiempo, pero debe comunicarse qué se sabe: factibilidad, valor alcanzado, comparación con alternativas y, si existe, una cota del óptimo. Para una maximización, una solución factible de valor ochenta y una cota superior de ochenta y dos dejan como máximo dos unidades de mejora posible. Sin cota, «no se encontró nada mejor» describe la búsqueda, no una demostración.

Un algoritmo de aproximación con garantía demostrada es distinto de una heurística sin ella. Su límite puede aplicarse sólo a una clase de problemas y a una definición concreta de calidad. En cualquier caso, el tiempo de cálculo debe relacionarse con la decisión: obtener un óptimo exacto después de que termine su utilidad puede ser peor operativamente que disponer a tiempo de una solución buena y verificable.

129.4. Decisiones multiobjetivo y compensaciones#

Muchos problemas no admiten una sola ordenación inmediata. Se desea reducir costes y retrasos, mejorar cobertura o evitar concentrar perjuicios. Una decisión domina a otra si no empeora ningún criterio y mejora al menos uno. Una decisión es eficiente de Pareto cuando ninguna otra decisión factible la domina. La frontera eficiente descarta alternativas superables bajo los criterios declarados; no elige automáticamente entre las restantes. (Boyd y Vandenberghe, optimización multicriterio, sección 4.7).

Ejemplo construido. Cuatro planes tienen pares coste-duración: U, $(8,6)$; V, $(9,5,5)$; W, $(10,4)$; y Z, $(12,5)$. El coste se mide en unidades presupuestarias comparables y la duración en semanas; se desea reducir ambos. W domina a Z, porque cuesta menos y termina antes. U, V y W no se dominan entre sí: reducir duración exige pagar más. La eficiencia no determina si una semana de mejora vale una o dos unidades presupuestarias.

Una suma ponderada convierte objetivos en una cifra, por ejemplo $C+\lambda T$, con coste $C$, duración $T$ y peso positivo $\lambda$ en unidades de coste por semana. La dimensión del peso hace explícito el intercambio aceptado. Cambiarlo puede seleccionar otro plan. Normalizar variables no elimina ese juicio: escoger la escala de normalización también modifica cuánto pesa cada cambio.

En el ejemplo, V nunca gana esa suma frente a U y W. Para costar menos que U en la suma necesitaría $\lambda >2$; para costar menos que W necesitaría $\lambda <2/3$. Ambas condiciones son incompatibles. V sigue siendo eficiente, pero una ponderación lineal positiva no lo selecciona. Las alternativas discretas o no convexas pueden tener puntos eficientes que ese procedimiento no recupera. Otras formulaciones, como minimizar duración bajo un límite de coste de nueve, sí pueden elegir V.

También se puede fijar un orden de prioridad: optimizar primero un criterio y, entre empates admitidos, el siguiente. Es una decisión diferente de permitir compensaciones continuas. Las prioridades, los márgenes de empate y las restricciones mínimas deben hacerse visibles. Cuando consecuencias recaen en personas distintas, mejorar un total puede ocultar una distribución desigual. La evaluación necesita datos y deliberación sobre esa distribución; llamar «óptimo» al total no establece por sí solo justicia o legitimidad.

Si una alternativa domina a otra sólo bajo las cifras centrales, la incertidumbre puede cambiar la comparación. Es útil distinguir dominación demostrada para las condiciones admitidas de ventaja nominal. Una frontera calculada con parámetros inciertos no debe presentarse como un límite físico inmutable. Puede señalar qué medición adicional, qué negociación o qué restricción merece atención.

129.5. Robustez frente a incertidumbre y cambio#

El óptimo del taller consume todas las horas previstas. Si una tarea B necesita cuatro horas en vez de tres, seis A y dos B requieren veinte, excediendo la capacidad. La solución nominal era exacta para sus parámetros, pero carecía de margen ante ese cambio. Robustez significa mantener propiedades relevantes frente a variaciones especificadas, no ser inmune a cualquier acontecimiento. Hay que declarar qué cambia, dentro de qué límites y qué debe preservarse.

Ejemplo construido. Se mantiene todo lo demás y se supone que cada B puede necesitar entre tres y cuatro horas. La decisión se fija antes de conocer la duración; se quiere garantizar factibilidad en todo ese intervalo. Como $y\ge 0$, el mayor consumo ocurre con cuatro horas por B. La restricción robusta se vuelve $2x+4y\le 18$. Implica $x+2y\le 9$, por lo que también respeta el límite de diez unidades de material.

Con esa restricción, $3x+5y\le 3x+6y=3(x+2y)\le 27$. Nueve A y cero B alcanzan veintisiete y cumplen todo; son un óptimo robusto, también entero. Se pierde un punto frente al óptimo nominal, pero se conserva la ejecución para las duraciones admitidas. La elección depende de que se valore esa garantía y de que el intervalo represente adecuadamente la incertidumbre. No protege frente a duraciones superiores a cuatro o falta de materiales. (Dimitris Bertsimas, optimización robusta).

La optimización estocástica plantea otro tratamiento: asigna probabilidades a escenarios y puede minimizar un coste esperado o imponer límites de riesgo. Una restricción sobre probabilidad de incumplimiento admite cierto riesgo y necesita un modelo de distribución. Proteger todos los escenarios de un conjunto no equivale a proteger una proporción de ellos. Un promedio favorable tampoco descarta una consecuencia extrema; el criterio debe corresponder a lo que se intenta controlar.

La sensibilidad estudia cómo cambia la solución o su valor al cambiar parámetros. Volviendo al taller nominal, si $H$ es el valor numérico de la capacidad expresada en horas y el material permanece en diez, el cruce de las restricciones da $x=2H-30$ e $y=20-H$. Para $15\le H\le 20$, estas cantidades son no negativas y el valor es $H+10$. La suma de restricciones lo acota por ese mismo valor, por lo que sigue siendo óptimo en el problema continuo. Una hora adicional vale un punto dentro de ese intervalo; después de veinte, el material impide seguir aumentando y diez A ya alcanzan treinta.

Ese valor marginal es una interpretación de los precios sombra asociados a restricciones, bajo condiciones apropiadas. No es una tarifa de mercado ni una garantía para cambios arbitrariamente grandes. En el problema entero, capacidades fraccionarias pueden impedir alcanzar el cruce calculado. Antes de usar un valor marginal hay que precisar intervalo de validez, unidades y posibilidad de redistribuir las decisiones. (Boyd, Vandenberghe y Nobel, análisis de sensibilidad).

Una decisión adaptable puede superar a una fija porque usa información que llega después. Pero no se puede atribuir a una acción inicial conocimiento del futuro. Al optimizar por escenarios debe distinguirse qué decisiones se toman antes y cuáles pueden revisarse luego. De lo contrario, el modelo obtiene una ventaja ficticia al escoger retrospectivamente la mejor acción para cada resultado.

La implementación exige comprobar las condiciones que hicieron factible la solución, registrar desviaciones y decidir cuándo recalcular. Un margen deliberado puede valer más que una pequeña mejora nominal si las capacidades son inestables. La matemática permite medir ese intercambio dentro del modelo. Elegir el objetivo, validar las restricciones y responder por las consecuencias sigue requiriendo conocimiento del sistema y decisiones que ningún algoritmo deduce sólo de una tabla.

Preguntas de transferencia#

¿Una solución factible demuestra que es la mejor?#

En el taller nominal, nueve A y cero B respetan las capacidades. ¿Basta esa comprobación para declararlas óptimas?

Mejor razón, peor conjunto#

Ejemplo construido. Un presupuesto de cuatro permite elegir un proyecto de coste tres y valor cinco o dos proyectos de coste dos y valor tres cada uno. ¿Por qué falla seleccionar primero la mejor razón valor-coste?

Una alternativa eficiente que no gana una suma#

En los planes U, V y W, ¿el hecho de que V nunca minimice una suma ponderada positiva demuestra que está dominado?

¿Robusto frente a qué?#

Ejemplo construido. El taller adopta nueve A para protegerse de la duración incierta de B. Luego sólo dispone de dieciséis horas. ¿Se incumplió la garantía matemática?

Fuentes y lecturas del capítulo#

Stephen Boyd, Steven Diamond, Enzo Busseti, Akshay Agrawal y Junzi Zhang. Convex Optimization Overview, diapositivas de Stanford. Consultadas para distinguir variables, objetivos y restricciones. La aplicación del taller y sus certificados algebraicos son construidos. (Documento).

Stephen Boyd y Lieven Vandenberghe. Convex Optimization, Cambridge University Press (2004), secciones 4.2 y 4.7. Consultadas para la relación entre optimalidad local y global y para dominación, eficiencia y limitaciones de las sumas ponderadas. (Libro abierto por los autores).

Stephen Boyd, Lieven Vandenberghe y Parth Nobel. Convex Optimization, diapositivas revisadas. Consultadas las secciones de problemas convexos, relajación y sensibilidad; complementan las garantías conceptuales sin convertirlas en una afirmación sobre cualquier problema no convexo. (Documento).

Dimitri Bertsekas. Dynamic Programming and Stochastic Control, lección 2, MIT (2015). Consultada para el principio de optimalidad, la necesidad de un estado suficiente y la reutilización de subproblemas. (Diapositivas).

Dimitris Bertsimas. Optimization Methods, lección 8, Robust Optimization, MIT (2009). Consultada para distinguir datos nominales, variaciones admitidas y protección de factibilidad. La garantía del ejemplo se deriva directamente de sus restricciones, sin utilizar probabilidades no especificadas. (Diapositivas).

Bibliografía de la parte XII · Bibliografía general

Última revisión editorial

29 de septiembre de 2026

Cierre de contenidos

29 de septiembre de 2026