Simplex Algorithm

Rajiv Raman
February 18, 2026

We discuss the Simplex algorithm.

Developing the simplex algorithm

Consider an LP in standard form, where x ∈ Rn , A is an m × n matrix

s.t. rank (A) = m.

min c⊤ x
s.t.
Ax = b
x ≥0
We let P denote the polyhedron defined by the constraints of the
LP. We have established that if this LP has a finite optimal solution,
then this solution occurs at a vertex. In brief, the simplex algorithm
starts at a vertex and repeatedly moves to an adjacent vertex with
lower cost, until no such move is possible. At this point, we would
have found an optimal solution.
So, suppose we are given a BFS x of the LP above. At a BFS, there
are n active constraints. Since m of them come from the system of lin-
ear equations, n − m of the variables must be 0. Therefore, there are
at most m non-zero variables at x. We use B(1), . . . , B(m) to denote
the indices of these m (potentially) non-zero variables at x.
We call the set B(1), . . . , B(m) of the indices of the potentially non-
zero variables the basic indices. The set x B(1) , . . . , x B(m) are called the
basic variables. The set N of zero variables the non-basic variables at
x. The m × m matrix B of columns corresponding to the variables in
B(1), . . . , B(m) is called the basis matrix. Notation:
By the definition of a BFS, the basis matrix B is invertible. Thus, • { B(1), . . . , B(m)}: basic indices.
the values of the basic variables is given by • { x B(1) , . . . , x B(m) }: basic variables.
• B: m × m matrix of columns of A
x B = B −1 b corr. to basic indices.
• A B(1) , . . . , A B(m) : columns of B.
Note that at x, since x N = 0, the objective function value at x is • N: non-basic variables.
c⊤B B.
x
In order to decrease the objective function value, our goal is to
find a direction in which to move so that the objective function value A BFS looks like the following:
decreases. A feasible direction is a direction d along which we can  
move so that we are still in the feasible region P.
 
 xB 
 
 xB   
   
   
 = 
   0 
   
 xN   . 
 . 
 . 
0
 simplex algorithm 2

Definition 1 (Feasible Direction). Let x ∈ P. A vector d ∈ Rn is a

feasible direction at x if there exists a positive scalar θ > 0 such that

y = x + θd ∈ P

If we want to move in a feasible direction from x and still stay

within P, we need to increase some non-basic variables to a positive
quantity. We will restrict our movement, increasing only one non-
basic variable. This is without loss of generality, as moving along any
direction can be decomposed into a sequence of moves along each
coordinate direction.
Thus, we want to set d j = 1, for some j ∈ N and d j′ = 0 for all
j ∈ N and j′ ̸= j. Along this direction, we want to move by an extent
′

θ > 0.
Each choice of j ∈ N along which we can move is called a basic
direction (although we are really increasing a non-basic variable. So
may be we should call this the jth non-basic direction, but this is a bit
unweildy. So we’ll stick to the standard definition and call this the jth
basic direction.)
If we move to y = x + θd, and we want y ∈ P, then the values of
the basic variables must change. How should they change?
Since y ∈ P,

Ay = b ⇒ A(x + θd) = Bx B + θd = b + θd = b
Thus, Ad = 0
!
dB
Let d = . We have chosen d⊤
N = (0, . . . , 0, 1, 0 . . . , 0), with 1
dN
at position j and 0 elsewhere. Then,

Ad = Bd B + A j = 0
⇒ d B = − B −1 A j (1)

Thus, if we want to stay in P and move along the direction j ∈ N

to an extent θ, it follows that the basic variables in x B change by an
extent θd B . But we need to do so carefully so that x B + θd B ≥ 0.
Suppose we move to a feasible point y = x + θd. What happens to
the objective function at y.

c⊤ y = c⊤ (x + θd) = c⊤ ⊤ ⊤
B x B + θc B d B + c j
= c⊤ −1
B x B − θB A j + θc j [Plugging in the value of d B from (1)]

The change in objective function value is therefore

 simplex algorithm 3

c⊤ y − c⊤ x = c⊤ −1 ⊤
B x B − θB A j + θc j − c B x B
 
= θ c j − B −1 A j

This rate of change in the objective function value will be an im-

portant parameter, and so we will give it a name.

Definition 2. The reduced cost along the jth basic direction, j ∈ N is

given by

c j = c j − θB−1 A j (2)

Clearly, if moving along jth basic direction reduces the cost of the
objective function value, then we must have c j < 0.
Note: If x were non-degenerate, x B > 0. Thus, we can pick θ > 0 small
enough so that y ̸= x. However, if x were degenerate, there is an i ∈ B Reduced cost along the jth basic
direction: c j − θB−1 A j
such that xi = 0. In this case, for any θ > 0 we will have yi < 0, an
infeasible solution. Thus, in effect, we can not move from x. We will
restrict ourselves to the non-degenerate setting initially, and then
describe how we can deal with degeneracy.
Suppose, starting from a BFS x, we have moved to a point y ∈
P as described above. How large can we set θ? The value of θ is
determined by the sign and magnitude of (d B )i , i ∈ B, i.e., the entries
of d B . If d B ≥ 0, then, one can easily check that for any θ > 0, we
remain in P. It follows that the LP is unbounded. Suppose we have
i ∈ B such that (d B )i < 0. Then, we obtain an upper bound:
xi
θ∗ ≤ min (3)
i ∈ B:(d B )i <0 −( d B )i

Suppose we set y = x + θ ∗ d. Then, any basic variables that mini-

mize the ratio in (3) become zero, while the non-basic variable y j has
a non-zero value. If exactly one basic variable B(ℓ) at x becomes zero
at y, then we have obtained a new set of basic indices that includes
j but excludes B(ℓ). If there are more than one basic variables that
become zero in y, we can remove any of of those variables arbitrarily
from the basis. We correspondingly obtain a new basis B at y. We
claim that y is a BFS.

Exercise 1. Let x be an element of the standard form polyhedron P = {x ∈

Rn : Ax = b, x ≥ 0}. Prove that a vector d is a feasible direction at x if and
only if Ad = 0 and di ≥ 0 for every i such that xi = 0.

Exercise 2. Consider the problem of minimizing c⊤ x over the set P = {x ∈

Rn : Ax = b, Dx ≤ f, Ex ≤ g}. Let x∗ be an element of P that satisfies
Dx∗ = f and (Ex∗ )i < gi for al i. Show that the set of feasible directions at
the point x∗ is the set {d ∈ Rn : Ad = 0, Dd ≤ 0}.
 simplex algorithm 4

Exercise 3. Let P = {x ∈ R3 : x1 + x2 + x3 ≤ 1, x ≥ 0} and consider the

vector x = (0, 0, 1). Find the set of feasible directions at x.

Simplex Algorithm

The algorithm below is described in the non-degenerate setting, and

we will deal with degeneracy in the next section. We want to first
show that B is a basis, and that y is a basic feasible solution.
Algorithm 1: Simplex Iteration
1: Let x be a BFS, with basis B, and non-basic variables N.
2: Let p⊤ = c⊤ −1
BB .
3: for j ∈ N do
4: Compute c j = c j − p⊤ A j .
5: end for
6: if c j ≥ 0 for each j ∈ N then
7: Return x is an opt. soln.
8: end if
9: Select j ∈ N such that c j < 0, and set d B = −B−1 A j .
10: if (d B )i ≥ 0 for all i ∈ B then
11: Return “The LP is unbounded”
12: end if
x
13: Let i = arg mini′ ∈ B:(dB ) ′ <0 −(di′ ) ′ .
i B i
14: Set θ = −(xdi ) .
B i
15: Set y = x + θd
16: B = (B \ {i }) ∪ { j}.
17: Set x = y, B = B.
18: Goto Step 2.

Theorem 1. If we start with a BFS x with basis B, and in one step we move
to y = x + θ ∗ d as in the Simplex algorithm above. Then, we claim that

1. B, as computed in the algorithm above is a basis,

2. y is a BFS.

Proof. We will prove the first part by contradiction. So, suppose B is

not a basis. Then, the columns Ak , k ∈ B must be linearly dependent.
That is, there exist λi , i = 1, . . . , m, not identically 0 such that

m
∑ λk Ak = 0
k =1

If we pre-multiply with B−1 , we obtain:

 simplex algorithm 5

m
∑ λ k B −1 A k = 0
k =1
| |
 

Now, B = B \ {i } ∪ { j}. So, B and B differ in only one column. B =  A B (1) . . . A B ( m ) 

| |
Thus, B−1 Ak = ek for k ∈ B, k ̸= j, where ek = (0, . . . , 0, 1, 0, . . . , 0)⊤ .
| | | |
 
In particular, the ℓth position of ek is 0. On the other hand, B−1 A j =
B =  A B(1) . . . A B(ℓ−1) A j . . . A B(m) 
−d B , and we know that (d B )ℓ ̸= 0. Therefore, A j is not a linear | | | |
combination of the other columns and hence B has rank m.
| | | |
 
