Глава 6. Двойственные задачи

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

6.1. Экономическая интерпретация задачи, двойственной задаче об использовании ресурсов

В гл. 1 рассмотрена задача об использовании ресурсов (экономико-математическая модель и содержательная интерпретация этой задачи I представлены в левой части табл. 6.1). В приведенной модели Ь- (г = 1, 2,..., т) обозначает запас ресурса S' а. – число единиц ресурса Sjt потребляемого при производстве единицы продукции Р. (j = 1,2, ..., п); Cj – прибыль (выручка) от реализации единицы продукции Р. (или цена продукции Р.).

Предположим, что некоторая организация решила закупить ресурсы 5,, S2,..., Sm предприятия и необходимо установить оптимальные цены на эти ресурсы yv у2,..., ут.

Очевидно, что покупающая организация заинтересована в том, чтобы затраты на все ресурсы Z в количествах bv b2,..., Ьт по ценам соответственно уу у2,..., ут были минимальны, т.е.

В то же время, предприятие, продающее ресурсы, заинтересовано в том, чтобы полученная выручка была не менее той суммы, которую предприятие может получить при переработке ресурсов в готовую продукцию. На изготовление единицы продукции Р{ расходуется "∏ единиц ресурса 54, а2[ единиц ресурса S2,..., ап единиц ресурса 5(,..., ami единиц ресурса Sm по цене соответственно у{, у2,..., ут. Поэтому для удовлетворения требований продавца затраты на ресурсы, потребляемые при изготовлении единицы продукции Р{, должны быть нс менее ее цены cv т.е.

Аналогично можно составить ограничения в виде неравенств по каждому виду продукции. Экономико-математическая модель и содержательная интерпретация полученной таким образом двойственной задачи II приведены в правой части табл. 6.1.

Таблица 6.1

Цены ресурсовв экономической литературе получили различные названия: учетные, неявные, теневые. Смысл этих названий состоит в том, что это условные, "ненастоящие" цены. В отличие от "внешних" цен па продукцию, известных, как правило, до начала производства, цены ресурсовявляются внутренними, так как они задаются не извне, а определяются непосредственно в результате решения задачи, поэтому их чаще называют оценками ресурсов.

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

Рассмотрим формально две задачи I и 11 линейного программирования, представленные в табл. 6.1, абстрагируясь от содержательной интерпретации параметров, входящих в их экономико-математические модели. Обе задачи обладают следующими свойствами.

• 1. В одной задаче ищут максимум линейной функции, в другой – минимум.
• 2. Коэффициенты при переменных в линейной функции одной задачи являются свободными членами системы ограничений в другой.
• 3. Каждая из задач задана в стандартной форме, причем в задаче максимизации все неравенства вида "<", а в задаче минимизации все неравенства вида ">".
• 4. Матрицы коэффициентов при переменных в системах ограничений обеих задач являются транспонированными друг к другу: 5 6

• 5. Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой задаче.
• 6. Условия неотрицательности переменных имеются в обеих задачах.

Две задачи I и II линейного программирования, обладающие указанными свойствами, называются симметричными взаимно двойственными задачами. В дальнейшем для простоты будем называть их просто двойственными задачами.

Исходя из определения, можно предложить следующий алгоритм составления двойственной задачи.

• 1. Привести все неравенства системы ограничений исходной задачи к одному смыслу: если в исходной задаче ищут максимум линейной функции, то все неравенства системы ограничений привести к виду "≤", а если минимум – к виду "≥". Для этого неравенства, в которых данное требование не выполняется, умножить на -1.
• 2. Составить расширенную матрицу системы Ау в которую включить матрицу коэффициентов при переменных А, столбец свободных членов системы ограничений и строку коэффициентов при переменных в линейной функции.
• 3. Найти матрицу А{, транспонированную к матрице Аг
• 4. Сформулировать двойственную задачу на основании полученной матрицы А и условия неотрицательности переменных.
• 6.1. Составить задачу, двойственную следующей задаче:

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

Решение. 1. Так как исходная задача на максимизацию, то приведем все неравенства системы ограничений к виду "≤", для чего обе части первого и четвертого неравенства умножим на -1. Получим

2. Составим расширенную матрицу системы:

3. Найдем матрицу А , транспонированную к А:

4. Сформулируем двойственную задачу: при ограничениях:

►