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

, ,

, .

(Напомним, что если задача (I) имеет размер , то задача (II) – размер .)

Отметим основное неравенство теории двойственности.

Теорема 10.3. Пусть X – любое допустимое решение исходной задачи (I), а Y – любое допустимое решение двойственной задачи (II). Тогда имеет место неравенство

. (10.10)

Доказательство. Так как все переменные в обеих задачах неотрицательные, получаем (с учетом ):

. (*)

В силу ассоциативности умножения матрицы и с учетом

. (**)

Соединяя (*) и (**), получаем

,

что и требовалось доказать.

Заметим, в частности, что, применительно к задаче, рассмотренной в примере 10.3, неравенство (10.10) означает

.

Следствие из основного неравенства: если допустимое множество одной из задач I, II не пусто, то целевая функция другой задачи ограничена в направлении экстремума на своем допустимом множестве.

Действительно, пусть, например, множество D исходной задачи I не пусто, т. е. существует хотя бы одна точка . Тогда, согласно неравенству (10.10), для любой точки Y из допустимого множества задачи II выполняется неравенство , т. е. все значения функции j ограничены снизу одним и тем же числом .

Теорема 10.4 (основная теорема двойственности). Если одна из двойственных задач I или II имеет оптимальное решение, то и другая задача имеет оптимальное решение, причем экстремальные значения целевых функций равны:

. (10.11)

(Примем эту теорему без доказательства.)

Одним из важных следствий основной теоремы двойственности является критерий оптимальности допустимых решений. Рассмотрим его. Пусть и – допустимые решения исходной и двойственной задач I и II. Для того чтобы эти решения были оптимальными, необходимо и достаточно выполнение равенства

. (10.12)

Доказательство. 1. Необходимость. Пусть и – оптимальные решения. Тогда , и равенство (10.12) следует из основной теоремы двойственности.

2. Достаточность. Пусть выполняется неравенство (10.12), и пусть – произвольная точка, принадлежащая допустимому множеству исходной задачи. Тогда, в силу основного неравенства (10.10), имеем . Следовательно, , т. е. – точка максимума. Аналогично доказывается, что точка , для которой выполняется равенство (10.12), есть точка минимума.

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

, j = 1, 2, …, n; (10.13)

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

(Эту теорему примем без доказательства.)

Выясним смысл равенств (10.13) и (10.14). Например, второе из них означает, что если при подстановке оптимального решения в систему ограничений (10.3) i-е ограничение исходной задачи выполняется как строгое неравенство, то i-я координата оптимального решения двойственной задачи равна нулю. Напротив, если i-я координата оптимального решения двойственной задачи отлична от нуля, то i-е ограничение исходной задачи при подстановке оптимального решения обращается в равенство.

Эти условия устанавливают в некотором смысле равновесие между задачами I и II. Поэтому терему 10.5 называют также теоремой равновесия.

Пример 10.4. Решить задачу:

,

.

Решение. В данной задаче три переменных. Решить ее графически, подобно тому, как это сделано в примере 10.1, нельзя. Составим для этой задачи двойственную, решим ее графическим методом, а затем, применяя вторую теорему двойственности, решим данную, исходную задачу.

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

,

,

.

Решим ее графическим методом. На рис. 10.2 изображены область допустимых решений, нормаль и оптимальное решение – точка (4, 3).

Рис. 10.2

Теперь находим решение исходной задачи с помощью второй теоремы двойственности. Так как третье ограничение двойственной задачи есть строгое неравенство при , то . Далее, так как , то , откуда . Следовательно, оптимальное решение исходной задачи есть точка (1, 2, 0).

Пример 10.5. С помощью второй теоремы двойственности решить задачу:

,

.

Решение. Составим для этой задачи двойственную. Сначала приведем все неравенства к виду «³», так как целевая функция минимизируется:

,

, , .

Напишем теперь двойственную задачу:

,

.

Эта задача совпадает с задачей, уже рассмотренной в примере 10.1 (только там переменные , а здесь – ). Воспользуемся ее решением: .

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