Дискретные задачи оптимизации в экономике, планировании и управлении

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ 

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ  
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ  
«НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ «МИСиС» 

 

 
 
 

 

 

 

 
 

 

Кафедра финансов и менеджмента горного производства

А.М. Валуев 
 
 

Дискретные задачи 
оптимизации в экономике,  
планировании и управлении 

Учебное пособие 
для бакалавров и магистров, обучающихся по направлениям 
080100 – «Экономика», 080200 – «Менеджмент», 380408 – 
«Финансы и кредит», 230100 – «Информатика и вычислительная 
техника» 

Москва 2014 

УДК 519.8:658.5 
 
В15 

Р е ц е н з е н т ы :  
проф. кафедры математической кибернетики и информационных технологий  
Московского технического университета связи и информатики,  
д-р физ.-мат. наук, А.Г. Таташев; 
проф. математики НИТУ «МИСиС», д-р техн. наук, В.К. Ушаков 

Валуев А.М. 
В15  
Дискретные задачи оптимизации в экономике, планировании и управлении : Учеб. пособие / А.М. Валуев. – М. : Изд. 
Дом МИСиС, 2014. – 135 с. 
 

Рассмотрены важнейшие для экономики, планирования и управления задачи дискретной (комбинаторной) оптимизации, анализируются их формулировки и описываются методы решения. Большая часть представленных задач относятся к сетям различного типа – сетевым графикам проектов, дорожным сетям, графам переходов между состояниями производственных 
и экономических процессов и др., что позволяет решать их одними и теми же 
методами. Рассматриваются обобщения ряда традиционных задач, в частности, задачи субоптимальной маршрутизации, задачи оптимального дискретного динамического распределения ресурсов при выполнении проекта. Представлены некоторые задачи и методы оптимизации горного производства. 
Для задач оптимизации в условиях неопределенности охарактеризованы возможные цели – оптимизация «в среднем», поиск оптимального гарантированного результата и Парето-оптимизация, описаны методы решения. 
Предназначено для бакалавров и магистров, обучающихся по направлениям 080100 – «Экономика», 080200 – «Менеджмент», 380408 – «Финансы 
и кредит», 230100 «Информатика и вычислительная техника». 
Работа выполнена при финансовой поддержке Министерства образования 
и науки Российской Федерации в рамках базовой части государственного задания НИТУ «МИСиС». 

УДК 519.8:658.5 

 
© А.М. Валуев, 2014 

ОГЛАВЛЕНИЕ 

Введение....................................................................................................5 
1. Графы и сети. Связность графов.........................................................7 
Вопросы и упражнения ......................................................................15 
2. Задача о кратчайшем остовном дереве и ее практическое  
значение...................................................................................................16 
2.1. Понятие дерева и корневого дерева...........................................16 
2.2. Значение деревьев для хранения и обработки  
упорядоченных списков.....................................................................18 
2.3. Задача о кратчайшем остовном дереве......................................20 
Вопросы и упражнения ......................................................................24 
3. Метод динамического программирования.......................................25 
3.1. Задача о замене оборудования....................................................25 
3.2. Задача об оптимальном двоичном  поисковом дереве.............29 
Вопросы и упражнения ......................................................................32 
4. Задача сетевого планирования как оптимизационная  
задача на сети..........................................................................................33 
4.1. Постановка задачи. Сетевой график..........................................33 
4.2. Метод критического пути...........................................................37 
Вопросы и упражнения ......................................................................41 
5. Задача о кратчайшем пути на графе и ее аналоги.  
Варианты метода динамического программирования ........................42 
5.1. Алгоритм Дейкстры.....................................................................43 
5.2. Оценка трудоемкости решений. Модификация Грибова.........48 
5.3. Алгоритм Левита .........................................................................50 
5.4. Использование «потенциалов» вершин для повышения 
эффективности поиска .......................................................................52 
5.5. Задача о многополюсной кратчайшей цепи..............................54 
Вопросы и упражнения ......................................................................59 
6. Метод ветвей и границ для поиска кратчайшего пути на графе. 
Обобщение на случай сетей с изменяющимися параметрами ...........60 
6.1. Задача об оптимальной трассе обхода запрещенных  
областей...............................................................................................60 
6.2. Применение метода ветвей и границ для поиска  
кратчайшей траектории на геометрическом графе .........................65 
Вопросы и упражнения ......................................................................67 
7. Оптимизация дискретного распределения ресурсов 
при планировании и выполнении проекта ...........................................69 
7.1. Многовариантность постановки задачи сетевого  
планирования ......................................................................................69 

