Сетевая модель и ее основные элементы

ОГЛАВЛЕНИЕ

Введение............................................................................................ 5

1. МЕТОДЫ СЕТЕВОГО ПЛАНИРОВАНИЯ И

УПРАВЛЕНИЯ..................................................................................... 6

1.1. Сетевая модель и ее основные элементы.................................. 6

1.2. Параметры сетевой модели с учетом временных

характеристик…………………...................................................... 12

1.3. Методы расчета параметров сетевой модели......................... 18

2 Вероятностные модели систем.................................. 26

2.1. Ориентированный граф состояния системы. Марковские

процессы........................................................................................... 26

2.2. Уравнения Колмогорова для вероятностей состояний.......... 30

2.3. Системы массового обслуживания (СМО)............................. 33

2.3.1. Общая характеристика СМО............................................. 33

2.3.2. Математическая модель однофазной СМО и показатели ее эффективности.............................................................................. 36

2.3.3. СМО с конечной очередью................................................ 40

2.3.4. СМО с отказами.................................................................. 43

2.3.5. Чистая СМО с ожиданием................................................. 43

2.3.6. Смешанные системы массового обслуживания.............. 46

2.3.7. Особенности применения моделей массового

обслуживания................................................................................ 48

3 Управление запасами......................................................... 51

3.1. Системы управления запасами................................................ 51

3.2. Управление запасами при детерминированном стационарном

спросе…………………..................................................................... 59

3.2.1. Мгновенная поставка, возникновение дефицита не допускается. 60

3.2.2.Мгновенная поставка, возникновение дефицита.............. допускается……………………… 62

3.2.3. Поставка с постоянной интенсивностью......................... 64

3.3. Однокаскадные СУЗ при вероятностном дискретном

спросе……………………………… 66

4 МЕТОДЫ ПРИНЯТИЯ ТЕХНИЧЕСКИХ РЕШЕНИЙ.......... 73

4.1. Основная формальная структура принятия решений............ 73

4.1.1. Матрица решений............................................................... 73

4.1.2. Оценочная функция............................................................ 76

4.1.3. Особые случаи..................................................................... 83

4.2. Классические критерии принятия решений........................... 84

4.2.1. Минимаксный критерий.................................................... 84

4.2.2. Критерий Байеса — Лапласа............................................. 85

4.2.3. Критерий Сэвиджа.............................................................. 86

4.2.4. Расширенный минимаксный критерий............................ 87

4.2.5. Применение классических критериев.............................. 88

4.3. Производные критерии............................................................. 91

4.3.1. Критерий Гурвица.............................................................. 91

4.3.2. Критерий Ходжа-Лемана................................................... 92

4.3.3. Критерий Гермейера.......................................................... 93

4.3.4. BL (MM)-критерий............................................................. 94

4.3.5. Критерий произведений..................................................... 97

4.3.6. Принятие решений согласно производным критериям.. 98

Литература............................................................................... 102

Введение

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

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

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

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

 

1 МЕТОДЫ СЕТЕВОГО ПЛАНИРОВАНИЯ
И УПРАВЛЕНИЯ

СЕТЕВАЯ МОДЕЛЬ И ЕЕ ОСНОВНЫЕ ЭЛЕМЕНТЫ

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

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

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

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

Наиболее распространен способ представления моделируемого комплекса работ в понятиях работ и событий.

Понятие «работа» имеет следующие значения:

– «действительная работа» – процесс, требующий затрат вре­мени и ресурсов;

– «фиктивная работа» – логическая связь между двумя или несколькими работами, указывающая на то, что начало одной ра­боты зависит от результатов другой. Фиктивная работа не тре­бует затрат времени и ресурсов, продолжительность ее равна нулю.

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

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

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

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

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

На сетевой модели событиям соответствуют вершины графа.

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

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

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

Пусть информация о комплексе работ задана табл. 1.1, в кото­рой работы условно обозначены символами а ₁, a ₂ ,.... Из табли­цы видно, что работы а ₁, а ₅, а ₆ не имеют предшествующих, поэтому в сетевой модели дуги, соответствующие этим работам, будут выхо­дить из исходного события комплекса. Работы а ₁₂, a ₁₃, a ₁₄ не пред­шествуют никаким другим работам, и поэтому дуги, соответствую­щие этим работам, будут входить в завершающее событие комп­лекса. Конечное событие работы а ₁ является начальным событием для работ a ₂, a ₂, a ₂; конечное событие для работы a ₂ является на­чальным для работы a ₁₄ и так далее Сетевой график комплекса изобра­жен на рис. 1.1.

