Автор: Пользователь скрыл имя, 25 Октября 2014 в 09:27, курсовая работа
В практике экономико-математического моделирования часто встречаются задачи линейного программирования (ЛП) большой размерности (десятки тысяч переменных), обладающие такими "нерегулярными" свойствами как неполнота, противоречивость и изменчивость входных данных. Программные комплексы, базирующиеся на симплекс-методе и его модификациях, плохо приспособлены для решения такого рода задач. Кроме того, симплекс-метод обладает плохой масштабируемостью применительно к многопроцессорным вычислительным системам с массовым параллелизмом. В соответствии с этим необходимы иные алгоритмы и методы решения больших задач ЛП в условиях неполных, противоречивых и эволюционирующих исходных данных.
Введение 2
1. Параметрические методы решения задач линейного программирования 4
2. Метод барьерных поверхностей 4
3. Алгоритм метода барьерных поверхностей 5
4. Метод штрафных функций 6
5. Алгоритм метода штрафных функций 8
Заключение 9
Литература 10
Содержание
В практике экономико-математического моделирования часто встречаются задачи линейного программирования (ЛП) большой размерности (десятки тысяч переменных), обладающие такими "нерегулярными" свойствами как неполнота, противоречивость и изменчивость входных данных. Программные комплексы, базирующиеся на симплекс-методе и его модификациях, плохо приспособлены для решения такого рода задач. Кроме того, симплекс-метод обладает плохой масштабируемостью применительно к многопроцессорным вычислительным системам с массовым параллелизмом. В соответствии с этим необходимы иные алгоритмы и методы решения больших задач ЛП в условиях неполных, противоречивых и эволюционирующих исходных данных.
Наиболее известным и широко применяемым на практике для решения общей задачи линейного программирования (ЛП) является симплекс-метод. Несмотря на то, что симплекс-метод является достаточно эффективным алгоритмом, показавшим хорошие результаты при решении прикладных задач ЛП, он является алгоритмом с экспоненциальной сложностью. Причина этого состоит в комбинаторном характере симплекс-метода, последовательно перебирающего вершины многогранника допустимых решений при поиске оптимального решения.[6]
Первый полиномиальный алгоритм, метод эллипсоидов, был предложен в 1979 году советским математиком Л. Хачияном, разрешив таким образом проблему, долгое время остававшуюся нерешённой. Метод эллипсоидов имеет совершенно другую, некомбинаторную, природу, нежели симплекс-метод. Однако в вычислительном плане этот метод оказался неперспективным. Тем не менее, сам факт полиномиальной сложности задач привёл к созданию целого класса эффективных алгоритмов ЛП — методов внутренней точки, первым из которых был алгоритм Н. Кармаркара, предложенный в 1984 году. Алгоритмы этого типа используют непрерывную трактовку задачи ЛП, когда вместо перебора вершин многогранника решений задачи ЛП осуществляется поиск вдоль траекторий в пространстве переменных задачи, не проходящих через вершины многогранника. Метод внутренних точек, который, в отличие от симплекс-метода, обходит точки из внутренней части области допустимых значений, использует методы логарифмических барьерных функций нелинейного программирования, разработанные в 1960-х годах Фиако (Fiacco) и МакКормиком (McCormick).[7]
Параметрические методы подразделяются на: 1) методы внутренней точки; 2) методы внешней точки; 3) комбинированные методы.
При использовании методов внутренней точки текущая точка постоянно находится внутри допустимой области с помощью штрафной функции, которая в этом случае называется барьерной. Методы внешней точки, наоборот, генерируют последовательность точек, которые выходят за пределы допустимой области, но в пределе дают допустимое решение. Наконец, в комбинированных методах, которые необходимо использовать при ограничениях-равенствах, в процессе оптимизации одни из ограничений удовлетворяются, а другие – нет. Однако при достижении искомого решения все условия в пределах заданного допуска выполняются.[1]
Рассмотрим некоторые методы из групп методов внутренней точки и внешней точки.
Метод барьерных поверхностей (МБП) относится к группе методов внутренней точки и основан на использовании барьерной поверхности вида
,
где – параметр, значения которого убывают с каждой итерацией при ; – положительные весовые коэффициенты.
При этом барьерная функция (поверхность) неограниченно возрастает при .
Примерами барьерных функций являются:
а) обратная функция ,
б) логарифмическая функция .
При приближении к границе изнутри области, как только , штраф становится очень большим. Таким образом, вдоль всех границ допустимой области образуются сильные барьеры.
Построив барьерную функцию и определив начальную внутреннюю точку, приступаем к процедуре минимизации при заданном начальном значении . Тогда конечная точка первой итерации процедуры становится исходной для минимизации при уменьшенном значении и т.д. Завершающий этап (итерация) минимизации реализуется при очень малом значении , так что результирующая точка с точностью до установленного допуска может сказаться либо на одной, либо сразу на нескольких поверхностях, заданных ограничениями задачи.
Если через обозначить точку минимума вспомогательной функции , то при весьма слабых предположениях относительно исходной задачи последовательность сходится к решению исходной задачи при .
Минимизация барьерной функции может быть выполнена любым методом безусловной оптимизации, например градиентным, или методами переменной метрики, или одним из прямых методов.
Один из существенных недостатков метода барьерных функций связан с тем, что эти функции определены в допустимой области, которая должна иметь непустую внутреннюю область, т.е. множество должно быть непустым.
Пусть задача НП имеет следующий вид:
минимизировать
при ограничениях , .
Начальный этап. Выбрать в качестве константы остановки, начальную допустимую точку , для которой , , скаляр и 0 < <1. Положить и перейти к основному этапу.
Основной этап. -я итерация. Первый шаг. При исходной точке решить следующую задачу безусловной оптимизации:
минимизировать ,
где - барьерная функция.
Положить равным оптимальному решению задачи и перейти ко второму шагу.
Второй шаг. Если , то остановиться. Решение является искомым. В противном случае положить . Изменить и перейти к первому шагу -й итерации.
Метод барьерных поверхностей относится к группе методов внутренней точки, т.е. он начинает работать с допустимой точки и генерирует последовательность допустимых точек . Метод штрафных функций, наоборот, относится к группе методов внешней точки, он начинает поиск с недопустимой точки и генерирует последовательность недопустимых решений, которая приближается к оптимальному решению извне допустимой области.
Пусть, как и выше, имеется задача:
минимизировать , (1)
при ограничениях
(2)
Метод штрафных функций основан на преобразовании исходной задачи с ограничениями в одну задачу безусловной оптимизации или в их последовательность. С помощью функций-ограничений строят штрафную функцию, которая прибавляется к целевой функции исходной задачи, так, чтобы нарушение какого-либо из ограничений исходной задачи было невыгодным с точки зрения полученной задачи безусловной оптимизации.
В частности, для ограничений типа (2) целесообразно использовать штрафную функцию следующего вида:
где – непрерывные функции, которые удовлетворяют условиям:
, если и , , если ,
, если и , , если .
Типичными являются следующие выражения для функций :
; , где – целое положительное число.
Таким образом, штрафная функция обычно имеет вид
(3)
Далее от задачи (1) переходим к задаче безусловной оптимизации вспомогательной функции:
минимизировать ,
где – штрафной коэффициент.
Пусть – непрерывная функция вида (3). Обозначим
Подход, связанный со штрафной функцией, состоит в решении задачи вида:
максимизировать
при ограничении
В связи с трудностями, связанными с использованием большого параметра штрафа , в большинстве алгоритмов метода штрафных функций применяют последовательность возрастающих параметров штрафа .
Итак, пусть имеем задачу ЛП:
минимизировать
при ограничениях ,
где функции непрерывны.
Начальный этап. Выбрать . Выбрать начальную точку , параметр штрафа и число . Положить и перейти к основному этапу.
Основной этап. Первый шаг. При начальной точке и параметре штрафа решить следующую задачу:
минимизировать
где – целое.
Положить равным оптимальному решению этой задачи и перейти ко второму шагу.
Второй шаг. Если , то остановиться. В противном случае положить . Заменить на и перейти к первому шагу.
Полиноминальные методы решения линейного программирования, к которым относятся рассмотренные в данной работе метод барьерных поверхностей и метод штрафных функций, несомненно более перспективные и лучше подходят для решения задач большой размерности (а часто и безальтернативно) чем экспоненциальные методы к которым относится, например симплекс-метод. Этот факт подтверждается огромным объемом литературы и исследований на эту тему.
1. Банди Б. Методы Оптимизации. Вводный курс. М.: Радио и связь, 1988.
2. Васильев Ф.П., Иваницкий А.Ю. Линейное программирование. М.: Факториал, 2003.
3. Голиков А.И., Евтушенко Ю.Г, Моллаверди Н. Применение метода Ньютона к решению задач линейного программирования большой размерности // Ж. вычисл. матем. и матем. физ. 2004. Т. 44. №
4. Голынтейн Е.Г., Юдин Д.Б. Новые направления в линейном программировании. М.: Сов.радио, 1966.
5. Поляк Б.Т., Третьяков Н.В. Об одном итерационном методе линейного программирования и его экономической интерпретации // Эконом, и матем. методы. 1972. Т. VIII. Вып. 5.
6. http://life.susu.ru/#Web-
7. http://ru.wikipedia.org Википедия. Свободная энциклопедия
8. Булавский В.А., Звягина Р.А., Яковлева М.А. Численные методы линейного программирования. М.: Наука, 1977.
Информация о работе Оптимизация и математические методы принятия решений