Двойственный симплекс-метод

Величина оценки из двойственного плана показывает, на сколько возрастет максимальное значение целевой функции прямой задачи при увеличении количества заготовок соответствующего вида на 1 штуку.

Оптимальные двойственные оценки удовлетворяют всем условиям двойственной задачи. При этом минимальное значение целевой функции двойственной задачи, равное, совпадает с максимальным значением целевой функции исходной задачи.

Следовательно,.

Дадим экономическую интерпретацию двойственных оценок. Переменные и обозначают оценки единицы заготовок соответственно 2-го и 3-го видов соответственно. Эти оценки отличны от нуля, что означает, что заготовки 2-го и 3-го видов полностью используются при оптимальном плане производства обуви. и это означает, что заготовки 1-го вида используются не полностью при оптимальном плане производства обуви. Таким образом, двойственные оценки определяют дефицитность используемых фабрикой заготовок, т.е. заготовки 2-го и 3-го вида являются дефицитными, а заготовки 1-го вида – недефицитными.

Увеличение количества заготовок 2-го вида на 1 штуку приведет к тому, что появится возможность найти оптимальный план производства обуви, при котором общая стоимость изготовляемой обуви возрастет на ден.ед. и станет 18+1=19 ден.ед.

Аналогично, увеличение количества заготовок 3-го вида на 1 штуку приведет к тому, что появится возможность найти оптимальный план производства обуви, при котором общая стоимость изготовляемой обуви возрастет на ден.ед. и станет 18+1=19 ден.ед.

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

(2.55)

,(2.56)

,. (2.57)

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

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

Дата добавления: 2013-12-13