Содержани

Введение 5

1.Оптимизационные задачи, их классификация 7

1.1Классификация задач оптимизации 7

1.2Классификация методов оптимизации 12

2. Постановка задачи линейного программирования 13

2.1 Общая задача линейного программирования (ЗЛП) 13

2.2 Математические модели задач линейного программирования 14

2.3 Формы записи задач линейного программирования: общая, каноническая и стандартная 17

3. Графический метод решения задачи линейного программирования 20

4. Симплекс- метод решения задач линейного программирования 25

4.1 Метод Жордана – Гаусса - метод решения систем линейных уравнений 25

4.2. Симплексные таблицы. Нахождение начального опорного решения 31

4.3. Критерий оптимальности 34

4.4. Невырожденные ЗЛП, алгоритм их решения 34

4.5. Альтернативный оптимум, алгоритм нахождения всех оптимальных решений 41

4.6. Вырожденные ЗЛП, алгоритм их решения 46

5. Двойственные задачи 48

5.1 Постановка двойственной задачи 48

5.2 Основное неравенство двойственности 53

5.3 Критерий Канторовича 54

5.4 Первая теорема двойственности 55

5.5. Вторая теорема двойственности 55

(необходимое и достаточное условия оптимальности решения). 55

5.6. Третья теорема двойственности 56

5.7. Двойственный симплекс-метод 59

6. Транспортная задача 63

6.1 Экономическая постановка и математическая модель транспортной задачи 63

6.2 Методы нахождения начального плана перевозок 66

6.3 Метод потенциалов решения транспортной задачи 68

6.4 Открытая модель транспортной задачи 78

7. Матричные игры, их применение к решению оптимизационных задач 82

7.1 Основные понятия теории матричных игр 82

7.2 Решение матричных игр в чистых стратегиях 85

7.3 Решение матричной игры в смешанных стратегиях 88

7.4 Сведение матричной игры к задаче линейного программирования 93

7.5 Статистические игры 97

8. Графы, их применение в решение оптимизационных задач 105

8.1 Определение графа 105

8.2 Путь и цикл в графе 107

8.3 Связность графа, деревья 109

8.4 Виды графов 110

8.5 Сети. Критический путь 115

Вопросы к экзамену 121

Индивидуальные задания 124

ТЕСТЫ 145

Библиографический список 151

Введение 4

1. Оптимизационные задачи, их классификация 6

1.1 Классификация задач оптимизации 6

1.2 Классификация методов оптимизации 10

2. Постановка задачи линейного программирования 11

2.1 Общая задача линейного программирования (ЗЛП) 11

2.2 Математические модели задач линейного программирования 12

2.3 Формы записи задач линейного программирования: общая, каноническая и стандартная 15

3. Графический метод решения задачи линейного программирования 17

4. Симплекс- метод решения задач линейного программирования 23

4.1 Метод Жордана – Гаусса - метод решения систем линейных уравнений 23

4.2. Симплексные таблицы. Нахождение начального опорного решения 28

4.3. Критерий оптимальности 31

4.4. Невырожденные ЗЛП, алгоритм их решения 32

4.5. Альтернативный оптимум, алгоритм нахождения всех оптимальных решений 38

4.6. Вырожденные ЗЛП, алгоритм их решения 42

5. Двойственные задачи 44

5.1 Постановка двойственной задачи44

5.2 Основное неравенство двойственности49

5.3 Критерий Канторовича 50

5.4 Первая теорема двойственности 50

5.5. Вторая теорема двойственности 50

(необходимое и достаточное условия оптимальности решения). 50

5.6. Третья теорема двойственности 51

5.7. Двойственный симплекс-метод 53

6. Транспортная задача 57

6.1 Экономическая постановка и математическая модель транспортной задачи57

6.2 Методы нахождения начального плана перевозок 60

6.3 Метод потенциалов решения транспортной задачи 62

6.4 Открытая модель транспортной задачи 70

7. Матричные игры, их применение к решению оптимизационных задач72

7.1 Основные понятия теории матричных игр72

7.2 Решение матричных игр в чистых стратегиях76

7.3 Решение матричной игры в смешанных стратегиях79

