Практическое применение теории игр (стр. 3 из 5)

1. События правильно пронумерованы, т. е. для каждой работы (i,j) i <j (см. на рис. работы (4,3) и (3,2)). При невыполнении этого требования необходимо использовать алгоритм перенумерации событий, который заключается в следующем:

нумерация событий начинается с исходного события, которому присваивается № 1;

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

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

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

2. Отсутствуют тупиковые события (кроме завершающего), т. е. такие, за которыми не следует хотя бы одна работа (событие 5);

3. Отсутствуют события (за исключением исходного), которым не предшествует хотя бы одна работа (событие 7);

4. Отсутствуют циклы, т. е. замкнутые пути, соединяющие событие с ним же самим (см. путь (2,4,3)).

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

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

t_p(N)= t_кр(L):

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

Этот показатель определяется «обратным ходом», начиная с завершающего события, с учетом соотношения t._п(N) = t_p(N). Все события, за исключением событий, принадлежащих критическому пути, имеют резерв R(i):

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

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

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

4.Моделирование систем массового обслуживания

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

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

Системы массового обслуживания могут быть классифицированы по ряду признаков.

1. В зависимости от условий ожидания начала обслуживания различают:

• СМО с потерями (отказами),

• СМО с ожиданием.

В СМО с отказами требования, поступающие в момент, когда все каналы обслуживания заняты, получают отказ и теряются. Классическим примером системы с отказами является телефонная станция. Если вызываемый абонент занят, то требование на соединение с ним получает отказ и теряется.

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

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

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

2. По числу каналов обслуживания СМО делятся на:

одноканальные;

многоканальные.

3. По месту нахождения источника требований МО делятся на:

- разомкнутые, когда источник требования находится вне системы;

- замкнутые, когда источник находится в самой системе.

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

Возможны и другие признаки классификации СМО, например, по дисциплине обслуживания, однофазные и многофазные СМО и др.

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

Аналитические методы теории массового обслуживания позволяют получить характеристики системы как некоторые функции параметров её функционирования. Благодаря этому появляется возможность проводить качественный анализ влияния отдельных факторов на эффективность работы СМО. Имитационные методы основаны на моделировании процессов массового обслуживания на ЭВМ и применяются, если, невозможно применение аналитических моделей. Далее будем рассматривать аналитические метод моделирования СМО.

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

Для простейшего потока частота поступления требований в систему подчиняется закону Пуассона, т.е. вероятность поступления за время t ровно k требований задается формулой:

Простейший поток обладает тремя основными свойств ординарности, стационарности и отсутствием последствия.

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

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

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

Отсутствие последействия означает, что число требований, поступивших в систему до момента t, не определяет того сколько требований поступит в систему за промежуток времени от t до t+

t.

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

времени обслуживания. Функция распределения для этого она имеет вид:

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

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