Параллельное программирование



              

Параллельный алгоритм решения


Исследование плана параллельного решения и формирование алгоритма будем сопровождать примером, для проверки правильности заимствованным в [15]. Для краткости условия (5.3) и (5.4) опущены.

Пример.

Z=7x11+8x12+5x13+3x14+2x21+4x22+5x23+ +9x24+6x31+3x32+1x33+2x34

min (5.5)

при ограничениях

x11 + x12 + x13 + x14 = 11

x21 + x22 + x23 + x24 = 11

x31 + x32 + x33 + x34 = 8

x11 + x21 + x31 = 5 (5.6)

x12 + x22 + x32 = 9

x13 + x23 + x33 = 9

x14 + x24 + x34 = 7

Введем линейный массив переменных xij = yk, где k = (i - 1)n + j.

Исключим из рассмотрения последнее уравнение. Система уравнений граней (действительных и возможных) многогранника решений примет вид

y1 + y2 + y3 + y4 = 11

y5 + y6 + y7 + y8 = 11

y9 + y10 + y11 + y12 = 8 (5.7)

y1+y5+ y9=5

y2+y6+y10 = 9

y3+ y7+ y11 = 9

yk = 0, k = 1, 2, ... , 12.

Итак, на первом этапе задача свелась к выбору и анализу комбинаций по 12 - 6 = 6нулевых значений координат искомой вершины многогранника решений. Выполняя подстановку выбранной комбинации в (5.7), мы можем решить образовавшуюся систему шести уравнений с шестью неизвестными. Таким образом, мы сможем найти координаты некоторой вершины.

Комбинации по шесть нулевых значений координат ("комбинации нулей") следует выбирать так, чтобы не обратилась в нуль левая часть хотя бы одного уравнения (5.7), включая исключенное уравнение. Например, комбинация, где y1 = y2 = y3 = y4 = 0, недопустима.

Найдем дополнительные контрольные ограничения: чтобы решение было не отрицательным, необходимо, чтобы любое значение yk, k = 1, ... , m ? n, не превышало значение yk — величины правой части того уравнения, в котором оно участвует.

Тогда в нашем примере y1

min(11, 5) =y1 = 5, аналогично y2
y2 = 9, y3
y3 = 9, y4
y4 = 7, y5
y5 = 5, y6
y6 = 9, y7
y7 = 9, y8
y8 =7, y9
y9 = 5, y10
y10 = 8, y11
y11 = 8, y12

y12 = 7. Здесь при оценке y4, y8, y12учтено последнее уравнение в (5.6).

Воспользуемся векторной формой представления, чтобы подготовить удобные, нетрудоемкие матричные преобразования. А именно, наша система m + n - 1линейных уравнений-ограничений имеет вид




Содержание  Назад  Вперед