Классы операционных задач

Внастоящее время исследование операций находит применение почти во всех областях целенаправленной человеческой деятельности. Отсюда широкий диапазон математических моделей операций и методов их исследования. В то же время исследование операций развивалось и продолжает развиваться по определенным направлениям, которые различаются типами задач, и появление новых направлений обусловливается возникновением новых задач. В классическом исследовании операций выделяют классы типичных задач, рассмотрение которых позволяет лучше представить круг проблем ИСО. Наиболее характерными классами операционных задач являются:

- задачи управления запасами;

- задачи распределения;

- задачи массового обслуживания;

- задачи выбора маршрута;

- задачи замены;

- задачи упорядочения;

- задачи сетевого планирования и управления;

- состязательные задачи;

- задачи поиска.

Приведем краткую характеристику и постановку перечисленных задач.

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

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

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

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

Классическим примером такой задачи является сбалансированная транспортная задача. С одной стороны, имеются поставщики с известными количествами груза, с другой - потребители сизвестными потребностями в грузе, при этом сумма потребностей равна сумме возможностей (баланс). Кроме того, для всех пар поставщик-потребитель даны затраты на перевозку единицы груза от поставщика к потребителю. Очевидно, что наилучшим вариантом удовлетворения отдельного потребителя будет поставка груза с минимальными для него затратами, однако это может привести к значительному возрастанию транспортных затрат у других потребителей. Поэтому задача состоит в определении такой схемы перевозки, при которой суммарные транспортные издержки будут минимальны. Разновидность транспортной задачи, называемая задачей о назначенияхили задачей выбора, заключается в распределении N кандидатов по Nдолжностям, работам или машинам при известной эффективности каждого кандидата на каждой должности с целью достижения максимальной эффективности всей системы (например, расстановка 10 спортсменов по 10 этапам эстафеты, обеспечивающая минимальное время прохождения всех этапов).

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

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

Задачи массового обслуживаниявозникают, когда имеет место поток заявок, требований или клиентов, нуждающихся в обслуживании. В общем случае заявки приходят через случайные промежутки времени и продолжительность обслуживания одной заявки также случайна. Системы, занятые обслуживанием таких потоков, называют системами массового обслуживания (СМО). Обычно в СМО выделяют 4 составляющих: поток заявок (входящий поток), очередь заявок, обслуживающие устройства, выходящий поток. Как следует из характера поступления и обслуживания заявок, в СМО может возникать как очередь заявок на обслуживание, так и очередь обслуживающих устройств (простои). Очевидно, что с любой очередью связаны потери. Различают СМО с отказами, когда при занятых устройствах пришедшая в систему заявка получает отказ и, следовательно, очереди заявок быть не может, и системы с ожиданием (с очередью), когда при занятых устройствах обслуживания заявка встает в очередь и ожидает обслуживания.

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

Задачи массового обслуживания особенно характерны для сферы услуг и производства. Примерами могут служить задачи организации торговли, медицинского обслуживания, ремонта, серийного и массового производства, работы вычислительного центра и отдельной ЭВМ в многозадачном и многопользовательском режимах и т.п.

Задачи выбора маршрута.В зависимости от вида искомого маршрута различают два варианта задач. Первый тип задач иногда называют задачами о кратчайшем пути. Между двумя заданными пунктами или узлами имеется конечное множество путей, состоящих из переходов (дуг), соединяющих промежуточные пункты. Один переход может входить более чем в один путь. Каждый переход характеризуется показателем или рядом показателей, в качестве которых могут быть время, длина, стоимость, расход ресурса и т.п. Требуется найти путь, кратчайший в смысле принятого критерия. Отметим, что искомым является незамкнутый путь и не требуется прохождение всехпромежуточных пунктов. При детерминированных показателях используется детерминированная модель, а при случайных показателях - вероятностная модель. Такие задачи возникают при прокладке маршрутов различных транспортных средств, трасс дорог, линий электропередач, трубопроводов, выборе вариантов поведения на заданном конечном промежутке времени, расчете сетевых графиков и т.д.

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

