«Исследование и сопоставительный анализ численных методов решения задач не линейного программирования с ограничением типа неравенств»

Вид материала

Исследование

Содержание 8 Семестр 4 курс Глава 1 обзор тематики, сопоставление источников, постановка задачи Методы исследования функций классического анализа Метод множителей Лагранжа Методы вариационного исчисления Динамическое программирование Принцип максимума Линейное программирование Методы нелинейного программирования Геометрическое программирование 3.3. Градиентный метод с постоянным шагом. Линией уровня функции f М, аппроксимирующий допустимую область G 3.4. Один пример исследования сходимости. Области пременения нелинейного программирования Библиографический список

Подобный материал:

• Краткий обзор моделей стохастического программирования и методов решения экономических, 59.55kb.
• Литература: [1,8-11,16,18], 419.3kb.
• Кафедра «Прикладная математика» Экономические приложения линейного программирования, 27.15kb.
• Рабочая программа дисциплины информатика направление ооп, 1183.82kb.
• Методические рекомендации к проведению урока: «Методы решения уравнений и неравенств., 15.21kb.
• Методы решения матричных игр. Метод линейного программирования, 31.9kb.
• Базы данных и файловые системы, 141.17kb.
• Задачи линейного программирования Геометрическая интерпретация задач линейного программирования, 132.4kb.
• Задачи линейного программирования Геометрическая интерпретация задач линейного программирования, 38.07kb.
• Темы курсовых работ «Методы оптимизации» Графический метод решения задачи линейного, 11.12kb.

ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ


ГОУВПО «Самарский государственный архитектурно-строительный университет»


Факультет информационных систем и технологий


Кафедра прикладной математики и вычислительной техники


ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

К КУРСОВОЙ РАБОТЕ


по дисциплине

ТЕХНОЛОГИЯ

НАУЧНЫХ ИССЛЕДОВАНИЙ


На тему


«Исследование и сопоставительный анализ численных методов решения задач не линейного программирования с ограничением типа

неравенств»


8 СЕМЕСТР 4 КУРС


Научный руководитель: Пиявский С. А.

Проверили:	Выполнила студентка ГИП-104 Ахметова Г.С.
1. Пиявский С.А ________________________	_______________________

Введение

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

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


ГЛАВА 1 ОБЗОР ТЕМАТИКИ, СОПОСТАВЛЕНИЕ ИСТОЧНИКОВ, ПОСТАНОВКА ЗАДАЧИ


1.1 ХАРАКТЕРИСТИКА НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

1.1.1 ОБЗОР МЕТОДОВ ПРОГРАММИРОВАНИЯ

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

В настоящее время для решения оптимальных задач применяют в основном следующие методы:

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

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

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

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

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

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

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

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

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

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

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

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


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

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

Уравнения Эйлера выводятся как необходимые условия экстремума функционала. Поэтому полученные интегрированием системы дифференциальных уравнений функции должны быть проверены на экстремум функционала.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Названием “методы нелинейного программирования” объединяется большая группа численных методов, многие из которых приспособлены для решения оптимальных задач соответствующего класса. Выбор того или иного метода обусловлен сложностью вычисления критерия оптимальности и сложностью ограничивающих условий, необходимой точностью решения, мощностью имеющейся вычислительной машины и т.д. Ряд методов нелинейного программирования практически постоянно используется в сочетании с другими методами оптимизации, как, например, метод сканирования в динамическом программировании. Кроме того, эти методы служат основой построения систем автоматической оптимизации - оптимизаторов, непосредственно применяющихся для управления производственными процессами.

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

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

Важной характеристикой любой оптимальной задачи является ее размерность п, равная числу переменных, задание значений которых необходимо для однозначного определения состояния оптимизируемого объекта. Как правило, решение задач высокой размерности связано с необходимостью выполнения большого объема вычислений. Ряд методов (например, динамическое программирование и дискретный принцип максимума) специально предназначен для решения задач оптимизации процессов высокой размерности, которые могут быть представлены как многостадийные процессы с относительно невысокой размерностью каждой стадии.

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

• вид математического описания процесса;
  
• тип ограничений на переменные процесса
  
• число переменных.
  

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

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


Таблица1.1

