, , ,

<<


 >>  ()

2 (110) 2012

..

625.73 : 517.9

.. ..

- , .

, . ( ).

: , , ,.

l, l ;

x ,, - ( );

T, T0 -. x=0 x=R;

s ;

w l T l T0 dx =sw + () ;

m=R/x;

t .

(1), x m -1 x (1) dt a T0 - T exp - 0 =l q. (6) ( ) x =x 0 xx I 2 a erfc a 0 2 a p at 2 (110) x, x xR II T0 - T =l q x =x (7).

R - a0 t R (6) (7), x. 1. () : p R erfc (y ) exp y 2, m= =1+ I ;

(8) x II 2y y = a 0 2 a. (9) (8) (9), m= =R/x. m.

l T 2t l T + x=. (2) sw m -1 , - (2).

-, m, - :

xxR (. 1), dx U = f (x ) = - (10), :

x dt T ( x - x ). x T= U = - f (z ) dz, x (0 ) = x 0, U .

(3) R-x x m - - (2), (10) xx [1] l T + l T0 x = - U dx - = (11)..

2s w t R-x x dt [1] T 2T ;

x x ;

=a t x 2 U T (x, 0 ) = T0 ;

= f (x ) = 0. (12) x T (x, t ) = T ;

T (, t ) = T0 ;

(4) x = a t, l T l T + x = 0. (13) R -x T , ;

a l T xx;

a0 , - R m= =1-, (14) x l T.

x x l T T0 - T erfc T ( x, t ) = T0 - x0 = R ( ). (5) (15).

erfc a 0 l T - l T 2 at 2a (5) x, U l,, 20. x0 q x=x f (x 0 ) 2U (x 0 ), 0 (16)., x x, x -.

2. - 1 1 l T + l T0 x U = .

x 2 2 2s w t R -x 3., (14),, 1 R 0. (17), m, (R - x ) 2 (110) 2s w t.

, x0, (15), 2U, x 2 1.,.. x., /... . :, 1973. 254.

,, x0 2. /...,..,. . :, 1981. 256.

x0 [2]. 3.,., U - /.,.,.. [3],. :, 1974. 318.

dU (x ( t ) ) U dx U f (x ) = - f 2 (x ) = =. (18) x dt x dt, ,,,.,, (),.

,,, (),, -.

,,,,.

.

. : gramota47@yahoo.com 1. - 11.01.2012.

..,..,..

51/,.. :..

010400 (010300 ) /.. ;

. :

-, 2011. 83 c. ISBN 978-5-8149-1158-2.

,,. :

,,.

51/,.. - :.

/..,..,.. ;

. :

-, 2011. 83 c. ISBN 978-5-8149-1164-3.

, -..

.. 687. .. 2 (110) . .. , , . , - .

, , : , .

1.

,., - (,,, -..)., -,. -,., -, :,... -, , -, - [7, 8]., - [15]. [6],,.,. -, -. -..

(SAT), . :

(MAX-SAT). J , - J={1,,n};

j j J ;

() - xj ,, j, .

[1, 2] ;

I ,,, I={1,,m};

- I ,., I= ={1,,m}, I I ;

Ci , i, i I,.

, - xj / x j ;

. di Ci, 22, i I \ I.

.

-, Ci, i I, - :

, Ci, i I \ I, di zi, max, (5). iI \ I. yj 1, i I, (6), jCi.

C i- C i+ 2 (110) y j + zi 2, i I \ I, (7), Ci jCi.

yj = p, (8) :

jJ di zi max, (1) y i, z i { 0,1}, i I \ I, j J. (9) iI \ I, (6), (7) y j Ci- - 1, i I, yj - (2).

jCi- jCi+, y j + zi Ci- - 1, i I \ I, yj - (3), G= =(V, E1, E2) jCi- jCi+, (5)(9), y i, z i { 0,1}, i I \ I, j J. (4) V={v1, v2, , vn}, vj , j- ( vj).

E1 i zi=1,, E2 .

Ci.

, (1)(4) - NP-, -., MAX-SAT., -,,, -, .

G 1 G,,, :, G2 , V G.

yj yj = p p,.

jJ jJ 1. G V, p . V.

2. G.

,, p, V.

p., - G,,, V.

G:

ajy j b, V jJ p, aj ,, j-, b .

., - - G, V. G1 (,, G), 2..

p=0 p=1. p NP-, Ci, -.

,.. x x, x, x ., -, C i = 2, C i+. (.,, [1, 4, 6])... //, :

.. VI..-.. :

, 2007. . 3. C. 2630.

3. 2.,.. 2 (110), /..,.. //, - :. III.

-. (, 11 2006) / ..... :

-,. 2006. . 176.

G, 3.,.. -. [1, 2], /.. //, - :. VI..-.. :

, : -, 2007. . 3. C. 6568.

1. 4.,.. G ( ). /..,.. // 2. - :. IV.

.. (, 29 4 2009) /, -.... :

-, 2009. . 237.

( 1) 5.,... /..,... // :..

3...-... 9, 2009. 2.. 2 / . -., 2009. . 4950.

. - 6.,.. 1., 1 - /..,.. //. 2010. 2(90). . 234237.

. 7.,.. :.

.... /... :

-, 2003. 432.

,, - 8.,... :. /.. // :

. -, 2005. 176.

:,, L-.

,. -, (),,... -.

