Исходные предпосылки симплексного метода

1. Существует такая точка многогранника решений, в которой линейная функция достигает своего оптимального решения.

2. Каждой угловой точке многогранника решений соответствует опорный план.

3. Каждый опорный план определяется системой линейно независимых векторов, которые содержатся в данной системе, состоящей из векторов.

4. Для отыскания оптимального плана достаточно исследовать только опорные планы.

5. Максимальное число опорных планов данной задачи – это число сочетаний из элементов по :

, где .

Симплексный метод является схемой, позволяющей осуществлять упорядоченный переход от одного опорного плана к другому.

Построение первоначального опорного плана

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

(1)

при ограничениях:

; .

В векторной форме система будет выглядеть так:

, (2)

где

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

В выражении (2) – базисные переменные, а – свободные переменные. Приравняем свободные переменные нулю и учитывая получим первоначальный опорный план:

. (3)

Данному опорному плану соответствует разложение:

. (4)