Источник:
Орлов Ю.К., Мокрый Г.В. "Методические рекомендации по использованию методов линейного программирования при создании комплексной автоматизированной системы информации": Д, 1990, 92с.

ПОИСК ОПТИМАЛЬНОГО РЕШЕНИЯ

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

    Поиск оптимального решения сводится к переходу от полученной вершины области допустимых решений к соседней, в которой значение z больше Q. Этот процесс продолжается до тех пор, пока не будет установлено, что функция z не ограничена сверху или пока не будет найдена вершина с максимальным значением z.
    Таким образом, в качестве направления движения выбирается ось, для которой . Откуда и . Следовательно, для увеличения функции z следует двигаться по оси, расположенной в таблице над отрицательным коэффициентом z-строки.
    В качестве разрешающего берем столбец с . Пусть он лежит в s-м столбце. Для этого столбца выбираем минимальное положительное отношение элементов столбца свободных членов к элементам разрешающего столбца.
    После шага модифицированных жордановых исключений с разрешающим элементом знак изменится на противоположный.
    Описанную процедуру продолжаем до тех пор, пока не избавимся от отрицательных коэффициентов в целевой строке или пока не придем к случаю отсутствия положительных коэффициентов в столбце с отрицательным . Последнее свидетельствует о неограниченности сверху функции z. Действительно, если все , получим, что любое ограничение

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

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

  

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