LINEAR PROGRAMMING

SUBJECT : MATHEMATICS UNIT : 2 TOPIC : LINEAR PROGRAMMING TARGET GROUP : S.4 TIME REQUIRED : 640 minutes (16 periods) 3 weeks Brief description of topic

Linear programming is a branch of Mathematics which deals with problems of maximizing or minimizing linear functions by finding the optimum solution. The problems are given in form of statements based on certain conditions. Linear inequalities are formulated depending on the conditions commonly referred to as constraints. Our study is concerned with problems in x and y variables as represented on the Cartesian plane and the optimum solution are obtained using the graphical method. The wanted region or the feasible region which satisfies the condition is obtained from the graph. Linear programming helps in solving practical solutions in maximizing profits and productivity while minimizing costs and wastage. It is applied in business, factories, and industries and in the transport sector. It is also used making budgets in companies and during economic planning. NB: For problems which involve so many constraints, companies use computer programming which follows the same concept.

Learning objectives By the end of this topic, the learners should be bale to (i) Define the term – linear programming

                         	  - Constraints
                        - Objective function 

- Optimum solution - Feasible region - Lattice points (ii) Formulate linear inequalities based on real life situation (iii) Represent the linear inequalities on the graph (iv) Show the feasible region of the inequalities (v) List the lattice points from the feasible region (vi) Solve and interprete the optimum solution(s) of the linear inequalities (vii) Acquire the following Job-Mark generic skills i.e. team work, planning/organizational, communication, numeracy and decision making.

Main content and concepts to emphasize Before the teacher introduces this topic, she /he should review the following: Plotting of a line (keeping in mind whether it is continuous or dotted) Shading the unwanted region Listing the integral points in the wanted region

Materials required Graph papers, rulers, pencils.

Activity 1: Shading of regions This activity should be done in pairs Represent each of the following inequalities on a graph (i) x ≤ 5 (ii) x › 7 (iii) x ≥ -3 (iv) y ‹ -1 (v) x ≥ 0 (vi) y ≥ 0

     (b)	      (i)	 y ≤ 2x –y	(ii)	y ‹ 5-2x	(iii)	y ≥ 7-x
	      (iv)	 y › 3x+2
     (c)	      On the same axes, by shading the unwanted region represent 

The teacher should introduce the concept of linear programming using real life examples. She / he should first help the students to understand the definitions of the terms: objective function, constraints, lattice points, feasible region. Activity 2: On objective function This activity helps the students to understand the term objective function. 1. Match the following professionals in the school environment with the objective function. Professionals objective function School nurse maximize profits as costs are minimized Teacher maximumly supervises the activities, programmes Business person in school Student minimizes food wastage and spoilage Caterer monitors health issues of the student Head teacher increases awareness and knowledge to students Maximize the opportunities given by the school

Solution:

2.	Write down three personal targets / goals / objective functions. 

Understanding the term “Constraint” The teacher should engage the student in the activity below:

Student’s objective function Some of the limiting factors Wants maximum satisfaction - fixed amount of money from his/her pocket money - fixed quality of goods in the canteen of shs.10,000/= - price of goods - prohibited goods in the canteen e.g. chicken, Rolex, cell phones, etc

The limiting factors are what we refer to as constraints. Activity 3 Ask the students to list down the objective function(s) and constraints of the following Large scale farmer Computer club Car manufacturer Teacher’s credit scheme

NB: The teacher is reminded to keep the choice of questions in the business line. Encourage them to come up with a well organized structure as below.

Students should then be informed that in Mathematics these constraints are represented using the linear inequalities as we shall see later. Then the objective function is represented as a linear function.

Understanding the term feasible region

The teacher should refer to the already drawn graphs Should ask the students to identify the wanted region In linear programming the wanted region is what is called the feasible region.

Understanding the term lattice points Ask the students to identify all the points in the wanted region Some students will even list points such as (4.5, 7.5) In linear programming since we’re dealing with a practical situation we only identify integral points. These integral points are what we call the lattice points.

Understanding the term optimum solution One of the above points when substituted in the objective function gives either a maximum or minimum value. This value is called the optimum solution.

Understanding the term linear programming Activity 4 Design your personal programme / timetable identifying the activities from 6.00 am to 6.00 pm in intervals of 1 hour. What are some of the constraints that enabled you to follow it up?

Definition of linear programming Linear programming is a branch of Mathematics which deals with problems of maximizing or minimizing the objective function by finding the optimum solution.

LINEAR INEQUALITIES

FORMATION OF LINEAR INEQUALITIES Linear inequalities are mathematical sentences with the symbols >, <, ≥ or ≤. They are identified with the word phrases below: At least, at most, does not exceed, maximum, minimum, fewer than, more than, less than.

Task:

Relate the above word phrases with the symbols.

Word phrase Symbol At least At most Does not exceed Maximum Minimum Fewer than More than Less than ≥ ≤ ≤ ≤ ≥ < > <

Which other word phrases can be represented with any of the above symbols?

Task 2: Formation of inequalities using the word phrases. Sarah is at least 18 years old. After selling 10 of his cows, Jason had over 15 left. Mugimu went shopping with sh. 10,000 to buy groundnuts and sugar. If he bought a kg of groundnuts at sh. 3000 each and a kg of sugar at sh. 2000. Write down three inequalities to describe this situation. On K & A ranching scheme; 3,000,000/= is available for planting the land with maize and beans. Planting maize costs 120,000 per hectare and whereas the beans cost 150,000/= per hectare. Given that x represents the number of hectares for maize and y the number of hectares for beans. Form four inequalities from the above information. Solutions At least means “greater or equal to” ≥. Let y represent the number of years → y ≥ 18. Over means greater Let c be the total number of cows → c – 10 > 15 let g be the number of kg of groundnuts let s be the number of kg of sugar 3000g + 2000s ≤ 10,000 (total cost of both g & s must not exceed 10,000 3g + 25 ≤ 10 (encourage them to reduce the inequality) g ≥ 0 (since one cannot buy negative kg of groundnuts) s ≥ 0 (but one can decide not to buy any) 4. (i) 120,000x + 150,000y ≤ 3,000,000 4x + 5y ≤ 100 Number of hectares x + y ≤ 15 (iii) non-negativity condition for maize x ≥ 0 (iv) non-negativity condition for beans y ≥ 0

Activity 5 Let the students work in pairs, read the information below and answer the following questions that follow: Students should be given graph papers.

Example: UNEB / 2 1999 A wild life club in a certain school wishes to go for an excursion to a national park. The club has hired a mini-bus and a bus to take the students. Each trip for the bus is sh. 50,000 and that of a mini-bus is sh. 30,000. The bus has a capacity of 54 students and mini-bus 18 students. The maximum number of students allowed to go for the excursion is 216.the number of trips the bus makes do not have to exceed those made by the mini-bus. The club has mobilized as much as sh. 300,000 for transportation of the students. If x and y represent the number of trips made by the bus and mini-bus respectively. Before giving the questions first give the students the following tasks: What is the objective function? How many constraints are there to this problem?

(i) Write down five inequalities representing the above information. (ii) Plot these inequalities on the same axes. By shading the unwanted region, show the region satisfying all the above inequalities. List the possible number of trips each vehicle can make. State the greatest number of students who went for the excursion.

Solution: Help the students to identify the constraints in the information and the club’s objective function.

     (i)	      Club’s objective function: to take (transport) the students for an excursion.

Constraints type of transport: mini-bus and a bus cost of each trip capacity of each vehicle number of trips

The inequalities are then developed depending on the constraints: Type of vehicle bus mini-bus Number of trips x y Cost of each trip 50,000 30,000 max. 300,000 Capacity of each vehicle 54 18 max. 216

(a) Number of trips: x ≤ y (b) Cost of trip: 50,000x + 30,000y ≤ 300,000 5x + 3y ≤ 30 (c) Capacity: 54x + 18y ≤ 216 3x + y ≤ 12

Note: Since there are no negative trips made (d) → x ≥ 0 And (e) y ≥ 0

Plotting the above inequalities: Help the students to identify the boundary lines for: (i) x ≤ y : boundary line is x = y (continuous line) (ii) 5x + 3y ≤ 30: boundary line is 5x + 3y = 30 (iii) 3x + y ≤ 12  : boundary line is 3x + y = 12

Encourage the students to draw one line at ago and shade its unwanted region. (iv) (0,0), (0,1), (0,2), (0,3), (0,4), (0,5), (0,6), (0,7) (0,8), (0,9), (0,10), (1,1), (1,2), (1,3), (1,4), (1,5) (1,6), (1,7), (1,8), (2,2), (2,3), (2,4), (2,5), (2,6) (3,3) (v) The greatest number of students who went for the excursion: = 216 students.

UNEB 1998 Paper 1 Qn 17. Supporters of a certain soccer team wish to accompany their team for a soccer match. They are to travel by a taxi and a mini-bus. The capacity of the taxi is 18 people while that of the mini-bus is 27 people. The number of supporters to go will not exceed 108. each trip the taxi and mini-bus make costs sh. 24,000 and sh. 30,000 respectively. The money contributions for transportation of the supporters is sh. 240,000. The number trips made by the taxi should not exceed those made by the mini-bus by more than 2. if x and y are the number of trips made by the taxi and mini-bus respectively.

Task: a) Ask the students in their groups to read the passage above underlining the key word phrases then answer the following:

 	(i)	What is the main objective function of the above?

