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



              

Пример


Рассмотрим задачу линейного программирования

Z = 26x + 20y + 21z

max (4.6)

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

q1 = 2x + 7y - 76z + 222

0

q2 = - 8x +9y - 8z + 64

0

q3 = - 8x + 13y -24z + 96

0 (4.7)

q4 = - x - 6y - z + 70

0

q5 = - 2x - 7y - 2z + 90

0

q6 = 33x + 3y +22z - 165

0

и при условии x

0, y
0, z

0.

Ограничения и условия образуют многогранник R(ABCDEFGHKL) допустимых решений, представленный на рис. 4.4.

Многогранник допустимых решений

Рис. 4.4.  Многогранник допустимых решений

Формально мы не знаем R, и множество граней — действительных и возможных — этого многогранника представлено системой уравнений:

q1 = 2x + 7y - 76z + 222 = 0

q2 = - 8x +9y - 8z + 64 = 0

q3 = - 8x + 13y -24z + 96 = 0

q4 = - x - 6y - z + 70 = 0

q5 = - 2x - 7y - 2z + 90 = 0 (4.8)

q6 = 33x + 3y +22z - 165 = 0

q7 = x = 0

q8 = y = 0

q9 = z = 0

В результате решения первой же подсистемы трех уравнений (n = 3) системы (4.8) получаем координаты вершины E многогранника R

 \begin{equation} \left\{ \begin{gathered} q_1 = 0 \hfill \\ q_2 = 0 \to E(13,8,4),\quad Z(E) = 592 \\ q_3 = 0 \hfill \\ \end{gathered} \right. \end{equation}

(4.9)

Постараемся "сместиться" в ту вершину, смежную вершине E, т.е. соединенную с ней ребром (в одну из вершин A, D, L, F), в которой целевая функция Z имеет максимальное значение, превышающее Z(E).

Ребра, исходящие из вершины, определяются подсистемами n-1 плоскостей, пересекающихся в этой вершине, т.е. образующими ее.

В данном случае подсистема

 \left\{ \begin{gathered} q_1 = 0 \hfill \\ q_2 = 0\quad \hfill \\ \end{gathered} \right.
определяет несуществующее ребро. Пока мы знаем это только по рисунку. Подсистема

 \left\{ \begin{gathered} q_1 = 0 \hfill \\ q_3 = 0 \hfill \\ \end{gathered} \right.

определяет ребро EA, подсистема

\left\{ \begin{gathered} q_2 = 0 \hfill \\ q_3 = 0 \hfill \\ \end{gathered} \right.

определяет ребро ED. А вот ребра EL и EF мы пока не знаем, т.к. не знаем (формально, а не по рисунку!) все плоскости (плоскость q5), пересекающиеся в E. Это значит, что из каждой вершины в общем случае исходят не менее n ребер, а сколько в действительности — предстоит уточнить. (Представьте себе R — бриллиант классической огранки.)

Значит, q1, q2, q3 — это лишь наше начальное представление о множестве плоскостей — граней, пересекающихся в вершине E. Нам необходимо развить это представление до полного.

Тогда выясним все множество граней, образующих вершину E, подстановкой ее координат во все другие уравнения (9.8) и испытанием на получение тождества.


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