5. Определение двойственных оценок
Каждая из задач I и II является самостоятельной задачей линейного программирования и может решаться независимо друг от друга. Однако замечательным свойством симплексного метода является то, что решение прямой задачи I автоматически приводит и к решению двойственной задачи II.
Решение задачи II, то
есть значения двойственных оценок
можно найти непосредственно из последней
(индексной) строки симплекс-таблицы,
оптимальной для прямой задачи I. Искомые
значения
равны взятым
с противоположными знаками элементам,
лежащим на пересечении индексной строки
и столбцов, соответствующих дополнительным
переменными.
6. Пример:
В качестве примера
определим двойственные оценки
для сырья трех видов и проведем анализ
оптимального плана выпуска изделий А
и В для
производственной задачи, об использовании
сырья, рассмотренной в п. 2 темы 2.
Двойственная задача II формулируется следующим образом. Условия производства описываются системой из n = 2 неравенств c m = 3 неизвестными
Общая стоимость сырья на производстве определяется целевой функцией
Требуется найти удовлетворяющие системе неравенств (18) и обеспечивающие минимум функции (19).
При решении прямой
задачи I получена оптимальная
симплекс-таблица 3. На пресечении
индексной строки этой таблицы и столбцов
для дополнительных переменных
находим значения двойственных оценок
Чтобы убедиться в правильности их вычисления подставим полученные значения в выражение (19) для целевой функции Z, откуда имеем
руб.
Решение двойственных задач представляет интерес при планировании работы предприятий. Так как план производства и оценки ресурсов являются оптимальными тогда и только тогда, когда цена производственной продукции и суммарная оценка ресурсов совпадают, можно использовать двойственные оценки как инструмент балансирования затрат и результатов.
При решении двойственной
задачи были получены следующие результаты
: сырье 1 – го и 2 – го видов, полностью
используемые по оптимальному плану
производства, имеют положительные
оценки
,
а сырье 3 – го типа, не полностью
используемое, имеет нулевую оценку :
.
Таким образом положительную оценку имеют лишь те виды сырья, которые полностью используются при оптимальном плане производства. Поэтому двойственные оценки определяют дефицитность используемого сырья. Величина двойственной оценки показывает, насколько возрастет максимальное значение целевой функции F прямой задачи при увеличении количества сырья соответствующего вида на один кг. Так, увеличение сырья I вида на один килограмм приведет к тому, что появится возможность найти новый оптимальный план производства, при котором общая стоимость F возрастет на 24 руб.
При этом числа в столбце,
соответствующем
в табл. 3, показывают, что указанное
увеличение F
может быть достигнуто за счет увеличения
выпуска изделий вида A на 4/5 ед. и сокращения
выпуска изделий вида В на 3/5 ед. В
следствие этого остатки используемого
сырья 3 вида возрастут та 1 кг. Точно так
же увеличение на 1 кг. сырья, 2-го вида
позволит найти новый оптимальный план,
при котором общая стоимость F
возрастет на 4 руб. Это будет достигнуто
за счет увеличения выпуска изделий вида
В на 2/5 ед. и уменьшения изделий А на 1/5
ед. причем остатки используемого сырья
3 вида сократятся на 1 кг. При увеличении
на 1 кг. сырья 3 вида общая стоимость F
не изменится. Это означает, что сырье 3
вида не дефицитное. На практике сырье
каждого вида целесообразно изменять
таким образом, что бы добавочная продукция
составила целое число единиц.
7. Анализ устойчивости двойственных оценок
Двойственные оценки сырья можно использовать, чтобы определить меру влияния изменения запасов сырья на величину максимума выпуска продукции, чтобы выявить «узкие» места производства и установить направление мероприятий по изменению ресурсов, обеспечивающих поучение наибольшего экономического эффекта. Представляет также интерес определить интервалы изменения сырья, в которых оптимальный план двойственной задачи не меняется. Такое исследование называется анализом устойчивости двойственных оценок. Для этого используют следующую процедуру.
Составляют матрицу А
из элементов столбцов соответствующих
переменным
в табл. 3, определяющей оптимальный план
производства :
,
Умножают матрицу А на
вектор
,
где 400, 900, 600 – запасы сырья соответственно
1, 2, 3 - го вида :
- предполагаемое изменение соответствующего
вида сырья.
Запишем условия неотрицательности компонент полученного в результате вектора :
Определим, при каких
значениях
эта система неравенств верна. Очевидно,
если
,
то
.
Это означает, что если количество сырья
3 вида будет уменьшено в пределах 100 кг,
или увеличено произвольным образом, то
несмотря на это, двойственные оценки
сырья не изменятся.
Если
,
то решая систему (20), получим
.
Если
,
то
.
Это означает, что, если количество одного
из видов сырья 1 или 2 вида принадлежит,
соответственно, промежутку
или
,
а количество остальных ресурсов является
первоначальным, то двойственные оценки
сырья не меняются.
Если
изменяются одновременно, то для
исследования влияния этого изменения
на оптимальный план необходимо определить
многогранник решений системы линейных
неравенств (20). Точки этого многогранника
определяют количество сырья каждого
вида, при которых двойственные оценки
остаются прежними.
Предположим, что в
рассматриваемой задаче изменения сырья
составляют
кг.,
кг. и
кг. Определим, как
при этом изменится оптимальный план,
стоимость готовой продукции F
и двойственные оценки сырья. Подставим
в (20). Так как все неравенства остаются
верными, это означает, что двойственные
оценки сырья не изменятся :
.
В этом случае изменение стоимости
готовой продукции составит
(руб.).
т.е. стоимость готовой продукции по новому оптимальному плану равна F=18400 (руб.). Соответствующий план производства найдем следующим образом. Система ограничений, описывающих новые условия производства, примет вид :
Так как
и
,
сырье 1-го и 2-го вида используется
полностью. Поэтому 1-е и 2-е условия
выполняются как равенства. Решая
совместно систему
получим новый оптимальный
план производства
ед.;
ед.
При этом остатки сырья составляют
кг.
Если при изменении объемов сырья меняются двойственные оценки, т.е. при подстановке в систему (20) неравенства становятся неверными, то формулируется новая производственная задача, которая может быть решена описанным выше симплекс-методом.