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



              

Графический метод решения и его обобщение - часть 2


При этом граница x2 = 0 внизу осталась бы.

  • Другое важное замечание: решение задачи мы нашли на границе многогранника R.
  • При этом возможны варианты:

    1. Единственному конечному решению соответствует вершина R, как в нашем примере.
    2. Решением может являться бесконечное множество точек на грани R, например, если бы ограничение q3 определяло бы прямую, параллельную z (уравнения q3 и z были бы линейно зависимыми).
    3. Система ограничений может определять "открытый" многогранник R, включающий бесконечно удаленные точки, в которых достигается max z, т.е. max z = ?. Например, та же задача ЛП могла быть поставлена при отсутствии ограничений q2 и q3 (

      рис. 4.2). Перемещение z в сторону ее увеличения может быть бесконечным, т.е. max z = ?. Но если бы была поставлена задача z

      min, то она бы при этих ограничениях имела конечное и единственное решение, в данном случае x1=x2=0.

    Случай отсутствия решения

    Рис. 4.2.  Случай отсутствия решения

    Значит, имеет значение, с какой стороны многогранник R открыт: либо он позволяет поиск решения вдоль "закрытых" стенок, либо допускает возможность "выпасть" за его пределы, искать решение в бесконечности.

    Тогда, как бы мы могли искать решение нашей первоначально поставленной задачи ЛП?

    Учитывая, что решение задачи — в одной из вершин R, мы сначала выпишем уравнения всех прямых, ограничивающих R, т.е. уравнения всех его границ:

    x1 = 40

    x2 = 30

    x1 + x2 = 50

    x1 = 0

    x2 = 0

    Для нахождения координат каждой вершины R решаем совместно пару уравнений прямых, образующих эту вершину, и находим значение z в найденной вершине:

     \begin{gathered} \left\{ \begin{gathered} x_1 = 0 \hfill \\ x_2 = 0\quad \to \quad z = 0 \hfill \\ \end{gathered} \right. \hfill \\ \left\{ \begin{gathered} x_1 = 0 \hfill \\ x_2 = 30\quad \to \quad z = 150 \hfill \\ \end{gathered} \right. \hfill\\ \left\{ \begin{gathered} x_2 = 30 \hfill \\ x_1 + x_2 = 50\quad \to \quad z(20,\;30) = 190 \hfill \\ \end{gathered} \right. \hfill \\ \end{gathered}

     \begin{gathered} \left\{ \begin{gathered} x_1 = 40 \hfill \\ x_1 + x_2 = 50\quad \to \quad z(40,\;10) = 130 \hfill \\ \end{gathered} \right. \hfill \\ \left\{ \begin{gathered} x_1 = 40 \hfill \\ x_2 = 0\quad \;\quad \to \quad z = 80 \hfill \\ \end{gathered} \right. \hfill \\ \end{gathered} \vspace{-1mm}

    Действительно, max z = 190 достигается в точке A.

    Отметим возможноcть распараллеливания решения задачи на многопроцессорной ВС, точнее, ВС SPMD-технологии.

    В трехмерном пространстве ограничения и условия образуют пространственный многогранник R, охваченный плоскостями-границами, записанными на основе ограничений и условий, где неравенства заменены равенствами, а каждая плоскость z = const, среди которых мы ищем решение, пересекает, "прорезает" его, деля на две части (




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