Нахождения критического пути в сетевом графе с помощью программы Microsoft Excel

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

Требуется найти критический путь, соединяющий начальное событие v₁ с конечным событием v_s, так чтобы общая длина пути была максимальной.

Переменными математической модели задачи о критическом пути в сетевом графе являются переменные x_ij. Каждая из этих переменных принимает значение 1, если дуга (i, j) входит в критический путь, и 0 — в противном случае.

Для решения задачи нахождения критического пути с помощью программы Microsoft Excel вводим данные задачи на новый лист.

Рисунок 2.1 — Ввод данных Для дальнейшего решения задачи следует вызвать мастер поиска решения, для чего необходимо выполнить операцию главного меню: Сервис|Поиск решения.

После появления диалогового окна Поиск решения следует задать:

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

Общий вид диалогового окна спецификации параметров мастера поиска решения имеет следующий вид.

Рисунок 2.2 — Параметры поиска решения После выполнения расчетов программой Microsoft Excel будет получено количественное решение задачи.

Результатом решения поставленной задачи являются найденные оптимальные значения переменных x_ij=1 (остальные переменные равны 0). Найденному оптимальному решению соответствует значение целевой функции. Критический путь в сетевом графе содержит дуги (i, j), соответствующие критическим операциям моделируемого процесса.