,, -, -. : orlova.tanya@gmail.com 09.12.2011.

1.,.. ..,..

/ . . 544.4: 519.6: 538.971/.971.3: 542... , .

2 (110) , -,

, , - , , . .

- . , , .

, - : , , .

1. dx = 2k1PA 2 (1 - x - y )2 - 2k-1x 2 - k3 xy dt -- dy = k P (1 - x - y ) - k y - k xy, (1) - 2B dt 70- [13]. x, y AZ, BZ ;

k1, k 2 A 2, B;

k -1, k - 2 A 2 + 2B 2AB, ;

k 3 (I) (II);

t ;

PA, PB A 2, B.

- [1, 4] (1), (II), G = A 2 + 2Z 2 AZ = {(x, y) | x 0, y 0, x + y 1}.

B + Z BZ (II) AZ + BZ 2Z + AB. ( k-1 = k- 2 = 0) (1).., G: x1 = 0, y1 = 1 () x 2 = 1, y 2 = AZ, BZ Z;

A2, B, AB . - () [1, 5]. - () -.. (Pt, Pd) =(2k1PA /k2)/ (1+(8k1PA /k3)1/2).

- (..). (II), - [6] (II), - [1, 2, 5, 7]. () - [1, 4, 5]:.

, m A, mB , - () [4]..

[811] - (2),, 2 (110)..: (1, y1)=(0,1) (x2, y2)= =(1,0). u v..

, - G...

. = :

mB = ln u - m A up v = (3). -.

(1 - x - y ), : 1) ( p 00 m A,,..,, ;

2) )( )( ), m B, x m A, mB, y m A, m B ;

3), -.

- ;

4) - [1215].

, - - [13, 15, 1719].. [8]., (2) m A, m B,,, (x, t), (y, t), ( m A,t ), ( mB, t ).,.

,,,. -. - (2) :

,. - ( ( )) d m A = 1 y u - exp m + m p A B D mB (), dt - 1 y d mB ( ( )). - - u - exp m A + mB p00 + = D mA dt [1215].

(v(1 - x - y ) - p00 exp(mA + mB )) x 2. - mB - (4) (v(1 - x - y ) - p00 exp(mA )) x + mB, + mA [8].

D (x,y) ( m A, mB ).

[9], (4) 27 e AA,,,,.. [16].

e AB, e BB, 10;

10;

0 /,. - =500 K.,. u = 2 k1PA 2 / k3, v = k2 PB / k3, m A = m A / RT, mB = m B / RT, t = k3t, : (4).

( ( )) dx = p00 u - exp m A + mB dt, ( ) dy = v (1 - x - y ) - p exp m + m, (2) .

00 A B dt.

p00 ,. (a;

b;

) 26 e AA = a, e AB = b, e BB = c /.

R , T 2 (110). 2. (10;

10;

0),.. =500 K.

. 1. (10;

10;

0).

..

. 4. (10;

10;

10),.., u,v,, ;

. 3.. 2, (10;

10;

0)..,, u,v. 3.. 13.. 1... 3.1. - (10;

10;

0), -.. =500 K.

,, -,.. =500 K. -.. =4 ( -. (10;

10;

0),, ) =300 .. =500 K (. 2), 1000 K,, -. 3. =600 K (0;

0;

0).,.., =800 K.., =1400 K -.., =2600 K.. -... u,v,, -,.

. 3.2. - =500 K =.. =4;

6;

8., 2 (110) . 5. (10;

10;

10) =4.,,. 6.. 5, (10;

10;

10) =500 K =4;

.., =6;

8 - =500 K.. 4, (10;

10;

10). =6 =8 -, (10;

10;

10), - -.

.., :

1.,, -... u,v, 3.3. -,.

2., -,, - -.

- 3., (4). -, - (4) u, v, ;

-.

u,v ( ),,,.

. 5 (10;

10;

10). - 1. Bykov V.I., Elokhin V.I., Gorban A.N., Yablonskii G.S.

- Comprehensive chemical kinetics. //Kinetic models of catalytic, - reactions (Ed. R.G. Compton). V.32. Amsterdam: Elsevier, 1991.

, 2. Slinko M.M, Jaeger N.I. Oscillatory heterogeneous catalytic. systems. //Studies in Surface Science and Catalysis. V. 86. Amster 3.4. - dam: Elsevier, 1994.

3. Zhdanov V.P. Monte-Carlo simulations of oscillations, chaos =4;

6. - and pattern formation in heterogeneous catalytic reactions. // 28, M - Surf. Sci. Rep. 2002. V.45. P. 231.

4.,.. /... 14.,.. - :, 1986. 304. /.. 5.,.. /,..,.. //..,..,... :. 2002. T. 384. 5. . 650654.

, 1986. 320. 15. Runnels L.K., Combs L.L. Exact finite method of lattice sta 6. Bykov V.I., Yablonskii G.S., Kuznetzova T.V. Simple catalytic tistics. I. Square and triangular lattice gases of hard molecules // mechanism permitting a multiplicity of catalyst steady states. //Re- J. Chem. Phys. 1966. V.45, 7.. 24822492.

acting Kinetic and Catalysis Letters. 1979. V.10, 4. P. 307310. 16.,.. - 7.,.. - /... :, /..,..,... 1988. 296.

