Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

Оптимизация в расчетах

Покупка
Основная коллекция
Артикул: 867099.01.99
Доступ онлайн
500 ₽
В корзину
Содержит в теоретической части описание методов и алгоритмов оптимизации, а в практической - примеры их расчетов. Рассматриваются теории и примеры расчетов: многокритериальной оптимизации, линейного программирования, безусловной и стохастической оптимизации. Также обсуждаются вопросы применения оптимизационных алгоритмов в теории игр и в технологиях искусственных нейронных сетей. Для студентов начальных курсов, изучающих дисциплины: «Теория принятия решений», «Исследование операций», «Теория игр» и «Искусственный интеллект».
40
Сорокин, А. Б. Оптимизация в расчетах : учебное пособие / А. Б. Сорокин. – Москва ; Вологда : Инфра-Инженерия, 2025. - 224 с. – ISBN 978-5-9729-2519-3. - Текст : электронный. - URL: https://znanium.ru/catalog/product/2226632 (дата обращения: 19.11.2026). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов
 
 
 
 
 
 
А. Б. СОРОКИН 
 
 
 
 
 
 
 
ОПТИМИЗАЦИЯ В РАСЧЕТАХ 
 
 
Учебное пособие 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Москва    Вологда 
«Инфра-Инженерия» 
2025 


УДК 004.8 
ББК 32.813 
С65 
 
 
 
Рецензенты: 
кандидат технических наук, доцент, заведующий кафедрой вычислительной техники  
Института информационных технологий МИРЭА – Российский технологический  
университет Платонова Ольга Владимировна; 
доктор технических наук, доцент, руководитель научно-методического центра  
АО «Концерн «Моринсис-Агат» Андреева Ольга Николаевна 
 
 
 
 
 
 
 
 
 
 
 
 
Сорокин, А. Б.  
С65   
Оптимизация в расчетах : учебное пособие / А. Б. Сорокин. – Москва ; 
Вологда : Инфра-Инженерия, 2025. – 224 с. : ил., табл. 
ISBN 978-5-9729-2519-3 
 
Содержит в теоретической части описание методов и алгоритмов оптимизации, 
а в практической – примеры их расчетов. Рассматриваются теории и примеры расчетов: 
многокритериальной оптимизации, линейного программирования, безусловной и стохастической оптимизации. Также обсуждаются вопросы применения оптимизационных алгоритмов в теории игр и в технологиях искусственных нейронных сетей.  
Для студентов начальных курсов, изучающих дисциплины: «Теория принятия решений», «Исследование операций», «Теория игр» и «Искусственный интеллект».  
 
УДК 004.8 
ББК 32.813 
 
 
 
 
ISBN 978-5-9729-2519-3 
© Сорокин А. Б., 2025 
 
© Издательство «Инфра-Инженерия», 2025 
 