(ii) How many constraints are in the above mentioned passage? b) (i) Write down fine inequalities representing the above information. (ii) Plot on the same axes the above inequalities. (iii) By shading the unwanted region, show the region satisfying all the inequalities. (iv) List the possible number of trips each vehicle will make, given that all the money for transport is to be used. (v) What is the greatest number of supporters that was transported?

Solution : Key word phrases will not exceed, exceed, more than available Main objective: to transport supporters of a soccer team Constraints : 3 Constraint (i) Type of transport taxi mini-bus (ii) Capacity 18 27 max. 108 (iii) Cost per trip 24,000 30,000 available 240,000 (iv) Number of trips x y

(b) (i) inequalities capacity 18x + 27y ≤ 108 2x + 3y ≤ 12 ………. (i) Cost 24,000x + 30,000y ≤ 240,000 8x + 10y ≤ 80 ………. (ii) Number of trips x ≤ y + 2 ……………….. (iii) None-negativity x ≥ 0 …………………… (iv) Y ≥ 0 …………………… (v)

(b) Graph work: For 2x + 3y ≤ 12 boundary line: 2x + 3y = 12 Points For 8x + 10y ≤ 80 boundary line: 8x + 10y = 80 (full)

For x ≤ y + 2 boundary line: x = y+2

(iv) From the graph, we read the lattice points from the feasible region: (0,0), (0,1), (0,2), (0,3), (0,4), (1,0), (1,1) (1,2), (1,3), (2,0), (2,1), (2,2), (3,1), (3,2)

We then substitute the lattice points in the original cost inequality such that the total cost = 240,000/= 24,000 × 3 + 30,000 × 2 = 132,000/=

UNEB 1996 / Paper 2

A factory makes two kinds of bottle tops “Coca-cola” tops and “Pepsi tops”. The same equipment can be used to make either. In making Coca-cola tops one man can survive 10 machines and this batch will give a profit of pounds sterling (£) 50 per week. Pepsi tops yield a profit of £ 250 a week, using 25 machines and 8 men. There are 200 machines and 40 men are available. By taking x batches of Coca-cola tops and y batches of Pepsi tops, write down inequalities for: (i) the number of machines used (ii) the number of men employed (iii) an expression for profit p

Use these inequalities to draw a suitable graph showing the region which satisfies them.

From your graph, determine the numbers of Coca-cola and Pepsi tops which should be made to obtain the maximum profit. Hence find the maximum profit.

UNEB 2001 / Paper 1

A wholesaler wishes to transport 870 crates of soda from a factory. He has a lorry which can carry 150 crates at a time and pick-up truck which can carry 60 crates at a time. The cost of each journey for the lorry is Sh. 25,000 and for the pick-up Sh. 20,000. The pick-up makes more journeys than the lorry because it travels faster. The amount of money available for transporting the soda is Sh. 220,000.

