4.5. Основные теоремы

Сформулируем, во-первых, теорему, которая является частным случаем теоремы 3.5 (когда φ(x) линейна) и поэтому в отдельном доказательстве не нуждается.

Будем обозначать функцию Лагранжа для задачи (4.1) так:

Теорема 4.1. Для того чтобы точка х^*∈R₁ была оптимальной для основной задача линейного программирования, необходимо и достаточно существование y^*≥0 такого, чтобы пара х^*, y^* была седловой точкой функции Лагранжа L₁(x, y) в области х≥0, y≥0, то есть

Замечание 1. Из соотношения (3.35) следует, что необходимым и достаточным условием оптимальности х^* для задачи (4.1) является следующее представление вектора с:

(4.5)

где

и

Замечание 2. Из теорем 3.3 и 4.1 следует, что для х^* и y^* выполняются следующие равенства:

(4.6)

Теорема 4.2 (двойственности). Прямая и двойственная задачи либо обе имеют оптимальные точки х^* и y^*, причем

либо обе их не имеют.

Доказательство. Рассмотрим функцию Лагранжа для задачи (4.2). Для этого запишем эту задачу в виде основной задачи линейного программирования, то есть в виде (4.1).

Ясно, что задача (4.2)

эквивалентна задаче

А для этой задачи, поскольку она записана в виде основной задачи, функцией Лагранжа будет

Седловой точкой для L₂(y, x) в области y≥0, x≥0 будет пара y', x' такая, что

Сравнивая (4.8) и (4.3), получаем

Из (4.10), (4.9) и (4.4) следует, что если х^*, y^* - седловая точка для L₁(x, y), то y^*, х^* - седловая точка для L₂(y, x), а значит, либо x^* и y^* оптимальны соответственно для задач (4.1) и (4.2), либо, когда седловая точка отсутствует, то и задача (4.1), и задача (4.2) не имеют решений.

Наконец, равенство (4.7) следует из формул (4.6).

Теорема 4.3. Для любых допустимых x∈R₁ и y∈Q₁ выполняется неравенство

Доказательство. Из неравенств, определяющих R₁ и Q₁, следует

Теорема 4.4. Если x^*∈R₁ и y^*∈Q₁, а

то x^* и y^* оптимальны соответственно для задан (4.1) и (4.2), и обратно.

Доказательство. Для любого x∈R₁ в силу (4.11) и условия теоремы будет

то есть х^* оптимален. Аналогично доказывается оптимальность y^*. Обратное утверждение теоремы содержится в теореме двойственности 4.2.

Теорема 4.5. Если линейная функция <c, x>, c≠0 ограничена снизу на непустом множестве R₁, то существует точка x^*∈R₁ такая, что

Доказательство. Во-первых, запишем неравенства, определяющие множество R₁, в следующем виде:

Здесь , где Е - единичная матрица, а d^Т = (b^Т, 0, 0, ..., 0).

Обозначим Тогда

является границей множества R₁, причем Γ≠0, поскольку R₁ является пересечением выпуклого замкнутого множества {х: х≥0}, заведомо обладающего граничными точками, с выпуклым замкнутым множеством {х: Ах≥b}.

Не умаляя общности, можно считать, что

лишь для , s≤m + n, поэтому

Доказательство будем вести по индукции числа n - размерности пространства Е_n. Для Е₁ (одномерный случай) допустимое множество R₁ может быть либо точкой, либо отрезком, либо полупрямой, для которых теорема очевидна.

Предположив, что теорема справедлива для Е₁, Е₂,... E_k-1, докажем ее для Е_k.

Так как L_i∩R₁⊂E_k-1 (), то по индуктивному предположению для любого найдется x_i∈L_i∩R₁ такой, что

Из определения Г следует, что существует x^*∈Г такой,

что

Осталось показать, что

Для этого достаточно убедиться, что для любой точки х∈R₁\Г существует такая граничная точка x'∈Г, что

Рассмотрим точку ̄х = х - λс, λ>0. Поскольку x - внутренняя точка для R₁, то ̄х = х - λс ∈ R₁ по крайней мере для малых X. По предположению <с, ̄x> ограничена снизу:

Следовательно,

Тогда существует

(4.12)

где минимум берется по всем к таким, что

Ясно, что ̄х = х - λ'с ∈Г. В самом деле, если x' - внутренняя точка для R₁, то найдется λ" >λ>0 такое, что х - λ"с ∈R₁. Но тогда

А это противоречит (4.12). Итак,

Теорема доказана.

Замечание. Следует обратить внимание на то, что теорема справедлива, вообще говоря, лишь для задач линейного программирования.

Рассмотрим, например, следующую задачу: минимизировать х₂ на множестве

Очевидно, что X выпукло и замкнуто,

но не существует точки из X, в которой достигается inf_X x₂ (рис. 4.2).

Рис. 4.2

Теорема 4.6. Для существования решения одной из двойственных задач (и, следовательно, обеих) необходимо и достаточно, чтобы

Доказательство. Необходимость очевидна.

Достаточность. Пусть y∈Q₁ тогда для любого x∈R₁ имеет место (4.11):

а тогда по теореме 4.5 задача (4.1) имеет решение и, значит, имеет решение и задача (4.2) (ввиду теоремы 4.2).

Следствие а^*. Если <c, x> (<b, y>) неограничена снизу на R₁ (сверху на Q₁), то

^* (В скобках приводится двойственное утверждение.)

Следствие б. Если Q₁ = ∅ (К₁ = ∅), a К₁ ≠ ∅ (Q₁ ≠ ∅), то R₁ (Q₁) неограничено и <c, x> неограничена снизу на R₁ (<b, y> неограничена сверху на Q₁).

Теорема 4.7. Если

и если существуют х₁, х₂, ..., х_M такие, что

(а)

x_i∈R₁ (),

(б)

(), то

Доказательство. Предположим, что

Тогда

Учитывая (4.13), получаем

Сделаем индуктивное предположение:

и докажем, что

Действительно,

Отсюда

И так как (поскольку k<М), то

А тогда (см. (4.13))

Теорема 4.8. Если задача (4.1) имеет решение х^*, то существует угловая точка х такая, что

Доказательство. 1) Если R₁ ограничено, то из теоремы 2.6 следует, что существуют такие угловые точки х₁, х₂, ..., x_N множества R₁, что для любого x∈R₁ и, в частности, для х^* будет

α_i≥0 ()

Вычеркнем из системы точек х₁, х₂, ..., x_N те, которым соответствуют α_i = 0. Не ограничивая общности, можем полагать, что это точки х_M+1, х_M+2, ..., x_N. Тогда

α_i>0 ()

то есть выполняются условия теоремы 4.7, откуда и следует утверждение теоремы

2) Пусть R₁ неограничено, а x^* оптимален. Очевидно, что для достаточно большого числа μ>0 множество

таково, что

Так как пересечение "ортанта" x≥0 с множеством L ограничено, то и R₁∩L ограничено и, следовательно (теорема 2.6), существуют угловые точки x₁, x₂, ..., х_M множества R₁∩L такие, что

Если хотя бы одна точка x_i∉l, то теорема доказана, поскольку тогда х_i будет угловой точкой множества R₁. Если все x_i∈l (), то из представления

α_i>0 ()

следует x^*∈l, что противоречит выбору числа μ>0 при построении множества L.