Now, the second part follows directly. yk = 0 for all k ̸∈ B, and by B−1 B =  e1 . . . e(ℓ−1 B−1 A j . . . em 
our choice of θ, yi ≥ 0 for all i ∈ B. Hence, y is a BFS. | | | |

The simplex algorithm therefore, traverses from one basic feasible

solution to another, each time improving the cost. We now prove that
the simplex algorithm returns the correct solution.

Theorem 2. For an LP problem, suppose we run the simplex algorithm

with an initial BFS. If at a BFS x, the vector c of reduced costs for the non-
basic variables is such that c ≥ 0, then x is an optimal solution. On the
other hand, if x is a non-degenerate LP, then at an optimal solution, c ≥ 0.

Proof. Let x be a BFS such that c ≥ 0. Consider an arbitrary point

y ∈ P and let d = y − x. Since Ax = b and Ay = b, it follows that
Ad = 0. Indeed,

Ad = A(y − x) = b − b = 0 (4)

We want to show that c⊤ y − c⊤ x ≥ 0, and this will imply that x

is an optimal solution. Let B be the basis matrix corresponding to x,
and let B(1), . . . , B(m) be the basic variables at x. Let N denote the
set of non-basic variables at x.
We first rewrite Eqn. (4) in terms of the basic and non-basic vari-
ables at x. Thus,

Ad = Bd B + ∑ Ai di = 0
i∈ N

Since B is invertible, it follows that

dB = − ∑ B −1 A i d i (5)
i∈ N
 simplex algorithm 6

Thus,

c⊤ (y − x) = c⊤ d
= c⊤
B (d B ) + ∑ ci di
i∈ N
= c⊤
B (− ∑B −1
Ai di ) + ∑ ci di [from Eqn.(5)]
i∈ N i∈ N
 
= ∑ ci − c ⊤ −1
B B Ai di
i∈ N
= ∑ ci di
i∈ N
≥0

The last inequality holds because for any i ∈ N, yi ≥ 0 but xi = 0.

Therefore, di ≥ 0. By assumption each c ≥ 0. Hence, for each i ∈ N,
ci di ≥ 0.
Suppose x is a non-degenerate BFS. If there is a basic direction
j ∈ N s.t. c j < 0, then the simplex algorithm can move to a new BFS
with smaller cost contradicting the assumption that x is an optimal
BFS.

Theorem 3. For a non-degenerate LP problem, given an initial BFS for a

feasible LP, the simplex algorithm terminates in a finite number of steps with
an optimal solution, if an optimal solution exists. Otherwise, it returns −∞.

Proof. The number of basic solutions is finite, and hence, so are the
number of BFS. In each iteration, the algorithm moves to a new BFS
of lower cost. Therefore, after a finite number of steps the algorithm
halts with an optimal solution. The algorithm halts at a BFS x if
c ≥ 0, or if d B ≥ 0. In the first case, by Theorem 2, we obtain an
optimal solution. In the second case, the algorithm returns that the
optimal solution is unbounded.

Note:

• Note that the algorithm is not well specified. In particular, we do

not specify how to pick a basic direction of reduced cost if we have
a choice, and we do not specify how to choose an exiting variable
if there is a tie. These will turn out to be crucial in dealing with
degeneracy. Before we do that, we discuss the running time of the
simplex algorithm.

• The algorithm asks you to start with an initial BFS. How do we

find a BFS? This problem is at least as hard as solving an LP!

Exercise 4. Let x be a basic feasible solution associated with some basis

matrix B. Prove the following:
 simplex algorithm 7

1. If the reduced cost of every nonbasic variable is positive, then x is the

unique optimal solution.

2. If x the unique optimal solution and is nondegenerate, then the reduced

cost of every nonbasic variable is positive.
Exercise 5. Consider a feasible solution x to a standard form problem, and
let Z = {i : xi = 0} Show that x is an optimal solution if and only if the
linear programming problem minimize {c⊤ d : Ad = 0, di > 0, i ∈ Z } has
an optimal cost of zero. (In this sense, deciding optimality is equivalent to
solving a new linear programming problem.)
Exercise 6. Consider a feasible solution x to a standard form problem, and
let Z = {i : xi = 0}. Show that x is an optimal solution if and only if the
linear programming problem

min c⊤ x
s.t.
Ad = 0
di ≥ 0, i ∈ Z
has an optimal cost of zero. In this sense, deciding optimality is equiva-
lent to solving a new linear programming problem.
Exercise 7. This exercise deals with the problem of deciding whether a given
degenerate basic feasible solution is optimal and shows that this is essentially
as hard as solving a general linear programming problem. Consider the
linear programming problem of minimizing c⊤ x over all x ∈ P, where
P = {x ∈ Rn : Ax ≤ b} is a given bounded and nonempty polyhedron.
Let Q = {( x, t) ∈ Rn+1 : Ax ≤ tb, t ∈ [0, 1]}.
1. Give an example of P and Q, with n = 2, for which the zero vector (in
Rn+1 ) is a degenerate basic feasible solution in Q; show the example in a
figure.

2. Show that the zero vector in Rn+1 minimizes (c, 0)⊤ y over all y ∈ Q if
and only if the optimal cost in the original linear programming problem
is greater than or equal to zero.

Implementation

A basic implementation
Let us now analyze the complexity of an iteration of the simplex
algorithm. Suppose we have an initial BFS. At each iteration, we
compute, for each of the n − m basic directions, the reduced cost.
Each computation of the reduced cost invovles computing

c j = c j − c⊤ −1
B B Aj
 simplex algorithm 8

This can be done by computing p = c⊤ −1

B B , and for each column
A j , compute p⊤ A j for each of the n − m basic directions j ∈ N. This
takes O(m3 ) time to compute p. Each p⊤ A j computation takes O(m)
time. Thus, the total time is O(m3 + mn). It is easy to see that this is
the computation that dominates the time for a step. Thus, each step
takes O(m3 + mn).
How many steps does the algorithm take to converge to an opti-
mal solution? Unfortunately, we will see that there are examples and
pivoting rules for which the algorithm could take super-polynomial
time to converge. However, we can speed up this naïve implementa-
tion. Next, we see how we can speed up each iteration of the simplex
algorithm.

Revised Simplex
The biggest time-suck in each iteration is the computation of B−1 .
At the end of an iteration, we obtain a basis B and we re-compute
−1
B from scratch. However, note that the columns of B and B dif-
fer in only one column. So it seems likely that we could use B−1 to
compute B. Let us see how we can use this.
 

B −1 A B =  e 1 ... e i −1 B −1 A j e i +1 ... em 
 

 
Consider the vector (B)−1 A j . There is a sequence of row-
operations that converts this vector into the vector ei . This sequence
of row-operations can be represented by a matrix, say Q. Then, it
follows that:

 
Q B −1 A j = e i

Thus,
−1
B = QB−1 (6)
−1
In other words, we can compute B in time required to pre-
multiply with Q. This is a sequence of row operations, and hence
takes only O(m2 ) time to compute. Therefore, we can reduce the run-
ning time of each iteration of the simplex algorithm to O(m2 + mn).

Finding an initial BFS

The iterations of a simplex algorithm assume that there is an intial
BFS to start with. If the LP is of the LP is of the form min{c⊤ x : Ax ≤
b, x ≥ 0}, then we add slack variables to convert the LP into standard
 simplex algorithm 9

form. Hence, in standard form, the LP becomes min{c⊤ x : Ax + Is =

b, x, s ≥ 0}. Suppose b ≥ 0. Then, setting s = b yields a BFS for the
standard form problem.
What if the input is a standard form problem? We again introduce
additional artificial variables. Given an LP in standard form: min{c⊤ x :
Ax = b, x ≥ 0}, we first flip signs to ensure that b ≥ 0. We then add a
set of artificial variables to obtain an auxiliary LP
m
min ∑ si
i =1
s.t.
Ax + Is =b
x, s ≥0
Now, setting s = b is a BFS for this auxiliary LP. We make the
following observations:

1. If the original LP is feasible, i.e., there exists x ≥ 0 s.t. Ax = b,

then the minimum value of the auxiliary LP is 0.

2. If the optimal solution to the auxiliary LP is positive, then the

original LP is infeasible.

Since we have an initial BFS for the auxiliary LP, we can solve
it optimally using the Simplex algorithm. Let ( x, s) be the optimal
solution returned and let B be the basis matrix corresponding to this
solution. If all the columns of B come from A, then it follows that B
is also a basis for the original LP and x is a BFS for the original LP.
On the other hand, if B contains some columns corresponding to s,
then we proceed as follows:
Suppose there are k < m columns from A, namely A1 , . . . , Ak
in B. By assumption A has rank m. Therefore, we can add an addi-
tional m − k columns from A to obtain a linearly independent set of
columns. For the added columns, set the corresponding variables for
the original LP to 0. We claim that this is a BFS for the original LP.
Observe that this is a degenerate BFS. Therefore, we obtain an initial
BFS for the original LP and we can now solve the original LP via the
Simplex algorithm. This method of removing the artifical variables
from the basis is called driving out the artificial variables.
Running the Simplex algorithm on the auxiliary LP to obtain an
initial BFS for the original LP is called the 2-phase simplex method.

Big-M method A second method that does not use two distinct runs
of the simplex algorithm is the so called big-M method. Given an LP
min{c⊤ x : Ax = b, x ≥ 0} in standard form. As before, we augment
the LP with auxiliary variables. But, this time, we add the auxiliary
 simplex algorithm 10

variables to the objective function with a large positive value, namely

M. We obtain the LP:
m
min c⊤ x + M ∑ si
i =1
s.t.
Ax + Is =b
x, s ≥0
We don’t have to explicitly try to find a suitable value of M. We
can leave it as is, computing symbolically assuming that it takes a
value larger than any other number. We next desecribe the tableau
method - a technique to solve LPs by hand.

Full tableau
We now describe the simplex algorithm in a form that is described
in most textbooks. The simplex algorithm was invented in the 1940s.
Since there were hardly any computers then, the computation had
to be done by hand. The tableau therefore, is a presentation of the
algorithm that enables one to find solutions to small LPs by hand.
Nevertheless, the tableau also makes it easy to track the change in
the variables as the algorithm progresses and also helps us in the
analysis of the algorithm when we deal with degeneracies.
The tableau stores the values as described in the table. This is a
full tableau since we also store the columns B−1 Ai for the columns
corresponding to the basic variables as well as the ones correspond-
ing to the non-basic variables. The first column, also called the zeroth
column stores the values of the basic variables. The first row is called
the zeroth row and stores the objective function value at the current
BFS as well as the reduced costs. Note that we store the reduced costs
for all basic directions, i.e., corresponding to the non-basic variables,
as well as the ones corresponding to the basic variables (which is 0).
The simplex algorithm chooses a column with negative reduced-
cost, and picks a row that restricts the increase the most. The oper-
ations as described in the revised simplex method above yield the
tableau with the new basis B.

c ⊤ B −1 b c⊤ − c⊤ −1
BB A
B −1 b −
B A1

Observe that the reduced costs of the basic variables is 0. In an

iteration of the simplex algorithm, we first look for a non-basic vari-
able with negative reduced cost. The column in the tableau corre-
sponding to the non-basic variable selected as the entering variable
 simplex algorithm 11

is called the pivot column. Once the pivot column is chosen, our goal
is to find θ ∗ . Observe that the values of the basic variables is in the
0th column. Hence, we only need to find the ratios of the 0th column
with the positive entries in the pivot column and pick the minimum
of these ratios. Among the rows achieving the minimum, we choose
one row. This the row corresponding to an exiting variable. This row
is called the pivot row. The entry in the tableau lying in both the pivot
row and pivot column is called the pivot element.
We now need to update the tableau corresponding to the new
basis - the entering variable is in the new basis B and the exiting
variable is removed from the basis.
How do we update the tableau? First, consider the columns
1, . . . , n and the rows 1, . . . , m (that is, we ignore the 0th row and 0th
−1
column for now). We want to compute the columns B A j . From
the description of the revised simplex algorithm, we know that
−1
B = QB−1 . That is, Q is the sequence of row operations that con-
−1
vert BB to the identity matrix. That is, the sequence of elementary
row operations that transform the pivot column into the identity. It
follows that in order to do this, we multiply the pivot row by −ui /uℓ
and add it to the ith row, where we use u = B−1 A j , where j is the
pivot column. We then scale the pivot row by uℓ so that the pivot
column becomes the unit vector eℓ .
How are the entries in the 0th column changed? The entries were
−1 −1
−
B 1 b under basis B and are now B b. Since B = QB−1 , it follows
that we apply the same operations as for the other columns to obtain
the new 0th column.
Finally, we need to update the 0th row. It turns out that this update
is also just an elementary row operation as the other rows of the
tableau.
In the following, we present some linear programming problems
solved via the simplex algorithm using the tableau.

Example.
Consider the following minimization problem:

min z = −3x1 − 2x2

Subject to:

x1 + x2 ≤ 4
2x1 + x2 ≤ 6
x1 , x2 ≥ 0

Converting Standard Form

 simplex algorithm 12

We introduce slack variables x3 and x4 to convert the inequalities into

equalities.

x2
min z = −3x1 − 2x2 + 0x3 + 0x4
s.t. x1 + x2 + x3 = 4
2x1 + x2 + x4 = 6 (0, 4)

x1 , x2 , x3 , x4 ≥ 0
Optimal
Initial Tableau (Iteration 0) (z = −(2,
10)2)
The initial basic variables are the slack variables { x3 , x4 }.

• We choose the entering variable based on the most negative re- Iter 2
duced cost (x1 with −3).
x1
• We choose the leaving variable based on the minimum ratio test: (0, 0) Start Iter 1 (3, 0)
x1 + x2 = 4
min{4/1, 6/2}. (z = 0)
2x1 + x2 = 6

Basic Value x1 x2 x3 x4
z 0 − 3 −2 0 0
x3 4 1 1 1 0
x4 6 2 1 0 1
Pivot Element: 2 (Row x4 , Column x1 ).
Leaving Variable: x4 .
3. Iteration 1
We perform row operations to convert the pivot column into a unit
vector.
1
• New x1 Row: 2 R2

• New x3 Row: R1 − 1(New x1 )

• New z Row: R0 − (−3)(New x1 )

Basic Value x1 x2 x3 x4
z −9 0 −0.5 0 1.5
x3 1 0 0.5 1 −0.5
x1 3 1 0.5 0 0.5
Pivot Selection:

• Entering Variable: x2 (Reduced cost −0.5).

• Leaving Variable: Ratio test min{1/0.5 = 2, 3/0.5 = 6}. The

minimum is Row x3 .
 simplex algorithm 13

Pivot Element: 0.5 (Row x3 , Column x2 ).

4. Iteration 2 (Final Tableau)
We perform row operations to clear the x2 column.
1
• New x2 Row: 0.5 R1

• New x1 Row: R2 − 0.5(New x2 )

• New z Row: R0 − (−0.5)(New x2 )

Basic Value x1 x2 x3 x4
z −10 0 0 1 1
x2 2 0 1 2 −1
x1 2 1 0 −1 1

5. Conclusion
All reduced costs in the top row are non-negative (0, 0, 1, 1). There-
fore, we have reached the optimal solution.
Optimal Solution:

x1 = 2, x2 = 2, zmin = −10

Example 2
We consider the following minimization problem where the feasible
region allows for infinite improvement of the objective function.

min z = − x1 − 4x2
Subject to:

−2x1 + x2 ≤ 2
x1 − x2 ≤ 1
x1 , x2 ≥ 0
x2
Standard Form:
−2x1 + x2 = 2
min z = − x1 − 4x2 + 0x3 + 0x4
s.t. − 2x1 + x2 + x3 = 2 x1 − x2 =
Unbounded
x1 − x2 + x4 = 1
x1 , x2 , x3 , x4 ≥ 0

(0, 2)
Iteration 0 ( Tableau)
The initial basis is { x3 , x4 }.
Iter 1
• Entering Variable: x2 (Reduced cost −4 is the most negative). Start
x1
(0, 0)
 simplex algorithm 14

• Leaving Variable:

– Ratio for x3 : 2/1 = 2.

– Ratio for x4 : 1/(−1) (Ignore negative denominator).

Variable x3 leaves.

Basic Value x1 x2 x3 x4
z 0 −1 − 4 0 0
x3 2 −2 1 1 0
x4 1 1 −1 0 1

Iteration 1 (Unboundedness Detected)

We pivot on row 1, column 2.

• New Row x2 is identical to old Row x3 .

• New Row x4 = Old Row x4 + New Row x2 .

• New Row z = Old Row z + 4(New Row x2 ).

Basic Value x1 x2 x3 x4
z −8 −9 0 4 0
x2 2 −2 1 1 0
x4 3 −1 0 1 1
Stopping Condition:

• We attempt to select an entering variable. x1 has a reduced cost of

−9, so it is a candidate to enter.

• We " # the column for x1 to find a leaving variable. The entries

check
−2
are .
−1

• Since all entries in the constraint column are ≤ 0, we cannot per-

form the minimum ratio test. This implies x1 can be increased
indefinitely without violating any constraints.

Conclusion: The Linear Program is unbounded.

A cycling example
This example shows that if we are not careful about the entering and
exiting variables, then the Simplex algorithm may not terminate. We
use the standard pivot rule (most negative reduced cost) and break
ties for leaving variables by choosing the smallest index (topmost
row).
 simplex algorithm 15

Minimize:
z = −10x1 + 57x2 + 9x3 + 24x4

Subject to:

0.5x1 − 5.5x2 − 2.5x3 + 9x4 ≤ 0

0.5x1 − 1.5x2 − 0.5x3 + x4 ≤ 0
x1 , x2 , x3 , x4 ≥ 0

Standard Form

We introduce slack variables x5 and x6 to convert the inequalities into

equalities.
Minimize:
z = −10x1 + 57x2 + 9x3 + 24x4
Subject to:

0.5x1 − 5.5x2 − 2.5x3 + 9x4 + x5 = 0

0.5x1 − 1.5x2 − 0.5x3 + x4 + x6 = 0
x1 , x2 , x3 , x4 , x5 , x6 ≥ 0

Iteration 0

Basis: { x5 , x6 }. Entering: x1 (-10). Leaving: x5 (Ratio 0, Top Row).

Basic Val x1 x2 x3 x4 x5 x6
z 0 −10 57 9 24 0 0
x5 0 0.5 −5.5 −2.5 9 1 0
x6 0 0.5 −1.5 −0.5 1 0 1

Iteration 1

Basis: { x1 , x6 }. Entering: x2 (-53). Leaving: x6 (Ratio 0).

Basic Val x1 x2 x3 x4 x5 x6
z 0 0 −53 −41 204 20 0
x1 0 1 −11 −5 18 2 0
x6 0 0 4 2 −8 −1 1
 simplex algorithm 16

Iteration 2

Basis: { x1 , x2 }. Entering: x3 (-14.5). Leaving: x1 (Tie for ratio 0, x1 is

row 1).

Basic Val x1 x2 x3 x4 x5 x6
z 0 0 0 −14.5 98 6.75 13.25
x1 0 1 0 0.5 −4 −0.75 2.75
x2 0 0 1 0.5 −2 −0.25 0.25

Iteration 3

Basis: { x3 , x2 }. Entering: x4 (-18). Leaving: x2 (Ratio 0).

Basic Val x1 x2 x3 x4 x5 x6
z 0 29 0 0 −18 −15 93
x3 0 2 0 1 −8 −1.5 5.5
x2 0 −1 1 0 2 0.5 −2.5

Iteration 4

Basis: { x3 , x4 }. Entering: x5 (-10.5). Leaving: x3 (Tie for ratio 0, x3 is

row 1).

Basic Val x1 x2 x3 x4 x5 x6
z 0 20 9 0 0 −10.5 70.5
x3 0 −2 4 1 0 0.5 −4.5
x4 0 −0.5 0.5 0 1 0.25 −1.25

Iteration 5

Basis: { x5 , x4 }. Entering: x6 (-24). Leaving: x4 (Ratio 0).

Basic Val x1 x2 x3 x4 x5 x6
z 0 −22 93 21 0 0 −24
x5 0 −4 8 2 0 1 −9
x4 0 0.5 −1.5 −0.5 0 0 1

Iteration 6 (Cycle Complete)

Basis: { x5 , x6 }. The tableau is identical to Iteration 0.

Basic Val x1 x2 x3 x4 x5 x6
z 0 −10 57 9 24 0 0
x5 0 0.5 −5.5 −2.5 9 1 0
x6 0 0.5 −1.5 −0.5 1 0 1
 simplex algorithm 17

Exercise 8. Solve the following LP both graphically and via the tableau
method.

1. Maximize z = 3x1 + 2x2 subject to:

2x1 + x2 ≤ 6
x1 + 2x2 ≤ 6
x1 , x2 ≥ 0

2. Maximize z = 2x1 + 3x2 subject to:

x1 − x2 ≤ 2
x1 ≤ 3
x1 , x2 ≥ 0

3. Maximize z = 4x1 + 3x2 subject to:

x1 ≤ 4
2x2 ≤ 12
3x1 + 2x2 ≤ 18
x1 , x2 ≥ 0

4. Maximize z = 2x1 + x2 subject to:

x1 − x2 ≤ 1
− x1 + x2 ≤ 1
x1 , x2 ≥ 0

Exercise 9. Consider the problem

min 2x1 − x2
s.t.
x1 − x2 ≤ 2
x1 + x2 ≤ 6
x1 , x2 ≥ 0

(i) Convert the problem into standard form and construct a basic feasible
solution at which ( x1 , x2 ) = (0, 0).

(ii) Carry out the ful tableau implementation of the simplex method, start-
ing with the basic feasible solution of part (i ).

(iii) Draw a graphical representation of the problem ni terms of the original

variables x1 , x2 , and indicate the path taken by the simplex algorithm.
 simplex algorithm 18

Exercise 10. Show how Phase 1 of the simplex method can be used to solve
n simultaneous linear equations in n unknowns. Show how the following
cases can be detected:

1. Inconsistency of the system.

2. Redundancy of the equations.

3. Unique solution.

Exercise 11. Consider the system of linear inequalities Ax = b, x ≥ 0 with

b ≥ 0. This system can be transformed to standard form by the introduction
of m surplus variables so that it becomes Ax − y = b, x ≥ 0, y ≥ 0. Let
bk = maxi bi and consider the new system in standard form obtained by
adding the kth row to the negative of every other row. Show that the new
system requires the addition of only a single artificial variable to obtain
an initial basic feasible solution. Use this technique to find a basic feasible
solution to the system.

x1 + 2x2 + x3 ≥4
2x1 + x2 + x3 ≥5
2x1 + 3x2 + 2x3 ≥6
x1 , x2 , x3 ≥ 0

Degeneracy

We prove that Simplex with a lexicographic pivoting rule converges. We

first define a lexicographic order on vectors.

Definition 3. 1. A vector u ∈ Rn is lex-positive if the first non-zero entry

of u is positive.

2. Let u, v ∈ Rn . Then, u < L v if and only if the first non-zero entry in

w = v − u is positive, i.e., w is lex-positive.

3. Given a set of vectors U = {u1 , . . . , un }, u ∈ U is lex-min, if u < L v for

all v ∈ U.

For example, consider the vectors v = (2, 3, −3, 4) and u =

(2, 2, 5, 1). Then, v − u = (0, 1, −8, 3). Since the first non-zero en-
try in this vector is positive, we have that u < L v. We can now define
the lex-pivot rule.
Note that we assume that the lex-pivot rule chooses the entering
variable arbitrarily, but chooses the exiting variable carefully. We
show that the lex-pivot rule does not cycle.

Theorem 4. Simplex with the lex-pivot rule converges

 simplex algorithm 19

Algorithm 2: Lex-pivot rule

1: Choose entering variable x j arbitrarily so long as c j < 0.
2: Among the exiting variables, choose the one whose row in the
simplex tableau is lex-min when each row i is divided by the
corresponding entry in the jth column, i.e., by ( A− 1
B A j )i .

Proof. In order to prove that simplex with the lex-pivot rule con-
verges, it is sufficient to prove that the bases do not repeat. Since
the number of different bases is finite, the algorithm must terminate
in finite time. In order to show that the bases do not cycle, we will
show that with each pivoting operation, the o th row, i.e., the row with
reduced costs is monotonically lex-increasing. i.e., If c was the row
of reduced costs before the pivot, and c′ is the row of reduced costs
after the pivot, then c < L c′ .
We show this as follows. First, if at the start of the pivot operation,
each row is lex-positive, then this property holds after the pivot step.
Suppose at a pivot step, the entering variable is x j and the exiting
variable chosen by the lex-pivot rule is xi . To obtain the new tableau,
we do the following. For each row k ̸= i, we apply the following.

( B −1 A j ) k
Multiply row i by ( B −1 A j ) i
Subtract from row k

Note that (B−1 A j )i > 0. If (B−1 A j )k < 0, we obtain that this

row remains lex-positive since we multiply row i by a positive quan-
tity and add it to row k. On the other hand, if (−B−1 A j )k > 0 ,
then we subtract a positive The multiple of the ith row from the kth
row. In this case, it is easy to check that we remain lex-positive since
rowi /(B−1 A j )i < L rowk /(B−1 A j )k .
For the 0th row, we have that c j < 0. Since we add a positive
multiple of row i, and the reduced cost of row j becomes 0, it follows
that that 0th row lexicographically monotonically increases.

Exercise 12. 1. If a basic feasible solution is degenerate, it is then theo-

retically possible that a sequence of degenerate basic feasible solutions
will be generated that endlessly cycles without making progress. It is the
purpose of this exercise and the next two to develop a technique that can
be applied to the simplex method to avoid this cycling. Corresponding
to the linear system Ax = b, where A = [A1 , . . . , An ], where Ai ’s
are the columns of A define the perturbed system Ax = b(ϵ), where
b(ϵ) = b + ϵA1 + ϵ2 A2 + . . . + ϵn An .
Show that if there is a basic feasible solution (possibly degenerate) to the
unperturbed system with basis B = [A1 , . . . , Am ], then corresponding
 simplex algorithm 20

to the same basis, there is a non-degenerate basic feasible solution to the

perturbed system for some range of ϵ > 0.

2. Show that corresponding to any basic feasible solution to the perturbed

system of the previous exercise, which is nondegenerate for some range of
ϵ > 0 and to a vector Ak not in the basis, there is a unique vector Ai in
the basis which when replaced by Ak leads to a basic feasible solution; and
that solution is nondegenerate for a range of ϵ > 0.

Deterministic Pivot Rules and Exponential Lower Bounds

While the Simplex algorithm performs remarkably well in practice,

its worst-case complexity depends heavily on the pivot rule used
to select the entering variable. For most deterministic pivot rules,
families of Linear Programming (LP) instances have been constructed
where the algorithm visits an exponential number of vertices.

Standard Rules (Dantzig, Bland, Steepest-Edge)

• Dantzig’s Rule: The original rule selects the variable with the
most negative reduced cost. Klee and Minty 1 famously con- 1
V. Klee and G. J. Minty. How good is
structed the "Klee-Minty cube," where this rule visits all 2d ver- the simplex algorithm? In O. Shisha,
editor, Inequalities III, pages 159–175.
tices. Academic Press, New York, 1972

• Bland’s Rule: To avoid cycling, this rule selects variables with the
smallest indices. Avis and Chvátal 2 proved this requires exponen- 2
D. Avis and V. Chvátal. Notes on
tial time (2d/2 steps) on specific examples. bland’s pivoting rule. Mathematical
Programming Study, 8:24–34, 1978
• Steepest-Edge: This rule, efficient in practice, moves in the di-
rection closest to the gradient. Goldfarb and Sit 3 showed it also 3
D. Goldfarb and W. Y. Sit. Worst case
suffers from exponential worst-case complexity. behavior of the steepest edge simplex
method. Discrete Applied Mathematics,
1(4):277–285, 1979
• Lexicographic Rule: Designed to resolve degeneracy and prevent
cycling, this rule maintains a lexicographically positive order of
tableau rows. Despite this guarantee, it does not escape exponen-
tial behavior on Klee-Minty style cubes.

Randomized Sub-Exponential Algorithms

Given the exponential lower bounds for deterministic rules, research

shifted toward randomized pivot rules. While a polynomial-time
pivot rule remains elusive, breakthrough algorithms in the 1990s
established sub-exponential bounds.
 simplex algorithm 21

Kalai’s Algorithm
In 1992, Gil Kalai proposed a randomized algorithm that selects
entering variables based on a random permutation of the facets.
√
• Complexity: Kalai proved an expected time bound of eO( d log n) ,
where d is the dimension and n is the number of constraints 4 . 4
G. Kalai. A randomized simplex
algorithm with subexponential number
of pivots. In Proceedings of the 24th
Matousek, Sharir, and Welzl (MSW) Annual ACM Symposium on Theory of
Computing (STOC), pages 475–482, 1992
Independently, Matousek, Sharir, and Welzl developed a randomized
algorithm with nearly the same bounds as Kalai’s algorithm
These results represented the first theoretical evidence that the
Simplex algorithm could beat purely exponential bounds, though the
question of a polynomial-time pivot rule (deterministic or random-
ized) remains one of the greatest open problems in optimization.

The Hirsh Conjecture

In 1957, Warren M. Hirsch formulated a conjecture regarding the

combinatorial structure of polytopes, which became one of the most
famous open problems in discrete geometry and optimization.
The Hirsch Conjecture: Let P be a d-dimensional polytope with
n facets. Let δ( P) denote the diameter of the graph (1-skeleton) of P.
Then:
δ( P) ≤ n − d
In other words, the conjecture says that one can travel from any ver-
tex to any other vertex of the polytope traversing at most n − d edges.

Implications for the Simplex Algorithm

The relevance of the Hirsch conjecture to Linear Programming is

fundamental. The Simplex algorithm operates by moving along the
edges of the polytope from one vertex to an adjacent vertex.

• Lower Bound on Complexity: The diameter of the polytope graph

represents a lower bound on the number of iterations the Simplex
algorithm requires in the worst case.

• Implication: If the Hirsch conjecture were true (or if the diameter

were polynomially bounded), it would imply that the underlying
graph structure allows for a short path to the optimal solution.

• Polynomial Time: While a small diameter is a necessary condi-

tion for a strongly polynomial-time Simplex algorithm, it is not
sufficient. Even if a short path exists, there is no guarantee that a
specific pivot rule (like Dantzig’s or Steepest-Edge) will find it.
 simplex algorithm 22

Current Status: The Santos Counterexample

For over five decades, the conjecture held for all known classes of
polytopes. However, in a landmark result in 2010, **Francisco San-
tos** disproved the Hirsch Conjecture.

• The Counterexample: Santos constructed a 43-dimensional poly-

tope with 86 facets where the diameter exceeds the Hirsch bound
(n − d). Specifically, the diameter is at least 44, whereas the bound
predicts 43 5 . 5
F. Santos. A counterexample to the
hirsch conjecture. Annals of Mathematics,
• Consequence: The strict inequality δ( P) ≤ n − d is false in general. 176(1):383–412, 2012

The Polynomial Hirsch Conjecture

Despite Santos’ disproof, the "spirit" of the conjecture remains alive

in a relaxed form known as the **Polynomial Hirsch Conjecture**.
Open Problem: Is the diameter of a polytope bounded by a poly-
nomial function of n and d? Specifically, is δ( P) ≤ poly(n, d)?

• Santos’ counterexample violates the linear bound n − d, but it does

not exhibit exponential growth.

• The best known upper bound for the diameter of general poly-
topes is quasi-polynomial, provided by Kalai and Kleitman 6 : 6
G. Kalai and D. J. Kleitman. A quasi-
polynomial bound for the diameter
δ( P) ≤ nlog2 d+1 of graphs of polyhedra. Bulletin of the
American Mathematical Society, 26(2):315–
316, 1992
• If the Polynomial Hirsch Conjecture is true, it leaves open the
possibility that a version of the Simplex algorithm could run in
polynomial time. If the diameter is exponential, then the Simplex
algorithm must be exponential in the worst case regardless of the
pivot rule.

Exercise 13. A meat packing plant produces 480 hams, 400 pork bellies,
and 230 picnic hams every day; each of these products can be sold either
fresh or smoked. The total number of hams, bellies, and picnics that can be
smoked during a normal working day is 420; in addition, up to 250 products
can be smoked on overtime at a higher cost. The net profits are as follows:

Fresh Smoked on regular time Smoked on overtime

Hams $8 $14 $11
Bellies $4 $12 $7
Picnics $4 $13 $9
For example, the following schedule yields a total net profit of $9,965:
The objective is to find the schedule that maximizes the total net profit.
Formulate as an LP problem in the standard form.
 simplex algorithm 23

Fresh Smoked Smoked (overtime)

Hams 165 280 35
Bellies 295 70 35
Picnics 55 70 105

Exercise 14. An oil refinery produces four types of raw gasoline: alkylate,
catalytic-cracked, straight-run, and isopentane. Two important characteris-
tics of each gasoline are its performance number PN (indicating antiknock
properties) and its vapor pressure RVP (indicating volatility). These two
characteristics, together with the production levels in barrels per day, are as
follows:

PN RVP Barrels produced

Alkylate 107 5 3,814
Catalytic-cracked 93 8 2,666
Straight-run 87 4 4,016
Isopentane 108 21 1,300
These gasolines can be sold either raw at $4.83 per barrel, or blended into
aviation gasolines (Avgas A and/or Avgas B). Quality standards impose
certain requirements on the aviation gasolines; these requirements, together
with the selling prices, are as follows:

PN RVP Price per barrel

Avgas A at least 100 at most 7 $6.45
Avgas B at least 91 at most 7 $5.91
The PN and RVP of each mixture are simply weighted averages of the
PNs and RVPs of its constituents. For example, the refinery could adopt the
following strategy:

• Blend 2,666 barrels of alkylate and 2,666 barrels of catalytic into 5,332
barrels of Avgas A with [cite: 29]

(2, 666 × 107) + (2, 666 × 93)

PN = = 100
5, 332
(2, 666 × 5) + (2, 666 × 8)
RVP = = 6.5
5, 332
• Blend 1,148 barrels of alkylate, 4,016 barrels of straight-run, and 1,024
barrels of isopentane into 6,188 barrels of Avgas B with

(1, 148 × 107) + (4, 016 × 87) + (1, 024 × 108) ∼

PN = = 94.2
6, 188
(1, 148 × 5) + (4, 016 × 4) + (1, 024 × 21) ∼
RVP = =7
6, 188
• Sell 276 barrels of isopentane raw.
 simplex algorithm 24

This sample plan yields a total profit of

(5, 332 × 6.45) + (6, 188 × 5.91) + (276 × 4.83) = 572, 296.

The refinery aims for the plan that yields the largest possible profit. For-
mulate as an LP problem in the standard form.

Exercise 15. An electronics company has a contract to deliver 20,000 radios

within the next four weeks. The client is willing to pay $20 for each radio
delivered by the end of the first week, $18 for those delivered by the end of
the second week, $16 by the end of the third week, and $14 by the end of the
fourth week. Since each worker can assemble only 50 radios per week, the
company cannot meet the order with its present labor force of 40; hence it
must hire and train temporary help. Any of the experienced workers can
be taken off the assembly line to instruct a class of three trainees; after one
week of instruction, each of the trainees can either proceed to the assembly
line or instruct additional new classes. At present, the company has no
other contracts hence some workers may become idle once the delivery is
completed. All of them, whether permanent or temporary, must be kept on
the payroll till the end of the fourth week. The weekly wages of a worker,
whether assembling, instructing, or being idle, are $200; the weekly wages of
a trainee are $100. The production costs, excluding the worker’s wages, are
$5 per radio.
For example, the company could adopt the following program.

• First week: 10 assemblers, 30 instructors, 90 trainees. Workers’ wages:

$8,000; Trainees’ wages: $9,000. Profit from 500 radios: $7,500; Net loss:
$9,500.

• Second week: 120 assemblers, 10 instructors, 30 trainees. Workers’

wages: $26,000; Trainees’ wages: $3,000. Profit from 6,000 radios:
$78,000; Net profit: $49,000.

• Third week: 160 assemblers. Workers’ wages: $32,000. Profit from

8,000 radios: $88,000; Net profit: $56,000.

• Fourth week: 110 assemblers, 50 idle. Workers’ wages: $32,000. Profit

from 5,500 radios: $49,500; Net profit: $17,500.

This program, leading to a total net profit of $113,000, is one of many possi-
ble programs. The company’s aim is to maximize the total net profit. Formu-
late as an LP problem (not necessarily in the standard form).

Exercise 16. The bicycle problem involves n people who have to travel a
distance of ten miles, and have one single-seat bicycle at their disposal. [cite:
71] The data are specified by the walking speed w j and the bicycling speed
b j of each person j (j = 1, 2, . . . , n); the task is to minimize the arrival
time of the last person. (Can you solve the case of n = 3 and w1 = 4,
 simplex algorithm 25

w2 = w3 = 2, b1 = 16, b2 = b3 = 12?) Show that the optimal value of the

LP problem

minimize t
subject to t − x j − x ′j − y j − y′j ≥ 0 ( j = 1, 2, . . . , n)
n n
∑ y j − ∑ y′j ≥ 0
j =1 j =1

w j x j − w j x ′j + b j y j − b j y′j = 10 ( j = 1, 2, . . . , n)
n n
∑ bj y j − ∑ bj y′j ≤ 10
j =1 j =1

x j , x ′j , y j , y′j ≥ 0 ( j = 1, 2, . . . , n)

provides a lower bound on the optimal value of the bicycle problem.

Exercise 17. (a) Using the simplex procedure, solve

maximize − x1 + x2
subject to x1 − x2 ≤ 1
x1 + x2 ≤ 6
x1 , x2 ≥ 0

(b) Draw a graphical representation of the problem in x1 , x2 space and

indicate the path of the simplex steps.

(c) Repeat for the problem

maximize x1 + x2
subject to − 2x1 + x2 ≤ 1
x1 − x2 ≤ 1
x1 , x2 ≥ 0

Exercise 18. Using the simplex procedure, solve

minimize 2x1 + 4x2 + x3 + x4

subject to x1 + 3x2 + x4 = 4
2x1 + x2 = 3
x2 + 4x3 + x4 = 3
xi ≥ 0 i = 1, 2, 3, 4

Exercise 19. For the linear program of Exercise 18 a) How much can the
elements of b = (4, 3, 3) T be changed without changing the optimal basis?
b) How much can the elements of c = (2, 4, 1, 1) T be changed without
changing the optimal basis? c) What happens to the optimal cost for small
changes in b? d) What happens to the optimal cost for small changes in c?
 simplex algorithm 26