Работы (дуги) на сетевых графиках обозначают символом (i, j), где i – номер начального события работы, а j – номер ко­нечного события. События должны быть пронумерованы так, что­бы для любой работы (в том числе и фиктивной) всегда i < j. Для получения такой нумерации применяется метод разделения собы­тий на ранги. Сущность метода заключается в следующем.

Таблица 1.1

Комплекс работ

Работа	Каким работам непосредственно предшествует	Работа	Каким работам непосредственно предшествует
a 1	a 2, a 3, a 4	a 8	a 12
a 2	a 14	a 9	a 11, a 13
a 3	a 11, a 13	a 10	a 12
a 4	a 9, a 10	a 11	a 14
a 5	a 9, a 10	a 12	–
a 6	a 7, a 8	a 13	–
a 7	a 9, a 10	a 14	–

	Рис. 1.1. Сетевой график

 

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

Легко видеть, что событие любого ранга связано с событием предшествующего ранга одной дугой. Следовательно, событие k- го ранга обязательно связано с исходным событием путем, со­стоящим из k дуг; хотя, кроме того, событие k- горанга может быть соединено с исходным событием и путем, состоящим из мень­шего числа дуг. Так, например, событие 6 на сетевом графике рис. 1.1 связано с исходным событием тремя путями: 1) путем, состоящим из дуг (0, 1), (1, 6); 2) путем, состоящим из дуг (0, 3), (3, 4), (4, 6) и 3) путем, состоящим из дуг (0, 1), (1, 3), (3, 4), (4, 6). Ранг события 6 равен 4, так как последний путь содержит максимальное число дуг, равное 4.

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

После распределения всех событий по рангам нумерация осу­ществляется следующим образом. Исходное событие нулевого ран­га получает номер 0. Событиям первого ранга в произвольном по­рядке присваивают номера 1, 2,..., n ₁, где п ₁ – число событий первого ранга; события второго ранга получают номера n ₁+1, n ₁+2,..., n ₁+ n ₂ где п ₂ – число событий второго ранга, и так далее

Так как события одного ранга между собой не соединены, а со­бытия меньшего ранга имеют меньший номер, то для любой дуги (i, j) всегда i < j.

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

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

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

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

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

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

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

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

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

Продолжительность работы (i, j) обозначают через t_ij. Оценка величины t_ij может производиться:

– по действующим нормативам;

– по накопленным данным с достаточно высоким процентом повторяемости работ;

– методом экспертных оценок;

– на основе вероятностных оценок.

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

В системах СПУ используются три вероятностные оценки:

a_ij – минимальное время, необходимое для выполнения работы при наиболее благоприятных условиях;

b_ij – максимальное время, необходимое для выполнения ра­боты при наименее благоприятных условиях;

m_ij – наиболее вероятное время выполнения работы при нор­мальных, наиболее часто встречающихся условиях.

Все эти оценки даются ответственными исполнителями или экспертами.

Величины a_ij, b_ij и m_ij используются для вычисления ожидае­мого значения продолжительности работы , представляющего со­бой математическое ожидание случайной величины t_ij, и дисперсии D_ij. Полученные значения и D_ij являются характеристи­ками случайной величины t_ij, распределенной по закону бета-рас­пределения. Кривая бета-распределения изображена на рис. 1.2.

Вследствие различного подхода к учету возможного отклонения реального закона распределения от принятого бета-распределения и ошибок в определении исходных величин a_ij, b_ij и m_ij, а также некоторых других факторов создано несколько формул для вычис­ления и D_ij. Из них в системах СПУ наиболее широко при­меняются следующие:

(1.1)

(1.2)

(1.3)

(1.4)

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

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

Комплексная (сводная) сетевая модель охватывает все работы комплекса. Сшивание комплексной модели производится анало­гично сшиванию частных моделей.

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

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

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

– исходное и завершающее события в детализированной и укрупненной моделях должны иметь одинаковый смысл:

– объединять в одну работу следует только такие группы ра­бот, которые закреплены за одним ответственным исполнителем.

