Алгоритм отыскания опорного решения задачи ЛП

Этот алгоритм выполняется сразу после записи симплекс-таблицы.

Алгоритм 2:

1. Просматриваем столбец свободных членов (не смотря на свободный член строки ). Если все свободные члены , то данная таблица уже соответ­ствует опорному решению, иначе переходим к п. 2.

2. В столбце свободных членов выбираем первый по порядку отрицатель­ный элемент и в этой строке находим еще один отрицательный элемент. Если такого элемента нет, то задача ЛП не имеет решения, если есть, то переходим к п. 3.

3. Столбец с найденным отрицательным элементом объявляем генеральным.

4. В генеральном столбце фиксируем элементы, имеющие такой же знак, что и знак соответствующих свободных членов, и среди них в качестве генерального элемента выбираем тот, отношение к которому соответствующего свободного члена минимально:
, знак = знак .

5. По выбранному генеральному элементу выполняем стандартное сим­плекс- преобразование (алгоритм 1) и переходим к п. 1.

Если при вычислениях нет ошибок, то количество отрицательных сво­бодных членов должно уменьшаться или должна уменьшаться их абсолют­ная величина.

Примечание к пункту 2:

Задача ЛП не имеет решения, когда соответствующая строка СТ имеет, например, вид: , которая не удовлетворяется ни при

каких неотрицательных переменных.