Обобщенная модель курьера с дополнительными ограничениями

Рассматривается математическая модель процесса последовательного обхода, мегаполисов с условиями предшествования (обобщенная задача, курьера), в которой как функции стоимости, так и ограничения на текущие перемещения зависят от списка заданий, не выполненных на текущий момент, или, напротив, — от списка уже выполненных заданий.

Данная особенность возникает в целом ряде инженерных задач, из которых сейчас отметим только одну, а. именно: задачу управления инструментом при листовой резке деталей на машинах с ЧПУ. Помимо большого числа условий предшествования, возникающих из технологических ограничений, связанных с более ранней резкой внутренних контуров (и « внутренних » деталей) в сравнении с внешним для каждой детали, имеются другие условия. Сейчас отметим требование к обеспечению жесткости листа. Последнее означает, что новые точки врезки должны всякий раз отстоять на достаточном расстоянии от « пустот » , образовавшихся за счет уже вырезанных деталей, что требует от процедуры управления использования информационной памяти.

В статье рассматривается постановка, позволяющая учесть упомянутое обстоятельство, связанное с использованием памяти, и распространяющаяся вместе с тем на другие прикладные задачи (так, например, предлагаемая схема, может быть применена. с целью учета, естественных ограничений в задаче о демонтаже энергоблока АЭС, выведенного из эксплуатации). Важно отметить, что предлагаемая конструкция на основе динамического программирования (ДП), учитывающая зависимость от списка (выполненных, либо, напротив, не выполненных) заданий, реализуется в пределах тех же возможностей в части вычислений, что и ранее применяемые ее аналоги в постановках, где указанная зависимость отсутствовала. Упомянутая конструкция излагается в статье в виде алгоритма на функциональном уровне; данный алгоритм был реализован на ПЭВМ, в статье приведено описание вычислительного эксперимента для модельного примера задачи, связанной с листовой резкой на машинах с ЧПУ.

Исследуемая в работе задача имеет своим прототипом известную труднорешаемую задачу коммивояжера (ЗК); см., в частности, [1-4]. В связи с применением ДП для решения ЗК отметим работы [5,6]. Рассматриваемый в статье вариант маршрутной задачи существенно отличается от ЗК как в части задания функций стоимости (допускается зависимость от списка заданий), так и в части используемых ограничений, что мотивировано потребностями прикладных задач. В связи с вышеупомянутой задачей управления инструментом при листовой резке на машинах с ЧПУ отметим работы [7-10], а в связи с машрутизацией в задачах атомной энергетики см., в частности, монографию [11].

1. Обозначения и определения общего характера

В дальнейшем используется стандартная теоретико-множественная символика: кванторы, связки: = — равенство по определению, def заменяе'т фразу « по определению », 0 — пустое множество. Семейством называем множество, все элементы которого — множества; в дальнейшем, как правило, рассматриваются семейства подмножеств (п/м) того или иного наперед заданного множества. В этой связи следуем соглашениям: если H — миожество. то через P ( H ) (через P‘ ( H )) обозначаем семейство всех (всех непустых) п/м H ; Fin( H ) есть def семейство всех конечных множеств из P' ( H ) (если H конечно. то Fin( H ) = P' ( H )).

Для любых объектов x п у че}зез {x ; у} обо значаем миожество. содержащее x. у и не содержащее никаких других элементов. Если z — объект, то {z} = {z ; z} есть синглетон, содержащий z. Каждое множество — объект, а потому для произвольных объектов p ii q . следуя [12. с. 67]. полагаем, что ( p, q ) = {{p} ; {p ; q} }. получая упорядоченную пару (УП) с первым элементом p и вторым элементом q . Если же z есть

какая-либо УП, то через pr1( z ) и pr₂( z ) обозначаем элементы z: разумеется, z = (pr1 ( z ) , pr₂( z )).

Как обычно, для любых трех объектов a, b и (( a,b ) , с ). Традиционное [13, с. 17] соглашение о том,

соответственно первый и второй

с полагаем [13. с. 17] ( a, b, с) = что Л х В х С = ( Л х В ) х С для

