Описание симплекс-метода.

Выразим целевую функцию через свободные переменные и допишем к задаче:

f = a₀ -a_r+1х_r+1 -... -a_nх_n.

Для базисного решения получим f =a₀.

Перед нами стоит цель: уменьшить значение функции f за счет изменения свободных переменных. Свободные переменные для базисного решения равны 0, следовательно, мы можем их только увеличивать. Попробуем увеличивать х_j, где r+1 £j £ n. Можем ли мы за счет увеличения этой свободной переменной уменьшить значение целевой функции? Если a_j, положительное, то f уменьшается, а если a_j отрицательное или 0, то нет. Т.е. если a_j отрицательное, то нет смысла увеличивать х_j, и наоборот.

Итак, если все a_j отрицательны, то данное базисное решение является оптимальным, а минимум целевой функции f равен a₀.

Как перейти от одного базисного решения к другому, более хорошему? Пусть есть такое j, что a_j >0. При этом можно улучшить целевую функцию за счет увеличения х_j. Все остальные свободные переменные оставляем равными 0. Тогда имеем:

Посмотрим, до какой степени можно увеличивать х_j. Для этого надо определить, что происходит при этом с базисными переменными. Если коэффициент а_ij не положителен, то значение x_i при увеличении x_j тоже растет и это не препятствует неограниченному росту x_j.

Если получилось, что в выбранном столбце все a_ij<=0, то задача поставлена некорректно, а оптимального решения не существует, поскольку можно бесконечно увеличивать х(_j) и вместе с ним бесконечно уменьшать значение целевой функции, а решение все время будет оставаться допустимым.

Пусть среди а_ij есть положительные числа. Тогда при возрастании х_j будут уменьшаться соответствующие базисные переменные x_i. При этом увеличивать х_j можно до тех пор, пока первая из переменных х₁, х₂...,х_r обратится в 0. Это произойдет, когда х_j примет значение минимальной из величин b_i/а_i,_j, у которых a_ij>0. После этого значение переменной х_j станет отлично от 0,а какая-то из переменных х_i обратится в 0. Это означает, что на очередном шаге мы переменную х_j переводим в базисные, а х_i - в свободные.

Алгоритм симплекс-метода:

1. Заполняем исходную таблицу (считается, что исходный базис найден).

2. Ищем в нижней строке максимальный положительный элемент (кроме a0). Если таких нет, то задача решена. Пусть a_j - максимальное положительное число в нижней строчке.

3. В j-том столбце ищем положительные коэффициенты а_kj (если таких нет, то задача не имеет решения). Во вспомогательный столбец заносим b_k/а_kj. Пусть минимальный элемент во вспомогательном столбце находится в i-й строке. На пересечении разрешающего столбца (j) и разрешающей строки (i) находится разрешающий элемент a_ij.

4. Заполняем новую таблицу в следующем порядке:

a) заголовок;

b) первый столбец (вместо х_i пишем х_j);

c) единичные столбцы;

d) разрешающую строку (делим на а_ij);

e) остальные строчки по порядку.

5. Возвращаемся к пункту 2.

 

ОСНОВНАЯ ФОРМУЛА симплекс-преобразования: (пункт 4e) имеет вид: