Главная - Прикладная математика - Дифференциальный алгоритм решения общей задачи математического программирования. Метод Франка-Вулфа
Дифференциальный алгоритм решения общей задачи математического программирования. Метод Франка-Вулфа Прикладная математика . Курсовая
- Тема: Дифференциальный алгоритм решения общей задачи математического программирования. Метод Франка-Вулфа
- Автор: Дмитрий
- Тип работы: Курсовая
- Предмет: Прикладная математика
- Страниц: 33
- Год сдачи: 2006
- ВУЗ, город: Харьковский Национальный Университет Радиоэлектроники
- Цена(руб.): 1500 рублей
Выдержка
Постановка задачи
Общая задача математического программирования имеет следующий вид:
Здесь минимизируемая функция, область допустимых решений.
1.2 Дифференциальный алгоритм
1.2.1 Переменные состояния и переменные решения
Область допустимых решений состоит из всех точек , которые удовлетворяют системе уравнений (1.1.2). В каждой окрестности точки имеется два типа точек: точки, не принадлежащие области , для которых , и точки, принадлежащие ей, для которых . Разобьем вектор на два составляющих вектора: , где -мерный, а -мерный ( ) векторы. Составляющие вектора называются переменными состояния (зависимыми переменными), а составляющие вектора переменными решения (независимыми переменными).
Пусть в качестве переменных состояния взяты первые составляющих вектора . Тогда
,
.
Разложим функцию и ограничения в ряд Тейлора в окрестности точки , ограничиваясь линейными членами:
, (1.2.1)
. (1.2.2)
Здесь матрицы Якоби (размерности ) и управления (размерности ) соответственно:
, .
Выражение (1.2.2) равно нулю, поскольку нас интересует изменения функций (1.1.2), не выходящие из области допустимых решений .
Система уравнений (1.2.1), (1.2.2) представляет собой линейное уравнение c неизвестным. Считаем, что эти уравнения линейно независимы; в противном случае берем их наибольшее число, образующее линейно независимую систему, пренебрегая остальными как избыточными. Отсюда, очевидно, автоматически исключается случай , когда число уравнений больше числа неизвестных, а не представляет интереса, поскольку единственно возможное решение есть , то есть не существует допустимой окрестности в области задания вообще, что выражается в (1.1.2).
В общем случае разбиение на переменные состояния и решения производится произвольно. Единственное условие, которое при этом необходимо соблюдать, неособенность матрицы Якоби: . Должно быть ровно зависимых и независимых переменных, но для решения рассматриваемой проблемы не имеет значения, какие из переменных к какой категории относятся, если выполнено данное условие. В конкретной ситуации иногда ясно, какие из переменных должны быть зависимыми, а какие независимыми.
Как бы не были выбраны независимые переменные, любые значения их приращений позволяют определить в результате решения системы (1.2.2) единственный ряд изменений зависимых переменных , не выводящих новую точку из заданной области. После этого результирующее изменение , вычисленное в соответствии с уравнением (1.2.1), можно использовать для анализа изменения критерия, чтобы увидеть, приводят ли указанные изменения к ее улучшению.
Переменные решения можно изменять свободно, в то время как основное назначение переменных состояния удержат новую точку в заданной области. Произвольное изменение более чем переменных выведет точку из заданной области . Задание менее переменных приводит к бесконечному множеству решений и к невозможности найти местоположение новой точки. Точное число независимых переменных (решений) называется числом степеней свободы системы. Каждое дополнительное ограничение уменьшает данное число и снижает число независимых переменных на единицу, упрощая тем самым проблему оптимизации.
Содержание
Введение 5
1 Теоретическая часть 6
1.1 Постановка задачи 6
1.2 Дифференциальный алгоритм 6
1.2.1 Переменные состояния и переменные решения 6
1.2.2 Условные производные решения 8
1.2.3 Необходимые условия 9
1.2.4 Достаточные условия 10
1.2.5 Дифференциальный алгоритм 12
1.3 Метод Франка-Вулфа 16
1.3.1 Градиентные методы 16
1.3.2 Метод Франка-Вулфа 17
2 Практическая часть 19
2.1 Постановка задачи 19
2.2 Входные и выходные параметры 19
2.3 Решение дифференциальным алгоритмом 19
2.4 Решение методом Франка-Вулфа 22
2.5 Сравнительный анализ методов 24
Выводы 25
Список использованных источников 26
Приложение 27
Литература
1.Евдокимов А.Г. Минимизация функций и ее приложения к задачам автоматизированного управления инженерными сетями. Харьков: Вища школа, 1985. 288 с.
2.Акулич М.Л. Математическое программирование в упражнениях и задачах. М.: Высшая школа, 1986. 319 с.
3.Химмельблау Д. Прикладное нелинейное программирование. М.: Мир, 1975. 455 с.
4.Кузнецов А.В., Сакович В.А., Холод И.И. Высшая математика. Математическое программирование. Мн.: Выш. школа, 1988. 392 с.
Форма заказа
Похожие работы
| Название | Тип | Год сдачи | Страниц | Цена |
|---|---|---|---|---|
| Модели целочисленного булевого программирования. Алгоритм последовательного анализа вариантов решения | Курсовая | 2006 | 29 | 1500 |
| Метод проекции градиента (метод Розена) для решения задач нелинейного программирования | Курсовая | 2006 | 29 | 1500 |
| Решение задач целочисленного программирования методами ветвей и границ и частичного перебора | Курсовая | 2006 | 42 | 1500 |
| Задача Жуковского о полете планера | Курсовая | 2005 | 15 | 1500 |
| Курсовая работа по прикладной математике | Курсовая | 2001 | 17 | 1500 |
| Численные методы | Курсовая | 2003 | 26 | 1500 |
| Линейное программирование: постановка задач и графическое решение | Курсовая | 2000 | 17 | 1500 |
| Линейное программирование: решение задач графическим способом | Курсовая | 2003 | 33 | 1500 |
| Линейное и динамическое программирование | Курсовая | 2004 | 18 | 1500 |
| Определение максимума (минимума) функций методом «золотого сечения | Курсовая | 2008 | 19 | 1500 |