2
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ
Севастопольский национальный технический университет
Кафедра кибернетики и вычислительной техники
Пояснительная записка
к курсовому проекту
по дисциплине
«Прикладная математика»
Выполнил: ст. гр. М-21д
Ткаченко К. С.
зач. книжка № 040xxx
вариант № 22
Проверил: ст. преп.
Балакирева И. А.
Севастополь - 2006
Содержание
Введение
Современный этап развития человечества отличается тем, что на смену века энергетики приходит век информатики. Происходит интенсивное внедрение новых технологий во все сферы человеческой деятельности. Встает реальная проблема перехода в информационное общество, для которого приоритетным должно стать развитие образования. Изменяется и структура знаний в обществе. Все большее значение для практической жизни приобретают фундаментальные знания, способствующие творческому развитию личности. Важна и конструктивность приобретаемых знаний, умение их структурировать в соответствии с поставленной целью. На базе знаний формируются новые информационные ресурсы общества. Формирование и получение новых знаний должно базироваться на строгой методологии системного подхода, в рамках которого отдельное место занимает модельный подход. Возможности модельного подхода крайне многообразны как по используемым формальным моделям, так и по способам реализации методов моделирования. Физическое моделирование позволяет получить достоверные результаты для достаточно простых систем.
В настоящее время нельзя назвать область человеческой деятельности, в которой в той или иной степени не использовались бы методы моделирования. Особенно это относится к сфере управления различными системами, где основными являются процессы принятия решений на основе получаемой информации.
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 |
| ! | Как писать курсовую работу Практические советы по написанию семестровых и курсовых работ. |
| ! | Схема написания курсовой Из каких частей состоит курсовик. С чего начать и как правильно закончить работу. |
| ! | Формулировка проблемы Описываем цель курсовой, что анализируем, разрабатываем, какого результата хотим добиться. |
| ! | План курсовой работы Нумерованным списком описывается порядок и структура будующей работы. |
| ! | Введение курсовой работы Что пишется в введении, какой объем вводной части? |
| ! | Задачи курсовой работы Правильно начинать любую работу с постановки задач, описания того что необходимо сделать. |
| ! | Источники информации Какими источниками следует пользоваться. Почему не стоит доверять бесплатно скачанным работа. |
| ! | Заключение курсовой работы Подведение итогов проведенных мероприятий, достигнута ли цель, решена ли проблема. |
| ! | Оригинальность текстов Каким образом можно повысить оригинальность текстов чтобы пройти проверку антиплагиатом. |
| ! | Оформление курсовика Требования и методические рекомендации по оформлению работы по ГОСТ. |
| → | Разновидности курсовых Какие курсовые бывают в чем их особенности и принципиальные отличия. |
| → | Отличие курсового проекта от работы Чем принципиально отличается по структуре и подходу разработка курсового проекта. |
| → | Типичные недостатки На что чаще всего обращают внимание преподаватели и какие ошибки допускают студенты. |
| → | Защита курсовой работы Как подготовиться к защите курсовой работы и как ее провести. |
| → | Доклад на защиту Как подготовить доклад чтобы он был не скучным, интересным и информативным для преподавателя. |
| → | Оценка курсовой работы Каким образом преподаватели оценивают качества подготовленного курсовика. |
| Курсовая работа | Деятельность Движения Харе Кришна в свете трансформационных процессов современности |
| Курсовая работа | Маркетинговая деятельность предприятия (на примере ООО СФ "Контакт Плюс") |
| Курсовая работа | Политический маркетинг |
| Курсовая работа | Создание и внедрение мембранного аппарата |
| Курсовая работа | Социальные услуги |
| Курсовая работа | Педагогические условия нравственного воспитания младших школьников |
| Курсовая работа | Деятельность социального педагога по решению проблемы злоупотребления алкоголем среди школьников |
| Курсовая работа | Карибский кризис |
| Курсовая работа | Сахарный диабет |
| Курсовая работа | Разработка оптимизированных систем аспирации процессов переработки и дробления руд в цехе среднего и мелкого дробления Стойленского ГОКа |