Зад лин прогр и мет их решения 16 12 08

Условия оптимальности выполнены для всех клеток, а значит, последний план перевозок является оптимальным планом (т.е. имеет наименьшие транспортные расходы).

Изобразим оптимальный план перевозок в виде графа.

Оптимальный план перевозок

Объем перевозки

−− Pɺ2Pɺ6 − −

−−

События – {–} {P2}{P6}{P1}{P7P8}{P3 P5 P6}{P4 P9 P10 P11} Первыми работами являются P2, P5, P6.

Последними – P4, P9, P10, P11. Начало проекта – {–}

Конец проекта – {P4 P9 P10 P11}

265

Построим сетевой график проекта.

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

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

P3P5P6

P4P9P10P11

P7P8

-P2

P1

P6

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

Сокращаем фиктивные дуги по правилам:

1.Если (i, j) – фиктивная дуга такая, что из i (начала фиктивной дуги) в j (конец фиктивной дуги) есть другой путь, то (i, j) удаляем.

2.Пусть (i, j) – фиктивная дуга, которая единственная среди дуг сети начинается в i (единственная выходящая из i) или же единственная среди дуг сети, заканчивается в j. Тогда эту фиктивную дугу можно сократить, объединив вершины i, j в одну (говорят, сжав фиктивную дугу), если при этом не образуются параллельные дуги. Для новой объединённой вершины обычно оставляют обозначение i или j.

3.Фиктивную дугу ( i, j ) можно сжать, объединив её начало i и конец j в одну вершину, если при этом не образуются лишние связи предшествования, т.е. связи, которых нет в проекте, и не образуются параллельные дуги.

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

Сделаем правильную нумерацию в полученной сети. Искомый сетевой график построен.

Для хранения полученного графика, т.е. логической структуры проекта запомним

набор записей: {(1,3), Р5}, {(1,2), Р2}, {(1,4), Р6}, {(2,5), Р7}, {(4,5), Р8}, {(5,7), Р9}, {(5,6),

Р1}, {(4,7), Р4}, {(6,7), Р11}, {(3,7), Р10}, {(2,3), Р3}.

Найдем критический путь, критические работы, критическое время.

Критическое время – наименьшее время, за которое можно выполнить все работы

проекта, Ткрит.

1)(1,3) (3,7) сумма времен работ = 5 + 24 = 29

2)(1,2) (2,3) (3,7) сумма времен работ = 6 + 5 + 24 = 35

3)(1,2) (2,5) (5,7) сумма времен работ = 6 + 8 + 3 = 17

268

4)(1,2) (2,5) (5,6) (6,7) сумма времен работ = 6 + 8 + 7 + 6 = 27

5)(1,4) (4,5) (5,7) сумма времен работ = 16 + 10 + 3 = 29

6)(1,4) (4,5) (5,6) (6,7) сумма времен работ = 16 + 10 + 3 = 29

7)(1,4) (4,7) сумма времен работ = 16 + 10 = 26

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

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

конец проекта, т.е. Tкрит = max{ 29, 35,17, 27, 29, 39, 26} = 39 у.е.

Самый длинный путь из начала проекта в конец проекта в сетевом графике называется критическим путём. Критический путь будет (1,4) (4,5) (5,6) (6,7).

Критические работы будут Р6 Р8 Р1 Р11.

Найдем критический путь методом потенциалов. Потенциалы, рассчитанные с начала проекта по формуле:

y1=0; yj=max{yi+tij}, j=2,3,…,7 y2=y1+t12=0+6=6;

y3=max{y1+ t13, y2+ t23}=max{0+5;6+5}=11;

y4=y1+ t14=16+0=16;

y5=max{y2+ t25, y4+ t45}=max{6+8;16+10}=26;

y6=y5+ t56=26+7=33;

y7=max{y3+ t37, y5+ t57, y6+ t67, y4+ t47}=max{11+24;26+3;33+6;16+10}=max{35;29;39;26}=39

Таким образом, критическое время Ткрит=39; критический путь 1,4,75,6,7; критиче-

ские работы Р6 Р8 Р1 Р11. Найденные потенциалы выделим квадратиками.

Потенциалы, рассчитанные с конца проекта по формуле:

максимум берётся по всем дугам ( i, j ), выходящим из вершины i. v7=0;

v6=v7+t67=0+6=6;

v5=max{v7+t57, v6+t56}=max{0+3;6+7}=max{3;13}=13;

v4= max{v5+t45, v7+t47}=max{13+10;0+10}=max{23;10}=23;

v3=v7+ t37=0+24=24;

v2= max{v5+t25, v3+t23}=max{13+8;24+5}=max{21;29}=29; v1=max{v3+t13, v2+t12, v4+ t14}=max{24+5;29+6;23+16}=max{29;35;39}=39

Таким образом, критическое время Ткрит=39; критический путь 1,4,5,6,7; критические работы Р6 Р1 Р8 Р11. Найденные потенциалы выделим треугольниками.

Найдем временные параметры событий.

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

tP (i) = Tкрит′ (i) = yi ,

где yi – потенциалы, рассчитанные с начала.

tp(1) = 0; tp(2) = 6; tp(3) = 11; tp(4) = 16; tp(5) = 26; tp(6) = 33; tp(7) = 39.

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

дующих за событием работ равно T ′′ (i) , поэтому

крит