Линейные модели в экономике (стр. 2 )

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

, (10.2)

(10.3)

, , …, . (10.4)

Здесь , j = 1, 2, …, n – объем производства j-го вида продукции.

В более компактном виде целевая функция и система ограничений обычно записываются в виде:

,

, i = 1, 2, …, m,

, j = 1, 2, …, n.

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

Рассмотрим двойственную задачу, решение которой позволит определить условия продажи ресурсов. Обозначим оценку (цену) i-го ресурса через , тогда вектор этих оценок будет иметь вид .

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

. (10.5)

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

.

Следовательно, система ограничений задачи имеет вид

(10.6)

Кроме того, очевидно, оценки всех видов ресурсов неотрицательны:

, i = 1, 2, …, m. (10.7)

Итак, условия (10.5)–(10.7) определяют новую задачу линейного программирования. Она называется двойственной к исходной задаче (10.2)–(10.4).

Рассмотрим подробнее связь исходной и двойственной задач:

1) коэффициенты целевой функции исходной задачи являются свободными членами системы ограничений (10.6) двойственной задачи;

2) свободные члены системы ограничений (10.3) исходной задачи являются коэффициентами целевой функции двойственной задачи;

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

Далее мы узнаем, что если одна из двойственных задач имеет оптимальное решение, то и другая также имеет оптимальное решение (см. теорему 10.4).

Рассмотренная пара задач относится к так называемым симметричным парам двойственных задач. В теории двойственности рассматриваются две симметричные пары двойственных задач. Приведем их в матрично-векторной форме (слева – исходная задача, справа – двойственная ей):

1.

, , (10.8)

; .

2.

, , (10.9)

; .

Напомним, что здесь

, ,

, , .

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

Сформулируем теперь более четко правила составления двойственной задачи:

1. Целевая функция j двойственной задачи должна оптимизироваться противоположным по сравнению f образом, т. е. если , то и наоборот.

2. В правых частях ограничений исходной задачи стоят коэффициенты при неизвестных целевой функции двойственной задачи.

3. Матрицы из коэффициентов при неизвестных в левых частях ограничений обеих задач (исходной и двойственной) являются взаимно транспонированными. При этом если исходная задача имеет размер (m ограничений с n неизвестными), то двойственная – размер .

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

,

, j = 1, 2, 3.

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

.

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

Окончательно получаем двойственную задачу в виде:

,

, i = 1, 2, 3.

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

,

, .

Решение. Так как целевая функция минимизируется, то все ограничения-неравенства должны иметь вид «³». Поэтому преобразуем исходную задачу, умножив второе ограничение-неравенство на –1. Исходная задача запишется в виде

,

, .

Составим теперь двойственную задачу подобно тому, как это делалось в предыдущем примере:

,

, i = 1, 2.

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

Рассмотрим симметричную пару двойственных задач (10.8):

I. , II.