Первоначально задача коммивояжера рассматривалась как математическая головоломка, но в последние десятилетия обнаружили, что к ней сводится ряд важных практических проблем. Например, если на одном оборудовании каждый месяц нужно производить фиксированную номенклатуру изделий, а затраты на переналадку зависят от предшествующего и последующего видов изделий, то определение последовательности запуска изделий в производство, обеспечивающей минимальные затраты на переналадку в течение месяца, представляет собой типичную задачу коммивояжера. Другой пример: составляется программа для станка с ЧПУ на сверление нескольких десятков отверстий в плате и требуется определить порядок, в котором будет производиться сверление, так, чтобы общее время операции было минимальным. Это - тоже задача коммивояжера. В чем трудности решения таких задач, если число возможных вариантов всегда конечно? При трех городах имеется два варианта решения, при четырех - уже шесть, а при 11- более 3,6 млн. В общем случае задача коммивояжера с N городами (пунктами) имеет (N-1)! замкнутых маршрутов, проходящих через все пункты. Таким образом, в реальных задачах число возможных вариантов исчисляется астрономическими величинами и в этом заключается основная проблема решения задачи.

Рассматриваемая задача может быть обобщена на ткоммивояжеров. В базовом городе находится ткоммивояжеров, обслуживающих всех клиентов фирмы (клиент - город). Необходимо составить тзамкнутых маршрутов, охватывающих всех клиентов по одному разу и имеющих наилучший суммарный показатель, например, минимальную суммарную длину. Увеличение числа коммивояжеров повышает сложность задачи.

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

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

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

В качестве примера рассмотрим классическую задачу Джонсона. Каждая из N деталей обрабатывается на mстанках в одинаковом порядке, время обработки известно. Требуется определить очередность запуска деталей на обработку, обеспечивающую минимальное время обработки всех деталей. Для двух станков и двух деталей возможны только два варианта последовательности обработки, которые можно представить в виде графиков Ганта:

Нетрудно подсчитать, что Т_АB=14,а Т_BA=11 и, следовательно, оптимальной является очередность ВА.

Однако при двух станках и 10 деталях число вариантов уже превысит 3,6 млн., а для nдеталей оно составляет n!. Поэтому простым перебором вариантов задачу не решить.

Проблема еще более усложняется с увеличением числа станков. В общем случае в оптимальном решении очередность деталей на разных станках может быть неодинаковой, что значительно увеличивает число вариантов решения. Правда, теоретические исследования дали интересный результат: в оптимальном решении очередность одинакова на первых двух и на последних двух станках (но между собой эти очередности не совпадают). Отсюда следует, что при двух и трех станках очередность на всех станках одинакова. Но для большего числа станков это неверно. Так, например, для 5 станков возможны 3 различные очередности обработки и, значит, при 10 деталях число вариантов составит (10!)³=4,78×10¹⁹. Такие значения трудно представить.

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

Задачи сетевого планирования и управления.Одна из первых задач этого класса была поставлена и решена применительно к американской программе разработки ракет «Поларис». Программа охватывала огромное множество работ и большое число фирм-исполнителей, для координации которых требовались новые подходы. Таким образом, в отличие от задач упорядочения в задачах сетевого планирования рассматривается комплекс взаимосвязанныхработ. Исходным является список работ, подлежащих выполнению, с известными продолжительностями и непосредственно предшествующими работами.

Взаимосвязи работ моделируются ориентированным графом, называемым сетевым графиком или просто сетью. Возможны два варианта представления сети: 1) сеть типа "работы-дуги", когда дуга отображает работу с присущими ей параметрами (показателями) и связями, а вершины - состояния объекта (программы, проекта), к которому относятся работы; 2) сеть типа "вершины-работы", когда дуги показывают только связи, а работам ставятся в соответствие вершины. Для первоначального построения сети удобнее второй вариант, но для расчетов чаще используется сеть "работы-дуги". Существуют простые алгоритмы перехода от одного представления к другому. Сеть может быть детерминированной и вероятностной. Во втором случае обычно случайным является время выполнения работ или ряд работ альтернативны с известными вероятностями необходимости их выполнения. С работами может быть связано время (простейшие сети), ресурсы, стоимость или их сочетания. Сеть может применяться один раз или многократно. По ходу выполнения работ сеть может корректироваться. В задачах сетевого планирования и управления различают анализ и синтез сети.

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

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

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

