1. Симплекс-таблица, стандартный алгоритм симплекс-преобразования

Существует много форм симплекс-таблиц (СТ). Мы рассмотрим наибо­лее компактную форму, в которой строки — базисные переменные, а столбцы свободные переменные. Каждая СТ содержит коэффициенты модели задачи ЛП. Для записи СТ необходимо представить ОЗЛП в стандартной форме:

т.е. на первом месте свободный член, а коэффициенты при свободных пере­менных меняют знак.

Рассмотрим порядок вычислений для перехода в новую вершину. Пусть нам необходимо выполнить симплекс-преобразование . Тогда нужно получить новую симплекс-таблицу. Для этого выполним ал­горитм.

Алгоритм 1:

1. Отыскиваем в СТ элемент и объявляем его генеральным. Тогда i-я строка и j -й столбец - генеральные.

2. Вычисляем величину, обратную генеральному элементу, и записываем ее в нижней части генеральной клетки:

3. Все элементы генеральной строки умножаем на . Результат записываем в нижней части соответствующих клеток.

4. Все элементы генерального столбца умножаем на . Результат записы­ваем в нижней части клеток.

5. Отмечаем верхние элементы генеральной строки и нижние элементы генерального столбца.

6. В каждой клетке, не принадлежащей ни генеральному столбцу, ни гене­ральной строке, в нижнюю часть записываем произведение отмеченных элементов, стоящих в том же столбце и той же строке, что и данная клетка.

7. Переписываем СТ, заменяя в соответствии с табл. 2:

2. Алгоритм отыскания опорного решения задачи лп

Этот алгоритм выполняется сразу после записи симплекс-таблицы.

Алгоритм 2:

1. Просматриваем столбец свободных членов (не смотря на свободный член строки ). Если все свободные члены , то данная таблица уже соответ­ствует опорному решению, иначе переходим к п. 2.

2. В столбце свободных членов выбираем первый по порядку отрицатель­ный элемент и в этой строке находим еще один отрицательный элемент. Если такого элемента нет, то задача ЛП не имеет решения, если есть, то переходим к п. 3.

3. Столбец с найденным отрицательным элементом объявляем генеральным.

4. В генеральном столбце фиксируем элементы, имеющие такой же знак, что и знак соответствующих свободных членов, и среди них в качестве генерального элемента выбираем тот, отношение к которому соответствующего свободного члена минимально: , знак = знак .

5. По выбранному генеральному элементу выполняем стандартное сим­плекс- преобразование (алгоритм 1) и переходим к п. 1.

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

Примечание к пункту 2:

Задача ЛП не имеет решения, когда соответствующая строка СТ имеет, например, вид: , которая не удовлетворяется ни при

каких неотрицательных переменных.

3. Алгоритм отыскания оптимального решения задачи лп

Этот алгоритм выполняется после того, как найдено опорное решение, то есть когда в симплекс-таблице все свободные члены .

Алгоритм 3:

1. Просматриваем элементы строки (несмотря на свободный член). Если все элементы , то данная симплекс-таблица уже соответствует опти­мальному решению, иначе переходим к п. 2.

2. В строке выбираем наибольший положительный элемент и соответст­вующий столбец объявляем генеральным.

3. В генеральном столбце находим положительные элементы. Если таких нет, то задача не имеет оптимального решения, иначе переходим к п. 4.

4. Среди положительных элементов генерального столбца выбирается тот, отношение к которому соответствующего свободного члена минимально: , , .

5. По выбранному генеральному элементу осуществляем симплекс- преобразование (алгоритм 1) и переходим к п. 1.

Примечание к пункту 2:

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

4. Схема алгоритмов решения задач ЛП