произвольных непустых множеств Л, В и С, позволяет при выборе любой функции Ф, действующей из Л х В х С в непустое множество D, рассматривать значение

Ф ( x,y ) G D при x G Л х В ii у G С: полагая x 1 =

Ф ⁽ x 1 ^,x 2 ,y ) = Ф ⁽ x,y )•

Как обычно. R — вещественная прямая. N { 0;1;2; ...} G P' (R):

p T q = { k G No | ( p < k )&( k < q )}

pr1( x ) 11 x 2 = pr₂( x ). имеем также

= { 1; 2; ...} 11 No = { 0 } U N =

Vp G No Vq G No

(в (1) допускается реализация 0). Еели K — непустое конечное множество, то |K| G N есть def мощность (количество элементов) K при этом определено непустое множество (bi)[K] всех бпекщin [14. с. 87] «промежутка» 1, \K| пa, K. Накеэпец. |0| = 0.

Через R + [ T ] обозначаем множество всех функций, действующих из непустого множества, T в полупрямую [0 , то [ = {^ G R | 0 < £}.

• 2.    Постановка задачи

Фиксируем непустое множество X, x ⁰ G X. N G N , N >  2. множества,

M i G Fin( X ) ,..., M n G Fin( X ) ,

• а, также отношения M1 G P‘ ( M 1 x M 1) ,..., M _N G P‘ ( MN x MN ). Постулируем, что ( x ⁰ G Mj Vj G 1 ,N )&( Mp ПMq = 0 Vp G 1 ,Nq G 1 ,N\ {p} ). Множества (2) именуем мегаполисами. Отношения M j, j G 1 , N , соответствуют возможным вариантам проведения (внутренних) работ при посещении мегаполисов. В этой связи при j G 1 ,N полагаем, что M j = {pr1( z ) : z G M j } i1 M j = {pr₂( z ) : z G M j }. получая непустые п м Mj. Тогда,

X = {x ⁰ } и (J Mi ) G Fin( X ) , X = {x ⁰ } U (J M . ) G Fin(X) . i =1 i =1

Пусть в дальнейшем N = P‘ (1 , N ) и заданы (многозначные) отображения

A i : X x N ^ P‘ ( M i) , ..., A n : X x N ^ P‘ ( M n ) .              (3)

Мы полагаем, что при j G 1 , N. x G X \ Mj ii K G N множество Aj ( x, K ) C Mj исчерпывает возможности перемещения из x в мегаполис Mj при уеловии, что K — список заданий, не выполненных на момент перемещения (зависимость такого рода, мы распространяем и на случай x G Mj, что формально можно сделать, отождествляя, например, соответствующий вариант Aj ( x,K ) с Mj-, доопределения такого рода используем ниже без дополнительных пояснений). Возможен случай, когда, упомянутые возможности зависят на самом деле не от K, а от списка K заданий, которые на момент перемещения уже выполнены; однако данный случай легко включается в рассматриваемую ниже схему, поскольку K = 1 , N \ K ; мы не будем специально на этом останавливаться. Полагаем в дальнейшем, что

Aj ( x, K ) П M j = 0 Vx G X VK G N Vj G K.                (4)

Если j G 1 , N. x G Xi i K G N. to

A j ( x,K ) = { z G M j| pr1( z ) G Aj ( x,K )} .                     (5)

Элементы непустого множества P = (bi)[1 , N ] именуем (полными) маршрутами. Каждому маршруту a G P (перестановке [14, с. 87]) сопоставляем перестановку а- ¹ G P. обратиую к а: а- 1( а ( k )) = а ( а- 1( k )) = k Vk G 1 , N . Пл-сть Z ecть def множество всех кортежей

( z. ) i₆ O N : ал ^ X x X ;                            (6)

среди кортежей (6) выделяем траектории, согласованные с маршрутами; итак, при a Е P в виде

Za = {( zt ) te on Е Z | ( z о = ( x ⁰ ,x ⁰))&( Z t Е M , ( _т ) V t Е 1 ,N )& &(pn( Zs ) Е Aa ( s )(pr₂( Zs- 1) , {a ( j ) : j Е s,N} ) Vs Е 1 ,N )}

имеем множество всех траекторий, согласованных с a. Удобно рассматривать (7), как вариант более общего определения, полагая при K Е N, что Z к есть def множество всех кортежей ( zi ) _ie 0” [к[ ^: 0 , KI ^ X х X- ¹¹ рассматрпвая при x Е Xi i а Е (bi)[ K ] множество

Z ( x,K,a ) = {z Е Z к| (z(0) = ( x,x ))&(z( t ) Е M a ( t ) Vt Е 1 , |K| ) &        ,_g.

&(p^r1(z( s )) ^Е Aa ( s ) ⁽p^r2^{(z( s} - 1)) , ^{{ a (} j ^): j ^Е s ^{| K |}} ) ^{V s Е 1} , ^{| K 1} )} •

Тогда Z_a = Z ( x ⁰ , 1 , N, a ) Va Е P. С использованием индукции устанавливается, что Z ( x, K, a ) = 0 Vx Е X VK Е N Va Е (bi)[ K ]. В частпости, Za Е Fin(Z) Va Е P.

Предполагается, что выбор маршрута a Е P может быть стеснен условиями предшествования. В этой связи фиксируем множество K Е P (1 , N х 1 , N ), элементы которого (а это УП) называем адресными парами; при z Е K pr1( z ) и pr₂( z ) имеют смысл индексов « отправителя » и « получателя » соответственно. Полагаем в дальнейшем, что V K₀ Е P‘ (K) 3z о Е K₀ : pr1( z о) = pr₂( z ) Vz Е K₀. Тогда, (см. [15. часть 2])

A = { a Е P | Vz Е K Vt 1 Е 1 , N Vt ₂ Е 1 , N ((pr1 ( z ) = a ( t 1 ))&(pr₂( z ) = a ( t ₂))) ^    ,g\

^ (t1 < t2)} = {a Е P| a-1 (pr1(z)) < a- 1(pr2(z)) Vz Е K} Е P‘(P), а потому A Е Fin(P). В качестве допустимых решений (ДР) мы рассматриваем УП (a, z), a Е A, z Е Za. В виде

D = ^{( a, z) e A х Z | z Е Za ^} ,

имеем непустое множество всех ДР. Введем в рассмотрение функции стоимости, позволяющие затем определить аддитивный критерий. Итак, фиксируем c Е R +[X х X х N], с 1 Е R +[X х X х N],^^^,cw Е R +[X х X х N], f Е R + [X]•  (11)

Итак, (с, с 1, •••, cN, f) есть набор функций стоимости; c служит для оценивания внешних перемещений (из x0 в мегаполисы и между мегаполисами), Cj, г де j Е 1, N, оценивает работы, связанные с посещением Mj, а f используется для оценки терминального состояния. Функции (11), следовательно, применяются для оценивания процессов вида,

^z 0 ^ (^pr1^{( z} 1) ^Е Ma (1) ^ ^pr2^{( z} 1) ^Е Ma (1)) ^ ••• ^ (pF1( Z n ) Е Ma ( N ) -^ pr2( Z n ) Е Ma ( N )) ,

где a Е A 11 (zi)ieotn Е Za. Соответствешю. 5'П (a, (zi)ieotn) Е D (cm. (10)) сопостав ляется

N

^C a ^{[( z} i ) ie 0 N ^] = )E1 [^C(p^r2^{( z} s- 1) , p^r1^{( z} s ) , ^{{ a (} t ) ^: t ^Е s ^{,N } ) +} + Ca ( s )( Zs, {a ( t ) : t Е s,N} )] + f (pr2( Z n )) Е [0 , to [ •

В качестве основной, рассматриваем в дальнейшем следующую задачу:

C а [( zi ) i_e on ^] ^ min , ^а G A , ⁽ zi ) i_G on E Za.                    (14)

Данная задача совместна по ограничениям и обладает (конечным) значением

V △ min. Amin   ^C а ^[( zi ) iG O N ^{] G [0} , ^ ^[                      U5)

aGA (zi)iG0,N GZa и непустым множеством D0 = {(a0, z0) G D| Ca0 [z0] = V} оптимальных решений. Наша цель состоит в нахождении V (15) и какого-либо оптимального ДР.

• 3.    Слои функции Беллмана; решение задачи

В настоящем разделе рассматривается экономичный вариант динамического программирования (ДП), восходящий к [15, §4.9]; см. также [16,17]. Последующее изложение соответствует алгоритму на функциональном уровне и его логично начать с построения слоев пространства позиций. Последние, в свою очередь, базируются на конструкции существенных списков заданий, которую сейчас напомним совсем кратко, полагая C = K G N | Vz G K (pr1( z ) G K ) ^ (pr₂( z ) G K )} ii получая семейство (всех) существенных списков заданий. Семейства Cs = { K G C| s = |K| }, где s G 1 , N . образуют в своей совокушюсти разбиение С . При этом C_N = { 1 , N} (cini-глетои. содержащий 1 , N ) п С ₁ = { {t} : t G 1 , N \ K₁}. г,те K₁ = { pr₁( z ) : z G K }. Следуя схеме [15, часть 2], введем отображение I, действующее в N по правилу I( K ) = K \ {pr2( z ) : z G Е[ K ]}. где (при K G N) Е[ K ] = { z G K | (pri( z ) G K )&(p^( z ) G K )} (см. также [16-19]). Наконец, (см. [18,19])

Cs 1 = { K \ {t} : K G Cs, t G I( K )} Vs G 2N               (16)

Итак, в виде C_N ^ C_N_ ₁ ^ ... ^ С ₁ имеем рекурретгтиую процедуру: C_N известно, а далее следует применять (16). Следующий этап состоит в построении множеств D о , D ₁ , ...,D_N, являющихся по смыслу слоями пространства позиций. Полагаем, что

D n △ {( X ⁰ , XN )} 11 D 0 △ {( X, 0 ) : X G M} ,                  (17)

△ где M = [J Mi. Если же s G 1, N — 1, то при K G Cs вводим последовательно iG 1N \K1

Js ( K ) △ { j G 1Л \ K | {j } U K G Cs +1} G P‘ (1Л) ,

Ms[K] △  J  Mj G P‘(X), Ds[K] △ {(x,K) : x G Ms[K]} G P‘(X x Cs), jGjs (K)

после чего полагаем, что

Ds △ U D s [ K ] G P' (X x Cs ) ,                        (18)

KGCs получая непустое п/м X х Cs. Итак, все множества Dо,D1,...,DN определены. Отметим следующее свойство, рассматриваемое в более частных случаях в [15-19]:

(pr2 (г) ,K \ {j }) G Ds-1 Vs G 1N V(x, K) G Ds Vj G I(K) Vz G Aj (x, K).(19)

С учетом непустоты множеств-слоев D0, D1 ,...,DN последовательно определяем функции vо GR +[Dо],v 1 GR +[D1],...,VN GR +[Dn].(20)

Итак, определяем функцию v0 в (20) посредством условия vо(x, 0) = f (x) Vx G M;(21)

учитываем при этом (17). Если s G 1 , N и функция v_{s- 1} (см. (20)) уже построена, то v_s G R +[ D_s ] определяем следующим правилом, учитывающим (19):

Vs ( x,K ) = min min [ c ( x, ргД z ) ,K ) + cj ( z,K ) + v_s_ 1(pr₂( z ) ,K\{j } )] je I( к ) ze a j ( x,K )

V ( x, K ) G Ds.

Тем самым реализуется рекуррентная процедура

Vо —— V1 —— ... —— VN, на последнем этапе которой определяется vN(xо, 1, N) G [0, то[ (см. (17)). При этом

V = v n ( x ^о , 1 , N ) .

Доказательство (24) использует рассуждения, опирающиеся на конструкции, подобные [16-19] и использующие соответствующее уравнение Беллмана.

Построение оптимального решения. Полагаем, что процедура (23) завершена. Из (22) и (24) вытекает, что

V = min min  [c(xо, рГ1 (z), 1 ,N) + cj(z, 1 ,N) + vn- 1(pr2(z), 1 ,N \ {j})], (25) jeI(1 ,N) zeAj(xо, 1 ,n)L где согласно (17) п (19) (pr2(z), 1, N \ {j}) G DN_1 щш j G I(1, N) i1 z G Aj(xо, 1, N). С учетом (25) выбираем n 1 G I(1, N) и z(1) G An 1 (xо, 1, N) из условия

V = c ( x ^о , pr1( z ⁽¹⁾) , 1 ,N ) + Cn 1 ( z ⁽¹⁾ , 1 ,N ) + v n - 1(pr2( z ⁽¹⁾) , 1 ,N \ {n 1 } )      (26)

(свойство (26) означает, что ( n ₁ , z ⁽¹⁾) есть решение локальной экстремальной задачи, связанной с (25)). При этом, конечно,

(pr2( z ⁽¹⁾) , 1 N \{n 1 } ) G D n - 1 .                           (27)

Тогда, согласно (19) (pr2( z ) , 1 ,N \ {n 1; j} ) = (pr2( z ) , (1 ,N \ {n 1 } ) \ {j} ) G D n - 2 при j G I (1 ,N \ {n 1 } ) 11 z G A j (pr2( z ⁽¹⁾) , 1 ,N \{n 1 } ). С учетом (22) ii (27) имеем, что

VN- 1⁽p^r2^(z(1)) , ^{1 ,N} \^{n 1 ^} )=     ____

= mi n            min          c (pr₂( z ⁽¹⁾) , pr₁( z ) , 1 , N \ {n ₁ } ) +

je I(1 ,N\{n 1 } ) z e A j (p r₂(z⁽¹⁾) , 1 ,n \{n 1 } )              ______

+ cj ( z, 1 ^,N \ ^{n 1 } ) + ^V N - 2(p^r2< ^z ) , 1 ,N \ ^{n 1; ^j } )] .

С учетом (28) выбираем п 2 € I(1 , N\{п 1 } ) и z⁽²⁾ G A _n 2(pr₂(z⁽¹⁾) , 1 , N\{п 1 } ) из условия

VN- 1⁽P^r2⁽z⁽¹⁾⁾ , ^{1 ,N} \ ^{П 1 ^} ) = ^c(P^r2^(z(1)) , P^r1^(z(2)) , ^{1 ,N} \ ^{П 1 ^{} ) +} + cn 2 ⁽z⁽²⁾ , ¹ ,N \ ^{п 1 ^} ) + vN- 2⁽P^r2⁽z⁽²⁾) , ^{1 ,N} \ ^{п 1; п 2 ^} ) ,

