Пример игры «Дилемма узников», или «Дилемма заключенных» (Prisoners’ Dilemma).

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

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

Таблица 5.1

Игра «Дилемма узников»

		Подозреваемый 2
		«Молчать»	«Говорить»
Подозреваемый 1	«Молчать»	(-1; -1)	(-15; 0)
«Говорить»	(0; -15)	(-5; -5)

 

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

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

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

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

2) если одна компания снизит цену, а конкурент будет продолжать продавать по высокой цене, тогда он останется в проигрыше;

3) если обе компании торгуют по низким ценам, прибыли незначительные.

Обобщением игры «Дилемма узников» считается трагедия общин (Tradegy of the commons). Этим термином обозначается род явлений, связанных с противоречием между личными интересами и общественным благом. В основном под этим имеется в виду проблема переиспользования общественного блага. Исходная формулировка этой ситуации заключается в следующем. Существует пастбище, на котором крестьяне пасут свой скот. Выпас скота уменьшает количество травы, растущей на нем. Каждый член общины может увеличить поголовье своего скота и тем самым увеличить свой доход, но при этом плодородие пастбища сократится, хотя и незначительно. Но если все члены общины сделают то же самое, пастбище станет уже намного хуже. Если же член общины уменьшит свой выпас, плодородие поля увеличится, но его личный выигрыш от этого будет намного меньше, чем потерянный доход. Получается, что всем членам общины выгодно только увеличивать использование пастбища. Трагедия общин показывает, как свободный доступ к ресурсу, например пастбищу, полностью уничтожает ресурс из-за чрезмерного его использования. Это происходит потому, что все пользующиеся им получают выгоду (или доход) непосредственно для себя, а издержки содержания ресурса ложатся на них всех равномерно.

Пример игры «Семейный спор» (Battle of the sexes).

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

Таблица 5.2

Игра «Семейный спор»

		Муж
		Футбол	Театр
Жена	Футбол	(1; 2)	(-3; -3)
Театр	(-1; -1)	(2; 1)

 

Это один из вариантов так называемой координационной игры, в которой «кооперативные» стратегии дают обоим игрокам лучший платеж, чем «эгоистические» стратегии.

3.2. Классификация игр.

Рассмотрим классификацию игр в зависимости от различных параметров.

Количество игроков. Различаются игры двух лиц (два участника игры) и игры n лиц (число участников более двух).

Количество стратегий. Если каждый из игроков имеет конечное число возможных стратегий в игре, то игра называется конечной. Если число стратегий хотя бы одного из участников игры бесконечно, то игра называется бесконечной.

Соотношение интересов участников. Игры с нулевой суммой – сумма выигрышей участников всегда равна нулю (антагонистические интересы – антагонистические игры). Игры с ненулевой суммой.

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

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

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

Кроме этого выделяют различные классы игр по иным признакам (статистические, дифференциальные и многие другие). В частности рассматривают так называемые «игры с природой», т.е. игры, когда в качестве второго игрока выступает не игрок с противоположными интересами, а некоторая сторона с «неопределенными» интересами (природа). В этом случае для поиска оптимальных стратегий наряду с принципом гарантированного результата используются и другие критерии, например Максимакса, Вальда, Сэдвиджа, Гурвица.

5.3. В некоторых играх имеется неопределенность, вызванная отсутствием информации об условиях, в которых осуществляется действие (погода, покупательский спрос и т.д.). Эти условия зависят не от сознательных действий другого игрока, а от объективной действительности. Такие игры называются играми с «природой». Человек в играх с «природой» старается действовать осмотрительно, второй игрок (природа, покупательский спрос) действуют случайно.

Условия игры задаются матрицей .

Пусть игрок А имеет стратегии А₁, А₂, ¼, А_m, а природа состояния В₁, В₂, ¼, В_n. Наиболее простой является ситуация, когда известна вероятность р_j каждого состояния природы В_j. При этом, если учтены все возможные состояния, то .

Если игрок А выбирает чистую стратегию А_i, то математическое ожидание выигрыша составит p₁a_i1 + p₂a_i2 + ¼ + p_na_in. Наиболее выгодной будет та стратегия, при которой достигается

(p₁a_i1 + p₂a_i2 + ¼ + p_na_in).

Если информация о состояниях природы мала, то можно применить принцип недостаточного основания Лапласа, согласно которому можно считать, что все состояния природы равновероятны

(a_i1 + a_i2 + ¼ + a_in)/ n,

т.е. стратегию, для которой среднее арифметическое элементов соответствующей строки максимальное.

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

1. Критерий Вальда. Рекомендуется применять максиминную стратегию. Она достигается из условия

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

2. Критерий максимума. Он выбирается из условия

.

Критерий является оптимистический, считается, что природа будет наиболее благоприятна для человека.

3. Критерий Гурвица. Критерий рекомендует стратегию, определяемую по формуле

,

где a - степень оптимизма и изменяется в диапазоне [0, 1].

Критерий придерживается некоторой промежуточной позиции, учитывающей возможность как наихудшего, так и наилучшего поведения природы. При a = 1 критерий превращается в критерий Вальде, при a = 0 – в критерий максимума. На a оказывает влияние степень ответственности лица, принимающего решение по выбору стратегии. Чем больше последствия ошибочных решений, больше желания застраховаться, тем a ближе к единице.

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

,

где max a_ij – максимальный элемент в столбце исходной матрицы.

Оптимальная стратегия находится из выражения:

.

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

Пример игры с природой

Фирма «Фармацевт» – производитель медикаментов и биомедицинских изделий в регионе. Известно, что пик спроса на препараты сердечно-сосудистой группы и анальгетики приходится на летний период, а на антиинфекционные и противокашлевые – на осенний и весенний периоды.

Затраты на 1 усл. ед. продукции за сентябрь – октябрь составили: по первой группе – 20 ден. ед., по второй группе – 15 ден. ед.

По данным наблюдений за несколько последних лет установлено, что фирма может реализовать в течение двух месяцев в условиях теплой погоды – 3050 усл. ед. продукции первой группы и 1100 усл. ед. продукции второй группы, а в условиях плохой погоды – 1525 усл. ед. продукции первой группы и 3690 усл. ед. второй группы.

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

Решение. Фирма располагает двумя стратегиями:

А₁ – в этом году будет теплая погода; А₂ – погода будет холодная.

Если фирма примет стратегию А₁ и в действительности будет теплая погода (стратегия природы В₁), то выпущенная продукция (3050 усл. ед. препаратов первой группы и 1100 усл. ед. второй группы) будет полностью реализована и доход составит:

3050 (40 – 20) +1100(30 – 15) = 77500 ден. ед.

В условиях прохладной погоды (стратегия природы В₂) препараты второй группы будут проданы полностью, а первой группы только в количестве 1525 усл. ед., и часть препаратов останется нереализованной. Фирма получит доход:

1525 (40 – 20) +1100 (30 – 15) – 20(3050 – 1525) = 16500 ден. ед.

Аналогично, если фирма примет стратегию А₂ и в действительности будет холодная погода, то ее доход будет:

1525(40 – 20) + 3690(30 – 15) = 85850 ден. ед.

При теплой погоде доход составит:

1525(40 – 20) + 1100(30 – 15) – 15(3690 – 1100) = 8150 ден. ед.

Рассматривая фирму и погоду (покупательский спрос) в качестве двух игроков, получим платежную матрицу

	В1	В2
А1
А2

 

a = max(16500, 8150) = 16500;

b = min(77500, 85850) = 77500.

Цена игры лежит в диапазоне 16500 ден. ед. £ v £ 77500 ден. ед.

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

Обозначим вероятность применения фирмой стратегии А₁ – х₁, А₂ – х₂, причем х₁ = 1 – х₂.

Решая игру, получим: х^* =(0,56; 0,44), при этом цена игры v = 47000 ден. ед. Оптимальный план производства лекарственных препаратов составит:

