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

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

Прямая задача:

(3.1)

при условиях:

(3.2)

. (3.3)

Необходимо определить, какое количество продукции каждого j- го вида необходимо изготовлять в процессе производства, чтобы максимизировать общую выручку от реализации продукции предприятия. Причем известны: имеющиеся объемы ресурсов – ; нормы затрат i-го вида ресурса на производство единицы j - го вида продукции – , а также – цены реализации единицы j- ой продукции.

Рассмотрим теперь эту самую задачу с другой точки зрения. Допустим, что при определенных условиях целесообразно продавать некоторую часть или все имеющиеся ресурсы. Необходимо определить цены ресурсов. Каждому ресурсу поставим в соответствие его оценку Условно будем считать, что – цена единицы i-го ресурса.

На изготовление единицы j - го вида продукции тратится согласно модели (3.1)—(3.3) m видов ресурсов в количестве соответственно . Поскольку цена единицы i-го вида ресурса равняется , то общая стоимость ресурсов, которые тратятся на производство единицы j - го вида продукции, исчисляется таким образом:

.

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

.

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

.

Итак, в результате имеем двойственную задачу:

(3.4)

при условиях:

(3.5)

(3.6)

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

Заметим, что содержание величин – условные цены, которые выражают уровень «ценности» соответствующего ресурса для данного производства. Английский термин«shadow prices» в литературе переводится как «оценка» или «теневая, неявная цена». Академик Л.В.Канторович назвал их объективно обусловленными оценками соответствующего ресурса.

Задача (3.4)-(3.6) есть двойственной или сопряженной к задаче (3.1)-(3.3), которую называют прямой (основной, начальной). Понятие двойственности есть взаимным. По сути речь идет об одной и той же задаче, но с разных точек зрения. Действительно, не тяжело убедиться, что двойственная задача к (3.4)-(3.6) совпадает с начальной. Поэтому каждую из них можно считать прямой, а другую – двойственной. Симметричность двух таких задач очевидная. Как в прямой, так и в двойственной задаче используют один набор начальных данных: , ; . Кроме того, вектор ограничений начальной задачи становится вектором коэффициентов целевой функции двойственной задачи и наоборот, а строки матрицы А (матрицы коэффициентов при переменных из ограничений прямой задачи) становятся столбцами матрицы коэффициентов при переменных в ограничениях двойственной задачи. Каждому ограничению начальной задачи отвечает переменная двойственной и наоборот.

Начальная постановка задачи и математическая модель может иметь вид как (3.1)-(3.3), так и (3.4)-(3.6). Итак, как правило, говорят о паре сопряженных задач линейного программирования.