Programación lineal, rango de precio sombra

Question

No estoy seguro de cómo determinar el rango para el cual un precio sombra es válido.

Tal vez puedas ir directamente a la pregunta aquí.

Me han introducido a esto usando el siguiente enfoque en 2D.

Contexto

Dada una solución óptima que está en una esquina, hay dos líneas que se intersectan. Digamos que esas líneas representan las siguientes desigualdades

\begin{equation} \begin{aligned} 2K + 3S & \leq 10 \\ K + 2S & \leq 6 \\ Z & = 30K + 50S \end{aligned} \end{equation}

Entonces el precio sombra es el cambio en la función objetivo, $Z$, cuando el lado derecho de una desigualdad se cambia por una unidad.

Calcular esto para la segunda ecuación se hace de la siguiente manera:

\begin{equation} \begin{aligned} 2K + 3S & \leq 10 \\ K + 2S & \leq 6 + \Delta\\ \end{aligned} \end{equation}

Luego restando la segunda ecuación de la primera dos veces

\begin{equation} \begin{aligned} S & = 2 + 2 \Delta \end{aligned} \end{equation}

Por lo tanto

\begin{equation} \begin{aligned} K &= 2 - 3 \Delta \end{aligned} \end{equation}

Y la función objetivo se puede escribir como

\begin{equation} \begin{aligned} 30K + 50S &= 30(2 - 3 \Delta) + 50(2 + 2\Delta) \\ &= 160 + 10 \Delta \end{aligned} \end{equation}

Y el precio sombra se encuentra a partir de $z(1) - z(0)$, donde $z(\Delta) = 160 + 10 \Delta$ lo cual da $10$.

Por lo tanto el precio sombra es 10.

Pero ¿cómo calculo el rango para el cual esto es válido? Puedo resolver el álgebra aquí bastante fácilmente, pero tiene poco significado.

Pregunta

¿Cómo determino el rango para el cual puedo ajustar la segunda desigualdad de manera que la diferencia hecha a la función objetivo sea $10 \times \text{ajuste}$.

Answer 1

El precio sombra formalmente no es el aumento en la función objetivo al relajar una restricción en una unidad, sino al relajarla infinitesimalmente. En el mundo de la programación lineal, puede ser válido para una unidad, pero no necesariamente. En tu problema de ejemplo, de hecho no lo es. Esto queda más claro cuando usamos imágenes.

Voy a asumir que estabas maximizando, no minimizando tu función objetivo y además que tienes dos restricciones adicionales que en realidad no habías mencionado:

$K\geq0$ y $S\geq0$

Eso resultaría en el siguiente gráfico con K en el eje y y S en el eje x, y el óptimo en el punto rojo. Las líneas punteadas negras son isoquentas de Z, para Z=100, Z=150 y Z=200.

La región factible está formada por los ejes x e y, la línea azul desde el eje y hasta la intersección, y la línea naranja desde ese punto en adelante hasta el eje x.

Ahora relajemos tu restricción $K+2S\leq6$ en una unidad, como propones. En esencia eso significa que la restricción se convierte en $K+2S\leq7$ y al dibujar las nuevas restricciones obtenemos:

Resulta que la nueva restricción ya no juega un papel en determinar el óptimo. Ahora el óptimo está determinado por las restricciones: $S\geq0$ y $2K+3S\leq10$.

La respuesta a tu pregunta debería estar clara ahora: el precio sombra es válido hasta el punto en que esa combinación particular de restricciones continué determinando el óptimo. En este caso, eso significa que puedes aumentar 6 a $6\frac{2}{3}$, con un aumento correspondiente en la función objetivo de $10*\frac{2}{3}=\frac{20}{3}$. Después de ese punto, la combinación de restricciones ya no determina el óptimo.

Como punto adicional, déjame agregar que al menos el Solver de Excel (y espero que muchos otros solvers también) informan hasta qué punto puedes relajar las restricciones antes de que el óptimo sea determinado por otro conjunto de restricciones.