Optimization

(BFS)

In a geometric way, any feasible region of any LP is a convex set because every constraint

will split space in half and each half space is a convex set. The intersection of a convex set

is a convex set. In this sense the BFS are the extreme point and are finite numbers. Of

course, if a LP has an optimal solution, there should be an extreme point that is the optimal

solution.

Let’s introduce another concept. For any LP with m constraints, two BFSs are adjacent if

they have m-1 basic variables in common.

Simplex method (graphical resolution):

Considering the last sentence about adjacent points, we can talk about the geometric

resolution. If we represent the convex polyhedron to solve the LP problem it is necessary to

start with the first FBS and calculate the value of the objective function (Z). Then, we

calculate the value of Z for the adjacent point and pass with that point that has a greater

value of Z.

Simplex method (pivot rules):

The key elements are: entering variables, leaving variables, ratio test and pivoting. These

are the elements to solve a LP problem.

Let’s start with an example of maximization problem:

z = 3x + 2x and s.t.

1 2

2x + x <= 9

1 2

x + 2x <= 9

1 2

x >= 0

i

Now, we get the standard form of a LP by re-writing the inequalities with equalities and add

two slack variables that help us:

z - 3x + 2x = 0 and s.t.

1 2

2x + x + s = 9

1 2 1

x + 2x + s = 9

1 2 2 On the bottom we have the simplex canonical form,

while on the top the simplex tableau.

The BV appears with the coefficient equal to 1 in one equation and not all in others.

Also, the slack variables can be used as a BV if RHS (right-hand side) of the constraints is

non negative.

So, in this case we have s and s as BV with values s = 9, s = 9, x = 0, x = 0. The

1 2 1 2 1 2

objective function is z = 3x + 2x . The question is:

1 2

Can z be improved by increasing some NBV from its current value of 0 while holding all

others NBV as 0?

The answer is yes, by increasing x tha in the tableau has the most negative coefficient

1

value for R0 (-3). Now, we need to determine the largest we can make x so that all BVs are

1

still non-negative. We determine this through the ratio test:

rhs of constraints / coef of entering variable in constraint row

The rule is that the row with the smallest ratio wins. In our case, in R1 the x has the

1

smallest ratio (4,5 < 9)

Now, we make the entering variable (x ) use EROs (simple elementary operation rows) and

1

divide by 2: This process is

called pivoting on R1 and x takes the place of s (leaving variable) as BV in R1. Then we

1 1

will do the EROs for the other rows

The new BV are x and s , while the objective function is z = 27/2 + x 1/2 - s 3/2. The

1 2 2 1

question is the same: Can z be improved by increasing some NBV from its current value of 0

while holding all others NBV as 0?

The answer is yes, we can go ahead ourself to obtain this results

A canonical tableau is optimal (for a max problem) if each NBV has a non negative

coefficient in R0.