Двойственная задача и экономическая интерпретация переменных двойственной задачи
Двойственная задача и экономическая интерпретация переменных двойственной задачи
Составим математическую модель двойственной задачи: минимизировать Z = 180y1 + 210y2 + 800y3 при ограничениях
При решении задачи «вручную» симплексным методом надо перейти к канонической форме, добавляя в каждое ограничение неотрицательную дополнительную переменную.
Запишем канонические формы прямой и двойственной задач в табл. 11.
Таблица 11
В канонической форме прямой задачи переменные х1, х2, х3, х4 являются основными, а переменные х5, х6, х7 – дополнительными. В канонической форме двойственной задачи основными переменными являются у1, у2, у3, а переменные у4, у5, у6, у7 – дополнительными.
Между переменными прямой и двойственной задачами существует взаимно-однозначное соответствие, которое представлено в табл. 12.
Таблица 12
| Основные переменные | Дополнительные переменные | |
| Прямая задача | х1, х2, х3, х4 | х5, х6, х7 |
| Двойственная задача | у4, у5, у6, у7 | у1, у2, у3 |
| Дополнительные переменные | Основные переменные |
Учитывая это соответствие, выпишем из последней строки симплекс-таблицы, содержащей оптимальное решение прямой задачи (табл. 10), координаты искомого вектора двойственной задачи Y*=(0; 3/2; 9/4; 0; 0; 1/2; 5).
При этом оптимальном плане первое ограничение прямой задачи выполняется как строгое неравенство: 95 + 2∙0 + 0 = 95 < 180. Это означает, что расход ресурса Р1 меньше его запаса на величину, равную 85, то есть ресурс Р1 – избыточный. Именно поэтому, в оптимальном плане Y* двойственная оценка этого ресурса y1* равна 0. А оценки ресурсов Р2 и Р3 выражаются положительными числами у2* = 3/2, у3* = 9/4, это свидетельствует о дефицитности этих ресурсов, они при оптимальном плане прямой задачи используются полностью (х6* = 0; х7* = 0).
Действительно, ограничения по этим ресурсам в прямой задаче выполняются как строгие равенства:
210 + 3∙0 + 2∙0 = 210,
4∙95 +2∙210 + 4∙0 = 800.
Поскольку 9/4 > 3/2, ресурс Р3 считается более дефицитным, чем ресурс Р2.
Экономическая интерпретация ограничений двойственной задачи
Для интерпретации ограничений двойственной задачи используем часть теоремы о равновесии:
.
Величина 
представляет суммарную стоимость ресурсов, используемых на производство единицы продукции j-го вида.
Величина 
, равная коэффициенту при переменной xj в последней строке симплекс табл. 10, определяющей оптимальное решение прямой задачи, называется приведенной стоимостью (приведенными издержками) j-го вида продукции.
Подставим значения 
в двойственную задачу:
получим:
На основании теоремы равновесия нетрудно понять почему не вошла в оптимальный план продукция вида С и D: третье и четвертое ограничение двойственной задачи выполняются как строгие неравенства. Это означает, что оценки ресурсов, расходуемых на изготовление единицы продукции вида С и D превышают цену единицы этой продукции на величину 0,5 и 5 соответственно. Продукцию вида С и D предприятию не выгодно выпускать.
Первое и второе ограничение двойственной задачи обращаются в точное равенство, то есть оценка израсходованных ресурсов для производства продукции вида А и В совпадает с ценой произведенной продукции.
Таким образом, в оптимальный план войдет только та продукция, которая выгодна предприятию и не войдет убыточная продукция. В этом проявляется рентабельность оптимального плана.
Анализ устойчивости двойственных оценок
Двойственные оценки связаны с оптимальным планом прямой задачи и всякое изменение исходных данных прямой задачи оказывает влияние на ее оптимальный план и на систему двойственных оценок. В свою очередь двойственные оценки служат инструментом анализа и принятия правильных решений в условиях изменившейся производственной ситуации.
По основной теореме двойственности, исходя из решения пары двойственных задач, мы видели, что объем различных видов продукции и оценки ресурсов являются оптимальными тогда и только тогда, когда общая стоимость произведенной продукции и суммарная оценка ресурсов совпадают:
. = Zmin
Таким образом, максимальное значение целевой функции прямой задачи можно рассматривать как функцию свободных членов системы линейных уравнений (ограничений):
.
Изменим незначительно запас i-го вида ресурса на величину 
, так, чтобы оптимальное решение двойственной задачи не изменилось. Тогда изменение минимальных затрат на ресурсы 
составит:
.
По основной теореме двойственности для оптимальных планов измененной задачи 
, значит и максимальная прибыль увеличится на величину 
, откуда 
.
При 
, получаем следующий вывод: двойственные оценки (теневые цены) ресурсов показывают, на сколько денежных единиц изменится максимальная прибыль от реализации продукции при изменении запаса соответствующего ресурса на одну единицу.
Таким образом, имеет место следующая теорема об оценках:
Двойственные оценки показывают приращение целевой функции, вызванное малым изменением свободного члена соответствующего ограничения задачи: 
.
В нашей задаче выше установлено, что ресурсы Р2 и Р3 являются дефицитными. Каждая дополнительная единица ресурса Р2 (
) обеспечит прирост максимального значения целевой функции на величину 
, а каждая дополнительная единица ресурса Р3 (
) обеспечит прирост выручки равный 
. Отсюда становится понятно, почему ресурс Р3 считается более дефицитным, по сравнению с ресурсом Р2, так как он содействует получению большей прибыли от реализации произведенной продукции.
Что же касается избыточного ресурса Р1, то увеличение его запаса не приводит к росту максимального значения функции, поскольку
.
То есть с помощью двойственных оценок можно определить степень влияния ограничений на значение целевой функции.
Таким образом, если получено оптимальное решение прямой задачи, то можно провести анализ устойчивости двойственных оценок относительно изменений bi .
Максимальное значение целевой функции 
при изменении отдельно взятого ресурса изменяется ровно на величину двойственной оценки этого ресурса, поэтому при изменении объема каждого ресурса bi на величину 
приращение прибыли составит: 
.
Но эта формула верна только при достаточно малых изменениях 
объемов ресурсов по сравнению с исходными 
.
Следовательно, интерес представляет определение интервалов изменения запасов ресурсов каждого вида, при которых не меняются двойственные оценки 
, т.е. сохраняется то же оптимальное решение двойственной задачи.
Наиболее компактный способ записи вычислений, производимых симплекс-методом заключается в использовании матриц.
Расширенная матрица 
нашей задачи имеет вид:
,
где 
– вектор-столбец свободных членов
Известно, что для нахождения оптимального решения задачи линейной оптимизации, достаточно рассматривать только базисные решения системы линейных уравнений, поэтому выпишем матрицу D из тех столбцов матрицы , которые соответствуют базисным переменным:
D 
.
Матрица D
образована последними тремя столбцами в последней симплексной таблице (табл. 10):
D 
.
Симплексные таблицы на каждом шаге совершают преобразования однократного замещения одной из базисных переменных, и эти преобразования приводят исходную симплексную форму задачи к конечной, дающей оптимальное решение. Можно показать, что эти преобразования эквивалентны умножению обратной матрицы D на расширенную матрицу :
D
*
=
.
Отсюда видно, что новый столбец свободных членов получается простым умножением матрицы D на исходный столбец свободных членов B.
Рассмотрим произвольное изменение объемов ресурсов исходной задачи 
, т.е. измененный вектор-столбец свободных членов будет иметь вид:
При тех же симплексных преобразованиях часть системы, за исключением столбца свободных членов не изменяется. Новое базисное решение остается допустимым, т.е. оптимальным при измененных ресурсах, если все его компоненты не отрицательны.
Итак, условие D
определяет область устойчивости двойственных оценок в зависимости от 
.
Двойственные оценки ресурсов можно использовать, чтобы определить меру влияния изменения запасов ресурсов на величину максимума выпуска продукции, чтобы выявить “узкие” места производства и установить направление мероприятий по изменению ресурсов, обеспечивающих получение наибольшего экономического эффекта. Определим интервалы изменения ресурсов, в которых оптимальный план двойственной задачи не меняется. Такое исследование называется анализом устойчивости двойственных оценок.
Проведем анализ устойчивости двойственных оценок для нашего примера:
1. Составляем матрицу D из элементов столбцов, соответствующих дополнительным переменным 
табл. 10, определяющей оптимальный план производства:
D .
2. Умножаем матрицу D на вектор 
,
где 180, 210, 800 – запасы ресурсов соответственно I, II и III типов, а 
– предполагаемое изменение соответствующих ресурсов.
Условие D определяет область устойчивости двойственных оценок в зависимости от 
:
D
(4)
3. Определяем, при каких значениях координаты полученного вектора неотрицательны.
Очевидно, если 
и 
, то 
.Это означает, что если количество ресурсов I типа будет увеличено или даже уменьшено в пределах 85 единиц, то план 
остается оптимальным планом двойственной задачи
Если 
и , то
.
Аналогично, если и , то 
.
Таким образом, если количество ресурсов одного из типов сырья II и III принадлежат соответствующему промежутку:
, 
,
, 
,
а количество ресурса I вида остается неизменным, то двойственная задача имеет один и тот же оптимальный план . И если предполагаемые изменения ресурсов удовлетворяют неравенствам (4), то найденное оптимальное решение двойственной задачи остается прежним.
Если 
и 
изменяются одновременно, то исследования устойчивости двойственных оценок несколько усложняется, так как необходимо определить многогранник решений системы неравенств относительно 
. Точки этого многогранника определяют количество ресурсов каждого типа, при которых двойственные оценки остаются прежними. Если при подстановке в систему неравенств (4) хотя бы одно из них становится неверным, то формулируется новая производственная задача, которая решается заново.
Выявим изменение общей стоимости изготовленной продукции, определяемой оптимальным планом при изменении количества ресурсов приуменьшении количества ресурсов I-го типа на 60 единиц и увеличении количества ресурсов II и III-го типов на 120 и 160 единиц.
Количество ресурсов I типа уменьшается на 60 единиц, т.е. 
, а II и III типа увеличивается соответственно на 120 ед. и 160 ед., т.е. 
и 
.
Чтобы выяснить остается ли план оптимальным планом двойственной задачи при указанном изменении количества ресурсов или нет, необходимо проверить удовлетворяют ли данные 
и 
системе неравенств (4).
Подставим значения в неравенства:
Так как все неравенства остаются верными, это означает, что двойственные оценки ресурсов не изменяются и останутся 
. Тогда изменение стоимости готовой продукции составит:
.
Это означает, что уменьшение количества ресурсов I типа на 60 единиц и увеличение количества ресурсов II и III типа соответственно на 120 ед. и 160 ед. приведет к возможности построения такого плана производства продукции, реализация которого обеспечит выпуск изделий на 540 ден. единиц больше, чем при первоначальном количестве ресурсов.
Соответствующий план производства определится следующим образом. Система ограничений, описывающих наше условие производства примет вид:
Так как 
, то ресурсы II и III-го типов используются полностью, поэтому 2-е и 3-е неравенства обратятся в равенства. Уменьшение количества ресурсов I-го типа на 60 ед. не повлияет на изменение максимального значения целевой функции, в то время как увеличение количества ресурсов II и III-го типов на 120 ед. и 160 ед. приведет к увеличению максимального значения целевой функции соответственно на 
и 
ден. единиц.
Таблица 11
| Базис | Свободный член | Переменные | ||||||
| x1 | x2 | x3 | x4 | x5 | x6 | x7 | ||
| x1 (А) | 95 | 1 | 0 | –3/2 | 0 | 0 | –1/2 | 1/4 |
| x5 (Р1) | 85 | 0 | 0 | 7/2 | 1 | 1 | 1/2 | –1/4 |
| x2 (В) | 210 | 0 | 1 | 3 | 2 | 0 | 1 | 0 |
| F | 2115 | 0 | 0 | 1/2 | 5 | 0 | 3/2 | 9/4 |
Для удобства рассуждений, мы привели симплекс-таблицу, содержащую оптимальное решение прямой задачи (табл.11).
Найдем оптимальный план, при увеличении сырья II вида на 120 единиц. Он приводит к увеличению общей стоимости на 180 ден. ед. (), что может быть достигнуто за счет увеличения выпуска изделий вида В на 120 ед. и сокращения выпуска изделий вида А на 
. Использование сырья I вида увеличится единиц.
Оптимальный план выпуска продукции, при изменении только II-го ресурса, становится 
.
При одновременном увеличении сырья II и III-го видов соответственно на 120 и 160 ед., приведет к увеличению общей стоимости на 540 ден. ед., что достигается за счет увеличения выпуска продукции вида А на 
ед., а количество выпуска изделий вида В не меняется, но объем используемого сырья I-го вида уменьшится на 
.
Оптимальный план выпуска продукции, при одновременном изменении ресурсов II и III-го видов, становится равным 
.
Уменьшение количества не дефицитного ресурса I-го типа на 60 ед. не повлияет на оптимальный план выпуска продукции.
Рассмотрим возможность дальнейшего совершенствования оптимального ассортимента выпускаемой продукции:
а) добавляя в модель новый вид продукции;
б) включая в план производства предприятия не выгодную продукцию, с точки зрения максимального дохода.
В случае а) введение в модель нового вида продукции эквивалентно добавлению новой переменной прямой задачи. И эта новая переменная войдет в оптимальный план, если издержки на производство этой продукции будут равны нулю. Например: выясним, целесообразно ли выпускать продукцию пятого вида, на единицу которого расходуются ресурсы 
, 
и 
, цена этой продукции 
.
Сопоставим дополнительные затраты на ресурсы в расчете на единицу продукции П5 с ценой ее реализации:
.
То есть, приведенные издержки единицы этой продукции равны 
, поэтому выпуск продукции вида П5 невыгодно предприятию включать в план производства, а чтобы производство продукции было рентабельным ее цена должна составлять не менее 12 единиц.
В случае б) включение в план производства невыгодной продукции, с точки зрения максимального дохода, возможный объем ее продукции в рамках устойчивости оптимального плана определяется следующим интервалом:
,
где 
– компонент оптимального плана;
– коэффициенты столбцов свободных переменных в оптимальном плане.
Например, в оптимальный план не вошла основная переменная 
. Определим максимально возможный объем выпуска продукции вида С по приведенной формуле:
,
.
Таким образом, в план производства можно ввести выпуск продукции С до 24 единиц.
Введение в план выпуска единицы продукции вида С приведет к уменьшению максимальной прибыли на величину 
. Это происходит за счет уменьшения выпуска продукции В на 3 единицы, хотя производство продукции вида А увеличивается на 
.
Выявим изменение общей стоимости изготовления продукции, определяемой оптимальным планом ее производства при включении в план производства не выгодой продукции вида С в объеме 20 единиц.
; 
;
"9 Организация ремонта ат" - тут тоже много полезного для Вас.
;
;
.
Проверим прибыль от реализации, произведенной продукции:
.
ъ
