|
Вестник Удмуртского университета. Математика, 2006, выпуск 1, страницы 127–150
(Mi vuu253)
|
|
|
|
Эта публикация цитируется в 8 научных статьях (всего в 8 статьях)
МАТЕМАТИКА
О структуре одной экстремальной задачи маршрутизации с ограничениями в виде условий предшествования
А. Г. Ченцов Институт математики и механики УрО РАН, г. Екатеринбург
Аннотация:
Рассматривается задача последовательного обхода сечений многозначных отображений, осложненная ограничениями. Последние связаны с реализацией конечного набора адресных перемещений для заданных пар «отправитель – получатель» (по ходу этих перемещений могут посещаться сечения других многозначных отображений). В качестве решения рассматривается пара маршрут – трасса; маршрут определяется в виде перестановки индексов многозначных отображений и имеет смысл дискретной компоненты (полного) решения, а трасса («непрерывная» компонента) понимается как кортеж точек в сечениях многозначных отображений, индексированных в соответствии с маршрутом. Последний должен удовлетворять вышеупомянутым условиям адресных перемещений. Перемещения же между множествами характеризуются затратами, которые аггрегируются посредством суммирования, порождая аддитивный критерий, который и должен минимизироваться в классе всех допустимых пар маршрут – трасса. В работе построена модификация метода динамического программирования (МДП) на основе эквивалентного преобразования исходной задачи к задаче с ограничениями на реализацию (текущих) переходов с множества на очередное (следующее по списку) множество. Для частного случая «метрической» задачи на плоскости проведены расчеты на основе алгоритма с использованием МДП.
Ключевые слова:
маршрут, метод динамического программирования, условия предшествования.
Поступила в редакцию: 01.10.2005
Образец цитирования:
А. Г. Ченцов, “О структуре одной экстремальной задачи маршрутизации с ограничениями в виде условий предшествования”, Вестн. Удмуртск. ун-та. Матем., 2006, № 1, 127–150
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/vuu253 https://www.mathnet.ru/rus/vuu/y2006/i1/p127
|
Статистика просмотров: |
Страница аннотации: | 250 | PDF полного текста: | 44 | Первая страница: | 1 |
|