Параллельное решение задач НП при линейных ограничениях

Пусть решается задача

f(x1, ... ,xn)

max

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

g1(x1, ... ,xn)

g2(x1, ... ,xn)

...

gm(x1, ... ,xn)

и при условиях: gi — линейны, xi

0, i = 1, ... ,m.

Предположим, что гиперплоскости gi, i = 1, ... ,m, возможно, совместно с координатными плоскостями, образуют в n-мерном пространстве выпуклый многогранник R допустимых решений, т.е. область задания функции f.

Определим, как и ранее, все вершины {X1, ... ,Xn}, Xl

=(x1(l) , ... ,xn(l) ), l = 1, ... ,N, этого многогранника в результате решения Cm + nn систем n линейных уравнений на основе всех заданных и возможных его граней

Тогда множество точек X = (x1,x2, ... ,xn) этого многогранника описывается как

, где 0

. Или:

а целевая функция на многограннике R становится функцией параметров f(x1, ... ,x_n) = f*(k1, ... ,k_{N-1}).

Т.е., задавая разные значения k1, k2, ... ,k_{N-1} так, чтобы выполнялось условие 0

1, так же как и для

мы можем организовать перебор всех точек R с некоторым шагом h по всем параметрам. Этим мы накладываем N-мерную "сетку" на многогранник R. В каждой точке-узле этой сетки мы будем находить значение функции f* и выберем максимальное. Шаг h должен быть выбран так, чтобы обеспечить необходимую точность решения задачи.

Распараллеливание возможно на двух этапах решения:

Распределение систем линейных уравнений между процессорами для нахождения всех вершин многогранника допустимых решений. (Эквивалентно прямому перебору при решении задачи линейного программирования.)
Распределение между процессорами узлов сетки — точек многогранника допустимых решений для нахождения и анализа в них значений целевой функции.

Метод допускает развитие и совершенствование.

Например, движение в сторону возрастания функции f может быть направленным, определяемым с помощью конечно-разностных значений частных производных по параметрам kl в точке текущего анализа

функции f. Это вариант так называемого градиентного метода. Эти же значения частных производных могут определять переменный шаг h.

Пример (рис. 6.1)

f(x,y)=x2+y

max

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

-x-2y+12

0

-3x-y+21

0

и при условии x,y

Рис. 6.1. Нелинейная задача с линейными ограничениями

Решая попарно уравнения границ, находим

Xl=(0,0), X2=(0,6), X3=(6,3), X4=(7,0).

Уравнение многогранника R:

Пусть h — шаг изменения каждого ki для получения испытываемой точки X многогранника R. Будем перебирать точки

k1 = 0, k2 = 0, k3 = 0 (тем самым k4 = 1);

k1 = h, k2 = 0, k3 = 0 (k4 = 1-h);

k1 = h, k2 = h, k3 = 0 (k4 = 1-2h);

k1 = h, k2 = h, k3 = h (k4 = 1-3h);

k1 = 2h, k2 = h, k3 = h (k4 = 1-4h);

...

Однако нам надо следить, чтобы величина k4 = 1 - k1 - k2 - k3

оставалась неотрицательной.

Выполнив такой перебор, например, для h = 0,1, получим max f(x,y) = f*(k1 = 0, k2 = 0, k3 = 0, k4 = 1) = f(7,0) = 49.