0,56(3050; 1100) + 0,44(1525; 3690) = (2562; 2108).

Ответ. Таким образом, фирме целесообразно производить в течение сентября и октября 2562 усл. ед. препаратов первой группы и 2108 усл. ед. препаратов второй группы, тогда при любой погоде она получит доход не менее 47000 ден. ед.

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

1. Критерий Вальда:

= max(16500; 8150) = 16500 ден. ед., фирме целесообразно использовать стратегию А₁.

2. Критерий максимума:

= max(77500; 858500) = 858500 ден. ед., целесообразно использовать стратегию А₂.

3. Критерий Гурвица. Для определенности примем a = 0,4, тогда для стратегии фирмы А₁

= 0,4×16500 + (1 – 0,4) 77500= 53100 ден. ед.

Для стратегии А₂

= 0,4×8150 + (1 – 0,4) 85850 = 54770 ден. ед.

max(53100; 54770) = 54770 ден. ед.

Фирме целесообразно использовать стратегию А₂.

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

Максимальный элемент в первом столбце – 77500, во втором столбце – 85850. Элементы матрицы рисков находят из выражения:

,

Откуда r₁₁ = 77500 – 77500 = 0, r₁₂ = 85850 – 16500 = 69350, r₂₁ = 77500 – 8150 = 69350, r₂₂ = 858500 – 858500 = 0.

Матрица рисков имеет вид:

= min (69350, 69350) = 69350 ден. ед., таким образом, критерий Сэвиджа не дает однозначной рекомендации по использованию какой-либо стратегии.

Следовательно, по совокупности критериев «природы» фирме целесообразно использовать стратегию А₂.

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

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

Пусть известно для рассматриваемой задачи, что вероятности теплой и холодной погоды равновероятны и равны 0,5. В этом случае оптимальная стратегия фирмы определяется:

max{(0,5×77500 + 0,5×5875), (0,5×8150 + 0,5×85850)} = (41687,5; 47000) = 47000 ден. ед.

Фирме целесообразно использовать стратегию А₂, т.е. рассчитывать свое поведение, ориентируясь на холодную погоду.

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

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

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

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

a ₁ (x, у^*) £ a ₁ (х^*, у^*), a ₁ (х^*, у) £ a ₁ (х^*, у^*) для любых х и у.

 

Пример. Определить точки равновесия для игры с матрицей выигрышей:

.

Решение. Нетрудно видеть, что в этой игре первому игроку невыгодно отклоняться от 1-й стратегии, если ее придерживается второй игрок, а второму игроку невыгодно отклоняться от 2-й стратегии, если ее придерживается первый игрок.

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

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

В этом случае игра (вернее ее исходы) представляется, как множество S на плоскости общих выигрышей а ₁ и а ₂ (рис. 5.1). Задаются значения выигрышей Т₁ и Т₂, которые могут получить соответственно 1-й и 2-й игроки без кооперации с партнером. В предположении о том, что множество S является выпуклым, замкнутым и ограниченным сверху, можно доказать, что оптимальные решения находятся на правой верхней границе этого множества.

На этой границе выделяется множество Р парето-оптимальных решений, на котором увеличение выигрыша одного из игроков возможно только за счет уменьшения выигрыша его партнера. На множестве Р точками и ограничено переговорное множество N; оно характерно тем, что игрокам нет смысла вести переговоры относительно решений вне его, так как положение одного из игроков может быть либо улучшено без ущерба для партнера, либо он может достичь лучшего выигрыша в одиночку. На переговорном множестве выделяется точка N ^*, соответствующая равновесию по Нэшу – точка Нэша; в ней достигается максимум произведения

max(a ₁ – T ₁)(a ₂ – T ₂),

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

Рис.5.1.

 

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

 

Пример. Кооперативная игра дается матрицей выигрышей:

.

Определить основные характеристики игры.

