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



              

Параллельный алгоритм решения - часть 2


AY = B,

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

 \begin{equation} \setcounter{MaxMatrixCols}{20} \begin{pmatrix} \colorbox[gray]{0.8}1 & \colorbox[gray]{0.8}1 &1 & 1 & \colorbox[gray]{0.8}0 & 0 & \colorbox[gray]{0.8}0 & 0 & 0 & \colorbox[gray]{0.8}0 & \colorbox[gray]{0.8}0 & 0\\ \colorbox[gray]{0.8}0 & \colorbox[gray]{0.8}0 &0 & 0 & \colorbox[gray]{0.8}1 & 1 & \colorbox[gray]{0.8}1 & 1 & 0 & \colorbox[gray]{0.8}0 & \colorbox[gray]{0.8}0 & 0\\ \colorbox[gray]{0.8}0 & \colorbox[gray]{0.8}0 &0 & 0 & \colorbox[gray]{0.8}0 & 0 & \colorbox[gray]{0.8}0 & 0 & 1 & \colorbox[gray]{0.8}1 & \colorbox[gray]{0.8}1 & 1\\ \colorbox[gray]{0.8}1 & \colorbox[gray]{0.8}0 &0 & 0 & \colorbox[gray]{0.8}1 & 0 & \colorbox[gray]{0.8}0 & 0 & 1 & \colorbox[gray]{0.8}0 & \colorbox[gray]{0.8}0 & 0\\ \colorbox[gray]{0.8}0 & \colorbox[gray]{0.8}1 &0 & 0 & \colorbox[gray]{0.8}0 & 1 & \colorbox[gray]{0.8}0 & 0 & 0 & \colorbox[gray]{0.8}1 & \colorbox[gray]{0.8}0 & 0\\ \colorbox[gray]{0.8}0 & \colorbox[gray]{0.8}0 &1 & 0 & \colorbox[gray]{0.8}0 & 0 & \colorbox[gray]{0.8}1 & 0 & 0 & \colorbox[gray]{0.8}0 & \colorbox[gray]{0.8}1 & 0\\ \end{pmatrix} \times \begin{pmatrix} y_{1}\\ y_{2}\\ y_{3}\\ y_{4}\\ y_{5}\\ y_{6}\\ y_{7}\\ y_{8}\\ y_{9}\\ y_{10}\\ y_{11}\\ y_{12}\\ \end{pmatrix} =\begin{pmatrix} 11\\ 11\\ 8\\ 5\\ 9\\ 9 \end{pmatrix} \end{equation}

(5.8)

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

  1. Положим l = 0.
  2. Положим l := l + 1, yl = 0. Исключим из матрицы A столбец, соответствующий этой переменной.
  3. Проверяем, появилась ли в A строка, содержащая только нулевые элементы, или обратилась ли в нуль левая часть исключенного уравнения. (Предполагаем, что все свободные члены уравнений больше нуля.) При положительном результате анализа выполняем шаг 5. В противном случае — следующий шаг.
  4. Для каждой s-й строки A выделяем множество {ys}переменных, соответствующих единичным элементам. Проверяем:
    \sum\limits_s {\bar y_s } \geqslant b_s ?
    При отрицательном результате анализа (свободный член превышает сумму верхних оценок переменных) выполняем шаг 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 приводит к появлению нулевой строки.




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