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



              

Пример применения параллельной процедуры прямого перебора


Решим ту же задачу (2), подойдя формально, по правилу, пригодному для любой размерности пространства.

Исходная система уравнений действительных или потенциальных плоскостей — граней R имеет вид

 \begin{equation} \begin{aligned} \left. \begin{aligned} x_1 = 40\\ x_2 =30\\ x_1+x_2=50 \end{aligned}\right\}\text{m=3 уравнений}\\ \left.\begin{aligned} x_1=0\\ x_2=0 \end{aligned}\right\}\text{n=2 уравнений} \end{aligned} \end{equation}

(4.4)

Т.к. C23+2=10, исследование десяти комбинаций (подсистем уравнений) по два уравнения из (9.4) выглядит следующим образом.

  1.  \left\{ \begin{gathered} x_1 = 40 \\ x_2 = 30 \\ \end{gathered} \right.

    Подставляем это уже готовое решение в третье ограничение задачи, x1+ x2

    50, и отвергаем его, т.к. ограничение не выполняется.

  2. \left\{ \begin{aligned} {}& x_1 = 40 \\ {}& x_1 + x_2 = 50 \to x_1 = 40,\quad x_2 = 10. \end{aligned} \right.

    Решение удовлетворяет третьему ограничению x2

    30.

    Находим и запоминаем z(40, 10) = 130.

  3.  \left\{ \begin{gathered} x_1 = 40 \hfill \\ x_1 = 0 \hfill \\ \end{gathered} \right.

    Система не имеет решения.

  4.  \left\{ \begin{gathered} x_1 = 40 \hfill \\ x_2 = 0 \hfill \\ \end{gathered} \right.

    Решение удовлетворяет ограничениям

     \left\{ \begin{gathered} x_2 \leqslant 30 \hfill \\ x_1 + x_2 \leqslant 50. \hfill \\ \end{gathered} \right.

    Находим z(40, 0) = 80. Если мы решаем задачу не на параллельном компьютере, то сразу же видим, что новое значение z не превосходит уже найденное. Поэтому и это решение отвергаем.

  5.  \left\{ \begin{gathered} x_2 = 30 \hfill \\ x_1 + x_2 = 50. \hfill \\ \end{gathered} \right.

    Решение x1 = 20, x2 = 30 удовлетворяет и третьему "основному" ограничению задачи x1

    40. Находим z(20, 30) = 190. Запоминаем его вместе с решением, т.к. оно превосходит ранее полученное.

  6.  \left\{ \begin{gathered} x_2 = 30 \hfill \\ x_1 = 0. \hfill \\ \end{gathered} \right.

    Решение удовлетворяет всем ограничениям задачи. z(0, 30) = 150, что не превосходит уже найденное значение. Решение отвергаем.

  7. \left\{ \begin{gathered} x_2 = 30 \hfill \\ x_2 = 0. \hfill \\ \end{gathered} \right.

    Не имеет решения.

  8. \left\{ \begin{gathered} x_1 + x_2 = 50 \hfill \\ x_1 = 0. \hfill \\ \end{gathered} \right.

    Решение x1 = 0, x2 = 50 противоречит "основному" ограничению x2

    30. Отвергаем его.

  9.  \left\{ \begin{gathered} x_1 + x_2 = 50 \hfill \\ x_2 = 0. \hfill \\ \end{gathered} \right.

    Решение x1 = 50, x2 = 0 противоречит "основному" ограничению x1

    40. Отвергаем его.

  10.  \left\{ \begin{gathered} x_1 = 0 \hfill \\ x_2 = 0. \hfill \\ \end{gathered} \right.

    Решение не противоречит "основным" ограничениям задачи. Однако z(0, 0) = 0, что не превосходит уже найденное значение. (Кстати, оно обеспечивает решение задачи z

    min.)

Итак, x1 = 20, x2 =30 обеспечивает zmax =190, т.е. является решением задачи ЛП.




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