Dantzig-Wolfe Decomposition 187
Recall that it is not necessary to know the quantities N
1
and N
2
in advance.
Step 0: Start with as basic variables s
1
= b
0
1
= 4, s
2
= b
0
2
= 3, λ
1
1
= 1, and
λ
2
1
= 1, so x
B
= (s
1
, s
2
, λ
1
1
, λ
2
1
)
T
with initial extreme points v
1
1
=
x
1
x
2
=
0
0
and v
2
1
=
x
3
x
4
=
0
0
.
Then, the restricted master problem is
minimize λ
1
1
f
1
1
+ λ
2
1
f
2
1
subject to λ
1
1
L
1
v
1
1
+λ
2
1
L
2
v
2
1
+ s = b
0
λ
1
1
= 1
λ
2
1
= 1
λ
1
1
≥ 0
λ
2
1
≥ 0
s ≥ 0,
and since the initial extreme point for each subproblem is the zero vector we
get
minimize 0
subject to s
1
= 4
s
2
= 3
λ
1
1
= 1
λ
2
1
= 1
λ
1
1
≥ 0
λ
2
1
≥ 0
s ≥ 0.
The basis matrix B = I, i.e., the 4 by 4 identity matrix.
Iteration 1
Step 1: f
B
=
c
s
1
c
s
2
f
1
1
f
2
1
=
0
0
(c
1
)
T
v
1
1
(c
2
)
T
v
2
1
=
0
0
0
0
, then solving B
T
π = f
B
gives
π =
π
1
π
2
1
π
2
2
=
π
1
1
π
1
2
π
2
1
π
2
2
=