Улучшение опорного решения

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

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

Перейдем к новому опорному решению , введем в базис вектор и исключим из базиса вектор . В этом случае приращение целевой функции равно

.

Решение невырожденное, поэтому параметр , вычисляемый по формуле (4.5), отличен от нуля ( > 0). Так как > 0, , то

.

Следовательно, значение целевой функции на новом опорном решении будет больше, чем на первом .

Доказательство для задачи на минимум аналогично.

Следствие 1 (условие наибольшего приближения к оптимальному решению). Для наибольшего изменения целевой функции при улучшении опорного решения необходимо выбор вектора, выводимого из базиса (с номером l) и вводимого в базис (с номером k), производить из условий:

– в задаче на максимум ; (4.10)

– в задаче на минимум . (4.11)

В упрощенном варианте выбор вектора, вводимого в базис, можно производить с использованием условий:

– в задаче на максимум ; (4.12)

– в задаче на минимум . (4.13)

Этот вариант перехода к новому опорному решению обычно используется при расчетах на ЭВМ.

Следствие 2 (признак оптимальности опорного решения). Опорное решение задачи линейного программирования на максимум (минимум) является оптимальным, если для любого вектора условий оценка разложения по базису опорного решения неотрицательная (неположительная), т. е.

– в задаче на максимум ; (4.14)

– в задаче на минимум . (4.15)

Действительно, если Z(x) , , , то

,

т. е. – оптимальное решение. Для задачи на минимум доказательство аналогично.

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

. (4.16)

Здесь предполагается, что в базис оптимального решения входят первые m векторов.

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

$ k Î {m+1, m+2, ..., n}: . (4.17)

Следствие 5 (признак отсутствия оптимального решения ввиду неограниченности целевой функции). Задача линейного программирования не имеет решения ввиду неограниченности целевой функции, если для какого-либо из векторов условий с оценкой , противоречащей признаку оптимальности, среди коэффициентов разложения по базису опорного решения нет положительного, т. е.

– в задаче на максимум и ; (4.18)

– в задаче на минимум и . (4.19)