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

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

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

Основные этапы алгоритма симплексного метода:

1. Приведение системы ограничений к каноническому виду;

2. Поиск опорного решения задачи;

3. Нахождение базиса задачи;

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

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

6. Последовательное улучшение плана до получения оптимального.

С=2* х₁+3* х₂ à max

1. Приведение системы ограничений к каноническому виду

В этих целях в каждое ограничение задачи вводят по одной дополнительной переменной:

Дополнительные переменные в ограничениях типа £ обозначают недоиспользованные ресурсы.

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

С=2х₁ + 3х₂ + 0x₃ + 0x₄ +0x₅ +0x₆ à max

2. Поиск опорного решения задачи;

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

Переменные, которые были в системе ограничений до приведения ее к каноническому виду, называются основными переменными задачи.

Хопор={х₁=0, х₂=0, х₃=18, х₄=16, х₅=5, х₆=21}

3. Нахождение базиса задачи

Переменные, отличные от нуля в опорном решении называются базисными переменными.

В нашем примере базисными переменными будут

Бх={х₃, х₄, х₅, х₆}

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

Построим исходную симплексную таблицу. В литературе существует много способов построения симплексных таблиц (полные и сокращенные). Мы разберем один из них, способ построения полной симплексной таблицы: i – обозначим номер ограничения. Бх - базис задачи; bi - свободные члены; Q - симплексное отношение (тета)

На любом этапе задачи базисные переменные всегда равны соответствующим свободным членам.

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

В первой симплексной таблице значение целевой функции равно 0, т.к. значение основных переменных равно 0.

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

План считается оптимальным при решении задачи на максимум в том случае, если в индексной строке отсутствуют отрицательные коэффициенты.

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

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

6. Последовательное улучшение плана

Последовательное улучшение плана сводится к отысканию нового базиса задачи. Для перехода к новому базису из старого удаляется одна из переменных и вместо нее вводится другая из числа свободных.

Чтобы определить какую из переменных надо ввести в базис необходимо найти разрешающий столбец. Для этого просматриваем индексную строку симплексной таблицы:

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

ü если решаем задачу на минимум – то наибольший положительный:

В нашем случае разрешающим столбцом, будет столбец содержащий переменную х2.

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

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

Нулевое симплексное отношение определяет разрешающую строку в том случае, если в знаменателе этого отношения находится положительное число.

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

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

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

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

ü На месте разрешающего элемента в новой таблице ставят 1;

ü Элементы новой таблицы, соответствующие разрешающему столбцу равны 0;

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

ü Обыкновенные элементы (т.е. все остальные) рассчитываются по правилу прямоугольника, выраженному формулой:

b_ij – обыкновенный элемент новой симплексной таблицы;

a_rs – разрешающий элемент (в старой симплексной таблице);

a_ij – элемент главной диагонали прямоугольника старой симплексной таблицы;

a_is, a_rj – элементы побочной диагонали прямоугольника старой симплексной таблицы.

ВСЕ РАСЧЕТЫ ПРОИЗВОДЯТСЯ В СТАРОЙ СИМПЛЕКСНОЙ ТАБЛИЦЕ, В НОВУЮ ЗАНОСЯТСЯ ТОЛЬКО РЕЗУЛЬТАТЫ ЭТИХ РАСЧЕТОВ.

Смотрим новую симплексную таблицу и проверяем ее на условие оптимальности.

И так повторяем до тех пор, пока не выполнится условие оптимальности (не будет отрицательных элементов в индексной строке.

Для наглядности первую таблицу приведем еще раз.

Ответ выделен цветом