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

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

Исходная или прямая задача в общем виде:                                                                              (54)

Ограничение:

,                                                            (55)

 Тогда двойственная по отношению к ней задача в общем виде:

                                                              (56)

Ограничение:

,                                        (57)

Рассмотрим упрощенный вариант задачи оптимизации производственной программы. Пусть предприятие выпускает j =1,2,…, n видов приборов. Цена каждого прибора U_j (руб), выпуск x_j (шт). При производстве j -го прибора затрачивается a_ij кг i-го материала. Общие запасы материальных ресурсов составляют B_i (i=1,2,…,m).

Исходная задача будет иметь вид:

                                                        (58)

Ограничение:

 ,                                                              (59)

Для этого же предприятия можно сформулировать и двойственную задачу. Требуется найти такие оценки ресурсов  (руб/кг), которые обеспечили бы минимум общего расхода ресурсов в стоимостном выражении, а затраты на производство каждого вида продукции не были бы меньше его цены .  

Двойственная задача будет иметь вид:                                                                          (60)

Ограничение

,                                                                   (61)

Из  выражений (56, 58)  видно, что исходная или прямая задача (56) является задачей на максимум, а двойственная (58) – задачей на минимум. Параметры целевой функции исходной задачи являются ограничением двойственной задачи. Матрица коэффициентов расхода ресурсов исходной задачи транспонируется в двойственной задаче. Переменная  называется оценками, или учетными, неявными ценами ресурсов.

При решении исходной и двойственной задач используются следующие теоремы двойственности:

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

                                                                                 (62)

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

3. Двойственная оценка i-го ограничения (множитель Лагранжа) представляет собой частную производную целевой функции исходной задачи по правой части соответствующего ограничения:

.                                                                              (63)

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

На основе теорем двойственности, можно сформулировать свойства двойственных оценок:

Свойство 1. Если то есть i-й ресурс потребляется полностью, то  и i-й ресурс является дефицитным. Если , то , то есть если ресурс избыточен, то он имеет нулевую «цену».

Свойство 2. Если , то , то есть, если суммарная оценка ресурсов, идущих на производство изделия равна цене, то изделие выпускается. Если , то , то есть, если суммарная оценка больше цены, то изделие убыточно и не выпускается.

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

5.4. Транспортная задача

      Транспортная задача является разновидностью линейной задачи математического моделирования. Имеется m пунктов производства однородного продукта и n пунктов потреблений. Известны затраты по перевозке продуктов. Необходимо привязать поставщиков к потребителям, чтобы минимизировать затраты.

Целевая функция: 

                                                          (64)

где  - затраты по перевозке единицы продукта,

- количество продукта, перевозимое из пункта i в пункт j .

В качестве ограничений используют:

1. - нужно полностью использовать возможности (65) каждого поставщика.

где - производительность i-го поставщика.

2.  – нужно удовлетворить потребности                             (66) каждого потребителя.

     где - потребности j-го потребителя.

         Транспортная задача бывает закрытой, если то есть количество производимой продукции равно количеству потребляемой продукции и открытой, если  Открытая задача при решении сводится к закрытой путём введения фиктивных пунктов производства или потребления, причем затраты по перевозке из фиктивных или в фиктивные пункты принимаются равными нулю.

Для решения транспортной задачи используется несколько методов, самым распространенным из которых является метод потенциалов, однако можно использовать для решения и двойственный симплекс-метод.

Разновидностью транспортной задачи является задача о назначениях: комплексная бригада из m работников, которая выполняет n работ.

Целевой функцией будет максимальная производительность всей бригады:

,                                                     (67)

где c_ij – производитель i -го работника на j-й работе,

  d _ij – булева переменная, которая равна нулю, если i -й работник не выполняет j- ю работу; или равна 1, если i-й работник выполняет j-ю работу.   

Ограничения:

- каждый работник должен быть занят;

                                                                               (68)

- каждая работа должна быть выполнена.

                                                                                      (69)