Этапы симплекс-метода

1. Проверка признака оптимальности ()

2. Если есть ,то решение не оптимальное. Тогда выбираем столбец с минимальной оценкой. Его назовем разрешающим.

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

1. Текущая симплекс-таблица преобразуется по следующему правилу:

• разрешающая строка делится на разрешающий элемент:

• разрешающий столбец заменяется единичным.

• все остальные элементы симплекс-таблицы могут быть пересчитаны по правилу четырехугольника:

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

Или новое значение элемента равно произведению элементов на главной диагонали минус произведение элементов на противоположной диагонали, и все это деленное на разрешающий элемент.

Замечание: Если в разрешающей строке был нулевой элемент, значит этот столбец не меняется; если в разрешающем столбце есть нулевой элемент, то соответствующая строка не меняется.

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

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

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

Для построения такого плана положим , тогда

(15)

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

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

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

,

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

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

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

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

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

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

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

Действительно, на планах вида (15) критерий не изменяется, значит, все эти планы оптимальны.

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

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

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

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

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

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

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

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

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

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

Б.п.	x1	x2	x3	x4	x5	x6	b
x1	1	3	2	-2	0	0	6	2	1/3
x5	0	2	-6	4	1	0	4	2	0/2=0	-6/2=-3	4/2=2
x6	0	5	-15	5	0	1	10	2	0/5=0	-15/5=-3	5/5=1
F	0	-7	-2	3	0	0	50

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