Виды математических моделей двойственных задач

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

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

Имеется m видов сырья в количестве , которые используются для изготовления n видов продукции. Известно: a_ij – расход i-го вида сырья на единицу j-й продукции; с_j - прибыль при реализации единицы j-го вида продукции. Составить план выпуска продукции, обеспечивающий максимальную прибыль.

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

, (5.1)

(5.2)

, j = 1, 2, . . . , n. (5.3)

Здесь , j = 1, 2, ..., n – объем производства j-го вида продукции.

Предположим, что имеется второй производитель, который хочет перекупить сырье. Составим двойственную задачу, решение которой позволяет определить условия продажи сырья. Введем вектор оценок (цен) видов сырья Y = ( ). Затраты на приобретение i-го вида сырья в количестве равны . Второму производителю выгодно минимизировать суммарные затраты на приобретение всех видов сырья, поэтому целевая функция имеет вид

. (5.4)

Первому производителю невыгодно продавать сырье, если суммарная стоимость всех видов сырья, расходуемых на каждое изделие j-й продукции

,

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

(5.5)

Очевидно, что оценки видов сырья должны удовлетворять условиям неотрицательности

, i = 1, 2, ..., m. (5.6)

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

Рассмотренная пара задач относится к симметричным парам двойственных задач. В теории двойственности используются четыре пары двойственных задач (приведем их в матричной форме записи).

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