Аттестационная комиссия
Комиссия по аккредитации
Комиссия по экспертов
Распоряжения, инструкции
Нормативные акты
Номенклатура
Организации
Ученые советы
Семинары
Диссертации
Научные руководители
Ученые
Докторанты
Постдокторанты
CNAA logo

 română | русский | english


Оптимальные потоки в динамических сетях и алгоритмы их нахождения


Автор: Fonoberova Maria
Степень:доктор физико-математических наук
Специальность: 01.01.09 - Математическая кибернетика и операционные исследования
Год:2008
Научный руководитель: Dumitru Lozovanu
доктор хабилитат, профессор, Государственный Университет Молдовы
Институт: Институт математики и информатики АНМ
Ученый совет: DH 30-01.01.09-27.03.08
Государственный Университет Молдовы

Статус

Диссертация была зашищена 25 января 2008
Утверждена Национальным Советом 28 февраля 2008

Автореферат

Adobe PDF document0.41 Mb / на румынском

Диссертация

CZU 519.1

Adobe PDF document 0.97 Mb / на английском
90 страниц


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

потоки в сетях, динамические сети, поток минимальной стоимости, максимальный поток, многопродуктовые потоки, метод расширенной сети

Аннотация

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

В диссертации исследуются две основные задачи, касающиеся нахождения оптимальных потоков в динамических сетях: задача о потоке минимальной стоимости и задача о максимальном потоке. В динамических сетях для этих задач поток работает во времени, и стоимости прохождения потока по дугам нелинейны и зависят от времени и потока. Рассматриваемые задачи исследуются на динамических сетях, когда все параметры сети зависят от времени. Эти задачи обобщают классические потоковые задачи на статических сетях и некоторые известные динамические оптимизационные модели на сетях. Предполагается, что функция пропускной способности и функция спроса-предложения зависят от времени, а функция стоимости на дугах зависит как от времени, так и от потока. В общем случае для многопродуктовых задач предполагается, что время прохождения потока по дуге зависит от типа продукта, входящего в нее. Кроме того, исследуется динамическая модель с функциями времени прохождения по дугам, которые зависят от величины потока и момента времени вхождения потока в дугу. Для решения поставленных задач разработаны и обоснованы эффективные алгоритмы на базе принципов динамического программирования и метода расширенной сети. Используя концепцию кооперативных и некооперативных игр сформулированы и исследованы многокритериальные варианты указанных задач. Рассматриваются некоторые подходы и методы нахождения оптимальных в смысле Парето и Нэша решений для многокритериальных задач. Раскрывается взаимосвязь между задачей оптимального управления на сети и задачей о потоке минимальной стоимости на сети с вогнутыми функциями стоимости на дугах. В среде программирования Visual Studio 2005 разработаны программы построения расширенной и уменьшенной расширенной сетей для однопродуктовых и многопродуктовых динамических сетей для исследуемых задач.

Диссертация написана на английском языке.

Содержание


ГЛАВА 1. Статические потоковые модели и нахождение оптимальных потоков в сетях
  • 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. Задачи о потоке минимальной стоимости с вогнутыми функциями стоимости и задачи оптимального управления на сетях