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

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

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

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

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 - симплексное отношение (тета)

i	Бх	bi	Осн. пер.	Доп. пер.	Q
х1	х2	х3	х4	х5	х6
	х3
	х4
	х5
	х6								-
С		-2	-3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Симплексное отношение (Q)	=	элементы столбца свободных членов
соответствующие элементы разрешающего столбца

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

i	Бх	bi	Осн. пер.	Доп. пер.	Q
х1	х2	х3	х4	х5	х6
	х3
	х4
	х5
	х6								-
С		-2	-3

i	Бх	bi	Осн. пер.	Доп. пер.	Q
х1	х2	х3	х4	х5	х6
	х3						-3
	х4						-1		5,5
	х2								-
	х6
С		-2
i	Бх	bi	Осн. пер.	Доп. пер.	Q
х1	х2	х3	х4	х5	х6
	х1						-3		-
	х4				-2
	х2
	х6				-3				4/3
С						-3
i	Бх	bi	Осн. пер.	Доп. пер.	Q
х1	х2	х3	х4	х5	х6
	х1
	х5				-2/5	1/5
	х2
	х6
С				4/5	3/5

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