Табличный симплекс-метод

Шаг 1. Проверка на допустимость.

Проверяем на положительность элементы столбца b (свободные члены):

1. Если среди них нет отрицательных то найдено допустимое решение (решение соответствующее одной из вершин многогранника условий) и мы переходим к шагу 2.

2. Если в столбце свободных членов имеются отрицательные элементы то выбираем среди них максимальный по модулю - он задает ведущую строку k. В этой строке так же находим максимальный по модулю отрицательный элемент ak,l - он задает ведущий столбец - l и является ведущим элементом. Переменная, соответствующая ведущей строке исключается из базиса, переменная соответствующая ведущему столбцу включается в базис. Затем снова пересчитываем симплекс-таблицу согласно правилам.

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

. Если после перерасчета в столбце свободных членов остались отрицаетельные элементы, то переходим к первому шагу, если таких нет, то ко второму.

Шаг 2. Проверка на оптимальность.

На предыдущем этапе найдено допустимое решение. Проверим его на оптимальность:

1. Если среди элементов симплексной таблицы, находщихся в строке F (не беря в расчет элемент b0 - текущее значение целевой функции) нет отрицательных, то найдено оптимальное решение.

2. Если в строке F есть отрицательные элементы то решение требует улучшения. Выбираем среди отрицательных элементов строки F максимальный по модулю (исключая значение функции b0) a0,l=min{a0,i }. Первый столбец в котором он находится будет ведущим. Для того, что бы найти ведущую строку, находим отношение соответствующего свободного члена и элемента из ведущего столбца, при условии, что они неотрицательны.

/ak,l =min {bi/ai,l } при ai,l>0, bi>0

- cтрока, для которой это отношение минимально - ведущая. Элемент ak,l - ведущий (разрешающий). Переменная, соответствующая ведущей строке (xk) исключается из базиса, переменная соответствующая ведущему столбцу (xl) включается в базис.

Пересчитываем симплекс-таблицу по формулам <http://www.uchimatchast.ru/teory/tabl_simplex.php>:

1. Если в новой таблице после перерасчета в строке F остались отрицательные элементы переходим к шагу 2

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

. Если в строке F и в столбце свободных членов все элементы положительные, то найдено оптимальное решение.

Правила преобразований симплексной таблицы.

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

1) Вместо базисной переменной xk записываем xl; вместо небазисной переменной xlзаписываем xk.

2) ведущий элемент заменяется на обратную величину ak,l'= 1/ak,l

3) все элементы ведущего столбца (кроме ak,l) умножаются на -1/ak,l

4) все элементы ведущей строки (кроме ak,l) умножаются на 1/ak,l

5) оставшиеся элементы симплекс-таблицы преобразуются по формуле ai,j'= ai,j- ai,lx ak,j/ ak,l

Схему преобразования элементов симплекс-таблицы (кроме ведущей строки и ведущего столбца) называют схемой ”прямоугольника”.

Преобразуемый элемент ai,j и соответствующие ему три сомножителя как раз и являются вершинами ”прямоугольника”.

1. Решение задачи ЛП