7.2. Базовая модель и метод ее расчета ............................................71 
7.3. Пример вариантов составления плана и управления  
его выполнением.................................................................................73 
7.4. Оптимизация графика выполнения проекта .............................77 
7.5. Другие виды задач оптимального динамического 
распределения ресурсов при выполнении проекта .........................83 
Вопросы и упражнения......................................................................84 
8. Некоторые задачи дискретной оптимизации границ  
и порядка разработки месторождения открытым способом ..............85 
8.1. Оптимизация последовательности разработки пологого 
месторождения открытым способом ................................................85 
8.2. Оптимизация границ разработки месторождения  
глубоким карьером  (на вертикальном разрезе) ..............................88 
Вопросы и упражнения......................................................................92 
9. Оптимизация маршрута на динамической сети................................94 
9.1. Оптимизация маршрута на дорожной сети  
с детерминированной динамикой характеристик .............................94 
9.2. Оптимизация маршрута с использованием общественного 
транспорта с известным расписанием ..............................................98 
9.3. Оптимизация маршрута с учетом неопределенности 
характеристик участков сети...........................................................102 
Вопросы и упражнения....................................................................105 
10. Задача построения множества субоптимальных  
ациклических путей..............................................................................106 
10.1. Варианты задачи о субоптимальных путях...........................106 
10.2. Метод решения задачи о Δd-субоптимальных путях...........107 
Вопросы и упражнения....................................................................111 
11. Задачи об оптимальной траектории на сети с учетом затрат .....112 
11.1. Варианты постановки задачи. Оптимизация  
по комплексному критерию.............................................................112 
11.2. Оптимизация одновременного выбора маршрута  
и скоростного режима при ограничениях на расход горючего....115 
11.3. Оптимизация выбора маршрута с использованием 
общественного транспорта с учетом стоимости проезда .............121 
11.4. Экономическая интерпретация задачи ..................................124 
11.5. Применение алгоритмов субоптимальной маршрутизации  
для многокритериальной оптимизации маршрута ........................125 
Вопросы и упражнения....................................................................127 
12. Задача коммивояжера.....................................................................128 
Вопросы и упражнения....................................................................132 
Заключение............................................................................................133 
Библиографический список.................................................................134 

ВВЕДЕНИЕ 

Задачи дискретной оптимизации широко распространены в современной прикладной математике и имеют большое практическое 
значение для экономики, планирования и управления. Важным классом среди них являются задачи на сетях, ибо сеть (в математическом 
смысле – класс графов) есть форма многообразных систем, относящихся к различным предметным областям. В частности, существуют 
такие типы сетей, как потокопроводящие инженерные сети (водопроводы, нефтепроводы, вентиляционные сети, электрические сети), 
транспортные, коммуникационные. Большинство других типов задач 
дискретной оптимизации также имеют графовую форму. 
Рассматриваемые задачи имеют отношение к различным областям 
экономики и управления: выбор оптимального графика выполнения 
комплекса работ (проекта), оптимальное вложение средств в оборудование и его обновление, задачи оптимизации перевозок и транспортных систем, задачи оптимизации границ и порядка разработки 
месторождений открытым способом.  
Преимущественным типом критериев являются экономические – 
в первую очередь чистый дисконтированный доход. Если же речь 
идет о минимизации времени выполнения проекта или осуществления маршрута, то это также ведет к снижению затрат или увеличению доходов (недаром говорят: «время – деньги»).  
Оптимальные решения имеют форму плана. Часто этот план развернут во времени, является планом-графиком. Кроме того, изменившиеся обстоятельства или получение новой информации могут быть 
использованы для улучшения планового результата. В этом состоит 
управление выполнением плана. Хотя в пособии рассмотрены лишь 
частные элементарные примеры такого управления, оно является универсальным явлением. В этом смысле оптимизация деловых процессов 
является не только последовательностью разделенных во времени 
плановых решений, но и непрерывным процессом управления. 
В пленарном докладе «Сетевое управление проблемы и перспективы» на XII Всероссийском совещании по проблемам управления (его 
сделал 19 июня 2014 г. д.т.н., профессор, заведующий лабораторией 
управления сложными системами Института проблем машиноведения 
РАН А.Л. Фрадков) была обоснована роль исследования сетевых задач 
управления как одной из ведущих составляющих современной науки 
управления в мировом масштабе. По мнению докладчика, в отечест

