Реферат: Построение и исследование математической модели для задачи линейного программирования
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИУКРАИНЫ
Севастопольский национальныйтехнический университет
Кафедра кибернетики и вычислительнойтехники
Пояснительная записка
к курсовому проекту
по дисциплине
«Прикладная математика»
Выполнил:ст. гр. М-21д
ТкаченкоК. С.
зач.книжка № 040xxx
вариант№ 22
Проверил:ст. преп.
БалакиреваИ. А.
Севастополь – 2006
<span Times New Roman",«serif»; mso-fareast-font-family:«Times New Roman»;mso-ansi-language:RU;mso-fareast-language: RU;mso-bidi-language:AR-SA">Содержание
TOC o «1-3» h z u Введение. PAGEREF _Toc135182657 h 4
1 Общая формулировка задания на курсовой проект. PAGEREF _Toc135182658 h 5
2 Линейное программирование. PAGEREF _Toc135182659 h 7
2.1 Задача линейного программирования. PAGEREF _Toc135182660 h 7
2.1.1 Постановка задачи линейногопрограммирования. PAGEREF _Toc135182661 h 7
2.1.2 Математическая модель задачи линейногопрограммирования. PAGEREF _Toc135182662 h 8
2.1.3 Графический метод. PAGEREF _Toc135182663 h 9
2.1.4 Алгебраический метод. PAGEREF _Toc135182664 h 10
2.1.5 Метод симплекс-таблицы… PAGEREF _Toc135182665 h 12
2.1.6 Метод допустимого базиса. PAGEREF _Toc135182666 h 14
2.1.7 Решение двойственной задачи. PAGEREF _Toc135182667 h 17
2.2 Задача целочисленного линейногопрограммирования. PAGEREF _Toc135182668 h 19
2.2.1 Постановка задачи целочисленного линейногопрограммирования. PAGEREF _Toc135182669 h 19
2.2.2 Метод Гомори. PAGEREF _Toc135182670 h 20
2.2.3 Метод ветвей и границ. PAGEREF _Toc135182671 h 22
2.3 Задача целочисленного линейногопрограммирования с булевскими переменными PAGEREF _Toc135182672 h 24
2.3.1 Постановка задачи целочисленного линейногопрограммирования с булевскими переменными. PAGEREF _Toc135182673 h 24
2.3.2 Метод Баллаша. PAGEREF _Toc135182674 h 25
2.3.3 Определение снижения трудоемкостивычислений. PAGEREF _Toc135182675 h 26
3 Нелинейное программирование. PAGEREF _Toc135182676 h 27
3.1 Задача поиска глобального экстремума функции. PAGEREF _Toc135182677 h 27
3.1.1 Постановка задачи поиска глобальногоэкстремума функции. PAGEREF _Toc135182678 h 27
3.1.2 Метод поиска по координатной сетке спостоянным шагом и метод случайного поиска. Сравнение результатов вычислений. PAGEREF _Toc135182679 h 28
3.2 Задача одномерной оптимизации функции. PAGEREF _Toc135182680 h 29
3.2.1 Постановка задачи одномерной оптимизациифункции. PAGEREF _Toc135182681 h 29
3.2.2 Метод дихотомии. PAGEREF _Toc135182682 h 30
3.2.3 Метод Фибоначчи. PAGEREF _Toc135182683 h 31
3.2.4 Метод кубической аппроксимации. PAGEREF _Toc135182684 h 32
3.3 Задача многомерной оптимизации функции. PAGEREF _Toc135182685 h 33
3.3.1 Постановка задачи многомерной оптимизациифункции. PAGEREF _Toc135182686 h 33
3.3.2 Метод Хука – Дживса. PAGEREF _Toc135182687 h 34
3.3.3 Метод наискорейшего спуска (метод Коши)PAGEREF _Toc135182688 h 36
3.3.4 Метод Ньютона. PAGEREF _Toc135182689 h 37
3.3.5 Сравнение результатов вычислений. PAGEREF _Toc135182690 h 38
Заключение. PAGEREF _Toc135182691 h 39
Библиографический список. PAGEREF _Toc135182692 h 40
ПРИЛОЖЕНИЕ. PAGEREF _Toc135182693 h 41
А Текст программы глобальной многомернойоптимизации. PAGEREF _Toc135182694 h 41
Б. Результаты работы программы… PAGEREF _Toc135182695 h 44
<span Arial",«sans-serif»; mso-fareast-font-family:«Times New Roman»;mso-font-kerning:16.0pt;mso-ansi-language: RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">
Введение
Современный этап развития человечества отличается тем, что на сменувека энергетики приходит век информатики. Происходит интенсивное внедрениеновых технологий во все сферы человеческой деятельности. Встает реальная проблемаперехода в информационное общество, для которого приоритетным должно статьразвитие образования. Изменяется и структура знаний в обществе. Все большеезначение для практической жизни приобретают фундаментальные знания,способствующие творческому развитию личности. Важна и конструктивностьприобретаемых знаний, умение их структурировать в соответствии с поставленнойцелью. На базе знаний формируются новые информационные ресурсы общества.Формирование и получение новых знаний должно базироваться на строгойметодологии системного подхода, в рамках которого отдельное место занимаетмодельный подход. Возможности модельного подхода крайне многообразны как поиспользуемым формальным моделям, так и по способам реализации методовмоделирования. Физическое моделирование позволяет получить достоверныерезультаты для достаточно простых систем.
В настоящее время нельзя назвать область человеческой деятельности,в которой в той или иной степени не использовались бы методы моделирования.Особенно это относится к сфере управления различными системами, где основнымиявляются процессы принятия решений на основе получаемой информации.
<span Arial",«sans-serif»; mso-fareast-font-family:«Times New Roman»;mso-font-kerning:16.0pt;mso-ansi-language: RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">
1 Общая формулировка задания на курсовойпроект
Вариант задания для задачи линейного программирования (ЗЛП) представляетсобой область допустимых решений ЗЛП и целевую функцию. Для того чтобыопределить, какое значение должна достигать целевая функция – минимальное илимаксимальное, необходимо найти градиент целевой функции. Если направлениеградиента совпадает с направлением стрелки у целевой функции в вариантезадания, то в задаче определяется максимальное значение целевой функции, иначе– минимальное.
Итак, задание по решению ЗЛП состоит в следующем: построитьматематическую модель ЗЛП согласно варианту; получить решение ЗЛП графическим методом;решить ЗЛП алгебраическим методом; решить ЗЛП методом симплекс-таблицы; определитьдопустимое решение ЗЛП методом введения искусственного базиса; построить ЗЛП,двойственную данной, решить эту задачу и исследовать взаимосвязь междурешениями взаимодвойственных задач.
Вариант для задачи целочисленного линейного программирования (ЗЦЛП)представляет собой область допустимых решений ЗЛП и целевую функцию. Заданиесостоит в следующем: решить ЗЦЛП, при условии целочисленности всех переменных,входящих в задачу методом ветвей и границ и методом отсекающих плоскостей(методом Гомори).
Вариант для задачи целочисленного линейного программирования сбулевскими переменными составляется студентом самостоятельно с учетом следующихправил: в задаче используется не менее 5 переменных, не менее 4 ограничений,коэффициенты ограничений и целевой функции выбираются произвольно, но такимобразом, чтобы система ограничений была совместна. Задание состоит в том, чтобырешить ЗЦЛП с булевскими переменными, используя алгоритм Баллаша и определитьснижение трудоемкости вычислений по отношению к решению задачи методом полногоперебора.
Задание на поиск глобального экстремума функции состоит в написаниипрограммы. Программа для поиска экстремума функции может быть разработана на любомалгоритмическом языке. Задание состоитв следующем: 1) найти точку глобального экстремума функции f(X)методом поиска по координатной сетке с постоянным шагом; 2) найти точкуглобального экстремума функции f(X)методом случайного поиска; 3)сравнить результатывычислений.
Задание для нахождения одномерного локального экстремума функции(одномерная оптимизация) состоит в том, чтобы выполнить поиск минимума заданнойфункции методом дихотомии (3-4 итерации), уточнить интервал поиска методомФибоначчи (3 итерации) и завершить поиск методом кубической аппроксимации.
Задание для нахождения многомерного локального экстремума функции(многомерная оптимизация) состоит в том, чтобы минимизировать функцию, применяяследующие методы: нулевого порядка – Хука-Дживса, первого порядка –наискорейшего спуска (Коши), второго порядка – Ньютона, и провестисравнительный анализ методов оптимизации по количеству итераций, необходимыхдля поиска экстремума при фиксированной точности и начальных координатах поискаX(0)=[-1,-1]T.
<span Arial",«sans-serif»; mso-fareast-font-family:«Times New Roman»;mso-font-kerning:16.0pt;mso-ansi-language: RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">
2 Линейное программирование
2.1 Задача линейного программирования
2.1.1 Постановка задачи линейногопрограммирования
Построить математическую модель ЗЛП согласно варианту. Получитьрешение ЗЛП графическим методом. Решить ЗЛП алгебраическим методом. Решить ЗЛПметодом симплекс-таблицы. Определить допустимое решение ЗЛП методом введенияискусственного базиса. Построить ЗЛП, двойственную данной, решить эту задачу иисследовать взаимосвязь между решениями взаимодвойственных задач.
<span Arial",«sans-serif»; mso-fareast-font-family:«Times New Roman»;mso-ansi-language:RU;mso-fareast-language: RU;mso-bidi-language:AR-SA">
2.1.2 Математическая модель задачи линейногопрограммирования
AB: <img src="/cache/referats/22045/image002.gif" v:shapes="_x0000_i1025"><img src="/cache/referats/22045/image004.gif" v:shapes="_x0000_i1026"><img src="/cache/referats/22045/image006.gif" v:shapes="_x0000_i1027">
<img src="/cache/referats/22045/image008.gif" v:shapes="_x0000_i1028">
BC: <img src="/cache/referats/22045/image010.gif" v:shapes="_x0000_i1029"><img src="/cache/referats/22045/image012.gif" v:shapes="_x0000_i1030"><img src="/cache/referats/22045/image014.gif" v:shapes="_x0000_i1031">
<img src="/cache/referats/22045/image016.gif" v:shapes="_x0000_i1032">
CD: <img src="/cache/referats/22045/image018.gif" v:shapes="_x0000_i1033"><img src="/cache/referats/22045/image020.gif" v:shapes="_x0000_i1034"><img src="/cache/referats/22045/image022.gif" v:shapes="_x0000_i1035">
<img src="/cache/referats/22045/image024.gif" v:shapes="_x0000_i1036">
DE: <img src="/cache/referats/22045/image026.gif" v:shapes="_x0000_i1037"><img src="/cache/referats/22045/image028.gif" v:shapes="_x0000_i1038"><img src="/cache/referats/22045/image030.gif" v:shapes="_x0000_i1039">
<img src="/cache/referats/22045/image032.gif" v:shapes="_x0000_i1040">
F: <img src="/cache/referats/22045/image034.gif" v:shapes="_x0000_i1041"><img src="/cache/referats/22045/image036.gif" v:shapes="_x0000_i1042"><img src="/cache/referats/22045/image038.gif" v:shapes="_x0000_i1043">
<img src="/cache/referats/22045/image040.gif" v:shapes="_x0000_i1044">
Математическаямодель:
<img src="/cache/referats/22045/image042.gif" v:shapes="_x0000_i1045">
<span Arial",«sans-serif»; mso-fareast-font-family:«Times New Roman»;mso-ansi-language:RU;mso-fareast-language: RU;mso-bidi-language:AR-SA">2.1.3 Графический метод
Вычисляем значение целевой функции во всех вершинах симплекса ивыбираем из них наименьшее. Это и будет оптимальное решение.
FA= 1
FB= -8
FC = -14
FD= 0
FE= 3
C(2, 4)
<img src="/cache/referats/22045/image044.gif" v:shapes="_x0000_i1046">
F = -14
<span Arial",«sans-serif»; mso-fareast-font-family:«Times New Roman»;mso-ansi-language:EN-US;mso-fareast-language: RU;mso-bidi-language:AR-SA">
2.1.4 Алгебраический метод
<img src="/cache/referats/22045/image046.gif" v:shapes="_x0000_i1047">
<img src="/cache/referats/22045/image048.gif" v:shapes="_x0000_i1048">
x2, x4, x5, x6 – базисные переменные, x1, x3– свободные переменные
<img src="/cache/referats/22045/image050.gif" v:shapes="_x0000_i1049">
x1↑F↑ x3↑F↓ Выбираем x3↔ x4
x2, x3, x5, x6 – базисные переменные, x1, x4– свободные переменные
<img src="/cache/referats/22045/image052.gif" v:shapes="_x0000_i1050">
x1↑F↓ x4↑F↑ Выбираем x1↔ x5
x1, x2, x3, x6 — базисные переменные, x4, x5– свободные переменные
<img src="/cache/referats/22045/image054.gif" v:shapes="_x0000_i1051">
x1↑F↑ x4↑F↑
X=(2, 4, 7,0, 0, 5)
F = -14
<img src="/cache/referats/22045/image044.gif" v:shapes="_x0000_i1052">
<span Arial",«sans-serif»; mso-fareast-font-family:«Times New Roman»;mso-ansi-language:RU;mso-fareast-language: RU;mso-bidi-language:AR-SA">2.1.5 Метод симплекс-таблицы
<img src="/cache/referats/22045/image046.gif" v:shapes="_x0000_i1053">
<img src="/cache/referats/22045/image056.gif" v:shapes="_x0000_i1054">
Приведем кканоническому виду:
x2, x4, x5, x6– базисные переменные, x1, x3– свободные переменные
<img src="/cache/referats/22045/image058.gif" v:shapes="_x0000_i1055">
↑
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
1
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
1
F
-14
-3/5
-14/5
X = (2, 4,7, 0, 0, 5)
F = -14 <img src="/cache/referats/22045/image059.gif" v:shapes="_x0000_i1056">
<span Arial",«sans-serif»; mso-fareast-font-family:«Times New Roman»;mso-ansi-language:RU;mso-fareast-language: RU;mso-bidi-language:AR-SA">2.1.6 Метод допустимого базиса
<img src="/cache/referats/22045/image056.gif" v:shapes="_x0000_i1057">
<img src="/cache/referats/22045/image061.gif" v:shapes="_x0000_i1058">
<img src="/cache/referats/22045/image063.gif" v:shapes="_x0000_i1059">
<img src="/cache/referats/22045/image065.gif" v:shapes="_x0000_i1060">
<img src="/cache/referats/22045/image067.gif" v:shapes="_x0000_i1061">
<img src="/cache/referats/22045/image069.gif" v:shapes="_x0000_i1062">
↑
b
x1
x2
x3
x4
x5
x6
F
-1
4
1/2
1/2
1/2
-1/2
←
ξ1
1
2
1
-1
1/2
1/2
1/2
1/2
-1/2
ξ2
2
-1
1
1
14/3
1/2
1/2
1/2
-1/2
ξ3
14
3
2
1
3
-3/2
-3/2
-3/2
3/2
ξ4
3
1
-1
1
-1/2
-1/2
-1/2
1/2
f
20
5
3
-1
1
1
1
-5/2
-5/2
-5/2
5/2
↑
b
ξ1
x2
x3
x4
x5
x6
F
1/2
1/2
9/2
-1/2
5/2
-1/2
-3/2
1
1
x1
1/2
1/2
1/2
-1/2
5/2
-1/2
-3/2
1