ФУНДАМЕНТАЛЬНАЯ И ПРИКЛАДНАЯ МАТЕМАТИКА
2003, ТОМ 9, ВЫПУСК 1, СТР. 235-251

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

Е. В. Панкратьев
А. М. Чеповский
Е. А. Черепанов
С. В. Чернышёв

Аннотация

Посмотреть как HTML    Посмотреть как рисунок

Рассматривается ориентированный граф $G\; =\; (V,E)$ большой размерности, на рёбрах которого задан набор характеристик. В графе выделено подмножество вершин $V\text{'}$Ì V, на которые наложены дополнительные условия. В работе приведён алгоритм сведения задачи оптимизации на графе $G$ к задаче оптимизации на графе $G\text{'}\; =\; (V\text{'},E\text{'})$ меньшей размерности. Приведены основные этапы решения и методы построения приближённого решения задачи на преобразованном графе $G\text{'}$.

Полнотекстовая версия статьи в формате PDF (196 Kb)

URL страницы: http://mech.math.msu.su/~fpm/rus/k03/k031/k03114h.htm.
Изменения вносились 4 апреля 2004 г.