Оптимизация и математические методы принятия решений

 

Содержание

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

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

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

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

 

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

 

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

,                      

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

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

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

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

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

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

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

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

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

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

 

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

 

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

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

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

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

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

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

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

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

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

 

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

 

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

Пусть, как и выше, имеется задача:

минимизировать   ,        (1) 

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

                                    (2)

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

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

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

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

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

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

;   , где – целое положительное число.

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

     (3)

 Далее от задачи (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.