Geoscience Reference
In-Depth Information
A solution to L
SFLP
./ can be obtained applying the following two steps:
(1) For each i
2
I solve the knapsack problem
KP
.i/
W
maximize
X
j2J
c
ij
j
x
ij
(3.28)
subject to
X
j2J
d
j
x
ij
q
i
(3.29)
x
ij
2f
0;1
g
j
2
J:
(3.30)
Let J.i/ denote the index set of variables at value 1 in an optimal solution to
KP
.i/ and v.i/
D
P
j2J.i/
.c
ij
j
/ its associated optimal value.
(2) For each i
2
I, with f
i
C
v.i/ < 0 then y
i
D
1,andx
ij
D
1,forj
2
J.i/.
The Lagrangean dual associated with L
SFLP
./ is
D
SFLP
2
R
n
L
SFLP
./:
max
Proposition 3.1
The optimal value of the Lagrangean dual
D
SFLP
coincides with
the value of the linear programming (LP) relaxation of program SPSFLP.
Proof
Consider the following Lagrangean function resulting from relaxing con-
straints (
3.20
)in
SPSFLP
in a Lagrangean fashion:
0
@
1
X
i2I
1
L
SPSFLP
./
D
minimize
X
i2I
X
p
ki
z
ki
C
X
j2J
X
A
j
a
ijk
z
ki
k2K
k2K
i
(3.31)
X
subject to
z
ki
y
i
i
2
I
(3.32)
k2K
i
z
ki
0
i
2
I; k
2
K
i
(3.33)
y
i
2f
0;1
g
i
2
I:
(3.34)
The objective function (
3.31
) can be expressed as
2
4
X
i2I
3
X
X
p
ki
z
ki
X
i2I
X
X
5
D
j
C
min
j
a
ijk
z
ki
j2J
k2K
i
k2K
i
j2J
2
4
X
i2I
3
X
X
.p
ki
X
j2T
k
5
:
j
C
min
j
/
z
ki
j2J
k2K
i
