close

Вход

Забыли?

вход по аккаунту

?

Исследование декомпозиционного подхода для двухстадийной задачи размещения.

код для вставкиСкачать
.
.
-
. 2010.
4.
. 24?31.
519.8
. .
, . .
, . .
.
. .
. .
*
,
(
-
).
.
-
.
,
.
:
,
,
,
L-
,
,
.
-
,
,
,
[1�.
.
,
-
.
,
.
,
,
.
,
,
. .
,
,
.
,
p-
-
,
,
(
.,
, [4�]).
.
*
� . .
10-01-00598
, . .
, . .
, 2010
-
...
25
L
-
,r
1,
�
;
,
[12, 13].
,
-
.
(
,
,
).
L-
.
1,
di
;
0 �
, i
cl
l
G �
, l
i
L;
-
gil
l
I;
-
;
,
i
0,
1,
gil
,
I,l L ;
tij �
-
,
,n �
i
0 �
-
[1, 14�].
-
p-
J
-
j
i, i
I, j J.
z : zi 1 ,
.
i
1.
[8].
,
,
.
,
(
)
(
-
),
zi
,
-
-
0, i
I.
yl
, l
, xij
xij
1,
, i
0
I, j
L.
i
j,
J.
-
.
(
-
)
(
.
M1)
-
,
.
.
:
F z, y, X
cl yl
di zi
l L
i I
tij xij
,
min
(1)
J,
(2)
i I j J
.
xij
-
,
zi
xij , i
yl
gil zi , i
I,l
xij , yl , zi
0,1 , i
I, j
.
,
1, j
i I
I, j
J,
(3)
L,
J ,l
:
1,
,m
L.
(5)
-
.
I
(4)
�
(2)
-
.
;
.
,
(3)
. .
26
.
(4)
, . .
. .
-
,
-
,
.
1.
-
.
[8]
,
-
(3)
yl
gil xij , j
J ,l
L
DM 1
.
,
,
, (1)�(3), (5), (6),
,
j0
J,
-
gi0l0
1
0 0
-
.
00
1, . .
i0
).
.
( x, y , z ) .
l0 L , i 0 I ,
0
gi0l0 xi l 1 .
yl0
xi j
-
(6)
,
-
( 2).
,
.
(6)
.
DM 2 .
( z , y, x ) DM 1 ,
.
(2), (3), (5)
(6)
i I
(
,
j0 .
(3)
,
-
i0
G, . .
gil
1, i
l, i
I,l
L.
,
.
-
yl0
gi0 j0 zi0
1.
1.
-
yl0
0.
, yl0
1,
.
,
G,
,
.
,
-
,
G
,
-
DM 1 DM 2 .
,
.
,
-
,
. zi0
(4)
,
.
.
,
,
PM1
,
PM2
.
-
.
2.
:
xij
0 ,1
yl
0 , zi
0 ,i
I, j
J ,l
L. (7)
(1)�(5)
[12].
,
(2)�(4)
(
(7).
�
PM1
(1)�(5), PM2 �
M2; DM1, DM2 �
,
),
).
(
(
-
).
-
.
.
...
27
wil
-
.
sl
cl , l
L,
i I
vij , wil , sl
0, i
I, j
,
J ,l
L.
(9)�(14)
.
y
.
,
y
,
tij xij
min
i I j J
xij
,
,
LP1
x:
z.
-
,
z
,
-
z
:
1, j
J,
i I
-
.
,
xij
zi , i
I, j
J,
xij
0, i
I, j
J.
y:
LP2
,
-
cl yl
[17].
min
l L
-
M1.
yl
g il zi , i I , l L ,
yl 1, l L ,
yl 0, l L .
z,
z
ri i
r 0,
r 1,
, ,
(8)
D(z),
-
u
(9)�(12),
D1
i I
zi
0,1 , i
I,
.
(8) �
,
,
�
uj
.
z,
,
l L
min
-
tij , i
vij
(9)
0, i
I, j
I, j
J.
w:
g il z i wil
1, j
J,
D2
i I j J
xij
max
i I j J
u j vij
tij xij
:
zi vij
j J
LP(z):
cl yl
v
J,
(10)
i I l L
sl
max
l L
i I
xij
zi , i
I, j
J,
wil
(11)
yl
g il zi , i I , l L ,
yl 1, l L ,
xij 0, i I , j J .
sl
cl , l
L,
0, i
I,l
L.
i I
(12)
wil , sl
(13)
(14)
LP1
LP(z)
,
D1, D2
LP2.
-
D(z):
uj
j J
zi vij
,
2
i I j J
gil zi wil
i I l L
sl
2.
max
l L
tij , i
I, j
J,
-
x
LP1,
u j vij
-
,
3.
-
. .
28
D1
, . .
,
tij ,
xij
0,
;
I, j
i
zi
yl
0,
xij
uj
yl
J.
cl
cl .
wil
sl
.
,
-
-
0 cl .
,
:
.
L1 {l
L | yl
I1l
1} ,
{i
I | gil zi
1} .
.
:
cl .
l L
max{0, u j tij } .
l L1
D2
gil zi wil
sl
i I l L
tij ,
uj
-
LP2
cl yl
wil
i I1l l L1
l L
cl .
l L1
,
max{0, u j tij } u j
uj
sl
0
0,
uj
2)
D2.
i I
max{0, u j tij } :
uj
wil
1,
max{0, tij tij } tij 0 tij .
uj
1)
L
1,
tij
u j vij
cl , l
i I
.
u j vij
sl
i I
.
xij
-
wil
1;
max{0, u j tij },
vij
. .
.
:
uj
,
0 uj
-
.
tij ;
.
M1.
tij ,
max{0, u j tij } u j u j tij
: P
tij .
(k )
�
-
k-
,
(k )
, z
.
; LP ( z
,
(k )
�
(k )
�
-
) �
,
.
LP1:
tij xij
( i , j ) {( i , j )| xij 1}
D1
uj
zi vij
uj
i I j J
j J
(k )
(y , x ) �
D( z (k ) ) �
F (0) �
tij .
i I j J
j J
(k )
:
LP( z )
(k )
�
0. (
.
3.
.)
LP2,
F (0)
.
P (1) :
D2
,
:
cl ,
0,
-
-
y
wil
k-
.
-
.
(1)
sl
;
-
, F
{tij | xij 1} .
i, j
,
;
(k )
0;
argmin{k | yl
,
-
:
g kl zk
1,
z
1},
ri i
r 0,
r 1,
, ,
(15)
i I
;
zi
i
I,l
I.
(15)
L.
.
,
-
,
,
0,1 , i
.
,
�
.
k, k 1.
-
...
29
,
,
P(k )
1.
L-
.
,
-
,
F
( k 1)
-
,
.
(
,
.
-
L-
c
,
[14]),
.
2.
,
-
,
LP( z ( k ) ) .
.
F (k )
min{F ( k 1) , F ( z ( k ) , y ( k ) , x( k ) )} .
F ( k ) F ( k 1) ,
F ( k 1)
F (k )
P(k ) .
LP ( z ( k ) )
D( z ( k ) ) .
,
-
.
.
-
3.
-
(k)
(k)
(k )
u ,v , w , s
(k )
3.
[16].
-
(
i I
F
,
gil wil( k ) )zi
j J
(k )
l L
(k )
u
-
(16)
):
vij( k )
( di
(k)
j
(k )
l
s
j J
.
.
(16)
-
l L
P(k
4.
z,
( k 1)
.
.
1)
.
:
-
I0 �
, I1 I \ I 0 �
( k 1)
,
(k )
-
.
,
-
-
,
i I1
(16).
(
I1
-
,
1).
(0)
zi
,
.
,
.
-
(16)
,
.
-
0.
:
-
1.
-
,
,
.
Q
,
(15).
,
,
,
,
.
�
T
�,
q
q
Q
Q
q
Q
Q
Q
Q
q
,
0.
-
c
I
J
(Q q,
, Q q) .
n.
.
. .
30
, . .
-
(Q q ) ,
-
zi
1.
.
p
(k )
z ,
-
.
z( p) .
,
.
-
,
z( p)
:
F ( z ( p), X ) p (Q q ) pq
(n p)Q nQ .
(k )
i I
,
-
u? j .
j J
.
,
j J
LP1,
q,
Q,
j
I0 , j
-
,
�
(http://math.nsc.ru/AP/
�
benchmarks/).
.
i
.
-
I1 ,
Q q,
i,
,
.
0,
.
.
F
,
,
F?
v?ij )zi
.
,
[14]:
vij
p.
i I1
-
z,
( di
. .
,
4.
uj
,
uj
pc
pq (n
(n
p )Q
p )Q
-
pq
,
j J
,
pc
p (Q q ) .
.
-
.
,
.
-
�
-
.
(ci
vij ) zi
i I
(ci
j J
vij ) zi
i I1
j J
(ci
(ci
i I0
vij ) zi
i I1
vij ) zi ;
.
j J
(Q q 0) zi
j J
i I1
[1]
. .,
(Q q) zi ;
(ci
vij ) zi
j J
(Q q (Q q)) zi 0 .
(Q q) zi
. .
, 1978.
.
:
160 .
[2]
. .,
. .,
.
i I0
:
i I1
. .,
-
i I1
i I0
-
p (Q q )
. .
-
, 1978. 335 .
[3] Cornuejols G., Fisher M. L., Nemhauser G. L.
Location of Bank Accounts to Optimize Float:
An Analytic Study of Exact and Approximate
Algorithms // Management Science. 1977.
Vol. 23. P. 789?810.
...
[4] Krarup J., Pruzan P. M. The simple plant location
problem: survay and synthesis // European J.
Oper. Res. 1983.
12. P. 36?81.
[5] Sridharan R. The capacitated plant location problem // European Journal of Operational Research.
1995. Vol. 87. P. 203?213.
[6] Discrete Location Theory / Ed. by Pitu B. Mirchandani and Richard L. Franscis, by John Wiley
and Sons, Inc. 1990. 576 p.
[7]
. .,
. .,
. .,
. .
.
:
. - , 1996. 167 .
[8]
. .
.
:
, 2005.
450 .
[9]
. .
.
. . : 1987. 64 .
[10]
. .
//
(
'96) :
.
..
.
, 1996.
. 44?47.
[11]
. .,
. .,
. .
31
//
-
. 2009. . 49.
6. . 1055?1066.
[12] Benders J. F. Partitioning Procedures for Solving
Mixed-variables Programming Problems // Numer. Math. 1962. 4.
3. P. 238?252.
[13] Magnanti T. L., Wong R. T. Accelerating Benders
Decomposition: Algorithmic Enhancement and
Model Selection Criteria // Oper. Res. 1981.
Vol. 29. 3. P. 464?484.
[14]
. .,
. .
L//
- .
:
, 1996.
1. C. 21?
23.
[15] Kolokolov A. A. Decomposition Algorithms for
Solving of some Production-Transportation Problems // Triennal Symposium on Transportation
Analysis II. Preprints. Vol. 1. Capri, Italy. 1994.
P. 179?183.
[16]
. .,
. .,
. .
//
.
2005.
2(31). . 76?80.
[17]
. .
.
:
, 1988. 472 .
Документ
Категория
Без категории
Просмотров
5
Размер файла
1 993 Кб
Теги
размещения, декомпозиционные, двухстадийной, подход, исследование, задачи
1/--страниц
Пожаловаться на содержимое документа