Детальная информация

В данной магистерской диссертации описана и формализована задача построения оптимального расписания для серии шлюзов. Построенная модель является задачей смешенного целочисленного линейного программирования. Для таких задач не существует эффективного алгоритма решений в общем виде. В основу данной работы лег специализированный алгоритм, учитывающий специфику и физические особенности данной задачи. Алгоритм реализует общую идею ветвей и границ. Благодаря эффективному правилу разбиения множества решений на подмножества и оценки точной нижней границы каждого подмножества удалось значительно повысить вычислительную эффективность. Также разработан алгоритм локального поиска, который выполняется в процессе работы алгоритма, после нахождения текущего наилучшего решения. Алгоритм локального поиска основан на физическом смысле решения, а не на классическом подходе поиска локального экстремума. Объясняется это тем, что в данной задаче крайне трудоемок поиск допустимого решения. Вычислительные тесты показали эффективность данного алгоритма, его преимущества перед алгоритмом ветвей и границ общей задачи бинарного программирования. Так же в данной работе был проведен сравнительный анализ с работой зарубежных авторов, в которой решалась аналогичная задача.