Целочисленное сбалансирование трехмерной матрицы

• Автор: Смирнов, Александр Валерьевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Ярославль
• Количество страниц: 177 с.

Содержание
Содержание
Введение

1 Постановка задачи

2 Кратные сети и кратные потоки: обобщение теории потоков Форда-Фалкерсона

2.1 Кратная сеть целочисленного сбалансирования

2.2 Полный поток и обобщенный путь прорыва

3 Алгоритм нахождения максимального кратного потока для решения задачи сбалансирования

3.1 Предварительные замечания

3.2 Описание алгоритма

3.3 Примеры работы алгоритма

3.4 Обоснование алгоритма
4 АП’-по л нота задачи целочисленного сбалансирования трехмерной матрицы
5 Сравнительный анализ алгоритмов целочисленного сбалансирования

5.1 Результаты вычислительных экспериментов для произвольных тестов
5.2 Результаты вычислительных экспериментов для задач ЦСЗ
6 Минимизация ошибок округления в задаче целочисленного сбалансирования матрицы
6.1 Задача минимизации ошибок округления и алгоритм ее решения
6.2 Пример работы алгоритма минимизации ошибок округления .
Заключение
Приложение А
Приложение В
Литература
Введение
Многие задачи дискретной оптимизации могут быть решены при помощи моделей и методов теории графов. Примеры приложений теории графов приведены, например, в [2, 7, 8, 16, 17, 18, 25, 34, 56, 57, 60]. Важным разделом теории графов является теория потоков Форда-Фалкерсона (см. [1, 31, 50, 59, 62]). Потоковые алгоритмы применяются для решения различных задач (см., например, [6, 9, 13, 26, 30, 33, 65, 72, 77, 80, 81]).
Наиболее известная задача теории потоков - задача о нахождении максимального потока в транспортной сети. Сведение к задаче о наибольшем потоке используется при решении ряда задач, одной из которых является задача целочисленного сбалансирования двумерной матрицы.
Различные задачи целочисленного сбалансирования возникают в сфере управления, экономики, финансов. В частности, подобная задача ставится при планировании железнодорожных грузоперевозок. Имеется матричный план по отправке вагонов, который группируется по некоторым показателям (например, направление, тип вагона, владелец вагона и т. п.). Данный план составляется на месяц и естественно является целочисленным. Однако вагоны необходимо отправлять ежедневно. При делении на количество дней в месяце план перестает быть целочисленным. Поэтому возникает проблема такого округления основных параметров, чтобы суммирующие показатели не выходили за определенные рамки. Данный план может быть представлен в

при этом запрещается уменьшение уже полученного потока для предыдущих слоев).
Основная идея состоит в применении направленного алгоритма получения полного кратного потока, который отвечает условиям разрешимости (2.1) при построении целочисленной сбалансированной матрицы. Для этого в кратной сети выделяются следующие множества дуг:
1) Р — СОСТОИТ ИЗ дуг сети (х'гОО, х'т) (I & 1 ,п)]
2) Р2 — состоит из дуг сети (До^Тсуо) 0' е 1 ,т);
3) Р3 — состоит из дуг сети (х'00р, х00р) (р 6 Тд);
Тогда направленный алгоритм получения полного потока в к-м слое формулируется следующим образом:
1. На множестве дуг Р1иР2иР3 временно считаем для этого шага нулевой пропускную способность и увеличиваем поток, пока это возможно.
2. Предыдущий шаг повторяем для следующих множеств дуг и в этом порядке Р2 и Р3, Р1 и Р2, Рг и Р3, Р3, Рь Р2.
3. Увеличиваем поток, пока это возможно, без ограничений пропускной способности на множествах дуг.
Очевидно, что послойный алгоритмявляется полиномиальным. Однако, как показали последующие исследования, данный алгоритм применим отнюдь не к любой задаче сбалансирования. Более того, Л'Р-полнота задачи целочисленного сбалансирования трехмерной матрицы (см. главу 4) влечет невозможность решения задачи за полиномиальное время.
Далее мы рассмотрим точный алгоритм нахождения максимального кратного потока, отвечающего условиям разрешимости (2.1).