решение задач линейной оптимизации большой размерности

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

---

Качественная дипломная работа под заказ . Обращайтесь в Work5.

---

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

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

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.