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


              

Другое важное замечание: решение задачи


При этом граница 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 в найденной вершине:





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

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

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


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