Элементы исследования операций

Э.Н. Гордеев
Элементы исследования операций
Учебное пособие

УДК 519.7
ББК 22.18
	
Г68
Издание доступно в электронном виде на портале ebooks.bmstu.ru
по адресу: http://ebooks.bmstu.ru/catalog/117/book1659.html
Факультет «Информатика и системы управления»
Кафедра «Информационная безопасность»
Рекомендовано Редакционно-издательским советом  
МГТУ им. Н.Э. Баумана в качестве учебного пособия 
Гордеев, Э. Н.
Г68	
	
Элементы исследования операций : учебное пособие  / 
Э. Н. Г
ордеев. — Москва : Издательство МГТУ им. Н. Э. Баумана, 2017. — 59, [1] с.: ил.
ISBN 978-5-7038-4685-8 
Представлен материал по дисциплине «Исследование операций», 
являющийся основой при изучении курса «Теория принятия решений 
в условиях информационных конфликтов». Приведены классические 
постановки базовых задач с указанием наиболее распространенных 
подходов к их решению, а также примеры алгоритмов решения. Изложение материала проиллюстрировано примерами таких особенностей 
постановок задач, которые могут трактоваться как информационные 
конфликты. 
Для студентов, обучающихся на факультете «Информатика и системы управления» МГТУ им. Н.Э. Баумана. Издание может представлять интерес для инженеров.
УДК 519.7
ББК 22.18
ISBN 978-5-7038-4685-8
©	 МГТУ им. Н.Э. Баумана, 2017
©	 Оформление. Издательство  
	
МГТУ им. Н.Э. Баумана, 2017

Предисловие
Издание подготовлено для студентов, изучающих курс «Теория 
принятия решений в  условиях информационных конфликтов», 
который предусмотрен учебным планом МГТУ им. Н.Э. Баумана. 
Пособие содержит материал по исследованию операций и основам математического программирования. Рассмотрены классические постановки задач с  указанием наиболее распространенных 
подходов к их решению, а также примеры алгоритмов решения. 
Изложение таких особенностей постановок задач, которые могут 
трактоваться как информационные конфликты, проиллюстрировано примерами.
В данный курс входят три основных теоретических подхода: 
методы оптимизации процесса принятия решения; эвристические 
методы и игровые модели принятия решений. Так как курс предназначен для студентов и инженеров, то понятие «информационный конфликт», имеющее свою специфику в  каждом из  приведенных подходов, должно формулироваться на языке математики 
или хотя бы на языке исследования операций. В качестве примеров можно привести формализацию ситуации принятия решения 
в следующих условиях:
1) работа с неточными данными;
2) работа с изменяющимися по времени данными;
3) работа в условиях, когда решение принимается несколькими лицами с несогласованными или противоречивыми целями;
4) завоевание (изменение) антагонистической среды. 
В данном пособии рассмотрены первые два упомянутых выше 
подхода.
Представленный курс опирается на базовые знания, полученные при изучении дискретной математики, математической логики и теории алгоритмов, теории информации и курса «Алгоритмы 
и структуры данных». Также будут более подробно изложены методы решения (алгоритмы) в их взаимосвязи между собой и классами задач, к которым они применены.
3

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

Введение
Рассмотрим определение изучаемого предмета, данное в классическом учебнике [1]. Исследование операций (ИО), operations 
research  — дисциплина, занимающаяся разработкой и  применением методов нахождения оптимальных решений на основе математического моделирования и  различных эвристических подходов 
в различных областях человеческой деятельности. Исследование 
операций — применение математических, количественных методов для обоснования решений во всех областях целенаправленной 
человеческой деятельности  — начинается тогда, когда для обоснования решений используют тот или другой математический 
аппарат. Операция  — всякое мероприятие (система действий), 
объединенное единым замыслом и  направленное к  достижению 
какой-то цели,  — всегда является управляемым мероприятием, 
т.  е. зависит от  человека, решающего каким способом выбрать 
параметры, характеризующие ее организацию (в широком смысле, включая набор применяемых технических средств). Решение 
(удачное, неудачное, разумное, неразумное)  — всякий определенный набор зависящих от  человека параметров. Оптимальное 
решение — это то, которое по тем или другим признакам предпочтительнее других. Цель исследования операций — предварительное 
количественное обоснование оптимальных решений с  опорой 
на показатель эффективности. Само принятие решения выходит 
за рамки исследования операций и относится к компетенции ответственного лица (лиц). Элементы решения — параметры, совокупность которых образует решение: числа, векторы, функции, 
физические признаки и  т.  д. Если элементами решения можно 
распоряжаться в определенных пределах, то заданные (дисциплинирующие) условия (ограничения) зафиксированы сразу и нарушены быть не могут (грузоподъемность, размеры, вес). К таким 
условиям относятся средства (материальные, технические, людские), которыми человек вправе распоряжаться, и иные ограничения, налагаемые на решение и своей совокупностью формирующие множество возможных решений. 
5

В определении дисциплины встречаются понятия: математическая модель; задача; решение; параметры решения; критерий 
эффективности решения; эвристическое решение; лицо, принимающее решение (выбирающее операцию для получения приемлемого решения). Итак, имеется задача. Исследователь знает 
набор методов ее решения. С каждым методом связаны реализующие его алгоритмы (точные или эвристические). Сама задача описывается набором параметров, подмножества которого определяют тот или иной используемый алгоритм. Цель решения задачи 
также описывается через эти параметры. При этом лицо использует некоторый формализованный набор критериев. Параметры 
могут меняться во времени, часть их может быть неизвестна или 
известна с некоторой точностью. Как во всем этом разобраться? 
Как представить (составить математическую модель) задачу и сопоставить ей решение нужного качества?
Начнем с обсуждения первого из упомянутых понятий — задачи. В разных курсах уже неоднократно об этом говорили, особенно подробно на «Математической логике и теории алгоритмов».
Например, в  [2] определение задачи вообще не  дается, считается, что оно «интуитивно очевидно». Под задачей понимается 
«некоторый общий вопрос, на который следует дать ответ». При 
этом «задача содержит несколько параметров или свободных переменных, конкретные значения которых не определены».
В [3] задачей называется «выбор наилучшей конфигурации или 
множества параметров для достижения некоторой цели». При этом 
задачи делятся на непрерывные и комбинаторные, в первых из них 
обычно отыскивается множество действительных чисел или даже 
некоторая функция, а  в  комбинаторных  — некоторый объект 
из конечного или возможно бесконечного (счетного) множества. 
Другими словами, задача оптимизации — это пара (F, c), где F — 
произвольное множество, область допустимых точек, а c — функция стоимости, отображающая элементы F на множество действительных чисел. Требуется найти такую точку x* (или множество 
 
точек) из F, при которой значение функции c(x*) имеет определенное свойство, например минимально, максимально и др.
При таком задании с  задачей обычно связаны два объекта: 
множество параметров и структура связей между ними. Параметры — это язык для описания условий задачи. Структура связей 
содержит нечто, позволяющее описать F, а также сформулировать 
вопрос [2, 3] или требование к c(x*), трактуемое как вопрос, свойство функционала и т. д. 
6