Двойственность в задаче о назначении исполнителей проекта

Аннотация

Рассматривается задача о назначении исполнителей проекта – совокупности взаимозависимых работ, связи между которыми описываются с помощью ориентированных взвешенных графов без петель и контуров, элементам которых поставлены в соответствие некоторые характеристики проекта. При этом события (факт окончания или начала выполнения работ) соответствуют вершинам графа, а работы – дугам, ориентация которых соответствует технологии этого процесса. Цель управления проектом заключается в оптимальном распределении исполнителей проекта по проектным заданиям. Критерий эффективности – минимум времени реализации проекта. Анализ литературы показал, что подобная задача является важной составной частью большинства сложных моделей управления проектами. Предложен метод решения данной задачи с использованием аппарата двойственности. Показано, что для вычисления соответствующей двойственной функции необходимо на каждом шаге решать классическую задачу о назначениях, ценовая матрица которой определяется умножением элементов ценовой матрицы исходной задачи на соответствующие множители Лагранжа. В ходе решения тестовых задач выяснилось, что классический алгоритм Х. Удзавы негладкой оптимизации порождает зигзагообразную траекторию поиска, сходную с траекторией оптимизации «овражных» функций. Было предложено воспользоваться подходом, разработанным В.Ф. Демьяновым и В.Л. Малоземовым для решения нелинейных минимаксных задач. В работе детально описан пример использования предлагаемого алгоритма. Тестовые расчеты подтвердили эффективность метода для задач умеренной размерности. Было показано, что в общем случае для данной задачи наблюдается разрыв двойственности, что не мешает найти приемлемое приближенное решение