Экстремальные задачи дискретной математики

С.А. Канцедал

ЭКСТРЕМАЛЬНЫЕ ЗАДАЧИ
ДИСКРЕТНОЙ МАТЕМАТИКИ

Рекомендовано Научно-методическим советом Московского

государственного института электронной техники (технического
университета) в качестве учебника для студентов высших учебных

заведений, обучающихся по техническим специальностям

МОСКВА

ИД «ФОРУМ» — ИНФРА-М

2018

Канцедал С.А.

Экстремальные задачи дискретной математики : учебник /

С.А. Канцедал. — М. : ИД «ФОРУМ» : ИНФРА-М, 2018. —
304 с. — (Высшее образование).

ISBN 978-5-8199-0633-0 (ИД «ФОРУМ»)
ISBN 978-5-16-011183-4 (ИНФРА-М, print)
ISBN 978-5-16-103290-9 (ИНФРА-М, online)

В учебнике систематизированы наиболее известные экстремальные

задачи дискретной математики и описаны лучшие методы их решения.

От других учебник отличается тем, что в нем кроме постановок 

экстремальных задач и изложения методов их решения подробно представлены алгоритмы реализации методов, сопровождающиеся, как правило, численными примерами.

Предназначен студентам высших учебных заведений, обучающихся

по специальности «Прикладная математика».

УДК 22.176я73
ББК 51(075.8)

К19

УДК 22.176я73
ББК 51(075.8)

К19

Издание не подлежит маркировке
в соответствии с п. 1 ч. 4 ст. 11

ФЗ

№ 436-ФЗ

ISBN 978-5-8199-0633-0 (ИД «ФОРУМ»)
ISBN 978-5-16-011183-4 (ИНФРА-М, print) 
© Канцедал С.А., 2016

ISBN 978-5-16-103290-9 (ИНФРА-М, online) 
© ИД «ФОРУМ», 2016

Р е ц е н з е н т ы:

доктор технических наук, профессор Л.Г. Гагарина;
доктор технических наук, профессор  А.В. Панишев

ПРЕДИСЛОВИЕ

Экстремальными задачами в математике принято называть за
дачи на поиск наибольших (наименьших) значений функций, заданных на тех или иных множествах. Они обычно возникают в тех 
сферах человеческой деятельности, которые поддаются строгому 
математическому описанию. Чаще всего это пробле мы планирования и управления в различных отраслях хозяйства, военного дела,
расчетов трассировки прокладываемых коммуникаций, расчетов
направлений выгодного движения транспорта и многие другие задачи, требующие выработки оптимальных решений.
Хотя экстремальные задачи известны математикам давно и для
них найдены универсальные методы решения, новым толчком к 
рассмотрению этих задач и расширению их спектра послужили изменения в экономической деятельности и военной политике, которые пришлись на 40—50-е годы прошлого столетия. Возросшая
конкуренция в производственной сфере, на транспорте, в сфере
услуг, противостояние во внешней политике вынудили менеджеров и лиц, принимающих решения, искать оптимальные пути решения проблем, минимизирующие затраты, сопровождающие эти
решения, или максимизирующие доходы от той или иной деятельности. Для этого был необходим количественный анализ ситуаций
и проблем, который позволяла осуществлять математика. В шутку 
говоря, математический «костыль», на который раньше опирались
физики, механики, строители различных машин и сооружений,
теперь потребовался в космической отрасли, военном деле, планировании производства, транспортных перевозках, прокладке
различ ных энергетических сетей, управлении беспилотными летательными аппаратами и др.

Примерно за 30 лет были созданы тысячи матема тических мо
делей, которые на языке математики описывали различ ные ситуации производственной деятельности и защиты государств. Большая часть этих моделей представляют собой экстремальные задачи,
отражающие стремление принимать оптимальные решения и получать лучшие результаты. Появилось много таких задач, которые
нельзя было решить классическими методами. В связи с этим был
разработан специальный аппарат их решения, известный под названием «математическое программирование», включающий такие

Предисловие

разделы, как линейное, нелинейное и динамическое программирование.

