Разработка методов и алгоритмов в задачах оптимального использования и развития сетей

• Автор: Думбадзе, Ламара Георгиевна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Москва
• Количество страниц: 140 с. : ил.

1. ГЛАВА
АНАЛИЗ РАЗВЕТВЛЕГКОСТИ СЕТИ
1Л. Эффективный метод анализа разветвленности сети 3
1ЛЛ. Общее
1Л .2. Постановка задач и метод их решения
і Л .3. Методика проверки существования трёх независимых путей между
любой парой узлов сети без использования компьютера
1 Л.4. Пример
1.2. Задача об улучшении разветвленности сети
2. ГЛАВА
МАКСИМИЗАЦИЯ ИСПОЛЬЗОВАНИЯ СЕТИ
2.1. Оптимальное использование сети для многопродуктового 49 одноприоритетного потока
2.1.1. Постановка задачи и алгоритм решения
2.1.2. Эффективный алгоритм генерации столбцов в задаче оптимального использования сети
2.2. Алгоритмы нахождения кратчайших путей в оптимизационных задачах на сетях связи
2.2.1. Поля кратчайших путей
2.2.2. Модифицированный алгоритм Дейкстры для неориентированной
сети
2.2.3. Модифицированный алгоритм Дейкстры для поля
2.2.4. Результаты вычислительного эксперимента
2.3. Задача эффективной эксплуатации сети связи
2.3.1. Постановка задачи

2.3.2. Алгоритм решения задачи
2.3.3. Пример решения задачи
3. ГЛАВ А
ОПТИМИЗАЦИОННЫЕ ЗАДАЧИ РАЗВИТИЯ СЕТИ
3.1. Задача развития сети с минимизацией капиталовложений при обеспечении заданных объемов потоков каждого продукта
3.1.1. Линейная частично-целочисленная задача с большим количеством непрерывных переменных
3.2. Задача развития сети при ограниченных капиталовложениях
3.2.1. Математическая постановка задачи
3.2.2. Алгоритм решения задачи развития сети при ограниченных капиталовложениях
3.2.3. Пример решения задачи развития сети при ограниченных капиталовложениях
3.3. Задача развития сети с целью максимизации прибыли в условиях получения кредита. Оптимизация объема кредита
3.3.1. Математическая постановка задачи
3.3.2. Алгоритм решения задачи развития сети с выбором оптимального кредита
3.3.3. Пример решения задачи развития сети с выбором оптимального кредита
4. ГЛАВА
МНОГОМЕРНАЯ ЗАДАЧА О РАНЦЕ СПЕЦИАЛЬНОЙ ЛЕСТНИЧНОЙ СТРУКТУРЫ С КОЭФФИЦИЕНТАМИ РАВНЫМИ 0 ИЛИ 1 В МАТРИЦЕ ОГРАНИЧЕНИЙ
4.1. Постановка и алгоритм решения задачи
4.2. Пример решения задачи
4.3. Абсолютно унимодулярные матрицы, состоящие из 0 и 1

4.3.1. Абсолютная унимодулярность матриц ограничений многомерной задачи о ранце специальной лестничной структуры
4.3.2. Абсолютная унимодулярность выпуклых матриц
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ

где х — Х . векх0р неизвестных переменных, который разбивается на
подвекторы размерностей ^к ~ ^к-> ^ = Ь2,.^ = 0 ; элементы
матрицы {ад} > / = 1»2»...,ТП, ] = 1,2 ? принимают значения 0 или 1;
, /=1,25 и ^ , к = 1,2 /Г ? . строго положительные
постоянные.
Ограничения (2.1.2) являются связывающими, а (2.1.3) - блочными. При этом в каждом блоке имеется единственная строка для неизвестных переменных. Величина % представляет собой связывающую скалярную переменную.
Задачу (2.1.1) - (2.1.3) будем решать по методу Данцига-Вулфа [8], [17]. Для этого сделаем предварительные преобразования. Заметим, что при
некотором достаточно малом 2 > 0 существует допустимое решение задачи (2.1.1) - (2.1.3). Пусть оно нам известно. Обозначим его через
•*7> ] ~ ..,«/£ . Введём
ж = пип 5с,, 5с, =5с,
<]иК } } ь
Пусть для определённости 1 — ] —*7. Выберем произвольно из каждой из остальных групп индексов У» ^к — У — ^к+■> ^ ~ К- — 1,
по одному х ^ , и вычтем из них . При этом ограничения (2.1.2), (2.1.3) преобразуются к виду