Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Исследование оп лекц.doc
Скачиваний:
0
Добавлен:
01.04.2025
Размер:
738 Кб
Скачать
☆

Тема 2 Принятие решений у задачах исследования операций

  1. Типичные классы задач исследования операций на транспорте

Накопленный опыт в решении практических задач исследования операций и его систематизация позволяют выделить по содержательной постановке следующие типичные классы задач: 1) управления запасами, 2) распределения ресурсов, 3) ремонта и замены оборудования, 4) массового обслуживания, 5) упорядочения, 6) сетевого планирования и управления, 7) выбора маршрута, 8) комбинированные.

Рассмотрим краткие особенности каждого класса задач.

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

В зависимости от условий задачи управления запасами делятся на следующие три группы:

1. Моменты поставок или оформления заказов на пополнение запасов фиксированы. Определить объемы производимых или закупаемых партий запасов.

2. Объемы производимых или закупаемых партий запасов фиксированы. Определить моменты оформления заказов на поставки.

3. Моменты оформления заказов и объемы производимых или за­купаемых партий не фиксированы. Определить эти величины, исходя из сформулированного выше критерия.

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

В зависимости от условий задачи распределения ресурсов делятся на три группы:

1. Заданы и работы, и ресурсы. Распределить ресурсы между работами таким образом, чтобы максимизировать некоторую меру эффективности (прибыль) или минимизировать ожидаемые затраты (издержки производства).

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

Какие способы производства надо выбрать для каждого вида изделий, чтобы выполнить задание с минимальными затратами?

2. Заданы только наличные ресурсы. Определить, какой состав работ можно выполнить с учетом этих ресурсов, чтобы обеспечить максимум некоторой меры эффективности.

Пример 1.2. Задано предприятие с определенными производственными мощностями. Какую продукцию следует производить, чтобы получить максимальный доход?

3. Заданы только работы. Определить, какие ресурсы необходимы для того, чтобы минимизировать суммарные издержки производства.

Пример 1.3. Известно месячное расписание движения пассажирских самолетов по авиалиниям. Какое количество экипажей необходимо подобрать, чтобы выполнить план перевозок с минимальными эксплуатационными затратами?

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

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

Определить такие сроки восстановительного ремонта и момент замены оборудования модернизированным, при которых минимизируется сумма затрат на ремонт и замену оборудования при его старении за все время эксплуатации.

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

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

Задачи массового обслуживания посвящены изучению и анализу систем обслуживания с очередями заявок, или требований. С явлением образования очередей приходится сталкиваться как в производственной практике, так и в быту. Типичными примерами являются очереди самолетов, ожидающих взлета или посадки, очереди клиентов в ателье бытового обслуживания, абонентов, ожидающих вызова на междугородной АТС, и т. д.

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

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

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

1. Минимизация общей продолжительности работ, т. е. интервала времени между моментом начала первой операции и моментом окончания последней.

2. Минимизация общего запаздывания. Запаздывание определяется как разность между фактическим и директивным сроком завершения обработки по каждой детали. Общее запаздывание представляет собой сумму запаздываний по всем деталям.

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

4. Минимизация потерь, обусловленных запаздыванием.

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

Для строгой постановки задач необходимы такие условия:

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

множество операций комплекса упорядочено так, что для каждой операции известно, какие операции непосредственно ей предшествуют, а какие следуют за ней;

в пределах заданного отношения упорядочения операции можно начинать и заканчивать независимо друг от друга;

известна взаимосвязь между величиной потребляемого ресурса и длительностью каждой операции.

Комплекс операций в этом случае можно представить в виде сетевого графика, состоящего из вершин (узлов) и ориентированных дуг. В этом случае операции изображают дугами, а вершины представляют собой некоторые события. Дуги, входящие в вершину, отвечают операциям, которые должны быть закончены раньше, чем можно будет начать операции, изображенные исходящими дугами. Событию, соответствующему началу выполнения комплекса, присваивают номер 0. Остальные события нумеруют так, что, если события і, j связаны некоторой операцией (і, j), то выполняется неравенство ta (j) >• tв (і) + tij, где tа (і), tв(j) — моменты наступления событий і, j и tij — длительность операции (i, j). Если выполняются вышеизложенные условия и допущения, возможны следующие постановки задач сетевого планирования и управления.

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

2. Заданы общие ресурсы. Определить сроки начала каждой операции, при которых минимизируется продолжительность выполнения всего комплекса работ. Методы решения задач СПУ изложены в [11].

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

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

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

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

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

1) сколько изделий каждого типа необходимо выпустить и каковы оптимальные размеры партий изделий? (Типичная задача планирования производства);

2) распределить производственные заказы по видам оборудования после того как определен оптимальный план производства. (Типичная задача распределения);

3) в какой последовательности и когда следует выполнять производственные заказы? (Типичная задача календарного планирования).

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

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

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