Why do we need (or use) identity matrix while proceeding simplex method

Question

I've been studying for operational research recently.I did comprehend how the algorithm works.However I could not figure out why do we need identity matrix and why do we need to create it while generating simplex tableaus.

Answer 1

The simplex algorithm moves from one basic feasible solution (BFS) to another, which means it needs to start with a known BFS. The identity matrix (typically consisting of columns for slack/surplus variables) gives you an easily identified nonsingular matrix that hopefully corresponds to a feasible solution. That is your starting BFS. When you do not have an obvious candidate for the first BFS, you can use the "two phase simplex" algorithm, which creates an artificial starting solution (not necessarily feasible, and usually not feasible) and works toward feasibility.