1.5. Двойственная задача линейного программирования. Экономическая интерпретация

Рассмотрим задачу линейного программирования следующего вида:

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

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

В двойственной задаче требуется найти минимум целевой функции, ограничения — неравенства со знаком , управляющие переменные неотрицательны. Задача содержит управляющих переменных и ограничений. Коэффициенты целевой функции задачи являются свободными членами исходной ЗЛП, а свободные члены двойственной задачи — коэффициентами целевой функции исходной ЗЛП. Матрица коэффициентов двойственной задачи транспонирована, т.е. строки заменены столбцами, а столбцы — строками.

Задачи (1.5.1), (1.5.2) и (1.5.3), (1.5.4) называются парой взаимно двойственных задач линейного программирования. Для двойственных задач верна следующая теорема.

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

Пусть в качестве управляющих переменных исходной модели рассматривается число изделий, производимых некоторым предприятием, а параметрами — количество ресурсов -ого типа, используемых для изготовления изделий. Через обозначено количество ресурсов -ого типа, идущее на изготовление одного изделия -ого вида. Тогда исходная модель (1.5.1), (1.5.2) соответствует задаче определения оптимального плана производства продукции, обеспечивающего максимальную прибыль.

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

1. они не должны быть слишком высокими, иначе ресурсы невозможно будет продать;

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

Первое условие выражается формулой (1.5.3), второе условие — ограничениями (1.5.4). В левой части каждого из неравенств (1.5.4) стоит прибыль от продажи ресурсов всех типов, идущих на изготовление -ого изделия, в правой части — прибыль от продажи -ого изделия. Таким образом, двойственная задача (1.5.3) — (1.5.4) соответствует следующей экономической проблеме: по каким минимальным ценам следует продавать ресурсы, чтобы прибыль от их реализации была больше прибыли, полученной от реализации продукции, изготавливаемой с использованием этих ресурсов. Значения переменных часто называют теневыми ценами.

Построение двойственной задачи позволяет глубже разобраться в поставленной экономической проблеме.