Модели и методы дискретной оптимизации. Модули 1 и 2

В.А. Овчинников

Модели и методы дискретной оптимизации

Модули 1 и 2

Допущено 
Федеральным учебно-методическим объединением 
в системе высшего образования по укрупненной группе специальностей 
и направлений подготовки 09.00.00 «Информатика и вычислительная 
техника» в качестве учебника для лиц (студентов, аспирантов, 
адъюнктов), обучающихся по основным образовательным программам 
высшего образования по направлению подготовки магистратуры 09.04.01 
«Информатика и вычислительная техника»

 
© Овчинников В.А., 2019

 
© Оформление. Издательство

ISBN 978-5-7038-5105-0 
 
МГТУ им. Н.Э. Баумана, 2019

УДК 004.02 + 519.1(075.8)
ББК 22.176
 
О-35

Издание доступно в электронном виде по адресу  
ebooks.bmstu.press/catalog/255/book2061.html

Овчинников, В. А.
О-35  
Модели и методы дискретной оптимизации. Модули 1 и 2 : учебник / 

В. А. Овчинников. — Москва : Издательство МГТУ им. Н. Э. Баумана, 
2019. — 277, [1] с. : ил. 

ISBN 978-5-7038-5105-0
Изложен ряд основных разделов теории графов, необходимых для разработки 

моделей объектов и задач дискретной оптимизации. Рассмотрены модели структур 
сложных систем в виде различного вида графов: ультра-, гипер-, ориентированных 
и неориентированных, а также формальные постановки задач комбинаторной 
оптимизации на графах. Описаны особенности и сущность точных методов 
дискретной оптимизации, таких как жадный выбор, поиск в ширину и в глубину с 
возвращением, ветвей и границ, Дейкстры, Форда — Фалкерсона и динамического 
программирования.

Для студентов, обучающихся по направлению подготовки «Информатика и 

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

УДК 004.02 + 519.1(075.8)
ББК 22.176

Предисловие

Учебник предназначен для углубления знаний, полученных при освоении лекционного материала, а также самостоятельного изучения студентами дисциплины «Модели и методы дискретной оптимизации», входящей 
в основную образовательную программу подготовки магистров в МГТУ 
им. Н.Э. Баумана по направлению 09.04.01 «Информатика и вычислительная техника».
Цель изучения дисциплины — усвоение теоретических знаний, необходимых для постановки и решения нетривиальных комбинаторно-оптимизационных задач проектирования сложных систем, формирование умений и 
навыков формализации задач проектирования, выбора и реализации методов 
их решения.

Планируемые результаты обучения 

После изучения дисциплины студенты овладеют:
 • базовыми знаниями о математических моделях объектов и задачах 
дискретной оптимизации, а также методах решения последних;

 • методиками анализа объектов и задач структурного синтеза;
 • практическими навыками формализации объектов и задач и применения методов дискретной оптимизации.
Для изучения дисциплины необходимо предварительное освоение следующих 
дисциплин:
Иностранный язык («Профессиональная и научная терминология»);
Дискретная математика;
Информатика;
Вычислительные системы;
Сетевые базы данных;
Глобальные сети;
Проектирование интеллектуальных систем;
Методология научного познания;
Управление проектированием информационных систем.

Методические указания по освоению материала учебника 

Дисциплина «Модели и методы дискретной оптимизации» состоит из 
двух модулей. 
Модуль 1 «Задачи дискретной оптимизации, модели их объектов и формальная постановка задач» включает главы 1–4. В нем рассмотрен ряд задач 
дискретной оптимизации и описаны классы их сложности; изложены основные понятия теории графов, причем особое внимание уделено гипер- и 
ультраграфам; приведена методика перехода от описания объекта проектирования к его математической модели в виде того или иного графа; рассмотрены 
модели объектов различных предметных областей; приведены формальные 
постановки широкого круга прикладных задач.

Предисловие

