Симплексный метод решения ЗЛП

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

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

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

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

Реализация симплекс-алгоритма включает восемь шагов. Опишем их, параллельно рассматривая пример выполнения каждого шага в применении к задаче о хоккейных клюках и шахматных наборах.

Шаг 1. Формулировка ЗЛП (формирование целевой функции и системы ограничений).

Для определенности будем считать, что решается задача на отыскание максимума. Ниже приведем общую постановку такой задачи.

,

Еще раз повторим формулировку задачи из нашего примера.

Шаг 2. Приведение задачи к канонической форме (перевод функциональных ограничений в систему уравнений).

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

Обозначим добавочные переменные несколько иначе, а именно: y₁ = x_n+1, y₂ = x_n+2,..., y_m = x_n+m, где n - число переменных в исходной задаче, m - число уравнений.

Все дополнительные переменные также должны быть неотрицательными.

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

Выполним второй шаг для нашего примера.

Шаг 3. Построение исходной симплекс-таблицы (получение первоначального допустимого базисного решения).

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

Таблица 2 - Общий вид исходной симплекс-таблицы

Итак, в левом столбце записываются основные (базисные) переменные, в первой строке таблицы перечисляются все переменные задачи. Крайний правый столбец содержит свободные члены системы ограничений b₁, b₂,..., b_m. В последней строке таблицы (она называется оценочной) записываются коэффициенты целевой функции, а также значение целевой функции (с обратным знаком) при текущем базисном решении (). В рабочую область таблицы (начиная со второго столбца и второй строки) занесены коэффициенты a_ij при переменных системы ограничений.

Таблица 3 - Общий вид исходной симплекс-таблицы для задачи о хоккейных клюшках и шахматных наборах

Таким образом, в данном базисном решении неосновные переменные x₁ и x₂ равны нулю. Базисные переменные отличны от нуля: x₃ = 120, x₄ = 72, x₅ = 10. Данное базисное решение является допустимым. Естественно, что значение целевой функции в этом случае равно нулю, так как в формировании целевой функции участвуют переменные, которые для данного базисного решения являются неосновными.

Шаг 4. Проверка условия: все c_j ≤ 0. Если НЕТ - осуществляется переход к шагу 5, если ДА - задача решена. Таким образом, на данном шаге проверяется наличие положительных элементов в последней строке симплексной таблицы. Если такие элементы имеются, необходимо продолжать решение.

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

Шаг 5. Выбор разрешающего столбца (переменной, вводимой в базис). Разрешающий столбец выбирается в соответствии со следующим условием:

где r - номер разрешающего столбца.

Таким образом, при определении разрешающего столбца просматривается последняя строка симплексной таблицы и в ней отыскивается наибольший положительный элемент.

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

Шаг 6. Проверка условия: все a_ir ≤ 0. Если ДА - целевая функция неограничена и решения нет, если НЕТ - переход к шагу 7.

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

В нашем примере все элементы разрешающего столбца положительны (6, 6 и 1), следовательно, необходимо перейти к шагу 7.

Шаг 7. Выбор разрешающей строки (переменной, выводимой из базиса) по условию:

для a_ir > 0,

где s - номер разрешающей строки.

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

Проиллюстрируем выполнение шага 7, обратившись к нашему примеру.

Для первой строки: D₁ = 120 / 6 = 20.

Для второй строки: D₂ = 72 / 6 = 12.

Для третьей строки: D₃ = 10 / 1 = 10.

Наименьший результат деления - в третьей строке, значит именно эту строку мы выбираем в качестве разрешающей, т.е. исключать из базисного решения будем переменную x₅.

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

Исходная симплекс-таблица нашего примера с выделенными цветом разрешающей строкой и разрешающим столбцом представлена ниже (таблица 4).

Таблица 4 - Исходная симплекс-таблица с выделенными разрешающей строкой и столбцом, а также с иллюстрацией к применению правила прямоугольника

базис	переменные	bi
x1	x2	x3	x4	x5
x3	4
x4
x5
cj

Шаг 8. Пересчет элементов симплекс-таблицы (переход к новому базисному решению). Порядок пересчета различных элементов таблицы несколько отличается.

Для элементов разрешающей строки используются следующие формулы:

где s - номер разрешающей строки,

r - номер разрешающего столбца,

- новые значения пересчитываемых элементов,

a_sj, b_s - старые значения пересчитываемых элементов,

a_sr - старое значение разрешающего элемента.

Таким образом, при пересчете элементов разрешающей строки каждый ее элемент делится на разрешающий элемент.

