Методы оптимальных решений
Покупка
Основная коллекция
Тематика:
Математика
Издательство:
Волгоградский государственный аграрный университет
Автор:
Богданов С. И.
Год издания: 2018
Кол-во страниц: 208
Дополнительно
Вид издания:
Учебно-методическая литература
Уровень образования:
ВО - Магистратура
Артикул: 702758.01.99
Учебно-методическое пособие предназначено для изучения дисциплины «Методы оптимальных решений». В пособии представлены теоретический материал и практические задания.
Для магистров по направлению подготовки 13.04.02 - «Электроэнергетика и электротехника».
Тематика:
ББК:
УДК:
ОКСО:
- 01.00.00: МАТЕМАТИКА И МЕХАНИКА
- ВО - Бакалавриат
- 01.03.01: Математика
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
Министерство сельского хозяйства Российской Федерации Департамент научно-технологической политики и образования Федеральное государственное бюджетное образовательное учреждение высшего образования «Волгоградский государственный аграрный университет» Электроэнергетический факультет Кафедра «Электротехнологии и электрооборудование в с.-х.» С.И. Богданов В.Г. Секаев МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ УЧЕБНО-МЕТОДИЧЕСКОЕ ПОСОБИЕ Волгоград Волгоградский ГАУ 2018
УДК 519.816:65.012.122 ББК 22.18 Б-73 Рецензент – кандидат технических наук, доцент, заведующий кафедрой ЭВМиС «Волгоградского государственного технического университета» А.Е. Андреев Богданов, Сергей Иванович Б-73 Методы оптимальных решений: учебно-методическое пособие / С.И. Богданов, В.Г. Секаев. – Волгоград: ФГБОУ ВО Волгоградский ГАУ, 2018. – 208 с. Учебно-методическое пособие предназначено для изучения дисциплины «Методы оптимальных решений». В пособии представлены теоретический материал и практические задания. Для магистров по направлению подготовки 13.04.02 – «Электро энергетика и электротехника». УДК 519.816:65.012.122 ББК 74.263 © ФГБОУ ВО Волгоградский ГАУ, 2018 © Богданов С.И, Секаев В.Г., 2018
ОГЛАВЛЕНИЕ Введение .............................................................................................. 7 1 Исследование операций и теория принятия решений как области применения математических методов оптимизации ................ 9 1.1 Историческая справка ................................................................... 9 1.2 Определение, предмет и цель исследования операций ............. 9 1.2.1 Определение исследования операций ...................................... 9 1.2.2 Предмет исследования операций .............................................. 10 1.2.3 Цель исследования операций .................................................... 11 1.3 Типичные задачи исследования операций .................................. 11 1.4 Особенности методологии исследования операций .................. 13 1.5 Определение и основные элементы операции ............................ 14 1.6 Основные этапы операционного исследования ......................... 17 1.6.1 Постановка задачи ...................................................................... 17 1.6.2 Построение модели операции ................................................... 19 1.6.3 Выбор метода и отыскание решения ........................................ 26 1.6.4 Проверка и корректировка модели .......................................... 27 1.6.5 Реализация решения ................................................................... 28 1.7 Проблема многокритериальности ............................................... 28 1.7.1 Сущность проблемы многокритериальности .......................... 28 1.7.2 Оптимальность по Парето. Сведение многокритериальной задачи к однокритериальной ........................................................ 29 2 Линейное программирование: математическая формулировка и геометрическая интерпретация ..................................................... 34 2.1 Математическая формулировка задачи линейного программирования .......................................................................................... 34 2.2 Каноническая форма задач линейного программирования ...... 35 2.2.1 Математическая модель ............................................................ 35 2.2.2 Разрешимость канонической задачи линейного программирования .......................................................................................... 35 2.2.3 Допущения ............................................................................ 36 2.2.4 Сведение произвольной задачи линейного программирования к канонической форме ............................................................37 37 2.3 Геометрическая интерпретация и графическое решение задач линейного программирования ...................................................... 40 2.3.1 Геометрическое представление и графическое решение задач с двумя свободными переменными ........................................ 40 2.3.2 Свойства решений задач линейного программирования 48 2.3.3 Геометрическая интерпретация задачи линейного программирования при n–m = 3 ............................................................... 49
2.3.4 Обобщение свойств канонической задачи линейного программирования на произвольное количество свободных переменных 51 3 Симплекс-метод решения задач линейного программирования 54 3.1 Краткий обзор методов решения задач линейного программирования ........................................................................................... 54 3.2 Идея симплекс-метода .................................................................. 55 3.3 Требования к вычислительным процедурам .............................. 58 3.4 Табличный алгоритм замены базисных переменных ................ 59 3.5 Поиск исходного опорного решения канонической задачи линейного программирования с помощью симплекс-таблиц ...... 65 3.6 Поиск оптимального решения канонической задачи линейного программирования с помощью симплекс-таблиц ................... 70 3.7 Вырожденный случай, зацикливание ......................................... 74 3.8 Альтернативные оптимальные решения ..................................... 76 3.9 Альтернативные представления симплекс-таблицы ................. 76 3.10 Поиск опорного решения задачи линейного программирования методом искусственного базиса ............................................. 78 3.10.1 Метод больших штрафов ........................................................ 79 3.10.2 Двухэтапный метод .................................................................. 80 4 Двойственность в задачах линейного программирования .......... 81 4.1 Построение математической модели двойственной задачи 81 4.2 Связь между задачами двойственной пары ................................ 83 4.3 Общий случай, симметричные и несимметричные двойственные пары ........................................................................................ 85 4.4 Поиск решения одной задачи двойственной пары по известному решению другой задачи ...................................................... 88 4.5 Экономическая интерпретация двойственности ........................ 92 4.6 Двойственный симплекс-метод ................................................... 93 5 Интерпретация симплекс-таблиц и анализ модели на чувствительность ........................................................................................ 98 5.1 Остаточные и избыточные переменные, статус ресурсов ......... 98 5.2 Ценность ресурсов ........................................................................ 99 5.3 Анализ модели на чувствительность .......................................... 103 5.3.1 Изменение запасов ресурсов .................................................... 103 5.3.2 Изменение коэффициентов целевой функции ........................ 108 6 Специальные задачи линейного программирования ................... 113 6.1 Транспортная задача .................................................................... 113 6.1.1 Постановка и математическая модель транспортной задачи по критерию стоимости ................................................................. 113 6.1.2 Особенности математической модели ТЗ ............................... 114 6.1.3 Транспортная таблица ............................................................... 115
6.1.4 Построение опорного плана транспортной задачи ................. 116 6.1.4.1 Диагональный метод (метод северо-западного угла) ........... 117 6.1.4.2 Метод наименьшей стоимости ............................................. 119 6.1.4.3 Модифицированный диагональный метод .......................... 120 6.1.5 Нахождение оптимального плана ТЗ по критерию стоимости 122 6.1.5.1 Необходимые понятия и определения.............................. 122 6.1.5.2 Распределительный метод ................................................ 125 6.1.5.3 Идея метода потенциалов ................................................... 125 6.1.5.4 Алгоритм метода потенциалов ............................................ 127 6.1.6 Вырожденность в транспортных задачах ................................ 131 6.1.7 Открытые транспортные задачи ............................................... 135 6.1.8 Транспортная задача по критерию времени ............................ 137 6.1.8.1 Постановка и математическая модель ТЗ по критерию времени ........................................................................................... 137 6.1.8.2 Решение ТЗ по критерию времени ........................................ 138 6.2 Задача о назначениях .................................................................... 141 6.2.1 Содержательная постановка и математическая модель задачи о назначениях ................................................................................. 141 6.2.2 Основы венгерского метода ...................................................... 143 6.2.3 Алгоритм венгерского метода .................................................. 144 7 Целочисленное программирование ................................................ 151 7.1 Математическая постановка задачи ............................................ 151 7.2 Примеры задач целочисленного программирования ................ 151 7.2.1 Задачи с неделимостью ............................................................. 152 7.2.2 Задачи с альтернативными переменными ............................... 153 7.3 Особенности решений задач целочисленного программирования 156 7.4 Общая характеристика методов решения задач целочисленного программирования .......................................................................... 157 7.4.1 Методы отсекающих плоскостей ............................................. 158 7.4.2 Методы возврата (ветвей и границ) .......................................... 160 7.5 Алгоритмы решения задач целочисленного программирования 161 7.5.1 Метод целочисленных форм (первый алгоритм Гомори ....... 161 7.5.2 Метод ветвей и границ .............................................................. 169 8 Нелинейное программирование ...................................................... 176 8.1 Математическая постановка и примеры задач нелинейного программирования ........................................................................ 176 8.2 Графическое представление и особенности решений задач нелинейного программирования .................................................. 178 8.3 Обзор методов решения нелинейных задач ............................... 182 8.4 Классические методы поиска экстремума функций. Метод множителей Лагранжа и его обобщения ...................................... 183
8.4.1 Поиск экстремума функции при отсутствии ограничений 183 8.4.2 Задачи с ограничениями-равенствами. Метод множителей Лагранжа ....................................................................................... 184 8.4.3 Обобщение метода множителей Лагранжа ............................. 185 8.5 Оптимизация функций одной переменной ................................. 187 8.5.1 Виды функций одной переменной ........................................... 188 8.5.2 Последовательный (адаптивный) поиск .................................. 191 8.5.2.1 Метод золотого сечения ......................................................... 191 8.5.2.2 Метод дихотомии .................................................................... 196 8.6 Оптимизация функций многих переменных .............................. 199 8.6.1 Теорема Куна-Таккера .............................................................. 199 8.6.2 Квадратичное программирование ............................................ 201 8.6.2.1 Математическая модель задачи квадратичного программирования ...................................................................................... 201 8.6.2.2 Идея метода Била, его сравнение с линейным симплексалгоритмом .................................................................................... 203 8.6.2.3 Общая схема квадратичного симплекс-алгоритма и характеристика итераций ....................................................................... 204 Список использованной литературы ................................................. 206
ВВЕДЕНИЕ Понятие оптимальности встречается практически во всех сферах человеческой деятельности. Речь может идти, например, об оптимальном соотношении цены и качества продукции, об оптимальной конструкции механизма, об оптимальном плане перевозок, об оптимальной производственной программе, о выборе оптимального маршрута, об оптимальном управлении движущимся объектом или системой и т.п. В конечном счете, все это сводится к принятию оптимального решения в той или иной области целенаправленной человеческой деятельности. Слово оптимальный происходит от латинского слова optimus, что означает наилучший. Таким образом, оптимальное решение – это наилучшее решение, а оптимизация – это поиск наилучшего (оптимального) решения. Потребность в решении оптимизационных задач возникла в глубокой древности. Возьмем, например, такую очень древнюю профессию, как гончарное дело. Прежде чем приступить к изготовлению самого простого сосуда, нужно решить, какую он должен иметь форму, чтобы при имеющемся количестве глины он обладал наибольшей вместимостью. Конечно, в глубокой древности эта задача едва ли явно формулировалась, но объективно она требовала решения. В явном виде подобная проблема была впервые сформулирова на еще в античные времена. В качестве примера рассмотрим знаменитую "задачу Дидоны" [1]. Суть ее состоит в том, финикийская царица Дидона, спасаясь от врагов, бежала в Северную Африку и обратилась к местному племени с просьбой приютить ее, выделив для этого столько земли, сколько можно охватить шкурой вола. Когда эта просьба была удовлетворена, Дидона разрезала шкуру на тончайшие ремешки и, связав их последовательно один с другим, получила длиннейшую нить. Охватив этой нитью изрядный участок земли, Дидона развернула там строительство и основала на этом месте знаменитый город Карфаген. Уже античные ученые заинтересовались задачей: как следовало Дидоне расположить свою нить, чтобы охватить наибольшую площадь. Иными словами, как выбрать из всех линий заданной длины ту, которая охватит наибольшую площадь. Такого рода задачи заложили основу одного из направлений ма тематики, которое получило название вариационное исчисление. В середине XX века это направление нашло применение в работах по теории оптимальных процессов (в частности для решения задач автоматического управления техническими системами). При этом выясни
лось, что классические методы решения, разработанные в трудах выдающихся математиков XVIII – XIX веков (Л. Эйлера, А. Лежандра, К. Вейерштрасса и др.), недостаточны для решения новых вариационных задач. В результате в начале 50-х гг. ХХ века практически одновременно в Советском Союзе и Соединенных Штатах Америки были разработаны новые методы – принцип максимума Л. С. Понтрягина и динамическое программирование Р. Беллмана. Последний метод в его дискретной форме оказался пригодным и для решения ряда задач организационного управления, благодаря чему он вошел в число математических методов, применяемых в рамках еще одной научной дисциплины, занимающейся решением задач оптимального управления организационными системами – исследования операций. Наряду с вышеупомянутыми учеными, большой вклад в разви тие современной теории оптимизации внесли Л.В. Канторович (Нобелевская премия по экономике совместно с американским экономистом Т.Купмансом в 1975 г. за вклад в разработку теории оптимального использования ресурсов) и Дж. Данциг, Г. Кун и А. Таккер, Дж. фон Нейман, Дж. Нэш (Нобелевская премия по экономике в 1994 г. за вклад в развитие теории игр), Р. Гомори, Н.Н. Моисеев и многие другие отечественные и зарубежные ученые. С их именами связаны такие направления математики, используемые при решении оптимизационных задач, как линейное, нелинейное, целочисленное программирование, теория игр и др. Рассмотрению этих и ряда других методов оптимизации и неко торых областей их применения и посвящено данное учебное пособие.
1 ИССЛЕДОВАНИЕ ОПЕРАЦИЙ И ТЕОРИЯ ПРИНЯТИЯ РЕШЕНИЙ КАК ОБЛАСТИ ПРИМЕНЕНИЯ МАТЕМАТИЧЕСКИХ МЕТОДОВ ОПТИМИЗАЦИИ 1.1 Историческая справка Формирование исследования операций как самостоятельной научной дисциплины относится к периоду второй мировой войны. Это объясняется тем, что за время между двумя мировыми войнами в технике ведения боевых операций произошли такие разительные перемены, что военные руководители оказались неподготовленными к ведению войны с помощью новых технических средств. Для повышения эффективности использования этих средств при военных штабах армий США, Англии, Канады и Франции были созданы новые отделы и группы исследования операций, в состав которых вошли и ученые. Ко времени окончания войны крупные изменения произошли и в управлении промышленностью. Возникновение огромных фирм и объединений, укрупнение заводов, бурный технический прогресс – все это привело к тому, что старые методы управления не давали должной эффективности. Успехи же от применения методов управления, рекомендован ных отделами исследования операций в армии, были весьма существенными. Поэтому после войны на крупных промышленных фирмах и объединениях стали создаваться подобные отделы. Раньше других стран методы исследования операций стали применяться в Англии: в угольной промышленности, в энергетике, на железнодорожном и воздушном транспорте. Начиная с 50-х годов ХХ века, в связи с успехами в области электронно-вычислительной техники и проникновением в производство автоматики и современных быстродействующих ЭВМ усиленно развиваются методы исследования операций во всех странах мира с высокоразвитой промышленностью. 1.2 Определение, предмет и цель исследования операций 1.2.1 Определение исследования операций В многочисленной литературе по исследованию операций (напр., [2 – 11]) приводится ряд определений этой научной дисциплины, ни одно из которых не является полностью исчерпывающим и каждое из которых раскрывает ту или иную сторону, тот или иной аспект исследования операций. Перечень этих определений, возможно, не полный, приведен в [11]. Для наших целей вполне приемлемо рас
сматривать исследование операций как комплекс научных методов, предназначенных для нахождения рациональных способов организации целенаправленной человеческой деятельности. Характерной особенностью такой деятельности является необ ходимость принятия решений по ее организации. В принципе любая деятельность, в конечном счете, представляет собой цепочку принятия решений. Простой пример: вы проснулись и сразу же принимаете решение – встать или можно поспать еще. Вы учитесь в университете, первая пара у вас сегодня – лекция по методам оптимизации. Вы решаете, пойти на эту лекцию или ее пропустить. Решили пойти на лекцию и в зависимости от погоды принимаете решение, как одеться, взять ли с собой зонтик и т.д. На лекции вы постоянно принимаете решение, записывать ли то, что говорит лектор, или можно пока просто послушать. Ясно, что подобные решения не требуют специальных расчетов. Человек их принимает на основе собственного опыта, интуиции и здравого смысла. Иное дело – более сложные ситуации, возникающие, например, при управлении войсковыми соединениями, крупными фирмами, предприятиями, при организации пассажирских или грузовых перевозок в рамках большого города или страны и т.п. Здесь, конечно, тоже можно опереться на опыт и интуицию руководителя, но в сложных случаях они могут подвести, особенно если речь идет о мероприятиях, осуществляемых впервые, опыта в проведении которых просто не существует, а цена ошибки может оказаться непомерно высокой. Решения в таких случаях целесообразно подкреплять количественными расчетами, научным обоснованием, для выполнения которого создаются комплексные операционные группы из специалистов разных профессий. Задачей таких групп является рассмотрение проблемы с разных сторон, с разных точек зрения, выработка возможных вариантов решений (альтернатив) и их оценка. 1.2.2 Предмет исследования операций Предметом изучения в исследовании операций являются в ос новном системы организационного управления, т.е. системы, включающие в себя людей, хотя методы этой науки находят применение и в других областях, например, в технических системах [12]. Во многих случаях организационные системы состоят из ряда взаимодействующих между собой подразделений, интересы которых не всегда совпадают друг с другом и могут быть даже противоположными. Например