В. 7 Алгоритм прямого симплексного метода

Прямой симп. метод предназначен для решения задачи ЛП вида .

Симплексный метод можно применять, только если выполняются 3 условия:

1) задача ЛП имеет канонический вид;

2) правая часть ограничений (вектор свободных членов) неотрицателен (b≥0)

3) матрица А содержит единичную подматрицу (имеется начальное допустимое базисное решение).

Тогда можно построить начальную симплексную таблицу:

Элементы , называемые оценками, вычисляются по формуле . Оценка равна текущему значению целевой функции.

Элементы вектора c_B содержат коэффициенты целевой функции, соответствующие базисным переменным. Столбец «Базис» содержит названия текущих базисных переменных (в правильном порядке). Столбец «БДР» показывает текущее значение базисных переменных, при которых достигается текущее значение целевой функции. В конце работы алгоритма в этом столбце будет содержаться ответ.

Алгоритм прямого симплексного метода.

Шаг 0. Построить начальную симп.таблицу. В столбце «Базис» записать базисные переменные в правильном порядке. Вычислить оценки. Перейти на шаг 1.

Шаг 1. Проверить оценки . Если все оценки , то найдено оптимальное решение. Перейти на шаг 5.

Среди положительных оценок найти максимальную и столбец, соответствующий выбранной оценке, объявить ведущим (s). Перейти на шаг 2.

Шаг 2. Просмотреть элементы s-го столбца, если все они , то целевая функция неограниченна (нет оптимального решения), перейти на шаг 5. Иначе перейти на шаг 3.

Шаг 3. Для положительных элементов s-го столбца найти строчку r, в которой симп. отношение b_r/a_rs принимает минимальное значение. Объявить строку r ведущей. Перейти на шаг 4.

Шаг 4. На пересечении ведущего столбца и ведущей строки обозначить ведущий элемент. Нарисовать новую симплексную таблицу. На месте элемента x_r в столбце «базис» поставить элемент x_s и с помощью преобразования Жордана-Гаусса пересчитать всю таблицу (в том числе оценки и столбец БДР). Перейти на шаг 1.

Шаг 5. Конец алгоритма.

Пример в распечатке!