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

Любую задачу максимизации с экономической точки зрения можно рассматривать как задачу о распределении ограниченных ресурсов b1, b2, …, bn между различными потребителями, например, между некоторыми технологическими процессами, которые представляются столбцами A1, А2, ..., Аm матрицы ограничений задачи. Любое допустимое решение задачи линейного программирования х1, х2, ..., хm дает конкретное распределение, указывающее ту долю каждого из ресурсов, которая должна быть использована при осуществлении соответствующего технологического процесса.

Рассмотрим пример. Завод производит три вида продукции х1, x2 и x3, каждый из которых требует затрат времени на обработку на токарном, фрезерном и сверлильном станках. Количество машинного времени для каждого из станков ограничено. Пусть с1, c2 и c3 — прибыль от реализации единицы соответствующего вида продукции. Необходимо определить, какое количество каждого вида продукции необходимо производить в течение недели, чтобы получить максимальную прибыль.

Формально эта задача записывается так:

найти

 (1)

при ограничениях

 (2)

где a1j, a2j, a3j — время, необходимое для обработки единицы j-го вида продукции соответственно на токарном, фрезерном и сверлильном станках (j = 1, 2, 3); b1, b2, b3 — недельный ресурс машинного времени соответственно для токарного, фрезерного и сверлильного станков.

Обозначим y1, y2 и y3 — цену единицы времени работы на токарном, фрезерном и сверлильном станках. Тогда a1jy1 + a2jy2+ a3jy3 мож­но трактовать как расходы на изготовление единицы продукции вида j.

Предположим, что цены ресурсов y1, y2 и y3 выбраны так, что выполняются следующие соотношения:

 (3)

Поскольку b1, b2, b3 — использованный ресурс машинного времени для каждого из станков, то b1y1 + b2y2 + b3y3 — суммарные расходы на производство.

Требуется найти такие y1, y2 и y3, удовлетворяющие условиям (3), при которых минимизируются суммарные расходы на производство:

min g(y1, y2, y3)= b1y1 + b2y2 + b3y3, (4)

y1³ 0, y2³ 0, y3³ 0.

Такую задачу называют двойственной задачей по отношению к задаче (1), называемой прямой.

Запишем теперь прямую и двойственную задачи в общем случае. Прямая задача

 (5)

при условиях

 (6)

. (7)

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

 (8)

при условиях

 (9)

. (10)

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

1) если прямая задача является задачей максимизации, то двойственная будет задачей минимизации, и наоборот;

2) коэффициенты целевой функции прямой задачи c1, c2, …, cn становятся свободными членами ограничений двойственной задачи;

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

4) матрицу ограничений двойственной задачи получают транспонированием матрицы ограничений прямой задачи;

5) если знаки всех неравенств в ограничениях прямой «£ », то в двойственной задаче все ограничения будут иметь знак «³ »;

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

Переменные y1, y2, …, ym двойственной задачи иногда называют «теневыми ценами».

Двойственную задачу выгоднее решать, чем исходную прямую, если в прямой задаче при малом количестве переменных имеется большое количество ограничений (т > n).

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

Теорема. Если x0 и у0 — допустимые решения прямой и двойственной задач, т. е. если Ах0 £ b и АTy0 ³ с, то

cTx0£ bTy0,

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

Теорема(основная теорема двойственности). Если x0 и у0 — допустимые решения прямой и двойственной задач и если cTx0=bTy0, то x0 и у0 — оптимальные решения пары двойственных задач.

Теорема. Если в оптимальном решении прямой задачи i-е ограничение выполняется как строгое неравенство, то оптимальное значение соответствующей двойственной переменной равно нулю.

Смысл этой теоремы состоит в следующем. Если некоторый ресурс bi имеется в избытке и i-е ограничение при оптимальном решении выполняется как строгое неравенство, то оно становится несущественным, и оптимальная цена соответствующего ресурса равна 0.

Теорема. Если в оптимальном решении двойственной задачи ограничение j выполняется как строгое неравенство, то оптимальное значение соответствующей переменной прямой задачи должно быть равно нулю.

Экономическая интерпретация этой теоремы: поскольку величины yj представляют собой цены соответствующих ресурсов, то  — это затраты на i-й технологический процесс, величина сi — прибыль от реализации на единицу изделия. Поэтому с экономической точки зрения теорема означает следующее: если i-й технологический процесс оказывается строго невыгодным с точки зрения оптимальных цен ресурсов уопт, то в оптимальном решении прямой задачи интенсивность использования данного технологического процесса хi должна быть равна 0.

Таким образом, теорема выражает принцип рентабельности оптимального организованного производства.

Теорема (теорема существования). Прямая и двойственная задачи имеют оптимальные решения тогда и только тогда, когда обе они имеют допустимые решения.

Теорема (теорема двойственности). Допустимый вектор x0 оптимален тогда и только тогда, когда в двойственной задаче имеется такое допустимое решение уо, что

.

⇐ Предыдущая1234567Следующая ⇒

Поделиться: