Решение. Этап I. Построение сетевой модели.

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

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

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

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

1) ;

T₁=t₂+ t₁₀+ t₁₁+ t₁₂=15+3+2+1=21 дн.

2)

T₂=t₂+ t₃+ t₄+ t₈+ t₁₀+ t₁₁+ t₁₂=8+6+3+5+3+2+1=28 дн.

3)

T₃=t₁+ t₃+ t₄+ t₇+ t₉+ t₁₁+ t₁₂=8+6+3+5+3+2+1=28 дн.

4)

T₄=t₁+ t₅+ t₆+ t₉+ t₁₁+ t₁₂=8+4+5+3+2+1=23 дн.

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

(очевидно, что критические пути не имеют резервов времени).

4. Строим временную диаграмму всех полных путей. Критические работы выделены «рамкой».

Рис 2. Исходная временная диаграмма

Этап II. Оптимизация сетевой модели.

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

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

При этом справедливы следующие формулы пересчета, которыми мы будем пользоваться без доказательства:

• новая длительность работы-донора: ,

• новая длительность работы-акцептора: ,

Здесь , -коэффициенты пересчета ресурсов донора и акцептора соответственно.

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

• во-первых, мы не можем взять у донора больше ресурсов, чем он имеет, поэтому ;

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

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

Наша цель— «выровнять» длины второго, третьего и четвертого пути, поэтому в качестве акцептора логично выбрать работу, принадлежащую как второму, так и третьему пути. Пусть это будет работа a₄ (завоз товара).

Изобразим это схематично на временной диаграмме:

Рис 3. Перенос ресурсов на 1 шаге оптимизации

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

(1)

Ограничения имеют вид: (2)

Решаем полученную систему уравнений, учитывая соотношения, полученные на этапе I:

Таким образом, снимаем 6,25 ед. ресурсов с работы a₆ и передаем их работе a₄. При этом ограничения (2) выполнены. В противном случае необходимо было бы искать другой вариант переноса ресурсов.

Вычисляем новую длительность работы a₆:

Вычисляем новую длительность работы a₄:

Вычисляем новые длительности путей:

Находим новые ресурсы работы-донора и работы-акцептора:

Строим новую таблицу:

Содержание работы	Обозначение работы	Опорные работы	Выделенные ресурсы bi	Длительность работ ti
Заказ на оборудование	а1	-	5	8
Разработка системы учета спроса	а2	-	5	15
Отбор товаров и выписка счетов	а3	а1	5	6
Завоз товара	а4	а3	16,25	1,125
Завоз оборудования	а5	а1	10	4
Установка оборудования	а6	а5	3,75,	8,125
Выкладка товара	а7	а4	10	5
Учет наличия товара	а8	а4	5	5
Оформление зала	а9	а6, а7	5	3
Изучение документов	а10	а2, а8	5	3
Репетиция	а11	а9, а10	10	2
Проведение ярмарки	а12	а11	20	1

Строим новую временную диаграмму:

Рис. 4. Результаты 1 шага оптимизации

2 шаг. Как следует из рис.4., по итогам первого шага оптимизации остался только один некритический путь (Путь 1) и только одна некритическая работа a₂ (разработка системы учета спроса). Для того, чтобы «уравнять» длины всех путей, необходимо снять допустимую часть ресурсов с работы a₂ и передать их работе или работам, лежащим на остальных путях. Следовательно, на этом шаге донора выступает работа a₂.

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

Изобразим это схематично на временной диаграмме:

Рис 5. Перенос ресурсов на 2 шаге оптимизации

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

(3)

Ограничения имеют вид: (4)

Решаем полученную систему уравнений:

Таким образом, снимаем 1,114 ед. ресурсов с работы a₂ и передаем их работе a₁. При этом ограничения (4) выполнены. В противном случае необходимо было бы искать другой вариант переноса ресурсов.

Вычисляем новую длительность работы a₂:

Вычисляем новую длительность работы a₁:

Вычисляем новые длительности путей:

Находим новые ресурсы работы-донора и работы-акцептора:

Строим новую таблицу:

Содержание работы	Обозначение работы	Опорные работы	Выделенные ресурсы bi	Длительность работ ti
Заказ на оборудование	а1	-	6,114	6,218
Разработка системы учета спроса	а2	-	3,886	18,342
Отбор товаров и выписка счетов	а3	а1	5	6
Завоз товара	а4	а3	16,25	1,125
Завоз оборудования	а5	а1	10	4
Установка оборудования	а6	а5	3,75,	8,125
Выкладка товара	а7	а4	10	5
Учет наличия товара	а8	а4	5	5
Оформление зала	а9	а6, а7	5	3
Изучение документов	а10	а2, а8	5	3
Репетиция	а11	а9, а10	10	2
Проведение ярмарки	а12	а11	20	1

Строим новую временную диаграмму:

Рис. 6. Оптимальная временная диаграмма

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

Экономия времени по сравнению с исходным вариантом распределения ресурсов составила 28-24,342=3,658 дн.

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