венной научной литературе им уделяется недостаточно внимания. То 
же самое касается и учебно-методической литературы. 
Рассматриваемые оптимизационные задачи имеют комбинаторную природу и решаются переборными методами. Тем не менее важно применять направленный перебор, отбрасывающий бесперспективные варианты на основе их оценивания и использования конкретных соображений, отражающих специфику задачи. В результате, несмотря на то, что количество возможных вариантов имеет экспоненциальный (как степенная функция) и даже более быстрый рост по 
отношению к размерности сети, для большинства из рассмотренных 
задач предложены методы с гораздо более медленным, полиномиальным (как многочлен, обычно степени 2–3) ростом объема вычислений от размерности задачи. Метод динамического программирования (основной для данного пособия), хотя и не свободен от «проклятия размерности» в общем случае, для изучаемых задач порождает 
достаточно эффективные алгоритмы. Однако в ряде случаев преимущество над ним имеет метод ветвей и границ. Вычислительная 
эффективность методов решения рассматриваемых задач зависит не 
только от принципиального построения метода, но в значительной 
степени и от деталей его алгоритмической реализации. Этот аспект 
методов решения рассматриваемых задач достаточно специфичен 
для систематического изложения в учебном пособии, но его общие 
черты также представлены здесь.  
В настоящем учебном пособии наряду с классическими задачами 
дискретной оптимизации (задачи о кратчайшем пути и задача сетевого планирования в традиционной постановке, задача коммивояжера) 
и широко известными методами их решения рассматриваются также 
и более новые, в том числе учитывающие действие случайных факторов и многокритериальность.  

1. ГРАФЫ И СЕТИ. СВЯЗНОСТЬ ГРАФОВ 

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

задачах. Объединяющим началом для всех типов графов является то, 
что, во-первых, для каждого графа определяется множество вершин 
(узлов) V и ребер (дуг, связей) E и, во-вторых, каждое ребро соединяет 
две вершины. Далее для каждого класса графов вводятся ограничения 
на взаимосвязи между V и E. В собственно графах и мультиграфах не 
допускается наличие ребер, соединяющих одну и ту же вершину (петель). Если этого ограничения нет, говорят, соответственно, о псевдографах и псевдомультиграфах. Псевдографы и псевдомультиграфы 
также применяются в некоторых практических задачах. 
В неориентированном графе (или просто графе) каждому ребру 
e
E
∈
 соответствует множество из двух вершин 
1
2
(
,
)
e
e
v
v
, называемых 
концами ребра, причем любые две вершины могут быть соединены 
лишь одним ребром. Последовательность вершин в паре 
1
2
(
,
)
e
e
v
v
 не 
имеет значения, и ребро можно называть неориентированным. 
По аналогии с задачей о кенигсбергских мостах, с которой и началась теория графов, рассмотрим граф связей между помещениями. 
Не следует думать, что приведенный пример не имеет отношения к 
экономике, планированию и управлению. Расположение проходов и 
вытекающий из него граф путей выхода из помещений определяет 
возможную динамику эвакуации (весьма важный вопрос, предмет 
регулярных международных конференций). Под эвакуацией понимают выход из здания не только при чрезвычайных обстоятельствах 
(взрыв, пожар), но и в повседневной обстановке (вокзал, стадион, 
крупное общественное здание). С этим вопросом тесно связано принятие экономических и управленческих решений как при строительстве здания, так и при его эксплуатации. 

 

1 
2

3 

4 

5

6

8

7

9

 

Рис. 1.1. План квартиры 

9 

1

2

3

4

8

6
7 

5 

 

Рис. 1.2. Граф связей между помещениями квартиры 

Ориентированным графом (орграфом) называется пара V, E, для 
которой каждому ребру e
E
∈
соответствует упорядоченная пара из 
двух несовпадающих вершин 
1
2
(
,
)
e
e
v
v
, называемых соответственно 
началом и концом ребра, причем разным ребрам соответствуют разные множества 
1
2
(
,
)
e
e
v
v
. (Следовательно, последовательность вершин в паре 
1
2
(
,
)
e
e
v
v
 имеет значение и ребро можно называть ориентированным). При наличии в графе ориентированных и неориентированных ребер неориентированные ребра рассматривают как пары 
встречных ориентированных ребер. 
Иногда, ради единого рассмотрения ориентированных и неориентированных графов, считают, что ребру соответствуют две упорядоченных пары – 
1
2
(
,
)
e
e
v
v
 и 
2
1
(
,
)
e
e
v
v
. При наличии в графе ориентированных и неориентированных ребер для его представления в виде орграфа неориентированные ребра рассматривают именно как пары 
встречных ориентированных ребер. В отличие от неориентированной 
связи «соединены проходом» между помещениями цитирование является односторонней связью (более поздняя работа ссылается на более 
ранние). Отношение цитирования в виде орграфа показано на рис. 1.3. 
Цитирование – одна из форм распространения информации. Подобным образом можно представить и более массовые его формы, в 
частности распространение информированности о новых видах товаров и услуг. 
Дорожные сети с участками одностороннего движения, сетевой 
график проекта и многие другие объекты, рассмотренные в пособии, 
представляют собой орграфы. В этих орграфах исключены дугипетли, начинающиеся и заканчивающиеся в одной вершине. Но такие 
графы (псевдоорграфы) существуют и часто используются.  

Попов.
Статья №1 

Попов.
Статья №2 

Попов.
Статья №3 

Седов.
Статья №1 

Седов. 
Статья №2

Петров.
Статья №2 

Петров.
Статья №1

Артемьев.
Статья №1

 

Рис. 1.3. Орграф цитирования статей 

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

Петров 

Попов 

Седов 

Артемьев 
 

Рис. 1.4. Псевдоорграф цитирования авторов статей 

Иногда, ради единого рассмотрения ориентированных и неориентированных графов, считают, что ребру соответствуют две упорядоченных пары – 
1
2
(
,
)
e
e
v
v
 и 
2
1
(
,
)
e
e
v
v
. При наличии в графе ориентированных и неориентированных ребер для его представления в виде 
орграфа неориентированные ребра рассматривают именно как пары 
встречных ориентированных ребер. 

