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



              

Алгоритм. Пример


Выше фактически уже описан алгоритм нахождения хотя бы одной вершины многогранника допустимых решений. Сведем вместе все необходимые построения.

Алгоритм.

  1. Определим направление возрастания целевой функции и выделим грани многогранника допустимых решений, образующие верхнюю (нижнюю) его поверхность. Дополним ее возможными гранями — координатными плоскостями.
  2. Составим матрицу S косинусов углов между всеми нормалями к действительным и возможным граням сформированной поверхности многогранника допустимых решений.
  3. Если число r действительных граней верхней (нижней) поверхности не меньше n — размерности задачи, выполняем первый этап алгоритма, исключив из рассмотрения строки и столбцы матрицы S, соответствующие координатным плоскостям.
  4. Этот пункт является общим для первого и второго этапов. Выбрав произвольно грань или организовав перебор всех граней, или организовав параллельный анализ всех граней, выберем в соответствующей этой грани строке матрицы S n максимальных косинусов. В этой последовательности косинусов, кроме максимального косинуса угла между нормалью выбранной грани и ею же самой, не должно быть косинусов, равных 1 или -1. Таким образом, окажутся выделенными n возможных образующих некоторой вершины многогранника допустимых решений.
  5. Решаем совместно уравнения выделенных граней.
  6. Если решение существует и оно неотрицательно, произведем анализ: удовлетворяет ли найденная точка всем ограничениям задачи? Если удовлетворяет, точка действительно является вершиной многогранника. В противном случае необходимо продолжить анализ граней, то есть строк матрицы S.
  7. Если перебор всех строк матрицы S не привел к успеху на первом этапе выполнения алгоритма, переходим ко второму этапу, введя в рассмотрение координатные плоскости, т.е. начинаем анализ матрицы в полном объеме. Если успех не был достигнут на втором этапе, то, как указано ниже, можно испытать удачу на другой — нижней (верхней) поверхности многогранника допустимых решений. Ведь важно найти хоть какую-то вершину, пусть не столь близкую к вершине-решению.


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