Модификация метода пометок для задач  многокритериальной оптимизации на графах

Метод пометок (метод Дейкстры) позволяет найти кратчайший путь между двумя вершинами в графе с заданными длинами ребер. В статье предлагается модификация метода пометок для случая, когда каждое ребро графа характеризуется не одной, а несколькими характеристиками, например временем и стоимостью проезда по ребру. В задачах многокритериальной оптимизации разные лица, принимающие решения (ЛПР), могут выбирать различные решения. Но, как правило, ЛПР не может формализовать свои предпочтения. Поэтому необходимо уметь строить достаточно представительное множество оптимальных по Парето путей. Традиционно для решения подобных задач используются интерактивные человеко-машинные процедуры, формирующие Парето-оптимальные решения на основе выявленных предпочтений ЛПР. В статье рассмотрен один из возможных подходов к построению такой процедуры, основанный на оптимизации одного из критериев при заданных ЛПР ограничениях на остальные критерии. Построенные таким образом пути предъявляются ЛПР, которые анализируют их и уточняют свои требования, до тех пор пока не будет получен удовлетворяющий их путь. Для проверки эффективности предложенного подхода планируется провести серию вычислительных экспериментов.

Ключевые слова

граф, метод пометок, многокритериальная оптимизация, оптимальность по Парето

Получено

05.03.2020

Дата публикации

20.03.2020

Кол-во символов

8386

Цитировать

ГОСТ	Заславский А. А. , Белова А. М. Модификация метода пометок для задач многокритериальной оптимизации на графах // Экономика и математические методы – 2020. – Tом 56. – Номер 1 C. 95-99 [Электронный ресурс]. URL: https://emm.jes.su/S042473880008559-3-1 (дата обращения: 02.05.2024). DOI: 10.31857/S042473880008559-3
MLA	Zaslavsky, Alexey, Belova, Alina "Modification of the label method for problems of multicriterial optimization." Ekonomika i matematicheskie metody 56.1 (2020):95-99. DOI: 10.31857/S042473880008559-3
APA	Zaslavsky A., Belova A. (2020). Modification of the label method for problems of multicriterial optimization. Ekonomika i matematicheskie metody 56(1), pp.95-99 DOI: 10.31857/S042473880008559-3

100 руб.

При оформлении подписки на статью или выпуск пользователь получает возможность скачать PDF, оценить публикацию и связаться с автором. Для оформления подписки требуется авторизация.

Оператором распространения коммерческих препринтов является ООО «Интеграция: ОН»

Всего подписок: 0, всего просмотров: 1000

Оценка читателей: голосов 0

1. Bellman R. (1958). On a routing problem (неопр.) // Quarterly of Applied Mathematics. — 1958. — Т. 16. — С. 87—90

2. Moore E.F. (1957) The shortest path through a maze// Proceedings of an International Symposium on the Theory of Switching 1957 — Harvard University Press, 1959. — Vol. 2. — P. 285–292. — 345 p. — Annals of the Computation Laboratory of Harvard University. V.30.

3. Галкина В.А. (2003). Построение кратчайших путей в ориентированном графе //Дискретная математика. Комбинаторная оптимизация на графах. — Москва: Издательство "Гелиос АРВ", 2003. — С. 75—94. — 232 с.

4. Левит Б.Ю., Лившиц В.Н. (1972). Нелинейные сетевые транспортные задачи. М.: Изд-во «Транспорт». 144 с.

5. Подиновский В.В., Ногин В.Д. (1982). Парето-оптимальные решения многокритериальных задач. М.: Наука. 256 с.

6. Ху Т. (1974). Целочисленное программирование и потоки в сетях. М.: Мир. 520с.

7. Черкасский и др. (1996), Cherkassky B.V., Goldberg A.V., Radzik T. Shortest past algorithms. // Math.Prog. — Springer Science+Business Media 1996. — Vol. 73, Iss. 2. — P. 129–174.