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

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

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

- в задаче на максимум ; (2.3.1)

- в задаче на минимум . (2.3.2)

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

- в задаче на максимум ; (2.3.3)

- в задаче на минимум . (2.3.4)

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

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

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

(2.3.5)

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

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

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

- в задаче на максимум <0 и (2.3.7)

- в задаче на минимум >0 и . (2.3.8)