Двойственность в линейном программировании

Понятие двойственности

С каждой задачей линейного программирования тесно связана другая линейная задача, называемая двойственной по отношению к первой (или сопряженной). Первоначальная задача называется исходной.

Связь исходной и двойственной задач заключается в том, что решение одной из них может быть получено непосредственно из решения другой.

Понятие двойственности рассмотрим на примере использования ресурсов: предприятие имеет m видов ресурсов в количестве b_i ед. (I = ), из которых производится n видов продукции. Для производства единицы j-ой продукции расходуется а _i,j единиц i-го ресурса, а ее стоимость составляет с_j единиц. Составить план max выпуска продукции, в стоимостном выражении.

Пусть х_j (j = ) – количество единиц j-й продукции, запланированной для производства. Тогда исходную задачу линейного можно сформулировать следующим образом: найти план (вектор) который удовлетворяет ограничениям:

и доставляет максимальное значение целевой функции

max z = с₁x₁ + с₂х₂ +…+ с_n х_n.

 Оценим ресурсы, необходимые для изготовления продукции. Для этого за единицу стоимости ресурсов примем единицу стоимости выпускаемой продукции. Обозначим через у_i (i = ) стоимость единицы i-го ресурса. Тогда стоимость всех затраченных ресурсов, идущих на изготовление j продукции, будет равна а _ij y_i, и она должна быть не меньше стоимости окончательного продукта, т. е. а _ij y_i  ≥ c_j, (j = ), а стоимость всех имеющихся ресурсов будет равна f (y) = b ₁ y ₁ + b ₂ y ₂ + … + b_my_m= b_iy_i  и она должна быть min.

Данная задача называется двойственной для исходной. Переменные у_i – называются оценками или неявными ценами (в зарубежной литературе – теневыми ценами)

Итак, двойственную задачу можно сформулировать следующим образом: найти план (вектор) который удовлетворяет ограничениям:

и доставляет min значение линейной функции

f(y) = b₁y₁ + b₂y₂+ … + b_my_m= b_iy_i.

Итак, в сокращенной форме записи имеем:

Прямая задача (ПЗ) ЛП	Двойственная задача (ДЗ) ЛП
max z = ,  (i = ), xj ³ 0 (j = ),	min f = ,  (j = ), yi ³ 0 (i = ),
или в матричной форме записи имеем.
Найти матрицу-столбец  которая удовлетворяет системе ограничений АХ £ В, x ³ 0, и максимизирует линейную функцию max z = СХ		Найти матрицу-строку  которая удовлетворяет системе ограничений YА ³ C, y ³ 0, и минимизирует линейную функцию min f = YB

Такие задачи называются симметричными двойственными задачами.

Сравнивая симметричные двойственные модели можно установить следующее:

1) Если прямая задача на mах, то двойственная к ней задача на min и наоборот.

2) Коэффициенты С_j целевой функции прямой задачи являются сво­бодными членами ограничений двойственной задачи.

3) Свободные члены b_i ограничений прямой задачи и являются коэф­фициентами целевой функции.

4) Матрицы ограничений прямой задачи и двойственной задачи яв­ляются транспонированными друг к другу.

5) Число ограничений прямой задачи равно числу переменных двой­ственной задачи и наоборот.

6) Переменные прямой задачи и двойственной задачи неотрицательны.

Рассмотренные исходная и двойственная задачи могут быть экономически интерпретированы следующим образом.

Исходная задача. Сколько и какой продукции x_j (j = ) необходимо произвести, чтобы при заданных стоимостях С _j (j = ) единицы продукции и размерах имеющихся ресурсов b_i (i = ) максимизировать выпуск продукции в стоимостном выражении.

Двойственная задача. Какова должна быть цена единицы каждого из ресурсов, чтобы при заданных количествах ресурсов b_i и величинах стоимости единицы продукции С _j минимизировать общую стоимость затрат?

Переменные y _i называются оценками или учетными, неявными ценами.

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

Многие задачи линейного программирования первоначально ставятся в виде исходных или двойственных задач, поэтому имеет смысл говорить о паре двойственных задач линейного программирования. 

Пример 12. Составить модель двойственной задачи.

Таблица 22

Ресурсы		Выпускаемая продукция				Объем ресурсов bi
Р1	Трудовые ресурсы, чел/ч	П1	П2	П3	П4
		4	2	2	8	b 1 = 4800
Р2	Полуфабрикаты, кг	2	10	6	0	b 2 = 2400
Р3	Станочное оборудование, станко/ч	1	0	2	1	b 3 = 1500
Цена единицы продукции, руб.		65	70	60	120

 

Решение.

1. Пусть х₁, х₂, х₃, х₄ – объемы продукций П₁, П₂, Пз, П₄, планируемые к вы­пуску; Z – сумма ожидаемой выручки.

Математическая модель прямой задачи:

Найти max z = 65х₁ + 70х₂ + 60х₃ + 120х₄, если

2. Тогда математическая модель двойственной задачи имеет вид: пусть y₁, y₂, y₃ – стоимость ресурсов P₁, P₂, P₃,тогда найти min f = 4800y₁ + 2400y₂ + 1500y₃, если

Пример 14. Прямая задача относится к симметричным двойственным задачам на отыскание min значения линейной функции. Для того, чтобы можно было записать двойственную задачу, ее модель ограничений должна иметь вид Ax ≥ B.

min z = 2х₁ + х₂ + 5х₃,

 

(при этом условие bi ≥ 0 уже не обязательно, смотри замечание)

Двойственная задача:

max f = – 4у₁ + 5у₂ + 6у₃,

Двойственные задачи могут иметь и несимметричный вид. В несимметричных двойственных задачах система ограничений исходной задачи задается в виде равенства, а двойственной – в виде неравенства, причем в последней переменные могут быть и отрицательными.

Прямая задача а) max Z = СХ,	Двойственная задача min f = YB, YA ³ C Y ³ 0.
б) min Z = CX	max f = YB, YA £ C Y ³ 0.