8.5. Симплекс – метод. Общая идея симплекс – метода

Для начала работы требуется, чтобы заданная система ограничений выражалась равенствами, причем в этом системе ограничений должны быть выделены базисные неизвестные. Решение задачи при помощи симплекс – метода распадается на ряд шагов. На каждом шаге от данного базиса Б переходят к другому, новому базису Б¹ с таким расчетом, чтобы значение функции Z уменьшалось, т.е. . Для перехода к новому базису из старого базиса удаляется одна из переменных и вместо нее вводится другая из числа свободных. После конечного числа шагов находится некоторый базис Б^(к), для которого есть искомый минимум для линейной функции Z, а соответствующее базисное решение является оптимальным либо выясняется, что задача не имеет решения.

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

Рассмотрим систему ограничений и линейную форму вида:

(8.37)

(8.38)

(8.39)

Используя метод Жордана – Гаусса, приведем записанную систему к виду, где выделены базисные переменные.

Введем условные обозначения:

x₁, x₂,… x_r – базисные переменные;

x_r+1, x_r+2,… x_n – свободные переменные.

(8.40)

(8.41)

По последней системе ограничений и целевой функции Z построим табл. 8.3.

Таблица 8.3

Симплекс – таблица

Данная таблица называется симплекс – таблицей. Все дальнейшие преобразования связаны с изменением содержания этой таблицы.

Алгоритм симплекс-метода сводится к следующему.

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

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

3. На пересечении разрешающей строки и разрешающего столб­ца находится разрешающий элемент.

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

2. После нахождения разрешающего элемента переходят к сле­дующей таблице. Неизвестные переменные, соответствующие раз­решающей строке и столбцу, меняют местами. При этом базисная переменная становится свободной переменной и наоборот. Симп­лекс - таблица преобразована следующим образом (табл. 7.4):

Таблица 8.4

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

Элемент табл. 8.4, соответствующий разрешающему элемен­ту табл. 8.3, равен обратной величине разрешающего элемента.

Элементы строки табл. 8.4, соответствующие элементам раз­решающей строки табл. 8.3, получаются путем деления соответст­вующих элементов табл. 8.3 на разрешающий элемент.

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

Остальные элементы вычисляются по правилу прямоугольни­ка: мысленно вычерчиваем прямоугольник в табл. 8.3, одна верши­на которого совпадает с разрешающим элементом, а другая — с элементом, образ которого мы ищем; остальные две вершины оп­ределяются однозначно. Тогда искомый элемент из табл. 8.4 будет равен соответствующему элементу табл. 8.3 минус дробь, в знаме­нателе которой стоит разрешающий элемент, а в числителе - про­изведение элементов из двух неиспользованных вершин прямо­угольника.

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

2. Если в разрешающем столбце все элементы отрицательны, то задача не имеет решений (минимум не достигается).

Пример 8.12. Решение задачи симплекс-методом:

Приведем задачу к виду, допускающему применение симплекс - алгоритма:

Подставим в выражение Z_max величины x₃, x₄, x₅:

По алгоритму целевая функция должна стремиться к минимуму:

Составим симплекс-таблицу:

Разыскиваем в последней строке наименьший положительный элемент, в нашем примере он равен + 6, первый столбец коэффи­циентов будет разрешающим. Определим отношение свободных членов к положительным элементам разрешающего столбца. Ми­нимальное симплекс-отношение равно I. Разрешающий элемент находится на пересечении строки переменной х₄ и столбца - x₁.

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

В последней строке нет положительных элементов, следовательно, оптимальное решение найдено:

Z_min=-9; X = (0;0;2;1;1); Z_max = - Z_min = 9.