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