Решение. На плоскости а ₁0 а ₂ множеством S, определяющим игру, является треугольник с вершинами, данными в матрице: 0 (0, 0), А(2, 8), В(8, 2); это множество является выпуклым (рис. 5.2).

Рис. 5.2

Сторона АВ треугольника представляет собой парето-оптимальное множество: увеличение выигрыша одного игрока возможно только за счет партнера. Точка Т (4, 4) определяет выигрыши, которые игроки могут получить без взаимодействия с партнером. Переговорное множество N (отрезок и ) лежит на линии АВ. На этой линии находится точка Нэша N^*(5, 5) – в ней произведение (a ₁ – 5)(a ₂ – 5) для точек max(a ₁, a ₂), лежащих вне множества N, принимает наибольшее значение.

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

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

Пример игры «Вступление на рынок».

Пусть на рынке доминирует производитель – фирма 1 и монопольное положение приносит ей прибыль 10 млн ден. ед. Фирма 2 решает вопрос о внедрении на этот рынок при следующих известных предпосылках.

В случае вступления фирмы 2 на рынок фирма 1 может отреагировать следующим образом:

а) снизить объем производства и тогда поделить с фирмой 2 свою прибыль по 5 млн ден. ед. на каждого конкурента;

б) не уступать в объеме производства – тогда прибыль фирмы 1 понизится до 3 млн ден. ед. вследствие снижения рыночной цены, а фирма 2 понесет убытки в размере 2 млн ден. ед. тоже из-за падения рыночной цены на товар, а также из-за того, что предварительные затраты на проработку рынка и организацию производства не будут компенсированы.

Если фирма 2 воздерживается от вступления на рынок, то она ничего не выигрывает и не проигрывает, т.е. ее прибыль будет нулевой. В этом случае за фирмой 1 по-прежнему остаются два варианта поведения: не снижать объем производства с прибылью 10 млн ден. ед. и снизить объем производства со снижением прибыли до 8 млн ден. ед.

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

 

		Стратегия фирмы 1
		сохранить объем производства	снизить объем производства
Стратегия фирмы 2	вступить	(3; -2)	(5; 5)
не вступить	(10; 0)	(8; 0)

 

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

Рассматриваемая игра имеет две пары стратегий (две партии), приводящих к равновесию по Нэшу; при отказе фирмы 2 от внедрения на рынок фирма 1 не меняет объем производства; в случае вступления фирмы 2 на рынок фирма 1 снижает объем производства.

В непозиционной игре, когда игроки принимают решения одновременно и независимо друг от друга, реализация обеих стратегий была бы равновероятна. В позиционной игре необходимо учитывать, что фирма 1 принимает свои решения, уже зная о решении фирмы 2. Согласно принципу максимина, фирме 2 следовало бы избрать стратегию отказа от вступления на рынок: в этом случае ее прибыль составит 0 млн ден. ед., а это больше, чем – 2 млн ден. ед. в случае вступления. Однако здесь не учитывается предположение о рациональном поведении игроков, основой которого является стремление к максимизации своих выигрышей – в данном случае прибыли.

Рисунок – 5.3

 

С учетом этого обстоятельства более рациональной стратегией фирмы 1 при вступлении фирмы 2 на рынок является снижение производства, так как прибыль 5 млн ден. ед. все-таки больше, чем прибыль 3 млн ден. ед. Именно эта партия наиболее вероятна для реализации, когда фирма 2 вступит на рынок.

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

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

 

6. Методы сетевого планирования и управления.

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

6.2. Порядок и правила построения сетевых графиков.

6.3. Оптимизация сетевого графика.

6.4. Сетевое планирование в условиях неопределенности.

 

6.1. Система методов сетевого планирования и управления (СПУ) – это система методов планирования и управления разработкой крупных комплексов, научными исследованиями, конструкторской и технологической подготовкой производства, новых видов изделий, строительством и реконструкцией путем применения сетевых графиков.

