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

Потенциал имеющихся пакетов, поддерживающих символические вычисления, не позволяет решать реальные проблемы математического и имитационного моделирования. Возможность обеспечения вычислений с произвольной точностью в программах пользователя дает библиотека GMP . Однако, ее использование требует от пользователя разработки собственного интерфейса для организации распределенных и параллельных вычислений [3]. Развитием библиотеки GMP является библиотека ExactComputational [4], которая предоставляет своим объектам возможность их использования в параллельных вычислениях.

Анализ способов распараллеливания показывает эффективность распараллеливания <по информации». При этой технологии вычислительный процесс строится на основе единственной программы, запускаемой на всех процессорах вычислительной системы или на многих станциях локальной сети. Копии программы могут выполняться по разным ветвям алгоритма, обрабатывая подмножества данных. Неизбежна синхронизация во времени и при обработке общих данных. Данная идеология используется в стандарте MPI (Message Passing Interface ).

Ранее авторами разработаны алгоритмы и программное обеспечение для абсолютно точного решения систем линейных алгебраических уравнений [5] и вычисления обобщенной обратной матрицы Мура-Пенроуза [6] на многопроцессорных вычислительных системах c использованием классов overlong и rational из библиотеки ExactComputational [4]. Теоретическое и практическое исследование данного программного обеспечения демонстрирует высокую эффективность использования многопроцессорных вычислительных систем.

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

1.    Техника реализации симплекс-метода

Применение симплекс-метода для практических задач линейного программирования остается вне конкуренции, несмотря на появившиеся полином иальные алгоритмы. В настоящее время используются две техники реализации симплекс-метода (см., например, [7]): (1) метод симплекс таблиц; (2) метод обратной матрицы (модифицированный симплекс метод).

Для сохранения целостности изложения приведем их особенно сти на примере задачи линейного программирования тах {сТх : Ах = Ь> 0, х > 0; с,х Е Rn; b Е Rm} . (1)

• 1.1.    Метод симплекс-таблиц

Данный метод на итерации к пересчитывает симплекс-таблицу

8 1к) = Z |к) =      /; го-1ь г|к) = -ст + J вВ(к) 1А д | к) Хд^) = В(к)- 1b В (к)-1А где В (к) - базисная матрица, содержащая все относящиеся к базисным переменным к-й итерации столбцы матрицы А (базисные столбцы); сд^) - вектор коэффициентов целевой функции, относящихся к базисным переменным к-й итерации. При этом левый столбец симплекс-таблицы содержит вектор Хд1к) = В(к)-1b значений базисных переменных к-й итерации и значение Z1к) целевой функции на этом решении. Столбцы матрицы S, соответствующие базисным переменным, являются ортами (т.е. из них может быть составлена единичная матрица). Верхняя строка содержит вектор z(k = —ст + cB(k)B(к) 1А невязок двойственной задачи. Значения элементов строки z(k, относящиеся к базисным столбцам являются нулевыми.

Критерием оптимальности текущего базисного решения является неотрицательность (к)

вектора z. Если же существует небазисная переменная Х г : z^ < 0, то условие L = { Z : S^ > 0 } = 0 является признаком неограниченности целевой функции. Если же L = {Z : S ^^ > 0 } = 0 , то введение переменной Х г в число базисных приведет к увеличению целевой функции на величину

^X B(k )„ "                              ^X B(k),»

Nt =--------,  где I = arg lex min.

с(k)                                  leL

Sl*i

Данный способ выбора Z* сохранит неотрицательность базисного решения на следующей итерации и исключает зацикливание, когда Д г = 0 [7].

Переход от таблицы к-й итерации к таблице (к + 1)-й итерации осуществляется применением процедуры исключения Жордана-Гаусса для столбца г (ведущего столбца), используя в качестве ведущей строку I*

( V Z = 0,1, 2,..., m; j = 0,1, 2,..., п) S^ ¹ =

с ^(k) с ^{(k)        l}*3 c(^k )

^S lj     Лк) ^S li   ^,

^Х- с^{(k) S} l*j

С^(k) , ^S l*t

если Z = I*, если Z = Z*

Легко заметить, что выполнение итерации, включая пересчет симплекс-таблицы, потребует не более (m+n) операций деления и сравнения, а также не менее m(n+1) операций сложения и умножения. Алгебраическая пространственная сложность табличного симплекс-метода в основном определяется числом операндов в симплекс-таблице, т.е. равна mn + O(m).

• 1.2.    Метод обратной матрицы

В данном методе, в отличие от табличного, на каждой итерации вместо пересчета симплекс-таблицы пересчитывается матрица В (к)^{- 1} . Наличие обратной матрицы позволяет для текущего базиса легко находить у(к)^т = c B(k) B(k) ^-1 - соответствующее решение двойственной задачи. Текущий базис является оптимальным если соответствующее ему двойственное решение допустимо: у(к) ^т А > с ^т . Если же в матрице А найдется столбец А,^ ) : у(к )^Т А г(к) < с ^(к) , то введение его в число базисных приведет к увеличению целевой функции.

Образом столбца А,^) в симплекс-таблице S(k) будет вектор д = В (к)- 1А^(к). Поэтому ведущей строкой, определяющей выводимый из базиса столбец, будет г = arg lex min l: g>

^X B(k)l g l     ^,

а новые значения базисных переменных равны

( V Z = 1, 2, . . . , m)

^X B(k+1)l =

^{g l}

^X B(k)l - — ^X B(k) _r , Y _   ^gr

XB(k)l gr    ,

если Z = г, если Z = г

Базисные матрицы В (к) =

m                m

V^)                             K^{(k + 1)}

bi ]     и В (к +1) = I о . I отличаются только г-м столб-

■ ^zj hd=i                  V ^z J    ) l,j=1

цом, поэтому элементы обратной матрицы В (к + 1) ¹

следующим образом

вычисляются через элементы матрицы В (fc) ¹

т

1,3=1

; (к+1) В

В(к) — в В

;<)

д , ^

д. ,№ дЛ4 ,

,

если Z = г, если Z = г.

Оценим алгебраическую вычислительную сложность рассматриваемого метода. Очевидно, что в общем случае на заключительной итерации потребуется проверка всех п ограничений двойственной задачи, для чего потребуется не более тп операций умножения и т(п — 1) операций сложения. На промежуточных итерациях для установления недопустимости двойственного решения эта величина, как правило, является существенно меньшей. Пересчет обратной матрицы потребует не более т операций деления, не более т ² операций умножения и не более (т ² — 1) операций сложения/вычитания. Поскольку т < п,то затраты вычислительных ресурсов на пересчет обратной матрицы могут быть существенно ниже затрат на пересчет симплекс-таблицы. Алгебраическая пространственная сложность метода обратной матрицы определяется числом элементов в исходных данных и в обратной матрице, т.е. равна тп + т ² + О(т), т.е. больше чем в табличном симплекс-методе.

• 1.3.    Битовая сложность абсолютно точной реализации симплекс-метода

Практическая реализуемость вычислений без округления, в частности, безошибочного решения задачи линейного программирования, определяет ся требуемыми для вычислений ресурсами: числом бит оперативной памяти и количеством операций с битами. Далее через S (А) будем обозначать число бит, требуемое для представления объекта А, а через С (А) - число битовых операций, выполненных при нахождении представления объекта А. Например, число бит, требуемое для представления целых чисел, будет равно S(0) = 1, ( У г G Z \ { 0 } )S(z) = p iog ₂ | г |) . Число бит, требуемое для представления рационального числа г = р/q, p,q G Z имеет верхнюю оценку S(r) < O(S (р) + S(q)).

Легко проверить, что если S (р), S (q) - память, требуемая для представления рациональных чисел р, q, то память, требуемая для представления результата арифметической операции о £ {+,—,/, х} над данными числами будет S (р о q) <  S(p) + S (q). Для битовой вычислительной сложности выполнения операции о £ {+,—,/, х} с помощью классических арифметических алгоритмов (умножение/деление столбиком) справедлива оценка С(р о q) <   О (S(p)S(q)). Использование алгоритмов быстрого умножения дает оценку С (ро q) < (S(р) + S(q)), которая будет использована в работе.

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

Предложение 1. Пусть В = (b ij ) - целочиелейная тхт матрица, Z = max S(b ij ).

i,j=1,2,...,n

Тогда

S (det В ) < n(log ₂ т + Z).

Доказательство. Рассмотрим верхнюю оценку абсолютной величины определителя

| det В | =

т

^ П ^bk⁽(В)

<7 к=1

т

<ЕП1 bk л_№| <т!Ь ^т< (тТ) ^т , а к=1

где L = max {| b ij | : гД = 1, 2,..., т } .

Из данной оценки следует S(det В ) = log ₂ | det В\ < m(log 2 т + Z).                    □

Предложение 2. Пусть В = (b ij ) - т х т рациональная матрица, Z = max S(b ij ). Тогда S (det В ) < m(log ₂ т + (2т + 1)Z).                                     ⁴¹ ’

Доказательство. Пусть К _Т равно наименьшему общему кратному всех знаменателей строки г = 1, 2,..., т матрицы В . Очевидно, что S(K _r ) <   Zт. Пусть К представляет диагональную матрицу: diag (K) = {К : г = 1, 2,...,т}. Рассмотрим матрицу В = КВ. Данная матрица является целочисленной. Верхняя оценка числа бит, необходимых для одного элемента матрицы В , имеет вид

Z = max S(b ij ) = max S(K i b ij ) <  1(т + 1). i,j=l,2,...,m       ^J      i,j=l,2,...,m

Принимая во внимание утверждение 1, а также log 2 | det К ^-| < Zт, получим

S(det В) = S (det К • det(В) J < m(log ₂ т + (2т + 1)Z)

□

Из формул Крамера для систем линейных алгебраических уравнений и доказанных утверждений вытекает

Следствие 1. Если один численный элемент исходных данных имеет пространственную сложность не более Z, то

• •    элементы симплекс-таблицы и обратной матрицы имеют пространственную сложность не более 4Zm²+ Zт + т log2 т + 1;

• •    столбец симплекс-таблицы и обратной матрицы имеют пространственную сложность не более 4Zт³+ Zт² + т² log2 т + т;

• •    для представления симплекс-таблицы достаточно 4Zт³n + o(Zт²n) бит;

• •    для представления обратной матрицы достаточно 4Zт⁴+ o(Zт³) бит.

2.    Параллельные версии симплекс-метода 2.1.    Метод симплекс-таблиц

Поскольку т < п, то, относительно битовой пространственной сложности симплекс-метода, предпочтение следует отдать методу обратной матрицы.

Для анализа вычислительной сложности и эффективности распараллеливания симплекс-метода рассмотрим его параллельные версии.

Для реализации м етода симплекс-таблиц наиболее подходящей представляется декомпозиция симплекс-таблицы по столбцам на число блоков равное числу процессоров N . Все столбцы симплекс-таблицы, за исключением левого столбца, делятся в равных пропорциях между N процессами, левый столбец т.е. вектор значений базисных пер еменных и значение целевой функции на нем, рассылаются всем процессам и обрабатываются ими независимо. Пример разбиения симплекс-таблицы S на блоки S (К ), К = 1, 2,...,N представлен на рис. 1.

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

	Процесс К	= 1, 2,..., A
S oo = Z	z \ K      1 +1	Z \K.' 1 +2	. . .	£ г Kn -i 1 N ।
S 1o = х в 1 S 20 = Х В 2 .	S 1 \ Д'' 1 +1 ^ 2 \ K." 1 +1 .	S 1 \ ( k-in 1 +2 ^ 2 \ Д '' 1 +2 .	.	S 1 г Kni 1 N । S 2 Г Kn^ 1 N । .
. S m0 = Х Вт	. S m \ K ^ 1 1 +1	. S m \ ^О1 1 +2	.	. S m 1 N ।

Рис. 1 . Декомпозиция симплекс-таблицы по процессорам

Алгоритм TabularSimplex

Итерация к

• •    Данные: симплекс-таблица S(K) для каждого процесса К = 1, 2, 3,..., А.

• •    Ш^аг 1. Каждому процессу К = 1, 2, 3,..., А

• —    найти столбец гк : %tK < 0; —    если столбец г к не найден, то положить С (К) = А(К) = г к = 0 и перейти на шаг 2; —    найти строку

,                (^XBl А

/ к = arg min -— ;

l; Sn _K >0 \SziK?

• —    если строка / к не найдена, то завершить выполнение всех процессов и вернуть ”Не ограничена”;

• —    вычислить Дг _к = —A si _K ^ г _к / S i _K г _к , положить А (К) = Aj _K , С (К ) = г к и перейти на шаг 2.

Комментарий. При выполнении данного шага будет либо установлена неразрешимость задачи, либо найдены данные для изменения базиса: ведущий столбец гк ~ кандидат для ввода в базис, ведущая строка / к , определяющая столбец выводимый из базиса, и приращение целевой функции Z Ki_K, - либо установлено отсутствие таких кандидатов: г к = 0.

• Ш^аг 2. Для L = 1, 2, 4, 8,..., А каждому процессу К = 1, 2, 3,..., А, номер которого удовлетворяет условию ((К — 1)%(2L)) < L, осуществить обмен данными с процессом К + L:

• —    Если С (К) = 0, то положить С (К) = С (К + L), А(К) = А(К + L) и продолжить вычисления для следующего L.

• —    Если С (К + L) = 0, то положить С (К + L) = С (К), А(К + L) = А(К) и продолжить вычисления для следующего L.

• —    Если А (К) > А(К + L), то положить С (К + L) = С (К), А(К + L) = А(К), иначе положить С (К) = С (К + L), А(К) = А(К + L).

• —    Продолжить вычисления для следующего L.

Комментарий. После завершения данного шага в каждом процессе К = 1, 2, 3,..., N значение С (К) будет равно номеру ведущего процесса

{ arglex max Дj„, К; г к ^О ^{г к ,}

О,

если { К : г к = 0 } = 0 , в противном случае,

• ТИаг З. Если К* = 0, то каждому процессу К = 1, 2, 3,..., N для

* = г А 1 + 1. г А 1 + 2..... г К? 1

положить

\ X bi , если ( S ir = 1)/\(( V z = 0,1,...,Z — 1,Z + 1.....m) S гk = 0), ^ж к

I 0,   в противном случае.

Вернуть ж - оптимальное решение задачи, Z - оптимальное значение целевой функции и завершить выполнение алгоритма.

Комментарий. Если текущее базисное решение задачи оптимально, то формирется ответ и завершается выполнение алгоритма.

• ^Цаг 4. Ведущему процессу К* передать остальным процессам ведущий столбец

S г

1гк* , ^к^* , . . . , ^тг^* у и номер ведущей строки 1к*

• ТИаг 5. Каждому процессу К = 1, 2, 3,..., N пересчитать по формуле (3) симплекс-таблицу S(К). Перейти к следующей итерации.

• • Конец алгоритма

• 2.2. Метод обратной матрицы

Из изложенного выше видно, что описание параллельной версии табличного симплекс-метода не намного сложнее чем для обычного алгоритма. При этом используется log ₂ ^ N 1 широковещательных коммуникаций между процессами при нахождении ведущего процесса К* и одна широковещательная коммуникация для передачи ведущего столбца S г _к<, и числа 1к* . В таблице 1 приведена сводка требуемого алгебраического (т.е. количества используемых алгебраических операций) вычислительного ресурса для последовательной и параллельной реализаций метода симплекс-таблиц. Из табл. и опис ания алгоритма видно, что процессоры загружены равномерно, а эффективность распараллеливания растет с ростом сложности задачи, достигая в пределе 100%.

Из описания метода обратной м атрицы следует, что максимальный эффект от распараллеливания при поиске вводимой в базис переменной достигается при декомпозиции исходных данных: вектора сТ и матрицы А, - по столбцам в равных пропорциях между процессорами на блоки

с(К) Т		= ( с ДК- 1)п V 1 у	1 +1	СГ % "  1 +2
	7 ai^	Г % "  1 +1)	ai^	Г % "  1 +2)
А(К ) =	«2(	Г % "  1 +1) . .	'У	Г Ку "  1 +2) . .
	ат /	Г % "  1 +1)	am /	Г к у "  1 +2)

^сг^к"1 У К = 1, 2,..., N; I у ।

К = 1, 2, 3, ...,N.

Таблица 1

Алгебраический вычислительный ресурс реализаций метода симплекс-таблиц

Оператор	Один процессор	N процессоров
	Количество алгебраических операций	Количество пересылаемых операндов	Нагрузка на один процесс
Проверка условия оптимальности Определение ведущей строки Выбор ведущего процесса Пересылка ведущего столбца Пересчет симплекс-таблицы	[фп] 2т + п + 2 2(т + 1)(п + 1)	N т + 2	[1,n/N ] 2т + п/N + 2 ( log 2 N 1 2т(1 + п/N )
Итого:	[1 , п ] + 2 тп + 4(т + п + 1)	т + N + 2	[1,n/N ] + 2(n/N )(т + 1) + 4 т + 2 + log 2 N

При этом предполагается, что вектор двойственных переменных у размещен в каждом процессе К = 1, 2,..., N,

Эффект от распараллеливания при пересчете обратной матрицы В^{- 1} будет максимальным при ее декомпозиции по строкам в равных пропорциях на блоки по числу процессов

В- ¹ (К ) =

/ Ь/ (К-l)rn .

।     N    l ^ ¹^¹

^Ь( г ^(К~^l)^ i | 2^1

I     N     ¹⁺²J¹

, , ,

\ ^Ь( Г ^Nr 1 )1

^Ь( гС^Штт+Аг

\¹     N    ^{1 +1}^²

^Ь( г(К-1)тп ₂Х₂

¹     N    ^{1 +2}^²

,, ,,

,

^Ь( Г Кг 1 +2 ) 2

Ь/г(К — l)r-i . -.X    ^

(^Г N ¹⁺¹) ^т

^Ь( Г (К— 1)т_п , г>Х

(^{Г (} n ^{)  1+2}) ^т

, , ,

^Ь( Г Кг 1 +2 )т /

, К = 1, 2, 3, ...,N. (9)

Из описания метода обратной матрицы следует целесообразность декомпозиции вектора Х в базисных переменных, вектора С в коэффициентов целевой функции при базисных переменных и вектора д по таким же блокам строк

Х в (К) =

^{Х в} Г X "  1 +1

^{Х в} Г ^К_N "  1 +2

, , ,

Х В Г Кт 1

^Г N ¹

с в (К ) =

^{С в} Г " _N "  1 +1 ^{С В} Г " _N "  1 +2

, , ,

^С В Г Кт !

^Г N ¹

; д^{(К )} =

/ ^д Г ⁽К- рт п .

^Г N ¹⁺¹

^д Г ^К_N "  1 +2

, , ,

^д Г Кт 1

К = 1, 2, 3, ...,N. (10)

Способ (9) декомпозиции обратной матрицы по процессам позволяет каждому процессу вычислить субвектор двойственных переменных

у(К ) = (В (К)- ^Т с в ₍ д) .

Очевидно, что вектор двойственных переменных

N у = ^2 у^.

Изложенное выше позволяет предложить следующую параллельную реализацию итерации метода обратной матрицы,

Алгоритм InvBasMatrSimplex

Итерация к

• •    Данные: в каждом процессе К = 1, 2, 3,..., А размещены

у - вектор двойственных переменпых, построенный по текущему базисному решению прямой задачи;

М (К) - вектор номеров базисных переменных процесса;

Х _в (К) - вектор значений базисных переменных процесса;

с в (К ) - вектор значений коэффициентов целевой функции при базисных переменных процесса;

А(К ) - блок матрицы ограничений процесса;

с(К) ^т - блок коэффициентов целевой функции процесса;

В^{- Т} (К ) - блок обратной матрицы процесса.

• •    Ш^аг 1. Каждому процессу К = 1, 2, 3,..., А

• —    найти столбец

г к ^: % г к = ^{А(К) Т} к у - ^{с( К}^к < °;

• —    если столбец г к не найден, то положить С (К) = А(К) = г к = °; иначе положить △ ( к ) =   , с ( к ) = г к .

• •    Ш^аг 2. Для L = 1, 2,4, 8,..., А каждому процессу К = 1, 2, 3,..., А, номер которого удовлетворяет условию ((К — 1)%(2L)) <  L, осуществить обмен данными с процессом К + L:

• —    Если С (К ) = °, то положить С (К ) = С (К + L), А(К) = А(К + L) и продолжить вычисления для следующего L.

• —    Если С (К + L) = °, то положить С (К + L) = С (К), А(К + L) = А(К) и продолжить вычисления для следующего L.

• —    Если А (К) < А(К + L), то положить С (К + L) = С (К), А(К + L) = А(К), иначе положить С (К) = С (К + L), А(К) = А(К + L).

• —    Продолжить вычисления для следующего L.

Комментарий. При завершении данного шага в каждом процессе К = 1, 2, 3,..., А значение С (К) будет равно номеру столбцового ведущего процесса

К с

arg

min

К; г к ^О

А ,

°,

если { К : г к = ° } = 0 , в противном случае,

Ш^аг 3 . Если К ^с = °, то сформировать решение задачи:

• —    положить т[1 : п] = °;

• —    каждому процессу К = 1, 2, 3,..., А для

  г

  
  

_ _г(К-М> ^     _г(К-М> ^        _гКт_п

I а । + , 1 а । + ,..., I а । положить жм (к)г = Хв(кр;

• —    вернуть х - оптимальное решение задачи, у - оптимальное решение двойственной задачи и завершить выполнение алгоритма.

• •    Ш^аг 4. Процессу К ^с разослать всем процессам К = 1, 2,..., N столбец А г _кс и значение коэффициента С г _кс .

• •    Ш^аг 5. Каждому процессу К = 1, 2,..., N вычислить д(К ) = В(К) ^-1А г _кс и

• г(К) = arg min   б(К, I) = —дудД^ .

• I:    9(К) _г >0 L                д^К)i

Если г (К ) не найдено, то положить С (К) = 0, в противном случае положить С (К) = г(К ), А(К) = И(К,г(К )).

• • Ш^аг 6. Для L = 1, 2, 4, 8,..., N каждому процессу К = 1, 2, 3,..., N, номер которого удовлетворяет условию ((К — 1)%(2L)) <  L, осуществить обмен данными с процессом К + L:

• —    Если С (К ) = 0, то положить С (К ) = С (К + L), А(К) = А(К + L) и продолжить вычисления для следующего L.

• —    Если С (К + L) = 0, то положить С (К + L) = С (К), А(К + L) = А(К) и продолжить вычисления для следующего L.

• —    Если А (К) < А(К + L), то положить С (К + L) = С (К ), А(К + L) = А(К), иначе положить С (К ) = С (К + L), А(К) = А(К + L).

• —    Продолжить вычисления для следующего L.

Комментарий. При завершении данного шага в каждом процессе К = 1, 2, 3,..., N значение С (К) будет равно номеру строкового ведущего процесса

К ^Т = arg lex min ^(К,г(К)).

К : З т(К)

е Ш^аг 7. Ведущему процессу К ^г разослать всем процессам К = 1, 2, 3,..., N ведущую строку г* = г(К ^т ) обратной матрицы

В(К) ^     — ( Ьт*г, Ьт«2, ■ • ■ , br*m } и значение д (Кг )г*. Положить М(К)г* = гкс, св (К)г* = Сгкс.

• •    Ш^аг 8. Каждому процессу К = 1, 2,..., N вычислить новые значения базисных переменных процесса Х в (К) по формулам (5), новый блок обратной матрицы процесса В^{- 1} (К) по формулам (6), и двойственное субрешение блока

у(К ) = (В(К)-^х) ^Т с в (К).

• •    Ш^аг 9. Для L = 1, 2, 4, 8,..., N каждому процессу К = 1, 2, 3,..., N, номер которого удовлетворяет условию ((К — 1)%(2L)) < L, осуществить обмен данными с процессом К + L:

• -    у = у(К) + у(К + L);

• -    у(К) = у(К + L) = у;

Таблица 2

Алгебраический вычислительный ресурс метода метода обратной матрицы

Оператор	Один процессор	N процессоров
	Количество алгебраических операций	Количество пересылаемых операндов	Нагрузка на один процесс
Проверка условия оптимальности	2т[1, п]		2т[1, n/N ]
Выбор с-ведущего процесса	—	N	log 2 N
Передача ведущего столбца	—	т + 1	—
Нахождение g	т(т — 1)	—	т(т — 1)/N
Нахождение ведущей строки	2т	N	2т/N + log 2 N
Модификация Х в	1 + 2т	1	2т/N
Модификация В- 1	3т 2	т	3(т 2 /N)
Вычисление у(К )	—		(т/N)(2(т/N ) - 1)
Вычисление у	т(2т — 1)	N	log 2 N
Итого:	2т[1, п] + 6т 2 + 2т — 1	2т + 3N + 2	2т[1, n/N ] + 6т 2 /N + 2т/N +
			3 log 2 N

• —    Продолжить вычисления для следующего L.

Комментарий. При завершении данного шага в каждом процессе К = 1, 2, 3,..., N вектор у(К ) будет содержать двойственное решение у, построенное по текущему базисному решению.

• • Конец алгоритма

3. Заключение

Таким образом, описание параллельной версии метода обратной матрицы оказывается сложнее описания табличного симплекс-метода. В основном это объясняется большей степенью неоднородности используемых структур. При выполнении одной итерации используется следующие широковещательные коммуникации между процессами: (1) log ₂ [ N "| широковещательных коммуникаций между процессами при нахождении столбцового ведущего процесса К ^с ; (2) широковещательная коммуникация для передачи вводимого в базис (ведущего) столбца ^ _/к1 и его номера, (3) log 2 [ N "| широковещательных коммуникаций между процессами при нахождении строкового ведущего процесса К ^г ; (4) широковещательная коммуникация для передачи ведущей строки (в (К )^-1^ и ее номера, (5) log 2 ^ N "| широковещательных коммуникаций между процессами для обмена двойственными субрешениями и нахождения двойственного решения.

В табл. 2 приведена сводка требуемого алгебраического вычи слительного ресурса для последовательной и параллельной реализаций метода обратной матрицы. Из таблицы и описания алгоритма видно, что процессоры загружены равномерно, а эффективность распараллеливания растет с ростом сложности задачи, достигая в пределе 100%.

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

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

В результате проведенного эксперимента можно сделать выводы о высокой эффективности распараллеленного алгоритма симплекс-метода. Однако, общее время вычислений может быть улучшено некоторыми оптимизациями реализации алгоритма, что является целью для дальнейшей работы.

Работа проводилась при финансовой поддержке РФФИ (проект 10-07-96003-р_урал_а)

Статья рекомендована к публикации программным комитетом международной научной конференции «Параллельные вычислительные технологии 2011».