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

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


Рассмотрим пример

z=c1x1+c2x2=2x1+5x2

max    (4.1)

при ограничениях

q1=x1

40

q2=x2

30

q3=x1+x2

50

и условиях x1

0, x2
0.

Каждое ограничение в двухмерном пространстве, n=2, определяет полуплоскость. Их пересечение образует многоугольник R (рис. 4.1). Его грани — прямые, получены на основе ограничений, в которых неравенства заменены равенствами.

q1 = 40

q2 = 30 (4.2)

q3 = 50

Эти равенства образуют уравнения границ или просто границы R.


Рис. 4.1.  Графический метод решения задачи линейного программирования

Этот многоугольник (выпуклый многогранник; выпуклый, — ибо он остается по одну сторону от любой прямой, проходящей через его ребро) представляет собой допустимое множество решений R задачи ЛП.

Выберем произвольное значение, например, z=100 целевой функции. Прямая 2x1+5x2=100 показана на рисунке. Она пересекает ось x1 в точке x1=50 и ось x2 в точке x2=20.

Отметим, что для

.

Т.к. dx1 и dx2 принадлежат прямой z, то скалярное произведение двух векторов, которое здесь изображено, равно нулю в том случае, если вектор (c1, c2) =(2, 5) перпендикулярен прямой z.

Увеличиваем значение z, передвигая (с помощью линейки) прямую — целевую — функцию параллельно самой себе в сторону ее возрастания вдоль вектора (2, 5) до тех пор, пока линейка не коснется последней возможной точки многогранника. R. Это значение z и будет максимальным. В данном случае — это точка A = (x1=20, x2=30).

Сделаем важное замечание относительно многогранника R.

  1. То, что он выпуклый, мы заметили ранее.
  2. Нам были заданы три ограничения, отсекающие полуплоскости, но определившие не все границы многогранника R. С "не закрытой" ими стороны область R оказалась закрытой условиями неотрицательного решения задачи: x1

    0, x2
    0. Значит, эти выражения пришлось из ранга условий перевести в ранг ограничений.

    При этом не все условия могут быть переведены в ограничения. В нашей задаче могло существовать некоторое ограничение q4 (на рисунке пунктиром), которое бы определяло границу R слева, исключая границу x1 = 0.
    При этом граница x2 = 0 внизу осталась бы.

  3. Другое важное замечание: решение задачи мы нашли на границе многогранника 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, среди которых мы ищем решение, пересекает, "прорезает" его, деля на две части (



рис. 4.3
).


Рис. 4.3.  Задача линейного программирования в трёхмерной области

На рисунке иллюстрируется задача ЛП:

z=c1x1+c2x2+c3x3
max

при ограничениях

q1=a11x1+a12x2+a13x3
b1

q2=a21x1+a22x2+a23x3
b2

и при условии

x1
0, x2
0, x3
0.

Две грани q1=b1 и q2=b2, ограничивают многогранник R — область возможных значений переменных сверху (спереди) и справа. Слева, внизу и сзади пространственный многогранник R ограничен условиями неотрицательности решения, ставшими ограничениями x1 = 0, x2 = 0, x3 = 0. Плоскость z=const пересекает многогранник R. Перемещая плоскость z параллельно себе, т.е. вдоль вектора (c1, c2, c3), в сторону возрастания значений линейной формы z, мы находим решение. Здесь наглядно показана очевидность того, что решение следует искать в вершинах R.

Однако графическое представление уже в трехмерном пространстве затруднительно, в n-мерном пространстве нам необходимо действовать формально. Здесь существует ряд проблем.

Во-первых, мы не представляем пространственной картины и не знаем, охватывают ли заданные ограничения область R со всех сторон и какими условиями эти ограничения должны быть дополнены без противоречий.

Во-вторых, мы не знаем, какие n ограничений, дополненных условиями, соответствуют каждой конкретной вершине многогранника R, чтобы найти координаты этой вершины и найти в ней значение целевой функции z. Значит, мы должны испытать все возможные комбинации по n (в данном случае — тройки) ограничений и условий, т.е. все возможные комбинации по три, составленные на основе всех потенциальных границ- ограничений и условий.

Тогда при построении (параллельной!) вычислительной процедуры мы должны опираться на то, что любая противоречивость в системе ограничений (в их состав мы включили теперь и условия) выразится в неразрешимости системы трех уравнений, составленной для нахождения координат очередной испытываемой вершины R. Т.е. в этом случае вершина находится в бесконечности или содержит отрицательные значения координат. Эта неразрешимость находится в процессе счета.



Оставаясь в области практических решений задач ЛП, т.е. в области инженерии и экономики, примем предположение, что задача сформулирована корректно. Под этим будем предполагать, что ограничения выбраны так, что она не имеет неограниченного решения z = ?.

Например, ставя задачу о максимизации прибыли от перевозки, не надо забывать о том, что объем перевозок ограничен ресурсами страны, сообщества и т.д. В противном случае мы получим тривиальное решение: чем больше, тем лучше.

Значит, мы будем предполагать, что в многограннике R обязательно есть вершины (их координаты не отрицательны), в целом ограничивающие области изменения переменных, и хотя бы в одной из этих вершин целевая функция — линейная форма z принимает максимальное значение.

В свете сказанного будем также считать, что ограничения не противоречивы. Противоречивые ограничения приводят к случаю R =
.

Например, ограничения

x + y
5

x + y
2

противоречивы.

Тогда, развивая на n-мерное пространство, мы можем реализовать следующую стратегию поиска решения задачи ЛП.


Содержание раздела