519.852


. .
, .
: , , .
() , , . , :
- ;
- , ;
- ;
- , .
: ; ; , ; . , , . , - .
:
- ( , , , );
402
- ;
- , ;
- (< 30 ) .
, . , . . n . :
- - ;
- - , .
1. . [1]
n n n
f (x) = Xcjxj + XX dkjxkxj (1)
j=1 j=1k=1
:
n
Xai jxj < bi, i = 1,2,...,m, (2)
j=1
xj = 0,1,2,..., j = 1,2,...,n, (3)
D = [dkj ] - n, A = [ai j ] - n x m; C = [c j ] B = [bi ] - n m .
u j ((j = 1, ..., n)
(2), (3):
n
uj = max X dkjxk, (4)
k=1
g(x) ,
n
n n
f(x) = X CjXj + X j=1 j=1
n
X dkjxk k=1
() = X + uJ)VxJ (5)
j=1
X = { xj, ] = 1,2,..., },
(2), (3), () > ^),

VxJ XcJxJ + X 1 J=1 j=1
(4), (2),
Xj > 0, j = 1,2,..., . (6)
- ( ) (4), (2), (6) , , , .
(4), (2), (6) -
:
m
uq = min X biYi, (7)
i=1
m
X ai kYi > dk q 5 k = 1,2,...,n, (8) i=1
yi > 0, i = 1,2,..., m. (9) (7)-(9) :
10. p(r) = bi, k = 1, 2,... - -
X ai k
kEl(r)
; I(r) - (8), ( r = 1 I(1) ={ k = 1,2,...,n }).
20. y(r), d(r) = min p(r).
i
m+nr-1 (,)
dk q - X Xai kye)
30. yer) = min-i 1 t 1
k ae k
40. I(r) , r = n. , r = r + 1 . 10, - . 50.
0 (r) m
5 . yj = X - , i = 1,2,...,m uq = X;;.
t =1 j i=!
, .
, n (7)-(9) Uj (5). .
Hsi(xj) = Csi(xj) + Zsi(xj),
Csl(xl) = X cjxj + X X dklXkXi - 1-
j e si j k e si
(1)-(3); Si ={ (kj), j = 1,2,..., l; 0 < l < n } -
(1)-(3), l- . ZSl (xl ) .
, (5), (2), (3) . . Zs1(xi)
-
m l
Zs1(xi) = X--, Y = (1,2, . ,) - i=1 j
(5), (2), (3) , 1 = bj - X aijxj, i = 1,2,...,m.
jeSl

s1 Hsl(xi) = max Hsi(xk).
k
Hs1 < C0, - .
, : cj pkj (j = 1, ..., m, k = 1, ..., n) -
, [0, 100], a^
(i = 1, ... , m, j = 1, ... , n) - , [1, 50]; -

(i = 1, ..., m). -

X,2X

10 10(20, 30, 40) 1(2,3) . . . , .
2. .

f () = X]] + XX ]] , (10)
]=1 j=1k=1
:

X! jXj 1 = 1,2,...,, (11)
j=1
Xj = {0,1}, ] = 1,2,...,, (12)
= [) ] - , = [! j ] - ; = [] ] = [ ] -
n m .
xj = xj xj = {0,1}, (10) , (10) . j = 1, ..., n uj :
n
uj = max X PkjXk, j = 1,2,...,n, (13)
k=1
(11)-(12).
g(x) ,
n
g(x) = X uj(xj). (14)
j=1
X = { xj, j = 1,2,...,n }, (11)-(12), g(x) > f(x), n
. u j
n
f (x) = X j=1
X Pkjxk k=1
(14) (13), (11),
0 < xj < 1, j = 1,2,...,n. (15)
- (n ) (11), (10), (15) , (14), , . (13), (11), (15) j = ( = 1, ..., n) :
, m m+n
uq = min X biYi + X yi, (16)
i=1 i=m+1
m
X ai kyi + ymk > Pk q , k = (17)
i=1
yi > 0, i = 1,2,...,m + n. (18)
, n (16)-(18) u j (14). .
, (14), (11), (15) , :
Z = min
:
^ m m+n ^
X bi yi + X yi
V i=1 i=m+1 )
(19)

