38.2 Modified Han Algorithm
In order to present Han’s algorithm together with its modified version proposed by
Carp et al. (2015), we first reformulate the problem (38.1), (38.2), (38.3) and (38.4).
In this respect, first we renumber the unknowns as
x ij ! y l , i 2 1; . . . n
f
g, j 2 1; . . . m
f
g, l 2 1; . . . mn
f
g
ð38:6Þ
Let now c 2 ℝ
mn be the cost vector of the above problem, B 1 , B 2 the m  mn,
n  mn matrices corresponding to the m inequalities from (38.2) and the n equalities
from (38.3), respectively. Moreover, let d 2 ℝ
m , s 2 ℝ
n be the demands and supplies vectors, respectively (see Table 38.1). Then, the problem (38.1), (38.2), (38.3),
and (38.4) can be written as
min c; y
h i s:t: B 1 y ! d, B 2 y ¼ s, y ! 0
ð38:7Þ
If we define the (m + 2n) Â mn matrix B and the vector δ 2 IR
m + 2n by
B ¼
B 1
B 2
ÀB 2
2
4
3
5 , δ ¼
d
s
Às
2
4
3
5 ,
ð38:8Þ
the problem (38.7) becomes
min c; y
h i s:t: By ! δ, y ! 0,
ð38:9Þ
together with its dual
max δ; u
h i s:t: B
T u c, u ! 0:
ð38:10Þ
Let P, D the set of feasible solutions of the primal (38.9) and dual (38.10)
problem, respectively. The following result (see for the proof Andrei 2011, page
181) connects this pair of problems to a system of linear inequalities
Proposition 38.1 Let us suppose that both problems (38.9)–(38.10) have feasible
solutions, i.e.P 6 ¼ ∅ , D 6 ¼ ∅ Then the following assumptions are equivalent:
(i) b y 2P, b u 2D are optimal solutions for problems (38.9) and (38.10), respectively.
(ii) the vector x ¼ b y
T
; b u
T
½
T 2 ℝ
mÂn is a solution of the system of linear inequalities
Ax b,
ð38:11Þ
where
38 Genetic Versus Han-Type Algorithms for Maritime Transportation Problems
633
In order to present Han’s algorithm together with its modified version proposed by
Carp et al. (2015), we first reformulate the problem (38.1), (38.2), (38.3) and (38.4).
In this respect, first we renumber the unknowns as
x ij ! y l , i 2 1; . . . n
f
g, j 2 1; . . . m
f
g, l 2 1; . . . mn
f
g
ð38:6Þ
Let now c 2 ℝ
mn be the cost vector of the above problem, B 1 , B 2 the m  mn,
n  mn matrices corresponding to the m inequalities from (38.2) and the n equalities
from (38.3), respectively. Moreover, let d 2 ℝ
m , s 2 ℝ
n be the demands and supplies vectors, respectively (see Table 38.1). Then, the problem (38.1), (38.2), (38.3),
and (38.4) can be written as
min c; y
h i s:t: B 1 y ! d, B 2 y ¼ s, y ! 0
ð38:7Þ
If we define the (m + 2n) Â mn matrix B and the vector δ 2 IR
m + 2n by
B ¼
B 1
B 2
ÀB 2
2
4
3
5 , δ ¼
d
s
Às
2
4
3
5 ,
ð38:8Þ
the problem (38.7) becomes
min c; y
h i s:t: By ! δ, y ! 0,
ð38:9Þ
together with its dual
max δ; u
h i s:t: B
T u c, u ! 0:
ð38:10Þ
Let P, D the set of feasible solutions of the primal (38.9) and dual (38.10)
problem, respectively. The following result (see for the proof Andrei 2011, page
181) connects this pair of problems to a system of linear inequalities
Proposition 38.1 Let us suppose that both problems (38.9)–(38.10) have feasible
solutions, i.e.P 6 ¼ ∅ , D 6 ¼ ∅ Then the following assumptions are equivalent:
(i) b y 2P, b u 2D are optimal solutions for problems (38.9) and (38.10), respectively.
(ii) the vector x ¼ b y
T
; b u
T
½
T 2 ℝ
mÂn is a solution of the system of linear inequalities
Ax b,
ð38:11Þ
where
38 Genetic Versus Han-Type Algorithms for Maritime Transportation Problems
633