2.1. Определение и экономический смысл двойственной злп

Пусть прямая задача записана в каноническом виде:

 

Задачей, двойственной к ЗЛП (2.1)-(2.3), называется следующая ЗЛП

Из приведенного определения следует, что двойственная ЗЛП строится по сле­дующим правилам:

1)  Каждому ограничению прямой задачи соответствует переменная двойственной задачи, т.е. число переменных двойственной задачи (y₁,.,.,y_n) равно числу ограничений прямой задачи.

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

3). Матрица функциональных ограничений двойственной задачи получается путем транспонирования матрицы функциональных ограничений прямой задачи.

для прямой  задачи I       

для двойственной задачи II     

4)  Вектор целевой функции прямой задачи становится вектором правой части ограничений двойственной задачи, а вектор правой части прямой задачи - вектором це­левой функции двойственной задачи.

5)  Если целевая функция прямой задачи максимизируется, то целевая функция двойственной задачи минимизируется, а ограничения имеют вид , и наоборот.

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

В случае, когда ограничения заданы в виде неравенств двойственная задача задается соотношениями:

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

  

Пример 2.1. Составить задачу, двойственную следующей задаче:

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

Решение.

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

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

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

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

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

 >

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

Ранее была рассмотрена задача об использовании ресурсов (эконо­мико-математическая модель и содержательная интерпретация этой задачи I представлены в левой части табл. 6.1). В приведен­ной модели   обозначает запас ресурса — число единиц ресурса , потребляемого при производстве едини­цы продукции  ;   — прибыль (выручка) от реали­зации единицы продукции   (или цена продукции ).

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

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

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

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

Составить такой план выпуска продукции X =(*], х2, ..., х„), при котором прибыль (выручка) от реализации продукции будет мак­симальной при условии, что по­требление ресурсов по каждому виду продукции не превзойдет имеющихся запасов

Найти такой набор цен (оценок) ресурсов Y = (yh уъ ..., ут), при котором общие затраты на ресурсы будут минимальными при условии, что затраты на ресурсы при произ­водстве каждого вида продукции будут не менее прибыли (выручки) от реализации этой продукции

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

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