ISSN 0236-235X · EISSN 2311-2735
Языки: ru · en

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

Читать онлайн

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

Ключевые фразы: ВЕРХНИЕ ОЦЕНКИ КРИТЕРИЯ, МЕТОД ВЕТВЕЙ И ГРАНИЦ, ПОЛИНОМИАЛЬНОСТЬ, СТАТИСТИЧЕСКИЙ ЭКСПЕРИМЕНТ, ПОГРУЖЕНИЕ ИСХОДНОЙ ЗАДАЧИ В СЕМЕЙСТВО ЗАДАЧ, СМЕШАННЫЕ РЕШЕНИЯ, ТРАНСПОРТНАЯ ЗАДАЧА О ГРУППОВОМ НАЗНАЧЕНИИ
Автор (ы): Скакодуб К. Р., Лесик Александра Ильинична, Перевозчиков Александр Геннадьевич
Журнал: ПРОГРАММНЫЕ ПРОДУКТЫ И СИСТЕМЫ

Идентификаторы и классификаторы

УДК
519.7. Математическая кибернетика
eLIBRARY ID
54262537
Для цитирования:
СКАКОДУБ К. Р., ЛЕСИК А. И., ПЕРЕВОЗЧИКОВ А. Г. СТАТИСТИЧЕСКИЙ ЭКСПЕРИМЕНТ ПО ПРОВЕРКЕ ПРАКТИЧЕСКОЙ СХОДИМОСТИ В ОДНОЙ ЗАДАЧЕ СУБМОДУЛЯРНОГО ПРОГРАММИРОВАНИЯ // ПРОГРАММНЫЕ ПРОДУКТЫ И СИСТЕМЫ. 2023. T. 36 № 2
Текстовый фрагмент статьи