© Оформление. Издательство «Инфра-Инженерия», 2025 
 


 
Оглавление 
Введение ............................................................................................................................ 5 
Глава 1. Многокритериальная оптимизация ............................................................ 8 
1.1. Парето-оптимальное множество и способы его сужения .................................. 9 
1.1.1. Отношение доминирования по Парето .......................................................... 9 
1.1.2. Множество Парето ......................................................................................... 11 
1.1.3. Сужение множества Парето .......................................................................... 13 
1.2. Метод ELECTRE ................................................................................................... 15 
1.2.1. Общая схема метода ELECTRE .................................................................... 15 
1.2.2. Использование метода ELECTRE ................................................................ 18 
1.3. Метод анализа иерархий ...................................................................................... 23 
1.3.1. Общая схема метода анализа иерархий ....................................................... 23 
1.3.2. Использование метода анализа иерархий .................................................... 28 
1.4. Оптимальность по Парето в бескоалиционных играх ...................................... 33 
1.4.1. Пример бескоалиционной игры .................................................................... 34 
1.4.2. Ситуации равновесия по Нэшу ..................................................................... 35 
1.4.3. Оптимальные по Парето ситуации игры ..................................................... 37 
Глава 2. Линейное программирование ..................................................................... 40 
2.1. Основные понятия линейного программирования ........................................... 40 
2.1.1. Сущность линейного программирования .................................................... 40 
2.1.2. Общая постановка задачи линейного программирования ......................... 41 
2.1.3. Построение математической модели ........................................................... 42 
2.1.4. Понятие выпуклого множества .................................................................... 45 
2.2. Решение задачи линейного программирования  
с помощью графического метода ............................................................................... 47 
2.2.1. Стандартная форма задачи линейного программирования ....................... 47 
2.2.2. Рекомендации по построению модели в стандартной форме ................... 48 
2.2.3. Решение задач с двумя переменными графическим методом ................... 49 
2.2.4. Графический анализ чувствительности оптимального решения .............. 54 
2.3. Симплексный метод решения задачи линейного программирования ............ 58 
2.3.1. Каноническая форма ...................................................................................... 59 
2.3.2. Сущность симплексного метода ................................................................... 60 
2.3.3. Алгоритм симплексного метода ................................................................... 62 
2.3.4. Решение задач линейного программирования  
симплексным методом ............................................................................................. 63 
2.4. Двойственность задачи линейного программирования ................................... 68 
2.4.1. Сущность прямой и двойственной задачи  
линейного программирования ................................................................................ 68 
2.4.2. Сущность прямой и двойственной задачи ................................................... 69 
2.4.3. Первая теорема двойственности ................................................................... 71 
2.4.4. Вторая теорема двойственности ................................................................... 75 
2.4.5. Третья теорема двойственности ................................................................... 78 
2.5. Методы решения транспортных задач ............................................................... 81 
2.5.1. Постановка транспортной задачи ................................................................. 82 
2.5.2. Методы нахождения начального опорного решения ................................. 83 


 
2.5.3. Метод потенциалов ........................................................................................ 85 
2.5.4. Задачи с нарушенным балансом ................................................................... 90 
2.6. Принятие решений в матричных играх .............................................................. 94 
2.6.1. Сущность матричной игры ............................................................................ 94 
2.6.2. Ситуации равновесия в матричной игре ...................................................... 95 
2.6.3. Смешанные стратегии ................................................................................... 97 
2.6.4. Решение матричных игр ................................................................................ 98 
Глава 3. Безусловная оптимизация ......................................................................... 101 
3.1. Методы нулевого порядка ................................................................................. 101 
3.1.1. Симплексный метод ..................................................................................... 102 
3.1.2. Метод Нелдера – Мида ................................................................................ 110 
3.1.3. Метод Хука – Дживса .................................................................................. 119 
3.2. Методы первого порядка ................................................................................... 126 
3.2.1. Метод градиентного спуска с постоянным шагом ................................... 126 
3.2.2. Метод наискорейшего градиентного спуска ............................................. 132 
3.2.3. Метод покоординатного спуска ................................................................. 135 
3.2.4. Метод Флетчера – Ривса .............................................................................. 138 
3.3. Методы второго порядка ................................................................................... 141 
3.3.1. Метод Ньютона ............................................................................................ 141 
3.3.2. Метод Ньютона – Рафсона .......................................................................... 143 
3.4. Применение градиентных методов в искусственных нейронных сетях ....... 146 
3.4.1. Математический нейрон .............................................................................. 146 
3.4.2. Многослойный перцептрон ......................................................................... 152 
3.4.3. Алгоритм обратного распространения ошибки ........................................ 155 
3.4.4. Проблемы оптимизации нейронных сетей ................................................ 161 
Глава 4. Стохастическая оптимизация .................................................................. 165 
4.1. Генетический алгоритм ...................................................................................... 165 
4.1.1. Общая схема работы генетического алгоритма ........................................ 166 
4.1.2. Операторы генетического алгоритма ......................................................... 169 
4.1.3. Примеры работы генетического алгоритма .............................................. 176 
4.1.4. Настройка параметров генетического алгоритма ..................................... 182 
4.2. Роевой интеллект ................................................................................................ 184 
4.2.1. Алгоритм роя частиц ................................................................................... 184 
4.2.2. Муравьиный алгоритм ................................................................................. 192 
4.2.3. Алгоритм пчелиной колонии ...................................................................... 198 
4.3. Метод имитации отжига .................................................................................... 202 
4.3.1. Алгоритм имитации отжига ........................................................................ 203 
4.3.2. Пример работы алгоритма имитации отжига ............................................ 206 
Приложение А. Расчет индекса согласия ............................................................... 210 
Приложение Б. Расчет важности приоритетов ..................................................... 213 
Список литературы .................................................................................................... 222 
 
 
 


 
Введение 
Любое исследование основывается на применении научного метода, 
предоставляет научную информацию и теории для объяснения природы  
и свойств окружающего мира. При этом не существует неприступных границ –  
и подходы, и методы могут переплетаться в едином исследовании. Научные подходы нацеливают на научные разработки и открытия, а методы помогают совершать их. Изучение и исследование любого процесса или объекта тесно связано с 
оптимизацией. 
Существует достаточное число дефиниций понятия «оптимизация». Будем 
рассматривать оптимизацию как процесс максимизации выгодных характеристик, 
соотношений и минимизации расходов; нахождение экстремума (минимума или 
максимума) целевой функции в некоторой области конечномерного векторного 
пространства; процесс поиска оптимума, использующий случайность. 
Есть классы оптимизационных задач, решение которых удается находить 
с помощью достаточно эффективных методов, вполне приемлемых по трудоемкости. Вместе с тем имеются и такие классы оптимизационных задач, решение 
которых невозможно найти без полного перебора вариантов. В частности,  
к числу последних относятся многие разновидности задач многокритериальной 
оптимизации. 
На первый взгляд может показаться, что многокритериальная задача представляет собой наиболее простой выбор. Кажется в этом случае достаточно лишь 
«сравнить» между собой альтернативы и выбрать из них наилучшую. Однако на 
самом деле такой выбор оказывается весьма сложным. Даже бинарное решение 
требует от управленца определенных умственных усилий, а по мере увеличения 
альтернатив возникает парадокс выбора, когда человек отказывается от решения. 
Надо учитывать, что люди обладают ограниченными возможностями в плане обработки информации и часто идут по пути наименьшего сопротивления и, действуя подобным образом, они лишь защищают себя от информационной перегрузки и усталости. 
Интересные выводы на эту тему делает Барри Шварц (американский психолог): «Когда количество вариантов выбора продолжает увеличиваться, начинают проявляться негативные аспекты многообразия альтернатив. А когда возможностей выбирать становится еще больше, негативные чувства обостряются 
до того, что мы оказываемся перегруженными многообразием выбора. В этот момент выбор больше не добавляет свободы, а вызывает беспомощность. Можно 
даже сказать, подавляет». 
Процессы принятия решений лежат в основе любой целенаправленной деятельности. В экономике они предшествуют созданию производственных и хозяйственных организаций, обеспечивают их оптимальное функционирование  
и взаимодействие. В научных исследованиях – позволяют выделить важнейшие 
научные проблемы, найти способы их изучения, предопределяют развитие экспериментальной базы и теоретического аппарата. При создании новой техники – 
составляют важный этап в проектировании машин, устройств, приборов, ком
 
