Двойственные задачи. Экономический смысл двойственных переменных

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

Задача минимизации линейной формы

ПРИ УСЛОВИИ

называется сопряженной к задаче (52.16)'-(52.18).

Обе задачи образуют пару двойственных задач.

Установим ряд частных выводов.

Пусть X и Y — некоторые планы задач.

Тогда

т.е. для любых планов L(X) < L(Y).

2. _Пусть для планов X* и Y* имеет место равенство

Тогда достигается максимум

L(X). С учетом ] : делаем вывод об оптимальности планов X* и Y*.

3. Пусть линейная форма сопряженной задачи не ограничена снизу. Тогда существует план Y такой, что B Y < М, где М > 0 сколь угодно велико.

т

Если существует хотя бы один план X исходной задачи, то С X < < BTY < М, чего при конечных значениях X не может быть.

Отсюда можно получить следующее утверждение.

Теорема 52.1 (первая теорема двойственности).

Если одна из двойственных задач разрешима, то разрешима и сопряженная задача. При этом для оптимальных планов X* и Y* этих задач имеет место равенство значений целевых линейных форм С X* = В Y*.

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

Определение 52.11. Условия называют

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

Теорема 52.2 (вторая теорема двойственности).

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

Пример. Предприятие производит продукты двух видов: А и Б. Цена реализации единицы каждого вида продуктов и затраты сырья при производстве, а также имеющиеся запасы сырья представлены в табл. 52.9.

Таблица 52.9

Исходные данные

Тип сырья

Товар

Запас сырья

А

Б

10

20

100

20

10

150

$

15

10

200

Цена

15

10

Задача сводится к следующему: найти максимальное значение линейной формы (целевой функции)

при условиях

Эта задача имеет решение:

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

Она решена выше:

Можно сделать два полезных вывода:

  • — если в исходной задаче нет условия неотрицательности на некоторую переменную, то построенное по коэффициентам при этой переменной ограничение сопряженной задачи выполняется в форме равенства;
  • — если некоторое (основное) ограничение исходной задачи задано равенством, то двойственное условие сопряженной задачи не существует.

Экономическая интерпретация пары двойственных задач.

Обозначим Xj — объем производства у'-го вида продукта, Ь, — запас /-го вида сырья, ау — затраты /-го вида сырья на производство единицы у'-го продукта и q — стоимость единицыу'-го продукта.

Необходимо максимизировать выручку от продажи

произведенной продукции при условиях

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

Отсюда появляется задача минимизации при

условиях

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

некотором i выполняется неравенство то /-е сырье не является лимитирующим и условная его стоимость у, = 0.

Таким образом, в рассмотренной постановке двойственная задача является математической формулировкой объективной оценки всех производственных факторов.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >