Cимплекс-метод

Задача ЛП во второй канонической форме

Максимизировать линейную функцию

на множестве векторов х= (х₁,х₂, …х_n),

удовлетворяющих условиям:

1. х_j ³0 для j= 1, ...,n (1)

2.

Cимплекс-метод

1. Симплекс-метод – многошаговый. На каждом шаге происходит переход от одного базиса к другому, при этом значение целевой функции улучшается (или не ухудшается).

2. Базисные переменные принимают положительные значения, внебазисные равны нулю.

3. Оптимальный базис – это базис, от которого нельзя перейти к другому базису, улучшающему значение целевой функции

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

Это дает следующее:

будут известны значения базисных переменных;

будет известно, насколько улучшилось значение целевой функции;

5. Базисные столбцы должны быть приведены к единичным векторам на основе преобразований всех ограничений и целевой функции задачи ЛП. Для этого используется метод Жордана–Гаусса.