Модуль 2 «Точные методы дискретной оптимизации и способы сни
жения вычислительной сложности алгоритмов» включает главы 5–7. В нем 
изложены точные методы решения задач дискретной оптимизации; описаны 
алгоритмы реализации некоторых операций над графами, которые необходимы для выполнения проектных процедур преобразования структур сложных систем по их моделям; рассмотрены способы снижения вычислительной 
сложности алгоритмов. 
Каждый модуль является логически завершенным разделом дисциплины. 
Для каждого модуля приводится набор планируемых результатов обучения, 
заданных программой дисциплины. 
Для закрепления усвоенной информации, приобретения навыков 
ее применения для решения практических задач в предметной области 
дисциплины по каждому модулю проводятся семинарские занятия с 
элементами дискуссии. 
Главы учебника необходимо прорабатывать последовательно, так как 
каждая из них обеспечивает успешное восприятие материала.
Основные понятия математических основ дисциплины, модели объектов 
и задач дискретной оптимизации и методы их решения проиллюстрированы 
примерами. Для успешного усвоения материала необходимо внимательно 
разбирать примеры, целесообразно синтезировать и прорабатывать 
аналогичные примеры. Новые термины следует оформлять в виде глоссария, 
а изученный материал – в виде концептуальной карты (карты памяти).
В конце каждой главы (за исключением главы 1) приведены контрольные 
вопросы и задания, которые необходимо проработать. Ответы на вопросы 
позволят обучающемуся самому оценить степень понимания и усвоения 
теоретических положений, методик и методов решения задач дискретной 
оптимизации. Выполнение заданий обеспечит приобретение умений 
и навыков, необходимых для постановки и решения задач дискретной 
оптимизации в различных предметных областях.
При изучении студентами дисциплины для оценки степени понимания 
и освоения теоретических положений, методик и методов решения задач 
дискретной оптимизации, приобретения умений и навыков, указанных в 
программе, проводится текущий контроль в виде рейтингов. 
Рекомендуется использовать интернет-ресурсы, например [27–30].

Условные обозначения1

X  — множество вершин графа
X  — мощность множества X
U  — множество ребер графа
U  — мощность множества U
∅  — пустое множество
UN  — универсальное множество
H
X U
U (
,
) — ультраграф

H X U
(
,
)  — гиперграф

G
X U
→(
,
) — ориентированный граф

G
X U
(
,
)  — неориентированный граф

≅  — символ изоморфизма графов 
x
X
i ∈
 — вершина xi  принадлежит множеству X

x
X
i ∉
 — вершина xi  не принадлежит множеству X

u
U
j ∈
 — ребро uj  принадлежит множеству U

u
U
j ∉
 — ребро uj  не принадлежит множеству U

x x
x
1
2
3
,
,
{
}  — множество, состоящее из элементов x x
x
1
2
3
,
,

<
>
x x
x
1
2
3
,
,
 — кортеж элементов x x
x
1
2
3
,
,

X
x
X
i
k
=
∈
{
}
: ...  — множество Xi,  состоящее из тех элементов множества X, 
для которых выполняется условие, указанное после двоеточия

Г1 X U
,
(
)  — двуместный предикат «вершинам множества X инцидентны ребра 
множества U»

Г1 x U
i,
(
)  — одноместный предикат-свойство «вершине xi  инцидентны ребра 
множества U»

Г1
1
− ( ,
)
U X  — двуместный предикат «ребра множества U инцидентны вершинам множества X», обратный к предикату Г1 X U
,
(
)

Г1
1
− (
,
)
u
X
j
 — одноместный предикат-свойство «ребро uj  инцидентно вершинам множества X»

Г2 U X
,
(
)  — двуместный предикат «ребрам множества xi  инцидентны вершины множества X»

Г2 u
X
j,
(
)  — одноместный предикат-свойство «ребру uj  инцидентны вершины множества X»

Г2

1
− (
,
)
X U
 — двуместный предикат «вершины множества X инцидентны 
ребрам множества U», обратный к предикату Г2 U X
,
(
)

Г2
1
− (
,
)
x U
i
 — одноместный предикат-свойство «вершина xi  инцидентна 
ребрам множества U»

Г1 x
U
i
i
( ) =
+  — образ вершины xi  относительно предиката Г1 X U
,
,
(
)  т. е. инцидентные ей ребра

Г1X  — множество образов вершин x
X
∈
 относительно предиката Г1 X U
,
(
)

Г2
1
−
−
( ) =
x
U
i
i  — прообраз вершины xi  относительно предиката Г2 U X
,
,
(
)  т. е. 
ребра, которым она инцидентна

1 Условные обозначения приведены в порядке появления их в тексте.

Условные обозначения

Г2X  — множество прообразов вершин x
X
∈
относительно предиката 

Г1 X U
,
(
)

Г2 u
X
j
j
(
) =
+  — образ ребра uj  относительно предиката Г2 U X
,
,
(
)  т. е. вершины, инцидентные ему

Г2U  — множество образов ребер u
U
∈
 относительно предиката Г2 U X
,
(
)

Г1
1
−
−
(
) =
u
X
j
j  — прообраз ребра uj  относительно предиката Г1 X U
,
,
(
)  т. е. 

вершины, которым оно инцидентно

Г1U  — множество прообразов ребер относительно предиката Г2 U X
,
(
)

P X U X
,
,
(
)  — трехместный предикат-инцидентор

F X X
1
,
(
)  — двуместный предикат смежности вершин множества X

F
X X
1
1
− (
)
,
 — предикат, обратный к предикату F X X
1
,
(
)

F U U
2
,
(
)  — двуместный предикат смежности ребер множества U

F
U U
2
1
− (
)
,
 — предикат, обратный к предикату F U U
