Решение.

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

t_A = (a_A + 4 m_A + b_A)/6 = (4 + 4 * 5 + 12)/6 = 6;

= var_A = ((b_A - a_A)/6)² = ((12 – 4)/6)² = 1.78.

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

Работа	Ожидаемое время ti	Дисперсия	Непосредственно предшествующая работа
A		1.78	-
B		0.44	-
C		0.11	A
D		1.78	A
E		0.11	A
F		0.03	C
G		0.25	D
H		0.69	B, E
I		0.03	H
J		0.11	F,G,I

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

Результаты расчетов представлены в следующей таблице.

Работа	Время выполнения	tрн	tро	tпн	tпо	Дисперсия	R
A						1.78
B						0.44
C						0.11
D						1.78
E						0.11
F						0.03
G						0.25
H						0.69
I						0.03
J						0.11

Критический путь для данного проекта включает работы A, E, H, I, J. Длина критического пути равна 6 + 3 + 4 + 2 + 2 = 17. Это означает, что ожидаемое время выполнения проекта составляет 17 недель.

Предполагая, что распределение времени выполнения проекта является нормальным, мы можем определить вероятность того, что проект будет выполнен за 20 недель. Определим дисперсию времени выполнения проекта. Ее значение равно сумме значений дисперсий времен выполнения работ на критическом пути: s²(T)= 1.78+ 0.11 + 0.69 + 0.03 +0.11 = 2.72. Тогда, учитывая, что s(T) = 1.65, находим значение z для нормального распределения при T0=20:

z = (T0-E(T))/ s (T) = (20-17) /1.65 = 1.82.

Используя таблицу нормального распределения, находим вероятность того, что время T выполнения проекта находится в интервале E(T)≤T≤T0. На пересечении столбца «1.8» и строки «0.02» таблицы нормального распределения находим значение 0.4656. Следовательно, искомая вероятность того, что время T выполнения проекта находится в интервале 0≤T≤T0, т.е. вероятность того, что проект будет выполнен за 20 недель при ожидаемом времени его выполнения 17 недель, равна 0.5 + 0.4656 = 0.9656.

Контрольные вопросы.

1. Метод PERT разработан для:

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

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

в. минимизации издержек на сокращение продолжительности проекта

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

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

2. Объясните суть оптимизации сетевых моделей по критерию «Время - затраты».

3. Какими свойствами должна обладать работа, выбираемая на конкретном шаге для сокращения?

5. Варианты заданий по теме «Метод PERT»

Вариант 1

Ниже даны оценки продолжительности выполнения работ (в днях) применительно к небольшому проекту:

Работа	Оптимистическое время аi	Наиболее вероятное время mi	Пессимистическое время bi
A
B
C		7.5
D
E
F

Рассчитайте ожидаемое время выполнения и дисперсию для каждой работы. Известно, что критический путь составляют работы B, D, F.

Найдите:

§ чему равно ожидаемое время выполнения работы B;

§ чему равна дисперсия времени выполнения работы D;

§ ожидаемое время выполнения проекта;

§ чему равна дисперсия времени выполнения проекта.

Вариант 2

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

Работа	Непосредственно предшествующая работа	Оптимистическое время аi	Наиболее вероятное время mi	Пессимистическое время bi
A	-
B	-
C	A, B
D	A, B
E	B
F	C
G	D
H	D, F
I	E, G, H

Постройте сеть для этого проекта.

Найдите:

§ каков ожидаемый срок завершения проекта;

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

§ какова вероятность того, что проект будет выполнен за 24 рабочих дня.

Вариант 3

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

Работа	Непосредственно предшествующая работа	Оптимистическое время ai	Наиболее вероятное время mi	Пессимистическое время bi
A	-
B	-	2.5		3.5
C	A
D	A		5.5
E	B
F	D, E
G	D, E
H	C, F

Найдите:

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

§ какова вероятность того, что проект будет завершен за 21 неделю;

§ какова вероятность того, что проект будет завершен за 25 недель.

6. Оптимизация сетевых моделей по критерию «время-затраты»

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

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

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

6.1. Методика оптимизации сетевых моделей по критерию «Время – затраты»

Целью оптимизации по критерию «Время – затраты» является сокращение времени выполнения проекта в целом. Эта оптимизация имеет смысл только в том случае, когда время выполнения работ может быть уменьшено за счет задействования дополнительных ресурсов, что приводит к повышению затрат на выполнение работ (см. Рисунок 1). Для оценки величины дополнительных затрат, связанных с ускорением выполнения той или иной работы, используются либо нормативы, либо данные о выполнении аналогичных работ в прошлом. Под параметрами работ и понимаются так называемые прямые затраты, непосредственно связанные с выполнением конкретной работы. Таким образом, косвенные затраты типа административно-управленческих в процессе сокращения длительности проекта во внимание не принимаются, однако их влияние учитывается при выборе окончательного календарного плана проекта.

Рисунок 1. Зависимость прямых затрат на работу от времени ее выполнения

Важными параметрами работы (i,j) при проведении данного вида оптимизации являются:

· коэффициент нарастания затрат

,

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

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

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

.

Эта ситуация имеет место, когда длительность работы (i,j) еще ни разу не сокращали, т.е. .

Общая схема проведения оптимизации «время-затраты»

1. Исходя из нормальных длительностей работ , определяются критические L_kp и подкритические L_п пути сетевой модели и их длительности T_kp и T_п.

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

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

3.1. Для сокращения выбирается критическая работа с min коэффициентом нарастания затрат k(i,j), имеющая ненулевой запас времени сокращения Z_T(i,j).

3.2. Время , на которое необходимо сжать длительность работы (i,j), определяется как

,

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

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

.

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

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

6.2 Пример проведения оптимизации сетевой модели по критерию «Время - затраты»

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

Таблица 1

Исходные данные для оптимизации «Время-затраты»

(i,j)	Нормальный режим	Ускоренный режим
Tн(i,j)	Сн(i,j)	Tу(i,j)	Сп(i,j)
(1,2)
(1,4)
(2,3)
(2,4)
(3,5)
(4,5)
Ск=1,50 руб./день	С0=73,00 руб.

Рисунок 2. Исходная сетевая модель

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

· Общие затраты на проект руб.

· Длительность проекта дней.

· Критический путь или .

· Подкритический путь или , дней.

Кроме того, вычислим коэффициенты нарастания затрат и максимальные запасы времени сокращения работ сетевой модели (таблица 2).

Таблица 2

Коэффициенты нарастания затрат работ сети

(i,j)	Zmax(i,j) [дни]	k(i,j) [руб./день]
(1,2)		7,00
(1,4)		3,00
(2,3)		3,50
(2,4)		2,00
(3,5)		0,60
(4,5)		1,00

Рисунок3. Сетевая модель после первого шага оптимизации

I шаг. Для сокращения выбираем критическую работу (4,5) с минимальным коэффициентом k(4,5)=1,00 руб./день. Текущий запас сокращения времени работы (4,5) на данном шаге равен дня. Разность между продолжительностью критического и подкритического путей дня. Поэтому согласно п.3.2 описанной выше общей схеме оптимизации сокращаем работу (4,5) на ∆t¹=min[3,2]=2 дня. Новая текущая длительность работы дня, а запас ее дальнейшего сокращения сокращается до дня. Измененный сетевой график представлен на рисунке 3

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

· Затраты на работу возросли на 1,00руб./день*2дня=2,00 руб. и общие затраты на проект составили руб.

· Длительность проекта дней.

· Критические пути и .

· Подкритический путь , дней.

II шаг. Одновременное сокращение двух критических путей можно провести либо ускорив работу (1,2), принадлежащую обоим путям, либо одновременно ускорив различные работы из каждого пути. Наиболее дешевым вариантом является ускорение работ (3,5) и (4,5) – 1,60 руб./день за обе работы, тогда как ускорение работы (1,2) обошлось бы в 7 руб./день. Поскольку , то сокращаем работы (3,5) и (4,5) на ∆t²=min[5,1,6]=1 день. Запасы дальнейшего сокращения времени работ сокращаются до и дней. Измененный сетевой график представлен на Рисунок 4.

Рисунок 4. Сетевая модель после второго шага оптимизации

После ускорения работ (3,5) и (4,5) возникли следующие изменения.

· Общие затраты на проект составили

руб.

· Длительность проекта дней.

· Два критических пути и .

· Подкритический путь , дней.

III шаг. Поскольку на данном шаге работа (4,5) исчерпала свой запас ускорения, то наиболее дешевым вариантом сокращения обоих критических путей является ускорение работ (3,5) и (2,4) - 2,60 руб./день за обе работы. Сокращаем работы (3,5) и (2,4) на ∆t³=min[4,4,6]=4 дня. Запасы дальнейшего сокращения времени работ (3,5) и (2,4) обнуляются. Измененный сетевой график представлен на Рисунок5.

Рисунок 5. Сетевая модель после третьего шага оптимизации

После ускорения работ (3,5) и (2,4) возникли следующие изменения.

· Общие затраты на проект составили

руб.

· Длительность проекта дней.

· Два критических пути и .

· Подкритический путь , дней.

IV шаг. Поскольку кроме работы (1,2) все остальные работы критического пути исчерпали свой запас времени ускорения, то единственно возможным вариантом сокращения обоих критических путей является ускорение работы (1,2). Сокращаем работу (1,2) на дня. Запас дальнейшего сокращения времени работы (1,2) обнуляется. Измененный сетевой график представлен на Рисунок 6.

Рисунок 6. Сетевая модель после четвертого шага оптимизации

Рисунок 7 График время–затраты

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

· Общие затраты на проект составили руб.

· Длительность проекта дней.

· Три критических пути , и .

· Подкритические пути отсутствуют.

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

Таким образом, при отсутствии ограничений на затраты минимально возможная длительность проекта составляет 7 дней. Сокращение длительности проекта с 16 до 7 дней потребовало 28,00 рублей прямых затрат. В отличие от прямых затрат при уменьшении продолжительности проекта косвенные затраты (С_к=1,50 руб./день) убывают, что показано на графике (см. Рисунок 7). Минимум общих затрат (точка А) соответствует продолжительности проекта 14 дней.

