LP: Graphic resolution

Graphics resolution

It is possible to solve the problems having two variables (or two constraints for a dual problem) directly by a graphic resolution. The resolution process takes place in three stages:

  1. Achievable domain
  2. Plot the objective function
  3. Determine the optimal solution

Achievable domain

For this, we represent each constraint in the graph, hatching or coloring the side that does not satisfy the constraint.
Thus, we highlight a definition field or feasible domain, any point in the domain of definition satisfies all the constraints of the mathematical model.

Let's take it linear program next :

Graphical resolution realizable domain linear programming

Let us draw the domain of definition:

Adding the first constraint and the type of variables

Graphical resolution realizable domain linear programming

Addition of the second constraint

Graphical resolution realizable domain linear programming

Addition of the third constraint

Graphical resolution realizable domain linear programming

Plot the objective function

In order to solve the problem, we represent the objective function at point (100,0) then at various points (following the gradient of the objective function) until the objective function has only one point or one facet of the definition field.

Graphical resolution realizable domain linear programming

The gradient of the objective function is (350,300). The z value therefore increases when the objective function is moved in the same direction as the vector (350,300), therefore by moving towards the northeast corner. We can clearly see in the following figure that the value of z has increased by taking another line of the objective function.

Graphical resolution realizable domain linear programming

We then obtain the optimal overall solution (s). If we trace the objective function again by following the gradient, the line will be outside the domain of definition.

Optimal solutions

The optimal solution (s) are the last point (s) before the line of the objective function leaves the domain of definition.

Graphical resolution realizable domain linear programming

The optimal solution is found at the intersection of the first and second constraint, therefore satisfies both constraints. The solution vector is the solution of the system:

Graphical resolution realizable domain linear programming

The solution of this system is (122,78) which gives z = 66100.

The four optimal solution possibilities

There are four possibilities:

  • either a unique solution exists (a point);
  • either an infinity of solutions (one facet);
  • either the solution is not bounded, the line of the objective function will always be in the domain of definition by following the gradient;
  • or there is no solution, for example if the domain is empty.
To share