Надо сказать, что успешному созданию аппарата решения не
классических экстремальных задач весьма сильно способствовало
бурное развитие средств вычислительной техники, а именно электронных вычислительных машин (ЭВМ). Только благодаря численным результатам, которые удавалось получать, применяя ЭВМ,
многие методы решения экстремальных задач оказались успешными. Более того, большинство из этих задач реального характера
оказалось возможным решать только на ЭВМ.

Вследствие ускоренного развития прикладной математики об
разовались новые ее разделы, в частности дискретная математика.
В основе этой математики лежит понятие дискретного множества,
а именно на таких множествах определены функции многих сформулированных задач.

Первая глава посвящена изложению тех разделов дискретной
математики, которые максимально необходимы для понимания
сути экстремальных задач и возможных подходов к их решению.
Во второй главе на элементарном уровне описаны общие методы
решения дискретных экстремальных задач. В третьей главе изложены постановки и методы решения экстремальных задач на графах. Четвертая глава — это описание наиболее известных экстремальных задач и методов их решения, ставших уже классическими,
и в дальнейшем называемых традиционными экстремальными задачами дискретной математики.
Учебник ориентирован на учащихся высших учебных заведе
ний, обучающихся по специальности «Прикладная математика».
Он не содержит строгих доказательств, как правило, свойственных 
пособиям такого назначения. Все утверждения, приведенные в
книге и доказанные в свое время различными авторами, следует
принимать на веру. В качестве доказательств и возможности применения на практике методы и алгоритмы решения рассмотренных задач в большинстве случаев иллюстрируются численными
примерами.

Г л а в а  1

МАТЕМАТИЧЕСКИЕ ОСНОВЫ ОПТИМИЗАЦИИ
НА ДИСКРЕТНЫХ МНОЖЕСТВАХ

1.1. Оптимизация и экстремальные задачи

В самом широком смысле под оптимизацией подразумевают
поиск наилучшего из возможного в данной ситуации. В связи с тем
что поиск может быть осуществлен только тогда, когда сущест вуют
различные варианты решения проблемы, порождаемой данной ситуацией, оптимизация принципиально может иметь место только в
том случае, если есть выбор. Это во-первых. Во-вторых, об оптимизации можно говорить тогда и только тогда, когда есть способ
оценки вариантов, применяя который можно сказать, какой из них 
лучше. Иными словами, когда определен критерий оптимизации,
т.е. величина, позволяющая сравнивать варианты.

Разумные люди всегда стремились к оптимизации своего пове
дения: получения наибольшего заработка при ограниченных возможностях, обеспечения наименьших трат денег при покупке определенного набора продуктов питания или вещей, достижения
наименьшего расхода энергии при выполнении тех или иных физических работ, наконец, им не чуждо стремление к известности и
славе. Поэтому с глубокой уверенностью можно сказать, что человек по своей природе естественный оптимизатор.

Вместе с тем практическая сторона оптимизации не так уж 
проста, как кажется. Весьма часто возникают проблемы, связанные с перечислением вариантов выбора. Иногда непросто оценить
эти варианты. Поэтому люди, занятые в управлении производством, строительством, транспортом, ведущие научные исследования, инженеры, экономисты и ученые для рационального решения
проблем оптимизации обратились к количественному их анализу.
Иными словами, для качественного решения этих проблем привлекли математику.

Непосредственно способ привлечения состоял в том, что раз
личные ситуации в той или иной области деятельности, где требовался анализ вариантов принятия решений, стали представлять
как математические задачи поиска лучшего варианта. Процесс
формулировки математической задачи получил название матема

Глава 1.  Математические основы оптимизации на дискретных множествах

тического моделирования, т.е. замены реальной ситуации математическим образом, когда ситуация описывается в математических 
терминах.

Вообще говоря, построение математической модели больше

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

Первые экстремальные задачи были сформулированы еще ан
тичной наукой. Чаще всего они касались максимизации площадей
и объемов. Так, в легенде о финикийской царевне Дидоне, основавшей около 825 года до н.э. город Карфаген, говорится о том,
что, спасаясь от преследований брата-тирана, она покинула родной город Тир и, найдя подходящее место на берегу Средиземного
моря (ныне Тунисский залив), откупила у местного князя столько
земли, сколько можно было покрыть бычьей шкурой. Разрезав
шкуру на тонкие полоски и связав их в один длинный ремень, Дидона окружила им максимальную площадь земли и заложила на
ней крепость Бирса (шкура).

