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


              

Основные предположения


Определение. Назовем плоскость в n-мерном пространстве образующей вершины A выпуклого многогранника R допустимых решений задачи ЛП, если ее уравнение входит в состав системы n линейных уравнений границ многогранника R, решением которой является точка A.

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

Изменим обозначение плоскостей-граней, образующих исследуемую далее верхнюю (нижнюю) поверхность многогранника R:

Qверхн (Qнижн) ={p1, p2,... , pr, pr+1, ... ,pr+n}. (6.7)

Здесь

, j = 1, ... , r, — действительные плоскости грани, pr+k = qm+k, k = 1, ... , n, — координатные плоскости.

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

p1 = d11 x1 + d12 x2 +... + d1n xn = 0

p2 = d21 x1 + d22 x2 +... + d2n xn = 0

...

pr = dr1 x1 + dr2 x2 +... + dr n xn = 0 (6.8)

pr+1 = x1 = 0

...

pr+n = xn = 0.

Найдем координаты единичных векторов нормалей Nj, j = 1,... , n+r, к плоскостям (6.8):

(6.9)

где

(6.10)

Тогда косинус угла между нормалями к двум граням верхней (нижней) поверхности R вычисляется как результат скалярного произведения единичных векторов нормалей:

(6.11)

Выскажем гипотезу, которая является основой теоремы существования:

Если плоскости pj и pq совместно не являются образующими какой-либо вершины верхней (нижней) поверхности выпуклого многогранника R допустимых решений задачи ЛП, а их нормали Nj и Nq образуют "угол"

, то существует плоскость pl с нормалью Nl, совместно с pj являющаяся образующей некоторой вершины этой же поверхности и такая, что "угол" ? между нормалями Nj и Nl меньше угла
. (? <
).

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

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

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