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

Независимые переменные, на знаки которых наложены ограничения называютсянесвободными, а переменные, не имеющие таких ограничений, называются свободными.

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

Если же в таблице (6) имеется хотя бы один отрицательный свободный член , то получаемый план не является опорным.

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

Разрешающий элемент симплексной таблицы выбирается по правилу:

1) Отыскивается строка с отрицательным свободным членом, если их несколько, то выбирается строка с наибольшим по модулю отрицательным свободным членом. Если среди коэффициентов взятой строки нет отрицательных, то система №2 несовместна.

2) Если в рассматриваемой строке имеются отрицательные коэффициенты, то выбирается любой из них (обычно наибольший по абсолютной величине) и столбец с этим коэффициентом принимается за разрешающий.

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

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