Operations research

The graphical method

The graphical method is a technique for solving linear programming problems that is primarily used for cases with two variables. Although it is not very practical for a large number of variables, it is very useful for interpreting and analyzing the results and sensitivity of the problem. However, in cases where a greater number of variables is required, it is possible to use other techniques such as projection onto a plane.

The graphical method is based on the graphical representation of the constraints of the linear programming model, which allows for the determination of the solution polygon or feasible region. According to the fundamental theorem of linear programming, if a solution exists that satisfies the constraints of the model, it will be found at one of the vertices of the feasible region.

The graphical method is a technique that has been the subject of debate among different authors throughout history. Some of them have pointed out that this methodology presents certain assumptions or limitations.

One of the most well-known assumptions is that it does not allow for sensitivity analysis in the case of simultaneous changes in the right-hand side of the constraints or in the coefficients of the objective function. Another assumption is that binary variables cannot be considered in the model.

However, with the advancement of technology, it is possible to use tools like GeoGebra to overcome these limitations and perform sensitivity analysis with simultaneous changes and consider binary variables in the model. Therefore, these assumptions are no longer valid in the present.

Prior considerations

It is necessary to remember that the graphical method is a solution method, and therefore, a previous stage corresponds to mathematical modeling.

graphical_method

The problem

We will use a technically formulated problem in order to approach each of the phases of the graphical method.

The Hilados y Tejidos “Salazar” factory needs to produce two different quality fabrics, Standard and Premium. 500 kg of thread a, 300 kg of thread b, and 108 kg of thread c are available. To obtain one meter of Standard fabric daily, 125 grams of a, 150 grams of b, and 72 grams of c are needed; to produce one meter of Premium fabric per day, 200 grams of a, 100 grams of b, and 27 grams of c are needed. The Standard fabric is sold for $4000 per meter and the Premium fabric is sold for $5000 per meter. If the maximum profit must be obtained, how many meters of Standard and Premium fabrics must be produced?

 

Linear programming modeling

As mentioned earlier, the basis for using the graphical method corresponds to the linear programming mathematical model:

Variables

x: Quantity of daily meters of Standard fabric to be produced

y: Quantity of daily meters of Premium fabric to be produced

Constraints

0.12x + 0.2y <= 500 Kg of thread “a”

0.15x + 0.1y <= 300 Kg of thread “b”

0.072x + 0.027y <= 108 Kg of thread “c”

x >= 0 Non-negativity constraint

y >= 0 Non-negativity constraint

Objective function

Zmax = 4000x + 5000y (Maximize total revenues given in $)


Solution by graphical method

1: Graphing the constraints

The process for finding the feasible solution begins with the graphical representation of the constraints; each of them must be represented in such a way as to limit the possible solutions of the model.

At this point, we must consider two possibilities:

  1. That we carry out the entire process manually
  2. That we use a graphical software that simplifies mathematical operations

In this case, we will show the entire methodology for carrying out the manual procedure, while at the same time we will use a graphical software to represent each phase of the method.


Each constraint corresponds to a linear function, which means that it is graphically represented by a line in the Cartesian plane. To draw a line in the Cartesian plane, it is necessary to know at least two points of the function.

To begin drawing the constraints, it is essential to set the constraints to zero, so that we can use the clearing of the equations to start the tabulation that will give us the coordinates to draw each of the graphs.

We set the constraints to zero:

0.12x + 0.2y = 500          (Constraint 1)

0.15x + 0.1y = 300          (Constraint 2)

0.072x + 0.027y = 108    (Constraint 3)

x = 0                               (Constraint 4)

y = 0                               (Constraint 5)

We begin with Constraint 1: We find the first two coordinates. To find the coordinates, we usually set one of the variables to zero, so that the second one can be cleared more easily.

For example, when x = 0:

0.12(0) + 0.2y = 500

0.2y = 500

500/0.2 = y

2500 = y

When y = 0:

0.12x + 0.2(0) = 500

0.12x = 500

x = 500/0.12

x = 4167

Constraint 1 x y
First coordinate 0 2500
Second coordinate 4167 0

C1


Constraint 2:

When x = 0

0.15(0) + 0.1y = 300

0.1y = 300

y = 300/0.1

y = 3000

When y = 0

0.15x + 0.1(0) = 300

0.15x = 300

x = 300/0.15

x = 2000

Constraint 2 x y
First coordinate 0 3000
Second coordinate 2000 0

r2


Constraint 3:

When x = 0

0.072x + 0.027y = 108

0.072(0) + 0.027y = 108

0.027y = 108

y = 108/0.027

y = 4000

When y = 0

0.072x + 0.027(0) = 108

0.072x = 108

x = 108/0.072

x = 1500

Constraint 3 x y
First coordinate 0 4000
Second coordinate 1500 0

r3


Nonnegativity constraints:

r4 y r5

Paso 2: Find the solution area (Solution polygon)

After all the restrictions are represented graphically, the next step is to find the feasible area or solution polygon; which is nothing more than the region in which all points satisfy all the constraints, that is, they are feasible.

To delimit the feasible area, it is necessary to determine the sense of the constraints. Here I stop for a bit; since I prefer to explain it in detail. Each line that represents a constraint divides the Cartesian plane into two half-planes: On one side and on the other side of the constraint. Well, only the points on one side can be considered feasible.

If we want to find the feasible area, we must start by finding the feasible side of each of the constraints; this is what I call: evaluating the sense of the constraints.

