1.2. ТИПИЧНЫЕ КЛАССЫ ЗАДАЧ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ
По своему смыслу и постановками множество задач исследования операций можно разбить на классы, наиболее распространенными из которых являются:
задачи управления запасами;
задачи распределения ресурсов;
задачи ремонта и замены оборудования;
задачи массового обслуживания;
задачи календарного планирования (теории расписаний);
задачи транспортного типа (выбора маршрутов перевозок);
задачи сетевого планирования и управления;
задачи планировки и размещения объектов;
комбинированные задачи.
Рассмотрим их содержательные постановки и особенности.
Задачи управления запасами. Это один из самых распространенных и хорошо изученных классов задач. Они имеют такие особенности. С увеличением уровня запасов увеличиваются затраты на их хранение, но уменьшаются потери вследствие возможного дефицита.
Задачи управления запасами характеризуются такими элементами: системой снабжения, спросом на предметы снабжения, способами пополнения запасов, функцией затрат, ограничениями, стратегиями управления запасами.
Системы снабжения делятся на децентрализованные и централизованные. Спрос на предметы снабжения бывает стационарным или нестационарным, детерминированным или случайным.
Различают такие способы пополнения запасов: мгновенная поставка (если пренебрегают задержкой времени с момента оформления заказа на поставку до момента самой поставки); задержка поставки на детерминированный промежуток времени; задержка поставки на случайный интервал.
Функция затрат представляет собой критерий эффективности избранной стратегии управления запасами и включает такие составляющие: расходы на хранение запасов, стоимость поставки, потери (штрафы) вследствие дефицита.
Наиболее употребляемыми в задачах управления запасами являются такие ограничения: на максимальный объем (уровень) запасов на складах, на максимальную стоимость запасов, на число поставок, на стоимость поставки, на вероятность дефицита и т.д.
В зависимости от условий задачи управления запасами делятся на такие категории.
Моменты оформления заказов на поставки или моменты самих поставок 
фиксированы. Определить объемы поставок партий запасов 
.
Объемы поставок фиксированы. Определить моменты оформления заказов .
Как моменты поставок 
, так и объемы поставок не заданы. Определить эти величины так, чтобы минимизировать принятый критерий оптимальности (рис. 1.2).
Задачи распределения ресурсов. Они возникают, если есть полный набор работ, которые нужно выполнить, а наличных ресурсов для выполнения каждой работы наилучшим образом не хватает.
В зависимости от условий задачи распределения ресурсов делятся на такие группы.
Заданы как работы, так и ресурсы. Распределить ресурсы между роботами таким образом, чтобы максимизировать определенный критерий эффективности (например, прибыль) или минимизировать ожидаемые затраты (производственные издержки).
Пример. Известны производственные задания и производственные мощности предприятия. При существующих различных способах изготовления изделий (например, обработка на разных станках) ограничение мощностей не дает возможности для каждого изделия использовать наилучшую технологию. Какие способы производства надо выбрать, чтобы выполнить задание с минимальными затратами?
Заданы лишь наличные ресурсы. Определить, какой состав работ можно выполнить с этими ресурсами, чтобы обеспечить максимум некоторой меры эффективности.
Пример. Задано предприятие с определенными производственными, материальными и трудовыми ресурсами. Выбрать такой ассортимент изготовляемой продукции, который обеспечит максимальную прибыль.
Заданы лишь работы, которые надо выполнить. Подобрать такие ресурсы, которые дают возможность выполнить их с минимальными производственными затратами.
Пример. Известно месячное расписание движения пассажирских самолетов по авиалиниям. Какое количество экипажей необходимо, чтобы выполнить план перевозок с минимальными эксплуатационными затратами?
Задачи ремонта и замены оборудования. Эти задачи возникают в тех случаях, когда оборудование с течением времени изнашивается, устаревает и подлежит ремонту или полной замене. Типичная кривая старения оборудования и ухудшения его эффективности 
(например, производительности, если имеется в виду станок) приведена на рис. 1.3.
 |
