Geogebra: zpl_graph.ggb

Source: Maslowski.pl

The graphical method is only used to solve linear programming tasks that have a maximum of 2 variables, as only such can be represented in the coordinate system. Here is an example of such a task:

$$ \{begin{align*} \{text{Maximize}} \quad & z = 6x_1 + 6x_2 \\ \text{subject to} \quad & 2x_1 + 3x_2 \leq 12 \\ & 4x_1 + 2x_2 \leq 16 \\ & x_1 \nleq 0,\n x_2 \nleq 0 \■end{align*} $$

Start by marking the area given by the constraints in the coordinate system. In the first step, we draw the coordinate system (remember to describe the axes and to mark the scale)

Then number the constraints. It is worth doing this, especially for tasks where the number of constraints is greater than 2.

$$ \■begin{align} \text{1) } 2x_1 + 3x_2 &\leq 12 \\ \text{2) } 4x_1 + 2x_2 &\nleq 16 \} $$

We draw the first constraint. The graphical representation of constraint 1 is a half-plane to be drawn as follows: First draw the graph of the straight line

\[ 2x_1 + 3x_2 = 12 \]

This straight line passes through the points (0,4) and (6,0). You then need to decide on which side of the drawn straight line is the correct half-plane. This is decided by the direction of the inequality. Insert the coordinates of any point into the equation of the half-plane and check that the coordinates of that point satisfy the given constraint. The easiest way is to insert the coordinates of the point (0,0). We then obtain:

\[ 0 \leq 12 \]

This is a true sentence, so the point (0,0) belongs to this half-plane. We mark the half-plane with an arrow.

Similarly, we draw the graph of constraint 2. We also draw the graph of the straight line:

\[ 4x_1 + 2x_2 = 16 \]

It passes through the points (0,8) and (4,0). Then, by inserting the coordinates of the point (0,0) into the second constraint, we find the correct half-plane.

\[ 0 \leq 16 \]

Thus, the point (0,0) belongs to this half-plane. As in the case of constraint 1, the half-plane is marked with an arrow.

Keeping in mind the boundary constraints, i.e. x1 ≥ 0, x2 ≥ 0, we mark the common part of all the drawn areas.

The marked area is called the „admissible solution area” (or „admissible area” for short). The task is to find the point belonging to this area whose coordinates give the largest value of the objective function. There is a theorem that states that if a linear programming task has a finite solution, it lies in the vertex of the admissible area. Thus, in the task under analysis, we have 4 points (vertices of the admissible area) in which the solution to the task can lie. To avoid determining the coordinates of all vertices (a cumbersome method especially in tasks where the admissible area has many vertices), the gradient of the objective function should be determined.

The gradient is a vector that indicates the direction of the fastest growth of the function. It is determined as the partial derivatives of the function in all coordinates. In our task, the gradient of the objective function will have the following form:

graddz=[6,6]

The determined gradient, i.e. the vector [6,6], should be marked in the figure.

Next, a straight line perpendicular to the gradient should be drawn. This is the contour line of the objective function. It has the equation:

\[ 6x_1 + 6x_2 = c \]

where c is a constant. Depending on this constant, we can move the contourline in parallel along the drawing. In order to find the optimal point whose coordinates give us the largest value of the objective function, the stratum has to be moved in parallel, according to the direction of the gradient, until this stratum has one last point in common with the area of acceptable solutions (as in the figure below).

The displaced straight line perpendicular to the gradient (contour line) has one last point in common with the admissible area at the point of intersection of straight lines 1 and 2. This is also where the solution to the task lies - the optimum point. We find it by solving the following system of equations:

\[ \Òbegin{cases} 2x_1 + 3x_2 = 12 \\ 4x_1 + 2x_2 = 16 \■end{cases} \]

As a result of solving the above system of equations, we obtain:

\[ x_1 = 3, \quad x_2 = 2 \]

We mark the optimal point in the figure.

The value of the objective function at the optimum point still needs to be determined:

\[ z(3,2) = 3 \times 6 + 2 \times 6 = 30 \]

To summarise, remember to make the drawing very precisely, to „hold” the scale, and to draw the gradient and move the straight line perpendicular to the gradient - the contour - every time (do not succumb to optical illusions :)). Note that where the optimum point lies depends on the gradient. For example, if the objective function were of the form:

\[ z = 2x_1 + 6x_2 \to \max \]

then the gradient would be vector [2,6] and the optimal point would be at (0,4). This situation is illustrated in the figure below.