7.4 Сведение матричной игры к задаче линейного программирования84

7.5 Статистические игры87

8. Графы, их применение в решение оптимизационных задач95

8.1 Определение графа95

8.2 Путь и цикл в графе 97

8.3 Связность графа, деревья98

8.4 Виды графов100

8.5 Сети. Критический путь105

Вопросы к экзамену 111

Индивидуальные задания 114

ТЕСТЫ 131

Библиографический список 138

Введение

Данное учебное пособие является первой частью учебно-методического комплекса дисциплины «Методы оптимизации» и содержит разделы :

• Классификация задач и методов оптимизации.

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

• Графический метод решения задач линейного программирования.

• Симплексный метод решения задач линейного программирования.

• Двойственные задачи, основные теоремы двойственности.

• Транспортные задачи, их решение методом потенциалов.

• Матричные игры, применение к решению оптимизационных задач.

• Графы, их применение к решению оптимизационных задач.

Целью данного учебно-методического комплекса является оказание помощи студентам всех форм обучения в организации самостоятельной работы при изучении курса «Методы оптимизации».

Настоящее учебное пособие предназначено для студентов второго курса специальности 080801.65 «Прикладная информатика в экономике». Пособие написано на основе курса лекций, который авторы читают для студентов всех форм обучения, оно рассчитано как для самостоятельной работы студентов, так и для обучения в аудитории.

Учебное пособие содержит контрольные задания (приложение А), которые необходимо выполнить, чтобы получить допуск к экзамену. Решения типовых задач рассмотрены подробно во всех разделах учебного пособия.

Предмет «Методы оптимизации» включает в себя изучение методов решения задач на отыскание оптимальных решений.

В настоящем учебном пособии рассматриваются линейные оптимизационные задачи, которые традиционно называют задачами линейного программирования. Термин «программирование» следует понимать как планирование и не смешивать с программированием,

обучающим составлению программы, осуществляющей заданный вычислительный процесс на ЭВМ.

Систематическое исследование линейных оптимизационных задач и разработка об­щих методов их решения начаты в работах советского математика, лауреата Нобелевской премии по экономике (1972), Л. В. Канторовича, который предложил в 1939 г. метод разрешаю­щих множителей и применил его к решению ряда практических задач.

Впервые постановка задачи линейного программирования по составлению оптимально­го плана перевозок дана в работе советского экономиста А. Н. Толстого в 1930 г.

Л. В. Канторович в 1949 г. совместно с М. К. Гавуриным разработал метод потенциалов для транспортной задачи линейного программирования, которая была поставлена в 1941 г. американским ученым Ф. Хичкоком, предло­жившим и метод последовательного улучшения для этой задачи.

Основным методом решения задач линейного программирования является симплекс­ный метод Дж. Данцига, опубликованный в 1949 г.

Большой толчок для интенсификации разработок методов линейного программирования дала концепция двойственности, разработанная в 1947 г. основа­телем теории игр (и одним из отцов кибернетики) американским ученым Дж. Фон Нейманом.

Великий математик Леонард Эйлер 2,5 века тому назад написал: «В мире не происходит ничего, где не виден был бы смысл какого-нибудь минимума или максимума».

За рамками учебного пособия остались методы и алгоритмы многих более сложных задач оптимизации. Это алгоритмы векторной и дискретной оптимизации, алгоритмы многоэкстремальной оптимизации и генетические алгоритмы, и другие.

Классические и численные методы безусловной оптимизации рассматриваются в дисциплинах: математика и численные методы.

Задача оптимизации, в которой целевая функция задана функцией одной переменной, относится к наиболее простому типу оптимизационных задач. Одномерные методы оптимизации часто используются и при решении задач с несколькими переменными при подходящем выборе направления и последующей минимизации вдоль этого направления. Методы решения задач одномерной оптимизации: методы дихотомии, золотого сечения, Фибоначчи, квадратичной интерполяции также рассматриваются при изучении численных методов.

В настоящем учебном пособии рассматривается условная оптимизация. Все практические задачи могут быть выполнены в пакетах численных расчетов, например, MATHCAD.