Сниженная стоимость

В линейном программировании приведенные затраты или альтернативные издержки — это величина, на которую коэффициент целевой функции должен улучшиться (т. е. увеличиться для задачи максимизации, уменьшиться для задачи минимизации), прежде чем соответствующая переменная сможет принять положительное значение. в оптимальном решении. Именно стоимость увеличения переменной на небольшую величину, т. е. первую производную от определенной точки многогранника , ограничивает задачу. Когда точка является вершиной многогранника, переменную с наибольшей стоимостью, отрицательной для минимизации и положительной максимизации, иногда называют самым крутым ребром .

Учитывая систему минимизации $\mathbf {c} ^{T}\mathbf {x}$ при условии $\mathbf {Ax} \leq \mathbf {b} ,\mathbf {x} \geq 0$вектор приведенной стоимости можно вычислить как $\mathbf {c} -\mathbf {A} ^{T}\mathbf {y}$, где $\mathbf {y}$ – вектор двойной стоимости.

Из этого непосредственно следует, что для задачи минимизации любые небазисные переменные на своих нижних границах со строго отрицательными приведенными затратами имеют право войти в этот базис, в то время как любые базовые переменные должны иметь приведенную стоимость, равную точно 0. Для задачи максимизации небазисные переменные на своих нижних границах, которые имеют право войти в базис, имеют строго положительную приведенную стоимость.

Интерпретация

В случае, когда x и y оптимальны, приведенные затраты могут помочь объяснить, почему переменные достигают того значения, которое они имеют. Для каждой переменной соответствующая сумма этих величин дает приведенную стоимость, показывающую, какие ограничения заставляют переменную увеличиваться и уменьшаться. Для неосновных переменных расстояние до нуля дает минимальное изменение целевого коэффициента для изменения вектора решения x.

В разворотной стратегии

В принципе, хорошей стратегией разворота было бы выбрать ту переменную, которая имеет наибольшую приведенную стоимость. Однако самый крутой край в конечном итоге может оказаться не самым привлекательным, поскольку край может быть очень коротким, что дает лишь небольшое улучшение значения объектной функции. С вычислительной точки зрения другая проблема заключается в том, что для вычисления самого крутого края необходимо вычислять внутренний продукт для каждой переменной в системе, что во многих случаях делает вычислительные затраты слишком высокими. Алгоритм Devex пытается преодолеть последнюю проблему, оценивая приведенные затраты, а не вычисляя их на каждом шаге поворота, используя тот факт, что шаг поворота не может существенно изменить приведенные затраты всех переменных.

В линейном программировании

ПРИМЕЧАНИЕ. Это прямая цитата с веб-сайта, ссылка на который приведена ниже:«С каждой переменной связано значение приведенной стоимости. Однако приведенное значение стоимости не равно нулю только тогда, когда оптимальное значение переменной равно нулю. Несколько интуитивный способ думать о переменной приведенной стоимости — это думать о ней как о показателе насколько стоимость действия, представленного переменной, должна быть снижена, прежде чем какое-либо из этих действий будет выполнено. Точнее,

... значение приведенной стоимости указывает, насколько должен быть улучшен коэффициент целевой функции соответствующей переменной, прежде чем значение переменной станет положительным в оптимальном решении.

В случае задачи минимизации «улучшение» означает «уменьшение». Итак, в случае задачи минимизации затрат, где коэффициенты целевой функции представляют собой затраты на единицу деятельности, представленные переменными, коэффициенты «приведенных затрат» указывают, насколько каждый коэффициент затрат должен быть уменьшен, прежде чем деятельность, представленная соответствующей переменной, будет экономически эффективной. В случае задачи максимизации «улучшение» означает «увеличение». В этом случае, например, коэффициент целевой функции может представлять собой чистую прибыль на единицу деятельности. Приведенное значение затрат показывает, насколько должна быть увеличена рентабельность деятельности, чтобы деятельность выполнялась в оптимальном решении. Единицы значений приведенных затрат такие же, как и единицы соответствующих коэффициентов целевой функции.

Если оптимальное значение переменной положительное (не ноль), то приведенная стоимость всегда равна нулю. Если оптимальное значение переменной равно нулю и приведенная стоимость, соответствующая этой переменной, также равна нулю, то существует по крайней мере еще один угол, который также находится в оптимальном решении. Значение этой переменной будет положительным в одном из других оптимальных углов».

См. также

• Линейное программирование
• Теневая цена