§8. Постановка двойственной задачи линейного программирования. Типы двойственных задач линейного программирования
Каждой ЗЛП можно определённым образом сопоставить некоторую другую задачу, называемую двойственной (или сопряжённой) по отношению к исходной задаче.
Рассмотрим пример, показывающий, как в реальной экономической ситуации появляются взаимно двойственные задачи линейного программирования [8]. На некотором предприятии после выполнения годового плана возник вопрос – как поступить с остатками сырья? У руководства и экономистов предприятия возникли два пути решения: либо продать остатки сырья какой-нибудь нуждающейся в нем организации (наиболее простой вариант), либо наладить из оставшегося сырья производство каких-то изделий на своем собственном оборудовании.
Для простоты будем считать, что имеются два вида сырья S1 и S2, остатки которого составляют соответственно и единиц. Из этого сырья можно наладить производство трех видов товаров: Т1, Т2, Т3. От реализации одной единицы каждого вида товара Т1, Т2, Т3 предприятие получит прибыль соответственно , , у.е. Нормы расхода сырья на производство товаров Т1, Т2, Т3 вместе с данными о прибыли и запасах представлены в следующей таблице, где означает, сколько единиц сырья расходуется на производство товара .
Проследим за ходом мыслей экономистов предприятия. Как уже говорилось, им предстояло проанализировать две возможности.
При исследовании второй возможности (наладить выпуск товаров Т1, Т2, Т3) возникает вопрос о плане выпуска товаров. План выпуска задается тремя числами , где – количество единиц товара , которое следует произвести ( ). Неизвестные должны удовлетворять системе ресурсных ограничений
причем прибыль, которую получит предприятие от реализации оптимального плана выпуска товаров, должна быть максимальной:
Следовательно, чтобы наилучшим образом использовать вторую возможность, нужно решить задачу линейного программирования (8.1), (8.2).
Исследуем теперь первую возможность – продать сырье другой организации. Здесь возникает вопрос: по каким ценам продавать сырье? Обозначим эти цены , где – цена единицы сырья Si ( ).
Справедливое требование к ценам со стороны продающего предприятия состоит в следующем. Если взять сырье, идущее на изготовление единицы товара Тi ( ), то выручка от его продажи должна быть не меньше, чем прибыль от реализации готового изделия (в противном случае нет смысла продавать сырье – лучше изготовить из него товар и получить за него прибыль). Это требование приводит к системе неравенств
Первое из написанных неравенств в системе (8.3) означает, что выручка от продажи единиц сырья S1 и единиц сырья S2 (именно такое количество сырья расходуется на изготовление единицы товара T1) не меньше, чем прибыль, которую могло бы получить предприятие от продажи единицы товара T1, если бы оно отказалось от идеи продать сырье и занялось изготовлением из него товаров T1, T2, T3. Аналогичный смысл имеют остальные два неравенства.
Что же касается покупателя, то для него единственное пожелание заключается в сокращении до минимума расходов на покупку сырья:
Итак, для оптимального использования первой возможности необходимо решить задачу линейного программирования (8.3), (8.4).
Для наглядности сопоставим формулировки двух задач:
Задача (8.1), (8.2) и задача (8.3), (8.4) в линейном программировании называются двойственными друг другу. При этом задачу (8.1), (8.2) называют прямой задачей.
Рассмотрим основные типы двойственных задач линейного программирования. Пусть прямая задача линейного программирования имеет вид
Запишем эту задачу в матричном виде
где – вектор-столбец коэффициентов целевой функции, – вектор-столбец управляющих переменных, – матрица коэффициентов при управляющих переменных, – вектор-столбец свободных членов.
Тогда соответствующая двойственная задача линейного программирования к прямой задаче (8.5) имеет вид
где – вектор-столбец управляющих переменных двойственной задачи.
Определение 8.1. Пару прямой (8.5) и двойственной (8.6) ЗЛП называют симметричной.
Симметрические двойственные ЗЛП составляются в том случае, когда в системе ограничений прямой ЗЛП стоят только все знаки , или только все знаки .
Приведем алгоритм построения симметрических двойственных ЗЛП.
1) Каждому неравенству системы ограничений прямой ЗЛП (8.5) поставить в соответствие неотрицательную переменную (число управляющих переменных двойственной задачи равно числу функциональных ограничений прямой задачи).
2) В качестве коэффициентов целевой функции двойственной ЗЛП взять свободные члены системы ограничений прямой задачи.
3) Направление оптимизации (тип экстремума) целевой функции двойственной задачи противоположно направлению оптимизации целевой функции прямой задачи (если прямая задача была на максимум, то двойственная задача – на минимум, и наоборот).
4) Пусть – матрица коэффициентов системы ограничений прямой ЗЛП. Получить матрицу коэффициентов системы ограничений двойственной ЗЛП из матрицы транспонированием: . Число ограничений в системе ограничений двойственной ЗЛП равно числу переменных прямой ЗЛП.
5) В качестве свободных членов системы ограничений двойственной задачи взять коэффициенты целевой функции прямой задачи.
6) В двойственной задаче на максимум задать знаки для всех неравенств-ограничений, в задаче на минимум – .
Пример 8.1. Построить двойственную ЗЛП для задачи
Решение. Матричная форма записи данной ЗЛП имеет вид (см. (8.5))
где – вектор-столбец коэффициентов целевой функции ,
– вектор-столбец управляющих переменных, – матрица коэффициентов при управляющих переменных, – вектор-столбец свободных членов.
Тогда соответствующая ДЗЛП запишется в виде (см. (8.6))
, где – вектор-столбец управляющих переменных двойственной задачи.
Рассмотрим ЗЛП канонического вида в матричном виде
Тогда соответствующая двойственная ЗЛП к (8.7) имеет вид
где – вектор-столбец управляющих переменных двойственной задачи, причем компоненты в общем случае произвольного знака (в том числе и отрицательного знака).
Определение 8.2. Пару прямой (8.7) и двойственной (8.8) ЗЛП называют несимметричной.
Определение 8.3. Пару прямой и двойственной ЗЛП называют смешанной, если система ограничений прямой задачи имеет как знаки строго равенства (знак =), так и знаки , .
При составлении смешанной пары двойственных задач руководствуются алгоритмом составления симметрической пары. Если функциональное ограничение прямой задачи имеет знак неравенства , то соответствующая этому ограничению переменная двойственной задачи следует считать неотрицательной. Если же функциональное ограничение прямой задачи является равенством, то соответствующая переменная двойственной задачи может принимать как положительные, так и отрицательные значения.
Пример 8.2. Построить двойственную ЗЛП для задачи
Решение. Соответствующая ДЗЛП имеет вид
Решение двойственной задачи линейного программирования
Инструкция . Выберите количество переменных и количество ограничений прямой задачи линейного программирования, нажмите Далее . Полученное решение сохраняется в файле Word и Excel . При этом ограничения типа xi ≥ 0 не учитывайте. Если прямая задача ЛП не имеет решение, но требуется составить двойственную задачу или одна из переменных xi неопределена, то можно использовать этот калькулятор.
Определив обратную матрицу А -1 через алгебраические дополнения, получим:
Как видно из последнего плана симплексной таблицы, обратная матрица A -1 расположена в столбцах дополнительных переменных x4 , x5 , x6 .
Тогда Y = C*A -1 =
Оптимальный план двойственной задачи равен: y1 = 23.75, y2 = 12.5, y3 = 0
Z(Y) = 1100*23.75+120*12.5+8000*0 = 27625
Подставим оптимальный план прямой задачи в систему ограниченной математической модели:
0.1*250 + 0.2*5375 + 0.4*0 = 1100 = 1100
0.05*250 + 0.02*5375 + 0.02*0 = 120 = 120
3*250 + 1*5375 + 2*0 = 6125 < 8000 1-ое ограничение прямой задачи выполняется как равенство. Это означает, что 1-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y1>0).
2-ое ограничение прямой задачи выполняется как равенство. Это означает, что 2-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y2>0).
3-ое ограничение выполняется как строгое неравенство, т.е. ресурс 3-го вида израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y3 = 0.
Таким образом, отличную от нуля двойственные оценки имеют лишь те виды ресурсов, которые полностью используются в оптимальном плане. Поэтому двойственные оценки определяют дефицитность ресурсов.
При постановке оптимальных двойственных оценок в систему ограничений двойственной задачи получим:
0.1*23.75 + 0.05*12.5 + 3*0 = 3 = 3
0.2*23.75 + 0.02*12.5 + 1*0 = 5 = 5
0.4*23.75 + 0.02*12.5 + 2*0 = 9.75 > 4
1-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 1-ый ресурс экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x1>0).
2-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 2-ый ресурс экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x2>0).
3-ое ограничение выполняется как строгое неравенство, т.е. ресурс 3-го вида использовать экономически не выгодно. И действительно в оптимальном плане прямой задачи x3 = 0.
Величина двойственной оценки показывает, на сколько возрастает значение целевой функции при увеличении дефицитного ресурса на единицу.
Например, увеличении 1-го ресурса на 1 приведет к получению нового оптимального плана, в котором целевая функция возрастает на 23.75 и станет равной: F(x) = 27625 + 23.75 = 27648.75
Проведем анализ устойчивости оптимального плана и оценим степень влияния изменения ресурсов на значение целевой функции.
Пусть каждое значение параметра целевой функции изменится на ∆ сi. Найдем интервалы, при которых будет экономически выгодно использование ресурсов.
1-ый параметр целевой функции может изменяться в пределах:
-3.8 ≤ с1 ≤ 1
Таким образом, 1-параметр может быть уменьшен на 3.8 или увеличен на 1
Интервал изменения равен: [3-3.8; 3+1] = [-0.8;4]
Если значение c1 будет лежать в данном интервале, то оптимальный план не изменится. 2-ый параметр целевой функции может изменяться в пределах:
-10 ≤ b2 ≤ 30
Таким образом, 2-ый запас может быть уменьшен на 10 или увеличен на 30
Интервал изменения равен: [120-10; 120+30] = [110;150]
Составим субоптимальные варианты плана с учетом изменений исходных данных модели (таблицы).
Пусть 2-ый ресурс увеличили на 50
| Базисные переменные | Значение базисных переменных | Коэффициент структурных сдвигов k c | Произведение k c на (50) | Расчет варианта плана |
| x 2 | 5375 | 6.25 | 312.5 | 5687.5 |
| x 1 | 250 | -2.5 | -125 | 125 |
| x 6 | 1875 | 1.25 | 62.5 | 1937.5 |
| F(X) | 27625 | 23.75 | 1187.5 | 28812.5 |
| Базисные переменные | Значение базисных переменных | Коэффициент структурных сдвигов k c | Произведение k c на (-5) | Расчет варианта плана |
| x 2 | 5375 | -12.5 | 62.5 | 5437.5 |
| x 1 | 250 | 25 | -125 | 125 |
| x 6 | 1875 | -62.5 | 312.5 | 2187.5 |
| F(X) | 27625 | 12.5 | -62.5 | 27562.5 |
F(X) = 3x1 + x2 → min
— 2x1 + x2≥4
2x1 + x2≤8
3x1 + 2x2≥6
Решение.
I этап. Приводим систему к каноническому виду.
II этап. Решаем симплекс-методом.
Примечание: Если задача решается данным калькулятором, то предыдущие два этапа пропускаем, поскольку они автоматически включены в решение.
На втором этапе окончательный вариант симплекс-таблицы имеет вид:
| Базис | B | x1 | x2 | x3 | x4 | x5 | x6 | x7 |
| x5 | 2 | -7 | 0 | -2 | 0 | 1 | 2 | -1 |
| x4 | 4 | 4 | 0 | 1 | 1 | 0 | -1 | 0 |
| x2 | 4 | -2 | 1 | -1 | 0 | 0 | 1 | 0 |
| F(X3) | 4 | -5 | 0 | -1 | 0 | 0 | 1-M | -M |
Так как в оптимальном решении отсутствуют искусственные переменные (они равны нулю), то данное решение является допустимым. Записываем оптимальный план:
x1 = 0, x2 = 4, F(X) = 1•4 = 4 Составим двойственную задачу к прямой задаче.
— 2y1 + 2y2 + 3y3≤3
y1 + y2 + 2y3≤1
4y1 + 8y2 + 6y3 → max
y1 ≥ 0, y2 ≤ 0, y3 ≥ 0
Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи. Из теоремы двойственности следует, что Y = C*A -1 . Составим матрицу A из компонентов векторов, входящих в оптимальный базис.
| A = (A5, A4, A2) = |