Основная особенность рассматриваемого нами симплексного метода заключается в том, что им можно решать только задачи, с ограничениями типа £ (не считая ограничения по неотрицательности переменных).
Алгоритм симплексного метода рассмотрим на знакомом уже нам примере решения задачи планирования производства.
Основные этапы алгоритма симплексного метода:
1. Приведение системы ограничений к каноническому виду;
2. Поиск опорного решения задачи;
3. Нахождение базиса задачи;
4. Построение первой симплексной таблицы
5. Проверка плана на оптимальность
6. Последовательное улучшение плана до получения оптимального.
С=2* х1+3* х2 à max
1. Приведение системы ограничений к каноническому виду
В этих целях в каждое ограничение задачи вводят по одной дополнительной переменной:
Дополнительные переменные в ограничениях типа £ обозначают недоиспользованные ресурсы.
Дополнительные переменные вводятся в целевую функцию задачи с нулевыми коэффициентами:
С=2х1 + 3х2 + 0x3 + 0x4 +0x5 +0x6 à max
2. Поиск опорного решения задачи;
Для нахождения опорного решения необходимо основные переменные приравнять к нулю, тогда дополнительные переменные будут равны соответствующим свободным членам:
Переменные, которые были в системе ограничений до приведения ее к каноническому виду, называются основными переменными задачи.
Хопор={х1=0, х2=0, х3=18, х4=16, х5=5, х6=21}
3. Нахождение базиса задачи
Переменные, отличные от нуля в опорном решении называются базисными переменными.
В нашем примере базисными переменными будут
Бх={х3, х4, х5, х6}
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;
ü Элементы, соответствующие разрешающей строке в новой таблице рассчитываются путем деления каждого на разрешающий элемент;
ü Обыкновенные элементы (т.е. все остальные) рассчитываются по правилу прямоугольника, выраженному формулой:
bij – обыкновенный элемент новой симплексной таблицы;
ars – разрешающий элемент (в старой симплексной таблице);
aij – элемент главной диагонали прямоугольника старой симплексной таблицы;
ais, arj – элементы побочной диагонали прямоугольника старой симплексной таблицы.
ВСЕ РАСЧЕТЫ ПРОИЗВОДЯТСЯ В СТАРОЙ СИМПЛЕКСНОЙ ТАБЛИЦЕ, В НОВУЮ ЗАНОСЯТСЯ ТОЛЬКО РЕЗУЛЬТАТЫ ЭТИХ РАСЧЕТОВ.
Смотрим новую симплексную таблицу и проверяем ее на условие оптимальности.
И так повторяем до тех пор, пока не выполнится условие оптимальности (не будет отрицательных элементов в индексной строке.
Для наглядности первую таблицу приведем еще раз.
| 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 |
Ответ выделен цветом
