Математическое программирование. Теория. алгоритмы, программы (290,00 руб.)

Стр.2

Стр.3

Стр.4

Стр.5

Стр.6

ББК 22.18я7 Т 19 УДК [517.8+004.421](075.8) Рецензенты: заведующий кафедрой информационных систем и технологий СГАУ, Заслуженный работник высшей школы РФ, Академик международной академии информатизации, д.т.н., профессор С.А.Прохоров; заведующий кафедрой теории оптимального управления МЭСИ, д.э.н., профессор Б.А.Лагоша; заведующий кафедрой прикладной математики ГУУ, д.э.н., профессор В.А.Колемаев. Тарасов В.Н., Бахарева Н.Ф. Математическое программирование. Теория, алгоритмы, программы. - Сама р а : РИЦ «Гольфстрим», 2017. -222 с. T 19 ISBN 5-7410-0559-4 Учебное пособие предназначено для студентов специальностей по направлениям «Прикладная информатика (по областям)», «Информатика и вычислительная техника» и «Информационные технологии», изучающих дисциплину «Методы оптимизации». ББК 22.18я7 ISBN 5-7410-0559-4

Стр.2

Содержание Введение Линейное программирование Примеры задач линейного программирования Задача планирования выпуска продукции (планирование производства) Планирование капитальных вложений Основные определения Геометрическая интерпретация двумерной задачи линейного программирования и ее решение Свойства задачи линейного программирования Обоснование симплекс метода Нахождение начального базиса Решение в форме симплекс - таблиц Двойственная задача линейного программирования Пример прямой и двойственной задачи линейного программирования Общая формулировка прямой и двойственной з а ­ дачи Свойства двойственной задачи Анализ чувствительности Экономическая интерпретация двойственных задач Специальные задачи линейного программирования Транспортная задача Поиск начального опорного плана Метод северо - западного угла Метод минимального элемента Решение транспортной задачи методом потенциалов Анализ чувствительности Дискретное программирование Задачи целочисленного линейного программирования Задача о размещениях 6 8 8 8 10 10 13 17 19 25 28 32 32 34 36 40 46 49 49 53 53 55 56 61 63 63 63 1

Стр.3

Задача о назначениях Задача о коммивояжере Методы решения задач целочисленного программирования Метод отсечения Гомори Метод ветвей и границ Метод ветвей и границ решения задачи о коммивояжере Аппроксимация решения задачи о коммивояжере Методы безусловной оптимизации Численные методы безусловной минимизации функции одной переменной. Методы прямого линейного поиска Метод равномерного поиска Метод золотого сечения Численные методы безусловной минимизации функции многих переменных Методы многомерного прямого поиска Метод циклического покоординатного спуска Метод Хука - Дживса Метод наискорейшего спуска Задачи нелинейного программирования Постановка задачи и основные определения Геометрическая интерпретация решения задач нелинейного программирования Задачи выпуклого программирования Основные определения и теоремы Метод неопределенных множителей Лагранжа для решения задач квадратичного программирования Градиентные методы решения задач нелинейного программирования Метод приведенного градиента Вулфа Метод штрафных функций Лабораторные работы Лабораторная работа №1. Решение задачи линейного программирования 64 65 66 66 69 70 75 77 77 79 79 81 81 82 85 85 88 88 90 93 93 98 101 102 109 114 114

Стр.4

6.2 6.3 6.4 6.5 6.6 6 .6.1 6 .6.2 6.6.3 6.7 6.7.1 6.7.2 6.8 6 .8.1 6 .8.2 6.9 Лабораторная работа №2. Решение двойственной задачи линейного программирования Лабораторная работа №3. Решение транспортной задачи Лабораторная работа №4. Решение задачи целочисленного программирования Лабораторная работа №5. Решение задачи о коммивояжере Лабораторная работа №6 . Решение задачи безусловной оптимизации функций одной переменной Метод равномерного поиска Метод золотого сечения Метод Ньютона Лабораторная работа №7. Решение задачи безусловной оптимизации функций многих переменных Метод циклического покоординатного спуска Метод наискорейшего спуска Лабораторная работа №8 . Решение задачи нелинейного программирования методами Лагранжа и приведенного градиента Вулфа Метод неопределенных множителей Лагранжа Метод приведенного градиента Вулфа Лабораторная работа №9. Решение задачи нелинейного программирования методом штрафных функций Список использованной литературы 126 130 150 161 178 178 180 181 183 183 186 191 191 2 00 214 2 22 3

Стр.5

Введение Математическое программирование представляет собой математическую дисциплину, занимающуюся изучением экстремальных задач и разработкой методов их р е ­ шения. В общем виде математическая постановка экстремальной задачи состоит в определении наибольшего или наименьшего значения целевой функции f ( x 1, х2, ..., хп) при условиях gi (х1, х 2, ..., хn) < bi (i = 1,m), где f и gi - заданные функции, а b i - некоторые действительные числа. В зависимости от свойств функций f и gi математическое программирование можно рассматривать как ряд самостоятельных дисциплин, занимающихся изучением и разработкой методов решения определенных классов з а ­ дач. Прежде всего, задачи математического программирования делятся на задачи линейного и нелинейного программирования. При этом если все функции f и gi линейные, то соответствующая задача является задачей линейного программирования. Если же хотя бы одна из указанных функций нелинейная, то соответствующая задача я в ­ ляется задачей нелинейного программирования. Наиболее изученным разделом математического программирования является линейное программирование. Для решения задач линейного программирования разработан целый ряд эффективных методов, алгоритмов и программ. Среди задач нелинейного программирования наиболее глубоко изучены задачи выпуклого программирования. Это задачи, в результате решения которых определяется минимум выпуклой (или максимум вогнутой) функции, заданной на выпуклом замкнутом множестве. В свою очередь, среди задач выпуклого программирования более подробно исследованы задачи квадратичного программирования. В результате решения таких задач требуется в общем случае найти максимум (или минимум) квадратичной функции при условии, что ее переменные удовлетворяют некоторой системе линейных не4

Стр.6