(i) Write down five inequalities representing the above information. (ii) Plot a graph for the inequalities, shading out the unwanted regions. (iii) How many journeys should the lorry and the pick-up make so as to keep the transport cost as low as possible. State how much money the wholesaler saves by making these journeys. (12 marks)

UNEB 2003 / Paper 1

A farmer plans to plant an 18 hectare field with carrots and potatoes. The farmer’s estimates for the project are shown in the table below:

CARROTS POTATOES Planting and harvesting costs per hectare. Sh. 95,000 Sh. 60,000 Number of working hours per hectare. 12 days 4 days Expected profit per hectare. Sh. 228,000 Sh. 157,000

The farmer has only Sh 1,140,000 to invest in the project. The total number of working days is 120.

a) By letting x represent the number of hectares to be planted with carrots and y the number of hectares to be planted with potatoes, write down the inequalities for (i) cost of the project (ii) working days (iii) number of hectares used in the project (iv) the possibility that the field will at least be used for planting either carrots or potatoes. b) Write down an expression for the profit, p, in terms of x and y. c) (i) On same axes plot graphs of the inequalities in (a) and (b) above, shading out unwanted regions. (ii) Use your graphs to determine how the farmer, should use the field to maximize profit. Hence find the farmer’s maximum profit. (12 marks)

UNEB 1992 / Paper 1

A school lorry and a school bus are to be used to transport a certain function. The capacities of the lorry and the bus are 50 and 70 students respectively. The number of students to attend the function should not exceed 350. Each trip made by the lorry or the bus cost Sh 3,000. The money available for the transportation is Sh. 18,000. The number of trips made by the lorry should not exceed that made by the bus. If x and y are the number of trips made by the lorry and the bus respectively.

Write down five inequalities representing this information. Plot these inequalities on the same axes. By shading the unwanted region satisfying all the inequalities. If all the available money for transport is to be used, list all the possible number of trips that each vehicle will make. (Assume that for each trip a vehicle makes it must be full) Find the greatest number of students that can be transported.

UNEB 1993 / Paper 2

A manufacturer makes two types of hoes A and B. the following conditions apply to daily production.

Each type of A costs Sh. 3000 and each type of B costs Sh. 5000 and the manufacturer has a maximum of Sh. 450,000 available. Due to labour shortage the production of type A plus four times that of B should not exceed 160. A study of the market recommended that the number of type B produced should not exceed twice the number of type A produced. Given that x hoes of type A and y hoes of type B are made, write down three inequalities apart x ≥ 0; y ≥ 0, satisfying the above conditions. Show graphically the region containing the points satisfying the above conditions. Taking x + 2y as a suitable expression for the manufacturer’s profit find the number of each type of hoe that should be made to obtain the greatest profit.

UNEB 1995 / Paper 2

A soccer club wishes to intensively train its top and second division players by residential training in preparation for soccer league tournaments. The cost of maintaining a player is Sh. 60,000 and Sh. 45,000 per top and per second division player. The club has a maximum of Sh. 1,800,000 for the residential training. One and a third times the number of top players must not exceed the number of second division players. Given that the club can only train up to 35 players who must be selected from the two divisions of players.

Write down the set of inequalities representing the above information. Using a scale of 2cm to represent 10 units of each axis, draw on the same axes graphs for these inequalities. Shade out the unwanted regions and find the maximum number of players from each division the club can train.

UNEB 2004 / Paper 1

A private car park is designed in such a way that it can accommodate x pick-ups and y mini-buses at any given time. Each pick-up is allowed 15m2 of space and each mini-bus 25m2 of space. There is only 400m2 of space available for parking. Not more than 35 vehicles are allowed in the park at a time. Both types of vehicles are allowed in the par, but at most 10 mini-buses are allowed at a time.

(a) (i) Write down all the inequalities to represent the above information. (05 marks) (ii) On the same axes plot graphs to represent the inequalities in (i) above, shading out the unwanted regions. (04 marks)

(b) If the parking charges for a pick-up is Sh 500 and that of a minibus is Sh 800 per day, find how many vehicles of each type should be parked in order to obtain maximum income. Hence find the maximum parking income per day. (03 marks)