Размещено на http://www.allbest.ru/

Содержание

• Введение
• 1. Параметрические методы решения задач линейного программирования
• 2. Метод барьерных поверхностей
• 3. Алгоритм метода барьерных поверхностей
• 4. Метод штрафных функций
• 5. Алгоритм метода штрафных функций
• Заключение
• Литература
• Введение
• В практике экономико-математического моделирования часто встречаются задачи линейного программирования (ЛП) большой размерности (десятки тысяч переменных), обладающие такими "нерегулярными" свойствами как неполнота, противоречивость и изменчивость входных данных. Программные комплексы, базирующиеся на симплекс-методе и его модификациях, плохо приспособлены для решения такого рода задач. Кроме того, симплекс-метод обладает плохой масштабируемостью применительно к многопроцессорным вычислительным системам с массовым параллелизмом. В соответствии с этим необходимы иные алгоритмы и методы решения больших задач ЛП в условиях неполных, противоречивых и эволюционирующих исходных данных.
• Наиболее известным и широко применяемым на практике для решения общей задачи линейного программирования (ЛП) является симплекс-метод. Несмотря на то, что симплекс-метод является достаточно эффективным алгоритмом, показавшим хорошие результаты при решении прикладных задач ЛП, он является алгоритмом с экспоненциальной сложностью. Причина этого состоит в комбинаторном характере симплекс-метода, последовательно перебирающего вершины многогранника допустимых решений при поиске оптимального решения.[6]
• Первый полиномиальный алгоритм, метод эллипсоидов, был предложен в 1979 году советским математиком Л. Хачияном, разрешив таким образом проблему, долгое время остававшуюся нерешённой. Метод эллипсоидов имеет совершенно другую, некомбинаторную, природу, нежели симплекс-метод. Однако в вычислительном плане этот метод оказался неперспективным. Тем не менее, сам факт полиномиальной сложности задач привёл к созданию целого класса эффективных алгоритмов ЛП -- методов внутренней точки, первым из которых был алгоритм Н. Кармаркара, предложенный в 1984 году. Алгоритмы этого типа используют непрерывную трактовку задачи ЛП, когда вместо перебора вершин многогранника решений задачи ЛП осуществляется поиск вдоль траекторий в пространстве переменных задачи, не проходящих через вершины многогранника. Метод внутренних точек, который, в отличие от симплекс-метода, обходит точки из внутренней части области допустимых значений, использует методы логарифмических барьерных функций нелинейного программирования, разработанные в 1960-х годах Фиако (Fiacco) и МакКормиком (McCormick).[7]

1. Параметрические методы решения задач линейного программирования

Параметрические методы подразделяются на: 1) методы внутренней точки; 2) методы внешней точки; 3) комбинированные методы.

При использовании методов внутренней точки текущая точка постоянно находится внутри допустимой области с помощью штрафной функции, которая в этом случае называется барьерной. Методы внешней точки, наоборот, генерируют последовательность точек, которые выходят за пределы допустимой области, но в пределе дают допустимое решение. Наконец, в комбинированных методах, которые необходимо использовать при ограничениях-равенствах, в процессе оптимизации одни из ограничений удовлетворяются, а другие - нет. Однако при достижении искомого решения все условия в пределах заданного допуска выполняются.[1]

Рассмотрим некоторые методы из групп методов внутренней точки и внешней точки.

2. Метод барьерных поверхностей

Метод барьерных поверхностей (МБП) относится к группе методов внутренней точки и основан на использовании барьерной поверхности вида

где - параметр, значения которого убывают с каждой итерацией при ; - положительные весовые коэффициенты.

При этом барьерная функция (поверхность) неограниченно возрастает при .

Примерами барьерных функций являются:

а) обратная функция ,

б) логарифмическая функция .

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

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

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

Минимизация барьерной функции может быть выполнена любым методом безусловной оптимизации, например градиентным, или методами переменной метрики, или одним из прямых методов.

