Варианты разрешимости задачи линейного программирования

Теорема 5: О возможности увеличения критерия.

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

Для построения такого плана положим, тогда Существует такое малое, что все базисные компоненты неотрицательны, то есть решение допустимое.

Теорема 6: О возможности построения нового опорного плана.

Если — невырожденный опорный план, существует, среди коэффициентов текущей матрицы условий существуют, то решение не оптимальное и существует новый опорный план с лучшим значением критерия.

.

Действительно, построив план вида и увеличивая, заметим, что по крайней мере одна базисная переменная уменьшается. Когда одна из уменьшающихся базисных переменных обратится в 0, получим новый опорный план с лучшим значением критерия.

Теорема 7: Условие неограниченности критерия.

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

Действительно, решение остается допустимым при любом :

.

а критерий неограниченно растет.

Теорема 8: Признак альтернативного оптимального решения.

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

.

Действительно, на планах критерий.

не изменяется, значит, все эти планы оптимальны.

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

.

Предупреждение зацикливания симплекс-метода

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

Способы предупреждения:

· придать малые приращения каждому ограничению.

Это приращение нужно следует настолько малым, чтобы это было несущественно для заказчика и различимо для вычислительных средств.

· То, что опорное решение будет вырожденным, можно выяснить на предыдущей итерации (по симплекс-таблице).

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

надо скорректировать правило выбора разрешающей строки.

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