Information Technology Reference
In-Depth Information
t S r ʔ 2
m ( r , t ) · ( s S x s , r ) ·
y r , t
ʔ 2 ( r )
= m ( ʔ 1 , ʔ 2 ) +
t S r ʔ 2
y r , t
ʔ 2 ( r )
m ( ʔ 1 , ʔ 2 )
=
+
m ( r , t )
·
ʔ 2 ( r )
·
t S r ʔ 2
= m ( ʔ 1 , ʔ 2 )
+
m ( r , t )
· y r , t
t S r S m ( r , t )
m ( ʔ 1 , ʔ 2 )
=
+
·
y r , t
m ( ʔ 1 , ʔ 2 )
m ( ʔ 2 , ʔ 3 ) .
=
+
m coincides with m .
Proposition 3.7
ˆ
Proof
The problem in ( 3.7 ) can be rewritten in the following form:
Maximise s S ʔ ( s )
x s s S ʔ ( s ) y s
·
subject to
•∀
s , t
S : x s
y t
m ( s , t )
(3.10)
•∀ s S : y s x s
0
•∀
s
S : x s
1, y s
1
•∀
s
S : x s
0, y s
0 .
Dualising ( 3.10 ) yields:
Minimise s , t S m ( s , t ) z s , t +
ʱ s +
ʲ s
S : t S z s , t
subject to
•∀
t
ʱ s +
ʲ s
ʔ ( s )
(3.11)
S : t S z t , s
ʔ ( s )
•∀
s
ʱ s
ʲ s
•∀
s , t
S : z s , t
0, ʱ s
0, ʲ s
0 .
The duality theorem of linear programming (Theorem 2.10) tells us that the dual
problem has the same value as the primal problem. We now observe that in the
optimal vector of ( 3.11 ) it must be the case that ʱ s =
ʲ s =
0 for all s
S .In
addition, we have s S ʔ ( s )
= s S ʔ ( s )
=
1. So we can simplify ( 3.11 )to
( 3.8 ).
3.4.2
Justification by Network Flow
The lifting operation discussed in Sect. 3.3 is also related to the maximum flow
problem in optimisation theory. This was already observed by Baier et al. in [ 26 ].
We briefly recall the basic definitions of networks. More details can be found in
e.g. [ 41 ]. A network is a tuple
N =
( N , E , s , s , c ) where ( N , E ) is a finite directed
graph (i.e. N is a set of nodes and E
N is a set of edges) with two special
nodes s (the source ) and s (the sink ) and a capacity c , i.e. a function that assigns
N
×
 
Search WWH ::




Custom Search