:, 1984. 250. 17. Myshlyavtsev A.V., Sales J.L., Zgrablich G., Zhdanov V.P. The 8.,.. - effect of three-body interactions on thermal desorption spectra // 2 (110) - - J.Statistical Phys. 1990. V. 58, 5/6. P.10291039.

. /.., 18. Myshlyavtsev A.V., Dongak M.D. (Myshlyavtseva) Statistics.. //. 2005. of adsorption on top and bridge sites of a square lattice: transfer 2(31). . 8590. matrix approach. //J. Stat. Phys. 1997. V.87. 3/4. P. 593607.

9.,.. 19. Bartlet N.C., Einstein T.L., Roelofs L.D. Transfer-matrix -. - approach to estimating coverage discontinuities and multicritical /..,.. // point positions in two-dimensional lattice gas phase diagram. //. 2006. 1(34). . 5760. Phys. Rev. B. 1986. V.34. 3. P. 16161625.

10.,.., - /..,,.. //. 2007. . 48,, 4. . 576585.

11.,..,.

/,..,.. //.

-,. 2007. . 50, 11. . 104109.

12. Myshlyavtsev A.V., Zhdanov V.P. The effect of nearest-neigh.

bour and next-nearest-neighbour lateral interactions on thermal desorption spectra //Chem. Phys.Lett. 1989. V. 162, 1,2. P. 4346. : 644050,.,., 11.

13.,.. 06.02.2012.

- /..,... ..,..

:, 2000. 101.

.. 512.816+517.958 : 530.

- , . . .

- , :, , .

H ( x, x ) j( x ) = - m 2j( x), 1. (1) H ( x, x ) g ij i j - (M, g) , gij, i g. x={xi} M -, - ( xa ) = xa (e) + ieca, caC(M) (e i ), m j(x). i,.

[xa ), H (e)] = 0.

(e, M 2 (110) G, i i x a = x a ( x ) i, a = 1,,dim G. -, i i, x a x a ( x ) i ca (1) L G., i j c a + Fij xa = 0, (4) g [xa, H ] = 0, [xa, xb ] = Cab xg, (2) g g ab = - ba dc a + ixa F = 0. (5) L, a, b, g = 1, , dim L. [.,.] - ix F a F xa.

.

1. M 2- (4), F = 1 Fij dx i dx j., 2- F G.

F=dA, A=Ai dxi 1-,.

M,,. Lx = ix d + +d ix 0- ca, (4) (5), 2- F - M Fij d 2 c = -d ixa F = ixa dF - Lxa F = -Lxa F,, 1- A.

, -, dF = 0. M , - -, 2- F (., - G.

, [1, 2]): i ( e ) i - ieAi, e -, i, i = - 1. (1) - (5) - ca = - ixa F = - Fij xa dx j.

i (6) H (e)(x, x ) j(x ) = - m2j(x ), (3), G- ij (e) (e) (e) ij H ( x, x ) g i j = g (i - ieAi )( j - ieA j )., -, -,. ( xa = xa i xae ) = x a ( e ) + iec a, i i : L - i (1) ca (6).

2- F?

, (2), -, xa( e ). g (e) (e) (e) [xa, xb ] = Cab xg + ( 1- ), - g + ie xa (c b ) - x b (ca ) - Cab cg - F (xa, x b ),..

,, (6),, g( [xa ), x b )] = Cab xge) + ieWab.

(e (e (7) ., :

[3]. g Wab F (xa, x b ) - Cab cg.

[4, 5]. (8) 2. -, e= (7) - (2) 30 - (1).

2. W ab, - L G, (8), M - 2- (8).

:, (9) (10), g, W ab = ab lg, W ab = -W ba, lg const. 2- (9) 2-. 2- d d d ab W dg + bg W da + ga W db = 0. L B 2(L;

R).

(10), ~ L,,. (8) ~ L = s(L) R, (5), W ab s. g, W ab = ab lg, g 2 (110) dWab = dix b ixa F - Cab dcg = (7) g [xa, xb ] = Cab xg + ielg.

(e) (e) (e) ( ) ( ) g = Lx b ixa F - ix b d ixa F + Cab ixg F = ca, (6), ( ) = -i[xa, x b ]F - ix b Lxa F - ixa dF +, s ca ca+la.

, g g ~ + Cab ixg F = -i[xa,x b ]F + +Cab ixg F = 0. L L [7].

L Lx ih = i[x,h], - G- F.., F F , Wab 2-, a, b = 1,,dim L. (9) (10) - M. 2 W W,., (10) ~~ F L L ~~ g ab L. L L , WWB2(L;

R), 2- W W L.

2-.

.,, W: L L R, (10), -, 2- L - R. -, 2 2- L Z 2(L;

L B2(L;

R).

R). W Z 2(L;

R) -, ~ L = L W R, - - H2(L;

R) Z2(L;

R)/ L /B2(L;

R), 2- R [6]. ~ L : L., ~ [X, Y ]L = [X, Y ]L + W (X, Y ), [L, Z ] = 0, ~ (11) 2- X,YL, ZR, [, ]L, [, ]L, ~.

~ L L.

3.

(7) (11), :

(e) (e) (e) x0 ie, x1, K, xdim L 3.1.

- L, 2- (8)., ds 2 = (dx 0 )2 - (dx1)2 - (dx 2 )2 - (dx 3 )2,.

. (M, g) xi (, +). g, G, i xa = xa i, F - G = R4 2- M. xa = a, a = 0, 1, 2, 3.

(3) ~ L,, -, 2- x0e) ie, xa ) = xa (e) + ieca, a = 1, K, dim L, ( (e i i.

, caC(M) (6). - 2- ~ L - M, : F = 1 Fij dx i dx j, F m (x 0, x 1) x0 x1, J R. const. -,, : A = 1 Fij x i dx j. H ( e ).. A0 = 0:

2 (110) - A = m(x 0, x1)dx 0 dx1 - J cos x 2dx 3.

H ( e ) ie ie H ( e ) = gij i + Fik x k j + F jk x k, 2 01 H (e) = e -n (x, x ) 2 - e - l(x, x ) 1 gij = diag(1,-1,-1,-1). 0 - ie m(x 0, x1)dx 0 - (x1)- 2 2 (6), ca - (3) - (x1 sin x 2 )- 2 3 - ieJ cos x (14) ie ca = Fak x k, xa ) = a (e Fak x k, a = 0,1,2,3. 2 (6) c1 = J sin x 2 sin x 3, c 2 = J sin x 2 cos x 3, c3 = - J cos x 2, :

g( [xa ), H (e)] = 0, [xa ), xb )] = Cab xge).

