Информационная система "Конференции"

Тезисы докладов

Вычислительная математика

Целочисленная задача может быть решена как линейная: решаем ее линейную релаксацию и получаем оптимальное решение, удовлетворяющее условию целочисленности. Это можно сделать тогда, когда все базисные решения линейной задачи целочисленные.

Трудность численного решения задач целочисленной оптимизации состоит в том, что множество допустимых решений этих задач является невыпуклым. Именно невыпуклость не позволяет установить глобальный оптимум из локальных условий. Указанная трудность преодолевается методом ветвей и границ.

Автором разработана и реализована вычислительная схема многоветвого алгоритма ветвей и границ для решения задач целочисленной оптимизации.

Этот метод представляет собой "специальный" перебор. Составные части этого метода: последовательно дробим допустимое множество задачи на все меньшие подмножества; на каждом подмножестве вычисляем нижнюю и верхнюю границы для неизвестного оптимального значения; используя вычисленные границы, из дальнейшего рассмотрения исключаем определенные подмножества. Процесс заканчивается, когда-либо для каждого подмножества уже произведено его наилучшее решение, либо каждое подмножество не содержит ни одного лучшего решения, чем уже имеющиеся решения. Наилучшее решение является глобальным оптимумом.

Планируется: расширить класс решаемых задач данным методом, добавление класса смешанных целочисленных задач; улучшить выбор активной вершины; улучшить схему решения релаксированной Л-задачи; ускорить решение рассматриваемого класса задач путем распараллеливания вычислений на многопроцессорных компьютерах.

Литература

Хохлюк В.И «Задачи целочисленной оптимизации», Новосибирск: НГУ, 1980. 92 с.

Научный руководитель - доктор физ.-мат. наук В.И. Хохлюк

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии Обратная связь

[Головная страница] [Конференции]

© 1996-2000, Институт вычислительных технологий СО РАН, Новосибирск
© 1996-2000, Сибирское отделение Российской академии наук, Новосибирск
    Дата последней модификации: 06-Jul-2012 (11:48:14)