Первые системы, использующие сетевые графики, были разработаны и использованы в США в середине 50-х годов. Основные понятия сетевого метода впервые наиболее полно были сформулированы в системе PERT (Program evaluation and review technique). В переводе с английского PERT означает метод оценки и обзора программы, где термин программа эквивалентен понятиям проект, разработка. Первый опыт применения нового метода при разработке ракеты «Поларис» для атомных подводных лодок превзошел все ожидания: по мнению специалистов срок разработки удалось сократить на 2-3 года, несмотря на то, что в ней принимали участие более 6000 фирм почти из всех штатов США.

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

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

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

Системы СПУ принято различать по характеру используемых в них сетевых моделей, которые в зависимости 1) от степени неопределенности информации могут быть детерминированными и вероятностными;

2) от количества независимых комплексов работ, отражаемых в модели, - односетевыми (система СПУ – однотемная или однозаказная) и многосетевыми (система СПУ – многотемная и многозаказная);

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

4) по составу параметров различают модели с учетом стоимости, времени и ресурсов.

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

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

Основными элементами сетевой модели являются работы, фиктивные работы и события.

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

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

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

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

По отношению к событиям называются непосредственно предшествующими (входящими) и непосредственно следующими (выходящими).

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

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

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

На рис. 6.1 представлен сетевой график разработки изделия.

 

Рис. 6.1. Сетевой график разработки изделия

 

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

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

Правила построения сетевого графика.

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

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

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

4. Любые два события должны быть непосредственно связаны не более чем одной работой-стрелкой.

5. В сети рекомендуется иметь одно исходное и одно завершающее событие.

Сетевой график должен быть упорядочен.

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

Одно из важнейших понятий сетевого графика – понятие пути.

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

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

Исходной информацией модели являются:

- детерминированная сеть с единственными исходным событием i₀ и завершающим событием i_w;

- продолжительности t_ij всех работ (i, j);

- момент начала выполнения комплекса T_i0=T₀, то есть момент наступления исходного события.

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

На основе модели определяют следующие параметры.

1. Критическое время T_кр – минимальное время, в течение которого может быть выполнен комплекс работ. Определяется продолжительностью критического пути L_кр, максимального полного пути сетевого графика, который может быть в общем случае и не единственным:

.

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

2. Ранние и поздние сроки наступления всех событий.

Ранний срок наступления i- го события - это минимальный из возможных моментов наступления данного события при заданных продолжительностях работ (без учета директивного срока). Определяется продолжительностью максимального предшествующего событию i пути L₁(i):

.

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

, (6.1)

где B(j) – множество событий i, соединенных с событием j работами (i,j).

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

.

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

, (6.2)

где C(i) – множество событий j, соединенных с i работами (i,j).

Для рассматриваемого примера и , на основе формул (4.1) и (4.2) рассчитаем основные параметры всех событий:

 

;

;

Продолжительность критического пути (критическое время):

.

3. Ранние и поздние сроки начала (окончания) всех работ.

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

Ранний срок окончания работы - это минимальный из возможных моментов окончания данной работы при заданных продолжительностях работ.

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

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

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

(6.3)

(6.4)

(6.5)

(6.6)

Одной из основных задач, решаемых в системах СПУ, является составление плана работ. Допустимым планом будет лишь такой, при котором выполняются следующие соотношения для сроков наступления всех событий T_i, начала и окончания всех работ t^н(i,j) и t^о(i,j):

;

;

.

В рассматриваемом примере результаты расчета ранних и поздних сроков начала и окончания работ представлены в табл. 6.1.

Таблица 6.1

Ранние и поздние сроки начала и окончания работ

(i,j)
0, 1		0+0,5=0,5	0,5-0,5=0	0,5
1, 2	0,5	0,5+1,5=2,0	2,0-1,5=0,5	2,0
2, 3		2,0+1,0=3,0	7,0-1,0=6,0	7,0
3, 4		3,0+1,0=4,0	8,0-1,0=7,0	8,0
1, 5	0,5	0,5+3,0=3,5	8,0-3,0=5,0	8,0
2, 6		2,0+6,0=8,0	8,0-6,0=2,0	8,0
6, 7		8,0+2,0=10,0	10,0-2,0=8,0	10,0
7, 8		10,0+1,0=11,0	11,0-1,0=10,0	11,0

 

