С сетевым графиком связана таблица, которая называется матрицей инцидентностей.
Рис. 2. Матрица инцидентностей.
Она строится следующим образом: столбцы соответствуют работам, а строки событиям. Если для дуги (i - j) начало соответствует i, а конец дуги соответствует j, то элемент матрицы в строке i будет равен -1, в строке j равен 1, а все другие элементы столбца равны 0.
1. Откройте новую книгу MS Excel и сохраните в своей папке под именем Сетевое проектирование.xls.
2. Переименуйте Лист1 в лист Матрица инцидентностей.
3. Для обеспечения проверки вводимых значений в диапазон ячеек B3:Q10 создайте список подстановки. Для этого:
· Выделите диапазон ячеек.
· Выполните команду Данные/Проверка…
· В окне Проверка вводимых значений на вкладке Параметры задайте Тип данных Список.
· В поле Источник введите значения : -1;1
4. В диапазон ячеек A11:Q11 введите продолжительность работ.
Путь – любая последовательность работ, в которой конечное событие каждой работы совпадает с начальным событием следующей за ней работы. Среди различных путей сетевого графика наибольший интерес представляет полный путь L – любой путь, начало которого совпадает с исходным событием сети, а конец – с завершающим.
|
|
Полными путями являются пути:
Ѕ0 Ѕ3 Ѕ5 Ѕ7 продолжительность его 22 ед.
Ѕ0 Ѕ2 Ѕ3 Ѕ4 Ѕ6 Ѕ7 продолжительность 45 ед.
Критический путь имеет максимальную продолжительность.
Для вычисления критического пути введем переменные хi = 0, если ребро не принадлежит пути и хi =1, если принадлежит. Такие переменные называются булевыми или двоичными.
Рассмотрим функцию U(хi)= , где Ti – исходные значения продолжительности работ.
По условию эта функция для критического пути должна быть максимальной. Построим систему ограничений. Все ограничения имеют вид:
,
где bj = -1 – для начальной вершины,
bj = 1 – для конечной вершины,
bj = 0 для всех промежуточных вершин,
aij – элементы строки матрицы инцидентностей
Для начального события Ѕ0 (вершина, исходящая для всех путей): -х1-х2-х3= -1
Для первого события Ѕ1: х1-х4- х5- х6=0
Для второго события Ѕ2: х2+х4- х7-х8 –х9=0
Для третьего события Ѕ3: х3+х5+х7- х10-х11=0
Для четвертого события Ѕ4: х6+х8 +х10-х12-х13=0
Для пятого события Ѕ5: х9+х11 +х12-х14-х15=0
Для шестого события Ѕ6: х13+х14 -х16=0
Для седьмого события Ѕ7 (завершающего) х15 +х16=1
Начальные значения всех переменных примем равными 1.
Составим модель для поиска критического пути: Для этого:
5. В строке 12 введите переменные xi, равные 1.
6. В столбце R рассчитайте , воспользовавшись функцией СУММПРОИЗ.
7. В столбец S введите ограничения bj, учитывая, что bj = -1 – для начальной вершины, bj = 1 – для конечной вершины, bj = 0 для всех промежуточных вершин.
|
|
8. В ячейке R11 рассчитайте .
9. Сравните полученный результат с рисунком 3.
Рис. 3. Матрица инцидентностей.
10. Для того, чтобы рассчитать критический путь (максимальную продолжительность проекта), воспользуйтесь возможностями MS Excel по поиску решений. Для этого:
· Выполните команду Сервис/Поиск решений (Если данный модуль отсутствует, то предварительно установите его, выполнив команду Сервис/Надстройки/Поиск решения).
· В диалоговом окне Поиск решения установите параметры поиска решения согласно рис.4.
· Установите параметры модели – Линейная и Неотрицательные значения, щелкнув по кнопке [Параметры] диалогового окна Поиск решения.
Рис. 4. Диалоговое окно Поиск решения.
Где: целевая ячейка – $R$11 (сумма произведений Ti xi).
изменяемые ячейки – $B$12:$Q$12 (переменные хi ).
ограничения – ячейки столбца Σaijxi= bj, а также $B$12:$Q$12 = двоичное.
· Установите параметры модели – Линейная и Неотрицательные значения, щелкнув по кнопке [Параметры] диалогового окна Поиск решения.
· Щелкните по кнопке [Выполнить] и в окне Результат поиска решения установите опцию « Сохранить найденное значение» и выберите Тип отчета – Результаты.
11. По результатам поиска определите критический путь и сравните с рис. 5.
Рис. 5. Результат поиска решения.
Значение целевой функции равно 57 ед.
Таким образом, критический путь включает работы Р01Р12 Р23 Р 34 Р 45 Р 56Р67.
Этот путь или подпроцесс имеет максимальную продолжительность, и работы находящиеся на нем не имеют ни каких резервов времени. Критический путь определяет полное время завершения всех работ.