где согласно (19) (pr₂(z⁽²⁾) , 1 , N \ {п .; п 2 } ) G DN- ₂. Из (26) и (29) получаем, что

V = c( x ⁰ , pr1(z⁽¹⁾) , 1 , N ) + c(pr2(z⁽¹⁾) , pr1(z⁽²⁾) , 1 ,N \ {п 1 } ) +

+ cn 1 ^(z(1) , ¹ ,N ) + cn 2 ^(z(2) , ^{1 ,N} \ ^{п 1 ^} ) + vN- 2⁽pr2^(z(2)) , ^{1 ,N} \ ^{п 1; п 2 ^} ) •

Процедуру, состоящую из этапов, подобных (26), (29), следует продолжать вплоть до исчерпывания всего индексного множества 1 , N , т.е. до исчерпывания полного списка заданий. В результате будут построены маршрут п = ( пj ) je 1 N G A и траектория ⁽z⁽ j ^}) je 0 N ^G Zn- образуктще ДР ⁽ п, ⁽z⁽ j )) j_G o N ) ^G D Для ксuoporo C n [⁽z^{( j} )) j_E o N ^] = V (при N = 2 данное свойство непосредственно следует из (30) по определению v ₀). Итак, построенное ДР оптимально в задаче (14): ( п, ( z ⁽ j )) j_e o N ) G D_o.

