Введение к работе
Актуальность теїш. Роль оубмодулярных функций в комбинаторной оптимизации сравнима с ролью выпуклых функций в непрерывной оптимизации. Многие классические комбинаторные проблемы могут быть сформулированы как задача поиска экстремума субмодулярной функции. Другой, еше более широкий класс зада^ комбинаторной оптимизации, составляют задачи с так называемыми субмодулярными или полиматроидными ограничениями. Основная трудность решения таких задач связана о большим (экспоненциальным) количестом ограничений, которые определяют множество допустимых решений.
Основной целью работы является разработка новых численных методов решения некоторых задач субмодулярной оптимизации и их применение к решению ряда практичесских задач.
Метода исследования. В работе применяются методы выпуклого и линейного программирования, теории игр, комбинаторной оптимизации, теории матроидов.
Научная новизна и практическая ценность работы. Все полученные результаты является новыми. В работе введен и исследован новый класс полиэдральных лгр '- матричные игры с зависимыми стратегиями. Предложены новые алгоритмы решения классических задач минимизации и макс.шизащш субмодулярной функции. Для двух классов целевых функций решены оптимизационные задачи на базовом многограннике субмодулярной функции. Субмодулярная задача упорядочения сведена к решению параметрической задачи линейного программирования. В диссертации приводится ряд практических задач, для решения которых можно использовать алгоритмы, разработанные в диссертации.
Аппробацня работ".. Основные результаты диссертации докладывались на межреспубликанских научно-практических конференциях творческой молодежи (Минск, 1990 г., Минск, 1992 г.і Минск, 1994 г.). На научных семинарах: в Белорусском государственном университете и в Институте математики АН Беларуси.
Публикации. Основные результаты диссертации опубликованы в работах И-4Ь
Структура и обьеи работы. Диссертация состоит из введения, двух глав, и .списка литературы, включающего 91 наименование. Объем диссертации Щ ртраниц машинописного текста, включая 15 рисунков.