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

 

Содержание


Введение

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

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

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

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

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

Заключение

Литература


Введение


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

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

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

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


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

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

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


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


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



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

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

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


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

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


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

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

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

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

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

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


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

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

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

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

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

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


,


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

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

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



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


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


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



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

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



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


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

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

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


;


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

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



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

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


,


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

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



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

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

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


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


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

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

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

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

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

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

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

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



где - целое.

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

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

Заключение

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

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


Литература


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

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

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

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

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

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

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

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


Содержание Введение . Параметрические методы решения задач линейного программирования . Метод барьерных поверхностей . Алгоритм метода барьерных

Больше работ по теме:

КОНТАКТНЫЙ EMAIL: [email protected]

Скачать реферат © 2017 | Пользовательское соглашение

Скачать      Реферат

ПРОФЕССИОНАЛЬНАЯ ПОМОЩЬ СТУДЕНТАМ