• 4.    Вычислительный эксперимент

Теоретические конструкции, рассматриваемые в данной статье, использованы при проведении вычислительного эксперимента по решению задачи оптимизации резки в виде следующей упрощенной модели. В качестве множества X будем рассматривать прямоугольную область на плоскости, имеющую смысл некоторого листа материала, подлежащего раскрою на некоторое множество деталей; а именно: в нашей модели X = [ a 1 , a ₂] х [ b 1 , b ₂]. г,те a 1 G R. a ₂ G R. b 1 G R i1 b ₂ G R; веществениые числа, a 1 < a ₂. b i < b ₂ зафиксированы. Под числом N будем понимать количество вырезаемых контуров деталей. Каждый контур характеризуется основной и вспомогательной эквидистантой: вспомогательную эквидистанту образуют точки врезки и соответствующие им точки выключения резака, а, основная эквидистанта — это собственно траектория движения инструмента, с включенным резаком, по которой он движется при резке контура детали. Вспомогательная эквидистанта расположена в непосредственной близости от основной, именно с ней отождествляются в нашей модели мегаполисы (2). В данной модели обе эквидистанты каждого контура подвергнуты дискретизации. Таким образом бинарные отношения Mi ,..., M N есть множества пар точек, первый элемент каждой пары — это точка врезки, второй — точка выключения инструмента. Точка x ⁰ в нашей модели является исходным положением, терминальным этапом процесса (12) является переход инструмента в точку x ⁰. Условия предшествования имеют вполне естественный технологический характер: резка внутренних контуров всегда, должна, предшествовать вырезанию внешних контуров; допускается размещение одних деталей внутри других, но не допускается пересечение эквидистант вырезаемых контуров.

Пусть функции (11) заданы следующим образом.

• 1)    Функция c оценивает затраты на перемещение инструмента из исходного положения x ⁰ или точки выключения резака в следующую (по порядку реализации раскройного плана) точку врезки и задается посредством евклидова, расстояния; данные перемещения производятся с выключенным резаком;

• 2)    Функции c 1 , •••^cN оценивают суммарные затраты на перемещение инструмента с включенным резаком из точки врезки x в точку у на основной эквидистанте

и на отвод инструмента после завершения вырезания контура в точку выключения резака, z . Данные функции задаютея в виде выражения 3 * р ( х,у ) + р ( у, z ). г,те р — евклидово расстояние; коэффициент 3 служит для оценивания дополнительных затрат, связанных с пробивкой материала, при врезке и движении к основной эквидистанте; отметим, что движение инструмента, от основной эквидистанте к точке выключения инструмента, поизводится также с включенным резаком, но в данном случае не требуется прорезание « перемычки » между основной и вспомогательной эквидистантами;

• 3)    Функция f — суть евклидово расстояние от точки выключения резака на последнем (по порядку реализации раскройного плана) контуре до исходной позиции _т 0 ^х

Зададим отображения (3) следующим образом. Пусть в данный момент времени не вырезанными остаются контура с индексами из множества K, K С 1 , N, а резак находится в позиции х , которая либо является исходным положением х ⁰ (в этом случае K = 1 , N ), либо некоторой точкой выключения инструмента, т.е. х Е M j, j Е 1 , N \ K. Рассматриваем способ построения множества допустимых для перемещения резака точек врезки на контуре с индексом i, т.е. п/м множества M i. Поскольку в случае, когда перемещение осуществляется из точки х ⁰, ни один контур еще не вырезан, все точки врезки доступны для перехода. Поэтому рассмотрим случай, когда K = 1 , N . Критериев допустимости два:

• 1)    соблюдение тепловых допусков;

• 2)    исключение сильно удаленных точек контура (минимизация времени перемещений резака между контурами).

Критерии упомянуты в порядке убывания приоритета, т.е. среди точек, удовлетворяющих 1) выбираются те, которые удовлетворяют 2).

Рассмотрим подробно оба, критерия отбора, точек врезки. Будем рассматривать процесс построения множества, допустимых точек врезки для контура с индексом i Е K- т.е. п м }тожества M i : зафиксируем для iтглядности индекс г.

Г) Пусть задана величина теплового допуска 5 Е R , 5 >  0. Точка врезки у, у Е M i удовлетворяет критерию Г), если ( р ( y,z 1) > 5 vz 1 Е M _k ^k Е 1 , N \ K )&( р ( у, z ₂) > 5 ^z ₂ Е Mk ^k Е 1 , N \ K ). где Mk — основная эквидиста!:та контура с индексом к. Если для контура не находится ни одной допустимой точки врезки, то все возможные его точки врезки признаются допустимыми для исключения коллизии, связанной с невозможностью задания множества Ai ( x,K ).

• 2’ ) Среди точек врезки у, у Е M⁽¹⁾, удовлетворяющих 1 ’), выбирается точка у’ такая, что c ( х,у‘ ) = min c ( х,у ). г,те х Е M j, j Е 1 ,N \ K. a, M⁽¹⁾ С M i — подмио- ye M⁽¹⁾