Один из существенных недостатков метода барьерных функций связан с тем, что эти функции определены в допустимой области, которая должна иметь непустую внутреннюю область, т.е. множество должно быть непустым.

3. Алгоритм метода барьерных поверхностей

Пусть задача НП имеет следующий вид:

минимизировать

при ограничениях , .

Начальный этап. Выбрать в качестве константы остановки, начальную допустимую точку , для которой , , скаляр и 0 < <1. Положить и перейти к основному этапу.

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

Минимизировать

,

где - барьерная функция.

Положить равным оптимальному решению задачи и перейти ко второму шагу.

Второй шаг. Если

то остановиться. Решение является искомым. В противном случае положить . Изменить и перейти к первому шагу -й итерации.

4. Метод штрафных функций

Метод барьерных поверхностей относится к группе методов внутренней точки, т.е. он начинает работать с допустимой точки и генерирует последовательность допустимых точек . Метод штрафных функций, наоборот, относится к группе методов внешней точки, он начинает поиск с недопустимой точки и генерирует последовательность недопустимых решений, которая приближается к оптимальному решению извне допустимой области.

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

В частности, для ограничений типа (2) целесообразно использовать штрафную функцию следующего вида:

где - непрерывные функции, которые удовлетворяют условиям:

, если и , , если ,

, если и , , если .

Типичными являются следующие выражения для функций :

;

где - целое положительное число.

Таким образом, штрафная функция обычно имеет вид

Далее от задачи (1) переходим к задаче безусловной оптимизации вспомогательной функции:

Минимизировать

,

где - штрафной коэффициент.

Пусть - непрерывная функция вида (3). Обозначим

Подход, связанный со штрафной функцией, состоит в решении задачи вида:

максимизировать

при ограничении

5. Алгоритм метода штрафных функций

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

Итак, пусть имеем задачу ЛП:

минимизировать

при ограничениях ,

где функции непрерывны.

Начальный этап. Выбрать . Выбрать начальную точку , параметр штрафа и число . Положить и перейти к основному этапу.

Основной этап. Первый шаг. При начальной точке и параметре штрафа решить следующую задачу:

Минимизировать

где - целое.

Положить равным оптимальному решению этой задачи и перейти ко второму шагу.

Второй шаг. Если , то остановиться. В противном случае положить . Заменить на и перейти к первому шагу.

Заключение

задача линейный программирование

Полиноминальные методы решения линейного программирования, к которым относятся рассмотренные в данной работе метод барьерных поверхностей и метод штрафных функций, несомненно более перспективные и лучше подходят для решения задач большой размерности (а часто и безальтернативно) чем экспоненциальные методы к которым относится, например симплекс-метод. Этот факт подтверждается огромным объемом литературы и исследований на эту тему.

Литература

1. Банди Б. Методы Оптимизации. Вводный курс. М.: Радио и связь, 1988.

2. Васильев Ф.П., Иваницкий А.Ю. Линейное программирование. М.: Факториал, 2003.

3. Голиков А.И., Евтушенко Ю.Г, Моллаверди Н. Применение метода Ньютона к решению задач линейного программирования большой размерности // Ж. вычисл. матем. и матем. физ. 2004. Т. 44. №

4. Голынтейн Е.Г., Юдин Д.Б. Новые направления в линейном программировании. М.: Сов.радио, 1966.

5. Поляк Б.Т., Третьяков Н.В. Об одном итерационном методе линейного программирования и его экономической интерпретации // Эконом, и матем. методы. 1972. Т. VIII. Вып. 5.

6. http://life.susu.ru/#Web-ресурсы. Проект LiFe. Алгоритмы и методы решения задач линейного программирования большой размерности в условиях неполных, противоречивых и изменяющихся исходных данных

7. http://ru.wikipedia.org Википедия. Свободная энциклопедия

8. Булавский В.А., Звягина Р.А., Яковлева М.А. Численные методы линейного программирования. М.: Наука, 1977.

Размещено на Allbest.ru