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

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

В линейном программировании наряду с исходной (прямой) задачей рассматривается двойственная ей задача.

ЗАДАЧА 1 (исходная) (1) х1≥0,…, хn≥0, (2) F=c1x1+…cnxn (3)

ЗАДАЧА 2 (двойственная) y1≥0,…, ym≥0, (5) Z= (6)

Рассмотрим свойства исходной и двойственной задач.

1. В одной задаче ищут максимум линейной функции, а в другой минимум.

2. Каждая из задач задана в стандартной форме, причем в задаче максимизации все неравенства вида « », а в задаче минимизации все неравенства « ».

3. Коэффициенты при переменных в линейной функции являются свободными членами системы ограничений второй.

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

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

6. В обеих задачах имеются ограничения на неотрицательность переменных.

Рассмотрим на примере связь между исходной и двойственной задачами.

ЗАДАЧА 1 (исходная) х1≥0, х2≥0, F=5x1+6x2

ЗАДАЧА 2 (двойственная) y1≥0,y2≥0, Z=8

Решим эти задачи геометрическим методом.

6 4 х1 х2 М =2, , =28.

М у1 у2

Совпадения и не случайны.