МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ, МОЛОДЕЖИ И СПОРТА УКРАИНЫ
СЕВАСТОПОЛЬСКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСТИТЕТ
Кафедра кибернетики и вычислительной техники
Пояснительная записка
к курсовой работе по дисциплине
"Прикладная математика"
Выполнила:
Студентка гр. М –22д
Чернокуцатова С.А
№ зачётной книжки:
100908(Вариант 19)
Севастополь
2012
Содержание
Введение ..3
1. Линейное программирование ....4
1.1. Построение математической модели ЗЛП ....4
1.2. Решение ЗЛП графическим методом ....5
1.3. Решение ЗЛП алгебраическим методом ....6
1.4. Решение ЗЛП симплекс – методом ....8
1.5. Решение ЗЛП методом искусственного базиса ....10
2. Решение ЗЦЛП методом Гомори ....13
3. Булевское программирование. Метод Баллаша. ....18
4. Поиск глобального экстремума функции… ....20
4.1. Метод Хука – Дживса ....20
4.2. Метод градиентного спуска с поятоянным шагом ....26
5. Одномерная минимизация…. ....27
6. Дополнительное задание. ....32
Заключение. ....39
Список используемой литературы…. ....40
Введение
В последние годы все большее значение приобретает математический подход к задачам планирования.
Первые работы в этом направлении были сделаны в России ещё в 1937 году. Основной задачей математического планирования в то время была “Оптимизация перевозки угля к узлам реализации за минимальную цену”. Первым её рассматривал русский учёный Л.В. Контарович, авторство которого получило мировое признание.
C помощью методов прикладной математики (в частности линейного программирования) решаются такие проблемы, как оптимизация транспортных перевозок, задача о наилучшем использовании сырья, наилучшем плане работы вычислительного комплекса, и многие другие задачи. Решение этих задач позволит значительно снизить экономические затраты на реализацию и эксплуатацию соответствующих проектов. Таким образом, задачи прикладной математики имеют самое обширное применение в жизни.
В данной курсовой работе необходимо решить ряд вышеописанных задач, используя методы линейного программирования и безусловной оптимизации. Так же в дополнительном задании для решения задачи используется программа Excel.
1. Линейное программирование
1.1. Построение математической модели злп
P
Восстанавливаем ограничения по графику:
AB (0,2) (0,5) x1 = 0
BC (0,5) (5,2)
-3x1
= 5x2
-25
Для определения знака неравенства, возьмем точку внутри области (2;2).
Получим,
-6 
-15 следовательно: -3x1
- 5x2
+ 25
0
CD (5,2) (3,0)
-2x1
+ 10 = -2x2
+ 4
Для определения знака неравенства, возьмем точку внутри области (2;2).
Получим, 6 0 следовательно: -2x1 + 2x2 + 6 0
DE (3,0) (1,1)
x1
– 3 = - 2x2
Для определения знака неравенства, возьмем точку внутри области (2;2).
Получим, - 1 - 4 следовательно: x1 + 2x2 – 3 0
EA (1,1) (0,2)
x1
– 1 = - x2 +1
Для определения знака неравенства, возьмем точку внутри области (2;2).
Получим, 1 - 1 следовательно: x1 + x2 – 2 0
Получим уравнение целевой функции:
ЦФ (4,2)(3,0)
-2x1 + 8 = - x2 + 2
F = - 2x1 + x2 = - 6
Делаем вывод, что целевая функция принадлежит к семейству прямых, которые описываются уравнением: F = - 2x1 + x2
Для
определения того, что надо искать минимум
или максимум строим градиент функции
(то есть берем частные производные по
х1,
х2):
Так как направление градиента противоположено с направлением, указанным стрелкой, то это значит, что мы должны двигаться в сторону, противоположную градиента функции, а значит, мы должны искать минимум функции, то есть
Запишем ограничения в виде системы неравенств:
F = - 2x1 + x2 min
-3x1 - 5x2 + 25 0
-2x1 + 2x2 + 6 0
x1 + 2x2 – 3 0
x1 + x2 – 2 0
F = - 2x1 + x2 min