Варианты разрешимости задачи линейного программирования
Для построения такого плана положим, тогда Существует такое малое, что все базисные компоненты неотрицательны, то есть решение допустимое. Зацикливание происходит тогда, когда в одной точке пересекаются границы гиперпространств, больших, чем количество свободных переменных. Это приращение нужно следует настолько малым, чтобы это было несущественно для заказчика и различимо для вычислительных… Читать ещё >
Варианты разрешимости задачи линейного программирования (реферат, курсовая, диплом, контрольная)
Теорема 5: О возможности увеличения критерия.
Пусть — невырожденный опорный план, существует оценка свободной переменной меньше нуля. Тогда план не оптимальный и существует решение с лучшим значением критерия.
Для построения такого плана положим, тогда Существует такое малое, что все базисные компоненты неотрицательны, то есть решение допустимое.
Теорема 6: О возможности построения нового опорного плана.
Если — невырожденный опорный план, существует, среди коэффициентов текущей матрицы условий существуют, то решение не оптимальное и существует новый опорный план с лучшим значением критерия.
.
Действительно, построив план вида и увеличивая, заметим, что по крайней мере одна базисная переменная уменьшается. Когда одна из уменьшающихся базисных переменных обратится в 0, получим новый опорный план с лучшим значением критерия.
Теорема 7: Условие неограниченности критерия.
Если — невырожденный опорный план, существует, среди коэффициентов текущей матрицы условий нет положительных, то задача неразрешима из-за неограниченности критерия ().
Действительно, решение остается допустимым при любом :
.
а критерий неограниченно растет.
Теорема 8: Признак альтернативного оптимального решения.
Пусть — невырожденный оптимальный план (выполняется признак оптимальности ,), и существует оценка свободной переменной. Тогда оптимальный план не единственный и существует другой план с таким же значением критерия.
.
Действительно, на планах критерий.
не изменяется, значит, все эти планы оптимальны.
В таком случае оптимальные решения находятся на отрезке.
.
Предупреждение зацикливания симплекс-метода
Зацикливание происходит тогда, когда в одной точке пересекаются границы гиперпространств, больших, чем количество свободных переменных.
Способы предупреждения:
· придать малые приращения каждому ограничению.
Это приращение нужно следует настолько малым, чтобы это было несущественно для заказчика и различимо для вычислительных средств.
· То, что опорное решение будет вырожденным, можно выяснить на предыдущей итерации (по симплекс-таблице).
Если минимум отношения свободных членов к положительным коэффициентам разрешающего столбца достигается в нескольких строках.
надо скорректировать правило выбора разрешающей строки.
Для выбора разрешающей строки, если минимальное отношение свободных членов к положительным коэффициентам разрешающего столбца определяется неоднозначно, достаточно из этих строк выбрать ту, в которой достигается минимальное отношение элементов другого столбца к элементам разрешающего столбца. Порядок выбора этих столбцов должен быть единым в ходе решения задачи, например в порядке нумерации переменных.