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



              

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


Продолжаем перебор по следующему ребру.

Замена y3 = 0 вместо y9 = 0 приводит к образованию нулевой (шестой) строки матрицы A.

Замена y4 = 0 вместо y9 = 0 приводит к тому, что в первом уравнении (5.15) не выполняется условие по ограничению y3 (y3 = 9).

Замена y5 = 0 вместо y9 = 0 приводит к тому, что во втором уравнении (5.15) не выполняется условие по ограничению y6 (y6= 9).

Замена y6 = 0 вместо y9 = 0 приводит к тому, что во втором же уравнении (5.15) не выполняется условие по ограничению y5 (y5 = 5).

Замена y10 = 0 вместо y9 = 0 приводит к системе

 \begin{equation} \begin{pmatrix} 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ \end{pmatrix} \times \begin{pmatrix} y_3\\y_4\\y_5\\y_6\\y_{9}\\y_{12} \end{pmatrix} = \begin{pmatrix} 11\\11\\8\\5\\9\\9 \end{pmatrix} \end{equation}

Ее решение Y1 = (0, 0, 9, 2, 2, 9, 0, 0, 3, 0, 0, 5) определяет значение Z(Y1) = 119 > 104.

Приступаем к анализу следующего ребра, исключая в (5.14) уравнение y11 = 0 и заменяя его последовательно уравнениями из (5.16).

Замена y3 = 0 вместо y11 = 0 приводит к тому, что в первом уравнении (5.15) не выполняется условие по ограничению y4 (y4 = 7).

Замена y4 = 0 вместо y11 = 0 приводит к тому, что в первом уравнении (5.15) не выполняется условие по ограничению y3 (y3 = 9).

Замена y5 = 0 вместо y11 = 0 приводит к тому, что во втором уравнении (5.15) не выполняется условие по ограничению y6 (y6 = 9).

Замена y6 = 0 вместо y11 = 0 приводит к тому, что во втором же уравнении (5.15) не выполняется условие по ограничению y5 (y5 = 5).

Замена y10 = 0 вместо y11 = 0 приводит к системе

 \begin{equation} \begin{pmatrix} 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 0 \\ \end{pmatrix} \times \begin{pmatrix} y_3\\y_4\\y_5\\y_6\\y_{11}\\y_{12} \end{pmatrix} = \begin{pmatrix} 11\\11\\8\\5\\9\\9 \end{pmatrix} \end{equation}

(5.17)

Система не имеет решения, т.к. ранг матрицы системы не равен рангу расширенной матрицы.

Примечание. В несложном примере это легко обнаружить: вторая строка матрицы равна сумме четвертой и пятой строк, что противоречит соотношению между соответствующими свободными членами, 9 + 5

11. По-видимому, это говорит в пользу применения схемы Гаусса. В противном случае мы должны контролировать последовательно получаемые решения на удовлетворение тем соотношениям, которые в его получении не участвовали. Так, из четвертого и пятого уравнений имеем y5 = 5, y6 = 9. Но в соответствии со вторым уравнением y5 + y6 = 11. В то же время, совершая подстановку во второе уравнение, мы получаем нулевую левую часть, т.е.


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