(e (e (e -, (13):

, ( sin x x ae ) x1e) = - cos x 3 2 + ctg x 2 sin x 33 + ieJ (,, sin x 2- Fab. cos x, Z 2(L;

R)=so(4;

R), x2e) = sin x 3 2 + ctg x 2 cos x 33 + ieJ ( B 2(L;

R)=0, H 2(L;

R)=so(4;

R), so(4;

R) -, sin x 4., x3e) = 3.

( 2- (3)., 3.2. - (14), --, xa.

, 01 ds 2 = en (x, x )(dx 0 )2 - e l(x, x )(dx1)2 -,. - (x1)2 (dx 2 )2 + sin2 x 2(dx 3 )2, (12), x0(, +), x1(0, +), x 2(0, p ), x 3(0, 2p). (x0, x1) l(x0, x1) , [8]. x0 x1., 2- - so(3) 2, H 2(so(3);

R) = 0.,, so(3), so(3).

x1 = - cos x 3 2 + ctg x 2 sin x 3 3, 3.3. x 2 = sin x 3 2 + ctg x 2 cos x 3 3, - x3 = 3, 01 ds 2 = en (x, x )(dx 0 )2 - e l(x, x )(dx1)2 - (x1)2 (dx 2 )2 + (dx 3 )2, [x1, x 2 ] = x3, [x 2, x3 ] = x1, [x1, x3 ] = -x 2.

x0(, +), x1(0, +), x2(0, 2p), x3(, +).

d F=0 Lx F=0 2- 32 F = m( x 0, x 1 )dx 0 dx 1 + J sin x 2 dx 2 dx 3, (13) x1 = - x 3 2 + x 2 3, x 2 = 2, x3 = 3.

e(2), 2- WJ = Je 2e 3.

e(2):

, [x1, x2 ] = -x3, [x2, x3 ] = x2, [x2, x3 ] = 0. J R H 2(e(2);

R), - 2-- 2- e(2)., : J F = m( x 0, x 1 )dx 0 dx 1 + J dx 2 dx 3, (15) e(2),, (3)., m(x 0, x 1) J x0 x1, JR. 2 2 (110) W J 2-: W JW J+l :

e1e3+l2 e1e2, l1, l2 R.

A = m(x 0, x1)dx 0 dx1 + J x 2dx 3.

H ( e ) -, - 1.,.. 2- (15), [] /..,..,... . :, 1980. 296.

2.,.. 01 H (e) = e -n (x, x ) 2 - e - l(x, x ) 1 [] /... . :

-, 1986. 288.

0 3.,.. /..,..,.. 2 - ie m(x 0, x1)dx 0 - (x1)- 2 2 - (x1)- 2 3 - ieJ x 2.

//. 2008. . 156, 1. . 189206.

(6), 4.,.. /.. // J 22. 2005. . 46, 1. (x ) + ( x ), c 2 = - J x, c3 = J x, 32 3 c1 = C. 106118.

2 5. Bolsinov, A. Magnetic flows on homogeneous spaces / A. Bol sinov, B. Jovanovic // Comment. Math. Helv. 2008. T. 83. . 3. P. 679700.

J 6.,.. x1e) = - x 3 2 + x 2 3 + ie (x 3 )2 - ( x 2 )2, ( [] /... . :, 1981. 272.

2 7.,. [] /.,. ;

..... x2e) = 2 - iex 3, x (e) = 3.

( (16). . :, 1981. 334.

8.,.. [] /, -... . :, 1982. 447.

,,, [x1e), x2e)] = -x3e), [x1e), x3e)] = x2e), [x2e), x3e)] = ie J. (17) ( ( ( ( ( ( ( ( .

: magazev@mail.ru (17), (16) - 14.11.2011.

(e) x0 ie ..

74.580.25/,.. : /.. ;

. :

-, 2011. 95 c. ISBN 978-5-8149-1167-4.

( , , ) - ( ,, ),.

-

,.

. .

544.723:004. .. . . 2 (110).. . . , .

- . . - , . : , , , , ( ).

- :, , , , .

(2009 2011), 1.

, k-, :, [1], - k- [1216],,,. k- [1517].

, -,,,, -,, -.,, - [18, 19].

, - k, - [17, 2022].

, [25], - [6]. - -,., [711]..,,, (). -,, -. . -, k-.,. k- , k-, -, -. k-.

., -. - 34 (k- k =2).,.

T = 0 K , n (6 6) 5 W =- m h 18 = 0,55(5) 2 (110) (8 8) 1 W =- m h 4 = 0, (10 10) 11 W =- m h 50 = 0, (12 12) 7 W =- m h 36 = 0,55(5) (20 20) 13 W =- m h 100 = 0, (2 2) W =- m = 0, -. -, -. : -.

1) ( ), 2) ( ). -, h 0, -.,,,, (h).,,,,, -,, -.

- 2 (110) . (m) 55 55 /.. 1, - (h) 20 /.

,, . -,. 1 2.,, ( )..,, 2, -. 2 [24].

- -,.,,.. 1, -.. (. 3) -. 6 (p = 6).

-. 1., - p = 6 p = 8 (. 4).

. 4, -. 3h/2,, -., -, 1 - [24], (n=) c(22). W.

, -, - W (616).

-.

- W=6;

8;

10;

12;

14;

16,. 5. -,, -, [23]. -., 12 16,, - , W. - - - (22) 2,, -.., W, - 1, 2 4, (22), (66) (1212). W=. 2 . 3.. 1.. 1 , 2,3,4,5 . ;

6 , 36 n (. 1) . 4.., 2 (110). 5., -, = 200 K W 1,3 6. - 4 , - (1212) 1=0,1(6);

2=0,19(4);

=0,(5)., 1. 1 4 (..1), W=12. (. 5)., 200 K,, 4 -,,. =25/, 1.

1=0,17;

2=0,192;

=0,556;

-,,, - 12. P. J. Flory, Thermodynamics of high-polymer solutions //, - J. Chem.Phys. 1942 v. 10. p. 5162.

., 13. T. Nitta, M. Kurooka, T. Katayama. An adsorption isotherm - of multisite occupancy model for homogeneous surface // J.

2 (110). Chem. Eng. Jpn. 1984 v. 17. p. 3915.

, 14. G. Kondart, Influence of temperature on percolation in a - simple model of flexible chains adsorption // J.Chem.Phys. - 2002 v. 117. 14 p. 66626666.

. 15.F. Roma, A. J. Ramirez-Pastor, J. L. Riccardo. Multisite, - occupancy adsorption: comparative study of new different analytical,, - approaches // Langmuir. 2003 v. 19. p. 67706777.

, - 16. F. Roma, J. L. Riccardo, A. J. Ramirez-Pastor. Application (n=1) 36- - of the FSTA to dsorption of linear and flexible k-mers on two. dimensional surfaces // Ind. Eng. Chem. Res. 2006 v. 45. - p. 20462053.

. 17. A. J. Ramirez-Pastor, T. P. Eggarter, V. Pereyra, J. L.

, 1, Riccardo. Statistical thermodynamics and transport of linear Ramirez-Pastor. - adsorbates // Phys. Rev. B. 1999 v. 59. p. 1102711036.

- 18. P. W. Kasteleyn // Physica Utrecht. 1961 v. 27. [25]., p. 1209.

19. P. W. Kasteleyn. Dimer Statistics and Phase Transitions // J. Math. Phys. 1963 v. 4. p. 287293.

., [26] 20. D. Lichtman, R. B. McQuistan. Exact occupation statistics for one-dimensional arrays of dumbbells // J.Math.Phys. 1967 - v. 8 p. 24412445.

Au(111). 21.,.., - /..,.. //... 1974. . XLVIII,, -. 1. . 177179.

22.,... /..,.. //... 1973. . 9,. 2. . 196204.

23. A. V. Myshlyavtsev, V. P. Zhdanov, The effect of nearest neighbour and next nearest-neighbour lateral interactions on 1. J. K. Roberts. Some properties of adsorbed films of oxygen thermal desorption spectra // Chem.Phys. Lett. 1989 v. 162. on tungsten // Proc. Roy. Soc. A. 1935 v. 152. p. 464477. p. 4346.

2. J. V. Barth. Molecular architectonic on metal surfaces // 24.,.. Annu.Rev.Phys.Chem. 2007 v. 58 p. 375407. - /..,... 3. H.-J. Gao, L. Gao. Scanning tunneling microscopy of :, 2000. 101.

functional nanostructures on solid surfaces: Manipulation, self- 25. E. J. Gonzalez, A. J. Ramirez-Pastor, V. D. Pereyra, Adsor assembly, and applications // Prog. Surf. Sci. 2010 v. 4. ption of dimers molecules on triangular and honeycomb latti p. 2891. ces // Langmuir. 2001 v. 17. p. 69746980.

4. H. Liang, Y. He, Y. Ye, X. Xu, F. Cheng,W. Sun, X. Shao, 26. Y. C. Ye, W. Sun, Y. F. Wang, X. Shao, X. G. Xu, F. Cheng, Y.Wang, J. Li, K. Wu. Two-dimensional molecular porous J. L. Li, K. Wu, A Unified Model: Self-Assembly of Trimesic networks constructed by surface assembling // Coord. Chem. Acid on Gold // J. Phys. Chem. C. 2007 V. 111. p. 10138 Rev. 2009 v. 253 p. 29592979. 10141.

5. S. M. Barlow, R. Raval. Complex organic molecules at, metal surfaces: bonding, organisation and chirality // Surf. Sci.

Rep. 2003 v. 50 p. 201341.

, 6. J. R. Heath. Molecular Electronics // Annu. Rev. Mater.

.

Res. 2009 v. 39. p. 123.

, 7.,..,.

/.. //. , 1985 . 24, 4. . 826836.

, 8.,.. , /... M. :

,, 1976. 248.

.

9.,.., . I. -, /.. //... 1972. . XLVI,.

. 9. . 23672371.

, 10...,. II..

/.. //... 1972. . XLVI,. 10. . 25842588. : iakobian@gmail.com 11.,.. 30.01.2012.

. III.

..,..,.., /.. //... 38..,..

1972. . XLVI,. 10. . 25892592.

.. 519... . .. . .. 2 (110)

. , , . .

, , : , , , .

-.,., :

,. -,,., -,,,..,.

,, -.. :

- I , i=1,,n;

j , j=1,,m, m n;

[14]. Ji , [57] i;

- Ij ,, - j;

, di ,. i.

- G=(V,W;

E,E,E). - V={v1,,vn} ( vi di, i=1,,n) W={w1,wm}, E {(vi,wj):i=1,,n,jJi} E, {(vi,vk):i k,i,k=1,,n} E {(wj,wr):j r,j,r=1,,m}.

, (vi,wj) E, i. j, cij i j. (vi,vk) E, i, k, (wj,wr) E, j, r ( P)., -.

. i j,, k r.

. (i,j),(k,r),, j, r -, i, k. W - (4) x,. : P -. 1.

(). 1.

2 (110) : 1.1. xij=1, i j, i, k j, r (4) xij=0 , i=1,,n, jJi., i j, P :.. xij=0 ( (vi,wj)E G). 2.

n c ij x ij min 1.2.

(1) i =1 j J i 1) :, 3.

x ij di, i = 1,..., n, (2) 2) jJi,, 1.2.

n x ij = 1, j = 1,..., m, (3) 3) i =, k r,.. xkr=0 x ij + x kr 1, ( i, j ), ( k, r ) W, (4) (vk,wr)E G ( k r, 1.1).

x ij {0,1}, i = 1,..., n, j J i. (5) 2.

2. : (1), (2) (1) (3), (5),, - 1.2., (3) - x, f(x).

, 1) f(x)rec,,, (4), -.. - rec, 1.2.

. 2) f(x)rec (4) x, rec:=f(x) 1.2.

3) f(x)rec (4). x, 1.1.

