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

редактировать

концепция в линейном программировании и математической оптимизации

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

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

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

Содержание

1 Интерпретация
2 В стратегии поворота
3 В линейном программировании
4 См. Также
5 Ссылки

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

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

В стратегии поворота

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

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

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

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

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

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

См. Также

Ссылки