LINEAR PROGRAMMING

Linear programming is the process of taking various linear inequalities relating to some situation, and finding the “best” value obtainable under those conditions. A typical example would be taking the limitations of materials and labor, and then determining the “best” production levels for maximal profits under those conditions.

In “real life”, linear programming is part of a very important area of mathematics called “optimization techniques”. This field of study (or at least the applied results of it) are used every day in the organization and allocation of resources. These “real life” systems can have dozens or hundreds of variables, or more. In algebra, though, you’ll only work with the simple (and graphable) two-variable linear case.

The general process for solving linear-programming exercises is to graph the inequalities (called the “constraints”) to form a walled-off area on the x,y-plane (called the “feasibility region”). Then you figure out the coordinates of the corners of this feasibility region (that is, you find the intersection points of the various pairs of lines), and test these corner points in the formula (called the “optimization equation”) for which you’re trying to find the highest or lowest value.

Example 1. Minimize z=3x–y subject to x–y≤1, x+y≤5, x≥0, and y≥0.
Solution:

vertex	value of z at vertex
(0,0)	z=3(0)-(0)=0
(1,0)	z=3(1)-(0)=3
(3,2)	z=3(3)-(2)=7
(0,5)	z=3(0)-(5)=-5

[Fig-1]
The minimum value of z is –5 and this occurs at (0, 5).

Example 2.
Solve the following linear programming problem graphically:

Minimise Z=200x+500y…(1)
subject to the constraints:
x+2y≥10...(2)
3x+4y≤24...(3)
x≥0,y≥0 ...(4)
Solution:
The shaded region in Fig-2 is the feasible region ABC determined by the system of constraints (2) to (4), which is bounded. The coordinates of corner points

Corner Point	Corresponding value of Z
(0,5) (4,3) (0,6)	2500 2300 ← minimum 3000

[Fig-2]
A, B and C are (0,5), (4,3) and (0,6) respectively. Now we evaluate Z=200x+500y at these points.
Hence, minimum value of Z is 2300 attained at the point (4, 3)

Example 3: Minimizing an Objective Function
Find the minimum value of the objective function
z=5x+7y [Objective function]
where x≥0 and y≥0, subject to the constraints

2x+3y≥6 3x–y≤15 –x+y≥4 2x+5y≥27

}Constraints

Solution:
The region bounded by the constraints is shown in Fig-3,

[Fig-3]
By testing the objective function at each vertex, you obtain

At (0,2): z=5(0)+7(2)=14 (Minimum value of z) At (0,4): z=5(0)+7(4)=28 At (1,5): z=5(1)+7(5)=40 At (6,3): z=5(6)+7(3)=51 At (5,0): z=5(5)+7(0)=25 At (3,0): z=5(3)+7(0)=15.

So, the minimum value of z is 14, and this occurs when x=0 and y=2.

Example 4. Minimise Z=3x+5y subject to the constraints:
x+2y≥10
x+y≥6
3x+y≥8
x,y≥0
Solution:
We first draw the graphs of x+2y=10, x+y=6, 3x+y=8. The shaded region ABCD is the feasible region (R) determined by the above constraints. The feasible region is unbounded. Therefore, minimum of Z may or may not occur. If it occurs, it will be on the corner point.

Corner Point	Value of Z
A(0,8)	40
B(1,5)	28
C(2,4)	26←smallest
D(10,0)	30

[Fig-4]
Let us draw the graph of 3x+5y<26 as shown in Fig-4 by dotted line. We see that the open half plane determined by 3x+5y<26 and R do not have a point in common. Thus, 26 is the minimum value of Z.

💎 How Can We Maximize and Minimize an Objective Function to the Constraints?