Экстремальные задачи дискретной математики
Экстремальные задачи дискретной математики: Обзор учебного пособия С.А. Канцедала
Учебное пособие С.А. Канцедала "Экстремальные задачи дискретной математики" представляет собой систематизированное изложение ключевых концепций и методов решения оптимизационных задач, возникающих в условиях дискретных множеств. Ориентированное на студентов технических специальностей, в частности "Прикладная математика", издание отличается подробным представлением алгоритмов реализации методов, сопровождающихся численными примерами, что делает его ценным ресурсом для практического применения.
Основы оптимизации и дискретные структуры
Книга начинается с введения в математические основы оптимизации, определяя экстремальные задачи как поиск наибольших или наименьших значений функций на заданных множествах. Особое внимание уделяется эволюции этих задач от античных времен до современных проблем планирования и управления, подчеркивая роль математического программирования и вычислительной техники в их решении. Автор акцентирует внимание на принципиальном отличии дискретных экстремальных задач от непрерывных, где классические методы дифференцирования неприменимы, и основным подходом становится перебор вариантов.
В первой главе подробно рассматриваются фундаментальные понятия дискретной математики: множества, их свойства и операции, а также теория графов. Графы представлены как мощный инструмент для моделирования отношений между объектами, описываются различные их типы (ориентированные, неориентированные, мультиграфы, псевдографы), ключевые характеристики (степень вершины, связность, циклы) и специальные структуры (деревья, сети). Важной частью является обсуждение способов представления графов для компьютерной обработки, таких как матрицы смежности и списки смежности, с акцентом на их влияние на эффективность алгоритмов. Завершает главу обзор линейной алгебры, включая векторы, матрицы и системы линейных уравнений, как базового аппарата для последующего изложения методов оптимизации.
Методы и алгоритмы решения дискретных задач
Вторая глава посвящена общим методам и алгоритмам решения дискретных экстремальных задач. Автор разъясняет различия между "методом" и "алгоритмом", подчеркивая требования к алгоритмам для их эффективной реализации на ЭВМ (вход/выход, конечность, детерминированность, результативность). Рассматриваются различные способы представления алгоритмов (графический, текстовый, программный) и методы оценки их временной сложности (теоретический и экспериментальный анализ, порядковые оценки). Вводится классификация алгоритмов на полиномиальные и экспоненциальные, что имеет критическое значение для понимания практической применимости решений.
Значительное место уделено линейному программированию (ЛП), его постановке, математической формулировке и симплекс-методу. Подробно анализируется геометрическая интерпретация задач ЛП, концепция опорных решений и теорема двойственности. Отдельно рассматривается целочисленное линейное программирование (ЦЛП), где переменные должны принимать целые значения. Автор описывает методы отсечений (Гомори) и метод ветвей и границ как основные подходы к решению ЦЛП, иллюстрируя их геометрической интерпретацией. Завершает главу динамическое программирование, представленное как универсальная схема для оптимизации многошаговых процессов, с акцентом на принцип оптимальности Беллмана и его применение.
Традиционные экстремальные задачи
Третья и четвертая главы посвящены конкретным экстремальным задачам дискретной математики. В третьей главе рассматриваются задачи на графах: построение кратчайшего остовного дерева (алгоритмы Прима и Крускала), поиск кратчайших и максимальных путей (алгоритм Дейкстры, динамическое программирование), задачи о наименьших покрытиях (сведение к ЦЛП, прямой перебор), раскраска графов и задачи о потоках в сетях (алгоритм Форда-Фалкерсона). Для каждой задачи приводятся практические примеры и обсуждаются особенности алгоритмов.
Четвертая глава охватывает "традиционные" экстремальные задачи: задачу о назначениях (венгерский метод, алгоритм Мака), задачу о рюкзаке (методы ветвей и границ, динамическое программирование, приближенные алгоритмы) и задачу коммивояжера (динамическое программирование, алгоритм Литтля, методы ветвей и границ с устранением циклов и штрафованием вершин). Особое внимание уделяется задачам составления расписаний, включая упорядочение работ для одной машины, конвейерные и общие задачи, с рассмотрением алгоритма Джонсона и различных эвристических правил. Для многих задач представлены сравнительные характеристики алгоритмов, их временная сложность и практическая применимость.
В целом, учебное пособие С.А. Канцедала является всеобъемлющим руководством по экстремальным задачам дискретной математики, сочетающим теоретические основы с практическими аспектами реализации алгоритмов. Оно предоставляет студентам глубокое понимание предмета и развивает навыки решения сложных оптимизационных задач.
- ВО - Бакалавриат
- 01.03.01: Математика
- 01.03.02: Прикладная математика и информатика
- 01.03.04: Прикладная математика
- 02.03.01: Математика и компьютерные науки
- 03.03.01: Прикладные математика и физика
- 03.03.02: Прикладная математика и информатика
- ВО - Магистратура
- 01.04.01: Математика
- 01.04.02: Прикладная математика и информатика
- 01.04.04: Прикладная математика
- 02.04.01: Математика и компьютерные науки
- 03.04.01: Прикладные математика и физика
ЭКСТРЕМАЛЬНЫЕ ЗАДАЧИ ДИСКРЕТНОЙ МАТЕМАТИКИ С.А. КАНЦЕДАЛ Рекомендовано Научно-методическим советом Московского государственного института электронной техники (технического университета) в качестве учебника для студентов высших учебных заведений, обучающихся по техническим специальностям Москва ИД «ФОРУМ» — ИНФРА-М 2026 УЧЕБНОЕ ПОСОБИЕ
УДК 22.176(075.8) ББК 51я73 К19 Канцедал С.А. К19 Экстремальные задачи дискретной математики : учебное пособие / С.А. Канцедал. — Москва : ИД «ФОРУМ» : ИНФРА-М, 2026. — 304 с. — (Высшее образование). ISBN 978-5-8199-0633-0 (ИД «ФОРУМ») ISBN 978-5-16-011183-4 (ИНФРА-М, print) ISBN 978-5-16-103290-9 (ИНФРА-М, online) В учебном пособии систематизированы наиболее известные экстремальные задачи дискретной математики и описаны лучшие методы их решения. От других учебник отличается тем, что в нем кроме постановок экстремальных задач и изложения методов их решения подробно представлены алгоритмы реализации методов, сопровождающиеся, как правило, численными примерами. Предназначен студентам высших учебных заведений, обучающихся по специальности «Прикладная математика». УДК 22.176(075.8) ББК 51я73 Р е ц е н з е н т ы: Гагарина Л.Г., доктор технических наук, профессор; Панышее А.В., доктор технических наук, профессор ISBN 978-5-8199-0633-0 (ИД «ФОРУМ») ISBN 978-5-16-011183-4 (ИНФРА-М, print) ISBN 978-5-16-103290-9 (ИНФРА-М, online) © Канцедал С.А., 2016 © ИД «ФОРУМ», 20216
ПРЕДИСЛОВИЕ Экстремальными задачами в математике принято называть задачи на поиск наибольших (наименьших) значений функций, заданных на тех или иных множествах. Они обычно возникают в тех сферах человеческой деятельности, которые поддаются строгому математическому описанию. Чаще всего это пробле мы планирования и управления в различных отраслях хозяйства, военного дела, расчетов трассировки прокладываемых коммуникаций, расчетов направлений выгодного движения транспорта и многие другие задачи, требующие выработки оптимальных решений. Хотя экстремальные задачи известны математикам давно и для них найдены универсальные методы решения, новым толчком к рассмотрению этих задач и расширению их спектра послужили изменения в экономической деятельности и военной политике, которые пришлись на 40—50-е годы прошлого столетия. Возросшая конкуренция в производственной сфере, на транспорте, в сфере услуг, противостояние во внешней политике вынудили менеджеров и лиц, принимающих решения, искать оптимальные пути решения проблем, минимизирующие затраты, сопровождающие эти решения, или максимизирующие доходы от той или иной деятельности. Для этого был необходим количественный анализ ситуаций и проблем, который позволяла осуществлять математика. В шутку говоря, математический «костыль», на который раньше опирались физики, механики, строители различных машин и сооружений, теперь потребовался в космической отрасли, военном деле, планировании производства, транспортных перевозках, прокладке различ ных энергетических сетей, управлении беспилотными летательными аппаратами и др. Примерно за 30 лет были созданы тысячи матема тических моделей, которые на языке математики описывали различ ные ситуации производственной деятельности и защиты государств. Большая часть этих моделей представляют собой экстремальные задачи, отражающие стремление принимать оптимальные решения и получать лучшие результаты. Появилось много таких задач, которые нельзя было решить классическими методами. В связи с этим был разработан специальный аппарат их решения, известный под названием «математическое программирование», включающий такие
Предисловие разделы, как линейное, нелинейное и динамическое программирование. Надо сказать, что успешному созданию аппарата решения неклассических экстремальных задач весьма сильно способствовало бурное развитие средств вычислительной техники, а именно электронных вычислительных машин (ЭВМ). Только благодаря численным результатам, которые удавалось получать, применяя ЭВМ, многие методы решения экстремальных задач оказались успешными. Более того, большинство из этих задач реального характера оказалось возможным решать только на ЭВМ. Вследствие ускоренного развития прикладной математики образовались новые ее разделы, в частности дискретная математика. В основе этой математики лежит понятие дискретного множества, а именно на таких множествах определены функции многих сформулированных задач. Первая глава посвящена изложению тех разделов дискретной математики, которые максимально необходимы для понимания сути экстремальных задач и возможных подходов к их решению. Во второй главе на элементарном уровне описаны общие методы решения дискретных экстремальных задач. В третьей главе изложены постановки и методы решения экстремальных задач на графах. Четвертая глава — это описание наиболее известных экстремальных задач и методов их решения, ставших уже классическими, и в дальнейшем называемых традиционными экстремальными задачами дискретной математики. Учебник ориентирован на учащихся высших учебных заведений, обучающихся по специальности «Прикладная математика». Он не содержит строгих доказательств, как правило, свойственных пособиям такого назначения. Все утверждения, приведенные в книге и доказанные в свое время различными авторами, следует принимать на веру. В качестве доказательств и возможности применения на практике методы и алгоритмы решения рассмотренных задач в большинстве случаев иллюстрируются численными примерами.
Г л а в а 1 МАТЕМАТИЧЕСКИЕ ОСНОВЫ ОПТИМИЗАЦИИ НА ДИСКРЕТНЫХ МНОЖЕСТВАХ 1.1. Оптимизация и экстремальные задачи В самом широком смысле под оптимизацией подразумевают поиск наилучшего из возможного в данной ситуации. В связи с тем что поиск может быть осуществлен только тогда, когда сущест вуют различные варианты решения проблемы, порождаемой данной ситуацией, оптимизация принципиально может иметь место только в том случае, если есть выбор. Это во-первых. Во-вторых, об оптимизации можно говорить тогда и только тогда, когда есть способ оценки вариантов, применяя который можно сказать, какой из них лучше. Иными словами, когда определен критерий оптимизации, т.е. величина, позволяющая сравнивать варианты. Разумные люди всегда стремились к оптимизации своего поведения: получения наибольшего заработка при ограниченных возможностях, обеспечения наименьших трат денег при покупке определенного набора продуктов питания или вещей, достижения наименьшего расхода энергии при выполнении тех или иных физических работ, наконец, им не чуждо стремление к известности и славе. Поэтому с глубокой уверенностью можно сказать, что человек по своей природе естественный оптимизатор. Вместе с тем практическая сторона оптимизации не так уж проста, как кажется. Весьма часто возникают проблемы, связанные с перечислением вариантов выбора. Иногда непросто оценить эти варианты. Поэтому люди, занятые в управлении производством, строительством, транспортом, ведущие научные исследования, инженеры, экономисты и ученые для рационального решения проблем оптимизации обратились к количественному их анализу. Иными словами, для качественного решения этих проблем привлекли математику. Непосредственно способ привлечения состоял в том, что различные ситуации в той или иной области деятельности, где требовался анализ вариантов принятия решений, стали представлять как математические задачи поиска лучшего варианта. Процесс формулировки математической задачи получил название матема
тического моделирования, т.е. замены реальной ситуации математическим образом, когда ситуация описывается в математических терминах. Вообще говоря, построение математической модели больше дело искусства, чем рутины. Для этого требуется и глубокое знание реальной ситуации, где нужен выбор варианта, и высокая математическая культура, и опыт. Обычно начинают с разложения реальной ситуации на простейшие элементы, анализа элементов, установления связей между ними, математической интерпретации связей. Как правило, вводят набор переменных, которые могут изменяться в определенных пределах, и функций, которые отображают некоторые количественные характеристики вариантов. Определяют формы связи между переменными, которыми чаще всего служат уравнения. В результате получают математическую структуру с набором связанных между собой переменных и математическое выражение критерия оптимизации. Как правило, это выражение представляет собой числовую функцию, заданную на ограниченном числовом множестве, или функционал-числовую функцию, заданную на произвольном множестве, наибольшее либо наименьшее — экстремальное (крайнее), значение которых требуется найти, изменяя переменные. Такого рода модели получили название экстремальных задач, а функции — оптимизируемых. Весьма часто их также называют целевыми функциями, поскольку их запись выражает цель оптимизации. Первые экстремальные задачи были сформулированы еще античной наукой. Чаще всего они касались максимизации площадей и объемов. Так, в легенде о финикийской царевне Дидоне, основавшей около 825 года до н.э. город Карфаген, говорится о том, что, спасаясь от преследований брата-тирана, она покинула родной город Тир и, найдя подходящее место на берегу Средиземного моря (ныне Тунисский залив), откупила у местного князя столько земли, сколько можно было покрыть бычьей шкурой. Разрезав шкуру на тонкие полоски и связав их в один длинный ремень, Дидона окружила им максимальную площадь земли и заложила на ней крепость Бирса (шкура). Таким образом, в легенде идет речь о задаче максимизации площади земли, охватываемой кривой заданной длины (длины ремня). Говоря современным языком, это изопериметрическая задача, т.е. задача на отыскание формы замкнутой кривой, отве
1.1. Оптимизация и экстремальные задачи чающей поставленным требованиям, в данном случае кривой, охватывающей максимальную площадь земли. Вариантами решения этой задачи являются различные формы замкнутых кривых, а оптимальная форма, как известно, представляет собой окружность. Известна экстремальная задача Евклида, состоящая в том, чтобы в данный треугольник вписать параллелограмм наибольшей площади. Ее решение такое, что три вершины параллелограмма должны быть размещены в точках, являющихся серединами сторон треугольника. Экстремальные задачи геометрического содержания решали Аполлоний, Кеплер, Ферма, Штейнер и другие известные математики древности, Средневековья и XIX века. Например, Кеплер дал решение задачи о цилиндре наибольшего объема, вписанном в шар. Штейнер нашел решение задачи о точке в треугольнике, сумма расстояний от которой до вершин треугольника минимальна. Вместе с тем до XVII века не было выработано никаких принципов решения экстремальных задач. Каждая из них решалась своим специальным методом. И только в результате работ И. Кеплера, П. Ферма, И. Ньютона, Г. Лейбница постепенно начал формироваться общий подход к их решению, который использовал дифференцирование оптимизируемых функций. В то же время кроме экстремальных задач геометрического толка и весьма редких задач алгебраического содержания возник совершенно новый класс задач, получивший впоследствии название экстремальных задач вариационного исчисления. Эти задачи отличались тем, что поиск экстремальных значений осуществлялся для функционалов, в частности для функций, которые заданы на множествах непрерывных функций. Родоначальником таких задач стала задача о брахистохроне — поиске кривой наискорейшего ската, сформулированная И. Бернулли и решенная его братом Я. Бернулли, Г. Лейбницем и И. Ньютоном. К этому же классу задач относится и изопериметрическая задача, согласно легенде практически якобы решенная Дидоной. В связи с тем что законы природы в большинстве своем носят ограничительный характер (они говорят о том, чего нельзя в принципе сделать, например, нельзя сделать устройство, распространяющее сигнал быстрее скорости света), формулировка реальных задач экстремального характера требует ввода ограничений, в пре
делах которых ищется экстремум функции. Эти ограничения могут порождаться непосредственно законами физики или ограниченностью материальных, трудовых, энергетических, финансовых, транспортных и других видов ресурсов, если экстремальная проблема формулируется в области экономики. Экстремальные задачи с ограничениями на область поиска полу чили название задач на условный экстремум. Основополагающий принцип решения таких задач дал Ж. Лагранж, предложивший свое знаменитое правило множителей сначала для экстремальных проблем вариационного характера (1788 г.), а затем (1797 г.) для аналитических функций. Это правило широко используется и в настоящее время как в практическом аспекте, так и в теоретических исследованиях различных экстремальных задач. В частности, на него опиралась группа советских математиков во главе с Л. Понтрягиным при разработке математической теории оптимального управления [1]. До начала 40-х годов ХХ века экстремальные задачи формулировались преимущественно в области математики, физики, техники. Однако в конце 30-х годов этого века появляются задачи из совершенно новой области — экономики. При этом одна из первых постановок экстремальных задач экономического содержания и метод ее решения — разрешающих множителей — принадлежит советскому математику В. Канторовичу, впоследствии лауреату Нобелевской премии в области экономики [2]. Экстремальные задачи экономического содержания представляли собой совершенно новый класс экстремальных проблем, не поддающихся решению методом Лагранжа. В связи с этим потребовались новые подходы к поиску и обоснованию их решений. За относительно короткий период (40—60-е годы) были найдены и обоснованы методы решения задач линейного, дискретного и выпуклого программирования, задач, в которых экстремумы линейных и нелинейных функций требуется найти на конечных и бесконечных числовых множествах. Методы воплощены в алгоритмы и программы для ЭВМ, в связи с чем получили реальную оценку эффективности и, таким образом, возможность практического их применения. Вместе с тем, отвечая на запросы времени — необходимость оптимально управлять движущимися объектами обороны и сложными технологическими процессами, — математики и инженеры в
1.1. Оптимизация и экстремальные задачи 50-х годах разработали аналитические и численные методы управления динамическими объектами: в СССР метод максимума Л. Понтрягина, в США — динамическое программирование Р. Беллмана. Таким образом, к 70-м годам прошлого века на математическом уровне принципиально были решены почти все возникшие в ХХ веке экстремальные проблемы. По признаку, к какой предметной области они относятся, эти проблемы касаются управления запасами, замены и ремонта оборудования, распределения ресурсов и назначения, упорядочения действий во времени, массового обслуживания, выбора маршрутов и сетевого планирования, поиска и распознавания образов, определения траекторий полетов и др. По другому признаку экстремальные задачи делят на статические и динамические. Идея статической оптимизации состоит в том, что экстремум функции ищется в заданный момент времени. Динамические экстремальные задачи отражают стремление получить наибольшее (наименьшее) значение функции на протяжении некоторого наперед заданного промежутка времени. По этому признаку к статическим задачам относятся задачи математического программирования, к динамическим — задачи вариационного исчисления и оптимального управления динамическими объектами. В свою очередь, класс задач математического программирования включает обширные подклассы задач линейного, нелинейного и дискретного программирования. При этом задачи этого класса отличаются тем, что их оптимизируемые функции определены на непрерывных и дискретных числовых множествах, а также на нечисловых множествах. Это обстоятельство предъявляет особые требования к поиску экстремумов функций таких задач. Если множество определения оптимизируемых функций дискретно, то и сами функции дискретны, и к ним неприменимы принципы поиска условного экстремума Ж. Лагранжа, разработанные для непрерывных множеств и непрерывных дифференцируемых функций. Наибольшее (наименьшее) значение такой функции располагается в какой-то одной точке дискретного множества, которую требуется найти. Поэтому, по существу, все методы поиска экстремума таких функций так или иначе связаны с полным или ограниченным перебором точек дискретного множества.
1.2. Множества Дискретная математика представляет собой тот ее раздел, который опирается на понятие дискретного множества. В свою очередь, под множеством вообще и дискретным в частности подразумевают совокупность вполне определенных и различимых между собой объектов любой природы, мыслимых как единое целое [3]. В приведенном определении обычно выделяют три характеристики: множество — это совокупность объектов, объекты различимы между собой, объекты могут быть любой природы, как реально существующие, так и воображаемые. Можно указать множество учащихся данного учебного заведения, множество его преподавателей, множество аудиторий, в которых обучаются студенты, множество учебников библиотеки, которыми они пользуются, множество библиотек конкретного государства, множество автомобилей данного города на текущий момент, множество футбольных команд, участвующих в розыгрыше кубка лиги чемпионов, множество звезд Солнечной галактики, множества мужчин и женщин на Земле, живущих в данный момент, множество песчинок на берегу моря и т.д. Все это реально существующие множества. Их объекты вполне различимы и определенны. В математике, как науке, основанной на абстракции и воображении, кроме реальных рассматриваются и воображаемые множества. Прежде всего это множества чисел. При этом выделяют множества натуральных и целых чисел, используемые для осуществления счета, множества правильных дробей и иррациональных чисел, введенных для измерения величин, множество комплексных чисел, применяемых в определенных разделах математики. Объединение множеств натуральных и целых чисел, а также правильных дробей носит название множества рациональных чисел. Объединение рациональных и иррациональных чисел называется множеством вещественных или действительных чисел. Среди этих множеств непрерывностью, часто говорят всюду плотностью, обладают только множества вещественных и комплексных чисел. Последнее в силу того, что являются производным от множества действительных чисел. Остальные отдельно взятые множества натуральных и целых чисел, а также правильных дробей этим свойством не обладают.