X + +] > ] , ] = 1,2,...,, (20)
1=1
1 > 0, 1 = 1,2,..., . (21)
: = {11,12, . , 1, . , 1} - , , (20), - (19)-(21); 0 = ^1, = 0,1,...,, 1 = 1,2,..., + } - , - (19)-(21) ] = 11,12,. ., 1 ; $ = 81 80 - , - ( 81 = {] = 1}} = { ] = 0}).
(19)-(21) (10)-(12) -
, : 10.
_
Z aij
dj _ , i = 1,2,...,m + n, bm+j _ 1,2,...,n.
k =1, 2, ... - , Ik - (17), (i1 _ {1,2,...,n}).
20. yk, -
k k dr _ min di
30. y (n - k + 1)-
m+n k-1 ,
uj- Z Z aijyi
yk _ min-i_1 i_1-,
j arj
y0 _ 0, i =1, ..., m+k. iq, yk, x-k, (n - k + 1)- , P(k) _ i q .
40. k- Q: qki _ qk-1,i + yk, i = 1,2,...,n + m, qoj _ 0, i = 1,2,..., m + n.
50. ik , (20). k = n, , k = k+1 . 10, - . 60.
k k m+n
60. - _ Zyj, i = 1,2,...,m + n. Z_ Zbjyj + Zyi.
j_1 i_1 i_m+1
, , (10)-(12) xin ,
xjn 1 . . x-k (k = n,
m m+n
n -1, ..., 2) H(xjk) _ Z Z Pkj + Zb qki + Z qki,
bW _ bj - Z ajj, i = 1,2,...,m.
k, jeSj i _1 i_m+1
ij 1=10 m
(1) < 0, 0 - . , . . 0 =
408
0.
: | |
( =1, ..., , = 1, ..., ) - , (0, 100), (1 = 1, ..., , | = 1, ..., ) -
(1, 50).


n
1, Z a
jj

(i = 1, ..., m).
j=1
, 10 , n > 40 1,1-3,2 . .
3. .
(1)-(3) , :
1) () q(x), , q(x) < f(x) X, (2),(3);
2) q(x). i = 1, ..., M uj
:
N
uj _ minZbix-i, (22)
l_1
(2), (3). q(x)
M N
q(x) _ ZZ u jb jx-j, (23)
i_1j_1
X _ {xjj,i _ 1,2,..., M, j = 1,2,..., N} (2),(3) q(x) < f(x). uj (23) uj _ min{bl,l _ 1,2,..., N}.
(23), (2), (3) q(x) . . N- . -
409
: ^ (°0,],...,0,] )= 1{0,] (0,1,...,0,1)+ ]}
0 0] ^ 1 = 1,2,...,, 1] +, 0 ^ +, 1 = 1,2,...,, 1] -,
(24)
(25)
+,- - , - .
(24) (25) , , 1 = 1, .., .
(24) 1 = 1, /0 (1 ) 1 (/0 ), = 1, ...,
N. 1 (/0 )
} (/0), 1 = 2, .., .
/0 ( ) 1 (/0 ), 1 = 2, .., ,
/0 ( ) = , (2) 1 = 1
/0(1 ) = ^, (2) 1 = 1, ..., .
11 = 12, ;, = 1, ..., N 11, (23),(2), (3), (11 > 12), , (25) 1 = 2.
1 = 2, .., . - :
1{/0,,...,05,]+ Fn,N[(01 -&0,)..., (_1 -^-1)] }< ,
= 1,2,...,N = 3,5,7,..., = 1{12,22,..., -12 } (24)
,0 1 ^-1,0

^..... & ]+ /0, [(, - }.., ( -1 - -1'0)] }<
= N,N -1,...,1, = 2,4,6,...,... (25). (2), (3), (13) , , (23).
(1)-(3) -
:
10. / = / (0) = g(Xo) (1). ^ = , 0 - (1)-(3), 0 - (1)-(3), 0 - (13), (2), (3); . 20.
20. 1, 1 = 1, ..., . g(X1) > ^ , 3 .
30. . ^; ) < ^ , ^ = ^;) ; - (1)-(3). . 20.
, . , : |, I = 1, ..., N - [1, 10]; I = 1, ...,
, = 1, ..., - [1, 50]; . 1 1, 1 = 1, ..., , = 1, ..., -
' N . 1=1

N
1,1|
|=1 .
, , 1 . .
, . .

1. .., . ., .., .. . .: - , 1997. 249 .
, - . , ., kiselevvd@yandex.ru, , ,
METHODS AND ALGORITHMS OF THE SOLUTION OF PROBLEMS OF INTEGER SQUARE PROGRAMMIRO-VANIYA ON THE BASIS OF LINEARIZA TION OF CRITERION
FUNCTION
V.D. Kiselev
The effective methods of the decision of the general of tasks and TsKP and problem of TsKP with Boolean variables based by N of linearization of criterion function with use of the theory of a duality are considered.
Key words: integer square programming, theory of a duality, criterion function.
Kiselev Vladimir Dmitrievich, doctor of technical science, professor, kise-levvd@yandex. ru, Russia, Tula, Tula State University
681.3
-
. . , .. , .. , . .
, 1- . , - !-.
: -, , .
- , , , -, , , [1, 2, 3].
, - - . , : -