Використання методу гілок і границь для розв’язання задачі дискретної оптимізації з метою вибору оптимальної регресійної моделі
Article suggests a stochastic method of leaps and bounds to solve a discrete optimization task for the optimum regression model choice with minimax function of model quality. For partition of a current set of task solutions into parts of branching subsets, the dichotomy principle is used. For a bran...
Gespeichert in:
| Datum: | 2009 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
2009
|
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/16985 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Використання методу гілок і границь для розв’язання задачі дискретної оптимізації з метою вибору оптимальної регресійної моделі / І.М. Мельник // Індуктивне моделювання складних систем: Зб. наук. пр. — К.: МННЦ ІТС НАН та МОН України, 2009. — Вип. 1. — С. 131-139. — Бібліогр.: 4 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-16985 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-169852011-02-18T12:07:03Z Використання методу гілок і границь для розв’язання задачі дискретної оптимізації з метою вибору оптимальної регресійної моделі Мельник, І.М. Article suggests a stochastic method of leaps and bounds to solve a discrete optimization task for the optimum regression model choice with minimax function of model quality. For partition of a current set of task solutions into parts of branching subsets, the dichotomy principle is used. For a branching subset, the lower estimation is calculated for the goal function of the optimum model. The choice of a current subset of the branching process is carried out by a stochastic procedure. 2009 Article Використання методу гілок і границь для розв’язання задачі дискретної оптимізації з метою вибору оптимальної регресійної моделі / І.М. Мельник // Індуктивне моделювання складних систем: Зб. наук. пр. — К.: МННЦ ІТС НАН та МОН України, 2009. — Вип. 1. — С. 131-139. — Бібліогр.: 4 назв. — укр. XXXX-0044 http://dspace.nbuv.gov.ua/handle/123456789/16985 519.1 uk Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| description |
Article suggests a stochastic method of leaps and bounds to solve a discrete optimization task for the optimum regression model choice with minimax function of model quality. For partition of a current set of task solutions into parts of branching subsets, the dichotomy principle is used. For a branching subset, the lower estimation is calculated for the goal function of the optimum model. The choice of a current subset of the branching process is carried out by a stochastic procedure. |
| format |
Article |
| author |
Мельник, І.М. |
| spellingShingle |
Мельник, І.М. Використання методу гілок і границь для розв’язання задачі дискретної оптимізації з метою вибору оптимальної регресійної моделі |
| author_facet |
Мельник, І.М. |
| author_sort |
Мельник, І.М. |
| title |
Використання методу гілок і границь для розв’язання задачі дискретної оптимізації з метою вибору оптимальної регресійної моделі |
| title_short |
Використання методу гілок і границь для розв’язання задачі дискретної оптимізації з метою вибору оптимальної регресійної моделі |
| title_full |
Використання методу гілок і границь для розв’язання задачі дискретної оптимізації з метою вибору оптимальної регресійної моделі |
| title_fullStr |
Використання методу гілок і границь для розв’язання задачі дискретної оптимізації з метою вибору оптимальної регресійної моделі |
| title_full_unstemmed |
Використання методу гілок і границь для розв’язання задачі дискретної оптимізації з метою вибору оптимальної регресійної моделі |
| title_sort |
використання методу гілок і границь для розв’язання задачі дискретної оптимізації з метою вибору оптимальної регресійної моделі |
| publisher |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| publishDate |
2009 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/16985 |
| citation_txt |
Використання методу гілок і границь для розв’язання задачі дискретної оптимізації з метою вибору оптимальної регресійної моделі / І.М. Мельник // Індуктивне моделювання складних систем: Зб. наук. пр. — К.: МННЦ ІТС НАН та МОН України, 2009. — Вип. 1. — С. 131-139. — Бібліогр.: 4 назв. — укр. |
| work_keys_str_mv |
AT melʹnikím vikoristannâmetodugílokígranicʹdlârozvâzannâzadačídiskretnoíoptimízacíízmetoûviboruoptimalʹnoíregresíjnoímodelí |
| first_indexed |
2025-07-02T18:17:47Z |
| last_indexed |
2025-07-02T18:17:47Z |
| _version_ |
1836560173239369728 |
| fulltext |
,
2009 131
519.1
. .
-
,
astrid@irtc.org.ua
.
-
.
.
.
: , , -
, ,
,
.
Article suggests a stochastic method of leaps and bounds to solve a discrete optimization task for
the optimum regression model choice with minimax function of model quality. For partition of a
current set of task solutions into parts of branching subsets, the dichotomy principle is used. For a
branching subset, the lower estimation is calculated for the goal function of the optimum model.
The choice of a current subset of the branching process is carried out by a stochastic procedure.
Keywords: optimum regression model, discrete optimization, method of leaps and bounds, branch-
ing subset, goal function.
.
-
.
. -
.
:
,
,
,
, , .
, , -
. , ,
-
, -
, , . -
.
,
.
2.
-
. -
. .
132
,
2009
[1]
1960 .
-
.
, ,
[2],
-
. ,
-
.
, -
,
,
.
-
( -
).
( ) ,
.
(
)
.
, ( ) -
.
-
. -
( ) , -
, -
. , , -
, ,
.
, .
(
) ,
-
.
( ,
),
. -
. . , ,
( )
.
-
,
.
. n - -
nR
( ) ),( yx , x
y
-
nR [3],
X
nR .
X
, -
Xxx, , 0)(x
,
y
,
2009 133
X
)(),( xyx . -
X
( ) X , -
.
)(xF
X , m -
mR . )(F
-
X
nR
W
m -
mR . )(F
-
W
X .
- x
y
X
:
1) x
y ( x y ), )(xF )(yF ;
x
y ( x
y ), )(xF
)(yF ;
2) , y
x
( y x ), )(xF )(yF ;
y
x ( y x ), )(xF )(yF .
3) x
y
(
), )(xF )(yF ( x y ), )(xF )(yF ( x y ).
X
dX
( dX X ), -
X .
dX
,
dX
( dXX \ )
, .
)(xF
( mR
, m
>1), dX -
)(xF
X .
)(xF
x
,
, )(F
W
-
X . dX
-
)(xF
X .
dX
( ) )(xF
-
( ), X
, -
)(xF
dX .
:
( ) )(xF , x
X , :
)(xF
min , (1)
Xx , (2)
X
- .
.
. .
134
,
2009
3.
,
, ,
. -
NP - .
.
, n
( ) ni xxx ...,,...,,1 ( ) -
y , m
. -
, -
( ). )(F , -
, .
.
mS ...,,1 . -
( ) }...,,...,,{ 1 ni xxx . -
ii xay , -
, -
, ia .
J
,
-
nI ...,,1 , },...,1{ nIJ .
)(JF
:
Ji
l
ii
l
Sl
xJayJF 2))((max)( , (3)
1| XxiJ i
I ,
1X
,
, ,),( JiJai
,
1X . (3) -
-
y
k -
, Sk ,
1X . ,
*J
I , IJ * , (3),
Ji
l
ii
l
Sl
xJayJF 2))((maxmin*)( , (4)
J
I .
[4]
,
2009 135
),( UI .
I
.
nixi ...,,1, , i .
: 0 1n . U
:
0
)...,,1( ni
),0( i ,
ijj, , ),( ji .
0
1n
, , -
ix , ),( UI ,
.
0
1n
-
,
)(F . ,
( )
0
1n
),( UI .
[4]
.
4.
-
.
, ,
-
.
( )
( ) , ,
.
n
,
n
-
. k - ( nk ,...,1 )
( )
.
, k - -
. (3)
( ) . k - -
: },...,1,{ nkkJ k
( },...,1{ nIJ k ). kJ -
k - , -
kJ , ,
},...,,{},{ 1 nkkkik xxxJixX .
)(JR
-
(3)
k - ,
kX ,
:
. .
136
,
2009
kJi
l
iki
m
l
l
k knxJayJR )1/()))((()( 2
1
. (5)
, )( kJR
)( 1
kk XXF , ,
1
kX kX
)()( 1
kk XRXF .
.
, )(JR
-
(
).
, -
n
-
. k -
-
k -
kI
( nk ,...,1 ).
k -
kI ( nk ,...,1 )
, ' 0, kk
( kx ), , , ix ,
k
( i
> k ). ,
I -
n
kI (
n
),
.
k -
kI ( nk ,...,1 ).
( ) kI
( ). 1
kI ,
( ,...1,kk ), ( ,...2, kk ),..., ( ],...2/)[(, knkk ),
]2/[( kn
2/)( kn . 2
kI
,
( ,...1]2/)[(, knkk ),
( ,...2]2/)[(, knkk ), ( ,...3]2/)[(, knkk ),..., ( ,...2,nk ), ( ,...1,nk ),
( ), nk ). ]2/[( kn
p , p
= ]2/[( kn .
(5), 1
kI
)1(
1R .
1
kI (5) :
pk
ki
l
iki
l
m
l
k pxIayIRR )1/())((()( 21
1
1)1(
1 , (5 )
),( 1
ki Ia pkkki ,...,1, ,
-
},...,,{ 1 pkkk xxx .
(5)
2
kI
)1(
2R .
,
2009 137
(5) :
n
pki
l
iki
l
m
l
k pknxIayIRR
1
22
1
2)1(
2 )/())((()( , (5 )
)( 1
ki Ia , .,...,1 npki ,
},...,{ 1 npk xx .
1
kI 2
kI
. 1
kI )1(
1P = )/( )1(
2
)1(
1
)1(
2 RRR ,
2
kI , ,
)1(
2P = )/( )1(
2
)1(
1
)1(
1 RRR . ,
( 1
kI 2
kI ) .
. -
, -
1
kI .
: 11
kI
12
kI . -
11
kI ( ,...1,kk ), ( ,...2, kk ),..., ( ]2/[, pkk ),
12
kI
-
( ,...1]2/[, pkk ), ( ,...2]2/[, pkk ), ..., ( pkk, ).
(5), (5 ) (5 )
. 11
kI 12
kI
)2(
1R
)2(
2R .
-
( 11
kI 12
kI ) -
: )2(
1P = )/( )2(
2
)2(
1
)2(
2 RRR
11
kI )2(
2P = )/( )2(
2
)2(
1
)2(
1 RRR
12
kI .
-
( 11
kI 12
kI ) -
.
-
. -
,
-
, , -
( ).
(3)
.
-
-
.
,
( ) , -
.
, -
. .
138
,
2009
, ,
-
.
-
,
,
. -
, , -
.
, - -
, , -
, ( )
,
,
.
,
.
-
, ,
.
-
. , ,
, -
.
k - -
.
n
, 1k ,
2k , , nk . ,
,
.
( -
),
.
. , -
,
.
.
-
, ,
. ,
.
-
,
.
,
-
( )
( -
) , .
,
-
, -
,
2009 139
, .
,
. , , -
.
-
, ,
(5 ) (5 ). ,
, , -
.
,
, -
.
.
-
,
, -
,
( -
) -
,
.
5.
-
. -
.
. -
.
, .
1. Land A.H., and Doig A.G. An automatic method of solving discrete program-
ming problems. Econometrics. V. 28 (1960), pp. 497-520.
2. Little J.D.C., Murty K.G., Sweeney D.W., and Karel C. An algorithm for the
traveling salesman problem. Operations Research. V. 11 (1963), pp. 972-989.
3. . . , . . . -
. , , 1976. - 544 .
4. . . -
//
. 2008. - 3. c.30-43
|