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

Пусть имеется ОЗЛП с ограничениями-равенствами, записанными в стандартной форме:

(7.1)

разрешенными относительно базисных переменных у₁,у₂,…,у_m, которые выражены через свободные переменные х₁,х₂,…,х _n. В каждой вершине ОРД (опорном решении) по крайней мере n переменных должны обращаться в нуль. Попробуем получить опорное решение, полагая в формулах (7.1) все свободные переменные равными нулю.

Имеем:

(7.2)

Если все свободные члены b₁,b₂,…,b_m в уравнениях (7.1) неотрицательны, это значит, что опорное решение уже получено; этот случай нас не интересует. Рассмотрим случай, когда среди свободных членов b₁,b₂,…,b_m есть отрицательные. Это значит, что решение (7.2) не является опорным – оно вообще не допустимо, и опорное решение еще предстоит найти. Для этого мы будем шаг за шагом обменивать местами базисные и свободные переменные в уравнениях (7.1) до тех пор, пока не придем к опорному решению или не убедимся, что его не существует. Последнее бывает в случае, когда система уравнений (7.1) несовместима с неравенствами

т.е. у нее нет неотрицательных решений.

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

Пусть имеется одно из уравнений (7.1) с отрицательным свободным членом. Ищем в этой строке отрицательный элемент α_ij. Если такого элемента нет (все элементы α_ij≥0), это знак того, что система уравнений (7.1) несовместима с неравенствами (7.3). Действительно, при отсутствии отрицательных элементов в строке вся правая часть соответствующего уравнения может быть только отрицательной, а это противоречит условиям неотрицательности переменных.

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

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

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