Симплекс-метод с естественным базисом

Предположим, что первые т векторов системы ограничений являются

единичными, т.е.

или в векторной форме

Векторы условий называются векторами базиса, так как они образуют

базис т -мерного пространства. Поэтому в разложении (1.18) за базисные неизвестные выбираем , свободные неизвестные приравниваем

нулю и, учитывая, что , а векторы - единичные, получаем

первоначальный план

который является опорным. Выражения для целевой функции и ограничений-равенств принимают при этом следующий вид:

где - компоненты разложения векторов условий А_]- по векторам базиса

- оценка вектора .

Далее возможен один из следующих трёх случаев:

а) для всех -опорной планоптимален, так как

при любых , удовлетворяющих ограничениям (1.20), ;

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

ограничена на множестве своих планов;

в) для некоторых и для каждого такого , по крайней мере,

одно из чисел положительно-опорный план не является оптимальным и следует перейти к новому базису, вводя вектор с вместо вектора

номер г которого определяется из условия

где минимум берётся по всем , для которых . Если для нескольких

, то вектору , подлежащему вводу в базис, соответствует .

С новым опорным планом повторяют процедуру а)—в) до тех пор, пока не будет получено решение задачи [случай а)] или будет установлена неограниченность её линейной формы [случай б)]. Так как число опорных планов конечно, то один из случаев а)—в) обязательно будет иметь место через конечное число шагов.

Для реализации симплекс-метода разработан ряд алгоритмов, каждый иэ которых сводится к составлению последовательности симплексных таблиц, содержащих характеристики опорного плана данной итерации. Для так называемого прямого алгоритма симплекс-метода (или I алгоритм) симплекс-таблица имеет вид табл. 1.1, где

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

где к и г - номера векторов условия, включаемого в базис (к —направляющий столбец) и исключаемого из базиса (г - направляющая строка) на соответствующей итерации.