Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







Тема 6. Математические модели принятия решений





1. Модели теории очередей (массового обслуживания)

2. Модели управления запасами

3. Задача упорядочения и согласования

4. Задача о назначении

5. Модели линейного программирования

 

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

1. Модели теории очередей (массового обслуживания)

Модели массового обслуживания условно делят на модели анализа и модели синтеза-оптимизации систем массового обслуживания.

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

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

                                   
           
       
       
 
 
         
 
     
         
 
 
 
     

 

 

           
     
 

               
 
       
 

               
   
Каналы обслуживания
 
Выходящие потоки
 
Входящие потоки
 
Очереди
 
 
 
 

 


Рис.1.

 

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

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

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

1) вероятность простоя канала обслуживание ;

2) вероятность того, что в системе находится n требований,- ;

3) среднее число требований, находящихся в системе (сфере обслуживания)

4) среднее число требований, находящихся в очереди

где - число каналов обслуживания:

5) среднее время ожидания требований в очереди :

а) для разомкнутой системы интенсивность поступления потока требований в систему;

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

6) среднее время ожидания требований в системе ;

7) среднее число свободных каналов обслуживания

;

8) среднее число занятых каналов обслуживания

.

Имеется большое число разновидностей систем массового обслуживания.

Самая простая – детерминированная одноканальная;


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

Имеется один канал обслуживания.

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

 

Основные особенности, взаимосвязи и количественные закономерности.

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

Схема рассматриваемой системы массового обслуживания:

                           
   
Пункт обслуживания
 
 
 
 
     
 
 
     

 

 

           
 
     
 
 

                                               
 
 
                 
 
   
Входящий поток требований
     
Очередь
 
Выходящий поток требований
 
 

 


Рис. 2

 

Пока обслуживается очередь из требований в течение времени вновь поступит на обслуживание требований:

Аналогично, пока будут обслуживаться требований в течение времени дополнительно поступит на обслуживание требований:

 

Это происходит до тех пор, пока , после чего очередь исчезнет.

Весь процесс функционирование системы представим в аналитическом виде.

Построение математической модели:

Время, через которое очередь исчезнет, можно представить в виде:

Исследование математической модели:

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

В модели использована формула суммы геометрической прогрессии.

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

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

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

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

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

2. Модели управления запасами

Можно выделить четыре основные причины, приводящие к необходимости образования запасов:

1) необходимость гарантирования бесперебойного питания производственного процесса с целью обеспечения его непрерывности;

2) периодичность производства отдельных сорторазмеров материальных ресурсов у поставщиков;

3) особенности транспортировки от поставщика до потребителя (несоответствие грузоподъемности транспортных средств и размеров потребления);

4) несовпадение ритма производства и поставок производственных ресурсов с ритмом их потребления.

Задача управления запасами в общем случае формируется так.

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

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

Существует множество постановок задачи управления запасами.

Рассмотрим самую простую: однопродуктовую детерминированную задачу управления запасами.

Постановка задачи и выбор критерия оптимизации:

Пусть месячная потребность предприятия в каком-либо материале (песок, щебень, цемент и т.д.) составляет Q условных единиц. Расход этого материала во времени происходит равномерно. Необходимо определить: каков должен быть размер поставки материалов, чтобы суммарные затраты на создание и хранение запаса были минимальны.

 

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

Обозначим - затраты на хранение единицы запаса в единицу времени, а - затраты на доставку партии материалов. Пусть затраты не зависят от количества материалов в поставляемой партии. Предполагается, что все партии состоят из одинакового числа единиц материала, S – величина поставок.

Движение запасов в течение времени Т (месяца) можно изобразить графически:

t – промежуток времени (период) от момента поставки партии материала до момента ее израсходования.

       
   
 
 

 


S

 
 

 


(мгновенное время пополнения запасов)

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

Построение математической модели

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

Исследование математической модели

Продифференцировав целевую функцию относительно и приравняв производную нулю, получим

откуда

Это выражение называется формулой Вильсона, из которой можно устанавливать оптимальный размер поставок. С помощью этой функции можно установить и оптимальные моменты времени пополнения запасов.

 

Лекция 10

3. Задача упорядочения и согласования

1) Детерминированная задача упорядочения

Постановка задачи и выбор критерия оптимизации

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

Таблица 1

Номер издания j            
Время обработки на первой машине t1j            
Время обработки на второй машине t2j            

 

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

 

Основные особенности, взаимосвязи и количественные закономерности.

Основные ограничения задачи:

 

1) Время перехода изделия от одной машины к другой незначительно и им можно пренебречь;

2) Каждое изделие обрабатывается в определенном технологическом порядке;

3) Каждое обслуживание должно быть завершено прежде, чем начнется следующее.

Обозначения:

t1i – время обработки i – го изделия на первой машине;

t2i – время обработки i – го изделия на второй машине.

 

Изобразим процесс обработки изделий на двух машинах графически:

Время обработки на Машине 1   t11=6 t12=4 t13=6 t14=5 t15=7 t16=4
Время обработки на Машине 2   Время простоя Машин 2   t21=5 t22=2 t23=3 t24=6 t25=6 t26=7     tn1 tn2 tn3 tn4 T
 
  Рис.1.

 

Т – полное время, которое пройдет от начала обработки первого изделия на первой машине до конца обработки последнего изделия на второй машине.

 

Построение математической модели.

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

Тогда суммарное время обработки изделий составит

,

 

а так как сумма известна, то надо минимизировать (в нашем случае ).

Исследование математической модели.

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

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

Алгоритм включает следующие основные этапы:

1) Поиск наименьшего элемента.

Ищем в Т-2 наименьший элемент (равен 2, относится ко второй машине) и отмечаем точкой

 

Таблица 2

Номер издания j            
Время обработки на первой машине t1j            
Время обработки на второй машине t2j   2 ● 3 ●      
Номер цикла              

 

 

2) Перестановки изделий; Определяется место нахождения элемента. Если этот элемент относится к первой машине, то столбец с точкой поставить на первое место, если ко второй, то поставить на последнее место календарного плана

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

Таблица 3

 

Номер издания j            
Время обработки на первой машине t1j            
Время обработки на второй машине t2j            

 

2) Вычеркивание из таблицы столбца, отмеченного точкой и возвращение к п.1 и так далее, пока не будет исчерпан список всех изделий. Получим оптимальную последовательность обработки на двух машинах (Т-3).

 

Процесс оптимальной обработки

  Время обработки на Машине 1   t16=4 t14=5 t15=7 t11=6 t13=6 t12=4
Время обработки на Машине 2   Время простое Машин 2   t26=7 t24=6 t25=6 t21=5 t23=3 t22=2   tn1 tn2   Tmin = 29+4+1 = 34

 







ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...

ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...

ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...

Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор...





Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:


©2015- 2024 zdamsam.ru Размещенные материалы защищены законодательством РФ.