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

*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):*

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

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****of the linear model is reached in the**

*optimal solution***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).

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:

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:

Finally the optimal solution (* optimal* is reached

*) with*

**basic feasible solution****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.

## No comments yet. Be the first to comment!