What is a Basic Feasible Solution in Linear Programming

In Linear Programming (LP) a basic feasible solution is one that also belong to the feasible region or problem area can be represented by a feasible solution in implementing the Simplex Method satisfying nonnegative conditions. In this context, a basic solution corresponds to one of the vertices whose coordinate feasibility domain or solution can be represented by a set of active constraints for the model. To develop the above concept consider the following mathematical optimization problem (linear):

linear programming example

The graphical solution of the above problem using Geogebra is presented in the following graph:

graphical-linear-programmin

The hatched area corresponds to the feasibility of the problem domain, in particular 5 identifying vertices have arbitrarily called A, B, C, D and E. The optimal solution of the linear model is reached in the vertex C where X=100 and Y=350 with optimal value V(P)=3.100. Note that this solution can be obtained by solving a system of equations with the constraints 1 and 3 (R1 and R3) in equality.

Consequently the vertex C besides being a basic solution is an optimal basic solution. As for the vertices A, B, D and E are feasible basic solutions (not optimal) because the application of the simplex method at least one non-basic variable have negative reduced cost (which will improve the current value of the function target). The table below is obtained by taking the problem into standard form, adding S1, S2 and S3 as slack variables for the constraints 1, 2 and 3, respectively (R1, R2 and R3).

initial-tableau-simplex-method

Both non-basic variables (initial) X and Y have negative reduced cost (-3 and -8) for both X=0 and Y=0 if it is a feasible basic solution ( vertex A) is not optimal solution. To continue the show will make an iteration of the simplex method incorporating the variable Y to the base (reduced cost criterion “more negative”) and where the minimum quotient Min {1600/4;1700/2; 350/1} = 350 ==> S3 leaves the base:

first-iteration-simplex-method

The basic solution is now X=0 and Y=350 ( point B ), however, the reduced cost of the variable X is still negative and thus we are not yet at the optimum. Consequently X enters the base and get the minimum quotient: Min {200/2; 1000/6} = 100 ==> S1  leaves the base:

optimal-tableau-simplex-method

Finally the optimal solution (optimal is reached basic feasible solution) with X=100 and Y=350 ( point C) where all non-basic variables (S1 and S3) have reduced greater or equal to zero cost, fulfilling the optimality criterion .

What happens to the vertices D and E? also are (suboptimal) feasible basic solutions could be found for example by incorporating in the first instance (initial table) to the variable X to the base. In this way, the vertex E should then one iteration and the vertex D in a second iteration. Note that there are other (non-basic) feasible solutions such as X=100 and Y=100 belonging to the domain of feasible solutions but can not be represented by solving a system of equations.

Rating: 3.9. From 9 votes.
Please wait...

, , , ,

Sin Comentarios aun. Se el primero en comentar!

Leave a Reply

Our Site is Proudly Hosted on