Linear Programming Definitions
In a linear programming situation, the function for which we are trying to find a maximum or minimum value is called the objective function.
The constraints in a linear programming problem form a system of inequalities. The graph of this system is called the feasible region. This region contains all of the ordered pairs that satisfy all of the constraints.
The feasible region is in the shape of a convex polygon. It has been proven that the maximum or minimum value of the objective function will always be found at a vertex of the feasible polygon region.
Example #3
Maximize the objective function P = 2x + y
The graph of the feasible region is shown below. The maximum value for P will be found at one of the vertices. The vertices of the feasible region are:
A(0, 4), B(2, 3), C (3, 0) and D(0, 0)
We take each of the those ordered pairs and plug them into P to determine which will give the maximum value for P.
A (0,4): P = 2(0) + 4 = 4
B (_,_)
C (_,_)
D (_,_)
Answer:
B (2,3)
C (3,0)
D (0,0)
We take each of the those ordered pairs and plug them into P to determine which will give the maximum value for P.
P = 2x + y
B (2,3) : P = 2(_) +_=_
C (3,0) : P = 2(_) +_=_
D (0,0) : P = 2(_) +_=_
Answer:
B (2,3) : P = 2(2) +3=7
C (3,0) : P = 2(3) +0=6
D (0,0) : P = 2(0) +0=0
Therefore, the maximum value of P is __ and occurs when x = __ and y = __ which is point __.
Answer:
Therefore, the maximum value of P is 7 and occurs when x = 2 and y = 3 which is point B.
Example #4
Minimize the objective function:
C = 0.2x + 0.3y
The graph of the feasible region is shown. The vertices of the region are:
A (_,_)
B (_,_)
C (_,_)
D (_,_)
Answer:
A (0,5)
B (5,0)
C (3,0)
D (0,4)
Plug in each of the vertices to C to determine the minimum value.
C = 0.2x + 0.3y
A : C = 0.2(_) + 0.3(_)
B : C = 0.2(_) + 0.3(_)
C : C = 0.2(_) + 0.3(_)
D : C = 0.2(_) + 0.3(_)
Answer:
A : C = 0.2(0) + 0.3(5)
B : C = 0.2(5) + 0.3(0)
C : C = 0.2(3) + 0.3(0)
D : C = 0.2(0) + 0.3(4)
Plug in each of the vertices to C to determine the minimum value.
C = 0.2x + 0.3y
A : C = 0.2(0) + 0.3(5) = _
B : C = 0.2(5) + 0.3(0) = _
C : C = 0.2(3) + 0.3(0) = _
D : C = 0.2(0) + 0.3(4) = _
Answer:
A : C = 0.2(0) + 0.3(5) = 1.5
B : C = 0.2(5) + 0.3(0) = 1
C : C = 0.2(3) + 0.3(0) = 0.6
D : C = 0.2(0) + 0.3(4) = 1.2
The minimum value of C is __ and occurs at point __
where x = __ and y = __ .
Answer: The minimum value of C is 0.6 and occurs at point C
where x = 3 and y = 0 .
