Двойственная задача линейного программирования

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

{spoiler=Подробнее}

Рассмотрим двойственную задачу в общей постановке.

I.Пусть ограничения исходной задачи имеют вид:

a₁₁x₁₊a₁₂x₂+ ... +a_1n x_n £ b₁,

a₂₁x₁+a₂₂x₂+ ...+a_2n x₂  £ b₂

.........................................                                  (1)

a_m1x₁+a_m2x₂+...+a_mnx_n=b_m

x_i³0, i=1,2,...,n.

На множестве решений этой системы требуется максимизировать функцию

F=c₁x₁+c₂x₂+...+c_nx_n

Двойственной для этой задачи будет задача с ограничениями

a₁₁y₁₊a₁₂y₂+ ... +a_m1 y_m £ c₁,

a₂₁y₁+a₂₂y₂+ ...+a_m2 x_m  £ c_2,

.........................................                                  (2)

a_1ny₁+a_2ny₂+...+a_mny_m=c_n,

x_i³0, i=1,2,...,m.

И  минимизируем ой целевой функцией

f=b₁y₁+b₂y₂+...+b_my_m.

Сравнивая обе задачи, нетрудно заметить, что :

1.Матрица из коэффициентов при переменных в исходной задаче

A=  

  и аналогичная матрица в двойственной задаче

A’=  

получаются друг из друга простой заменой строк столбцами с сохранением их порядка. Такая операция получила название транспонирование.

1. В исходной задаче n переменных и m ограничений , двойственной -m переменных и  n ограничений.
2. В правых частях систем  ограничений каждой из задач стоят коэффициенты целевой функции,  взятой из другой задачи.

В систему ограничений исходной задачи входят неравенства типа £, причем в задаче требуется максимизировать целевую функцию F. В систему ограничений  двойственной задачи входят неравенства типа  ³ , причем в двойственной задаче требуется минимизировать целевую функцию f.

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

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

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

Чтобы получить, например ,первое ограничение двойственной задачи, надо  найти сумму произведений чисел, стоящих в столбце под х₁ на соответствующие переменные первого столбца:

а₁₁у₁+а₂₁у₂+...+а_m1y_m.

Считаем , что это сумма не меньше с₁ :

а₁₁у₁+а₂₁у₂+...=а_m1y_m³с₁

Аналогично составляется и остальные ограничения для двойственной задачи. При этом устанавливается такое соответствие:

а)переменный х₁ исходной задачи соответствует первое ограничение двойственной задачи , переменной х₂ -второй ограничение двойственной задачи и т.д. переменной х_n - последнее ограничение двойственной задачи и на оборот ;

б)переменной у₁ двойственной задачи соответствует первое ограничение исходной задачи и т.д. переменной у_m двойственной задачи соответствует последнее ограничение исходной задачи на оборот .

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

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

Например , пусть система ограничений  исходной задачи на максимум входить уравнение

2х₁+3х₂+5х₃=12.

Легко видеть, что

2х₁+3х₂+5х₃=12,         (1) Û

                                 ì  2х₁+3х₂+5х₃³12,

                           Û  í                                       (2) Û

                                 î  2х₁+3х₂+5х₃£12,       

                                 ì   -2х₁-3х₂-5х₃£-12,       

                          Û   í                                        (3)

                                 î    2х₁+3х₂+5х₃£12,

Уравнения (1)  в системе ограничений исходной задачи на максимум должны быть типа £ , а в задачи на минимум - типа ³.

Рассмотрим на примере , как составляется двойственная задача.

Задача. (Исходная задача ) .Изготовление продукции двух видов (П₁ и П₂) требует использования четырех видов сырья (S₁,S_2,S₃,S₄). Запас сырья каждого вида ограничен (количественные данные приведены в таблице). В таблице указано , сколько единиц сырья необходимо для изготовления единицы каждого из видов продукции :

 (В последней строке таблицы указан доход, получаемый предприятием от реализации единицы продукции.) Требуется составить такой план выпуска продукции, при котором доход предприятия от реализации продукции оказался бы максимальным.

Эту задачу можно сформулировать так:

Пусть х₁ и х₂ - числа единиц продукции, соответственно видов П₁ и П_2. Среди ограничений

2x₁+3x₂£19,

2x₁+ x₂£ 13,                                        

3x₂£15,                                 (1)

3x₁     £18,

x₁  ³ 0,

x₂³ 0,        

необходимо выбрать такое, при котором целевая функция

F=7х₁ + 5х₂                                    (2)

достигает максимального значения.

Переходим к построению математической модели двойственной задачи.

В качестве переменных двойственной задачи возьмем у₁ , у₂ , у₃ , у₄, представляющие собой некие условные оценки запасов сырья. Теперь двойственную задачу можно сформулировать так: среди решений системы ограничений

2у₁ + 2у₂ + 3у₄ ³ 7,

3у₁ + у₂ + 3у₃ ³ 5,                               (3)

у₁³0, j=1,2,3,4

найти такое, при котором целевая функция

f= 19y₁ +13y₂ +15y₃ + 18y₄                           (4)

 достигает минимального значения.

Сравнение двух построенных математических моделей позволяет сделать следующие выводы: исходная задача имеет 2 переменные и 4 ограничения (ограничения х₁³0, х₂³0 не считаются), и в ней требуется отыскать максимальное значение целевой функции; двойственная задача имеет 4 переменные и 2 ограничения, и в ней требуется отыскать минимальное значение целевой функции.

{/spoilers}