4. Резервы времени для событий и работ.

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

. (6.7)

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

1) полный резерв

, (6.8)

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

2) свободный резерв

, (6.9)

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

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

.

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

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

, , ,

= , = , .

На рис. 6.1 критический путь выделен двойной линией.

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

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

Коэффициент напряженности пути L определяется отношением продолжительностей несовпадающих участков пути L и критического пути L_кр:

, (13.10)

где - продолжительность критических работ на пути L, T_кр – продолжительность критического пути.

Коэффициент напряженности работы (i,j) равен коэффициенту напряженности пути максимальной продолжительности L_m, проходящему через работу (i,j):

. (6.11)

Величина коэффициентов напряженности лежит в пределах , достигая единицы только на критических работах. Чем больше величина К^н, тем более жесткие сроки имеют работы, тем больше опасность превращения их в критические.

Вычисленные коэффициенты напряженности позволяют дополнительно классифицировать работы по зонам. В зависимости от величины выделяют три зоны: критическую ( >0,8); подкритическую (0,6 0,8); резервную ( <0,6).

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

Основные параметры работ и событий для рассмотренной сети представлены в табл. 6.2, 6.3.

Таблица 6.2

Параметры работ

Работа (i,j)	Параметры событий
А
0, 1				0,5	0,5
1, 2	0,5	0,5		2,0	2,0
2, 3	2,0	2,0		3,0	7,0
3, 4	3,0	7,0	4,0	4,0	8,0
1, 5	0,5	0,5		3,5	8,0
2, 6	2,0	2,0		8,0	8,0
6, 7	8,0	8,0
7, 8

 

Таблица 6.3

Параметры событий

Работа (i,j)	Параметры работ
А
0, 1	0,5		0,5		0,5
1, 2	1,5	0,5	2,0	0,5	2,0
2, 3	1,0	2,0	3,0	6,0	7,0	4,0		0,33
3, 4	1,0	3,0	4,0	7,0	8,0	4,0		0,33
1, 5	3,0	0,5	3,5	5,0	8,0	4,5		0,4
2, 6	6,0	2,0	8,0	2,0	8,0
6, 7	2,0	8,0		8,0
7, 8	1,0

 

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

Рис. 6.2. Представление параметров сети на графике

 

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

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

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

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

- параллельное выполнение работ критического пути;

- просмотр топологии сети, изменение состава работ и структуры сети.

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

6.4. При определении временных параметров сетевого графика предполагалось, что время каждой работы точно известно. Такое предположение в действительности выполняется редко: система СПУ обычно применяется для планирования сложных разработок, не имевших в прошлом никаких аналогов. Чаще всего продолжительность работы по сетевому графику заранее не известна и может принимать лишь одно из ряда возможных значений. То есть продолжительность работы t(i,j) является случайной величиной, характеризующейся своим законом распределения, а значит, своими числовыми характеристиками – средним значением, или математическим ожиданием, и дисперсией .

Практически во всех системах СПУ априори принимается, что распределение продолжительности работ обладает тремя свойствами:

а) непрерывностью;

б) унимодальностью, то есть наличием единственного максимума у кривой распределения;

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

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

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

 

Рисунок 6.3 - -распределение вероятностей продолжительности работ

 

Для определения числовых характеристик и этого распределения для работы (i,j) на основании опроса ответственных исполнителей проекта и экспертов определяют три временные оценки:

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

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

в) наиболее вероятную оценку - продолжительность работы (i,j) при нормальных условиях.

Предположение о -распределении продолжительности работы (i,j) позволяет получить оценки ее числовых характеристик:

;

.

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

.

Зная и , можно определять временные параметры сетевого графика и оценивать их надежность.

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

;

.

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

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

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

Полагая