Главная - IT - Прикладная математика - Дифференциальный алгоритм решения общей задачи математического программирования. Метод Франка-Вулфа

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

  • Тема: Дифференциальный алгоритм решения общей задачи математического программирования. Метод Франка-Вулфа
  • Автор: Дмитрий
  • Тип работы: Курсовая
  • Предмет: Прикладная математика
  • Страниц: 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 Купить Заказать
оригинальную