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

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

Составим двойственную задачу к следующей задаче.

Имеется т видов сырья в количестве b ₁, b ₂, ..., b_т, которые используются для изготовления п видов продукции. Известно: а_ij — расход i -го вида сырья на единицу j -ой продукции; с _j. — прибыль при реализации единицы j -го вида продукции. Составить план выпуска продукции, обеспечивающий максимальную прибыль.

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

F(X) = с ₁ х ₁+ с ₂ х ₂ +... + с_п х_п→ max,

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

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

Z(Y) = b ₁ у ₁ + b ₂ у ₂ +…+ b_ту_т→ min.

Первому производителю невыгодно продавать сырье, если суммарная стоимость всех видов сырья, расходуемых на каждое изделие j -й продукции, т.е. а _{1 j} у₁ + а _{2 j} у ₂ +…+ а_mj у_т, меньше прибыли с_j получаемой при реализации этого изделия. Система ограничений задачи имеет вид

Очевидно, что оценки видов сырья должны удовлетворять условиям неотрицательности у_i ≥ 0, i = 1, 2, …, т.

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

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

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

Симметричные пары

1. F (X) =CX→ max, Z (Y)= YA ₀→min

AX ≤ A ₀ , YA ≥ C,

X ≥θ; Y ≥θ.

2. F (X) =CX→ min, Z (Y)= YA ₀→ max,

AX ≥ A ₀ , YA ≤ C,

X ≥θ; Y ≥θ.

Несимметричные пары

3. F (X) =CX→ max, Z (Y)= YA ₀→min

AX = A ₀ , YA ≥ C.

X ≥θ;

2. F (X) =CX→ min, Z (Y)= YA ₀→ max,

AX = A ₀ , YA ≤ C.

X ≥θ;

Здесь С =(с ₁, с ₂,…, с_n), Y= (у ₁, у ₂ ,… …,у_т),