2
,
(
)

F x
X
i
i
1 ( ) =
+ — образ вершины xi  относительно предиката смежности F X X
1
,
,
(
)  

т. е. смежные ей вершины

F X
1
 — множество образов вершин x
X
∈
 относительно предиката смежности 

F X X
1
,
(
)

F
x
X
i
i
1
1
−
−
( ) =
 — прообраз вершины xi  относительно предиката смежности 

F X X
1
,
,
(
)  т. е. вершины, которым она смежна

F
X
1
1
−
 — множество прообразов вершин x
X
∈
 относительно предиката 

смежности F X X
1
,
(
)

F
uj
2 (
)  — образ ребра uj  относительно предиката F U U
2
,
,
(
)  т. е. смежные ему 

ребра

F U
2
 — множества образов ребер u
U
j ∈
 относительно предиката смежности 

F U U
2
,
(
)

F
uj
2
1
− (
)  = U j
−  — прообраз ребра uj относительно предиката F U U
2
,
(
)

F U
2

1
−
 — множество прообразов ребер uj ∈ U относительно предиката смежности F U U
2
,
(
)

• — символ операции композиции предикатов
X
X
j ⊂
 — множество X j  является подмножеством множества X (включено 
в X)

X
X
j ⊆
 — множество X j  включено в множество X или совпадает с ним

X
X
1
2
∪
 — объединение множеств X1  и X 2

X
X
1
2
∩
 — пересечение множеств X1  и X 2

• — символ операции конкатенации множеств
Г
Г
1
1
X
xi
x
X
i

( ) =
( )

∈
 — объединение образов вершин x
X
i ∈

P X
( )  и Q X
( )  — одноместные предикаты (предикаты-свойства)

P  и Q  — характеристические множества предикатов P X
( )  и Q X
( ),  состоящие из тех элементов множества X, для которых P x
( )  и Q x
( )принимают значение «истина»

P
Q
\
 — разность множеств P и Q 
P∆Q — симметрическая разность множеств P и Q
∃ — квантор существования (∃x  — существует x)
∀  — квантор всеобщности (∀x  — для любого x)

Введение

Задачи дискретной оптимизации возникают при разработке практически 
любых объектов или систем на всех этапах, начиная с эскизного проектирования 
и кончая выпуском конструкторской документации в различных предметных 
областях. Укажем в качестве примера некоторые из них:

 • определение оптимального, в смысле некоторого критерия, положения 
элементов структуры объекта и связей между ними в монтажном пространстве некоторого другого объекта;

 • разделение структуры объекта на части (декомпозиция) или объединение элементов структуры в «устойчивые» группы (композиция) таким 
образом, чтобы критерий оптимальности достигал экстремального значения;

 • установление идентичности структур сложных систем;
 • анализ и оптимизирующие преобразования алгоритмов;
 • определение максимально возможного количества параллельных процессов и распознавание зашумленных сообщений;

 • выделение в системе минимального количества подсистем, к которым 
подсоединены все линии связи;

 • определение минимального количества подсистем системы, на которые надо установить обслуживающие аппараты, причем любая из оставшихся 
подсистем должна быть связана с каким-либо из обслуживающих аппаратов;

 • определение максимального потока в сети.
Подготовка к решению задач анализа и синтеза структур сложных систем 
предполагает выполнение следующих основных этапов:
1) анализ содержательной постановки задачи с целью определения 
свойств и характеристик компонент объекта, необходимых для решения 
задачи;
2) разработка модели объекта проектирования;
3) формальная постановка задачи;
4) выбор метода решения задачи.
Из ранних работ, посвященных комбинаторно-оптимизационным 
задачам, можно отметить [6, 9, 20, 22, 25], современной фундаментальной 
книгой является [2].
При решении задач в качестве аппарата формализации объектов проектирования широко применяется теория графов. Аппарат теории графов 
глубоко развит, определены операции на графах, сформулированы теоремы, 
леммы и т. п., разработано много алгоритмов решения различных задач структурного синтеза. Использование графов для формального описания объекта 
проектирования должно обеспечивать:

 • получение моделей, адекватных объекту в смысле полноты и правильности отображения информации, которая требуется для решения проектной 
задачи;

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

Введение

Основное ядро теории графов составляют неориентированные и 
ориентированные графы. Гипер- и особенно ультраграфы исследованы в 
меньшей степени. В то же время адекватной моделью систем, в которых 
существуют соединения трех и более подсистем, может быть только 
гипер- или ультраграф. Операции, определенные над ориентированными 
и неориентированными графами, во-первых, нелегко распространить на 
ультра- и гиперграфы, а во-вторых, не охватывают широкий круг процедур 
преобразования исходного описания объектов проектирования.
В книгах по дискретной математике за редким исключением не 
затрагиваются вопросы перехода от объекта к его адекватной модели. 
Отсутствует систематическое изложение формальных постановок задач 
структурного синтеза, ориентированных на применение комбинаторных 
методов их решения.
Анализ работ [1–9, 20, 21], в которых описываются точные методы 
комбинаторной оптимизации, позволяет сделать следующие выводы:

 • непрерывно расширяется круг применения классических методов дискретной оптимизации при возрастании размерности проектируемых систем;

 • не существует источников, в которых систематически и в полном объеме излагаются методы решения комбинаторно-оптимизационных задач;

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

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