1. P NP-. 3.. recd,,, rec, ( ) (1)(5). P.,.

: h=|W| p(n) ( nm,.., ;

) ., ;

[9], (n3)..

2. LS O(2hp(n)).

;

cij=ci, i=1,,n, jJi., h. h=0,.. G=(V,E) G. (4), LS p(n) vi G. ci., h=k O(2kp(n))., h=k+1. ( m) G, :

NP- [8]. 1., k+1, P, O(2kp(n)).

P 2. k+1, LS,.. O(2kp(n)),, LS O(2k+1p(n)).

: rec . -, h, rec LS.

,, rec=d, LS S (1)(5),.

n d c. S. ij i =1 jJ i : 0. x, 40 (1)(3), (5). -,. LS 2. :. /,,.. [.]. . :, 2008. 360.

. 3. Richards W., Wormald N. Representing small group - evolution // 2009. P. 115.

P, - 4.,.. - P /.. //,. -. 2009. 3. . 4975.

5.,.. /..,..,.. // :.. 2 (110) Microsoft Visual Studio 2008, 2010. C. 220224.

C++ 6.,.. LS, /..,...,.. // :. XV LS.. 5.. :

h,, -, 2011. . 6166.

7.,.. IBM ILOG CPLEX. /..,.. LS - // 12., :. XIV.. . :, 2011. C. 188189.