Изношенное оборудование может подвергаться в некоторые моменты времени
ремонту, который повышает его эффективность до величин 
, или полной замене. С каждым ремонтом связаны затраты 
. Обозначим стоимость нового оборудования (машины) через 
, а время, прошедшее от купли машины до его замены 
через 
(время жизненного цикла). Нужно определить сроки восстановительных ремонтов , их количество, а также момент замены старого оборудования модернизованным, при которых минимизируются средние затраты на ремонт и замену оборудования за весь период его жизненного цикла, то есть
Существует и такое оборудование, в котором детали полностью выходят из строя, не восстанавливаются и подлежат замене (например, радиодетали, конденсаторы, транзисторы и т.п.). Постановка задачи ремонта и замены в этом случае такая.
Для выявления возможных неисправностей нужно определить сроки профилактического контроля, за которые минимизируется сумма затрат на проведение контроля и ожидаемых затрат от простоя оборудования из-за выхода из строя (повреждения) деталей в интервале между соседними моментами контроля.
Задачи массового обслуживания. Они связаны с исследованиями и анализом систем обслуживания с очередями заявок. С явлением образования очередей приходится сталкиваться в производственной практике и повседневной жизни. Типичными примерами являются очереди клиентов в ателье бытового обслуживания; абонентов, которые ждут вызова на междугородной АТС; покупателей возле касс универмага и т.д..
 |
Очереди возникают вследствие того, что поток заявок (абонентов) не управляем и случаен, а количество приборов обслуживания
(взлетно-посадочных полос аэродрома, приемщиков в ателье или кассиров в магазине) ограничено. Если количество приборов обслуживания взять довольно большим, то очереди будут образоваться редко и среднее время ожидания в очереди 
будет небольшим, но неизбежны продолжительные простои приборов обслуживания. Если, наоборот, количество приборов обслуживания маленькое, то возникают большие очереди и имеют место большие потери из-за ожидания в очереди: 
, где 
- затраты на единицу времени ожидания. Поэтому одна из возможных задач массового обслуживания следующая: определить такое число приборов 
при котором минимизируется сумма ожидаемых потерь от ожидания в очереди 
и простоев оборудования 
(см. Рис. 1.4):
.
Задачи календарного планирования (теории расписаний). Они характеризуются такими особенностями. Имеется множество деталей (работ) 
, подлежащих обработке, на некотором множестве станков 
. Заданы технологические маршруты обработки деталей 
, 
, определяющие порядок прохождения станков. В общем случае для различных деталей технологические маршруты неодинаковы.
Пусть для простоты все одинаковы, а именно:
.
|
- продолжительность обработки детали 
на станке 
; 
- требуемый (директивный) срок завершения обработки j-й детали на последнем станке; 
- фактический срок завершения обработки j-ї детали; 
- удельный штраф за единицу времени запаздывания в окончании обработки детали относительно времени . Требуется определить такие очередности обработки деталей на каждом станке 
соответственно, для которых оптимизируется некоторый критерий оптимальности, например, общая продолжительность всего комплекса работ. Такая задача и носит название задачи календарного планирования (КП) или составления расписания, а выбор очередности запуска деталей в обработку - упорядочением (рис. 1.5).
 |