вид описания процесса		конечные уравнения						Дифференциальные уравнения
Тип ограничений на переменные		Нет		Равенства		Неравенства		Нет		Равенства		Неравенства
Число переменных		?3	>3	?3	>3	?3	>3	?3	>3	?3	>3	?3	>3
Тип метода	Методы классического анализа	1	2	4	4	4	4	3	4	4	4	4	4
	Множители Лагранжа	-	-	1	2	-	-	-	-	2	3	-	-
	Вариационное исчисление	-	-	-	-	-	-	2	3	2; 7	3; 7	-	-
	Динамическое программирование	1; 5	3; 5	1;5;7	3; 5; 7	1; 5	3; 5	2	3	3	3	3	3
	Принцип максимума	2; 5	1; 5	2; 5	2; 5	2; 5	2; 5	1	1	2	2	2	2
	Линейное программирование	-	-	-	2; 6	2; 6	1; 6	-	-	-	-	-	-
	Методы нелинейного программирования	1	2	1	2	1	2	4	4	4	4	4	4
	Геометрическое программирование	2; 8	2; 8	-	-	2; 8	2; 8	-	-	-	-	-	-

Примечания:

1. Эффективное применение метода.
   2. Используется.
   3. Возможно применение.
   4. Используется как вспомогательный метод.
   5. Многостадийные процессы (размерность указывается для отдельной стадии).
   6. Задачи с линейными критериями оптимальности и линейными ограничениями.
   7. Используются множители Лагранжа.
   8. Задачи с критериями и ограничениями в форме позиномов.
   

Наиболее распространенные и эффективные методы приближенного решения задачи безусловной оптимизации f(x)  min,

где f: R^m  R, укладываются в следующую грубую схему. Начиная с некоторого x⁰  R^m, строится последовательность

{xⁿ}  R^m такая, что f(xⁿ⁺¹) < f(xⁿ)

при всех n  N. Такие последовательности иногда называют релаксационными, а методы построения релаксационных последовательностей — итерационными методами или методами спуска. Последовательность, удовлетворяющую (2), строят в надежде, что уменьшая на каждом шаге (переходе от xⁿ к xⁿ⁺¹) значение функции, мы приближаемся к минимуму (по крайней мере, локальному).

Мы будем говорить, что метод, начиная с данного x⁰  R^m,

а) условно сходится, если последовательность {xⁿ} релаксационна и

f (xⁿ)   при n  ;

б) сходится, если xⁿ  x* = argmin f(x) при n  ;

в) линейно сходится (или сходится со скоростью геометрической прогрессии, или имеет первый порядок сходимости), если при некоторых C > 0 и q  [0, 1)

||xⁿ  x*||  Cqⁿ;

г) сверхлинейно сходится, если для любого q  (0, 1) и некоторого (зависящего от q) C выполнено неравенство (3);

д) квадратично сходится (или имеет второй порядок сходимости), если при некоторых C > 0 и q  [0, 1) и всех n  N

||xⁿ  x*||  Cq²ⁿ.

Если эти свойства выполняются только для x⁰ достаточно близких к x*, то как всегда добавляется эпитет "локально".

З а д а ч а  3.1*. Пусть при некотором q  [0, 1)

||xⁿ⁺¹  x*||  q||xⁿ  x*||, n  N.

Докажите, что метод линейно сходится.

З а д а ч а  3.2*. Пусть при некотором C₁ > 0

||xⁿ⁺¹  x*||  C₁||xⁿ x*||², n  N

и ||x⁰  x*|| достаточно мала. Докажите, что метод квадратично сходится.

Будем говорить, что на данной последовательности метод сходится с порядком p (или имеет p-ый порядок сходимости), если при некотором C

||xⁿ⁺¹  x*||  C||xⁿ  x*||^p.

3.2. Эвристические соображения, приводящие к градиентным методам.

Выше уже отмечалось, что если x не является точкой локального минимума функции f, то двигаясь из x в направлении, противоположном градиенту (еще говорят, в направлении антиградиента), мы можем локально уменьшить значение функции. Этот факт позволяет надеяться, что последовательность {xⁿ}, рекуррентно определяемая формулой

xⁿ⁺¹ = xⁿ  f (xⁿ),

где  - некоторое положительное число, будет релаксационной.

К этой же формуле приводит и следующее рассуждение. Пусть у нас есть некоторое приближение xⁿ. Заменим в шаре B(xⁿ, ) с центром в точке xⁿ функцию f ее линейным (вернее, афинным) приближением:

f(x)  (x) = f(xⁿ) + (f (xⁿ), x  xⁿ)

(функция  аппроксимирует f в окрестности точки xⁿ с точностью o(x - xⁿ)). Разумеется, (линейная) безусловная задача (x)  min неразрешима, если f (xⁿ)   (см. задачу 1.3). В окрестности же B(xⁿ, ) функция  имеет точку минимума. Эту точку естественно взять за следующее приближение xⁿ⁺¹.