50 100. 8.,. (4), /.,. ;

.. . :, 1982. ., 416.

9.,. / h. n=50,. ;

.. 7-. . :, 2005. m=100, 100, 912.

30.

LS, IT-. 30 20.,,..,.

LS IBM ILOG CPLEX,, -.....

, - -, (), -.....

: kolo@ofim.oscsbras.ru, lubov shulepova@gmail.com.

1. 13.02.2012.

/.. [.]. . :

..,..

, 1989. 173.

51/ ,.. :. /... 12-.,. . :, 2010. 479. ISBN 978-5-9916-0616-5. -978-5-9692-0874-2.

...

.. 519.. . ..

2 (110)

, . .

, :, , .

1., ). (..),,, -,.

(..) F(x). (),, (, ..

N=10 N= ... .... ... ....

113/ 0,26/ 111/ 0,21/ 10469/ 0,10/ 10461/ 0,07/ 127,26/ 0,76/ 127,26/ 0,76/ 10723,75/ 0,22/ 10723,75/ 0,22/ q = 0,5 . 4 .4 . 4 .4 . 7 .7 . 7 . 111/ 0.23/ 105/ 0.17/ 10002/ 0.07/ 10686/ 0.11/ [0,1] 127,26/ 0,76/ 127,26/ 0,76/ 10723,75/ 0,22/ 10723,75/ 0,22/ .5 .5 .5 .5 .7 .7 .7 . M=0,5 111/ 0.25/ 111/ 0.20/ 10111/ 0.09/ 10921/ 0,08/ () 127,26/ 0,76/ 127,26/ 0,76/ 10723,75/ 0,22/ 10723,75/ 0,22/ . 6 .6 . 6 .6 . 7 .7 . 7 . ..


N=10 N= ... .... ... ....

97/ 0.37/ 115/ 0,18/ 10027/ 0,10/ 10494/ 0,07/ 127,26/ 0,76/ 127,26/ 0,76/ 10723,75/ 0,22/ 10723,75/ 0,22/ q =0 .10 .10 .10 .10 . 13 .13 . 13 . 93/ 0.31/ 104/ 0.25/ 9589/ 0.14/ 10443/ 0,06/ 127,26/ 0,76/ 127,26/ 0,76/ 10723,75/ 0,22/ 10723,75/ 0,22/ .11 .11 .11 .11 .14 .14 .14 . [- 2;

2] 117/ 0,30/ 111/ 0,26/ 10511/ 0,14/ 10052/ 0,12/ M=0 () 127,26/ 0,76/ 127,26/ 0,76/ 10723,75/ 0,22/ 10723,75/ 0,22/ 42 .12 .12 .12 .12 .15 .15 .15 . 2 (110). 1..,.......:

0,5 (), N =. 2..,.......:

q = 0,5, N = 2.,... F(x), -, F(x) [1, 2]. - S j = y i ( x )dF ( x ) = 0, i = 1,..., r, (1) (, F(x),,..), y1,,yr .

S ij = y i ( x )y j ( x )dF ( x ), i, j = 1,..., r...

.

, - (1) (...) FN(x) [3, 4]. - - F(x),,...

- 1) M p.