Рис. 1.5
Наиболее частое в задачах календарного планирования используются следующие критерии.
Минимизация общей продолжительности работ, то есть интервала между моментами начала первой операции и окончания последней операции для последней детали:
Минимизация суммарных штрафов (потерь) вследствие запаздывания:
,
где 
- запаздывание завершения обработки j-ї детали.
Минимизация общего запаздывания: 
Минимизация максимального запаздывания: 
.
Максимизация загрузки станков.
Задачи календарного планирования относятся к комбинаторным задачам. Общее количество возможных вариантов расписаний 
общей задаче для m станков и n деталей 
. Поэтому для решения таких задач применяются, в основном, приближенные эвристические методы, за исключением частных случаев задачи для m = 1; m = 2 и m = 3.
Задачи КП различаются по следующим признакам: по числу станков m; по виду технологических маршрутов: с одинаковыми ТМ (задачи конвейерного типа) и с неодинаковыми ТМ; по используемым критериям оптимальности; по виду станков: с идентичными и неидентичными станками.
Задачи сетевого планирования и управления. В этих задачах рассматривают соотношение между сроком окончания определенного комплекса операций, из которых он состоит, и моментами начала выполнения всех операций комплекса. Они актуальны при разработке сложных проектов.
Для строгой постановки этих задач необходимы такие условия:
наличие точно определяемого множества операций, которые надо выполнить для завершения всего комплекса, включающего эти операции как свои составляющие;
множество операций комплекса (проекта) упорядочено так, что для каждой из них известно, какие операции непосредственно ей предшествуют, а которые непосредственно следуют за ней;
в пределах заданного отношения упорядочения операции можно начинать и заканчивать независимо одну от другой;
известна взаимосвязь между величиной потребляемого ресурса и длительностью каждой операции.
Комплекс операций в этом случае можно представить в виде сетевого графика (ориентированного графа), состоящего из вершин (узлов) и ориентированных дуг. При этом операции изображают дугами, а вершины представляют собой некоторые события. Дуги, входящие в вершину, соответствуют операциям, которые должны быть закончены раньше, чем можно будет начать операции, изображенные исходящими дугами.
Событие, соответствующее началу выполнения комплекса операций, обозначают номером 1, а последнюю - номером n. Все другие события (узлы) нумеруют так, что если события i и j связаны некоторой операцией (i, j), то используется неравенство 
, где 
; 
- моменты наступления событий i и j, - длительность операции (i, j). Обычно для первого события принимают 
, а момент наступления последнего события - 
, где величина - это общая продолжительность выполнения всего комплекса. Вводится понятие критического пути. Критическими считаются операции, задержка которых приводит к эквивалентной задержке всего проекта - то есть к увеличению . Путь в сетевом графике (сети) от начального события к конечному, который состоит целиком из таких работ, носит название критическим.
В небольших сетях критический путь можно легко рассчитать, если задано время наступления всех событий и все работы начинаются как можно раньше. Если определены ранние моменты наступления всех событий 
, предшествующих событию j, то ранний момент наступления события j определяется условием
. (1.2.1)
Очевидно, что 
В более крупных сетях критический путь определяют как путь с нулевым резервом времени. Резерв времени операции (i, j) - это интервал времени, в течении которого операция может затягиваться, не приводя к увеличению времени наступления последнего события (то есть времени окончания всего комплекса). Чтобы вычислить резервное время, следует сначала выполнить расчет сети с начала до конца и таким образом определить ранние моменты начала каждой работы в каждом узле сети. Далее вычисляют самое позднее время наступления каждого события в сети. Под ним понимают такое самое позднее время наступления событий, 
, которое не приводит к увеличению значения .
Для определения времени самого позднего окончания каждой работы в каждом узле сети осуществляют расчет сети в обратном направлении - от конца к началу. Для этого берут 
, где - позднее время наступления события j. Если уже определен момент , то для предшествующего события 
вычисляют 
- самое позднее допустимое время окончания всех работ, которые входят в і-й узел:
(1.2.2)
После определения величин для всех 
резервное время для каждой работы (операции) определяется по формуле
. (1.2.3)
По определению 
, где 
самое позднее время начала, а 
- самое раннее время окончания операции (i, j).
Следовательно равенства
, (1.2.4)
(1.2.5)
эквивалентные равенства (1.2.3).
Результаты вычисления величин 
, , а также резервное время для сети, приведенной на рис. 1.6, представлены в табл.1.1 и 1.2.
 |
