Материал: 5021

27

6. ДВОЙСТВЕННОСТЬ

Пример 1. Рассмотрим задачу об оптимальном плане выпуска продукции: для изготовления 4 видов продукции используется 2 вида сырья. Запасы сырья и его расход на изготовление единицы каждого вида продукции даны в таблице:

Определить оптимальный план выпуска продукции из условия максимизации прибыли.

Математическая формулировка (модель) задачи: Максимизировать функцию

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

28

Обозначим соответственно, через y1 и y2 цену единицы сырья А и Б. Производство продукции вида I приносит предприятию доход 12

денежных единиц. При этом расходуется 4 единицы сырья А и 0 единиц сырья Б. Выручка от продажи сырья, расходуемого на единицу продукции I по ценам y1 и y2 , составит

4y1 0 y2 .

Эта величина должна быть не меньше тех доходов, которые предприятие получит от реализации продукции вида I, следовательно,

4y1 0 y2 12 .

Аналогичные рассуждения в отношении единицы продукции вида II, III, IV приводят к следующим неравенствам:

Общая стоимость всех запасов сырья, приобретаемого организацией, составит W 160y1 900y2 .

Покупатель будет стремиться купить сырье как можно дешевле, т.е. минимизировать функцию W .

Получим задачу:

W 160 y1 900 y2 min

Получили задачу, двойственную данной. Следовательно, для стандартной задачи нужно выполнить следующие действия, для того чтобы получить ей двойственную:

1)число неизвестных в двойственной задаче равно числу ограничений в исходной;

2)неравенства в системе ограничений двойственной задачи будут противоположного смысла, чем неравенства в системе ограничений исходной задачи; сохраняется неотрицательность переменных;

3)свободные члены ограничений исходной задачи становятся коэффициентами целевой функции двойственной задачи, а коэффициенты целевой функции исходной задачи превращаются в свободные члены двойственной задачи;

4)в исходной задаче целевая функция минимизируется, а в двойственной – максимизируется.

29

По решению одной из задач можно сразу определить решение другой.

Решим исходную задачу симплекс-методом:

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

Пример 2. В двойственной задаче к основной переменные могут иметь любой знак. Составим двойственную задачу к основной:

30

Двойственная задача имеет следующий вид:

W 6 y1 4 y2 min

Решим двойственную задачу графически

n

y1

1

Координаты точки А дают значения неизвестных y1 и y2 , при которых функция W принимает минимальное значение.

Найдем координаты этой точки:

По решению двойственной задачи найдем решение исходной по второй теореме двойственности (теореме равновесия).