Let’s see an example for the first constraint:

Evaluating the direction of Constraint 1

This is very simple, we just need to evaluate any point on the cartesian plane, it must correspond to one side of the constraint. If the constraint is satisfied or not, we will know the direction of it.

0.12x + 0.2y <= 500

It is normal to want to simplify the arithmetic process, and it is common to use the point of coordinates (0, 0):

0.12(0) + 0.2(0) <= 500

0 <= 500

True!

Since 0 is less than or equal to 500, we can affirm that on that side of the constraint are the values that satisfy it.

The green region represents the area where all points that satisfy constraint 1 are located.

When the function of the constraint (line on the plane) passes through the point (0, 0) it will not be useful to evaluate the constraint. Remember that a point must be chosen that is on one side of the constraint.

To find the feasible region, the procedure must be repeated for each constraint of the problem. Since all constraints must be met, the feasible region will be the result of the intersection of all feasible regions of each constraint of the model.

rf

The shaded area on the previous graph corresponds to the feasible region.

3: Finding the optimal solution

Once the feasible region that meets all constraints of the model has been found, the next step is to find the optimal solution. It is important to differentiate between feasibility and optimality.

The optimal solution will depend on the optimization criterion of the objective function and, according to the fundamental theorem of linear programming, it is found at one of the vertices of the feasible area. Technically, the optimal solution is found at the vertices for any optimization criterion: minimum value (minimization) and maximum value (maximization).

There are mainly two procedures for finding the optimal solution:

  1. Graphically
  2. Evaluating all vertices (Brute force)

Graphically

This method requires the graphical representation of the objective function. At least twice.

It is necessary to graph the objective function and find the direction in which it approaches the optimization criterion. How do we do it? In each case, we need two points to graph the first line that represents the objective function; these two points must result in the same Z. Let’s see:

Zmax = 4000x + 5000y

Objective function (Z1) 4000(x) 5000(y) z
First coordinate 4000(500) 5000(0) 2000000
Second coordinate 4000(0) 5000(400) 2000000

Ahora, podemos intentar con otra representación de la función objetivo que se acerque aún más al criterio de optimización: Maximizar; es decir, un Z2 mayor a Z1. Veamos:

Función objetivo (Z2) 4000(x) 5000(y) z
Primera coordenada 4000(1000) 5000(0) 4000000
Segunda coordenada 4000(0) 5000(800) 4000000

By graphing both functions, both Z1 and Z2, we will have the following:

One can see how the objective function approaches the optimization criterion (increases) as it moves upwards. The next step is to find the last vertex of the feasible area (in an upward direction in this case), where a line parallel to the objective function does not intersect the feasible polygon. At this point, the optimal solution will be found.

Use the GeoGebra scroll bar to move the objective function. You will see that the last vertex where the objective function does not cut the feasible area is the intersection of Constraint 2 and Constraint 3 (Vertex C). This point corresponds to the optimal solution.

To find the value of this coordinate, it is necessary to solve a 2×2 linear equation, and several solution methods can be considered, such as:

  • Substitution method
  • Equality method
  • Reduction or Elimination method
  • Gauss elimination method
  • Gauss-Jordan elimination method
  • Determinant method

There are many methods available, but one of the most commonly used is the reduction or elimination method, which is very easy to apply.

The reduction or elimination method consists of equalizing the coefficients of one of the variables by multiplying one or both equations, taking into account that these coefficients are equal but with opposite signs.

Equation 1                        0,12x + 0,2y = 500

Equation 2                        0,15x + 0,1y = 300  multiplicamos por (-2)

Equation 3 (2*(-2))          -0,30x –  0,2y = -600

Sum 1 y 3                        -0,18x = -100

Solve for  “x”                     x = -100 / (-0,18)

                                         x = 555,55

Then we substitute x = 555.55 into either of the original equations in order to solve for “y”.

Equation 1                     0,12x + 0,2y = 500

We substitute “x”          0,12(555,55) + 0,2y = 500

Solve for “y”                  66,666 + 0,2y = 500

                                      0,2y = 500 – 66,666

                                      0,2y = 433,334

                                      y = 433,334 / 0,2

                                      y = 2166,67

In this way, we have obtained the values for “x” and “y“.

x: Quantity of daily meters of Standard fabric to be produced

y: Quantity of daily meters of Premium fabric to be produced

Quantity of daily meters of Standard fabric to be produced = 555,55

Quantity of daily meters of Premium fabric to be produced = 2166,67

The obtained contribution (by replacing the variables in the objective function) is:

Zmax = 4000x + 5000y

Zmax = 4000(555,55) + 5000(2166,67)

Zmax = $13.055.550 

Now we can compare the results with those obtained by solving in Excel, but remember that the method of searching for the optimal solution in the graphic method that we use is geometric and that there is a much more complex but equally effective way, which is the vertex iteration method. This consists of finding all the coordinates of the vertices and then evaluating the objective function at each coordinate. Each coordinate gives us a value in “x” and another in “y”, then we replace these values in the objective function “4000x + 5000y = ?” and evaluate the results by selecting the highest value.

Bryan Salazar López

By profession, Industrial Engineer, Master in Logistics, specialized in productivity, with interest and experience in modeling processes under sustainability indicators. Founder of Ingenieriaindustrialonline.com, site where research contributions, articles and references are collected.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Back to top button