Линейное и нелинейное программирование
Общая формулировка задания на курсовой проект. Линейное программирование. Задача целочисленного линейного программирования, с булевскими переменными. Нелинейное программирование. Задача поиска глобального экстремума функции.
Рубрика | Математика |
Вид | курсовая работа |
Язык | русский |
Дата добавления | 17.05.2006 |
Размер файла | 506,1 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
2
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ
Севастопольский национальный технический университет
Кафедра кибернетики и вычислительной техники
Пояснительная записка
к курсовому проекту
по дисциплине
«Прикладная математика»
Выполнил: ст. гр. М-21д
Ткаченко К. С.
зач. книжка № 040xxx
вариант № 22
Проверил: ст. преп.
Балакирева И. А.
Севастополь - 2006
Содержание
- Введение 4
- 1 Общая формулировка задания на курсовой проект 5
- 2 Линейное программирование 7
- 2.1 Задача линейного программирования 7
- 2.1.1 Постановка задачи линейного программирования 7
- 2.1.2 Математическая модель задачи линейного программирования 8
- 2.1.3 Графический метод 9
- 2.1.4 Алгебраический метод 10
- 2.1.5 Метод симплекс-таблицы 12
- 2.1.6 Метод допустимого базиса 14
- 2.1.7 Решение двойственной задачи 17
- 2.2 Задача целочисленного линейного программирования 19
- 2.2.1 Постановка задачи целочисленного линейного программирования 19
- 2.2.2 Метод Гомори 20
- 2.2.3 Метод ветвей и границ 22
- 2.3 Задача целочисленного линейного программирования с булевскими переменными 24
- 2.3.1 Постановка задачи целочисленного линейного программирования с булевскими переменными 24
- 2.3.2 Метод Баллаша 25
- 2.3.3 Определение снижения трудоемкости вычислений 26
- 3 Нелинейное программирование 27
- 3.1 Задача поиска глобального экстремума функции 27
- 3.1.1 Постановка задачи поиска глобального экстремума функции 27
- 3.1.2 Метод поиска по координатной сетке с постоянным шагом и метод случайного поиска. Сравнение результатов вычислений 28
- 3.2 Задача одномерной оптимизации функции 29
- 3.2.1 Постановка задачи одномерной оптимизации функции 29
- 3.2.2 Метод дихотомии 30
- 3.2.3 Метод Фибоначчи 31
- 3.2.4 Метод кубической аппроксимации 32
- 3.3 Задача многомерной оптимизации функции 33
- 3.3.1 Постановка задачи многомерной оптимизации функции 33
- 3.3.2 Метод Хука - Дживса 34
- 3.3.3 Метод наискорейшего спуска (метод Коши) 36
- 3.3.4 Метод Ньютона 37
- 3.3.5 Сравнение результатов вычислений 38
- Заключение 39
- Библиографический список 40
- ПРИЛОЖЕНИЕ 41
- А Текст программы глобальной многомерной оптимизации 41
- Б. Результаты работы программы 44
Введение
Современный этап развития человечества отличается тем, что на смену века энергетики приходит век информатики. Происходит интенсивное внедрение новых технологий во все сферы человеческой деятельности. Встает реальная проблема перехода в информационное общество, для которого приоритетным должно стать развитие образования. Изменяется и структура знаний в обществе. Все большее значение для практической жизни приобретают фундаментальные знания, способствующие творческому развитию личности. Важна и конструктивность приобретаемых знаний, умение их структурировать в соответствии с поставленной целью. На базе знаний формируются новые информационные ресурсы общества. Формирование и получение новых знаний должно базироваться на строгой методологии системного подхода, в рамках которого отдельное место занимает модельный подход. Возможности модельного подхода крайне многообразны как по используемым формальным моделям, так и по способам реализации методов моделирования. Физическое моделирование позволяет получить достоверные результаты для достаточно простых систем.
В настоящее время нельзя назвать область человеческой деятельности, в которой в той или иной степени не использовались бы методы моделирования. Особенно это относится к сфере управления различными системами, где основными являются процессы принятия решений на основе получаемой информации.
1 Общая формулировка задания на курсовой проект
Вариант задания для задачи линейного программирования (ЗЛП) представляет собой область допустимых решений ЗЛП и целевую функцию. Для того чтобы определить, какое значение должна достигать целевая функция - минимальное или максимальное, необходимо найти градиент целевой функции. Если направление градиента совпадает с направлением стрелки у целевой функции в варианте задания, то в задаче определяется максимальное значение целевой функции, иначе - минимальное.
Итак, задание по решению ЗЛП состоит в следующем: построить математическую модель ЗЛП согласно варианту; получить решение ЗЛП графическим методом; решить ЗЛП алгебраическим методом; решить ЗЛП методом симплекс-таблицы; определить допустимое решение ЗЛП методом введения искусственного базиса; построить ЗЛП, двойственную данной, решить эту задачу и исследовать взаимосвязь между решениями взаимодвойственных задач.
Вариант для задачи целочисленного линейного программирования (ЗЦЛП) представляет собой область допустимых решений ЗЛП и целевую функцию. Задание состоит в следующем: решить ЗЦЛП, при условии целочисленности всех переменных, входящих в задачу методом ветвей и границ и методом отсекающих плоскостей (методом Гомори).
Вариант для задачи целочисленного линейного программирования с булевскими переменными составляется студентом самостоятельно с учетом следующих правил: в задаче используется не менее 5 переменных, не менее 4 ограничений, коэффициенты ограничений и целевой функции выбираются произвольно, но таким образом, чтобы система ограничений была совместна. Задание состоит в том, чтобы решить ЗЦЛП с булевскими переменными, используя алгоритм Баллаша и определить снижение трудоемкости вычислений по отношению к решению задачи методом полного перебора.
Задание на поиск глобального экстремума функции состоит в написании программы. Программа для поиска экстремума функции может быть разработана на любом алгоритмическом языке. Задание состоит в следующем: 1) найти точку глобального экстремума функции f(X) методом поиска по координатной сетке с постоянным шагом; 2) найти точку глобального экстремума функции f(X) методом случайного поиска; 3)сравнить результаты вычислений.
Задание для нахождения одномерного локального экстремума функции (одномерная оптимизация) состоит в том, чтобы выполнить поиск минимума заданной функции методом дихотомии (3-4 итерации), уточнить интервал поиска методом Фибоначчи (3 итерации) и завершить поиск методом кубической аппроксимации.
Задание для нахождения многомерного локального экстремума функции (многомерная оптимизация) состоит в том, чтобы минимизировать функцию, применяя следующие методы: нулевого порядка - Хука-Дживса, первого порядка - наискорейшего спуска (Коши), второго порядка - Ньютона, и провести сравнительный анализ методов оптимизации по количеству итераций, необходимых для поиска экстремума при фиксированной точности и начальных координатах поиска X(0)=[-1,-1]T.
2 Линейное программирование
2.1 Задача линейного программирования
2.1.1 Постановка задачи линейного программирования
Построить математическую модель ЗЛП согласно варианту. Получить решение ЗЛП графическим методом. Решить ЗЛП алгебраическим методом. Решить ЗЛП методом симплекс-таблицы. Определить допустимое решение ЗЛП методом введения искусственного базиса. Построить ЗЛП, двойственную данной, решить эту задачу и исследовать взаимосвязь между решениями взаимодвойственных задач.
2.1.2 Математическая модель задачи линейного программирования
AB: ; ;
BC: ; ;
CD: ; ;
DE: ; ;
F: ; ;
Математическая модель:
2.1.3 Графический метод
Вычисляем значение целевой функции во всех вершинах симплекса и выбираем из них наименьшее. Это и будет оптимальное решение.
FA = 1
FB = -8
FC = -14
FD = 0
FE = 3
C(2, 4)
F = -14
2.1.4 Алгебраический метод
x2, x4, x5, x6 - базисные переменные, x1, x3 - свободные переменные
x1?F? x3?F? Выбираем x3 ? x4
x2, x3, x5, x6 - базисные переменные, x1, x4 - свободные переменные
x1?F? x4?F? Выбираем x1 ? x5
x1, x2, x3, x6 - базисные переменные, x4, x5 - свободные переменные
x1?F? x4?F?
X=(2, 4, 7, 0, 0, 5)
F = -14
2.1.5 Метод симплекс-таблицы
Приведем к каноническому виду:
x2, x4, x5, x6 - базисные переменные, x1, x3 - свободные переменные
? |
|||||||||
b |
x1 |
x3 |
|||||||
x2 |
1 |
2 |
-1 |
||||||
1 |
-3 |
1 |
|||||||
? |
x4 |
1 |
-3 |
1 |
1 |
||||
1 |
-3 |
1 |
|||||||
x5 |
12 |
-1 |
2 |
6 |
|||||
-2 |
6 |
-2 |
|||||||
x6 |
4 |
3 |
-1 |
||||||
1 |
-3 |
1 |
|||||||
F |
-4 |
-9 |
4 |
||||||
-4 |
12 |
-4 |
? |
|||||||||
b |
x1 |
x4 |
|||||||
x2 |
2 |
-1 |
1 |
||||||
2 |
1/5 |
-2/5 |
|||||||
x3 |
1 |
-3 |
1 |
||||||
6 |
3/5 |
-6/5 |
|||||||
? |
x5 |
10 |
5 |
-2 |
2 |
||||
2 |
1/5 |
-2/5 |
|||||||
x6 |
5 |
0 |
1 |
||||||
0 |
0 |
0 |
|||||||
F |
-8 |
3 |
-4 |
||||||
-6 |
-3/5 |
6/5 |
b |
x5 |
x4 |
|||||||
x2 |
4 |
1/5 |
3/5 |
||||||
x3 |
7 |
3/5 |
-1/5 |
||||||
x1 |
2 |
1/5 |
-2/5 |
||||||
x6 |
5 |
0 |
1 |
||||||
F |
-14 |
-3/5 |
-14/5 |
||||||
X = (2, 4, 7, 0, 0, 5)
F = -14
2.1.6 Метод допустимого базиса
? |
|||||||||||||||||
b |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|||||||||||
F |
0 |
-1 |
4 |
0 |
0 |
0 |
0 |
||||||||||
1/2 |
1/2 |
1/2 |
-1/2 |
0 |
0 |
0 |
|||||||||||
? |
о1 |
1 |
2 |
1 |
-1 |
0 |
0 |
0 |
1/2 |
||||||||
1/2 |
1/2 |
1/2 |
-1/2 |
0 |
0 |
0 |
|||||||||||
о2 |
2 |
-1 |
1 |
0 |
1 |
0 |
0 |
14/3 |
|||||||||
1/2 |
1/2 |
1/2 |
-1/2 |
0 |
0 |
0 |
|||||||||||
о3 |
14 |
3 |
2 |
0 |
0 |
1 |
0 |
3 |
|||||||||
-3/2 |
-3/2 |
-3/2 |
3/2 |
0 |
0 |
0 |
|||||||||||
о4 |
3 |
1 |
-1 |
0 |
0 |
0 |
1 |
||||||||||
-1/2 |
-1/2 |
-1/2 |
1/2 |
0 |
0 |
0 |
|||||||||||
f |
20 |
5 |
3 |
-1 |
1 |
1 |
1 |
||||||||||
-5/2 |
-5/2 |
-5/2 |
5/2 |
0 |
0 |
0 |
? |
|||||||||||||||||
b |
о1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|||||||||||
F |
1/2 |
1/2 |
9/2 |
-1/2 |
0 |
0 |
0 |
||||||||||
5/2 |
-1/2 |
-3/2 |
1 |
0 |
0 |
1 |
|||||||||||
x1 |
1/2 |
1/2 |
1/2 |
-1/2 |
0 |
0 |
0 |
||||||||||
5/2 |
-1/2 |
-3/2 |
1 |
0 |
0 |
1 |
|||||||||||
о2 |
5/2 |
1/2 |
3/2 |
-1/2 |
1 |
0 |
0 |
||||||||||
5/2 |
-1/2 |
-3/2 |
1 |
0 |
0 |
1 |
|||||||||||
о3 |
25/2 |
-3/2 |
1/2 |
3/2 |
0 |
1 |
0 |
25/3 |
|||||||||
-15/2 |
3/2 |
9/2 |
-3 |
0 |
0 |
-3 |
|||||||||||
? |
о4 |
5/2 |
-1/2 |
-3/2 |
1/2 |
0 |
0 |
1 |
5 |
||||||||
5 |
-1 |
-3 |
2 |
0 |
0 |
2 |
|||||||||||
f |
35/2 |
-5/2 |
1/2 |
3/2 |
1 |
1 |
1 |
||||||||||
-15/2 |
3/2 |
9/2 |
-3 |
0 |
0 |
-3 |
? |
|||||||||||||||||
b |
о1 |
x2 |
о4 |
x4 |
x5 |
x6 |
|||||||||||
F |
3 |
0 |
3 |
1 |
0 |
0 |
1 |
||||||||||
-3 |
0 |
-3/5 |
9/5 |
0 |
-3/5 |
9/5 |
|||||||||||
x1 |
3 |
0 |
-1 |
1 |
0 |
0 |
1 |
||||||||||
1 |
0 |
1/5 |
-3/5 |
0 |
1/5 |
-3/5 |
|||||||||||
о2 |
5 |
0 |
0 |
1 |
1 |
0 |
1 |
||||||||||
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|||||||||||
? |
о3 |
5 |
0 |
5 |
-3 |
0 |
1 |
-3 |
1 |
||||||||
1 |
0 |
1/5 |
-3/5 |
0 |
1/5 |
-3/5 |
|||||||||||
x3 |
5 |
-1 |
-3 |
2 |
0 |
0 |
2 |
||||||||||
3 |
0 |
3/5 |
-9/5 |
0 |
3/5 |
-9/5 |
|||||||||||
f |
10 |
-1 |
5 |
-3 |
1 |
1 |
-2 |
||||||||||
-5 |
0 |
-1 |
3 |
0 |
-1 |
3 |
? |
|||||||||||||||||
b |
о1 |
о3 |
о4 |
x4 |
x5 |
x6 |
|||||||||||
F |
0 |
0 |
-3/5 |
14/5 |
0 |
-3/5 |
14/5 |
||||||||||
-14 |
0 |
0 |
-14/5 |
-14/5 |
0 |
-14/5 |
|||||||||||
x1 |
4 |
0 |
1/2 |
2/5 |
0 |
1/5 |
2/5 |
10 |
|||||||||
-2 |
0 |
0 |
-2/5 |
-2/5 |
0 |
-2/5 |
|||||||||||
? |
о2 |
5 |
0 |
0 |
1 |
1 |
0 |
1 |
5 |
||||||||
5 |
0 |
0 |
1 |
1 |
0 |
1 |
|||||||||||
x2 |
1 |
0 |
1/5 |
-3/5 |
0 |
1/5 |
-3/5 |
||||||||||
3 |
0 |
0 |
3/5 |
3/5 |
0 |
3/5 |
|||||||||||
x3 |
8 |
-1 |
3/5 |
1/5 |
0 |
3/5 |
1/5 |
40 |
|||||||||
-1 |
0 |
0 |
-1/5 |
-1/5 |
0 |
-1/5 |
|||||||||||
f |
5 |
-1 |
-1 |
0 |
1 |
0 |
1 |
||||||||||
-5 |
0 |
0 |
-1 |
-1 |
0 |
-1 |
b |
о1 |
о3 |
о4 |
x4 |
x5 |
о2 |
|||||||||||
F |
-14 |
0 |
-3/5 |
0 |
-14/5 |
-3/5 |
-14/5 |
||||||||||
x1 |
2 |
0 |
1/5 |
0 |
-2/5 |
1/5 |
-2/5 |
||||||||||
x6 |
5 |
0 |
0 |
1 |
1 |
0 |
1 |
||||||||||
x2 |
4 |
0 |
1/5 |
0 |
3/5 |
1/5 |
-3/5 |
||||||||||
x3 |
7 |
-1 |
3/5 |
0 |
-1/5 |
3/5 |
-1/5 |
||||||||||
f |
0 |
-1 |
-1 |
-1 |
0 |
0 |
-1 |
||||||||||
b |
x4 |
x5 |
||
F |
-14 |
-14/5 |
-3/5 |
|
x6 |
5 |
1 |
0 |
|
x2 |
4 |
3/5 |
1/5 |
|
x3 |
7 |
-1/5 |
3/5 |
|
x1 |
2 |
-2/5 |
1/5 |
Допустимое базисное оптимальное решение:
X = (2, 4, 7, 0, 0, 5)
F = -14
2.1.7 Решение двойственной задачи
Прямая задача:
Двойственная задача:
Приводим к каноническому виду:
y1, y3 - базисные переменные, y2, y4, y5, y6 - свободные переменные
? |
|||||||||||||
b |
y2 |
y4 |
y5 |
y6 |
|||||||||
? |
y1 |
14 |
5 |
-5 |
2 |
-3 |
14/5 |
||||||
14/5 |
1/5 |
-1 |
2/5 |
-3/5 |
|||||||||
y3 |
9 |
3 |
-3 |
1 |
-2 |
3 |
|||||||
-42/5 |
-3/5 |
3 |
-6/5 |
9/5 |
|||||||||
Ф' |
112 |
35 |
-40 |
12 |
-25 |
||||||||
-98 |
-7 |
35 |
-14 |
21 |
b |
y2 |
y4 |
y5 |
y6 |
|||||||||
y1 |
14/5 |
1/5 |
-1 |
2/5 |
-3/5 |
||||||||
y3 |
3/5 |
-3/5 |
0 |
-1/5 |
-1/5 |
||||||||
Ф' |
14 |
-7 |
-5 |
-2 |
-4 |
||||||||
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
? |
? |
? |
? |
? |
? |
|
y5 |
y6 |
y1 |
y2 |
y3 |
y4 |
|
2 |
4 |
7 |
0 |
0 |
5 |
F' = Ф' = 14
X = (2,4,7,0,0,5)
F= -F' = -14
2.2 Задача целочисленного линейного программирования
2.2.1 Постановка задачи целочисленного линейного программирования
Решить ЗЦЛП, при условии целочисленности всех переменных, входящих в задачу, методом ветвей и границ и методом отсекающих плоскостей (методом Гомори).
2.2.2 Метод Гомори
x3, x4 - базисные переменные, x1, x2 - свободные переменные
? |
|||||||||
b |
x1 |
x2 |
|||||||
x3 |
11 |
2 |
3 |
11/2 |
|||||
-5 |
-1/2 |
-1/2 |
|||||||
? |
x4 |
10 |
4 |
1 |
10/4 |
||||
5/2 |
1/4 |
1/4 |
|||||||
F' |
0 |
2 |
1 |
||||||
-5 |
-1/2 |
-1/2 |
? |
|||||||||
b |
x4 |
x2 |
|||||||
? |
x3 |
6 |
-1/2 |
5/2 |
12/5 |
||||
12/5 |
-1/5 |
2/5 |
|||||||
x1 |
5/2 |
1/4 |
1/4 |
10 |
|||||
-3/5 |
1/20 |
-1/10 |
|||||||
F' |
-5 |
-1/2 |
1/2 |
||||||
-6/5 |
1/10 |
-1/5 |
b |
x1 |
x2 |
|||||||
x3 |
12/5 |
-1/5 |
2/5 |
||||||
x4 |
19/10 |
3/10 |
-1/10 |
||||||
F' |
-31/5 |
-2/5 |
-1/5 |
||||||
X = (19/10, 12/5, 0, 0)
F = -F' = 31/5
Составляем неравенство Гомори:
? |
|||||||||
b |
x4 |
x3 |
|||||||
F' |
-31/5 |
-2/5 |
-1/5 |
||||||
1/5 |
1/10 |
-1/2 |
|||||||
x2 |
12/5 |
-1/5 |
2/5 |
||||||
-2/5 |
-1/5 |
1 |
|||||||
x1 |
19/10 |
3/10 |
-1/10 |
||||||
1/10 |
-1/4 |
||||||||
? |
u2 |
-2/5 |
-1/5 |
-2/5 |
|||||
1 |
1/2 |
-5/2 |
b |
x4 |
u2 |
|||||||
F' |
-6 |
-3/10 |
-1/2 |
||||||
x2 |
2 |
-2/5 |
1 |
||||||
x1 |
2 |
7/20 |
-1/4 |
||||||
x3 |
1 |
1/2 |
-5/2 |
||||||
X = (2, 2, 1, 0)
F = -F' = 6
2.2.3 Метод ветвей и границ
b |
x1 |
x2 |
||
x3 |
12/5 |
-1/5 |
2/5 |
|
x4 |
19/10 |
3/10 |
-1/10 |
|
F' |
-31/5 |
-2/5 |
-1/5 |
Задача № 1
Приводим к каноническому виду:
x3, x4, x5 - базисные переменные, x1, x2 - свободные переменные
? |
|||||||||
b |
x1 |
x2 |
|||||||
x3 |
11 |
2 |
3 |
11/2 |
|||||
-5 |
-1/2 |
-1/2 |
|||||||
? |
x4 |
10 |
4 |
1 |
5/2 |
||||
5/2 |
1/4 |
1/4 |
|||||||
x5 |
2 |
0 |
1 |
||||||
0 |
0 |
0 |
|||||||
F' |
0 |
2 |
1 |
||||||
-5 |
-1/2 |
-1/2 |
? |
|||||||||
b |
x4 |
x2 |
|||||||
x3 |
6 |
-1/2 |
5/2 |
12/5 |
|||||
-5 |
0 |
-5/2 |
|||||||
x1 |
5/2 |
1/4 |
1/4 |
10 |
|||||
-1/2 |
0 |
-1/4 |
|||||||
? |
x5 |
2 |
0 |
1 |
2 |
||||
2 |
0 |
1 |
|||||||
F' |
-5 |
-1/2 |
1/2 |
||||||
-1 |
0 |
-1/2 |
b |
x4 |
x5 |
|||||||
x3 |
1 |
-1/2 |
-5/2 |
||||||
x1 |
2 |
1/4 |
-1/4 |
||||||
x2 |
2 |
0 |
1 |
||||||
F' |
-6 |
-1/2 |
-1/2 |
||||||
X = (2, 2, 1, 0, 0)
F' = -6
F = -F' = 6
Задача № 2
Решаем задачу с x2 = 3 в подсистеме «Поиск решения» системы Excel. Получаем допустимое не оптимальное решение F = 5, X = (1, 3)
=2*$B$1+$B$2 |
1 |
=2*$B$1+3*$B$2 |
11 |
|
3 |
=4*$B$1+$B$2 |
10 |
||
=$B$2 |
3 |
5 |
1 |
11 |
11 |
|
3 |
7 |
10 |
||
3 |
3 |
Ограничения |
|||||||
Ячейка |
Имя |
Значение |
Формула |
Статус |
Разница |
||
$C$1 |
|
11 |
$C$1<=$D$1 |
связанное |
0 |
||
$C$2 |
|
7 |
$C$2<=$D$2 |
не связан. |
3 |
||
$C$3 |
|
3 |
$C$3>=$D$3 |
связанное |
0 |
2.3 Задача целочисленного линейного программирования с булевскими переменными
2.3.1 Постановка задачи целочисленного линейного программирования с булевскими переменными
Составить самостоятельно вариант для задачи целочисленного линейного программирования с булевскими переменными с учетом следующих правил: в задаче используется не менее 5 переменных, не менее 4 ограничений, коэффициенты ограничений и целевой функции выбираются произвольно, но таким образом, чтобы система ограничений была совместна. Задание состоит в том, чтобы решить ЗЦЛП с булевскими переменными, используя алгоритм Баллаша и определить снижение трудоемкости вычислений по отношению к решению задачи методом полного перебора.
2.3.2 Метод Баллаша
№ |
x4 |
x3 |
x2 |
x1 |
x5 |
Выполнение ограничений |
Значение F |
||||||
0 |
1 |
2 |
3 |
4 |
5 |
||||||||
1 |
0 |
0 |
0 |
0 |
0 |
0 |
Fф=0 |
||||||
2 |
0 |
0 |
0 |
0 |
1 |
44 |
|||||||
3 |
0 |
0 |
0 |
1 |
0 |
17 |
|||||||
4 |
0 |
0 |
0 |
1 |
1 |
61 |
|||||||
5 |
0 |
0 |
1 |
0 |
0 |
13 |
|||||||
6 |
0 |
0 |
1 |
0 |
1 |
57 |
|||||||
7 |
0 |
0 |
1 |
1 |
0 |
30 |
|||||||
8 |
0 |
0 |
1 |
1 |
1 |
74 |
|||||||
9 |
0 |
1 |
0 |
0 |
0 |
-10 |
+ |
+ |
+ |
+ |
+ |
Fф=-10 |
|
10 |
0 |
1 |
0 |
0 |
1 |
34 |
|||||||
11 |
0 |
1 |
0 |
1 |
0 |
7 |
|||||||
12 |
0 |
1 |
0 |
1 |
1 |
51 |
|||||||
13 |
0 |
1 |
1 |
0 |
0 |
3 |
|||||||
14 |
0 |
1 |
1 |
0 |
1 |
47 |
|||||||
15 |
0 |
1 |
1 |
1 |
0 |
20 |
|||||||
16 |
0 |
1 |
1 |
1 |
1 |
64 |
|||||||
17 |
1 |
0 |
0 |
0 |
0 |
-49 |
+ |
+ |
+ |
+ |
+ |
Fф=-49 |
|
18 |
1 |
0 |
0 |
0 |
1 |
-5 |
|||||||
19 |
1 |
0 |
0 |
1 |
0 |
-32 |
|||||||
20 |
1 |
0 |
0 |
1 |
1 |
12 |
|||||||
21 |
1 |
0 |
1 |
0 |
0 |
-36 |
|||||||
22 |
1 |
0 |
1 |
0 |
1 |
8 |
|||||||
23 |
1 |
0 |
1 |
1 |
0 |
-19 |
|||||||
24 |
1 |
0 |
1 |
1 |
1 |
25 |
|||||||
25 |
1 |
1 |
0 |
0 |
0 |
-59 |
+ |
+ |
+ |
+ |
+ |
Fф=-59 |
|
26 |
1 |
1 |
0 |
0 |
1 |
-15 |
|||||||
27 |
1 |
1 |
0 |
1 |
0 |
-42 |
|||||||
28 |
1 |
1 |
0 |
1 |
1 |
2 |
|||||||
29 |
1 |
1 |
1 |
0 |
0 |
-46 |
|||||||
30 |
1 |
1 |
1 |
0 |
1 |
-2 |
|||||||
31 |
1 |
1 |
1 |
1 |
0 |
-29 |
|||||||
32 |
1 |
1 |
1 |
1 |
1 |
15 |
Фильтрующее ограничение:
2.3.3 Определение снижения трудоемкости вычислений
Решение задачи методом полного перебора составляет 6*25=192 вычисленных выражения. Решение задачи методом Баллаша составляет 3*6+(25-3)=47 вычисленных выражений. Итого снижение трудоемкости вычислений по отношению к решению задачи методом полного перебора составляет .
3 Нелинейное программирование
3.1 Задача поиска глобального экстремума функции
3.1.1 Постановка задачи поиска глобального экстремума функции
Необходимо написать программа для поиска экстремума функции. Задание состоит в следующем: 1) найти точку глобального экстремума функции f(X) методом поиска по координатной сетке с постоянным шагом; 2) найти точку глобального экстремума функции f(X) методом случайного поиска; 3)сравнить результаты вычислений.
3.1.2 Метод поиска по координатной сетке с постоянным шагом и метод случайного поиска. Сравнение результатов вычислений
Метод поиска глобального минимума, называемый методом поиска по координатной сетке, является надежным, но применим только для задач малой размерности (n<4). Неправильный выбор начального шага сетки может привести к тому, что в действительности один из локальных минимумов может быть принят как глобальный. Из всех значений целевой функции, вычисленных в узлах координатной сетки, выбирается минимальное. Результат: число испытаний 905, f(X*) = -2.500, X*=(-0.500; 2.000)
Метод случайного поиска характеризуется намеренным введением элемента случайности в алгоритм поиска. Этот метод предполагает наличие генератора случайных чисел, обращаясь к которому, в любой нужный момент времени можно получить реализацию случайного вектора с заданным законом распределения. Результат: число испытаний 299, f(X*) = -2.469, X*=(-0.677; 2.173).
Расчет в системе MathCAD: f(X*) = -2.500, X*=(-0.500; 2.000)
Как видим, метод случайного поиска сократил число испытаний на 66%, при этом относительная погрешность составляет 1%. Т.е. мы достигли значительного сокращения вычислений с небольшой относительной погрешностью.
3.2 Задача одномерной оптимизации функции
3.2.1 Постановка задачи одномерной оптимизации функции
Задание для нахождения одномерного локального экстремума функции (одномерная оптимизация) состоит в том, чтобы выполнить поиск минимума заданной функции методом дихотомии (3-4 итерации), уточнить интервал поиска методом Фибоначчи (3 итерации) и завершить поиск методом кубической аппроксимации.
3.2.2 Метод дихотомии
Итерация 1
Итерация 2
Итерация 3
Итерация 4
После четырех итераций получим:
3.2.3 Метод Фибоначчи
Итерация 1
Итерация 2
Итерация 3
Итерация 4
Поиск окончен. Длина интервала:
3.2.4 Метод кубической аппроксимации
3.3 Задача многомерной оптимизации функции
3.3.1 Постановка задачи многомерной оптимизации функции
Минимизировать функцию, применяя следующие методы: нулевого порядка - Хука-Дживса, первого порядка - наискорейшего спуска (Коши), второго порядка - Ньютона, и провести сравнительный анализ методов оптимизации по количеству итераций, необходимых для поиска экстремума при фиксированной точности и начальных координатах поиска X(0)=[-1,-1]T.
3.3.2 Метод Хука - Дживса
Итерация 1
1 Исследующий поиск
2 Поиск по образцу
Итерация 2
1 Исследующий поиск
2 Поиск по образцу
Итерация 3
1 Исследующий поиск
2 Поиск по образцу
Поиск завершен
3.3.3 Метод наискорейшего спуска (метод Коши)
Итерация 1. Счет итераций k = 0
Итерация 2. Счет итераций k = 1
Поиск завершен
3.3.4 Метод Ньютона
3.3.5 Сравнение результатов вычислений
Метод Хука-Дживса сходится за три итерации, при этом происходит вычисление значения функции в 13 точках, всего 38 вычислений. Метод наискорейшего спуска (метод Коши) сходится за одну итерацию, 9 вычислений. Метод Ньютона сходится за одну итерация, 9 вычислений. Методы Коши и Ньютона в данном случае сходятся за одну итерацию, поскольку функция представляет собой функцию для сферы (линии уровня - концентрические окружности) и направление, противоположное градиенту функции, направлено на точку минимума. Из этого можно сделать вывод, что в случае функций такого вида использование метода Хука-Дживса нерационально.
Заключение
Процесс проектирования информационных систем, реализующих новую информационную технологию, непрерывно совершенствуется. В центре внимания инженеров-системотехников оказываются все более сложные системы, что затрудняет использование физических моделей и повышает значимость математических моделей и машинного моделирования систем. Машинное моделирование стало эффективным инструментом исследования и проектирования сложных систем. Актуальность математических моделей непрерывно возрастает из-за их гибкости, адекватности реальным процессам, невысокой стоимости реализации на базе современных ПЭВМ. Все большие возможности предоставляются пользователю, т. е. специалисту по моделированию систем средствами вычислительной техники. Особенно эффективно применение моделирования на ранних этапах проектирования автоматизированных систем, когда цена ошибочных решений наиболее значительна.
Современные вычислительные средства позволили существенно увеличить сложность используемых моделей при изучении систем, появилась возможность построения комбинированных, аналитико-имитационных моделей, учитывающих все многообразие факторов, имеющих место в реальных системах, т. е. использованию моделей, более адекватных исследуемым явлениям.
Библиографический список
1 Лященко И.Н. Линейное и нелинейное программирования / И.Н.Лященко, Е.А.Карагодова, Н.В.Черникова, Н.З.Шор. - К.: «Высшая школа», 1975, 372 с.
2 Методические указания для выполнения курсового проекта по дисциплине «Прикладная математика» для студентов специальности «Компьютерные системы и сети» дневной и заочной форм обучения / Сост.: И.А.Балакирева, А.В.Скатков- Севастополь: Изд-во СевНТУ, 2003. - 15 с.
3 Методические указания по изучению дисциплины «Прикладная математика», раздел «Методы глобального поиска и одномерной минимизации» / Сост. А.В.Скатков, И.А.Балакирева, Л.А.Литвинова - Севастополь: Изд-во СевГТУ, 2000. - 31с.
4 Методические указания для изучения дисциплины «Прикладная математика» для студентов специальности «Компьютерные системы и сети» Раздел «Решение задач целочисленного линейного программирования» дневной и заочной форм обучения / Сост.: И.А.Балакирева, А.В.Скатков - Севастополь: Изд-во СевНТУ, 2000. - 13 с.
ПРИЛОЖЕНИЕ
А Текст программы глобальной многомерной оптимизации
{$APPTYPE CONSOLE}
program GlobalMinimize;
const
large = 10e99;
var
a1, a2, b1, b2 : real;
a1n, a2n, b1n, b2n : real;
fmin, x1, x2 : real;
alpha, dV, eps : real;
Rho, P : real;
fT, fS : real;
d1, d2, dx1, dx2 : real;
x1min, x2min : real;
i, N : integer;
t : boolean;
function f(x1, x2 : real) : real;
begin
f := 2*sqr(x1) + 2*x1*x2 + sqr(x2) - 2*x1 - 3*x2
end;
function ceil(x : real) : integer;
var a : integer;
begin
a := trunc(x);
if frac(x) > 0 then
a := a + 1;
ceil := a
end;
function max(a, b : real) : real;
begin
if a > b then
max := a
else
max := b
end;
function min(a, b : real) : real;
begin
if a < b then
min := a
else
min := b
end;
begin
randomize;
writeln('Поиск глобального многомерного минимума функции');
writeln('(для курсового проекта по прикладной математике)');
writeln('Автор: Ткаченко К.С. М-21д');
writeln;
writeln('Введите интервал изменения x1');
write(' Введите a1 : '); readln(a1);
write(' Введите b1 : '); readln(b1);
writeln('Введите интервал изменения x2');
write(' Введите a2 : '); readln(a2);
write(' Введите b2 : '); readln(b2);
write('Введите погрешность eps : '); readln(eps);
write('Введите вероятность поиска P : '); readln(P);
write('Введите коэффициент alpha : '); readln(alpha);
write('Введите коэффициент dV : '); readln(dV);
writeln;
writeln('Алгоритм поиска глобального минимума по координатной '+
'сетке с равномерным шагом');
writeln;
t := false; N := 0;
fS := large; fmin := large;
a1n := a1; a2n := a2; b1n := b1; b2n := b2;
repeat
d1 := b1n - a1n; d2 := b2n - a2n;
dx1 := d1 / alpha; dx2 := d2 / alpha;
x1 := a1n; x2 := a2n;
fT := f(x1, x2);
N := N + 1;
if fT < fmin then
begin
fmin := fT;
x1min := x1; x2min := x2;
end;
repeat
repeat
x1 := x1 + dx1; (* Шаг 1 *)
fT := f(x1, x2);
N := N + 1;
if fT < fmin then (* Шаг 2 *)
begin
fmin := fT;
x1min := x1; x2min := x2;
end;
until x1 > b1n; (* Шаг 3 *)
x1 := a1n; x2 := x2 + dx2; (* Шаг 4 *)
fT := f(x1, x2); (* Шаг 5 *)
N := N + 1;
if fT < fmin then (* Шаг 6 *)
begin
fmin := fT;
x1min := x1; x2min := x2;
end;
until x2 > b2n; (* Шаг 7 *)
if abs(fS - fmin) > eps then (* Шаг 8 *)
begin (* Шаг 9 *)
fS := fmin;
a1n := max(x1min-dx1,a1n); b1n := min(x1min+dx1,b1n);
a2n := max(x2min-dx2,a2n); b2n := min(x2min+dx2,b2n);
end
else t := true; (* Шаг 10 *)
until t;
writeln('Число испытаний N = ', N);
writeln('fmin = ', fmin : 6 : 3);
writeln('x1min = ', x1min : 6 : 3);
writeln('x2min = ', x2min : 6 : 3);
writeln;
writeln('Алгоритм поиска глобального минимума функции '+
'методом случайного поиска');
writeln;
fmin := large;
x1min := fmin; x2min := fmin;
d1 := b1 - a1; d2 := b2 - a2;
Rho := dV/(d1 * d2);
N := ceil(ln(1 - P)/ln(1 - Rho));
writeln('Число испытаний N = ', N);
for i := 1 to N do (* Шаги 1, 2 *)
begin
x1 := a1 + random * d1; (* Шаги 3, 4 *)
x2 := a2 + random * d2;
fT := f(x1, x2); (* Шаг 5 *)
if fT < fmin then (* Шаг 6 *)
begin
fmin := fT;
x1min := x1;
x2min := x2
end;
end; (* Шаг 7 *)
writeln('fmin = ', fmin : 6 : 3);
writeln('x1min = ', x1min : 6 : 3);
writeln('x2min = ', x2min : 6 : 3);
end.
Б. Результаты работы программы
Поиск глобального многомерного минимума функции
(для курсового проекта по прикладной математике)
Автор: Ткаченко К.С. М-21д
Введите интервал изменения x1
Введите a1 : -5
Введите b1 : 5
Введите интервал изменения x2
Введите a2 : -5
Введите b2 : 5
Введите погрешность eps : 0.0001
Введите вероятность поиска P : 0.95
Введите коэффициент alpha : 20
Введите коэффициент dV : 1
Алгоритм поиска глобального минимума по координатной сетке с равномерным шагом
Число испытаний N = 905
fmin = -2.500
x1min = -0.500
x2min = 2.000
Алгоритм поиска глобального минимума функции методом случайного поиска
Число испытаний N = 299
fmin = -2.469
x1min = -0.677
x2min = 2.173
Подобные документы
Линейная производственная задача. Двойственная задача. Задача о "Расшивке узких мест производства". Транспортная задача. Распределение капитальных вложений. Динамическая задача управления запасами. Анализ доходности и риска.
курсовая работа [530,4 K], добавлен 29.05.2006Определение допустимого решения задачи линейного программирования методом введения искусственного базиса. Целочисленное линейное программирование с булевскими переменными. Поиск минимума функции методом градиентного спуска. Одномерная минимизация.
курсовая работа [281,7 K], добавлен 27.05.2013Задача целочисленного линейного программирования, приведение к канонической форме. Общие идеи методов отсечения. Алгоритм Гомори для решения целочисленных задач линейного программирования. Понятие правильного отсечения и простейший способ его построения.
курсовая работа [67,5 K], добавлен 25.11.2011Поиск экстремума функций при наличии ограничений типа неравенств; история возникновения, становления и перспективы линейного программирования. Практическое применение методов Канторовича. Количество информации и требования к коммуникационным системам.
реферат [30,5 K], добавлен 18.01.2014Сущность линейного программирования. Изучение математических методов решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейной целевой функцией. Нахождение точек наибольшего или наименьшего значения функции.
реферат [162,8 K], добавлен 20.05.2019Теория математического программирования. Методы поиска глобального экстремума функции нескольких переменных. Угловые точки допустимых множеств. Постановка общей задачи нелинейного программирования. Решения уравнения f(x)=0 методом простой итерации.
контрольная работа [775,4 K], добавлен 05.01.2013История зарождения и создания линейного программирования. Транспортная задача. Общая постановка, цели, задачи. Основные типы, виды моделей. Методы составления начального опорного плана. Понятие потенциала и цикла. Задача, двойственная к транспортной.
курсовая работа [166,7 K], добавлен 17.07.2002Графическое решение задачи линейного программирования. Общая постановка и решение двойственной задачи (как вспомогательной) М-методом, правила ее формирования из условий прямой задачи. Прямая задача в стандартной форме. Построение симплекс таблицы.
задача [165,3 K], добавлен 21.08.2010Обыкновенные и модифицированные жордановы исключения. Последовательность решения задач линейного программирования симплекс-методом применительно к задаче максимизации: составлении опорного плана решения, различные преобразования в симплекс-таблице.
курсовая работа [37,2 K], добавлен 01.05.2011Понятие линейного программирования и его основные методы. Формулировка задачи линейного программирования в матричной форме и ее решение различными методами: графическим, табличным, искусственного базиса. Особенности решения данной задачи симплекс-методом.
курсовая работа [65,3 K], добавлен 30.11.2010