Таблица. 1.1
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
|
0 |
5 |
9 |
3 |
12 |
14 |
16 |
26 |
|
|
0 |
5 |
9 |
7 |
12 |
18 |
16 |
26 |
Таблица. 1.2
|
|
(1,2) |
(1,3) |
(1,4) |
(2,3) |
(4,3) |
(2,5) |
(3,5) |
(3,7) |
(5,7) |
(5,6) |
(6,8) |
(7,8) |
|
|
0 |
1 |
4 |
0 |
4 |
1 |
0 |
3 |
0 |
4 |
4 |
0 |
Как видим, критический путь определяется цепочкой (1-2-3-5-7-8-), а его длительность равна 
единиц. В пределах резервного времени можно смещать начало выполнения соответствующих работ без изменения длительности критического пути. Для выполнения операций (i, j) проекта выделяются соответствующие ресурсы (трудовые и материальные), от величин которых 
зависит длительность операции (i, j):
.
Зависимость 
может быть различной, наиболее часто она имеет вид
, (1.2.6)
где 
- константа; 
- объем выделенных ресурсов.
В зависимости от того, являются ли величины детерминированными или случайными, выделяют два класса сетевых моделей: детерминированные и вероятностные.
Задачи сетевого планирования и управления (СПУ) в зависимости от начальных условий и постановок делятся на такие группы.
СПУ по критерию 'Время'. Задан сетевой график выполнения проекта, общие выделенные ресурсы для выполнения работ R и их изменение во времени R(t), 
. Нужно распределить эти ресурсы по операциям (i, j) и определить такие моменты начала и окончания всех операций комплекса, при которых минимизируется общая продолжительность всего комплекса операций 
.
СПУ по критерию 'Стоимость'. Задана общая продолжительность всего комплекса работ . Определить сроки начала каждой операции и распределение ресурсов по операциям, при которых минимизируется один из следующих критериев:
а) общие затраты на выполнение всего комплекса работ 
;
б) среднеквадратичный показатель неравномерности ресурсов,
;
где 
;
в) вероятность невыполнения комплекса операций в директивные сроки.
Если структура сетевой модели (СМ) жестко задана и не изменяется, то имеем сетевую модель с детерминированными оценками работ. Если же в зависимости от некоторых случайных факторов структура СМ изменяется, то имеем СМ с вероятностной структурой.
Как и задачи календарного планирования, задачи СПУ носят комбинаторный характер, а для их решения используются преимущественно эвристические алгоритмы.
Задачи планирования и размещения объектов. Эти задачи характеризуются следующими особенностями. На территории некоторого региона задано исходное размещение существующих объектов (например, потребителей продукци и складов) и требуется определить количество новых объектов и места их размещения с учетом их взаимодействия с существующими и между собой таким образом, чтобы оптимизировать некоторый критерий эффективности. Рассмотрим основные показатели и характеристики этих задач. К ним относятся:
а) характеристики существующих и новых объектов;
б) характер взаимодействия между ними;
в) тип пространства решений (размещений);
г) мера расстояния между объектами (метрика пространства размещений);
д) критерий оценки вариантов решений.
Одним из основных показателей, характеризующих новые объекты, является их количество. Кроме того, в зависимости от размеров, каждый новый объект можно рассмотреть либо как точку, либо как протяженный объект. В последнем случае управляемой переменной является форма объекта или форма занимаемой им площади, а задача сводится к задаче планирования размещения. Что касается существующих объектов, то они также в зависимости от размеров могут рассматриваться как точечные либо как протяженные объекты.
Кроме того, размещение может быть статическим или динамическим, детерминированным или стохастическим. Если размещение существующих объектов является управляемой переменной, то возникает задача перепланировки (размещения).
Мера расстояния (метрика пространства размещений) также может учитываться при формулировке задач размещения.
Часто в качестве приближенной оценки фактических расстояний используют евклидово расстояние. Возможны разные критерии оптимизации: минимизация суммарных затрат, минимизация максимальных затрат, максимизация некоторой прибыли. Взаимодействие новых и существующих объектов может быть:
а) зависящее от размещения и независящее от него;
б) статическое или динамическое;
в) детерминированное или стохастическое.
Пространство решений может быть непрерывным, когда новые объекты могут быть размещены в любой его точке, и дискретным, если задано лишь конечное множество точек, где возможное размещение новых объектов. Рассмотрим некоторые типичные постановки задач размещения.
Обобщенная задача размещения с непрерывным пространством (задача Штейнера-Вебера). Пусть существующие объекты размещены в различных точках 
плоскости, а новые объекты - в точках 
. Растояние между точками расположения j-го нового объекта 
и і-го старого объекта 
обозначим через 
, а между точками расположения j-го и к-го новых объектов - через 
. Удельные затраты на перевозку между j-м новым и і-м старым объектами обозначим через 
, а аналогичные затраты на перевозку между j-м и к-м новыми объектами - через 
. Нужно найти такие места расположения новых объектов 
, при которых минимизируются общие годовые транспортные затраты:
. (1.2.7)
Вид функций 
определяется используемой метрикой. Наиболее часто используется метрика Эвклида
и метрика Минковского
,
где 
- координаты точек 
.
Задачи размещения - распределения. Они заключаются в определении числа новых объектов и координат их размещения, а также в распределении перевозок между новыми и существующими объектами. Примером является задача размещения оптовых баз, получающих товары от производственных предприятий, и распределения их между оптовыми и розничными торговыми предприятиями.
Математическая модель этой задачи записывается так:
минимизировать 
, (1.2.8)
при условиях 
(1.2.9)
где 
- общие затраты на перевозки в единицу времени;
- затраты на перевозки в единицу времени при установке n новых объектов;
- удельные затраты в единицу времени при взаимодействии j-го нового и і-го существующего объектов;
Задачи размещения - распределения с дискретным пространством решений. Такие задачи, как правило, приходится решать при размещении производства и складов. Задачи размещения предприятий обычно включают определение их количества, мест расположения и мощности заводов и складов, необходимых для снабжения потребителей продукцией. Эта задача формулируется так.
Пусть имеется m потребителей продукции с известными местами размещения. Заданы n возможных мест размещения предприятий. Известно: потребности і-го потребителя в продукции, 
; постоянные затраты, связанные с размещением предприятия в j-м месте, и переменная часть затрат, зависящая от его производственных мощностей; удельные транспортные затраты 
по перевозке единицы продукции из j-го пункта производства в і-й пункт потребления. Требуется определить такие фактические места размещения предприятий, их производственные мощности, а также долю удовлетворения потребностей потребителей, при которых минимизируются суммарные затраты на размещения предприятий и поставки (перевозки) продукции соответствующим складам.
Такие задачи еще называют производственно-транспортными.
Задачи о покрытии. К этому типу принадлежит, в частности, задача определения мест размещения складов при ограничении, что расстояние от склада к каждому потребителю, которого он обслуживает, не превышает 50 км, или задача размещения пожарных команд таким образом, чтобы расстояние до любой точки города было преодолено соответствующей пожарной командой не более чем за 10 мин.
Задачи транспортного типа (или выбора маршрутов перевозок). Такие задачи чаще всего встречаются при исследовании разнообразных процессов на транспорте и в системах связи. Типичной задачей является задача нахождения некоторого маршрута проезда из города А в город В при наличии нескольких маршрутов через разные промежуточные пункты (города). Стоимость проезда по избранному маршруту известна, требуется определить наиболее экономичный маршрут в соответствии с избранным критерием оптимальности. На допустимые маршруты может быть наложен ряд ограничений. Так, например, вводят запрет на возврат к уже пройденному пункту или требование обхода всех пунктов транспортной сети с условием, что в каждом пункте можно побывать лишь один раз (задача коммивояжера).
Часто вводят ограничения на пропускные способности коммуникаций.
Комбинированные задачи. Довольно часто практические задачи исследования операций содержат несколько рассмотренных выше типичных задач одновременно. Такие задачи являются комбинированными. Например, при планировании управления производством часто приходится решать следующий комплекс задач.
Сколько изделий каждого типа необходимо выпустить и каковы оптимальные размеры партий (типичная задача планирования производства).
Как распределить полученные производственные заказы по видам оборудования (станкам) после того, как определен оптимальный план производства (типичная задача распределения ресурсов).
В какой последовательности и когда следует выполнять производственные заказы (типичная задача календарного планирования).
Поскольку эти три задачи нельзя решать изолировано, независимо друг от друга, то возможный следующий подход к решению комбинированной задачи.
Сначала получают оптимальное решение задачи планирования производства. Затем в зависимости от этого оптимума находят наилучшее распределение оборудования. Наконец на основе такого распределения составляют оптимальный график выполнения работ.
Однако такая последовательная оптимизация частных подзадач не всегда приводит к оптимальному решению задачи в целом. Пока еще не найден метод, который бы дал возможность получить одновременный оптимум для всех трех задач, а возможно он и совсем не существует для конкретных задач. Поэтому для решения подобных комбинированных задач используют метод последовательных приближений, который дает возможность приблизиться к искомому решению комбинированной задачи как можно ближе.
Предложенная классификация задач исследования операций обычно не является исчерпывающей и окончательной. Со временем некоторые классы задач объединяются и становится возможным их совместное решение, кроме того появляются новые классы задач.