, r = 1, F ( M ) = p ;

[C( M - x ) - p ]dF ( x ) = 0.,, r = 1, y ( x ) = C( M - x ) - p. C(x) ,, : ;

( ).

;

2), F(x) q ;

..,. r = 1, F ( x ) =. [F( x ) + 1 - F( 2q - x )]. = 1 - F ( 2q - x ). F ( x ) =.. F(x)...

FN(x) [5, 6]... F(x), [C( x - y ) + 1, - C( 2q - x - y )] dF( y ) = 0., y ( y, x,q ) = (....) FN(x) FN (x).

- = [C( x - y ) + 1 - C( 2q - x - y )].

- 3),. [a,b],.

2 (110) . 3..,.......:

.. [0,1], N =. 4.. 6.... FN ( x ) b r = 1, dF ( x ) = 1 r = 1, [C( b - x ) - - [5]. a - C( a - x ) - 1]dF ( x ) = 0., y ( y, x, q ) =,....

= [C( b - x ) - C( a - x ) - 1].. 13 FN ( x ) = FN ( x ) F(x), FN(x) - y i ( y )dFN ( y ) L-1 C( x - y )y j ( y )dFN ( y ) (2) FN ( x ) N.

F(x) - |||| , 44, L N Sij(FN), 2 (110). 8.. 10.. 12., r.

FN(x) ... FN ( x ), [5]:

1) ;

FN ( x )...,.. DFN ( x ) DFN ( x ).

2) ;

3) ;

[ ] 4) N FN ( x ) - F ( x ) - (0,sx2),.. [7] s x = F ( x ) - F 2 ( x ) - C( x U = F ( X ). (4) - y )y i ( y )dF ( y ) L-1 C( x - y )y j ( y )dF ( y ). (3) [7], U (3), C( x - [0, 1].

- y )y i ( y )dF ( y ) L-1 C( x - y )y j ( y )dF ( y ) 0,, - (4) 2 (110) . 14.. 16..,.......: 0,5 (M=0,7), N = X=F-1(U). (, - )... F(x) (4), - (, ).

.... FN ( x ).. (4). -.,.

[8] 4.

x [ m ] = x [ m - 1] - g m ( FN ( x [ m - 1]) - U ). (5), N1015, -..., 3..... (. 12, 46, 1012).

(N=100).. [0, 1].. -....... (. 7.. 0 1. 9, 1315).

,.......,,.. ---......., M=0,7 ( [9] [10]. - M=0,5).,..,. 12. ---.

, . - 1/2/, 1, 2 - 1.,.., - /..,.. // 46,. , 1990. . 110112.

2.,.. 10.,.. /..,... . :, 1983. 416.

/.. // : : II..-.. , 2009. . 478481.

3.,.. /... . :, 1984. 472.

4.,.., /... :

-. , 1974. 238.

.

5.,..,,, 2 (110) /..,... :, 1988. 194.

.

6.,... 2.. I.

, /... :, 2004. 216.

, 7.,.., /

..,.. . :, 1976. 320.

.

8.,.. /... . :, 1968. 399. : e-mail: alex_povt@mail.ru 9.,.., 27.09.2011.

/.., . : ..,..,..

, 1987. 334.

51/,.. :

. /... 11-.,.. . :, 2011. 404. ISBN 978-5-9916-1266-1. -978-5-9692-1180-3.

,,,.

.

51/,... :. /.. ;

.

... 8-.,.. . :, 2011. 447. ISBN 978-5-9916-0822-0. -978-5-9692 0970-1.

. .,,.

51/,.. :,, :. /... 5-.,. . :, 2010. 191 c. ISBN 978-5-406-00682-5.

,.,.

531/,.. :. /..,..,.. ;

