Linear Programming: Finding the Maximum with a family of Parallel Lines

A BIG IDEA of linear programming
If the feasible set of a linear programming problem with two variables is bounded (contained inside some big circle; equivalently, there is no direction in which you can travel indefinitely while staying in the feasible set), then, whether the problem is a minimization or a maximization, there will be an optimum value. Furthermore:
β–Έ there will be some corner point of the feasible region that is an optimum
πŸ’‘ if there is more than one optimum corner point then there will be exactly two of them, they will be adjacent, and any point in the line between them will also be optimum.

Figure-A illustrates this graphically.

lp a

lp b

lp c

Figure-A. As an objective function increases, the objective function line moves toward a comer. In (e) the objective function moves out of the feasible region and out of consideration.

Linear programming is a strategy for finding the optimum value – either maximum or minimum – of a linear function that is subject to certain constraints.

These constraints, or restrictions, are stated as a system of linear inequalities.

Solving Linear Programming Problems Graphically
1. Graph the feasible region.
2. Find the vertices of the region.
3. Evaluate the objective function at each vertex.
4. Select the vertices that optimize the objective function.

a) If the feasible region is bounded the objective function will have both a maximum and a minimum.

b) If the feasible region is unbounded and the objective function has an optimal value, the optimal value will occur at a vertex of the feasible region.

Note: If the optimum value occurs at two vertices, its value is the same at both vertices and along the line segment joining them.

Example 1. Find the maximum and minimum value of z=x+3y subject to the constraints –x+3y≀6, x-3yβ‰₯ 6, and x+yβ‰₯6.
✍
1. Graph the feasible region.

feasible region g

2. Find the vertices.
3. Evaluate the objective function at each vertex.
4. The maximum value of z is 12 and occurs at (3, 3).
The minimum value of z is 6 and occurs at both (0, 2) and (6, 0) and at every point along the line joining them.

Rewriting the objective function z=x+3y in slope-intercept form gives. This equation represents a family of parallel lines, one for each value of z.

the corresponding line passes through the feasible region

As z increases through values 0, 3, 6, 9, 12, and 15, the corresponding line passes through the feasible region.

The point at which the family of lines first meets the feasible region gives the minimum value of z, and the point at which the family of lines leaves the feasible region gives the maximum.

Example 2: Solving a Linear Programming Problem
Find the maximum value of

z=3x+2y [Objective function]

subject to the constraints listed below.

xβ‰₯0
yβ‰₯0
x+2y≀4
xy≀1
}Constraints

Solution:
The constraints form the region shown in Figure B.

constraints form the region

[Figure B]

At the four Vertices of this region, the objective function has the values listed below.

At (0, 0): z=3(0)+2(0)=0
At (1, 0): z=3(1)+2(0)=3
At (2, 1): z=3(2)+2(1)=8 (Maximum value of z)
At (0, 2): z=3(0)+2(2)=4

So, the maximum value of z is 8, and this occurs when x=2 and y=1.

In Example 2, test some of the interior points of the region. You will see that the corresponding values of z are less than 8. Here are some examples.

At (1, 1): z=3(1)+2(1)=5
At (1, Β½): z=3(1)+2(Β½)=4
At (3/2, 1): z=3(3/2)+2(1)=13/2

To see why the maximum value of the objective function in Example 2 must occur at a vertex, write the objective function in the form

y=-3/2β‹…x+Β½z.

This equation represents a family of lines, each of slope -3/2. Of these infinitely many lines, you want the one that has the largest z-value, while still intersecting the region determined by the constraints. In other words, of all the lines whose slope is -3/2, you want the one that has the largest y-intercept and intersects the specified region, as shown below. Such a line will pass through one (or more) of the vertices of the region.

infinitely many lines

[Figure C]

The graphical method for solving a linear programming problem works whether the objective function is to be maximized or minimized. The steps used are precisely the same in either case. After you have evaluated the objective function at the vertices of the set of feasible solutions, simply choose the largest value as the maximum and the smallest value as the minimum. For instance, the same test used in Example 2 to find the maximum value of z can be used to conclude that the minimum value of z is 0, and that this occurs at the vertex (0, 0).

Look at the statement signed by emoticon πŸ’‘ above at the beginning paragraph! That statement is realized by the following link below
πŸ’Ž Linear Programming: How Can We Maximize and Minimize an Objective Function to the Constraints?πŸ‘ˆ

RELATED POSTs