Параллельное программирование
508 Resource Limit Is Reached

Resource Limit Is Reached

The website is temporarily unable to service your request as it exceeded resource limit. Please try again later.

область возможных значений переменных сверху


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


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

508 Resource Limit Is Reached

Resource Limit Is Reached

The website is temporarily unable to service your request as it exceeded resource limit. Please try again later.