97 объекте. Справедливо и обратное утверждение: лю бом у варианту выполнения работ будет соответствовать некоторы й путь в сети возм ож ны х стратегий, соединяю щ ий начальную верш ину с конечной. В качестве длины д у ги сетевого граф ика соединяю щ его верш ины (i, j ) и (i+ 1 , j) примем величину затрат Су направленных на организацию 1-ой работы по j -му варианту. Т аким образом, м ы построили сетевую модель, которая содержит все рациональные варианты выполнения работ. К а ж д о м у та ком у варианту соответствует путь в сети, соединяю щ ий вход с выходом. Затраты на обеспечение совмещ енного выполнения работ равны длине соответствую щ его пути. Задача свелась к определению подкритического п ути , отличаю щ егося от крит ического на заданную величину. В качестве примера рассмотрим возможны е варианты выполнения работ по проекту, данные о котором представлены в табл. 3.6.1. Е сли предположить, что работы по проекту, характеристика которы х приведена в табл. 3.6.1, выполняются последовательно, то время разработки проекта составит 135 дней, что не устраивает заказчика. Необходимо обеспечить сокращ ение общ ей продолжительности вы полнения работ за счет частичного совмещения работ не менее чем на 50 дней. Таблица 3.6.1. И сходны е данные по проекту Наименование работ Продолжительность работы, дн. 1. Работы нулевого цикла (Н Ц ) 32 2. Ф ундам енты (Ф ) 29 3. Каркас ( К ) 29 4. Кровля (К р ) 45 В озможны е варианты производства работ и соответствую щ ие этим вариантам значения сокращ ения продолжительности и затрат приведены в табл. |
вершину с конечной, определяет некоторый вариант совмещенного выполнения работ. Например, пути [х0, (2), (1), х3] соответствует варианту, когда коэффициент совмещения между первой и второй работами принимает значение из третьего множества, а коэффициент совмещения между второй и третьей работами из второго множества. Справедливо и обратное утверждение: любому варианту совмещенного выполнения работ будет соответствовать некоторый путь в сети возможных стратегий, соединяющий начальную вершину с конечной. В качестве длины дуги сетевого графика соединяющего вершины (i, j) и (i+1, j) примем величину затрат с# направленных на организацию данной степени совмещения рассматриваемых работ. Таким образом, мы построили сетевую модель, которая содержит все рациональные варианты выполнения работ. Каждому такому варианту соответствует путь в сети, соединяющий вход с выходом. Затраты на обеспечение совмещенного выполнения работ равны длине соответствующего пути. Задача свелась к определению пути минимальной длины. Алгоритмы определения экстремальных путей в графах (то есть путей максимальной или минимальной длины) достаточно хорошо известны и описаны в литературе [14, 39]. Для нашего случая наиболее эффективен алгоритм определения кратчайших путей при правильной нумерации вершин сети. Напомним, что нумерация вершин называется правильной, если для любой дуги (/,j) имеет место / <у. В этом случае кратчайший путь определяется на основе последовательного присвоения вершинам сети индексов qj согласно следующей процедуре (индекс вершины 1 принимается равным 0): 7. = т т [< /; где Sji длина дуги (j, /). В этом случае индекс последней вершины „,+/ будет равен длине кратчайшего пути или величине минимальных затрат. Путь минимальной длины определяется на основе процедуры «обратного хода». Опишем эту процедуру. Находим вершину //, такую что Ят+1 *7/, • Если /'/ *1, то находим вершину такую что % =<7.»+5м, • Продолжаем таким образом, пока на очередном шаге к не получим ik = 1, то есть <7,,., =<7.+51л., • Путь ц =(1, ik-t, h-2, —, //, w+i) и является путем минимальной длины. В качестве примера рассмотрим возможные варианты выполнения работ по проекту, данные о котором представлены в табл. 4.6.1. Если предположить, что работы по проекты, характеристика которых приведена в табл. 4.6.1, выполняются последовательно, то время разработки проекта составит 135 дней, что не устраивает заказчика. Необходимо обеспечить сокращение общей продолжительности выполнения работ за счет частичного совмещения работ не менее чем на 50 дней. Таблица 4.6.1. Исходные данные по проекту. Наименование работ Продолжительность работы, дн. 1. Работы нулевого цикла 32 2. Фундаменты 24 3. Каркас 24 4. Кровля 36 5. Внутренние работы 19 Обозначим коэффициент совмещения между работами (1 2) и (3 4) через К), между работами (3 4) и (5 6) через К2между работами (5 6) и (7 8) Кз и между работами (7 8) и (9 10) К4. Значения сокращения продолжительности выполнения работ (знаменатель) и затраты (числитель), представлены в табл. 4.6.2. Тогда множество возможных вариантов назначения коэффициентов совмещения выполняемых работ образует граф, представленный на рис. 4.6.2. Представленный граф содержит все возможные решения для сокращения общей продолжительности выполнения работ. Причем по условиям по |