Mathematics Form 1-4 : CHAPTER SIXTY ONE – LINEAR PROGRAMMING

Specific Objectives

By the end of this topic, the learner should be able to:

• Form linear inequalities based on real-life situations;
• Represent linear inequalities on a graph;
• Solve and interpret the optimum solution of linear inequalities;
• Apply linear programming to real-life situations.

Content

• Formation of linear inequalities
• Analytical solutions of linear inequalities
• Solutions of linear inequalities by graphs
• Optimization (including objective function)
• Application of quadratic equations to real-life situations

Forming Linear Inequalities

In linear programming, we form inequalities representing given conditions involving real-life situations. These inequalities help us model constraints and limitations in various problems.

Example

Esha is five years younger than his sister. The sum of their ages is less than 36 years. If Esha’s age is x years, form all the inequalities in x for this situation.

Solution

The age of Esha’s sister is x + 5 years.

Therefore, the sum of their ages is:

x + (x + 5) years

Thus,

2x + 5 < 36

2x < 31

x < 15.5

Also, x > 0 (age is always positive).

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, 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 is used daily in the organization and allocation of resources. These real-life systems can have dozens or hundreds of variables or more. In algebra, however, you’ll typically 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 find the coordinates of the corners of this feasibility region (i.e., the intersection points of the various pairs of lines) and test these corner points in the formula (called the “objective function”) for which you’re trying to find the highest or lowest value.

Example

Suppose a factory wants to produce two types of hand calculators, type A and type B. The cost, labor time, and profit for each calculator are summarized in the following table:

Suppose the available money and labor are Ksh 18,000 and 1,600 hours respectively. What should the production schedule be to ensure maximum profit?

Solution

Let be the number of type A calculators and be the number of type B calculators. Let y be the profit. We want to maximize subject to:

where is the total profit.

Solution by Graphing

Solutions to inequalities formed to represent given conditions can be determined by graphing the inequalities and then reading off the appropriate values (possible values).

Example

A student wishes to purchase not less than 10 items comprising books and pens only. A book costs Sh 20 and a pen Sh 10. If the student has Sh 220 to spend, form all possible inequalities from the given conditions and graph them clearly, indicating the possible solutions.

Solution

Let the number of books be x and the number of pens be y. Then the inequalities are:

1. x + y ≥ 10
2. 20x + 10y ≤ 220
3. x ≥ 0, y ≥ 0

This simplifies to:

1. x + y ≥ 10
2. 2x + y ≤ 22

All the points in the unshaded region represent possible solutions. A point with coordinates (x, y) represents x books and y pens. For example, the point (3, 10) means 3 books and 10 pens could be bought by the student.

Optimization

The determination of the minimum or maximum value of the objective function ax + by is known as optimization. The objective function is an equation to be minimized or maximized.

Example

A contractor intends to transport 1000 bags of cement using a lorry and a pick-up. The lorry can carry a maximum of 80 bags per trip while the pick-up can carry a maximum of 20 bags per trip. The pick-up must make more than twice the number of trips the lorry makes, and the total number of trips must be less than 30. The cost per trip for the lorry is Ksh 2000, and Ksh 900 for the pick-up. Find the minimum expenditure.

Solution

Let x and y be the number of trips made by the lorry and the pick-up respectively. The conditions are given by the following inequalities:

1. 80x + 20y ≥ 1000 (to transport all bags)
2. y > 2x (pick-up makes more than twice the trips of the lorry)
3. x + y < 30 (total trips less than 30)
4. x, y ≥ 0 (non-negativity)

The total cost of transporting the cement is given by 2000x + 900y. This is called the objective function.

The graph below shows the inequalities.

From the graph, we can identify 7 possible corner points.

Note:

Coordinates represent the number of trips. For example, (7, 22) means 7 trips by the lorry and 22 trips by the pick-up. The possible expenditure in shillings can be calculated as follows:

1. Cost at (7, 22): 2000(7) + 900(22) = 14,000 + 19,800 = 33,800
2. Cost at (8, 18): 2000(8) + 900(18) = 16,000 + 16,200 = 32,200
3. Cost at (9, 16): 2000(9) + 900(16) = 18,000 + 14,400 = 32,400
4. Cost at (10, 14): 2000(10) + 900(14) = 20,000 + 12,600 = 32,600
5. Cost at (11, 12): 2000(11) + 900(12) = 22,000 + 10,800 = 32,800
6. Cost at (12, 10): 2000(12) + 900(10) = 24,000 + 9,000 = 33,000
7. Cost at (13, 8): 2000(13) + 900(8) = 26,000 + 7,200 = 33,200

We note from the calculation that the least amount the contractor would spend is Sh 32,200. This occurs when the lorry makes 8 trips and the pick-up 18 trips. When possibilities are many, determining the solution by calculation becomes tedious. The alternative method involves drawing the graph of the function we wish to maximize or minimize, the objective function. This function is usually of the form ax + by, where a and b are constants.

For this, we use the graph above and choose a convenient point (x, y) close to the feasible region. For example, the point (5, 10) was chosen to give an initial value of 2000x + 900y = 19,000. We then draw the line 2000x + 900y = 19,000. Such a line is referred to as a search line.

Using a ruler and set square, slide the set square keeping one edge parallel until the edge strikes the feasible point nearest (see the dotted line). From the graph, this point is (8, 18), which gives the minimum expenditure as seen earlier. The feasible point furthest from the line gives the maximum value of the objective function.

The determination of the minimum or maximum value of the objective function ax + by is known as optimization.

Note:

The process of solving linear programming problems is as follows:

1. Form the inequalities satisfying given conditions
2. Formulate the objective function
3. Graph the inequalities
4. Optimize the objective function

