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



              

Общий алгоритм перебора


  1. На основе ограничений задачи q1
    b1, ... qm
    bm строим систему граней (гиперплоскостей) q1 = b1, ... qm = bm. Дополним эту систему граней всеми потенциальными гранями на основе условий: x1

    = 0, ... , xn = 0. Получим систему m+n линейных уравнений, в общем случае избыточную и, возможно, противоречивую.

  2. Выбираем из этой системы очередную подсистему n линейных уравнений (всего таких подсистем Cnm + n) и решаем ее.

    Как известно, система n линейных уравнений имеет единственное решение в том и только в том случае, если ранг r матрицы системы равен рангу расширенной матрицы системы и равен n.

    Можно в вычислительную процедуру включить анализ соответствующих матриц. Можно ограничиться анализом только определителя системы, его отличием от нуля, т.к. нас интересует лишь единственное решение. Однако ориентация на современные вычислительные средства и их операционные системы позволяет этого не делать.

    Дело в том, что любой метод решения системы линейных уравнений в случае неразрешимости системы или неоднозначности решения столкнется с операцией деления на нуль — т.е. возникнет прерывание. Этим целесообразно активно пользоваться для упрощения вычислительной процедуры.

    После обработки прерывания необходимо предусмотреть переход к решению следующей, очередной подсистемы линейных уравнений, если такие еще не исчерпаны.

    Однако традиционно при решении систем линейных уравнений в подобных задачах используют метод Гаусса как обобщение метода последовательного исключения. Метод Гаусса позволяет получать значения переменных последовательно. Значит, их контроль на отрицательность производится немедленно и останавливает дальнейший счет. Кроме того, попутные преобразования системы уравнений позволяют динамически выявить тот случай, когда матрица — алгебраическое дополнение диагонального элемента содержит нулевую строку, т.е. определитель системы равен нулю. Это также останавливает дальнейший анализ системы уравнений.

    Если же получено единственное решение и все его компоненты x1, ... , xn не отрицательны, то они могут определять вершину многогранника R.


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