Неориентированный мультиграф отличается от графа, а мультиорграф – от орграфа тем, что снимается условие единственности ребра, соединяющего пару вершин. Иначе говоря, в мультиграфе вершины могут быть соединены несколькими ребрами, а в мультиорграфе – несколькими дугами в каждом направлении. 
Если удалить из графа часть вершин и (или) ребер, такой граф по 
отношению к исходному называется частичным графом (естественно, 
остаются только те ребра, которые соединяют оставшиеся вершины). 
Если удалить часть вершин и оставить все ребра, соединяющие оставшиеся вершины, такой частичный граф называется суграфом.  
Графы и псевдографы могут выражать бинарные (парные) отношения. В графовом представлении речь идет только о наличии парных связей, выражающих какое-либо отношение, а не о качестве 
этих связей. Рассмотрение отношений под этим углом зрения хорошее известно из математики (отношения <, = , ≤ и т.д. между числовыми значениями). В таком же плане можно рассматривать отношения на некотором множестве людей (факт наличия и отсутствия), такие как «знакомство», «доверие», «родственная связь». Некоторые из 
указанных отношений выражаются набором двусторонних связей 
(равенство, знакомство), причем в первом случае обязательно вводятся связи-петли (значение равно самому себе). В других случаях 
часть связей может быть односторонними (доверие, уважение). Формальное рассмотрение отношений как графов имеет значение не 
только для выполнения вычислений, но может применяться и в 
управлении социально-экономическими и коммуникационными процессами. Рассмотрение графа знакомств позволяет выяснить, например, возможности распространения информации по каналам межличностной коммуникации и тем самым – формирование мнений. 
Перейдем к дальнейшим определениям. Вершины называются 
смежными, если они являются концами какого-либо ребра, и несмежными – в противном случае. По отношению к каждому из своих 
концов ребро называется инцидентным, а концы ребра – инцидентными этому ребру. Степенью вершины считается количество смежных вершин. В графе, показанном на рис. 1.2, вершины 1, 5, 6 и 7 
имеют степень 1, вершины 2 и 4 – степень 2, вершина 3 и 8 – степень 
3, 9 – степень 4. 
Для вершины орграфа определяются также полустепень захода – 
количество дуг, концом которых она является, и и полустепень выхода – количество дуг, для которых она служит началом. Для городских дорожных сетей при двусторонней организации движения для 

узлов-перекрестков наиболее типичной является степень 4; то же 
значение имеют полустепени захода и выхода. А вот при пересечении улиц с односторонним движением полустепени захода и выхода 
равны 2. Например, статья Артемьева цитирует три другие статьи и 
не цитируется в других статьях, соответственно, ее полустепень выхода равна трем, полустепень захода – нулю. 
Последовательности ребер {
1
2
(
,
)
e
e
v
v
, e = e1,..., eN}, для которых 

1
1
2 ,
k
k
e
e
v
v
+ =
 k = 1,..., N-1, можно понимать как путь (маршрут) на графе, соединяющий начало первого ребра и конец последнего. Если не 
рассматривать мультиграфы, маршрут однозначно определяется последовательностью смежных вершин. Если игнорировать направление ребер, то последовательность неориентированных ребер указанного вида называется цепью. Длиной цепи называется количество 
входящих в нее ребер. Маршрут, у которого начальная и конечная 
вершины совпадают, называется контуром, а цепь с тем же свойством – циклом. 
Важнейшим свойством графа является связность. Связным называется граф, у которого любые две вершины соединены цепью. Диаметром связного графа называется максимальная длина простых цепей между его вершинами. Общепризнанным считается установленное эмпирическим путем утверждение, что граф знакомств между 
всеми людьми связен и его диаметр равен шести («теория шести рукопожатий»). Это значит, что каждая пара людей либо знакома (одно 
рукопожатие), либо имеет общих знакомых (два рукопожатия), либо 
кто-то из знакомых первого человека знаком с кем-то из знакомых 
второго (три рукопожатия) и т.д. В рассматриваемых примерах связность имела место всегда, но легко привести и примеры, когда ее нет. 
Например, если в жилище есть помещения с отдельным входом, изолированные от остальных, то граф, подобный представленному на 
рис. 1.2, окажется несвязным. Если ограничиться примером на рис. 
1.1, 1.2, можно сказать, что если дверь между помещениями 8 и 9 
закрыть, то граф утратит связность. То же самое произойдет в случае 
пожара в помещении 9. 
С точки зрения некоторых из рассматриваемых приложений связности недостаточно – нужна сильная связность. Последняя требует, 
чтобы любые две вершины были соединены маршрутом. Это можно 
прокомментировать на примере транспортных сетей.  
Если рассматривать дорожные сети общего назначения, соединяющие населенные пункты (автодорожные сети) или железнодорожные станции, в них ребра не ориентированы, поэтому связности