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


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


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

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

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

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

Здесь

p_j = q_{i_j }
, 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):

 \begin{equation} Nj = \left( {\frac{{d_{j1} }}{{s_j }},\frac{{d_{j2} }} {{s_j }},\quad ...,\quad \frac{{d_{jn} }}{{s_j }}} \right), \notag \endequation}

(6.9)

где

 \begin{equation} s_j = \sqrt {d_{j1}^2 + d_{j2}^2 + ... + d_{jn}^2 } . \end{equation}

(6.10)

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

 \begin{equation} \cos(N_j,N_l) = \frac{1}{{s_j s_l }}(d_{j1} d_{l1} + \ldots+ d_{jn} d_{ln}). \end{equation}

(6.11)

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

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

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

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

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


Начало  Назад  Вперед



Книжный магазин