Еще проще пересчитать элементы разрешающего столбца. Все они (кроме разрешающего элемента) становятся равными нулю:

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

где - новые значения пересчитываемых элементов,

a_ij, b_i, c_j, L - старые значения пересчитываемых элементов.

Применение правила прямоугольника проиллюстрируем, используя таблицу 4. Пересчитаем элемент a₁₁ (в исходной симплекс-таблице его значение равно 4). В таблице 4 можно видеть прямоугольник (прочерчен пунктиром), соединяющий четыре элемента, участвующих в пересчете:

Аналогичным образом пересчитываются остальные элементы.

По окончании пересчета осуществляется возврат к шагу 4.

Полностью результат пересчета для нашего примера можно видеть в таблице 5.

Таким образом, в новом базисном решении базисными переменными являются: x₂ = 10, x₃ = 60, x₅ = 12 (соответствующие значения можно видеть в последнем столбце таблицы). Неосновные переменные x₁ и x₅ равны нулю. Значение целевой функции в этом случае равно 40 (значение можно видеть в правой нижней ячейке таблицы).

Таблица 5 - Симплекс-таблица для задачи о хоккейных клюшках и шахматных наборах (второе базисное решение)

Доведем решение нашего примера до конца.

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

Шаг 5. Выберем разрешающий столбец. Им окажется столбец x₁, поскольку здесь содержится единственный положительный элемент нижней строки. Стало быть, переменную x₁ будем переводить в основные.

Далее. Шаг 6. Проверка показывает, что в разрешающем столбце есть положительные элементы, следовательно, можно продолжать решение.

Шаг 7. Определим разрешающую строку. При этом будем рассматривать лишь первую и вторую строки, поскольку для третьей строки в разрешающем столбце находится нуль. Найдем частное от деления элемента b_i на элемент, находящийся в разрешающем столбце:

Для первой строки: D₁ = 60 / 4 = 15.

Для второй строки: D₂ = 12 / 2 = 6.

Наименьший результат деления - во второй строке, значит именно эту строку мы выбираем в качестве разрешающей, т.е. переводить в неосновные (исключать из базиса) будем переменную x₄.

Ниже приведена симплекс-таблица с выделенными разрешающей строкой и столбцом (таблица 6).

Таблица 6 - Симплекс-таблица (второе базисное решение) с выделенными разрешающей строкой и столбцом

Далее перейдем к шагу 8 и осуществим пересчет элементов симплексной таблицы в соответствии с правилами, приводимыми выше. Результат пересчета представлен в таблице 7.

Таблица 7 - Симплекс-таблица для задачи о хоккейных клюшках и шахматных наборах (третье базисное решение)

Таким образом, в очередном (третьем) базисном решении основными переменными являются: x₁ = 6, x₂ = 10, x₃ = 36. Неосновные переменные x₄ и x₅ равны нулю. Значение целевой функции для этого решения равно 52.

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

Шаг 5. Выберем разрешающий столбец. Им окажется столбец x₅, поскольку здесь содержится единственный положительный элемент нижней строки. Переменную x₅ будем переводить в основные.

Шаг 6. Проверка показывает, что в разрешающем столбце есть положительные элементы, следовательно, можно продолжать решение.

Шаг 7. Определим разрешающую строку. При этом будем рассматривать лишь первую и третью строки, поскольку для второй строки в разрешающем столбце находится отрицательное число. Найдем частное от деления элемента b_i на элемент, находящийся в разрешающем столбце:

Для первой строки: D₁ = 36 / 6 = 6.

Для третьей строки: D₂ = 10 / 1 = 10.

Наименьший результат деления - в первой строке, значит именно эту строку мы выбираем в качестве разрешающей, т.е. переводить в неосновные (исключать из базиса) будем переменную x₃.

Ниже приведена симплекс-таблица с выделенными разрешающей строкой и столбцом (таблица 8).

Таблица 8 - Симплекс-таблица (третье базисное решение) с выделенными разрешающей строкой и столбцом

Далее перейдем к шагу 8 и осуществим пересчет элементов симплексной таблицы в соответствии с правилами, приводимыми выше. Результат пересчета представлен в таблице 9.

Таким образом, в очередном (четвертом) базисном решении основными переменными являются: x₁ = 24, x₂ = 4, x₅ = 6. Неосновные переменные x₃ и x₄ равны нулю. Значение целевой функции для этого решения равно 64.

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

Таблица 9 - Симплекс-таблица для задачи о хоккейных клюшках и шахматных наборах (четвертое базисное решение)

На рисунке 5 приведена общая схема симплексного алгоритма, наглядно показывающая порядок его реализации.

Поиск по сайту: