Engineering Optimization: Theory and Practice, Fourth Edition

3.4 Geometry of Linear Programming Problems 125

on the various machines are given by

10 x+ 5 y≤ 2500 (E 1 )

4 x+ 10 y≤ 2000 (E 2 )

x+ 1. 5 y≤ 450 (E 3 )

Since the variablesxandycannot take negative values, we have

x≥ 0

y≥ 0

(E 4 )

The total profit is given by

f (x, y)= 50 x+ 100 y (E 5 )

Thus the problem is to determine the nonnegative values ofxandythat satisfy the
constraints stated in Eqs.(E 1 ) ot (E 3 ) nd maximize the objective function given bya
Eq.(E 5 ) The inequalities. (E 1 ) ot (E 4 ) an be plotted in thec xyplane and the feasible
region identified as shown in Fig. 3.3 Our objective is to find at least one point out of the
infinite points in the shaded region of Fig. 3.3 that maximizes the profit function(E 5 ).
The contours of the objective function,f, are defined by the linear equation

50 x+ 100 y=k=constant

Askis varied, the objective function line is moved parallel to itself. The maximum
value off is the largestkwhose objective function line has at least one point in
common with the feasible region. Such a point can be identified as pointGin Fig. 3.4.
The optimum solution corresponds to a value ofx∗= 871 .5,y∗= 251 .0 and a profit
of $21,875.00.

Figure 3.3 Feasible region given by Eqs.(E 1 )to(E 4 ).