Исследование процессов сборки самолета по функции

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

Условие несмежности одновременно стягиваемых дуг соответствует тому, что в данной задаче сборки каждый узел может одновременно соединяться не более чем с одной дугой узла. Здесь не будем учитывать другие технологические и ресурсные ограничения, накладываемые на последовательность выполнения операций сборки.

Итак, пусть необходимо собрать за минимальное время часть фермы (рис. 1), состоящую из четырех продольных балок, четырех распорок и одной корневой детали (основные фермы).

Распорка 5 соединена с балками 1 и 2, распорка 6 – с балками 2 и 3, распорка 7 – с балками 3 и 4, распорка 8 – с балками 4 и 1. Корневая деталь (узел) 9 соединяется со всеми балками. Граф сопряжения такого изделия изображен на рис. 1. Предположим, что все соединения осуществляются за время t . Логичной является симметричная последовательность сборки, при которой на первом шаге каждая балка соединя-

Рис. 1. Схема собираемой фермы

Рис. 2. Схема стягивания дуг графа собираемой фермы (вариант 1)

ется с распоркой; далее полученные узлы соединяются между собой и с основанием (рис. 2).

Общее время сборки равно восьми единицам. Однако если рассмотреть другие варианты сборки, то можно найти последовательность, изображенную на рис. 3., при которой общее время сборки равно лишь семи единицам.

Для указанных условий ограничений определим последовательность стягивания дуг, стягивающих граф G в точку за наименьшее время.

Пусть здесь T ( G ) - наименьшее время стягивания графа G . Тогда для задачи стягивания графа G необходимо определить время стягивания дуг:

T ( G ) = t , + T ( Г , ) (1) где j - индекс дуги, стягиваемой последней;

r j - граф, получаемый из графа G удалением дуги U j .

Дугу U j , стягиваемую последней, назовем срединой графа G . Индекс средины обозначим Ф( G ). Граф может иметь несколько средин, как это показано, например, на рис. 4.

Здесь серединами будут дуги U 2 и U 4 . Если средин несколько, то ф( G ) - произвольный, но фиксированный индекс одной из средин. Совершенно очевидно, что граф r j не всегда связанный.

Из выражения (1) следует, что для определения T ( G ) достаточно знать T ( r j ) для всех r j с G с числом дуг на единицу меньше, чем в G . Следовательно, задача стягивания графа G сводится к задаче построения линейного порядка подграфов r j графа G , согласованного с их частичным порядком по включению. Тогда, если известны T (Г) для всех Г’ < Г, то T ( r j ) находится с использованием принципа оптимальности Беллмана.

Ниже рассмотрим подробную реализацию предложенной схемы для задачи стягивания дерева.

Пусть z₀, z 1 , ..., z m - висячие вершины дерева графа ( G ). Пусть L - расстояния между вершинами x и у обозначим L ( x , у ), а число дуг пути (расстояния) L обозначим через модуль | L| . Будем считать, что L ( x , у ) = j. Обозначим через L_K = L ( z₀, z_K ) путь, соединяющий вершины z₀ и z_K (1 <  К <  m ), а через

Рис. 3. Схема стягивания дуг графа собираемой фермы (вариант 2)

Рис. 4. Линейный граф, имеющий две середины (дуги U₂ и U 4 )

L_K = L ( x_K, z_K ) - часть пути (расстояния) L_K, не пере

секающуюся с путями с меньшими индексами:

~

LK

L K ^П U ^Lr

~

LK

Очевидно, что

I ^ь£2 ⁼ °,

к -к,,                   (2)

Индукцией по m устанавливается, что каждая вершина x дерева G , отличная от висячей, лежит внутри равенства одного пути L p . Так как вершины x K отличны от висячих, то для всех К > 1 существует единственное w ( К ) - такое, что x_K е L ® ( K ) при [ 1 £ w(K) < К ].

Пусть задано:

rK = ILxK, zk ),

Обратно, каждому элементу Г дерева графа G соответствует единственный допустимый набор. Чтобы убедиться в этом, достаточно проверить, что непустые пересечения L p П Г , кроме первого, содержат вершину x_p . Для этого рассмотрим разложение дерева G на два непересекаю-щихся элемента дерева графа G = M 1 U M 2 , где

M 1 = U LS’ при t =1, 2,•■;

