Симплекс метод является наиболее распространенным вычислительным методом, который может быть применен для решения любых задач ЛП как вручную, так и с помощью ЭВМ.
Этот метод позволяет переходить от одного допустимого решения к другому, причем так, что значения целевой функции непрерывно возрастают. Этот переход возможен, если известен какой-либо опорный план. В этом случае каноническая задача линейного программирования должна содержать единичную подматрицу порядка M. Тогда очевиден первоначальный опорный план( неотрицательное базисное решение системы ограничений ЗЛП).
В результате оптимальное решение находят за конечное число шагов. Алгоритм симплекс-метода позволяет также установить является ли задача ЛП разрешимой.
Любая задача линейного программирования с помощью элементарных преобразований может быть приведена к каноническому виду. 
где F(x) - целевая функция;  - базисные переменные; остальные переменные называются свободными.
Задача имеет m+n ограничений, среди них m ограничений типа равенства и n ограничений неотрицательности. По определению крайняя точка удовлетворяет n линейно-независимым ограничениям задачи как точным равенствам.
Алгоритм симплекс метода в случае неотрицательности свободных членов
Переходим от системы неравенств к равенствам с помощью ослабляющих переменных.
Находим единичные вектора условий, которые войдут в базис. Их должно быть столько, сколько уравнений в системе.
Составляем симплекс таблицу.
Таблица 1 Общий вид симплекс таблицы
Сб
|
Б
|
В
|
|
|
…
|
|
|
|
…
|
|
Q
|
|
|
…
|
|
|
|
…
|
|
|
|
|
|
|
…
|
|
1
|
0
|
…
|
0
|
|
|
|
|
|
|
…
|
|
0
|
1
|
…
|
0
|
|
…
|
…
|
…
|
…
|
…
|
…
|
…
|
…
|
…
|
…
|
…
|
|
|
|
|
|
|
…
|
|
0
|
0
|
…
|
1
|
|
∆
|
Z
|
|
|
|
|
|
|
|
|
|
L
|
|
|
|
|
|
|
|
|
|
В первой строке записываем коэффициенты целевой функции.
Коэффициенты ограничений переносятся в среднюю часть таблицы.
Вносим свободные члены в третий столбец «В».
Во второй столбец записываем базис (единичные вектора).
Находим «Z» как сумму попарных произведений 1-го и 3-го столбцов.
Предпоследнюю строку таблицы L находим как Сумму попарных произведений элементов первого столбца и соответствующего столбца средней части таблицы.
Последнюю строку ∆ определяем как разность элементов предпоследней строки и 1-й строки (коэффициентов целевой функции).
Величина «∆» - критерий оптимальности. Для задачи минимилизации оптимальным будет план, для которого все значения строки меньше или равны 0 ( ), а для задачи максимилизации план в котором все значения больше или равны 0 ( ).
Если план не оптимален, то переходим к заполнению новой симплексной таблице.
Находим разрешающий элемент.
Для задачи максимализации выбираем столбец с максимальным по модулю ∆ среди отрицательных. А для задачи минимализации столбец с максимальным по модулю среди положительных. Такой столбец называется «Разрешающим»
Для нахождения «Разрешающей» строки, значения элементов 3-го столбца («В») делим на значения соответствующих элементов Разрешающего столбца. Полученный результат записываем в последний столбец (Q).
Среди полученных значений выбираем наименьшее. Строка, содержащая это число, и будет «Разрешающей».
На пересечение Разрешающего столбца и разрешающей строки получаем «Разрешающий» элемент.
В новой таблице меняем базисную переменную и соответственно поправляем 1-й столбец.
Разрешающую строку делим на Разрешающий элемент и записываем на свои места.
Обнуляем остальные элементы Разрешающего столбца.
Остальные элементы таблицы находим по правилу прямоугольника.
Заполняем последние 2 строки.
В случае оптимальности плана Записываем полученные значения в ответ, а в случае неоптимальности составляем новую симплекс таблицу согласно предыдущим пунктам.
Через конечное число итераций либо будет получено решение задачи линейного программирования, либо будет установлено, что решение неограниченно.
Рисунок 2 7 Блок-схема алгоритма симплекс-метода
|
Скачать 5.67 Mb.