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


              

единичная матрица, Y— столбец переменных,


AY = B,

где A— нуль- единичная матрица, Y— столбец переменных, B— столбец свободных членов:


(5.8)


Тогда для нахождения хотя бы одного допустимого решения выберем допустимую комбинацию нулей по следующему алгоритму:

  1. Положим l = 0.
  2. Положим l := l + 1, yl = 0. Исключим из матрицы A столбец, соответствующий этой переменной.
  3. Проверяем, появилась ли в A строка, содержащая только нулевые элементы, или обратилась ли в нуль левая часть исключенного уравнения. (Предполагаем, что все свободные члены уравнений больше нуля.) При положительном результате анализа выполняем шаг 5. В противном случае — следующий шаг.
  4. Для каждой s-й строки A выделяем множество {ys}переменных, соответствующих единичным элементам. Проверяем:
    При отрицательном результате анализа (свободный член превышает сумму верхних оценок переменных) выполняем шаг 5. В случае успешной проверки 3 и 4 выполняем шаг 6.
  5. Данный шаг выполняется, если испытываемое значение yl = 0 выбрано неудачно. Отменяем исключение столбца, соответствующего переменной yl, и выполняем шаг 2.
  6. Фиксируем yl = 0, и если комбинация нулей сформирована не полностью, выполняем шаг 2.


Продолжим рассмотрение примера.

Полагаем y1 = 0. Это не приводит к нарушению оценок, указанных в алгоритме.

Полагаем y2 = 0. Это также не приводит к нарушению оценок.

Полагаем y3 = 0. Нулевые строки не появились. Однако в первой строке осталась единственная единица, соответствующая переменной y4. Т.к. y4= 7 < 11, отвергаем нулевое значение переменной.

Полагаем y4 = 0. Нулевые строки не появились, однако в первой же строке осталась единственная единица, соответствующая переменной y3. Т.к. y3 = 9 < 11, отвергаем и это значение.

Полагаем y5 = 0. Это не приводит к нарушению оценок.

Полагаем y6 = 0. В пятой строке остается единственная единица, соответствующая y10. Т.к. y10 = 8 < 9, отвергаем нулевое значение переменной.

Полагаем y7 = 0, что не приводит к нарушению оценок.

Значение y8 = 0 приводит к нарушению оценки во втором уравнении.

Значение y9 = 0 приводит к появлению нулевой строки.


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