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



              

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


рис. 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. Т.е. в этом случае вершина находится в бесконечности или содержит отрицательные значения координат. Эта неразрешимость находится в процессе счета.




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