Solution of Linear Programming Problems

Every business works with limited resources. A factory has only so many workers, so much raw material and a fixed amount of money. A shop has only so much space on its shelves. Each of them still wants the largest possible profit, or the smallest possible cost of production. Linear programming is a method of making such choices with mathematics. It is used in industry, trade and business to plan how sources, means and capital should be used, so that investment and production cost stay as low as possible and profit becomes as high as possible.

So in linear programming we try to minimize cost and maximize production and profit. To minimize a quantity means to make it as small as it can be. To maximize it means to make it as large as it can be. Neither can be done without limit, because every business works under fixed conditions. Linear programming finds the best value that those conditions allow.

Suppose a factory makes two kinds of goods. Let \( x \) be the number of units of the first kind and \( y \) the number of units of the second kind. If each unit of the first kind earns a profit of Rs. 10 and each unit of the second kind earns Rs. 12, the total profit is:

\[ Z = 10x + 12y \]

The factory wants \( Z \) to be as large as possible. That is its objective. But the machines can only run for a limited number of hours, and this gives conditions such as \( x + 2y \leq 12 \) and \( 3x + 2y \leq 24 \). The factory also cannot make a negative number of goods, so \( x \geq 0 \) and \( y \geq 0 \). These conditions are the constraints.

There are two methods of solving linear programming problems: the graphical method and the simplex method. At this level we solve them by the graphical method only, which turns the whole problem into a picture on graph paper.

Every linear programming problem at this level is solved by the same four steps, in this order:

• Step 1: Draw all the given linear inequalities on one graph.
• Step 2: Find the feasible region, which is the common solution region of all the inequalities.
• Step 3: The feasible region is a polygon. Read the coordinates of its vertices from the graph and put each one into the objective function.
• Step 4: If the objective function is to be maximized, pick the greatest of these values. If it is to be minimized, pick the smallest.

Two graphing skills are used again and again inside these steps. To draw the boundary line of an inequality, change the inequality sign into an equals sign and find any two points on that line, usually the points where it crosses the axes. To decide which side of the line is the solution, put a test point, usually the origin \( O(0, 0) \), into the inequality. If the result is true, the solution lies on the side of the line that contains the test point. If it is false, the solution lies on the other side.

Find the maximum and minimum values of the function \( Z = 10x + 12y \) under the conditions \( x + 2y \leq 12 \), \( 3x + 2y \leq 24 \), \( x \geq 0 \) and \( y \geq 0 \).

Step 1: The objective function to be tested is:

\[ Z = 10x + 12y \]

Step 2: Changing the first two inequalities into equations, so that their boundary lines can be drawn:

\[ x + 2y = 12 \quad \ldots (i) \]

\[ 3x + 2y = 24 \quad \ldots (ii) \]

Step 3: Finding two points on line (i). Putting \( x = 0 \) gives \( y = 6 \), and putting \( y = 0 \) gives \( x = 12 \):

So line (i) passes through the points \( (0, 6) \) and \( (12, 0) \).

Step 4: Putting the test point \( O(0, 0) \) into \( x + 2y \leq 12 \):

\[ 0 + 2 \times 0 \leq 12 \]

\[ 0 \leq 12 \]

This is true. So the solution region of \( x + 2y \leq 12 \) lies on the side of line (i) that contains the origin.

Step 5: Finding two points on line (ii). Putting \( x = 0 \) gives \( y = 12 \), and putting \( y = 0 \) gives \( x = 8 \):

So line (ii) passes through the points \( (0, 12) \) and \( (8, 0) \).

Step 6: Putting the test point \( O(0, 0) \) into \( 3x + 2y \leq 24 \):

\[ 3 \times 0 + 2 \times 0 \leq 24 \]

\[ 0 \leq 24 \]

This is also true, so the solution region of \( 3x + 2y \leq 24 \) lies on the side of line (ii) that contains the origin.

Step 7: Applying the last two constraints. The inequality \( x \geq 0 \) keeps the region to the right of the Y-axis, and \( y \geq 0 \) keeps it above the X-axis. So the feasible region lies in the first quadrant.

Step 8: Shading the part of the graph that obeys all four constraints at once. The arrows on each line point to its solution side, and the shaded part is where all of them overlap:

The feasible region is the polygon OABC. Its vertices are \( O(0, 0) \), \( A(8, 0) \), \( B(6, 3) \) and \( C(0, 6) \).

Step 9: Checking the vertex B exactly, because it is where lines (i) and (ii) cross. Subtracting equation (i) from equation (ii):

\[ (3x + 2y) - (x + 2y) = 24 - 12 \]

\[ 2x = 12 \]

\[ x = 6 \]

Putting \( x = 6 \) into equation (i):

\[ 6 + 2y = 12 \]

\[ y = 3 \]