Модуль 1
Задачи дискретной оптимизации, модели их объектов  
и формальная постановка задач

В главе 1 модуля рассмотрен ряд задач дискретной оптимизации, относящихся 
к различным предметным областям. Указаны их характерные признаки и соответствующие им задачи теории графов. Дана общая характеристика комбинаторно-оптимизационной задачи структурного синтеза. Перечислены и подробно изложены этапы 
решения прикладной задачи структурного синтеза. Определено понятие вычислительной сложности алгоритма. Описаны классы P, NP и NP-полных задач дискретной 
оптимизации. Рассмотрены некоторые наиболее известные NP-полные задачи.
Глава 2 посвящена изложению основных понятий теории графов. Особое 
внимание уделено ультра- и гиперграфам. В главе использован материал первого 

тия графа и установлена связь между ультра-, гиперграфами и обыкновенными 
графами.
Приведены формальные правила, связывающие матричное и аналитическое 
представления для каждого вида графов, а также выражения для оценки характеристик компонент графа. Рассмотрены некоторые особые графы, части графов, а 
также особые вершины и ребра и их множества. Ряд понятий, определенных на 
обыкновенных графах, распространены на ультра- и гиперграфы. Это позволит расширить круг объектов и задач дискретной оптимизации.
В главе 3 сформулированы требования к математическим моделям структур 
сложных систем. Приведена методика перехода от описания объекта проектирования 
к его математической модели в виде того или иного графа. Указаны особенности 
задач и свойства объектов структурного синтеза, определяющие выбор вида графа. 
Дана подробная информация о структуре системы и ее монтажном пространстве. 
Рассмотрены вопросы выбора той или иной модели. Указаны возможные прикладные 
задачи, для решения которых следует использовать модель в виде определенного 
графа, и соответствующие им задачи теории графов. Конкретизирована информация, 
которую необходимо отобразить в модели, сформулированы правила перехода от 
исходного описания структуры системы к ее модели. 
Глава 4 посвящена математическим моделям дискретной оптимизации. Приведена общая формальная постановка задачи дискретной оптимизации. На примере 
размещения микросхем на плате субблока рассмотрена методика получения математической модели задачи позиционирования. Даны формальные постановки 
широкого круга прикладных задач.

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

Планируемые результаты изучения модуля 

Студент должен знать:

 • виды задач дискретной оптимизации и классы их сложности, математические 
абстракции, используемые в качестве моделей объектов проектирования, и формальные постановки основных задач дискретной оптимизации;
 • методики анализа объектов и задач структурного синтеза и разработки их математических моделей;
Студент должен владеть:

 • базовыми знаниями теории графов, необходимыми для разработки математических моделей объектов и формализации задач проектирования сложных систем;

раздела работы [3], в которой был предложен единый подход к определению поня

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

 • методиками получения математических моделей объектов и задач структурного 
синтеза;

их математических моделей.
Студент должен уметь:

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

 • анализа сложных дискретных систем и получения их математических моделей;
 • анализа содержательной и получения формальной постановки задач дискретной 
оптимизации.

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

1.1. Примеры задач дискретной оптимизации

Для того чтобы выявить общие свойства задач дискретной математики, 
рассмотрим несколько примеров из различных предметных областей, объекты которых, как правило, являются сложными системами, состоящими 
из конечного множества компонентов — подсистем и связей между ними.
Задачи дискретной математики являются моделями задач синтеза и 
анализа структур сложных систем. Для сложных систем задача структурного 
синтеза заключается в поиске некоторого варианта состава компонентов и 
порядка их соединения, а задача анализа — в определении свойств или характеристик системы.
Довольно широкий круг задач структурного синтеза ставится следующим 
образом: заданы совокупность подсистем и возможные или существующие 
связи между ними (направленные или ненаправленные), необходимо найти 
максимальное или минимальное число компонентов системы, обладающих 
требуемыми свойствами. Примерами прикладных задач являются:

 • определение максимально возможного количества параллельных процессов;

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

 • выделение в системе минимального количества подсистем, к которым 
подсоединены все линии связи.
В теории графов это соответственно задачи определения наибольшего 
независимого множества вершин, наименьшего доминирующего множества 
вершин графа и наименьшего вершинного покрытия графа [1–3].

 • практическими навыками анализа объектов и задач проектирования, получения