Статья: СТАТИСТИЧЕСКИЙ ЭКСПЕРИМЕНТ ПО ПРОВЕРКЕ ПРАКТИЧЕСКОЙ СХОДИМОСТИ В ОДНОЙ ЗАДАЧЕ СУБМОДУЛЯРНОГО ПРОГРАММИРОВАНИЯ

В статье рассматривается cтатистический эксперимент по проверке практической сходимости в одной задаче субмодулярного программирования. Предлагается постановка задачи по максимизации суммы эффективности группового назначения. Вводится понятие смешанного решения транспортной задачи о групповом назначении, когда ресурсные ограничения в среднем выполняются. Показано, что определение смешанных решений транспортной задачи о групповом назначении может быть сведено к задаче субмодулярного программирования, решаемой методом ветвей и границ с верхними оценками, основанными на субмодулярности транспортной задачи с ограничениями в виде равенств по столбцам. Полиномиальность ε-оптимальной версии метода ветвей и границ доказана лишь в отношении классической схемы решения многомерной задачи о рюкзаке. Авторы применили схему, использующую специфику задачи, поэтому для проверки гипотезы полиномиальности необходимы дальнейшие усилия, в том числе и при помощи статистических экспериментов. Основным результатом являются разработка численной реализации ε-оптимальной версии метода ветвей и границ на высокоуровневом языке программирования С++ и проведение статистического эксперимента по проверке практической сходимости самого алгоритма на основании статической транспортной задачи о групповом назначении по эффективности назначения. По результатам анализа численного эксперимента установлено, что для рассматриваемой задачи процент раскрытых в ходе работы ε-оптимального алгоритма вершин от общего числа вершин в орграфе при увеличении размерности убывает довольно быстро, что говорит о достаточной эффективности алгоритма. Гипотеза о полиномиальности не подтвердилась, так как используется не классический алгоритм решения целочисленной задачи, а специфика поставленной задачи.