This entire process is called linear programming.

Example

A company produces gadgets in two colors: red and blue. The red gadgets are made of steel and sell for Ksh 30 each. The blue gadgets are made of wood and sell for Ksh 50 each. A unit of the red gadget requires 1 kilogram of steel and 3 hours of labor. A unit of the blue gadget requires 2 board meters of wood and 2 hours of labor. There are 180 hours of labor, 120 board meters of wood, and 50 kilograms of steel available. How many units of red and blue gadgets must the company produce and sell to maximize revenue?

Solution

The Graphical Approach

Step 1. Define all decision variables.

Let: x₁ = number of red gadgets to produce and sell

x₂ = number of blue gadgets to produce and sell

Step 2. Define the objective function.

Maximize R = 30x₁ + 50x₂ (total revenue in Ksh)

Step 3. Define all constraints.

(1) x₁ ≤ 50 (steel supply constraint in kilograms)

(2) 2x₂ ≤ 120 (wood supply constraint in board meters)

(3) 3x₁ + 2x₂ ≤ 180 (labor supply constraint in man-hours)

x₁, x₂ ≥ 0 (non-negativity requirement)

Step 4. Graph all constraints.

Then determine the area of feasible solutions:

Note:

• The area under the line marked blue is the feasible region.
• We shade the unwanted region outside the trapezium marked blue.

Optimization

List all corner points (identify the corresponding coordinates), and pick the best in terms of the resulting value of the objective function.

(1) x₁ = 0, x₂ = 0, R = 30(0) + 50(0) = 0

(2) x₁ = 50, x₂ = 0, R = 30(50) + 50(0) = 1500

(3) x₁ = 0, x₂ = 60, R = 30(0) + 50(60) = 3000

(4) x₁ = 20, x₂ = 60, R = 30(20) + 50(60) = 3600 (the optimal solution)

(5) x₁ = 50, x₂ = 15, R = 30(50) + 50(15) = 2250

End of topic

Past KCSE Questions on the Topic

1. A school has to take 384 people for a tour. There are two types of buses available, type X and type Y. Type X can carry 64 passengers and type Y can carry 48 passengers. They have to use at least 7 buses.

   1. Form all the linear inequalities which represent the above information.
   2. On the grid provided, draw the inequalities and shade the unwanted region.
   3. The charges for hiring the buses are:
   4. Type X: Ksh 25,000
   5. Type Y: Ksh 20,000
   6. Use your graph to determine the number of buses of each type that should be hired to minimize the cost.

2. An institute offers two types of courses: technical and business courses. The institute has a capacity of 500 students. There must be more business students than technical students, but at least 200 students must take technical courses. Let x represent the number of technical students and y the number of business students.

   1. Write down three inequalities that describe the given conditions.
   2. On the grid provided, draw the three inequalities.
   3. If the institute makes a profit of Ksh 2,500 to train one technical student and Ksh 1,000 to train one business student, determine:
   1. The number of students that must be enrolled in each course to maximize the profit.
   2. The maximum profit.

3. A draper is required to supply two types of shirts A and B.

   The total number of shirts must not be more than 400. He has to supply more type A than type B; however, the number of type A shirts must be more than 300 and the number of type B shirts must not be less than 80.

   Let x be the number of type A shirts and y be the number of type B shirts.

   1. Write down in terms of x and y all the linear inequalities representing the information above.
   2. On the grid provided, draw the inequalities and shade the unwanted regions.
   3. The profits were as follows:

   Type A: Ksh 600 per shirt

   Type B: Ksh 400 per shirt

   1. Use the graph to determine the number of shirts of each type that should be made to maximize the profit.
   2. Calculate the maximum possible profit.

4. A diet expert makes up a food product for sale by mixing two ingredients N and S. One kilogram of N contains 25 units of protein and 30 units of vitamins. One kilogram of S contains 50 units of protein and 45 units of vitamins. The food is sold in small bags each containing at least 175 units of protein and at least 180 units of vitamins. The mass of the food product in each bag must not exceed 6 kg.

   If one bag of the mixture contains x kg of N and y kg of S:

   1. Write down all the inequalities, in terms of x and y, representing the information above.
   2. On the grid provided, draw the inequalities by shading the unwanted regions.
   3. If one kilogram of N costs Ksh 20 and one kilogram of S costs Ksh 50, use the graph to determine the lowest cost of one bag of the mixture.

5. Esha Flying Company operates a flying service. It has two types of aeroplanes. The smaller one uses 180 litres of fuel per hour while the bigger one uses 300 litres per hour.

   The fuel available per week is 18,000 litres. The company is allowed 80 flying hours per week.

   (a) Write down all the inequalities representing the above information.

   (b) On the grid provided on page 21, draw all the inequalities in (a) above by shading the unwanted regions.

   (c) The profits on the smaller aeroplane is Ksh 4,000 per hour while that on the bigger one is Ksh 6,000 per hour. Use your graph to determine the maximum profit that the company made per week.

6. A company is considering installing two types of machines, A and B. The information about each type of machine is given in the table below.

   Machine	Number of operators	Floor space	Daily profit
   A	2	5m2	Ksh 1,500
   B	5	8m2	Ksh 2,500

   The company decided to install x machines of type A and y machines of type B.

   1. The number of operators available is 40.
   2. The floor space available is 80 m².
   3. The company is to install not less than 3 type A machines.
   4. The number of type B machines must be more than one third the number of type A machines.

   (b) On the grid provided, draw the inequalities in part (a) above and shade the unwanted region.

   (c) Draw a search line and use it to determine the number of machines of each type that should be installed to maximize the daily profit.