плексов, зданий, в разработке технологии их построения и эксплуатации; в социальной сфере – используются для организации функционирования и развития социальных процессов, их координации с хозяйственными и экономическими процессами. Оптимальные (эффективные) решения позволяют достигать цели при 
минимальных затратах трудовых, материальных и сырьевых ресурсов. 
Известно, что при большой размерности этих задач реализация перебора 
вариантов практически невозможна из-за чрезвычайно больших временных затрат. Усложнение многомерной целевой функции приводит экспоненциальному 
росту зависимости размерности задачи от времени вычислений. Возникает проблема, которая полечила название «проклятие размерности». Таким образом, оптимизационные задачи могут решаться классическими методами до определенного придела. В этой ситуации альтернативным подходом является применение 
методов, базирующихся на методологии стохастической оптимизации. К стохастической оптимизации относятся: эволюционные вычисления, роевой интеллект, алгоритм имитации отжига и др. 
Высокая согласованность и эффективность работы элементов биологических систем приводила целый ряд исследователей к естественной мысли о возможности использования принципов биологической эволюции для оптимизации 
важных для приложений систем, природа которых отлична от биологической. 
Термин «эволюционных вычислений» обычно используется для общего описания алгоритмов поиска, оптимизации или обучения, основанных на некоторых 
формализованных принципах естественного эволюционного отбора. Эволюционные вычисления представляет собой одно из направлений искусственного интеллекта, объединяющее компьютерные методы моделирования эволюционных 
процессов в естественных и искусственных системах, такие как генетические алгоритмы, эволюционные стратегии, эволюционное программирование и другие 
эвристические методы. 
Генетический алгоритм – это метаэвристика, вдохновленная процессом 
естественного отбора. Генетические алгоритмы обычно используются для генерации высококачественных решений задач оптимизации и поиска, полагаясь на биологически обусловленные операторы, такие как мутация, скрещивание и отбор. 
Слаженное поведение многих животных, насекомых и бактерий всегда вызывало интерес человека. Такое коллективное поведение описывает децентрализованную самоорганизующуюся систему, так называемый «роевой интеллект». 
Роевой интеллект – это коллективное поведение децентрализованных, самоорганизующихся систем, естественных или искусственных. 
Системы роевого интеллекта обычно состоят из популяции простых агентов, локально взаимодействующих друг с другом и с окружающей средой. Вдохновение часто приходит из природы, особенно из биологических систем. Агенты 
следуют очень простым правилам, хотя нет централизованной структуры управления, диктующей, как должны себя вести отдельные агенты, локальные и в 
определенной степени случайные взаимодействия между такими агентами приводят к появлению «разумного» глобального поведения, неизвестного отдельным агентам. Примерами роевого интеллекта в природных системах являются 
колонии муравьев, колонии пчел, стаи птиц и др. 


 
Существует ряд оптимизационных алгоритмов, которые используют естественную мотивацию процессов металлургии – алгоритм отжига. В металлургии 
метод включает нагрев и контролируемое охлаждение материала для изменения 
его физических свойств. Имитированный отжиг можно использовать для решения очень сложных задач вычислительной оптимизации, где классические алгоритмы не работают. Даже несмотря на то, что обычно достигается приближенное 
решение глобального минимума, этого может быть достаточно для многих практических задач. 
Таким образом, имитированный отжиг – это вероятностный метод аппроксимации глобального оптимума заданной функции. В частности, это метаэвристика для аппроксимации глобальной оптимизации в большом пространстве поиска для задачи оптимизации. Из большого количества локальных оптимумов 
целевой функции метод имитации отжига может найти глобальные оптимумы. 
Алгоритм часто используется, когда пространство задачи обусловлено дискретным поиском (например, задача коммивояжера). Для задач, где поиск приблизительного глобального оптимума более важен, чем поиск точного локального оптимума за фиксированный промежуток времени, имитация отжига может быть 
предпочтительнее точных алгоритмов, таких как градиентный спуск или метод 
ветвей и границ. 
Необходимо отметить, что различные алгоритмы и методы оптимизации 
широко применяются в технологиях искусственного интеллекта, как правило для 
обучения моделей. 
Надеюсь, что данное пособие позволит заинтересованному читателю сделать первый шаг в изучении всего многообразия алгоритмов оптимизации. 
 
 


 
Глава 1. Многокритериальная оптимизация 
Для понимания материала рассмотрим важнейшие термины и понятия 
многокритериальной оптимизации (МКО). 
Лицо, принимающее решение (ЛПР) – субъект решения (управленец, менеджер), наделённый определёнными полномочиями и несущий ответственность за последствия принятого и реализованного управленческого решения. 
ЛПР – один или несколько человек (коллектив), на которых лежит ответственность за принятое решение. 
Альтернатива – необходимость выбора одной из двух или более исключающих друг друга возможностей, а также каждая из этих возможностей. Альтернативы – неотъемлемая часть проблемы принятия решений: если не из чего выбирать, то нет и выбора. Для постановки многокритериальной задачи необходимо иметь хотя бы две альтернативы. 
Критерии – признак, основание, правило принятия решения по оценке 
чего-либо на соответствие предъявленным требованиям. Иными словами, критерии оценки альтернатив – это показатели их привлекательности (или непривлекательности) для участников процесса выбора. В профессиональной деятельности выбор критериев часто определяется многолетней практикой и опытом. При 
небольшом количестве критериев (два-три) задача сравнения альтернатив достаточно проста и прозрачна, качества по критериям могут быть непосредственно 
сопоставимы, и выбран компромисс. 
Исход – отображение множества допустимых альтернатив в множество 
критериальных оценок. Исход управленческого решения – это те результаты, которых ожидает руководство при принятии решения. Исход является основным 
аспектом управленческого решения просто потому, что в нем отражается превалирующее отношение менеджеров, которое существовало на момент принятия 
решения. 
Многокритериальная оптимизация – это метод решения задач, которые состоят в поиске наилучшего (оптимального) решения, удовлетворяющего нескольким несводимым друг к другу критериям. Тогда задача МКО ставится следующим образом: требуется найти числа ݔଵ, ݔଶ, … , ݔ௡, удовлетворяющие системе 
ограничений [1] 
 
