Решение задач по нелинейной оптимизации. Метод множителей Лагранжа.

Методы решения задач нелинейной оптимизации

Существующие методы нелинейного программирования можно подразделить на следующие основные классы.

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

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

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

2. Методы Монте-Карло. Здесь отыскивается n - мерный параллелепипед, включающий в себя множество планов, и затем моделируются N случайных точек с равномерным законом распределения в параллелепипеде (практически во всех программных средах предусмотрено наличие соответствующих датчиков псевдослучайных чисел).

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

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

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

При решении многих задач нелинейного программирования определенный эффект дает метод множителей Лагранжа.

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

Функция называется функцией Лагранжа и коэффициенты – множителями Лагранжа.

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

Пример 3.1 Найти максимум функции , при условии

Строится функция Лагранжа

Строим систему уравнений

, , , решение которой дает , .

3.2. Задания для самостоятельной работы.

1) при условии ;

2) при условии ;

3) при условии ;

4) при условии ;

5) при условии ;

6) при условии

Практическое занятие №4

Сетевая модель, расчет основных параметров сетевого графика.

Построение сетевого графика

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

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

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

События, как правило, обозначаются кружками. Предполагается, что события не имеют продолжительности во времени.

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

Различают три вида операций:

1) действительная операция ( ) – процесс, требующий затрат времени и ресурсов (разработка проекта, подвоз материалов, выполнение монтажных работ и т. д.);

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

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

При построении сетевых графиков необходимо соблюдать определенные правила:

1) в сети не должно быть событий (кроме исходного), в которые не входит ни одна дуга;

2) не должно быть событий (кроме завершающего), из которых не выходит ни одной дуги;

3) сеть не должна содержать контуров;

4) любая пара событий сетевого графика может быть соединена не более чем одной дугой. Если изобразить одновременно выполняемые три различные операции , , с общими начальным и конечным событиями (Рис. 4.1), то возникает путаница из-за того, что различные операции имеют одно и то же обозначение (2, 5). В этом случае рекомендуется ввести дополнительные события и соединить их с последующими фиктивными операциями (Рис. 4.2);

 

 

Рис. 4.1

 

5) номер начального события любой операции должен быть меньше номера ее конечного события.

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

 

Рис. 4.2

Эта зависимость представлена на Рис. 4.3, из которого видно, что операция следует за операцией и фиктивной операцией (2, З).

 

 

Рис. 4.3

 

В свою очередь, операция (2, 3) следует за операцией . Тогда в силу транзитивности выполнение операции предшествует выполнению операции .

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

После составления списка операций приступают к процедуре построения сети.

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

 

Таблица 4.1.

Описание составных работ проекта

Работа	Непосредственно предшествующие работы	Время выполнения
A	---
B	---
C	B
D	A, C
E	C
F	C
G	D, E, F

Анализ данных, приведенных в этой таблице, последовательности и взаимозависимости работ, позволяет построить сетевой график представленный на рис. 4.4.

Рис. 4.4

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

⇐ Предыдущая12345Следующая ⇒

Поделиться: