Параллельное решение задач НП при линейных ограничениях
Пусть решается задача
f(x1, ... ,xn)
при ограничениях
g1(x1, ... ,xn)
g2(x1, ... ,xn)
...
gm(x1, ... ,xn)
и при условиях: gi — линейны, xi
Предположим, что гиперплоскости gi, i = 1, ... ,m, возможно, совместно с координатными плоскостями, образуют в n-мерном пространстве выпуклый многогранник R допустимых решений, т.е. область задания функции f.
Определим, как и ранее, все вершины {X1, ... ,Xn}, Xl
=(x1(l) , ... ,xn(l) ), l = 1, ... ,N, этого многогранника в результате решения Cm + nn систем n линейных уравнений на основе всех заданных и возможных его граней
Тогда множество точек X = (x1,x2, ... ,xn) этого многогранника описывается как
а целевая функция на многограннике R становится функцией параметров f(x1, ... ,x_n) = f*(k1, ... ,k_{N-1}).
Т.е., задавая разные значения k1, k2, ... ,k_{N-1} так, чтобы выполнялось условие 0
мы можем организовать перебор всех точек R с некоторым шагом h по всем параметрам. Этим мы накладываем N-мерную "сетку" на многогранник R. В каждой точке-узле этой сетки мы будем находить значение функции f* и выберем максимальное. Шаг h должен быть выбран так, чтобы обеспечить необходимую точность решения задачи.
Распараллеливание возможно на двух этапах решения:
- Распределение систем линейных уравнений между процессорами для нахождения всех вершин многогранника допустимых решений. (Эквивалентно прямому перебору при решении задачи линейного программирования.)
- Распределение между процессорами узлов сетки — точек многогранника допустимых решений для нахождения и анализа в них значений целевой функции.
Метод допускает развитие и совершенствование.
Например, движение в сторону возрастания функции f может быть направленным, определяемым с помощью конечно-разностных значений частных производных по параметрам kl в точке текущего анализа
функции f. Это вариант так называемого градиентного метода. Эти же значения частных производных могут определять переменный шаг h.
Пример (рис. 6.1)
f(x,y)=x2+y
при ограничениях
-x-2y+12
-3x-y+21
и при условии 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.
