Исследование операций. Задачи, модели и алгоритмы

ИССЛЕДОВАНИЕ 
ОПЕРАЦИЙ
ЗАДАЧИ, МОДЕЛИ И АЛГОРИТМЫ
А.Н. БОЖКО
С.В. РОДИОНОВ
МОНОГРАФИЯ
Москва
ИНФРА-М
2026

УДК 51-7(075.4)
ББК 87.256.631
 
Б76
ISBN 978-5-16-021171-8 (print)
ISBN 978-5-16-113909-7 (online)
Божко А.Н.
Б76  
Исследование операций. Задачи, модели и алгоритмы : монография / А.Н. Божко, С.В. Родионов. — Москва : ИНФРА-М, 2026. — 
297 с. — (Научная мысль). — DOI 10.12737/2216485.
ISBN 978-5-16-021171-8 (print)
ISBN 978-5-16-113909-7 (online)
Монография посвящена применению математических методов для 
принятия рациональных решений в различных областях целенаправленной деятельности человека. Обсуждаются транспортная задача и ее многочисленные модификации, задача о назначениях, потоки в сетях, задачи 
маршрутизации на сетях и графах, задача коммивояжера. Содержит компактное и замкнутое изложение постановок, разновидностей и алгоритмов 
решения этих задач. Наиболее сложные алгоритмы подкреплены подробно 
разобранными примерами.
Может быть полезна широкому кругу специалистов по применению математических методов в различных отраслях народного хозяйства и программистам.
УДК 51-7(075.4)
ББК 87.256.631
Р е ц е н з е н т ы:
Каганов Ю.Т., кандидат технических наук, доцент, доцент Московского государственного технического университета имени Н.Э. Баумана;
Корсун О.Н., доктор технических наук, начальник сектора Государственного научно-исследовательского института авиационных систем
© Божко А.Н., Родионов С.В., 
2025

Предисловие
Книга посвящена актуальному разделу информационных технологий и прикладной математики – исследованию операций. Она создана на основе курса, который в 
течении многих лет читается студентам старших курсов, обучающихся по направлению «Информатика и вычислительная техника» в МГТУ им. Н.Э. Баумана.
Исследование операций – это глубоко развитая дисциплина и многие ее разделы 
хорошо поддержаны учебной и методической литературой. Однако, большинство изданий на русском языке выходили в советское время и сейчас стали труднодоступными. Из актуальных монографий, переизданных в наше дни, можно назвать только 
фундаментальную книгу Х. Таха «Исследование операций». В большинстве изданий 
по исследованию операций акцент в изложении ставился на описание задач и их математических моделей. За немногими исключениями, изложение алгоритмов было неполным или вообще отсутствовало. 
Книга состоит из восьми глав, в которых обсуждаются основные разделы исследования операций: задачи транспортного типа, задача о назначениях и ее многочисленные модификации, потоки в сетях, и задачи маршрутизации, где рассматриваются 
алгоритмы поиска кратчайших путей, построения остовных деревьев и гамильтоновых 
циклов. 
Авторы старались сделать изложение материала максимально замкнутым.  Вместе с постановками задачи исследования операций, описываются ее важнейшие практические применения, модификации и алгоритмы решения. Изложение большей части 
трудных алгоритмов сопровождается подробно разобранными примерами. 
В книге приводится доступное и подробное описание венгерского алгоритма –
эффективного средства решения различных вариантов задачи о назначении и транспортной задачи. 
Книга может быть полезна бакалаврам и магистрам, обучающимся по направлению 09.00.00 «Информатика и вычислительная техника». Она заинтересует специалистов по прикладной математике, программированию и математическому моделированию в различных отраслях народного хозяйства. 
3

Глава 1. Основные положения и терминология
Исследование операций (ИСО) – научная дисциплина, которая изучает формальные методы принятия решений на основе количественной оценки их результативности
в различных областях человеческой деятельности.
Первые упоминания о дисциплине относятся ко второй половине двадцатого 
века, когда в вооруженных силах стран-союзниц появились группы, отвечающие за 
научное обеспечение военных и логистических операций на фронтах второй мировой 
войны. Позднее методы, которые первоначально были разработаны для решения военных задач, были успешно применены в самых различных сферах человеческой практики: промышленная логистика, транспортные перевозки, проектирование коммуникаций, торговля и пр. 
Приведем несколько простых примеров задач ИСО. 
Задача о размещении. В некотором городе или поселке требуется разместить 
пункты первичного медицинского обслуживания (станции пожарной охраны, отделения охраны правопорядка и пр.) так, чтобы время реакции персонала на вызовы было 
минимальным. 
Задача одномерного раскроя. Существует заданное количество заготовок в 
форме прутка постоянного диаметра. Из этих заготовок требуется получить определенное количество втулок разной длины. Требуется найти раскрой заготовок с минимальным объемом (совокупной длиной) отходов. 
Задача коммивояжера. Есть карта или план некоторого населенного пункта (города или поселка). Известны расстояния между домами этого города. Требуется найти 
замкнутый обход всех домов, который посещает каждый дом ровно один раз и имеет 
минимальную длину. Вместо города и домов в этой задаче могут участвовать большой 
склад и логистические пункты, которые требуют обслуживания и многое другое.
Задача о рюкзаке. Есть множество предметов, которые можно взять в путешествие. Известны вес и полезность каждого предмета. Задано ограничение на общий вес 
предметов, которые можно положить в рюкзак. Требуется найти подмножество предметов максимальной общей полезности, совокупный вес которых не превосходит заданного предельного значения.
4