݃௜ሺݔଵ, ݔଶ, … , ݔ௡ሻ൑ܾ௜, ݅ =  1, 2, … ܫ, 
(1.1) 
для которых функции 
 
ݖ௞ = ݂௞ሺݔଵ, ݔଶ, … , ݔ௡ሻ, ݇ =  1, 2, … ܭ 
(1.2) 
достигают максимального или минимального значения. 
Множество точек ܺ = ሺݔଵ, ݔଶ, … , ݔ௡ሻ, удовлетворяющих условиям (1.1), 
образует область допустимых решений ܦؿ Թ௡ (является подмножеством евклидова пространства ݊-мерных векторов с вещественными компонентами). Элементы множества ܦ называются допустимыми решениями или альтернативами, 
а числовые функции ݂௞, ݇ =  1, 2, … , ܭ – целевыми функциями, или критериями, 
заданными на множестве ܦ. В формулировке задач присутствует ܭ целевых 


 
функций. Эти функции отображают множество ܦؿ Թ௡ в множество ܨؿ Թ௄, которое называется множеством достижимости. 
В векторной форме математическую модель МКО (1.2) можно записать 
следующим образом [1]: 
 
݂ҧሺܺሻ = ൫݂ଵሺܺሻ, … , ݂௄ሺܺሻ൯՜ ݉ܽݔ, 
(1.3) 
где 
݂ҧሺܺሻ – вектор-функция аргумента ܺא ܦ. 
Различают 2 группы методов многокритериальной оптимизации на конечном множестве альтернатив: векторные и скалярные. Под векторной оптимизацией на конечном множестве объектов понимается нахождение варианта (альтернативы) с наилучшим значением векторного критерия. Наибольшее распространение получили следующие методы векторной оптимизации: оптимизация 
по Парето; лексиминная оптимизация (упорядочивание по качеству); оптимизация по приоритету критериев (лексикографическая оптимизация) и др. 
Под скалярной оптимизацией на конечном множестве объектов понимается нахождение варианта (альтернативы) с наилучшим значением скалярного 
критерия. Скалярные оценки объектов вычисляются путём преобразования векторного аргумента в скаляр. Наибольшее распространение получили функции, 
усредняющие значения признаков, которые называются обобщающими (синтезирующими). При задании обобщающей функции важная роль отводится выбору 
шкал признаков и их весовым коэффициентам. 
Таким образом, многокритериальная модель задачи принятия решений может быть представлена фиксированным набором переменных следующего вида: 
< ʏ, ʙ, ܸ, ݂, ܲ, ݎ>, 
где 
ʏ – множество допустимых вариантов решений; 
ʙ – множество критериев, по которым оцениваются решения; 
ܸ – множество оценочных шкал; 
݂ – множество оценочных функций, задающих отображение множества допустимых решений во множестве векторных оценок; 
ܲ – система предпочтений лица, принимающего решение; 
ݎ – решающее правило. 
Решающее правило представляет собой алгоритм, который позволяет задать на множестве векторных оценок отношение предпочтения. В качестве решающего правила в практике используются следующие методы: метод простейшего многокритериального ранжирования; метод линейной свертки; метод 
ELECTRE; метод анализа иерархий и др. 
1.1. Парето-оптимальное множество и способы его сужения 
1.1.1. Отношение доминирования по Парето 
Если функции ݂ଵ, ݂ଶ, … , ݂௄ достигают максимум в одной и той же точке 
ܺכ א ܦ, то говорят, что задача (1.3) имеет идеальное решение. Случаи существования идеального решения в многокритериальной задаче крайне редки. Поэтому 


 
основная проблема при рассмотрении задачи (1.3) – формализация принципа оптимальности, т. е. определение того, в каком смысле «оптимальное» решение 
лучше других. В случае отсутствия «идеального решения» в задаче (1.3) ищется 
компромиссное решение. 
Для всякой альтернативы ܺא ܦ вектор из значений целевых функций 
൫݂ଵሺܺሻ, ݂ଶሺܺሻ, … , ݂௄ሺܺሻ൯ является векторной оценкой альтернативы ܺ. Векторная 
оценка альтернативы содержит полную информацию о ценности (полезности). 
Сравнение любых двух исходов заменяется сравнением их векторных оценок [2]. 
Пусть ܺଵ, ܺଶא ܦ. Если для всех критериев ݂ଵ, ݂ଶ, … , ݂௄ имеют место неравенства ݂௞(ܺଶ) ൒݂௞(ܺଵ), ݇ =  1, 2, … , ܭ, причем хотя бы одно неравенство строгое, то говорят, что решение ܺଶ предпочтительнее решения ܺଵ. Условие предпочтительности принято обозначать в виде ܺଶظ ܺଵ. 
В задаче МКО точка ܺ଴א ܦ называется оптимальной по Парето, если не 
существует другой точки ܺא ܦ, которая была бы предпочтительнее, чем ܺ଴. 
Точки, оптимальные по Парето, образуют множество точек, оптимальных 
по Парето (множество неулучшаемых или эффективных точек) ܦ௣ؿ ܦ. Оптимальные решения многокритериальной задачи следует искать только среди элементов множества альтернатив ܦ௣. В этой области ни один критерий не может 
быть улучшен без ухудшения хотя бы одного из других. Важным свойством множества Парето ܦ௣ является возможность «выбраковывать» из множества альтернатив ܦ заведомо неудачные, уступающие другим по всем критериям. Обычно 
решение многокритериальной задачи должно начинаться с выделения множества Парето ܦ௣. При отсутствии дополнительной информации о системе предпочтений ЛПР должно принимать решение именно из множества Парето [2]. 
В векторной оптимизации кроме множества Парето в общем случае нет общих правил, по которому варианту ܺଶ отдается предпочтение по сравнению  
с другим вариантом ܺଵ.Часто решение многокритериальной задачи состоит в построении множества Парето-оптимальных точек и дальнейшем выборе одной из 
них на основе «здравого смысла» или с помощью какого-либо другого критерия. 
Во всех случаях задача многокритериальной оптимизации каким-то способом 
сводится к задаче с одним критерием. Существует много способов построения 
такого окончательного критерия, однако ни одному из них нельзя заранее отдать 
наибольшее предпочтение. Для каждой задачи этот выбор должен делаться ЛПР. 
Проиллюстрируем (рис. 1.1) приём выделения решений по Парето на примере задачи с двумя критериями ܨଵ и ܨଶ (оба требуется максимизировать). 
Множество ܦ состоит из 11 возможных решений. Каждому решению соответствуют определённые значения показателей ܨଵ и ܨଶ. Пусть имеются следующие векторные оценки: ܨ(ܺଵ) = (2; 4), ܨ(ܺଶ) = (3; 5), ܨ(ܺଷ) = (3; 3), ܨ(ܺସ) = (5; 2), 
ܨ(ܺହ) = (4; 3), ܨ(ܺ଺) = (1; 3), ܨ(ܺ଻) = (2; 3), ܨ(଼ܺ) = (3; 2), ܨ(ܺଽ) = (2; 2), 
ܨ(ܺଵ଴) = (3; 1), ܨ(ܺଵଵ) = (2; 1). 
 


Доступ онлайн
500 ₽
В корзину