Математическое программирование. Задачи, модели и алгоритмы
Математическое программирование: задачи, модели и алгоритмы – обзор монографии
Монография А.Н. Божко и С.В. Родионова "Математическое программирование. Задачи, модели и алгоритмы" представляет собой комплексное исследование одного из ключевых разделов прикладной математики. Авторы охватывают широкий спектр методов, моделей и алгоритмов, необходимых для решения экстремальных задач, возникающих в различных областях науки и практики.
Ключевые направления математического программирования
Книга посвящена фундаментальным аспектам математического программирования, за исключением стохастического, динамического и выпуклого программирования. Основное внимание уделено следующим разделам:
- Линейное программирование: В первой главе подробно рассматриваются основы линейного программирования, включая различные вариации симплекс-метода и теорию двойственности. Представлены классические задачи, такие как транспортная задача и задача о назначениях, а также проиллюстрированы методы решения с помощью комбинаторного и геометрического подходов. Особое внимание уделено симплекс-методу, его прямому, двойственному и двухфазному вариантам, а также столбцовому алгоритму.
- Дискретное программирование: Вторая глава посвящена задачам дискретной и комбинаторной оптимизации. Обсуждаются точные и приближенные методы решения, включая методы отсечения, метод ветвей и границ, динамическое программирование, а также жадные алгоритмы. Особое внимание уделено классической задаче о рюкзаке и методам ее решения, включая метод Лэнд-Дойг, целочисленный алгоритм вектора спада и генетические алгоритмы. Рассмотрены также моделирование логических связей и отношений в задачах булева программирования.
- Эвристическое программирование: Третья глава знакомит читателя с мощными и универсальными метаэвристическими алгоритмами, такими как поиск с запретами (Tabu Search), имитация отжига (Simulated Annealing), алгоритм GRASP, итеративный локальный поиск (ILS), Guided Local Search (GLS) и Variable Neighborhood Search (VNS). Эти методы применяются для решения NP-сложных задач, где точные алгоритмы оказываются неэффективными. Особое внимание уделено генетическим алгоритмам, их эволюционному циклу, операторам селекции, кроссовера и мутации, а также их применению к задачам типа SAT и MIS.
- Нелинейное программирование: Четвертая глава излагает базовые принципы и обзор методов нелинейной оптимизации. Рассматриваются методы безусловной и условной оптимизации, включая одномерные методы (дихотомия, числа Фибоначчи, золотое сечение), градиентные методы (покоординатный спуск, метод Хука-Дживса, метод Нелдера-Мида), методы второго порядка (Ньютона, квазиньютоновские) и методы работы с ограничениями (множители Лагранжа, условия ККТ, штрафные и барьерные функции, методы возможных направлений, метод Зойтендейка, метод проекций градиента, метод скользящего допуска).
Целевая аудитория и применимость
Монография предназначена для студентов и аспирантов технических и экономических специальностей, изучающих математическое программирование, прикладную математику и исследование операций. Она также будет полезна инженерам, аналитикам, разработчикам и программистам, сталкивающимся с задачами оптимизации в своей профессиональной деятельности.
Книга предлагает как теоретические основы, так и практические примеры решения задач, что делает ее ценным ресурсом для освоения методов математического программирования и их применения в реальных сценариях.
- ВО - Бакалавриат
- 01.03.04: Прикладная математика
- ВО - Магистратура
- 01.04.04: Прикладная математика
- Аспирантура
- 01.06.01: Математика и механика
- 03.06.01: Физика и астрономия
Москва ИНФРА-М МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ ЗАДАЧИ, МОДЕЛИ И АЛГОРИТМЫ А.Н. БОЖКО С.В. РОДИОНОВ МОНОГРАФИЯ
УДК 519.85(075.4) ББК 22.185.4 Б76 Божко А.Н. Б76 Математическое программирование. Задачи, модели и алгоритмы : монография / А.Н. Божко, С.В. Родионов. — Москва : ИНФРА-М, 2027. — 426 с. — (Научная мысль). — DOI 10.12737/2254801. ISBN 978-5-16-022129-8 (print) ISBN 978-5-16-114863-1 (online) Монография посвящена методам, моделям и алгоритмам математического программирования. Рассматриваются все основные направления этого раздела прикладной математики, кроме стохастического, динамического и выпуклого программирования. В главе по линейному программированию описаны основные разновидности симплекс-метода и теория двойственности. В главе по дискретному программированию обсуждаются точные и приближенные методы решения задач дискретной и комбинаторной оптимизации. Подробно рассмотрена классическая труднорешаемая дискретная проблема — задача об упаковке рюкзака. В современной вычислительной практике многие NP-сложные задачи дискретной оптимизации и плохо обусловленные многомодальные нелинейные задачи решаются при помощи метаэвристик. В книгу включена глава по эвристическому программированию, в которой описаны мощные и универсальные метаэвристические алгоритмы. Последняя глава посвящена нелинейному программированию. В ней изложены базовые принципы и приведен обзор методов нелинейной оптимизации. Предназначена для студентов и аспирантов технических и экономических специальностей, изучающих математическое программирование, прикладную математику и исследование операций. Она будет полезна инженерам, аналитикам, разработчикам и программистам, которые по роду своей деятельности сталкиваются с задачами оптимизации. УДК 519.85(075.4) ББК 22.185.4 Р е ц е н з е н т ы: Каганов Ю.Т., кандидат технических наук, доцент, доцент Московского государственного технического университета имени Н.Э. Баумана; Корсун О.Н., доктор технических наук, профессор, руководитель научнообразовательного центра Государственного научно-исследовательского института авиационных систем ISBN 978-5-16-022129-8 (print) ISBN 978-5-16-114863-1 (online) © Божко А.Н., Родионов С.В., 2026
Предисловие Математическое программирование – одно из важнейших направлений современной прикладной математики. Оно занимается разработкой теории и численных методов решения различных экстремальных задач. Экстремальными принято называть задачи, в которых ищется оптимальное значеиие функции многих переменных, на диапазоны изменения которых наложены ограничения. Подобными задачами изобилует современная промышленная и экономическая практика. Назовем лишь самые важные источники постановок и области применения: x проектирование сложных технических систем; x оптимальное распределение ресурсов; x планирование и организация производства; x логистика и организация транспортных перевозок; x финансовое моделирование; x машинное обучение, анализ больших данных и искусственный интеллект; x планирование военных операций и многое другое. Обсуждаются все основные разделы математического программирования за исключением динамического и стохастического программирования. Нелинейное программирования рассматривается не столь подробно по следующим причинам. Во-первых, это ограниченный объем книги. Во-вторых, есть издания на русском языке [5,9], не утратившие своей актуальности в настоящее время. Книга состоит из четырех глав. В первой главе обсуждаются модели и методы линейного программирования. Этот классический раздел математического программирования не только дает аппарат для формализации многочисленных экономических и логистических задач (транспортная задача, распределение инвестиций, линейный раскрой материалов и др.), но и является основой для изучения методов решения других оптимизационных задач: дискретных и
нелинейных. В главе рассматриваются различные варианты симплекс-метода и теория двойственности. Многие оптимизационные задачи, которые поставляет практика, обладают естественной дискретностью. Нельзя использовать полтора станка или нанять «две трети» исполнителя. В отличие от непрерывной оптимизации, где при поиске максимума можно двигаться по направлению градиента, соседние точки дискретных задач могут весьма значительно отличаться по качеству. Пространство допустимых решений, как правило, растет по экспоненте с увеличением размерности входных данных. Это основные причины вычислительной сложности задач дискретной и комбинаторной оптимизации. Трудно переоценить важность дискретного программирования для различных задач и аспектов разработки сложных технических систем. В первую очередь это системотехническое, логическое и структурное проектирование изделий машиностроения и приборостроения. Данное направление технической оптимизации недостаточно поддержано учебной и монографической литературой на русском языке. Во второй главе рассматриваются точные и приближенные методы решения дискретных и булевых задач оптимизации. Задача о рюкзаке – это классическая труднорешаемая задача дискретной оптимизации. Многие трудные и практически важные дискретные проблемы (например, распределение ресурсов, загрузка контейнеров, формирование портфеля заказов и др.) сводятся или содержат в себе как подзадачу задачу о рюкзаке. Во второй главе подробно обсуждаются различные разновидности «рюкзака», а также и точные и приближенные методы его решения. Авторы сочли необходимым включить во вторую главу раздел, посвященный формализации логических связей и отношений. В подавляющем большинстве практических случаев на управляемые переменные наложены дополнительные ограничения, которые описывают логику принятия решений в данной ситуации. Например, два блока не могут быть включены в одно техническое устройство, или из трех альтернатив необходимо выбрать любые две, или выбор структурного
элемента x влечет за собой включение в структуру элемент y и т.п. Описание дополнительных ограничений в терминах линейного дискретного или булевого программирования значительно расширяет выразительную силу, адекватность и область применимости этого аппарата. Существует класс задач, которые невозможно решить даже на самых мощных современных компьютерах за приемлемые сроки. Это, прежде всего, NPтрудные дискретные задачи высокой размерности, с которыми приходится иметь дело инженерам, разработчикам программных систем, специалистам в области логистики и т.д. Эвристическое программирование – это сравнительно новый раздел теории и практики оптимизации, в котором гарантии оптимальности вычислительного метода или алгоритма компенсируются его способностью находить субоптимальное решение за приемлемое время. Более того, во многих случаях, когда исходные данные не точны, а представления о лучших решениях размыты, методы эвристического программирования не имеют разумной альтернативы. Они допускают интеграцию с экспертным знаниями и позволяют учесть качественные трудноформализуемые факторы, влияющие на оптимальность решения. Эвристические методы позволяют эффективно исследовать огромные пространства решений и часто превосходят любые точные классические методы оптимизации на на задачах с плохой структурой. В третьей главе рассматриваются популярные метаэвристичесие метода оптимизации, которые чаще всего применяются для решения сложных комбинаторных задач: поиск с запретами, имитация отжига, генетический алгоритм и др Четвертая глава посвящена моделям и методам нелинейной оптимизации. Оптимизационная задача относится к классу нелинейных, если хотя бы одно ограничение или целевая функция описываются нелинейными соотношениями. Основной источник таких проблем – это реальные системы и процессы, у которых зависимости между переменными не подчиняются принципу суперпозиции: физика, механика деформируемого тела, управление запасами, популяционная динамика и др.
Главная сложность нелинейных задач – это отсутствие гарантии глобальности оптимума. Поисковый алгоритм может найти ближайший локальный оптимум и предъявить решение задачи, в то время как в области допустимых решений существует точка с намного лучшим или экстремальным значением целевой функции. В четвертой главе приведена классификация методов нелинейного программирования. Обсуждаются самые известные методы одномерной и многомерной безусловной оптимизации. Даны теоретические основы нелинейной оптимизации: условия Каруша-Куна-Таккера (ККТ). Рассматриваются основные подходы к решению задачи условной оптимизации: методы множителей Лагранжа, штрафных и барьерных функций. Четвертая глава – обзорная, она содержит описание ключевых понятий и подходов нелинейного программирования. Ее цель дать представление об общей методологии этого сложнейшего раздела прикладной математики для того, чтобы лучше понимать принципы работы современных солверов и встроенных решателей (IPOPT, SNOPT, MATLAB и др.) Для развития навыков моделирования в последнюю главу включены упражнения для самостоятельного решения. Это, за редким исключением, геометрические задачи, в которых требуется выбрать управляемые параметры и формализовать целевую функцию и ограничения. Большая часть примеров формализуется в терминах нелинейного программирования.
Введение Математическое программирование – это раздел прикладной математики, занимающийся методами поиска экстремумов целевых функций с учетом ограничений на их аргументы. Задачами такого типа изобилует современная общественная практика: планирование перевозок на транспорте и промышленная логистика, оптимальное проектирование технических систем, планирование инвестиций, управление запасами, машинное обучение и др. Математическое программирование дает инструменты для формализации проблемных ситуаций, в которых требуется лучший вариант действий в условиях ограниченных ресурсов. В любой задаче математического программирования должны быть заданы следующие компоненты. 1. Управляемые переменные 1 2 ( , ,..., ) n x x x x , описывающие параметры задачи, влияющие на результат. Например, распределение инвестиций по проектам, множество технических параметров системы и пр. 2. Целевая функция (критерий оптимальности, критерий качества) ( ): n f x R R o , которая формализует представления лица принимающего решение о качестве проекта. В различных ситуациях целевой функцией может служить стоимость, вес, надежность и другие важные характеристики системы или проекта. 3. Система ограничений, описывающая требования, которые предъявляют к решению объективные и субъективные условия: физические законы, технические закономерности, технологические регламенты и др. Обычно систему ограничений записывают в виде равенств и неравенств 1 2 1 2 ( , ,..., ) 0, 1, ; ( , ,..., ) 0, 1, . i n j n g x x x i p h x x x j m d Множество всех точек (векторов) многомерного пространства n R , для которых выполняются все ограничения системы, называется областью допустимых решений D .
При помощи введенных обозначений общую постановку задачи математического программирования можно записать следующим образом. Найти * ( ) ( ) x D f x extr f x или * arg ( ) x D x extr f x . Здесь extr означает максимальное (max) или минимальное (min) значение целевой функции. В зависимости от типа переменных, вида ограничений и свойств целевой функции задачи математического программирования делятся на следующие классы. x Линейное программирование. В задачах этого типа все ограничения и целевая функция являются линейными функциями управляемых переменных. x Нелинейное программирование. К этому классу относятся задачи, у которых хотя бы одно ограничение или целевая функция описываются нелинейными зависимостями. x Дискретное программирование. В этот класс входят задачи, у которых управляемые переменные принимают значения из дискретного множества (конечного или счетного). Обычно это множество неотрицательных целых чисел. x Динамическое программирование. Это раздел математического программирования, в котором рассматриваются способы решения сложных задач при помощи разбиения их на простые подзадачи. Решение исходной задачи синтезируется из сохраненных решений подзадач. Для применения этого метода требуется, чтобы структура задачи удовлетворяла так называемому принципу оптимальности Беллмана. x Стохастическое программирование. Это раздел математического программирования, в котором рассматриваются методы решения
оптимизационных задач в условиях неопределенности. Такая информационная ситуация возникает, когда все или даже некоторые параметры математической модели являются случайными величинами с известными или подлежащими оценке распределениями вероятностей.
Глава 1. Линейное программирование Линейное программирование (ЛП) это раздел математического программирования, который изучает формальные постановки и численные методы решения оптимизационных задач, описываемых линейными ограничениями и линейной целевой функцией. Классическими задачами ЛП являются: x транспортная задача; x распределительная задача; x задачи поиска максимального потока в сети, потока минимальной стоимости и многие другие. К задачам линейного программирования могут быть сведены некоторые важные комбинаторные задачи, например: x задача поиска кратчайшего пути; x задача линейного назначения др. Модели и методы ЛП получили очень большое распространение в математической экономике для планирования и организации производства. 1.1. Формальная постановка задачи линейного программирования Приведем общую формальную постановку задачи линейного программирования (ЗЛП). В ней требуется найти неотрицательные значения управляемых переменных 1 2 , ,..., , 0, 1, n j x x x x j n t , которые удовлетворяют системе линейных ограничений 1 n ij j j a x ¦ ش ib , 1, i m и доставляют экстремальное значение линейной целевой функции вида: 1 ( ) n j j j Z x c x extr o