Различают две модели конфликта: игру и аукционный торг. Игра характеризуется известным количеством участников, называемых игроками,правилами игры, множеством возможных ситуаций (сочетаний стратегий игроков) и соответствующими им выигрышами или проигрышами (в общем случае платежами).По методу ведения игры различают дискретные игры, в которых игроки совершают поочередные ходы, и непрерывные, когда игроки действуют непрерывно. Последние также называют играми преследования (например, бой двух самолетов) или дифференциальными играми, так как поведение игроков описывается дифференциальными уравнениями. По количеству ходов выделяют игры с конечным и бесконечным числом шагов. Аналогичное деление производится по числу стратегий игроков. Так у противотанкового орудия имеется бесконечное число стратегий, так как огонь по нападающим танкам может быть открыт с любого расстояния, начиная с прицельной дальности стрельбы. По форме платы различают игры с нулевой суммой, когда выигрыши одних равны проигрышам других, и поэтому их также называют антагонистическими (цели полностью противоположные), и игры с ненулевой суммой, в которых выигрыши и проигрыши не совпадают. В зависимости от числа игроков говорят об играх 2, 3, ..., 7, N лиц. Дискретную игру двух лиц с ненулевой суммой называют биматричной игрой, в ней каждой ситуации соответствует два платежа (по одному для каждого игрока).

С основными положениями биматричных игр мы с вами знакомы.

Помимо рассмотренных нами моделей игр применяются также модели коалиционных и кооперативных игр. Так, в игре плиц (п>2) с нулевой суммой в процессе игры могут образовываться объединения части игроков против остальных, если такая коалиция улучшает результаты всех объединившихся игроков, что обеспечивается побочными платежами со стороны инициатора объединения. В отличие от этого кооперативная игра может улучшать результаты всех игроков за счет предварительных договоренностей с заключением обязывающих соглашений (в играх с ненулевой суммой). Очевидно, что кооперация возможна и в игре двух лиц.

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

Модели типа аукционного торгаприменяются, когда степень неопределенности выше, чем предполагает модель игры. Так, например, в аукционном торге неизвестно даже число участников, нельзя составить принятую в игре платежную матрицу. Разработка и исследование моделей этого типа находятся в начальной стадии.

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

Для поиска необходимы ресурсы (в общем случае он требует затрат). При ограниченных ресурсах на поиск увеличение выборки уменьшает ошибку выборки, но одновременно возрастает ошибка наблюдения, а при уменьшении объема выборки - наоборот. Задача заключается в определении объема выборки и стратегии поиска внутри нее, при которых достигается наибольшая эффективность поиска. Характерным примером такой задачи является контроль качества деталей или изделий при серийном или массовом производстве. Основным ресурсом при этом выступают контролеры ОТК, число которых всегда ограничено. Чем больше выборка, тем меньше негодных деталей пройдет мимо контролера, но тем меньше времени у него на проверку каждой детали, попавшей в выборку, а значит, больше вероятность пропуска негодной детали или отбраковки годной. Бракованные детали, не обнаруженные контролером, могут проявить себя только при испытаниях готовой продукции или у потребителя, что влечет убытки для производителя. Задача контроля качества - организовать его так, чтобы убытки свелись к минимуму.

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

Некоторые области применения задач поиска:

- организация ревизий;

- бухгалтерские операции;

- обнаружение объектов (потерпевших аварию, заблудившихся, пожаров и т.п.);

- военная разведка;

- разведка полезных ископаемых;

- организация контроля качества;

- хранение и поиск информации;

- размещение рекламы в районе или городе.

Следует заметить, что модели поиска разработаны слабо. В основном они носят частный характер.

Резюме

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

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

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