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

Аннотация

А.А. Аль-Хулайди, Ю.О. Чернышев

В данной работе описывается параллельный алгоритм для поиска оптимального решения транспортной задачи, в основе которого лежит метод потенциалов. Эффективность алгоритмов была доказана в ходе проведения эксперимента.
Ключевые слова: метод потенциалов, параллельное программирование, транспортная задача.

05.13.01 - Системный анализ, управление и обработка информации (по отраслям)

Введение. Рассматриваемая задача может найти применение в различных областях: в экономике; в логистическом планировании; в учебном процессе; при разработке баз данных и в программировании.
Это позволяет говорить об актуальности данной задачи. Использование данного алгоритма вместе с параллельным алгоритмом нахождения опорного плана    позволяет решать транспортную задачу в многопроцессорной или кластерной среде с большей эффективностью.
Подходы к решению транспортной задачи с помощью параллельных     алгоритмов изложены, например, в работе [1]. В работе [2] приведены      экспериментальные данные, полученные при выполнении параллельных       алгоритмов нахождения оптимального решения транспортной задачи на     кластере, однако отсутствует сколько-нибудь подробное описание       применявшихся при этом   методов. Монография [3] содержит подходы к     распараллеливанию методов      решения задачи целочисленной оптимизации, которые могут быть применены и при решении транспортной задачи.
В данной статье подробно описан параллельный алгоритм нахождения оптимального решения транспортной задачи, приводится блок-схема и данные о его производительности, полученные экспериментальным путём.
1. Постановка задачи
Транспортная задача является специальным типом задач линейного      программирования. Математическая постановка этой задачи имеет вид [4]:

     (1)                                                          
Здесь  – объем,  – тариф поставки продукции от i-го поставщика к j-му потребителю,  – потребности потребителей в продукции,  – запасы прдукции у поставщиков.
Видно, что задача (1) является задачей линейного программирования со специальной матрицей. В задаче (1) имеется (m ∙ n) неизвестных X_ij и (m + n) уравнений. Решение транспортной задачи называется оптимальным планом   перевозок (поставок) продукции.
Метод распределения ресурсов состоит из двух этапов:

1. построение опорного плана;
2. поиск оптимального плана.

   Для получения оптимального решения  используются различные алгоритмы, такие как венгерский метод; метод потенциалов [5].      Наиболее удобным для распараллеливания является метод      потенциалов. Метод потенциалов позволяет, отправляясь от            некоторого    опорного плана перевозок, построить решение      транспортной задачи за конечное число шагов (итераций).
Условные обозначения:

• u_i, v_j  ― симплексные множители (или потенциалы) для строк и столбцов соответственно (i = 1,2..m, j = 1,2..n);
• c_i,j  ― план поставок;
• k_i,j  ― коэффициенты для каждой ячейки, которые рассчитываются  по формуле ki,j = ui + vj – ci,j;
• minc – переменная, в которой хранится минимальное значение c_i,j  для всех ячеек, входящих в цикл перерасчёта.

     Последовательный алгоритм решения транспортной задачи методом потенциалов для получения оптимального решения  выглядит следующим     образом.

1. Полагаем v_n = 0.
2. Находим u_i (i = 1..m) ,  v_j ( j = 1..n–1).
3. Для каждой клетки (i, j) рассчитываем k_i,j = u_i + v_j – c_i,j.
4. Если для всех (i, j) в случае  k_i,j ≤ 0, то план является оптимальным и метод завершается.
5. Выбираем ячейку (imax, jmax) с наибольшим k_i,j = kmax и строим цикл, попутно находя наименьшее minc из значений c_ij в ячейках, имеющих в цикле чётный номер.
6. Полагаем
    где l – порядковый номер ячейки в цикле,  i, j – координаты ячейки цикла.
7. Переходим к шагу 3.

Примечание. Переменная cell_odd устанавливается в состояние true для ячеек в цикле, находящихся на чётных местах, и в состояние false для ячеек на нечётных местах.
На рис. 1 представлена схема последовательного алгоритма нахождения оптимального решения транспортной задачи методом потенциалов.

Рис1. Схема последовательного  алгоритма нахождения оптимального решения транспортной задачи на основе метода потенциалов.

2.Разработка модификации метода потенциалов для работы в     параллельной среде
Распараллеливанию в приведённом последовательном алгоритме       подлежат шаги 3–4 (расчёт и сравнение k) и шаг 6 (расчёт новой таблицы       поставок).
Параллельный алгоритм для нахождения оптимального  решения транспортной задачи выглядит следующим образом.

1.Полагаем v_n = 0.
2.Находим u_i, i = 1..m,  и  v_j, j = 1..n–1.
3.Разделяем множество клеток на части пропорционально количеству процессоров N. Передаём информацию вычислительным узлам.
4.Для каждой клетки (i, j) в группе рассчитываем k_i,j = u_i + v_j – c_i,j и     находим max k_i,j.
5.Получаем данные от вычислительных узлов и выбираем наибольший maxk (для ячейки maxi, maxj) из max k_i,j по группам.
6.Если maxk ≤ 0, то план является оптимальным и метод завершается.
7.Строим цикл из ячейки (maxi, maxj), попутно находя наименьшее minc из значений c в ячейках, имеющие в цикле чётный номер.
8.Разбиваем цикл на части пропорционально количеству узлов N. 9.Передаём координаты и положение ячеек цикла вычислительным узлам. 9.Для каждой ячейки полагаем  
где l – порядковый номер ячейки в цикле,  i, j – координаты ячейки цикла.

10.Переходим к шагу 3.

   На рис. 2а и 2б представлена схема параллельного алгоритма нахождения   оптимального решения транспортной задачи методом потенциалов.

 
Рис 2a. Начало схемы параллельного алгоритма нахождения оптимального решения транспортной задачи на основе метода потенциалов.

Рис 2б. Окончание схемы параллельного алгоритма нахождения оптимального решения транспортной задачи на основе метода потенциалов.

3. Экспериментальная проверка эффективности параллельного алгоритма
Эффективность приведённого параллельного  алгоритма проверялась путём выполнения его на кластере следующей конфигурации: 

• 4 вычислительных узла (Intel Pentium 4 2,4 ГГц);
•  управляющий узел (Intel Pentium 4 2,4 ГГц);
• Узлы объединены между собой сетью Infiniband     (пропускная способность 4 Гбит/с).Описанная программа реализована в среде С++. Время выполнения последовательного алгоритма - .

Время выполнения параллельного алгоритма -   .       Ускорение – У определялось по формуле:  У = .Выигрыш – В , В= *100%.       Результаты вычислительных экспериментов по исследованию параллельного алгоритма представлены в таблице 1, которую иллюстрирует рис. 3.
                Табл. 1. Результаты вычислительных экспериментов  исследования последовательного и  параллельного алгоритмов

Согласно полученным результатам, ускорение при небольших размерностях         задачи значительно меньше 0,5. Это означает, что алгоритм неэффективно      работает при небольших размерностях задачи. Однако для больших              размерностей  получается значительный  выигрыш (до 150%). Таким образом, при     увеличении размерности матриц соотношение операций пересылок и   полезных операций существенно уменьшается. На рис. 3 представлены            графически       зависимости ускорения параллельного алгоритма от числа     используемых процессоров при различной размерности задачи.

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

На рис. 4 представлены графически зависимости ускорения параллельного алгоритма от размерности задач.

Рис. 4. Зависимость ускорения параллельного алгоритма нахожденья оптимального решения, транспортной задачи  от размерности задач

Заключение
Был разработан параллельный алгоритм для нахождения оптимального решения  транспортной задачи, который  возможно использовать для работы на кластерной локальной сети,  либо на многопроцессорной системе. Проведенное тестирование,  позволяет сделать  вывод,  о том что данный алгоритм возможно      использовать для эффективного нахождения оптимального решения            транспортной задачи.
Данная работа выполнена при поддержке РФФИ (грант № 10-01-00481-а), г/б № 1.21.11.

Литература
1.Барский А. Б. Параллельное программирование. – СПб.: Бином, 2007.
2.Северин А. А. Исследование эффективности реализации численных методов на кластерах персональных ЭВМ. – Минск, 2005.
3.Хохлюк В. И. Параллельные алгоритмы целочисленной оптимизации. – 2007.
4.Каныгин Г.И., Месхи Б.Ч., Соболь Б.В. Методы оптимизации  / Каныгин Г.И., Месхи Б.Ч., Соболь Б.В. — М.: Издательство: Феникс, 2009 г. — 384 с.
5.Рыков А.С. Системный анализ: модели и методы принятия решений и поисковой оптимизации. — М.: МИСиС, 119049.