® ^{( t} > p

M 2 = U L S , Для некоторого t₀ .

^{ш ( t} o ) = p

Очевидно, что если Г П L_p = Ф и х_р е Г П L_p , то Г с M₂ . Следовательно, Г П L_T = Ф ( r <  p ) , что собственно необходимо было вычислить и доказать.

Множество допустимых наборов и множество элементов графа G необходимо упорядочить с использованием лексикографических правил. Здесь будем считать, что

(^ 1 , ¹ 2 ^,...^, i m + 1 ⁾<¹^ , ¹ ,..., i m + 1 ) ,

t K = I Lx ( K ) , x K

Набор ( i 1 , i 2 , ..., i_m+1 ) целых чисел назовем допустимым при условиях:

m

• 1 .E K > im+1

• 2 . iK = 0, K< Ko, 1 < Ko < m,0 < i < r о < /

K = 1

;

K o     K o ^o< ⁷ K <  r K ,

,

^если i m + 1 = i m + 1

или i m = i m ,..., i m-l + X = ‘ m-l + X ' i m-l <  ‘ m-l при O <  К m.

Соответственно

Г = Ф (,;, i„..„im+, )< Г= Ф (i\, I',..., im+i )

m

Ki o < K < m, io > im+1 - E tK > o ;

K = K _o + 1

Пусть Г = Ф ( i ₁, i₂,...,i m _{+ 1} ) - элемент дерева G . Построим дерево Г i = Ф ( j i , j ₂,..., j_m + i ) , непосредственно следующее за Г . Для этого следует использовать процедуру минимизации. Пусть l_o = min ( S / i_S <  r_S ) . Полагаем j_s = i S ( l o <  S < m + 1 ) , j\ = i l _o ^{+ 1} . Следует считать, что

i ® ( K ) ет i K o

для

m(k) > Ko из

> tK, для ®(k)= Ko > tK > E (1K - im+1 )

1_K >  O следует из 1_K >  O следу, для ® ( K ) <  K _o

m

E j K < j m + 1 .

K = l o

всегда i_K = O .

Каждый допустимый набор ( i 1 , i₂, ..., i_m+1 ) соответствует единственному элементу графа G

Г = Ф(ip i2,..., im+1 )

Пусть l1 = max[®(s)/ ®(l)< lo ].Полагаем,что jS= o (l1 < s< lo); j\ = maxctt / ®(l)=l1; jl> o).

Проверим выполнение неравенства (3) для l _o = l ‘ . Если оно выполнено, то процедуру построения повторяем.

В процессе построения с использованием лексикографических правил возможны следую-

такому, что выполняются условия i K = I L K ^{П Г} | ^,

щие случаи:

Для некоторого r >  O l_r = 1 и C = j_m1 - £ j _K >  O

K >  K o ;

^LK _o ^{П Г} = L ⁽ x K _o , y K _o i K o = | L ⁽ x K o ^, y K o ) ^;

получаем

jQ = j‘ + mi™ rQ

SS    S

при 1 < S < m.

(      S-1

jS, C-E(jK

V      k = 1

-

m

E

K = K o

LK П Г = i

m + 1 .

m

Для некоторого r > O C = j‘№1 - E jK < O

K - l r

проверим выполнение условий:

min t >  C ;             (4)

® ( K^K

K > 0(K > lr )^ ®(K)> lr.      (5)

Здесь, полагаем, что

Js = 0,1 <  Sl r ; j_s = j S , l r <  S <  m + 1 .

Если одно из условий (4), (5) не выполнено, то полагаем 1 0 = min ( S / i_s <  r_s ; S > 1 0 ) , тогда проводим построение набора ( j 1 ,j₂,..., j m + 1 ) сначала.

Если в процессе построения получится 1 ₀ = m + 1 , то принимаем версию:

f          s -i 1

j m + l = i m + 1 или j s = min ) j m + 1 ^- L ^jK Г , где 1 <  S < m .                  ^       ^K = 1

Построенныйдопустимыйнабор ( j 1 , j₂,..., j m, ) непосредственно следует за набором (/, , i ₂,..., i m + 1 ), а дерево Г = Ф ( j ₁, j₂,..., j m _{+ 1} ) непосредственно следует за деревом Г = Ф ( i ₁, i ₂,..., i_{m + 1} ) .

Совершенно очевидно, что полученный линейный порядок элементов дерева G согласован с их частичным порядком по включению.