В задачах ИСО используются различные разделы прикладной и дискретной математики. Перечислим основные: 
1. Математическое программирование; 
2. Динамическое программирование; 
3. Теория принятия решений; 
4. Теория игр; 
5. Теория массового обслуживания; 
6. Теория расписаний; 
7. Теория графов; 
8. Теория вероятностей и др. 
1.1. Основные понятия ИСО  
Операция – управляемое мероприятие (последовательность или система взаимосвязанных действий), направленное на достижение некоторой цели.  
Цель операции некоторое желательное состояние системы или процесса, которое формулируется в виде набора объективных количественных показателей.  
Решение – набор значений операционных параметров, от которого зависит достижение цели операции. 
Условия операции – множество количественных и качественных ограничений, 
наложенных на операционные параметры.  
Допустимое решение – решение, удовлетворяющее всем ограничениям операции. 
Оптимальное решение – набор операционных параметров, который обеспечивает достижение цели операции.  
1.2. Примеры операций  
Выбор последовательности обработки деталей на станке. Обработка партии 
деталей выполняется на одном станке без простоев и переналадок. В каждый момент 
времени на станке может обрабатываться только одна деталь. Для каждой детали пар5

тии известна продолжительность её обработки и установлен штраф за единицу времени ожидания обслуживания. Нужно определить такой порядок обслуживания деталей, при котором сумма штрафов за ожидание деталей будет минимальной.
Условия операции:
x
Длительность работы станка;
x
Размер партии деталей;
x
Продолжительность обработки каждой детали;
x
Величины штрафов за единицу времени ожидания обслуживания.
Параметры операции: перестановка номеров деталей в принятом порядке обработки. 
Критерий оптимальности: суммарный штраф за ожидание обслуживания всех 
деталей. 
Упаковки предметов в контейнеры. Набор предметов разных размеров необходимо упаковать в контейнеры одинакового размера. Размеры контейнера превосходят габариты любого предмета. В один контейнер можно поместить несколько предметов небольшого размера. Распределить предметы по контейнерам таким образом, 
чтобы число использованных контейнеров было минимальным. 
Условия операции:
x
Размеры предметов;
x
Размер контейнеров;
x
Общие габариты предметов в контейнере не может превышать его размер.
x
Количество предметов;
x
Требование о том, что все предметы должны быть распределены по контейнерам. 
Параметры операции: схема распределения предметов, которая для каждого 
предмета определяет номер контейнера для хранения.
Критерий оптимальности: число использованных контейнеров.
Поиск цели. Некоторый объект с заданной вероятностью может находиться в 
любом из нескольких районов. Для каждого района известна зависимость вероятности 
6

обнаружения объекта от времени. Предельное время поиска ограничено заданной величиной. Нужно установить время поиска в каждом районе, чтобы сделать вероятность 
обнаружения объекта максимальной.  
Условия операции: 
x Число районов поиска; 
x Вероятность присутствия цели в каждом районе; 
x Предельное время поиска цели. 
Параметры операции: продолжительность поиска цели в каждом районе. 
Критерий оптимальности: вероятность обнаружения цели. 
1.3. Классификация моделей ИСО 
Математическая модель в исследовании операций – это описание условий, параметров и критериев оптимальности при помощи формальных понятий и категорий некоторого раздела математики. Такое описание операции часто называют формальной 
постановкой задачи.  
Математические модели ИСО принято делить на три больших класса: детерминированные, стохастические и антагонистические.  
Модель ИСО называется детерминированной, если она описывает операцию, в 
которой есть полная информация об условиях ее проведения, а результат операции 
предопределен набором значений операционных параметров. Часто в таких случаях 
применяется глубоко развитый аппарат математического программирования.  
Модель ИСО называется стохастической, если операция проводится в условиях 
частичной неопределенности, которая имеет статистический характер. Например, эта 
неопределенность вызвана действием одного или нескольких случайных факторов. 
Стохастические модели основываются на математическом аппарате теории вероятностей и теории массового обслуживания.  
Модель ИСО называется антагонистической, если операция проводится в условиях активного противодействия противника. Антагонистические модели основаны на 
формальном аппарате теории игр и теории принятия решений. Часто такие операции 
встречаются в военных приложениях ИСО. 
7

1.4. Детерминированные модели ИСО 
Среди детерминированных моделей ИСО наибольшее распространение получили модели математического программирования. В этой дисциплине рассматриваются модели, методы и алгоритмы поиска экстремумов функций многих переменных. 
На допустимые значения аргументов могут быть наложены ограничения, которые формируют область допустимых решений. Базовыми понятиями любой задачи математического программирования являются вектор управляемых параметров, система ограничений и функция цели. 
Вектор управляемых переменных – упорядоченное множество переменных, 
которые влияют на решение задачи (результат операции). Обозначим вектор переменных 
1
2
( ,
,...,
)
n
x
x x
x
 