... . 3-.,.. . :, 2012. 593. ISBN 978-5-9916-1469-6.

(,,,, -, );

, ;

;

...

.. 519. - 2 (110)

. : G2, LS2 AC2. , . AC2.

: , , .

;

;

- - ;

[1]. - ,,, ;

, ,. ;

- , ;

, - [25]., - ;

, NP- ,..

,..

-..,.., C.B., -,..,... -.

, -, [1]. () [1].

, , -,, - m, - n.,. i=1,,m, j=1,,n, k=1,,m. 1. :

i i;

, di i;

qij ,. i ( ). j - i;

. B , (i,j),. i ,, j, Ci i;

, - G=V,E 48 : V E., -..,., -.. H ,, ,. : f -, ;

xik, yjk F S Tijk, Tijk . -..

xik=1, i k - O(nm).

, xik=0 . G2, 2 (110) yjk=1,, k i,, j, yjk=0 .. F S Tijk, Tijk i j, k.,.,.

: f min, G1.

F Tijk f i, k = 1,..., m;

j = 1,..., n ;

3. xik = 1 i = 1,..., m;

k, xik = 1 k = 1,..., m;

xX i A(x) x ik = 1 k = 1,..., m;

k x F S Tijk Tijk + v i qij (xik + y jk - 1) i, k = 1,..., m;

j = 1,..n;

,. TiSj, k + 1 T rjk - H ( 2 - x rk - y jk ) F,,, .

i, r = 1,..., m ;

j = 1,..., n ;

k = 1,..., m - 1;

. TiSj, k +1 Tijk S i = 1,..., m;

j = 1,..., n ;

k = 1,..., m - 1;

, ( x rh - xih ) 0 ( r, i ) E ;

k = 1,..., m;

, h k X, TiSj, k +1 Truk - H( 2 - x rk - y uk ) F,., xij=k, ( r, i ) E ;

j, u = 1,..., n ;

k = 1,..., m - 1;

k i j, i, F Tijk - H (1 - xik ) di i, k = 1,..., m;

j = 1,..n ;

j-, xij=0. :

S Tijk C i x ik ( i, j ) B ;

k = 1,..., m;

1..

2. S Tijk - H (1 - xik ) Ci i, k = 1,..., m;

j = 1,..n;

.

f, Tijk, Tijk R + ;

xik, y jk { 0,1};

i, k = 1,..., m;

j = 1,..., n.

S F. [1],,..,, - ( ),. - LS1,. [1].

. LS1 ( O(m2)), 2. ( O(nm) ), O(nm3).

G1, [1],, -,, n~100, m~10000,. LS2,, -..,, - [6].

G 2 (110) 500 1000 2000 % . % . % . % .

G2 7,5 0 5,0 0.2 3,1 0,5 1,4 1, LS2(G2) 9,7 70 8,0 530 3,6 660 1,5 AC2 11,6 40 9,1 110 4,3 150 2,0 LS2(AC2) 12,4 55 9,6 240 4,5 500 2,1 4..,,. -,, , -,, - ( ), - f_.

., -, [7].,, - f+., - - -,,..

5.

,. -,. - [6]. - G2, G2, LS1, LS2, AC1, AC1. G1, AC2.

LS1 AC1 [1]. - G1 G2. AC2. 20 500, 1000, 2000, - 5000.. 1.

G2, -, G1, G F. fik , G2 0,1%. i k (i=0,,n-1, k=1,,n), i=0 ,., - G2.,, -,.,.

LS. - LS2,, - 1000, 0qQ,. 0sQ q, - , . G1, - 100.

,. LS2 4,4, LS1.

i :, LS2, LS1 0,3 %.

, n i = arg max{( fik )a ( uk ) b | k = 1,..., m}, LS2 k 500, 1000, 2000, 5000.

fik , uk - k, a, b G2,. 500, 1000, 2000, 5000 100, 50, 20, 10.

50 F f0.. 1.

,.

LS2 -., : G2, 500 20% G2 LS2 . AC2., AC2, -.

k, q, -, f0, - 1.,.. f+, 2 (110) f_ /..,.. //.. . :, AC2 2010. 9. . 2933.

- 2.,.. /..,.. 500, 1000, 2000, 5000, -,... . :., 1975. 360.

100, 50, 20, 10 - 3.,.. : a=b=1, k=100, q=10, /.. // f0=mm, f+=10m, f_=0,1m, m .. :

-, 1992. . 94106.

G2 - 4.,.. LS2.. 1. /..,..,, -... :, 1994. 256.

5. Pinedo M. Chao X. Operations Scheduling with Applications - in Manufacturing und Services // Irwin/McGrafHill, 1999.

, LS2(G2). 6.,.. AC2 /.. // LS2(G2)... :

, -, 2011. 10. . 125130.

, 7.,.. AC2. :. /.. LS2,..,... :

-, (AC2), - 2008. 32.

AC2,.

, Intel Core i3 540 3.

-.

: lukyaqnov@mail.ru - 13.02.2012.

- ..

51/,.. :

/.. ;

. :

-, 2011. 82 c. ISBN 978-5-8149-1194-0.

,,., ,.

51/,.. :. /..,..

. 2-. . :, 2011. 479 c. ISBN 978-5-91134-181-7.

,, ;

, .

 
 >>  ()





 
<<     |    
2013 www.libed.ru - -

, .
, , , , 1-2 .