жество удовлетворяющих 1’) точек врезки контура с индексом i Точка у’ признается допустимой согласно критерию 2’). Для каждого контура пусть задана, величина допуска Ek Е R , Ek >  0, г де к Е 1 , N. Точка врезки у, у Е M⁽¹⁾, удовлетворяет критерию 2'). если с ( х,у ) — с ( х,у' ) < Ei.

Итак, при перемещении из точки выключения резака х Е M j, j Е 1 ,N \ K, на контур с индексом i значения отображения Ai ( x,K ) составляют точки у Е M i, которые удовлетворяют критериям Г) и 2’). При этом ограничение Г) реализует зависимость отображения Ai от списка уже выполненных заданий, а критерий отбора 2’) — зависимость от точки перехода.

Данная алгоритмическая контрукция была реализована в виде программы для

ПЭВМ, написанной на языке программирования C++. Программа работает под управлением 64-х разрядной операционной системы семейства Windows, начиная с версии Windows 7. Вычислительная часть программы реализована в отдельном от интерфейса пользователя потоке; для случая решения задачи на плоскости имеется возможность графического представления траектории движения инструмента с возможностью увеличения отдельных участков графика и сохранения изображения в файл графического формата bmp. Программа позволяет решать задачу оптимизации резки в условиях действия только критерия отбора точек Г) или Г) и 2’) (см. выше); в данной работе приведем пример решения задачи, где используются оба типа ограничения на выбор точек врезки.

Вычислительный эксперимент проводился на ПЭВМ с процессором Intel Core i7, объемом ОЗУ 64 гБ с установленной операционной системой Windows 7 Максимальная SP1. В исследуемом примере N = 31, | K | = 20, x ⁰ = (0 , 0) (совпадает с началом координат) и 6 =10. Величиньi допусков е 1 , ...,e_N задавались равными для всех контуров и варьировались. Приведем результаты решения задачи на ПЭВМ; на графиках значками < 1 помечены точки врезки, а >  — точки выключения инструмента.

При величине допуска е_к = 2 Vk Е 1 , 31 получены следующие результаты: величина совокупных затрат: V = 1104 , 18; время счета составило 4 ч 7 м 26 с. График маршрута и трассы приведен на рис. 1.

Рис. 1. Маршрут и трасса при значении допуска 2

Если величина допуска е_к = 10 Vk Е 1 , 31, то получены следующие результаты: величина совокупных затрат: V = 1017 , 891; время счета составило 4 ч 17 м 48 с. График маршрута и трассы приведен на рис. 2.

При величине допуска е_к = 50 Vk Е 1 , 31, получены следующие результаты: величина совокупных затрат: V = 1015 , 3 время счета составило 4 ч 23 м 12 с. График маршрута и трассы приведен на рис. 3.

Такое поведение результата вполне закономерно: с ростом величины допуска увеличивается количество вариантов для осуществления врезки и, как следствия, получается больше вариантов для оптимизации затрат, но при этом растет объем перебо-

Рис. 2. Маршрут и трасса при значении допуска 10

Рис. 3. Маршрут и трасса при значении допуска 50

ра, что неизбежно влечет увеличение времени счета; именно такие закономерности мы и наблюдаем в приведеных трех примерах.

Работа выполнена при финансовой поддержке РФФИ (проект 15-01-07909), постановление №211 Правительства РФ, контракт № 02.А03.21.0006.