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


           

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


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

f(x1, ... ,xn)

max

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

g1(x1, ... ,xn)

0

g2(x1, ... ,xn)

0

...

gm(x1, ... ,xn)

0

и при условиях: 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
kl
1,
. Или:

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

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

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

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

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

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

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

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

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



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





Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий