
220 Designing Scientific Applications on GPUs
Algorithm 10: standard simplex algorithm
1 //1. Find entering variable;
2 if c
N
≤ 0 then
3 return Optimal;
4 end
5 Choose an index e ∈ N such that c
e
> 0 ;
6 //2. Find leaving variable;
7 if (A
N
)
e
≤ 0 then
8 return Unbounded
9 end
10 Let ` ∈ B be the index such that ;
11 t
:
=
b
`
a
`e
= min
(
b
i
a
ie
a
ie
> 0, i = 1, . . . , m
)
;
12 //3. Pivoting, update ;
13 B
:
= (B \ {`}) ∪ {e}, N
:
= (N \{e}) ∪{`};
14 Compute z
best
:
= z
best
+ tc
e
;
15 Exchange (I
m
)
`
and (A
N
)
e
, (c
B
)
`
and (c
N
)
e
;
16 Update A
N
, c
N
and b;
17 Go to 1.;
system Ax = b into A
B
x
B
= b − A
N
x
N
. Let us denote B = A
B
, N = A
N
.
Since B is invertible, we can write
x
B
= B
−1
b − B
−1
Nx
N
z = c