PHPSimplex

Optimizing resources with Linear Programming

Graphical method theory

Graphical interpretation of Simplex method

Graphical method, or Geometric method, allows solving simple linear programming problems intuitively and visually. This method is limited to two or three problems decision variables since it is not possible to graphically illustrate more than 3D.

Although in reality only rarely problems arise with two or three decision variables, nonetheless it is very useful this solving methodology. To graphically show possible situations such as the existence of a single optimal solution, alternatives optimal solutions, the nonexistence of solution and unboundedness, it is a visual aid to interpret and understand the simplex method algorithm (much more sophisticated and abstract) and concepts surrounding it.

The process phases of problems solving by Graphical method are:

1. Draw a Cartesian coordinate system in which each decision variable is represented by an axis.
2. Establish a measurement scale for each axis suitable to its associated variable.
3. Draw in the coordinate system the constraints of the problem, including non-negativity (which will be the axes themelves). Note that an inequality defines a region which will be the half plane limited by the straight line you have to consider the restriction as an equality, while an equation defines a region that is the straight line itself.
4. The intersection of all regions determines the feasible region or solution space (which is a convex set). If this region is not empty, it will continue with the next step. Otherwise, there is no point that satisfies all constraints simultaneously, so the problem will not be solved, denominating not feasible.
5. Determine the extreme points (polygon or polyhedron vertices) that shape the feasible region. These points will be the candidates for the optimal solution.
6. Evaluate the objective function at each vertex and the optimal solution will be that (or those) which maximize (or minimize) the resulting value.

An example of the Graphical method is provided to more easily development and application understanding.

X

PHPSimplex
Version 0.81