НОВЫЙ АЛГОРИТМ ДЛЯ РЕШЕНИЯ СПЕЦИАЛЬНОЙ ЗАДАЧИ О НАЗНАЧЕНИЯХ С ФУНКЦИЕЙ СТОИМОСТИ ОБЩЕГО ВИДА ПРИ НАЛИЧИИ ОГРАНИЧЕНИЙ

摘要

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