1. Introduction

The simplex algorithm is a common method of solving linear programs. This module will define common terms used for linear programs; provide a step by step explanation of the method; provide a two dimensional graphical interpretation of the method; and demonstrate a free software tool that replicates the simplex method.

In linear algebra, the goal is to find the point that satisfies a set of equations. In linear programs, we have a set of equations that form a feasible space. Any point within that space satisfies those constraints. Another function is introduced where the goal is to maximize or minimize its value. This function is called the objective. So, the goal is to find the best solution from that set of solutions in the feasible space.

Linear programs are the set of optimization problems where all of the variable exponents are 1. This would be lines in 2D and surfaces in 3D and higher dimensions. A linear program has a set of decision variables whose values we are trying to determine based on a set of constraint equations (boundaries for the problem) and an objective function which is being maximized or minimized.