Таким образом, в легенде идет речь о задаче максимизации
площади земли, охватываемой кривой заданной длины (длины
ремня). Говоря современным языком, это изопериметрическая
задача, т.е. задача на отыскание формы замкнутой кривой, отве

1.1. Оптимизация и экстремальные задачи
7

чающей поставленным требованиям, в данном случае кривой, охватывающей максимальную площадь земли. Вариантами решения этой задачи являются различные формы замкнутых кривых, а
оптимальная форма, как известно, представляет собой окружность.

Известна экстремальная задача Евклида, состоящая в том, что
бы в данный треугольник вписать параллелограмм наибольшей
площади. Ее решение такое, что три вершины параллелограмма
должны быть размещены в точках, являющихся серединами сторон треугольника.

Экстремальные задачи геометрического содержания решали

Аполлоний, Кеплер, Ферма, Штейнер и другие известные математики древности, Средневековья и XIX века. Например, Кеплер дал
решение задачи о цилиндре наибольшего объема, вписанном в
шар. Штейнер нашел решение задачи о точке в треугольнике, сумма расстояний от которой до вершин треугольника минимальна.

Вместе с тем до XVII века не было выработано никаких при
нципов решения экстремальных задач. Каждая из них решалась
своим специальным методом. И только в результате работ И. Кеплера, П. Ферма, И. Ньютона, Г. Лейбница постепенно начал формироваться общий подход к их решению, который использовал
дифференцирование оптимизируемых функций.

В то же время кроме экстремальных задач геометрического
толка и весьма редких задач алгебраического содержания возник 
совершенно новый класс задач, получивший впоследствии название экстремальных задач вариационного исчисления. Эти задачи
отличались тем, что поиск экстремальных значений осуществлялся для функционалов, в частности для функций, которые заданы
на множествах непрерывных функций. Родоначальником таких задач стала задача о брахистохроне — поиске кривой наискорейшего
ската, сформулированная И. Бернулли и решенная его братом
Я. Бернулли, Г. Лейбницем и И. Ньютоном. К этому же классу задач относится и изопериметрическая задача, согласно легенде
практически якобы решенная Дидоной.

В связи с тем что законы природы в большинстве своем носят
ограничительный характер (они говорят о том, чего нельзя в принципе сделать, например, нельзя сделать устройство, распространяющее сигнал быстрее скорости света), формулировка реальных 
задач экстремального характера требует ввода ограничений, в пре

Глава 1.  Математические основы оптимизации на дискретных множествах

делах которых ищется экстремум функции. Эти ограничения могут
порождаться непосредственно законами физики или ограниченностью материальных, трудовых, энергетических, финансовых,
транспортных и других видов ресурсов, если экстремальная проблема формулируется в области экономики.

Экстремальные задачи с ограничениями на область поиска

полу чили название задач на условный экстремум. Основополагающий принцип решения таких задач дал Ж. Лагранж, предложивший свое знаменитое правило множителей сначала для экстремальных проблем вариационного характера (1788 г.), а затем
(1797 г.) для аналитических функций. Это правило широко используется и в настоящее время как в практическом аспекте, так и в теоретических исследованиях различных экстремальных задач.
В частности, на него опиралась группа советских математиков во
главе с Л. Понтрягиным при разработке математической теории
оптимального управления [1].

До начала 40-х годов ХХ века экстремальные задачи формули
ровались преимущественно в области математики, физики, техники. Однако в конце 30-х годов этого века появляются задачи из совершенно новой области — экономики. При этом одна из первых 
постановок экстремальных задач экономического содержания и
метод ее решения — разрешающих множителей — принадлежит
советскому математику В. Канторовичу, впоследствии лауреату
Нобелевской премии в области экономики [2].