So B is \( (6, 3) \), exactly as the graph shows.

Step 10: Putting the coordinates of each vertex into \( Z = 10x + 12y \):

\[ O(0, 0):\ Z = 10 \times 0 + 12 \times 0 = 0 \]

\[ A(8, 0):\ Z = 10 \times 8 + 12 \times 0 = 80 \]

\[ B(6, 3):\ Z = 10 \times 6 + 12 \times 3 = 96 \]

\[ C(0, 6):\ Z = 10 \times 0 + 12 \times 6 = 72 \]

Hence the maximum value of Z is 96, at the point B(6, 3), and the minimum value of Z is 0, at the point O(0, 0). In the factory story, making 6 units of the first kind and 3 units of the second kind gives the greatest profit the machines allow.

The feasible region does not always touch the origin. Find the maximum and minimum values of \( Z = 5x + 2y \) under the conditions \( x + 2y \geq 4 \), \( x + y \leq 5 \), \( x \geq 0 \) and \( y \geq 0 \).

Step 1: Changing the first two inequalities into equations:

\[ x + 2y = 4 \quad \ldots (i) \]

\[ x + y = 5 \quad \ldots (ii) \]

Step 2: Finding where each line crosses the axes, by putting \( x = 0 \) and then \( y = 0 \):

Step 3: Putting the test point \( O(0, 0) \) into \( x + 2y \geq 4 \):

\[ 0 + 2 \times 0 \geq 4 \]

\[ 0 \geq 4 \]

This is false. So the solution region of \( x + 2y \geq 4 \) lies on the side of line (i) away from the origin.

Step 4: Putting the test point \( O(0, 0) \) into \( x + y \leq 5 \):

\[ 0 + 0 \leq 5 \]

This is true, so the solution region of \( x + y \leq 5 \) lies on the side of line (ii) that contains the origin.

Step 5: Shading the common region. Together with \( x \geq 0 \) and \( y \geq 0 \), the feasible region is the band between the two lines in the first quadrant. It is the polygon PQRS with vertices \( P(4, 0) \), \( Q(5, 0) \), \( R(0, 5) \) and \( S(0, 2) \).

Step 6: Putting the coordinates of each vertex into \( Z = 5x + 2y \):

\[ P(4, 0):\ Z = 5 \times 4 + 2 \times 0 = 20 \]

\[ Q(5, 0):\ Z = 5 \times 5 + 2 \times 0 = 25 \]

\[ R(0, 5):\ Z = 5 \times 0 + 2 \times 5 = 10 \]

\[ S(0, 2):\ Z = 5 \times 0 + 2 \times 2 = 4 \]

Hence the maximum value of Z is 25, at Q(5, 0), and the minimum value of Z is 4, at S(0, 2). This time the minimum is not 0, because the origin is not inside the feasible region.

Sometimes the feasible region is already drawn and the constraints have to be found from it. This is the graphical method run backwards, and it is done one boundary line at a time:

• Read two marked points on the boundary line.
• Find the equation of the line through them. When the points are \( (a, 0) \) and \( (0, b) \) on the axes, the intercept form \( \frac{x}{a} + \frac{y}{b} = 1 \) gives it quickly.
• Choose a point that clearly lies in the shaded part, often the origin, and put it into the left side of the equation.
• Choose the sign that makes the statement true for that point. A solid line belongs to the region, so the sign is \( \leq \) or \( \geq \). A dashed line does not, so the sign is \( < \) or \( > \).

In the graph below, the boundary line is solid and passes through the marked points \( (0, 3) \) and \( (2, 0) \), and the side containing the origin is shaded.

Step 1: Writing the line through \( (2, 0) \) and \( (0, 3) \) in intercept form:

\[ \frac{x}{2} + \frac{y}{3} = 1 \]

Step 2: Multiplying both sides by 6 to clear the fractions:

\[ 3x + 2y = 6 \]

Step 3: Putting the shaded point \( O(0, 0) \) into the left side:

\[ 3 \times 0 + 2 \times 0 = 0 \]

Since 0 is less than 6 and the line is solid, the shaded region is \( 3x + 2y \leq 6 \). The third marked point \( (4, -3) \) confirms the line, because \( 3 \times 4 + 2 \times (-3) = 6 \).

Now look at a dashed line through \( (0, 1) \) and \( (2, 0) \). Its intercept form is \( \frac{x}{2} + \frac{y}{1} = 1 \), which becomes \( x + 2y = 2 \). The origin gives 0, which is less than 2, but this time the origin is not in the shaded part. So the shaded side is the one where \( x + 2y \) is greater than 2, and because the line is dashed the region is \( x + 2y > 2 \).

A region bounded by two or three lines is read in exactly the same way. Each line gives one inequality, and the same shaded point is tested in all of them. Read each of these graphs line by line: