Алгоритм отыскания оптимального решения задачи Л П
..........26 <...> Системный
'операционный) подход - основа для изучения и совершенствования слож
ных систем. <...> Схема операционного проекта
Весь комплекс работ по изучению и совершенствованию системы (опе
рации) проводит операционная группа системных аналитиков. <...> Если количество переменных в задачах ЛП и ЛЦП большое, то их необ
ходимо решать с использованием специальных алгоритмов (которые мы изу
13
чим) и компьютерных программ. <...> Изобразим линию постоянного уровня целевой функции Z,=const. возь
мем, например, L=170, получим уравнение прямой 170 = 10х, + 8,5х2. <...> Оптимальной точкой будет точка выхода этой
прямой из области допустимых решений. <...> 14
Очевидно, что точка А является оптимальной для случая, когда банки
можно вскрывать (xj и х2 могут быть нецелыми), а точка В - оптимальная
точка для целого решения. <...> Если стоимость банки краски первого типа повысится до 17 рублей, то
целевая функция будет £ = 17х, + 8,5х2 - » m in . <...> Впервые задача ЛП была сформулирована Л.В .Канторовичем, который
применил математическую модель задачи ЛП для экономики (1939 г.). <...> Задача ЛП - такая задача исследования операций, когда целевая функция
и все функции ограничений линейны, а все переменные - действительные
числа:
П
L
=
2 > , х 7 - »
m in (m a x ),
п
Xj
е
R,
V /
= 1 ,п . <...> Рассмотрим стандартную (основную) форму задачи ЛП, будем сокра
щенно называть ее ОЗЛП. <...> В ней:
1) целевая функция минимизируется: L —» min;
2) ограничения только равенства;
3) все переменные неотрицательны: Xj > О, V T . <...> Любую задачу ЛП в общем виде можно привести к ОЗЛП, для чего необ
ходимо выполнить следующие действия:
1. <...> Отсюда ясно, что в задаче ЛП внутри ОДР не
может быть оптимальной точки. <...> Допустимые решения находятся во внутренних точках многогранника, а
оптимальное, очевидно, может находиться только в вершине многогранника
в точке «последнего» касания плоскости - целевой функции и многогранни
ка, где пересекаются <...>
Методы_оптимизации_и_исследование_операций._Конспект_лекций_.pdf
Б.А. ЕСИПОВ
МЕТОДЫ ОПТИМИЗАЦИИ
И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
САМАРА
Стр.1
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ
УНИВЕРСИТЕТ имени академика С.П. КОРОЛЕВА»
Б.А. ЕСИПОВ
МЕТОДЫ ОПТИМИЗАЦИИ
И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Утверждено Редакционно-издательским советом университета
в качестве учебного пособия
САМАРА
Издательство СГАУ
2007
Стр.2
УДК 519.8
ББК 22.1
Е 833
Инновационная образовательная программа
«Развитие центра компетенции и подготовка
специалистов мирового уровня в области аэрокосмических
и геоинформационных технологий»
Рецензенты: д-р техн. наук, проф. А. Н. К о в а р ц е в,
д-р физ.-мат. наук, проф. С. Я. Ша т с к и х
Есипов Б.А.
Е 833 Методы оптимизации и исследование операций: учеб. пособие /
Б.А.Есипов. - Самара: Изд-во Самар, гос. аэрокосм, ун-та, 2007. -
180 с. : ил.
ISBN 978-5-7883-0640-7
В учебном пособии дано краткое изложение основных методов оптимизации
и исследования операций. Материал пособия основан на лекциях,
читаемых автором для студентов факультета «Информатика», и соответствует
программам курсов «Методы оптимизации», «Теория игр и исследование
операций», «Теория принятия решений». Настоящее пособие является
вспомогательным материалом к прослушиваемому курсу лекций, поэтому
применяется конспективный стиль изложения. Приведены алгоритмы
и примеры их работы, а также рисунки, поясняющие суть методов, что
позволяет студентам разрабатывать компьютерные программы для выполнения
индивидуальных заданий курсовой работы.
Предназначено для студентов специальностей «Прикладная математика
и информатика», «Автоматизированные системы обработки информации
и управления», а также аспирантов и специалистов, интересующихся
методами оптимизации и исследования операций. Подготовлено на кафедре
«Информационные системы и технологии» Самарского государственного
аэрокосмического университета.
УДК 519.8
ББК 22.1
ISBN 978-5-7883-0640-7
© Есипов Б. А., 2007
© Самарский государственный
аэрокосмический университет, 2007
Стр.3
Оглавление
Введение............................................................................................................................ ..
1. Методология системного анализа и исследование операций...........................7
1.1. Системный анализ, система, оптимизация...............................................7
1.2. Схема операционного проекта....................................................................8
1.3. Особенности математического моделирования операций..................11
1.4. Постановка задачи исследования операций в детерминированном
случае и в условиях неопределенности................................................. 12
1.5. Пример математического моделирования операции (задача о
краске)............................................................................................................13
2. Линейное программирование (ЛП)...................................................................... 16
2.1. Общая и основная задачи ЛП....................................................................17
2.2. Геометрическая интерпретация задачи ЛП............................................19
2.3. Идея симплекс-метода решения задачи ЛП.......................................... 21
2.4. Симплекс-таблица, стандартный алгоритм симплекспреобразования
............................................................................................23
2.5. Алгоритм отыскания опорного решения задачи ЛП............................25
2.6. Алгоритм отыскания оптимального решения задачи ЛП ..........26
2.7. Алгоритм получения первого базисного решения с
использованием симплекс - процедуры (метод искусственного
базиса)............................................................................................................29
2.8. Вырожденная задача ЛП............................................................................31
2.9. Двойственная задача ЛП............................................................................32
3. Транспортные задачи (ТЗ)...................................................................................... 35
3.1. Математическая модель ТЗ по критерию стоимости...........................35
3.2. Нахождение опорного плана транспортной задачи.............................36
3.3. Оптимизация плана ТЗ, распределительный метод.............................38
3.4. Метод потенциалов решения ТЗ.............................................................. 40
3.5. Решение ТЗ с неправильным балансом..................................................43
3.6. ТЗ по критерию времени, типы критериев.............................................45
4. Дискретное программирование.............................................................................48
4.1. Особенности задач дискретного программирования...........................49
4.2. Примеры моделей задач дискретного программирования.................50
4.2.1. Задача о покрытии.............................................................................54
4.2.2. Задача о коммивояжёре....................................................................54
4.2.3. Задача о раскрое материала.............................................................55
4.2.4. Задача о ранце.....................................................................................58
4.3. Алгоритм решения задачи о ранце..........................................................58
4.4. Решение задач ЛЦП методом отсечений Гомори................................ 61
4.5. Метод ветвей и границ (МВТ)...................................................................66
3
Стр.4
4.6. Алгоритм МВГ для задачи ЛЦП..............................................................68
4.7. Алгоритмы решения задач булевского программирования.............. 7^
5. Динамическое программирование
............................................................. 7!!
5.1 Принцип оптимальности Р.Беллмана.......................................................75
5.2. Решение графовых задач на основе принципа Беллмана...................8'
5.3. Функциональное уравнение Беллмана....................................................82
5.4. Задачи распределения ресурсов................................................................84
5.4.1. Классическая задача распределения ресурсов............................ 84
5.4.2. Неоднородные этапы и распределение ресурсов по п
отраслям...............................................................................................85
5.4.3. Распределение ресурсов с резервированием............................... 85
5.4.4. Распределение ресурсов с «вложением доходов»......................87
5.5. Расширение модели задач динамического программирования 89
5.6. Пример решения задачи распределения ресурсов...............................91
5.7. Эффективность динамического программирования........................... 93
6. Нелинейное программирование............................................................................95
6.1. Особенности задач нелинейного программирования......................... 95
6.2. Прямые методы одномерной оптимизации нелинейных функций
без ограничений.......................................................................................... 97
6.3. Градиентные методы многомерной оптимизации...............................99
6.3.1. Классический градиентный метод...............................................100
6.3.2. Покоординатный метод.................................................................. 101
6.3.3. Метод наискорейшего спуска и его модификации.................. 101
6.4. Метод деформируемого многогранника Нелдера-Мида.................. 101
6.5. Задача НЛП с ограничениями-равенствами.........................................103
6.6. Выпуклое НЛП...........................................................................................106
6.7. Теорема Куна-Таккера для выпуклого НЛП........................................108
6.8. Квадратичное программирование...........................................................109
6.9. Методы возможных направлений...........................................................114
6.10. Метод проекции градиента....................................................................118
6.11. Методы штрафных и барьерных функций.........................................121
6.12. Метод скользящего допуска.......................................... •.......................127
7. Особенности современной теории принятия оптимальных решений 130
7.1. Общая постановка задачи принятия решения..................................... 131
7.2.Классификация задач принятия решений.............................................. 133
7.3. Многокритериальная оптимизация........................................................ 135
7.4. Определение множества Парето.............................................................138
7.5. Методы условной многокритериальной оптимизации......................140
8. Игровые модели принятия решений...................................................................144
8.1. Основные понятия теории игр................................................................ 144
8.2. Платежная матрица антагонистической игры, принцип
минимакса...................................................................................................145
8.3. Решение игр в смешанных стратегиях..................................................147
4
Стр.5
8.4. Упрощение игр и аналитическое решение игр 2x2............................148
8.5. Геометрическое решение игр.................................................................. 150
8.6. Решение игр со многими стратегиями на основе метода
линейного программирования...............................................................153
8.7. Биматричные игры......................................................................................155
8.8.Кооперативные игры.................................................................................. 156
Элементы теории статистических оптимальных решений..........................159
9.1. Принятие решений при известных априорных вероятностях 160
9.2. Методы принятия решений в условиях априорной
неопределенности......................................................................................162
9.3. Планирование эксперимента при принятии решений........................163
9.4. Многоэтапное принятие решений...........................................................165
40. Экспертные процедуры для принятия решений............................................169
10.1. Общая схема экспертизы........................................................................169
10.2. Задача оценивания....................................................................................170
10.3. Подготовка экспертизы.......................................................................... 170
10.4. Методы обработки экспертной Информации..................................... 171
10.5. Метод Делфи для численной оценки...................................................173
10.6. Строгое ранжирование............................................................................174
10.7. Нестрогое ранжирование.........................................................................175
10.8. Метод попарных сравнений...................................................................176
Список литературы......................................................................................................178
5
Стр.6
ВВЕДЕНИЕ
Одним из главных направлений деятельности специалиста в любой сфере
является совершенствование существующих и создание новых изделии, систем
или технологий: создание лучших машин, экономное расходование ресурсов,
сокращение сроков строительства и т.д.
Обычно та или иная цель может быть достигнута разными путями, но
всегда важно знать наилучший из них, так как в реальных условиях приходится
считаться с ограниченностью материальных ресурсов и времени, расходуемых
на достижение цели. Понятие «лучший» начинает что-либо означать
тогда, когда назван количественный показатель или критерий качества
принимаемого решения. Например, изделие А лучше изделия В с точки зрения
затрат материала; система С лучше системы D по показателю надежности
и т.п. Вот почему получение наилучших вариантов возможно только при
количественном описании предметной области, т.е. на основе математической
модели.
Методология анализа сложных систем, их математическое моделирование
и нахождение на этой основе наилучших (оптимальных) решений в общем
виде изучается в науке «исследование операций». В рамках этого общего
направления изучаются и математические «методы оптимизации». Последнее
название применяют для методов нахождения экстремумов функций
и функционалов, когда математическая модель задачи уже сформулирована.
Большой вклад в развитие методологии исследования операций и методов
оптимизации внесли российские и зарубежные ученые: Л.В.Канторович,
Л.С.Понтрягин, Н.Н.Моисеев, Дж. Данциг, Г.Кун и А.Таккер, Р.Беллман,
Р.Гомори и многие другие.
При подготовке рукописи этой книги использован опыт преподавания на
факультете информатики Самарского государственного аэрокосмического
университета. Это предопределило перечень вопросов, которые в первую
очередь должны были быть освещены. При изложении автор предельно
кратко старался излагать сугубо теоретические вопросы, оставляя место основным
идеям и методам, имеющим универсальное значение. Особый акцент
сделан на практические алгоритмы решения разнообразных задач, которые
можно положить в основу разрабатываемых компьютерных программ.
6
Стр.7
Учебное издание
Есипов Борис Алексеевич
МЕТОДЫ ОПТИМИЗАЦИИ И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
Учебное пособие
Технический Н. Н. П а в л о в а
Редакторская обработка В. С. Те л е п о в а
Корректорская обработка Е. А. Л а р и о н о в а
ДоверсткаА. С. Ко ч е у л о в а
Подписано в печать 20.11.07. Формат 60x84 1/16.
Бумага офсетная. Печать офсетная.
Печ. л. 11,25.
Тираж 120 экз. Заказ 1 0 9 ИП-77/2007
Самарский государственный
аэрокосмический университет.
443086 Самара, Московское шоссе, 34.
Изд-во Самарского государственного
аэрокосмического университета.
443086 Самара, Московское шоссе, 34.
Стр.181