Читать книгу Optimizations and Programming - Bouchaib Radi, Ghias Kharmanda, Michel Ledoux - Страница 17

The graphical method works by plotting lines and searching for a solution as follows:

 – identify the admissible domain;

 – identify the contours;

 – contours perpendicular to the vector c, and therefore mutually parallel;

 – each value of z is associated with a contour;

 – the value of z increases in the direction of c.

EXAMPLE 1.2.– Consider, again, the example from earlier. Its mathematical model is defined by the following linear program:

The intersection of the half-planes determined by the lines corresponding to each constraint represents the set of solutions that satisfy the constraints (shaded area). The direction of the cost function is given by

This gives us the optimal solution by sliding the line with this direction upwards, while keeping it parallel, until its intersection with the y-axis is maximal. Graphical solutions are of course only applicable with programs of, at most, three variables (see Figure 1.2).

Figure 1.2. Graphical solution. For a color version of this figure, see www.iste.co.uk/radi/optimizations.zip

EXAMPLE 1.3.– Consider the linear program:

[1.2]

The graphical solution is shown in Figure 1.3. We have z* = −2, with and

Figure 1.3. Graphical solution with isoprofit lines. For a color version of this figure, see www.iste.co.uk/radi/optimizations.zip