Типичные классы задач исследования операцийНакопленный опыт в решении практических задач исследования операций и его систематизация позволяют выделить по содержательной постановке следующие типичные классы задач [3, 18]: 1) задачи принятия решений; 2) задачи управления запасами; 3) задачи распределения ресурсов; 4) задачи ремонта и замены оборудования; 5) задачи массового обслуживания; 6) задачи упорядочивания: 7) задачи сетевого планирования и управления; 8) задачи выбора оптимального маршрута; 9) комбинированные задачи. Предложенная классификация задач исследования операций не является окончательной. Со временем некоторые классы задач объединяются, и становится возможным их совместное решение, стираются грани между предложенными классами задач, а также появляются новые классы задач. Существуют задачи [18], которые не укладываются ни в один из известных классов и представляют наибольший интерес с научной точки зрения. Рассмотрим краткую характеристику некоторых названных классов задач. Задачи принятия решений являются фундаментом науки исследования операций. В процессе принятия решений возникают такие трудности: - большое число несогласованных между собой критериев, - высокая степень неопределенности, которая обусловлена недостатком информации для обоснованного принятия решения. Решающее правило отличает информированность лица, принимающего решение, о возможных исходах выбранных решений, а также предпочтительность тех или иных исходов. Теория принятия решений использует различные процедуры, позволяющие формализовать предпочтения, т. е. выразить их в единой количественной мере. Основой для таких процедур является теория полезности, разработанная Дж. фон Нейманом и О. Моргенштерном. Её математическая основа – система аксиом, в которых утверждается, что существует некоторая мера ценности, позволяющая упорядочить результаты решений. Эта мера называется функцией полезности решений или полезностью В зависимости от условий внешней среды и степени информированности существует следующая классификация задач понятия решений: - в условиях определенности, - в условиях риска, - в условиях неопределенности, - в условиях конфликтных ситуаций. Более полное описание теории принятия решений рассмотрено в главе 2. Задачи управления запасами составляют самый распространенный и изученный в настоящее время класс задач исследования операций. Они обладают рядом особенностей. Например, с увеличением запасов увеличиваются расходы на их хранение. Следовательно одна из задач управления запасами заключается в определении такого уровня запасов, который минимизирует сумму ожидаемых затрат от хранения и потери от дефицита. В зависимости от условий задачи управления запасами делятся на следующие группы: 1. Моменты пополнения запасов фиксированы. Требуется определить объемы закупаемой или производимой партии запасов. 2. Объемы закупаемой или производимой партии запасов фиксированы. Требуется определить моменты оформления заказов. 3. Объемы производимой или закупаемой партии запасов и моменты оформления заказов не фиксированы. Требуется определить эти величины, исходя из сформулированных выше критериев. Задачи распределения ресурсов возникают, когда имеется определенный набор работ (операций), которые следует выполнить. В зависимости от условий задачи делятся на три группы: 1. Заданы работы и ресурсы. Требуется распределить ресурсы между работами таким образом, чтобы минимизировать ожидаемые затраты или максимизировать эффективность (например, прибыль). 2. Заданы ресурсы. Определить состав работ, который следует выполнить с учетом этих ресурсов, чтобы обеспечить максимум некоторой меры эффективности. 3. Заданы только работы. Определить, какие ресурсы необходимы, чтобы минимизировать суммарные издержки производства. Задачи ремонта и замены оборудования возникают тогда, когда работающее оборудование устаревает, изнашивается и подлежит замене. Изношенное оборудование подвергают либо восстановительному ремонту, либо полной замене. Тогда формулировка задачи заключается в следующем. Определить сроки восстановительного ремонта и момент замены оборудования, при которых суммарные ожидаемые затраты по ремонту и замене оборудования, а также потери вследствие ухудшения технологических характеристик – старения за время эксплуатации - минимизируются. Существует и такое оборудование, которое не может быть восстановлено и полностью подлежит замене. В этом случае постановка задачи имеет вид. Определить сроки профилактического контроля по обнаружению неисправностей, при которых суммарные затраты на проведение контроля и потери от простоя оборудования из-за несвоевременного обнаружения неисправностей и замены вышедших из строя деталей минимизируются. Задачи массового обслуживания предназначены для исследования вопросов образования и функционирования очередей, с которыми приходится сталкиваться на практике и в быту. Очереди возникают из-за того, что поток требований или клиентов на обслуживание неуправляем и случаен. Если количество приборов обслуживания достаточно велико, то очередь образуется редко, однако неизбежны длительные простои оборудования. С другой стороны, при малом количестве приборов создается значительная очередь, и будут большие потери из-за ожидания в очереди. Поэтому постановка задачи массового обслуживания следующая: определить, какое количество приборов обслуживания необходимо, чтобы минимизировать суммарные ожидаемые потери от несвоевременного обслуживания и простоев оборудования. Задачи упорядочивания связаны с формированием расписаний и очередностей выполнения некоторых работ. Пусть имеется множество различных деталей с определенными технологическими маршрутами, а также несколько единиц оборудования (станки), на которых эти детали обрабатываются. Так как обрабатывать более одной детали на одном станке нельзя, то у некоторых станков образуется очередь из деталей, ждущих обработки. Время обработки каждой детали известно. Определить такую очередность обработки деталей на каждом станке, при которой минимизируется некоторый критерий оптимальности. Такая задача называется задачей календарного планирования или составления расписания, а выбор очередности запуска деталей в обработку – упорядочением. Критерии оптимальности, используемые в задачах календарного планирования, имеют различный вид. Наиболее часто встречаются следующие критерии. 1. Минимизация общей продолжительности работ, т.е. интервалом времени между моментом начала первой операции и последней. 2. Минимизация общего запаздывания. Запаздывание определяется как разность между фактическим и директивным сроком завершения обработки по каждой детали. Общее запаздывание представляет собой сумму запаздываний по всем деталям. 3. Минимизация максимального запаздывания, т.е. минимизация запаздывания по той детали, для которой эта величина является наибольшей. 4. Минимизация потерь, обусловленных запаздыванием. Задачи сетевого планирования и управления. В этом классе задач рассматривается соотношение между сроком окончания крупного комплекса операций и моментами начала всех операций комплекса. Для строгой постановки задачи необходимо: - существование точно определяемого множества операций, которые нужно выполнить для завершения всего комплекса операций, - существование технологического маршрута: последовательности выполнения операций, - в пределах заданного отношения упорядочения операции можно начинать и заканчивать независимо друг от друга, - знать взаимосвязь между величиной потребляемого ресурса и длительностью каждой операции. Комплекс операций можно представить в виде сетевого графика, состоящего из вершин (узлов) и ориентированных дуг (операции изображают дугами, а вершины представляют собой некоторые события). Тогда возможны следующие постановки задач сетевого планирования и управления: 1. Задана продолжительность всего комплекса. Определить сроки начала каждой операции, при которых минимизируется один из критериев: 1) общие затраты на выполнения всего комплекса работ; 2) среднеквадратичный показатель неравномерности потребляемых ресурсов; 3) вероятность невыполнения комплекса работ в директивный срок; 4) среднеквадратичное отклонение требуемых ресурсов от наличных. 2. Заданы общие ресурсы. Определить сроки начала каждой операции, при которых минимизируется продолжительность выполнения всего комплекса работ. Задачи выбора маршрута, или сетевые задачи чаще всего встречаются при исследовании разнообразных процессов на транспорте и в системах связи. Типичной задачей является задача нахождения некоторого маршрута проезда из города А в город В при наличии нескольких маршрутов для разных промежуточных пунктов. Стоимость проезда и затраченное на проезд время зависит от выбранного маршрута. Определить наиболее экономичный маршрут по выбранному критерию оптимальности. На допустимые маршруты может быть наложен ряд ограничений: например, запрет на возврат к уже пройденному пункту или требование обхода всех пунктов сети с условием, что в каждом пункте можно побывать лишь один раз (задача о коммивояжере). В пунктах сети возможны задержки, которые зависят от нагрузки на узел, от занятости коммуникаций, ограничений пропускной способности сети или носят случайный характер. Наиболее распространенными сетевыми задачами являются: задача выбора кратчайшего расстояния между произвольными пунктами, задача о коммивояжере, задача о максимальном потоке. Комбинированные задачи включают в себя несколько типовых моделей задач одновременно. Например, при планировании и управлении производством приходится решать следующий комплекс задач: 1) сколько изделий каждого типа следует выпустить и каковы оптимальные размеры партий выпускаемых изделий? (Типичная задача планирования производства). 2) распределить производственные заказы по видам оборудования после того как определен оптимальный план производства. (Типичная задача распределения). 3) в какой последовательности и когда следует выполнять производственные заказы? (Типичная задача календарного планирования). Так как эти задачи нельзя решить изолированно, то возможен следующий подход. Сначала получают оптимальное решение задачи планирования производства. Затем в зависимости от этого оптимума находят наилучшее распределение оборудования. На основе полученного распределения оборудования получают оптимальный график выполнения работ. Однако такая последовательная оптимизация частных подзадач не всегда приводит к оптимальному решению в целом. Поэтому для решения подобных комбинированных задач чаще всего применяется метод последовательных приближений.
|