Экстремальные задачи экономического содержания представ
ляли собой совершенно новый класс экстремальных проблем,
не поддающихся решению методом Лагранжа. В связи с этим потребовались новые подходы к поиску и обоснованию их решений.
За относительно короткий период (40—60-е годы) были найдены
и обоснованы методы решения задач линейного, дискретного и
выпуклого программирования, задач, в которых экстремумы линейных и нелинейных функций требуется найти на конечных и
бесконечных числовых множествах. Методы воплощены в алгоритмы и программы для ЭВМ, в связи с чем получили реальную
оценку эффективности и, таким образом, возможность практического их применения.

Вместе с тем, отвечая на запросы времени — необходимость
оптимально управлять движущимися объектами обороны и сложными технологическими процессами, — математики и инженеры в

1.1. Оптимизация и экстремальные задачи
9

50-х годах разработали аналитические и численные методы управления динамическими объектами: в СССР метод максимума
Л. Понтрягина, в США — динамическое программирование
Р. Беллмана.

Таким образом, к 70-м годам прошлого века на математичес
ком уровне принципиально были решены почти все возникшие в
ХХ веке экстремальные проблемы. По признаку, к какой предметной области они относятся, эти проблемы касаются управления запасами, замены и ремонта оборудования, распределения
ресурсов и назначения, упорядочения действий во времени, массового обслуживания, выбора маршрутов и сетевого планирования, поиска и распознавания образов, определения траекторий
полетов и др.

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

По этому признаку к статическим задачам относятся задачи
математического программирования, к динамическим — задачи
вариационного исчисления и оптимального управления динамическими объектами. В свою очередь, класс задач математического
программирования включает обширные подклассы задач линейного, нелинейного и дискретного программирования. При этом
задачи этого класса отличаются тем, что их оптимизируемые функции определены на непрерывных и дискретных числовых множествах, а также на нечисловых множествах. Это обстоятельство
предъявляет особые требования к поиску экстремумов функций
таких задач.

Если множество определения оптимизируемых функций диск
ретно, то и сами функции дискретны, и к ним неприменимы принципы поиска условного экстремума Ж. Лагранжа, разработанные
для непрерывных множеств и непрерывных дифференцируемых 
функций. Наибольшее (наименьшее) значение такой функции
располагается в какой-то одной точке дискретного множества, которую требуется найти. Поэтому, по существу, все методы поиска
экстремума таких функций так или иначе связаны с полным или
ограниченным перебором точек дискретного множества.

Глава 1.  Математические основы оптимизации на дискретных множествах

1.2. Множества

Дискретная математика представляет собой тот ее раздел, ко
торый опирается на понятие дискретного множества. В свою очередь, под множеством вообще и дискретным в частности подразумевают совокупность вполне определенных и различимых между 
собой объектов любой природы, мыслимых как единое целое [3].
В приведенном определении обычно выделяют три характеристики: множество — это совокупность объектов, объекты различимы
между собой, объекты могут быть любой природы, как реально существующие, так и воображаемые.

Можно указать множество учащихся данного учебного заведе
ния, множество его преподавателей, множество аудиторий, в которых обучаются студенты, множество учебников библиотеки, которыми они пользуются, множество библиотек конкретного
государства, множество автомобилей данного города на текущий
момент, множество футбольных команд, участвующих в розыгрыше кубка лиги чемпионов, множество звезд Солнечной галактики,
множества мужчин и женщин на Земле, живущих в данный момент, множество песчинок на берегу моря и т.д. Все это реально
существующие множества. Их объекты вполне различимы и определенны.

В математике, как науке, основанной на абстракции и вообра
жении, кроме реальных рассматриваются и воображаемые множества. Прежде всего это множества чисел. При этом выделяют
множества натуральных и целых чисел, используемые для осуществления счета, множества правильных дробей и иррациональных 
чисел, введенных для измерения величин, множество комплексных чисел, применяемых в определенных разделах математики.

Объединение множеств натуральных и целых чисел, а также
правильных дробей носит название множества рациональных чисел. Объединение рациональных и иррациональных чисел называется множеством вещественных или действительных чисел. Среди
этих множеств непрерывностью, часто говорят всюду плотностью,
обладают только множества вещественных и комплексных чисел.
Последнее в силу того, что являются производным от множества
действительных чисел. Остальные отдельно взятые множества натуральных и целых чисел, а также правильных дробей этим свойством не обладают.