Оптимальные потоки в динамических сетях и алгоритмы их нахождения
|
СтатусДиссертация была зашищена 25 января 2008Утверждена Национальным Советом 28 февраля 2008 Автореферат – 0.41 Mb / на румынскомДиссертацияCZU 519.1
|
Ключевые слова
потоки в сетях, динамические сети, поток минимальной стоимости, максимальный поток, многопродуктовые потоки, метод расширенной сетиАннотация
Диссертационная работа относится к области теории оптимизации, связанной с разработкой методов и алгоритмов решения однопродуктовых и многопродуктовых потоковых задач в динамических сетях. Данная тематика является естественным развитием теории статических потоков и имеет важное значение при исследовании и решении широкого круга прикладных задач.
В диссертации исследуются две основные задачи, касающиеся нахождения оптимальных потоков в динамических сетях: задача о потоке минимальной стоимости и задача о максимальном потоке. В динамических сетях для этих задач поток работает во времени, и стоимости прохождения потока по дугам нелинейны и зависят от времени и потока. Рассматриваемые задачи исследуются на динамических сетях, когда все параметры сети зависят от времени. Эти задачи обобщают классические потоковые задачи на статических сетях и некоторые известные динамические оптимизационные модели на сетях. Предполагается, что функция пропускной способности и функция спроса-предложения зависят от времени, а функция стоимости на дугах зависит как от времени, так и от потока. В общем случае для многопродуктовых задач предполагается, что время прохождения потока по дуге зависит от типа продукта, входящего в нее. Кроме того, исследуется динамическая модель с функциями времени прохождения по дугам, которые зависят от величины потока и момента времени вхождения потока в дугу. Для решения поставленных задач разработаны и обоснованы эффективные алгоритмы на базе принципов динамического программирования и метода расширенной сети. Используя концепцию кооперативных и некооперативных игр сформулированы и исследованы многокритериальные варианты указанных задач. Рассматриваются некоторые подходы и методы нахождения оптимальных в смысле Парето и Нэша решений для многокритериальных задач. Раскрывается взаимосвязь между задачей оптимального управления на сети и задачей о потоке минимальной стоимости на сети с вогнутыми функциями стоимости на дугах. В среде программирования Visual Studio 2005 разработаны программы построения расширенной и уменьшенной расширенной сетей для однопродуктовых и многопродуктовых динамических сетей для исследуемых задач.
Диссертация написана на английском языке.
Содержание
- 1.1. Статические потоки: определения и некоторые свойства
- 1.1.1. Однопродуктовый поток
- 1.1.2. Многопродуктовый поток
- 1.2. Задача о максимальном потоке
- 1.3. Задача о потоке минимальной стоимости
- 1.3.1. Линейный случай
- 1.3.2. Нелинейный случай
- 1.4. Задача о многопродуктовом потоке минимальной стоимости
- 1.4.1. Непрерывно-дифференцируемая и выпуклая функция цели
- 1.4.2. Сепарабельная функция цели
ГЛАВА 2. Динамические однопродуктовые потоковые задачи и метод расширенной сети для их решения
- 2.1. Динамическая задача о потоке минимальной стоимости
- 2.2. Метод решения динамической задачи о потоке минимальной стоимости
- 2.3. Динамическая модель с задержкой потока в вершинах
- 2.4. Динамическая модель с задержкой потока в вершинах и постоянными функциями спроса-предложения
- 2.5. Алгоритм
- 2.6. Подходы к решению динамических задач о потоке минимальной стоимости с различными типами функций стоимости на дугах и некоторые обобщения
- 2.7. Нахождение потоков минимальной стоимости в динамических сетях с функциями транзита, зависящими от потока и времени
- 2.8. Алгоритм решения задачи о максимальном потоке в динамической сети
ГЛАВА 3. Динамические многопродуктовые потоковые задачи и алгоритмы их решения
- 3.1. Задача о многопродуктовом потоке минимальной стоимости в динамической сети
- 3.2. Метод решения динамической задачи о многопродуктовом потоке минимальной стоимости
- 3.2.1. Динамическая сеть с разными временами прохождения по дуге для различных продуктов
- 3.2.2. Динамическая сеть с сепарабельными функциями стоимости и без ограничений на взаимные пропускные способности дуг
- 3.2.3. Динамическая сеть с одинаковыми временами прохождения по дуге для различных продуктов
- 3.3. Алгоритм
- 3.4. Примеры
- 3.5. Некоторые обобщения
- 3.6. Построение расширенной сети для ациклических графов
- 3.7. Динамическая задача о многопродуктовом потоке минимальной стоимости с функциями транзита, зависящими от потока и времени
- 3.8. Алгоритм решения динамической задачи о многопродуктовом максимальном потоке
ГЛАВА 4. Оптимальные динамические потоки в системах принятия решений
- 4.1. Теоретико-игровой подход для решения многокритериальных многопродуктовых потоковых задач на сетях
- 4.1.1. Равновесие Парето-Нэш для многокритериальных игр
- 4.1.2. Многокритериальные многопродуктовые потоковые модели
- 4.1.3. Комментарии
- 4.2. Динамические задачи о потоке минимальной стоимости без ограничений на пропускные способности дуг
- 4.2.1. Задачи о потоке минимальной стоимости с функциями стоимости, не зависящими от потока, и задачи синтеза сетей
- 4.2.2. Задачи о потоке минимальной стоимости с вогнутыми функциями стоимости и задачи оптимального управления на сетях
Официальные оппоненты
- Dumitru Zambiţchi
доктор, доцент - Gheorghii Doneţ
doctor habilitat în ştiinţe fizico-matematice, profesor universitar, Institutul de Cibernetică V. M. Gluşkov, Academia Naţională de Ştiinţe a Ucrainei, Kiev, Ucraina
Диссертации
