Определение опорного решения

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

В исходной формулировке задачи ЛП могут иметь ограничения в виде равенств и неравенств.

Чтобы привести к основной задаче ЛП (получить равенства), в неравенства вводят вспомогательные (дополнительные) переменные, например y_i ³ 0.

Так, вместо неравенств , где - число равенств в системе ограничений, будут , где верхние знаки соответствуют приведенному направлению неравенства, а нижние – обратному.

Для применения симплекс-таблиц равенства и неравенства удобно записать в стандартной форме:

целевая функция .

Теперь их можно записать в симплексную таблицу:

		…		…
		…		…
…	…	…	…	…	…	…
		…		…
		…		…
…	…	…	…	…	…	…
		…		…
F		…		…

В верхнюю часть таблицы заносятся равенства, а после них неравенства. В последнюю строку таблицы заносятся коэффициенты максимизируемой целевой функции со знаками, учитывающими вынос знака «минус» ко всем x_j, отнесенным в исходной симплекс-таблице к числу свободных.

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

После подготовительного этапа переходят к этапу нахождения опорного решения.

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