Задание 2. Определение критического пути в MS Excel

С сетевым графиком связана таблица, которая называется матрицей инцидентностей.

Рис. 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 – любой путь, начало которого совпадает с исходным событием сети, а конец – с завершающим.

Полными путями являются пути:

Ѕ₀ Ѕ₃ Ѕ₅ Ѕ₇ продолжительность его 22 ед.

Ѕ₀ Ѕ₂ Ѕ₃ Ѕ₄ Ѕ₆ Ѕ₇ продолжительность 45 ед.

Критический путь имеет максимальную продолжительность.

Для вычисления критического пути введем переменные х_i = 0, если ребро не принадлежит пути и х_i =1, если принадлежит. Такие переменные называются булевыми или двоичными.

Рассмотрим функцию U(х_i)= , где T_i – исходные значения продолжительности работ.

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

,

где b_j = -1 – для начальной вершины,

b_j = 1 – для конечной вершины,

b_j = 0 для всех промежуточных вершин,

a_ij – элементы строки матрицы инцидентностей

Для начального события Ѕ₀ (вершина, исходящая для всех путей): -х₁-х₂-х₃= -1

Для первого события Ѕ_1: х₁-х₄- х₅- х₆=0

Для второго события Ѕ₂: х₂+х₄- х₇-х₈ –х₉=0

Для третьего события Ѕ₃: х₃+х₅+х₇- х₁₀-х₁₁=0

Для четвертого события Ѕ₄: х₆+х₈ +х₁₀-х₁₂-х₁₃=0

Для пятого события Ѕ₅: х₉+х₁₁ +х₁₂-х₁₄-х₁₅=0

Для шестого события Ѕ_6: х₁₃+х₁₄ -х₁₆=0

Для седьмого события Ѕ₇ (завершающего) х₁₅ +х₁₆=1

Начальные значения всех переменных примем равными 1.

Составим модель для поиска критического пути: Для этого:

5. В строке 12 введите переменные x_i, равные 1.

6. В столбце R рассчитайте , воспользовавшись функцией СУММПРОИЗ.

7. В столбец S введите ограничения b_j, учитывая, что b_j = -1 – для начальной вершины, b_j = 1 – для конечной вершины, b_j = 0 для всех промежуточных вершин.

8. В ячейке R11 рассчитайте .

9. Сравните полученный результат с рисунком 3.

Рис. 3. Матрица инцидентностей.

10. Для того, чтобы рассчитать критический путь (максимальную продолжительность проекта), воспользуйтесь возможностями MS Excel по поиску решений. Для этого:

· Выполните команду Сервис/Поиск решений (Если данный модуль отсутствует, то предварительно установите его, выполнив команду Сервис/Надстройки/Поиск решения).

· В диалоговом окне Поиск решения установите параметры поиска решения согласно рис.4.

· Установите параметры модели – Линейная и Неотрицательные значения, щелкнув по кнопке [Параметры] диалогового окна Поиск решения.

Рис. 4. Диалоговое окно Поиск решения.

Где: целевая ячейка – $R$11 (сумма произведений T_i x_i).

изменяемые ячейки – $B$12:$Q$12 (переменные х_i ).

ограничения – ячейки столбца Σa_ijx_i= bj, а также $B$12:$Q$12 = двоичное.

· Установите параметры модели – Линейная и Неотрицательные значения, щелкнув по кнопке [Параметры] диалогового окна Поиск решения.

· Щелкните по кнопке [Выполнить] и в окне Результат поиска решения установите опцию « Сохранить найденное значение» и выберите Тип отчета – Результаты.

11. По результатам поиска определите критический путь и сравните с рис. 5.

Рис. 5. Результат поиска решения.

Значение целевой функции равно 57 ед.

Таким образом, критический путь включает работы Р₀₁Р₁₂ Р₂₃ Р ₃₄ Р ₄₅ Р ₅₆Р_67.

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