. Любая конкретизация значений координат вектора X представляет собой решение задачи. Множество векторов ɏ с допустимыми значениями координат образуют множество допустимых решений. Применительно к детерминированным моделям ИСО ограничения являются формальными описаниями условий операции.  
В математическом программировании ограничения принято разделять на прямые и функциональные.  
1. Прямые ограничения налагаются на отдельные координаты 
ix  вектора управляемых переменных X. Они устанавливают диапазон изменений управляемых переменных. В общем случае, прямые ограничения на непрерывные переменные можно 
записать в виде 
,
1,
i
i
i
a
x
A i
n
d
d
 
. 
Часто, по условиям задачи, управляемая переменная может принимать значения 
из конечного или счетного множества. Например, это состав станочного парка или 
множество путей некоторого населенного пункта и пр. Такие ограничения запишем 
как 
,
1, .
j
j
x
E
j
p

 
 
2. Функциональные ограничения формализуют сложные зависимости управляемых переменных и, в общем случае, представляются в виде системы неравенств и/или 
уравнений. 
8

1
2
1
2
( ,
,...,
)
,
1,
( ,
,...,
)
,
1, .
i
n
i
j
n
j
g x x
x
b i
m
h x x
x
c
j
k
d
 
 
 
Левые части этой системы ограничений являются известными скалярными функциями вектора управляемых переменных, а правые – заданными константами. Например, функционально ограничение 
1
2
0
x x  
формализует требование равенства нулю, по 
крайней мере, одной из переменных 
1
2
,
x x .
Любые наборы значений управляемых переменных, которые удовлетворяют
всем прямым и функциональным ограничениям, являются допустимыми решениями 
задачи математического программирования. Для оценки допустимых решений используется целевая функция. В задачах ИСО целевая функция представляет собой математическое описание критерия оптимальности операции. Она представляется в виде 
функции, зависящей от управляемых. Каждому набору управляемых параметров она 
ставит в соответствие число, которое служит показателем качества эффективности 
данного решения. Более формально, это отображение вида
:{ }
F
x
R
o
, где { }
x – множество векторов управляемых параметров, а R – множество действительных чисел.
Для многих важных задач ИСО целевая функция F может быть задана аналитической зависимостью критерия оптимальности об управляемых переменных: 
1
2
( ,
,...,
)
n
z
F x x
x
 
.
Такие задачи формально записываются в виде
1
2
( ,
,...,
)
n
z
F x x
x
extr
 
o
,
при условии, что набор управляемых переменных удовлетворяет всем прямым и 
функциональным ограничениям:
,
1,
i
i
i
a
x
A i
n
d
d
 
,
,
1,
j
j
x
E
j
p

 
,
1
2
1
2
( ,
,...,
)
,
1,
,
( ,
,...,
)
,
1, .
i
n
i
j
n
j
g x x
x
b i
m
h x x
x
c
j
k
d
 
 
 
Постановка задачи ИСО в таком виде называется задачей математического программирования.
9

Для примера рассмотрим простую задачу линейного раскроя, где пруток длиной 
L нужно разделить на три части так, чтобы длина каждой части была целым числом, а 
произведение длин частей – максимально.  
Управляемыми переменными данной задачи являются длины частей. Обозначим 
их 
1
2
3
( ,
,
)
x
x x x
 
. Эти величины должны быть целыми числами, поэтому добавим ограничение целочисленности 
1
2
3
,
,
{1,2,3,...}
x x x 
. 
Совокупная длина частей не может превосходить длины прутка. Это требование 
формализуется в виде функционального ограничения 
1
2
3
x
x
x
L


d
. 
Любое целочисленное решение этого неравенства даёт допустимый вариант раскроя прутка. Критерием оптимальности для этих решений является требование максимальной величины произведения длин частей. Поэтому целевая функция представляется в виде произведения управляемых переменных, а его величину требуется максимизировать 
1
2
3
max
z
x
x
x
 
˜
˜
o
. 
Задачи математического программирования принято классифицировать по характеру переменных, виду ограничений и способу формализации цели. По этим признакам можно выделить следующие основные подклассы.  
x Линейное программирование. В этом разделе исследования операций рассматриваются задачи, где целевая функция и все ограничения представляются 
линейными формами, а управляемые переменные неотрицательны.  
x Нелинейное программирование. В этом разделе ИСО рассматриваются задачи, где хотя бы одна из функций ограничений или целевая функция являются нелинейной, а прямые ограничения заданы диапазонами значений переменных.  
x Дискретное программирование – рассматриваются задачи, где переменные 
должны принимать значения из конечного либо счётного множества. Обычно 
это множество целых чисел.  
1.5. Стохастические модели ИСО 
Стохастические модели применяются для формального описания операций, где 
по объективным или субъективным причинам отсутствует полная информация об 
10