1.2. ПАРАМЕТРЫ СЕТЕВОЙ МОДЕЛИ С УЧЕТОМ
ВРЕМЕННЫХ ХАРАКТЕРИСТИК

Исходная информация для модели включает сеть, продолжи­тельности t_ij всех работ (i, j), момент начала выполнения комп­лекса Т ₀, а также может содержать (но не обязательно) дирек­тивный срок Т_дир наступления завершающего события. Продол­жительности работ задаются как детерминированные неотрица­тельные величины.

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

Важнейшим параметром является критическое время T_кр – ми­нимальное время, за которое может быть выполнен весь комплекс. Критическому времени соответствует критический путь L_кр, то есть полный путь, продолжительность которого и составляет критиче­ское время: t (L_кр)= Т_кр. Очевидно, что продолжительность лю­бого другого полного пути равна или меньше критического време­ни Т_кр, поэтому критический путь можно определить как путь, имеющий максимальную продолжительность.

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

В плане выполнения всего комплекса, естественно, должны быть определены моменты наступления всех событий, начала и окончания работ. Как правило, эти моменты устанавливаются не однозначно, а располагаются в некотором диапазоне. При анализе сетевой модели определяются параметры, ограничивающие эти диапазоны. Такими параметрами для каждого k- го события яв­ляются ранний срок наступления события и поздний срок на­ступления события . Используя эти параметры, можно вычис­лить и другие параметры, в том числе критическое время T_кр и критический путь L_кр, на основании которых составляется план выполнения комплекса. Поэтому начнем с рассмотрения парамет­ров и .

Предварительно заметим, что все временные параметры сетевой модели можно определять как календарные (при этом момент на­чала выполнения комплекса Т ₀ должен быть задан календарной датой) и как относительные (при этом принимают Т ₀=0). В после­дующем изложении принято Т ₀==0.

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

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

(1.5)

где нулем обозначен номер исходного события.

Например, к событию 7 (рис.1.3) ведут три пути: 0–1–3–6–7, продолжительность которого равна 105 единицам времени;

0–1–2–5–7 с продолжительностью 60 ед. и 0–2–5–7 с продол­жительностью 85 ед. Очевидно, что событие 7 может наступить не раньше, чем через 105 ед. времени после исходного события, поэтому ед.

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

(1.6)

где N – номер завершающего события, причем = 0.

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

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

(1.7)

 

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

. (1.8)

Например, от события 6 (рис. 1.3) к завершающему событию ведут два пути: 6–7–8–9–10 с продолжительностью 195 ед. и 6–8–9–10, продолжительность которого равна 200 ед. Согласно формуле (1.8) . Очевидно, что если событие 6 наступит в момент (тo есть позднее ), а на выполнение работ, составляющих путь 6–8–9–10, требует­ся 200 ед., то в результате завершающее событие наступит в мо­мент, превышающий Т_кр на столько, на сколько больше . Действительно, вычислим поздний срок наступления события 6 как разность между Т_кр и продолжительностью первого пути: = Т_кр– 195 = 305–195 = 110 ед. С этого момента требуется еще 200 ед. времени на выполнение работ второго пути, следовательно, завершающее событие наступит через 110+200=310 ед. после на­чала работ, то есть T_кр будет превышено на 5 ед.

Правило вычисления значения по выражению (1.8) можно сформулировать более полно следующим образом: если от данного k -го события к завершающему ведут несколько путей, то зна­чение определяется как разность между критическим време­нем и продолжительностью максимального пути или, что то же са­мое, как минимальная из разностей между критическим временем и продолжительностью каждого из путей.

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

= T _кр. (1.9)

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

(1.10)

где .

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

Зная ранние и поздние сроки наступления событий, можно вы­числить для каждой работы (i,j):

– ранний срок начала

– ранний срок окончания ,

– поздний срок начала ,

– поздний срок окончания .

Первые два параметра – это самые ранние из возможных мо­ментов начала и окончания данной работы. Очевидно, что ранний срок начала работы совпадает с ранним сроком наступления ее начального события, а ранний срок окончания превышает его на величину продолжительности работы (i, j):

; (1.11)

. (1.12)

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

; (1.13)

. (1.14)

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

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

, (1.15)

где k – номер события.

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

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

– полный резерв

,(1.16)

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

– свободный резерв

, (1.17)

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

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

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

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

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