Автоматика и телемеханика, № 4, 2014
Тематический выпуск
НЕКОТОРЫЕ СОВРЕМЕННЫЕ ПРОБЛЕМЫ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ
Данный тематический выпуск посвящен современным проблемам математического программирования. В выпуск включены статьи, которые прошли апробацию на Международной конференции "Дискретная оптимизация и исследование операций (DOOR-2013)", проходившей 24-28 июня 2013 г. в новосибирском Академгородке. Конференция была организована Институтом математики им. С.Л. Соболева СО РАН. В конференции приняли участие многие известные ученые из России, ближнего и дальнего зарубежья. Конференции по дискретной оптимизации и исследованию операций, ставшие регулярными, имеют своим началом Всесоюзные конференции по проблемам теоретической кибернетики, проходившие в Институте математики в 70-80 гг. ХХ в. по инициативе и под общим руководством Ю.И. Журавлева, С.В. Лупанова и С.В. Яблонского. Тематика конференций охватывала программирование и математическую лингвистику, математическое моделирование и математическую биологию, оптимальные процессы и исследование операций, дискретный анализ и теорию управляющих систем.
Среди тем, обсуждавшихся на прошедшей в 2013 г. конференции, большое внимание уделялось задачам дискретной оптимизации и их приложениям для обработки изображений и решения экономических задач. В частности, много докладов было посвящено методам решения двухуровневых задач, активно исследующихся в настоящее время в России и за рубежом. Кроме того, активно обсуждались и традиционные темы для математического программирования, такие как методы решения задач выпуклого программирования и теории игр.
В данный тематический выпуск вошли избранные статьи, посвященные всем перечисленным проблемам. В частности, в статье Е.А. Нурминского и Д. Тьена предложена модификация метода сопряженных градиентов для решения задачи выпуклой недифференцируемой оптимизации и доказана его сходимость. В работе А.С. Стрекаловского и Р. Энхбата исследована игра трех лиц, в которой установлены условия равновесия в смысле Нэша при использовании смешанных стратегий. В номере представлена также статья Л.Д. Попова, посвященная ускорению алгоритмов решения задач линейного программирования на основе их распараллеливания. В статье М.Ю. Хачая и М.И. Поберий исследуется задача о минимальном разделяющем комитете, для решения которой строится приближенный полиномиальный алгоритм с улучшенными показателями точности. В работе А.Е. Галашова и А.В. Кельманова рассматривается задача поиска семейства непересекающихся подмножеств, имеющих заданные мощности, в конечном множестве векторов евклидова пространства по критерию минимума суммы квадратов рас-
стояний от элементов подмножеств до их центров. Статью А.И. Кибзуна и
A.О. Иноземцева можно рассматривать как приложение известных методов решения задач выпуклой оптимизации при обработке неоднородной информации, полученной в результате прохождения тестов группой испытуемых. В статье доказана сходимость используемого алгоритма.
Большое внимание в номере уделено новому классу задач оптимизации — задачам двухуровневого математического программирования и, в частности, дискретным задачам двухуровневого программирования. Такие задачи возникают на практике при построении моделей принятия решений в условиях конкуренции или противоборства, когда имеются две или несколько сторон, находящихся в игровом взаимодействии и стремящихся достичь своих целей. В предлагаемых статьях содержатся формулировки новых задач двухуровневого программирования и алгоритмы поиска оптимальных решений таких задач. В частности, в статье В.Л. Береснева исследуется новая постановка задачи конкурентного последовательного размещения и показано, что эта задача может быть представлена в виде задачи максимизации псевдобулевой функции от малого числа переменных, a это позволяет использовать для вычисления оптимальных решений такой задачи имеющийся арсенал методов. Статья А.Г. Ченцова посвящена обоснованию точного метода решения, родственного методу динамического программирования, для обобщенной двухуровневой задачи курьера. В работе А.И. Давыдова, Ю.А. Кочетова, Н. Младеновича и Д. Уросевича предлагается алгоритм поиска решений задачи о (г|р)-центроиде, построенный на методе локального поиска и использующий идею о выделении "перспективной" подокрестности. В работе А.А. Мельникова предлагается алгоритм решения задачи конкурентного размещения большой размерности, построенный на идеях локального поиска с использованием окрестностей специального вида. Статья А.А. Панина, М.Г. Пащенко и А.В. Плясунова посвящена исследованию сложности предлагаемой модели двухуровневого программирования и построению алгоритмов решения полученной задачи.
Надеемся, что читатель, изучая статьи из данного номера, сможет самостоятельно оценить современные тенденции в математическом программировании. Следует подчеркнуть, что все статьи, представленные в данном номере, прошли не только апробацию на Международной конференции, но и тщательное рецензирование. Редакторами тематического выпуска являются
B.Л. Береснев и А.И. Кибзун.
В.Л. Береснев, А.И. Кибзун
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.