Costo reducido

En programación lineal , el costo reducido , o costo de oportunidad , es la cantidad en la que un coeficiente de función objetivo tendría que mejorar (por lo tanto, aumentar para el problema de maximización, disminuir para el problema de minimización) antes de que sea posible que una variable correspondiente asuma un valor positivo en la solución óptima. Es el costo de aumentar una variable en una cantidad pequeña, es decir, la primera derivada a partir de un cierto punto en el poliedro que restringe el problema. Cuando el punto es un vértice en el poliedro, la variable con el costo más extremo, negativo para la minimización y positivo para la maximización, a veces se denomina la arista más empinada .

Dado un sistema minimizado sujeto a , el vector de costo reducido se puede calcular como , donde es el vector de costo dual. ${\displaystyle \mathbf {c} ^{T}\mathbf {x} }$${\displaystyle \mathbf {Ax} \leq \mathbf {b} ,\mathbf {x} \geq 0}$${\displaystyle \mathbf {c} -\mathbf {A} ^{T}\mathbf {y} }$${\displaystyle \mathbf {y} }$

De ello se desprende directamente que, para un problema de minimización, todas las variables no básicas en sus límites inferiores con costos reducidos estrictamente negativos son elegibles para ingresar a esa base, mientras que todas las variables básicas deben tener un costo reducido que sea exactamente 0. Para un problema de maximización, las variables no básicas en sus límites inferiores que son elegibles para ingresar a la base tienen un costo reducido estrictamente positivo.

En el caso en que x e y son óptimas, los costos reducidos pueden ayudar a explicar por qué las variables alcanzan el valor que alcanzan. Para cada variable, la suma correspondiente de esos elementos da el costo reducido que muestra qué restricciones fuerzan a la variable hacia arriba y hacia abajo. Para las variables no básicas, la distancia a cero da el cambio mínimo en el coeficiente objetivo para cambiar el vector de solución x.

En principio, una buena estrategia de pivote sería seleccionar la variable que tenga el mayor costo reducido. Sin embargo, el borde más pronunciado podría no ser en última instancia el más atractivo, ya que podría ser muy corto, lo que solo ofrecería una pequeña mejora del valor de la función del objeto. Desde un punto de vista computacional, otro problema es que para calcular el borde más pronunciado, se debe calcular un producto interno para cada variable en el sistema, lo que hace que el costo computacional sea demasiado alto en muchos casos. El algoritmo Devex intenta superar este último problema estimando los costos reducidos en lugar de calcularlos en cada paso de pivote, aprovechando que un paso de pivote podría no alterar drásticamente los costos reducidos de todas las variables.

NOTA: Esta es una cita directa del sitio web vinculado a continuación: "Asociado a cada variable hay un valor de costo reducido. Sin embargo, el valor de costo reducido solo es distinto de cero cuando el valor óptimo de una variable es cero. Una forma algo intuitiva de pensar en la variable de costo reducido es pensar en ella como un indicador de cuánto debe reducirse el costo de la actividad representada por la variable antes de que se realice alguna de esas actividades. Más precisamente,

... el valor del costo reducido indica cuánto se debe mejorar el coeficiente de la función objetivo en la variable correspondiente antes de que el valor de la variable sea positivo en la solución óptima.

En el caso de un problema de minimización, "mejorado" significa "reducido". Por lo tanto, en el caso de un problema de minimización de costos, donde los coeficientes de la función objetivo representan el costo unitario de las actividades representadas por las variables, los coeficientes de "costo reducido" indican cuánto se debería reducir cada coeficiente de costo para que la actividad representada por la variable correspondiente fuera rentable. En el caso de un problema de maximización, "mejorado" significa "aumentado". En este caso, donde, por ejemplo, el coeficiente de la función objetivo podría representar la ganancia neta por unidad de la actividad, el valor del costo reducido indica cuánto se debería aumentar la rentabilidad de la actividad para que la actividad se realice en la solución óptima. Las unidades de los valores de costo reducido son las mismas que las unidades de los coeficientes de la función objetivo correspondiente.

"Si el valor óptimo de una variable es positivo (distinto de cero), entonces el coste reducido siempre es cero. Si el valor óptimo de una variable es cero y el coste reducido correspondiente a la variable también es cero, entonces hay al menos otro vértice que también está en la solución óptima. El valor de esta variable será positivo en uno de los otros vértices óptimos". ^[1]

• Programación lineal
• Precio sombra