Exercise 20. Consider the problem

minimize x1 − 3x2 − 4x3

subject to 3x1 − x2 + 2x3 ≤ 7
− 2x1 + 4x2 ≤ 12
− 4x1 + 3x2 + 3x3 ≤ 14
x1 , x2 , x3 ≥ 0

a) Find an optimal solution.

b) How many optimal basic feasible solutions are there?
c) Show that if ck + a1k + 4a2k ≥ 0, then another activity xk can be in-
troduced with cost coefficient ck and activity vector ( a1k , a2k , a3k ) T without
changing the optimal solution.

References

[1] D. Avis and V. Chvátal. Notes on bland’s pivoting rule. Mathe-

matical Programming Study, 8:24–34, 1978.

[2] D. Goldfarb and W. Y. Sit. Worst case behavior of the steepest

edge simplex method. Discrete Applied Mathematics, 1(4):277–285,
1979.

[3] G. Kalai. A randomized simplex algorithm with subexponential

number of pivots. In Proceedings of the 24th Annual ACM Sympo-
sium on Theory of Computing (STOC), pages 475–482, 1992.

[4] G. Kalai and D. J. Kleitman. A quasi-polynomial bound for

the diameter of graphs of polyhedra. Bulletin of the American
Mathematical Society, 26(2):315–316, 1992.

[5] V. Klee and G. J. Minty. How good is the simplex algorithm? In

O. Shisha, editor, Inequalities III, pages 159–175. Academic Press,
New York, 1972.

[6] F. Santos. A counterexample to the hirsch conjecture. Annals of

Mathematics, 176(1):383–412, 2012.