3.3. Градиентный метод с постоянным шагом.

В общем случае число  в формуле (4) может на каждом шаге (т. е. для каждого n) выбираться заново: xⁿ⁺¹ = xⁿ  ⁿf (xⁿ).

Именно методы, задаваемые формулой (5), называются градентными. Если ⁿ =  при всех n, то получающийся метод называется градиентным методом с постоянным шагом (с шагом .)

Поясним геометрическую суть градиентного метода. Для этого мы выберем способ изображения функции с помощью линий уровня. Линией уровня функции f (изолинией) называется любое множество вида {x  R^m: f(x) = c}. Каждому значению c отвечает своя линия уровня (см. рис. 5).


Рис. 5.

Геометрическая интерпретация градиентного метода с постоянным шагом изображена на рис. 6. На каждом шаге мы сдвигаемся по вектору антиградиента, "уменьшенному в  раз".


Рис. 6.



Метод проекции градиента

Рассмотрим данный метод применительно к задаче оптимизации с ограничениями-неравенствами. В качестве начальной выбирается некоторая точка допустимой области G. Если х[0] - внутренняя точка множества G (Рис. 3.1), то рассматриваемый метод является обычным градиентным методом:

x[k+l] x[k] –a_kf’(x[k]), k 0, 1, 2, ...,

где

градиент целевой функции f(х) в точке x[k].

После выхода на границу области G в некоторой граничной точке х[k] , k 0, 1, 2,..., движение в направлении антиградиента -f’(х[k]) может вывести за пределы допустимого множества (см. Рис. 3.1). Поэтому антиградиент проецируется на линейное многообразие М, аппроксимирующее участок границы в окрестности точки х[k]. Двигаясь в направлении проекции вектора -f'(x[k]) на многообразие М, отыскивают новую точку х[k+1], в которой f(х[k+1]) f(x[k]), принимают х[k+1] за исходное приближение и продолжают процесс. Проведем более подробный анализ данной процедуры.



Рис. 3.1. Геометрическая интерпретация метода проекции градиента

В точке х[k] часть ограничений-неравенств удовлетворяется как равенство:

h_i(x) 0, j 1, ..., l; l m.

Такие ограничения называют активными.

Обозначим через J набор индексов j(1 j l) этих ограничений. Их уравнения соответствуют гиперповерхностям, образующим границу области G в окрестности точки х[k] . В общем случае эта граница является нелинейной (см. рис. 3.1). Ограничения h_j(x), j J, аппроксимируются гиперплоскостями, касательными к ним в точке х[k]:



Полученные гиперплоскости ограничивают некоторый многогранник М, аппроксимирующий допустимую область G в окрестности точки х[k] (см. Рис. 3.1).

Проекция р[k] антиградиента -f'(x[k]) на многогранник вычисляется по формуле

p[k] P[-f’(x[k])].

Здесь Р - оператор ортогонального проектирования, определяемый выражением

Р E – A^T(AA^T)^-1A,

где Е - единичная матрица размеров п; А - матрица размеров lхn . Она образуется транспонированными векторами-градиентами а_j, j 1, ..., l, активных ограничений. Далее осуществляется спуск в выбранном направлении:

x[k+1] x[k] + a_kp[k].

Можно показать, что точка х[k+1] является решением задачи минимизации функции f(х) в области G тогда и только тогда, когда Р[-f’(x[k])] 0,

т. е, и u (u₁, ..., u_l) (A^TA)^-1A^T(-f’(х[k])) 0.

Эти условия означают, что антиградиент (-f’(х[k])) целевой функции является линейной комбинацией с неотрицательными коэффициентами градиентов ограничений h_j(x) 0.

В соответствии с изложенным алгоритм метода проекции градиента состоит из следующих операций.

1. В точке х[k] определяется направление спуска р[k].

2. Находится величина шага а_k.

3. Определяется новое приближение х[k+1].

Рассмотрим детально каждую из этих операций.

1. Определение направления спуска состоит в следующем. Пусть найдена некоторая точка х[k] G и известен набор активных ограничений h_i(х[k]) 0, j J. На основании данной информации вычисляют (-f’(х[k])) и определяют проекцию Р[-f’(х[k])]. При этом возможны два случая:

а) Р[-f’(х[k])] не равна 0. В качестве направления спуска р[k] принимают полученную проекцию;

б) Р[-f’(х[k])] 0, т. е. .

