En la 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 pequeña cantidad, es decir, la primera derivada de un cierto punto en el poliedro lo que restringe el problema. Cuando el punto es un vértice en el poliedro, la variable con el costo más extremo, negativamente para la minimización y positivamente para la maximización, a veces se denomina borde más empinado .
Dado un sistema minimizar sujeto a , el vector de costo reducido se puede calcular como , dónde es el vector de costo dual.
De ello se deduce directamente que para un problema de minimización, cualquier variable no básica en sus límites inferiores con costos reducidos estrictamente negativos son elegibles para ingresar a esa base, mientras que cualquier variable básica debe tener un costo reducido que es exactamente 0. Para un problema de maximización, el las variables no básicas en sus límites inferiores que son elegibles para ingresar a la base tienen un costo reducido estrictamente positivo.
Interpretación
Para el caso donde xey son óptimos, los costos reducidos pueden ayudar a explicar por qué las variables alcanzan el valor que tienen. Para cada variable, la suma correspondiente de ese material da el costo reducido muestra qué restricciones fuerzan 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 del objeto para cambiar el vector solución x.
En estrategia de pivote
En principio, una buena estrategia de pivote sería seleccionar la variable que tenga el mayor costo reducido. Sin embargo, el borde más empinado podría no ser en última instancia el más atractivo, ya que el borde puede ser muy corto, lo que permite solo 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 empinado, 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 los costos reducidos de todas las variables de manera espectacular.
En programación lineal
NOTA: Esta es una cotización directa del sitio web vinculado a continuación: "Asociado con 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 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.
... el valor de costo reducido indica cuánto debe mejorarse 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". Entonces, 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 tendría que reducirse cada coeficiente de costo antes de la la actividad representada por la variable correspondiente sería 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 el beneficio neto por unidad de actividad. El valor de coste reducido indica cuánto debería aumentarse la rentabilidad de la actividad para que la actividad se produzca en la solución óptima. Las unidades de los valores de costo reducido son las mismas que las unidades de los coeficientes de función objetivo correspondientes.
Si el valor óptimo de una variable es positivo (no cero), entonces el costo reducido es siempre cero. Si el valor óptimo de una variable es cero y el costo reducido correspondiente a la variable también es cero, entonces hay al menos otra esquina que también está en la solución óptima. El valor de esta variable será positivo en una de las otras esquinas óptimas ". [1]
Ver también
Referencias
- ^ "Interpretación de soluciones LP - costo reducido" . Courses.psu.edu . Consultado el 8 de agosto de 2013 .