Решение задачи линейного программирования симплекс-методом
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
ия.
Симплекс-метод был разработан и впервые применен для решения задач в 1947 г. американским математиком Дж. Данцигом.
Симплексный метод в отличие от геометрического универсален. С его помощью можно решить любую задачу линейного программирования.
В основу симплексного метода положена идея последовательного улучшения получаемого решения.
Геометрический смысл симплексного метода состоит в последовательном переходе от одной вершины многогранника ограничений к соседней, в которой целевая функция принимает лучшее (или, по крайней мере, не худшее) значение до тех пор, пока не будет найдено оптимальное решение - вершина, где достигается оптимальное значение функции цели (если задача имеет конечный оптимум).
Таким образом, имея систему ограничений, приведенную к канонической форме (все функциональные ограничения имеют вид равенств), находят любое базисное решение этой системы, заботясь только о том, чтобы найти его как можно проще. Если первое же найденное базисное решение оказалось допустимым, то проверяют его на оптимальность. Если оно не оптимально, то осуществляется переход к другому, обязательно допустимому базисному решению. Симплексный метод гарантирует, что при этом новом решении целевая функция, если и не достигнет оптимума, то приблизится к нему (или, по крайней мере, не удалится от него). С новым допустимым базисным решением поступают так же, пока не отыщется решение, которое является оптимальным.
Процесс применения симплексного метода предполагает реализацию трех его основных элементов:
) способ определения какого-либо первоначального допустимого базисного решения задачи;
) правило перехода к лучшему (точнее, не худшему) решению;
) критерий проверки оптимальности найденного решения.
Симплексный метод включает в себя ряд этапов и может быть сформулирован в виде четкого алгоритма (четкого предписания о выполнении последовательных операций). Это позволяет успешно программировать и реализовывать его на ЭВМ. Задачи с небольшим числом переменных и ограничений могут быть решены симплексным методом вручную.
1 Теоретическая часть
.1 Алгоритм решения задач линейного программирования симплекс-методом
Симплекс метод - метод линейного программирования , который реализует рациональный перебор базисных допустимых решений, в виде конечного итеративного процесса, необходимо улучшающего значение целевой функции на каждом шаге.
Для того чтобы задача имела оптимальное решение необходимо:
-чтобы ограничения задачи были совместимы;
-целевая функция была ограничена сверху при поиске максимального значения и снизу при поиске минимального значения.
Для решения задачи линейного программирования симплекс-методом необходимо привести задачу к канонической форме, для этого все ограничения должны иметь вид строгого равенства:
-ограничения вида меньше или равно приводятся к строгому равенству путём добавления к левой части каждого ограничения неотрицательной целой переменной, которая записывается в целевую функцию с коэффициентом равным нулю;
-чтобы привести ограничения вида больше или равно к строгому равенству надо из левой части каждого ограничения вычесть неотрицательную целую переменную и добавить искусственную неотрицательную переменную (y1,y2тАжyn), которая войдёт в целевую функцию с коэффициентом (-M).
Алгоритм:
)Привести математическую модель к канонической форме, заполнить симплекс таблицу и вычислить значение целевой функции и относительных оценок ?i.
)Если все относительные оценки не отрицательны и среди базисных переменных нет искусственных, то план оптимален и задача решена. Решение находится в столбце B:
;
;
.
Если искомая переменная не вышла в базис, значит, она равна нулю.
Если все относительные оценки не отрицательны и среди них есть хотя бы одна равная нулю, а в базисе нет искусственных переменных, то задача решена и имеет бесконечное множество решений, одно из которых вышло в базис и находится в столбце B;
Если все ?i ? 0, а в базисе остались искусственные переменные, то задача решений не имеет;
Если среди относительных оценок есть отрицательные, то данный план не оптимален и необходим переход к следующему базисному плану.
3)Из всех относительных оценок выбирается наибольшая по модулю, столбец соответствующий ей называется главным. Для определения главной строки надо поэлементно разделить столбец B на главный столбец, наименьшее из получившихся частных соответствует главной строке. Главный элемент симплекс-таблицы находится на пересечении главной строки и главного столбца. Далее необходимо произвести пересчёт симплекс-таблицы.
)В новой итерации элементы главной строки делятся на главный элемент, а элементы главного столбца делят на минус главный элемент. Если в главной строке или в главном столбце есть ноль, то элементы, соответствующие этим нулям столбца и строки переписываются в новую таблицу без изменений. Остальные клетки симплекс-таблицы пересчитываются по правилу прямоугольника - из произведения элементов главной диагонали, проходящей через главный элемент, вычитают произведение элементов побочной диагонали и результат делят на главный элемент.
)Вычисляется значение целевой функции, оно определяется путём вычисления суммы парных произведений столбца C и столбца B. Значение относительных оценок так же вычисляются к