Данное выражение представляет собой систему из п уравнений для определения коэффициентов и_j. Если все и_j 0, j J, то в соответствии с вышеизложенным точка х[k] является решением задачи. Если же некоторый компонент и_q 0, то соответствующий ему градиент выводится из матрицы А и порождается новая проецирующая матрица Р. Она определит новое направление спуска.

2. Для определения величины шага а_k целевая функция минимизируется по направлению р[k] при условии соблюдения ограничений задачи с установленной точностью. Последняя задается введением некоторого положительного числа . Считают, что точка х удовлетворяет условиям задачи с заданной точностью, если h_i(х) , j 1, ..., m. Величина шага а_k определяется решением задачи вида:

f(x[k] + ар[k]) > min;

h_j(x[k] + ар[k]) , j 1, ..., m.

3. Определение нового приближения состоит в следующем. Очередная точка вычисляется по формуле

x[k+1] x[k] + а_kр[k].

Признаком сходимости является стремление к нулю векторов р[k]. Рассмотренный метод является в некотором смысле аналогом градиентных методов для решения задач на безусловный экстремум, и ему свойствен их недостаток - медленная сходимость.


3.4. Один пример исследования сходимости.

Изучим сходимость градиентного метода с постоянным шагом на примере функции f(x) = |x|^p,

где p > 1 (случай p Ј 1 мы не рассматриваем, поскольку тогда функция f не будет гладкой, а мы такой случай не исследуем). Очевидно, задача (1) с такой функцией f имеет единственное решение x* = 0. Для этой функции приближения xⁿ градиентного метода имеют вид:

xⁿ⁺¹ = xⁿ - ap|xⁿ|^p-1sign xⁿ.

Пределом этой последовательности может быть только 0. Действительно, если x** = lim_n®Ґ xⁿ № 0, то, переходя к пределу в (6) при n ® Ґ, получаем противоречащее предположению x** № 0 равенство

x** = x** - ap|x**|^p-1sign  x**,

откуда x** = 0. Очевидно также, что если x⁰ = 0, то и xⁿ = 0 при всех n.

Покажем, что если p < 2, то при любом шаге a > 0 и любом начальном приближении x⁰ (за исключением не более чем счетного числа точек) приближения (6) не являются сходящимися. Для этого заметим, что если 0 < |xⁿ| < (2/ap)^1/2(2-p), то

|xⁿ⁺¹| > |xⁿ|.

Поэтому, если xⁿ не обращается в нуль, то она не может сходиться к нулю и, следовательно, не может сходиться вообще.

Таким образом, осталось доказать (7). В силу (6)

|xⁿ⁺¹| = |xⁿ - ap|xⁿ|^p-1 ·sign xⁿ| = |xⁿ|·| 1 -ap|xⁿ|^p-2·sign xⁿ|.

Остается заметить, что если 0 < |xⁿ| < (2/ap)^1/(2-p), то, как нетрудно видеть, |1 - ap|xⁿ|^p-2·sign  xⁿ| > 1, что и требовалось.

Если p = 2, т. е. f(x) = x², то (6) переписывается в виде

|xⁿ⁺¹| = |xⁿ|·|1 - 2a|.

Поэтому, если a О (0, 1), то |1 - 2a| < 1, а следовательно,

|xⁿ⁺¹| = |1 - 2a|ⁿ⁺¹·|x⁰| ® 0 при n ® Ґ.

Если же a і 1, то |xⁿ⁺¹| і |xⁿ|,

и последовательность {xⁿ}, начинающаяся из ненулевой начальной точки, расходится.

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

2. ОБЛАСТИ ПРЕМЕНЕНИЯ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
   

Задача нелинейного программирования встречается в естественных науках, технике, экономике, математике, в сфере деловых отношений и в науке управления государством.

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

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

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

Библиографический список

1 Лященко И.Н. Линейное и нелинейное программирования / И.Н.Лященко, Е.А.Карагодова, Н.В.Черникова, Н.З.Шор. – К.: «Высшая школа», 1975, 372 с.

2 Методические указания для выполнения курсового проекта по дисциплине «Прикладная математика» для студентов специальности «Компьютерные системы и сети» дневной и заочной форм обучения / Сост.: И.А.Балакирева, А.В.Скатков– Севастополь: Изд-во СевНТУ, 2003. – 15 с.

3 Методические указания по изучению дисциплины «Прикладная математика», раздел «Методы глобального поиска и одномерной минимизации» / Сост. А.В.Скатков, И.А.Балакирева, Л.А.Литвинова – Севастополь: Изд-во СевГТУ, 2000. – 31с.