3.2 Basic and non-basic variables

The simplex method is a powerful tool for solving linear programming problems. It uses basic and non-basic variables to find optimal solutions, with basic variables forming the current solution and non-basic variables set to zero.

Understanding how basic solutions are represented in simplex tableaux is crucial. The method involves identifying basic variables, extracting their values, and updating the tableau through pivoting to improve the solution iteratively.

Basic and Non-Basic Variables in the Simplex Method

Basic vs non-basic variables

• Basic variables form current basic feasible solution correspond to identity matrix columns in simplex tableau equal number of constraints (slack variables)
• Non-basic variables excluded from current solution set to zero correspond to non-identity matrix columns in simplex tableau (decision variables)

Basic solutions in simplex tableaux

1. Locate identity matrix columns representing basic variables
2. Extract values from right-hand side column for basic variable values
3. Set non-basic variables to zero
4. Resulting solution represents current basic feasible solution ($x_B = B^{-1}b$)

Basic variables and basis matrix

• Basis matrix square matrix of basic variable columns dimensions match constraint count
• Basis matrix properties include invertibility enables basic feasible solution computation
• Each basis matrix column links to specific basic variable determines objective function coefficients for basic variables

Entering and leaving variables

• Entering variable non-basic variable selected to join basis chosen by most negative reduced cost in objective row (largest improvement potential)
• Leaving variable basic variable exiting basis determined by minimum ratio test smallest non-negative ratio (maintains feasibility)
• Pivot element intersection of entering variable column and leaving variable row
• Update process employs Gaussian elimination transforms pivot column to unit vector adjusts tableau elements accordingly