Если же учитывать ограничение по средствам, выделенным на выполнение проекта, С₀=73,00 рубля, то оптимальным является выполнение проекта за 9 дней (точка B).

7. Варианты заданий по теме «Оптимизация сетевых моделей по критерию «Время-затраты»

Задание

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

Вариант 1

Назв. работы	Норм. длительность	Норм. стоимость	Сокр. длительность	Повыш. стоимость
A
B
C
D
E
F
G
H
I
J
K
	С0=99,00 руб.	Ск=1,20 руб./день

Упорядочение работ

1) A,E и F - исходные работы проекта, которые можно начинать одновременно;

2) Работы B и I начинаются сразу по окончании работы F;

3) Работа J следует за E, а работа C - за A;

4) Работы H и D следуют за B, но не могут начаться, пока не завершена C;

5) Работа K следует за I;

6) Работа G начинается после завершения H и J.

Вариант 2

Назв. работы	Норм. длительность	Норм. стоимость	Сокр. длительность	Повыш. стоимость
A
B
C
D
E
F
G
H
I
	С0=100,00 руб.	Ск=0,90 руб./день

Упорядочение работ

1) D - исходная работа проекта;

2) Работа E следует за D;

3) Работы A, G и C следуют за E;

4) Работа B следует за A;

5) Работа H следует за G;

6) Работа F следует за C;

7) Работа I начинается после завершения B, H, и F.

Вариант 3

Назв. работы	Норм. длительность	Норм. стоимость	Сокр. длительность	Повыш. стоимость
A
B
C
D
E
F
G
H
I
J
	С0=143,00 руб.	Ск=0,60 руб./день

Упорядочение работ

1) С, E и F - исходные работы проекта, которые можно начинать одновременно;

2) Работа A начинается сразу по окончании работы С;

3) Работа H следует за F;

4) Работа I следует за A, а работы D и J - за H;

5) Работа G следует за E, но не может начаться, пока не завершены D и I;

6) Работа B следует за G и J.

ПРИЛОЖЕНИЕ

Таблица нормального распределения.

z 0.00 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09

0.0¦.0000.0040.0080.0120.0160.0199.0239.0279.0319.0359

0.1¦.0398.0438.0478.0517.0557.0596.0636.0675.0714.0753

0.2¦.0793.0832.0871.0910.0948.0987.1026.1064.1103.1141

0.3¦.1179.1217.1255.1293.1331.1368.1406.1443.1480.1517

0.4¦.1554.1591.1628.1664.1700.1736.1772.1808.1844.1879

0.5¦.1915.1950.1985.2019.2054.2088.2123.2157.2190.2224

0.6¦.2257.2291.2324.2357.2389.2422.2454.2486.2518.2549

0.7¦.2580.2612.2642.2673.2704.2734.2764.2794.2823.2852

0.8¦.2881.2910.2939.2967.2995.3023.3051.3078.3106.3133

0.9¦.3159.3186.3212.3238.3264.3289.3315.3340.3365.3389

1.0¦.3413.3438.3461.3485.3508.3531.3554.3577.3599.3621

1.1¦.3643.3665.3686.3708.3729.3749.3770.3790.3810.3830

1.2¦.3849.3869.3888.3907.3925.3944.3962,3980.3997.4015

1.3¦.4032.4049.4066.4082.4099.4115.4131.4147.4162.4177

1.4¦.4192.4207.4222.4236.4251.4265.4279.4292.4306.4319

1.5¦.4332.4345.4357.4370.4382.4394.4406.4418.4429.4441

1.6¦.4452.4463.4474.4484.4495.4505.4515.4525.4535.4545

1.7¦.4554.4564.4573.4582.4591.4599.4608.4616.4625.4633

1.8¦.4641.4649.4656.4664.4671.4678.4686.4693.4699.4706

1.9¦.4713.4719.4726.4732.4738.4744.4750.4756.4761.4767

2.0¦.4772.4778.4783.4788.4793.4798.4803.4808.4812.4817

2.1¦.4821.4826.4830.4834.4838.4842.4846.4850.4854.4857

2.2¦.4861.4864.4868.4871.4875.4878.4881.4884.4887.4890

2.3¦.4893.4896.4898.4901.4904.4906.4909.4911.4913.4916

2.4¦.4918.4920.4922.4925.4927.4929.4931.4932.4934.4936

2.5¦.4938.4940.4941.4943.4945.4946.4948.4949.4951.4952

2.6¦.4953.4955.4956.4957.4959.4960.4961.4962.4963.4964

2.7¦.4965.4966.4967.4968.4969.4970.4971.4972.4973.4974

2.8¦.4974.4975.4976.4977.4977.4978.4979.4979.4980.4981

2.9¦.4981.4982.4982.4983.4984.4984.4985.4985.4986.4986

3.0¦.4986.4987.4987.4988.4988.4989.4989.4989.4990.4990

Дата добавления: 2015-07-15