Реферат: Построение и исследование математической модели для задачи линейного программирования

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИУКРАИНЫ

Севастопольский национальныйтехнический университет

Кафедра кибернетики и вычислительнойтехники

Пояснительная записка

к курсовому проекту

по дисциплине

«Прикладная математика»

Выполнил:ст. гр. М-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