Решение задач линейного программирования

• Введение
• 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.