Topic 3 Linear Programming

Key Words

constraints

feasible region

linear inequalities

objective function

optimization

variables

optimum solution

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

1. form linear inequalities based on real-life situations.
2. represent the inequalities on the graph and identify the required region.
3. find and interpret the optimum solution of a set of linear inequalities in two unknowns.

Introduction

On many occasions, farmers want to know how they can fully utilise their gardens in order to maximise profits; companies are always seeking to minimize costs, and governments are always striving to strike a balance between incomes and expenditures of different operations. All those entities work with limited resources.

Due to COVID-19 and its adverse effects on society, some schools have resorted to increasing school fees in order to recover financially. This has resulted into increased school dropouts and some parents/guardians transferring their children to other affordable schools.

All the examples mentioned above, involve the process of maximising the usage of available resources or minimising the costs involved. This branch of Mathematics is known as linear programming. In this topic, you will understand and use linear programming to solve problems.

3.1 Forming Linear Inequalities based on Real-life Situations

In Senior Two, you learnt how to formulate linear inequalities for different word problems. Linear inequalities are the core of linear programming and, therefore, you should be well-versed with them.

Activity 3.1(a) (Work in groups)

(a) Discuss the meanings of the following common phrases in Mathematics:

i) at least ii) at most iii) between iv) exceeding

(b) Identify and match other terms with the same meaning as the phrases mentioned above.

Activity 3.1(b)

The Ministry of Education and Sports was set to recruit at most 3,096 secondary school teachers by 2023, for selected schools. According to the Education Service Commission, the number of science teachers should be more than that of the teachers of Humanities. The selected schools would receive at least one teacher of History. Represent the information in terms of inequalities to the Ministry of Public Service that would enable it to plan and prepare ahead of the interviews.

Example 3.1

A shopkeeper buys 2 brands of rice: short grain and long grain, at UGX 200,000 and UGX 400,000 per 50 kg bag, respectively. She has UGX 1,600,000 available and decides to buy at least 5 bags altogether. She also decides that at least one third of the bags should be of the short grain rice. She buys x bags of short grain and y bags of long grain. Write down five inequalities which correspond to the above conditions.

Exercise 3.1

1. Basemera is given UGX 5,000 to buy x packets of biscuits and y apples. A packet of biscuits costs UGX 1,500 and an apple costs UGX 1,000. She is told to buy at least 6 items altogether, but she must not buy more apples than biscuits. Write down three (3) inequalities which satisfy the conditions above.
2. Okuti is told to buy melons and oranges. Melons are sold at UGX 3,000 each and oranges at UGX 500 each, and he has UGX 10,000 to spend. He must not buy more than 2 melons and he must buy at least 4 oranges. He is also told to buy at least 6 fruits altogether. Write four inequalities which must be satisfied.
3. A chef is going to make fruit cakes and sponge cakes. He has plenty of ingredients, except flour and sugar. He has only 2,000 grams of flour and 1,200 grams of sugar. A fruit cake uses 500 grams of flour and 100 grams of sugar. A sponge cake uses 200 grams of flour and 200 grams of sugar. He wishes to make more than 4 cakes altogether. Write down three inequalities which must be satisfied.
4. Kodet has a part-time job of washing c cars and v vans. She takes 1 hour to wash a car and 2 hours to wash a van. She has 14 hours available per week. She has an agreement with one firm to wash two of their vans every week. Apart from that, she has no fixed work. If she is to use her backyard, she must wash twice as many cars as vans. Write down three (3) inequalities which must be satisfied.
5. A shop owner wishes to buy up to 20 televisions for stock. He can buy either type A for UGX 630,000 each or type B for UGX 1,260,000 each. He has a total of UGX 18,900,000 to spend. He must have at least 6 of each type in stock. Write down four(4) inequalities which must be satisfied.
6. Mrs Kijambo has UGX 120,000 budgeted to fuel her 2 cars, one diesel- powered and the other petrol-powered. A litre of diesel costs UGX 3,500 while that of petrol costs UGX 3,900. The diesel-powered car uses more litres of fuel than the petrol-powered one. Write a system of linear inequalities to represent the information.

3.2 Representing the Inequalities on the Graph and Identifying the Required Region

You will use your prior knowledge on how to represent linear inequalities on a graph paper, to determine the feasible regions for linear programming problems.

Activity 3.2(a) (Work in groups)

(a) Identify the region satisfied by the following inequalities:

i) y ≤ x + 2

ii) 2y + x > 8

iii) 14y+ 2 + 1 <7

(b) Explain how you identified the regions in (a).

Activity 3.2(b) (Work in groups)

In a school, the Entrepreneurship Club members have decided to make fruit juice from lemons and oranges to sell at the school canteen. To produce enough juice per day, they have found out that they need to have a total of at least 25 lemons and oranges all together. For a better taste, the number of oranges must be twice greater than that of the lemons. They have to buy each orange at UGX 500 and a lemon at UGX 200.

How can the club members produce enough juice per day at the least cost, if they aim to maximise profits?

Exercise 3.2

1. Use a graph to identify the feasible region for the following set of linear inequalities. x + y ≤ 12 n 3x + y >12 ny > 0x>0.
2. Use a graph to identify the feasible region for the following set of inequalities. x>0ny>0n5x-y≥20 4y + 3x ≥ 24 16 + 21x ≤ 336112 + 28y-27×20
3. Nakiru, a local vegetable trader in Kotido District, bought p kilogrammes of tomatoes and y kilogrammes of eggplants. Tomatoes cost UGX 2,000 per kilogramme and eggplants cost UGX 1,000 per kilogramme. She had UGX 290,000 to spend and she bought more tomatoes than eggplants.
   • (a) Form inequalities to represent this information.
   • (b) Graph these inequalities on the same pair of axes, and identify the feasible region.
4. During breaktime, ten Senior Four learners went to buy snacks at the canteen. They each bought either a doughnut or a cake. A doughnut costs UGX 500, while a cake costs UGX 1,000. The learners had UGX 10,000 altogether. They bought more doughnuts than cakes.

(a) Form inequalities to represent this information.

(b) Graph these inequalities, showing the feasible region.

(c) List the possible solutions.

3.3 Finding and Interpreting the Optimum Solution of a Set of Linear Inequalities in Two Unknowns

Constraints

Some companies often have a goal of expanding their businesses by purchasing more equipment, but get limited by their available capital. Such factors which limit a party from achieving its desires are referred to as constraints (restrictions).

Constraints are always involved in linear programming problems, since the process involves solving practical problems (such as the allocation of resources) by means of linear functions, where the variables involved are subject to constraints.

(b) Identify the inequalities represented on the graph.

(c) State the vertices of the unshaded region.

(d) If in the graph above, x and y represent the numbers of kilogrammes of Feed A and Feed B, respectively, while the selling prices of Feeds A and B are UGX 3,000 and UGX 2,000 per kilogramme, respectively:

i) determine the maximum revenue that a seller can make from selling the feeds.

ii) determine the minimum revenue that a seller can make from selling the feeds.

(e) Present your findings to the rest of the class.

Activity 3.3(b) (Work in groups)

Due to the outbreak of CoViD-19 in Uganda in March, 2020, the Government c corona virus. This left many urban dwellers ‘vulnerable, since they were faced Uganda imposed a lockdown in a bid to curb down the spread of the SARS-CoV-2 with shortages of food and other necessities.

To that end, the Office of the Prime Minister started a door-to-door exercise of distributing food in those areas, and each person who received the relief got at least 3 and 6 kilogrammes of beans and maize flour, respectively. The quantity of beans that a person got was never more than that of maize flour, and no person received more than 18 kilogrammes of maize flour. The costs of one kilogramme of beans and maize flour were UGX 2,600 and UGX 1,200, respectively.

(a) Write down the inequalities that represent the information above.

(b) (i) Plot the inequalities you have written in (a) above on a graph. (ii) Given that a total of UGX 40,000 was spent on one person in particular village, use your graph to determine how much of maize flour and beans did that person get.

Example 3.3

The ground manager of a car park allows 10 m2 of parking space for each car and 30 m2 for each lorry. The total space available is 300 m2. He decides that the maximum number of vehicles at any time must not exceed 20 and also insists that there must be at least as many cars as lorries. If the number of cars is x and the number of lorries is y:

(a) write down five inequalities which must be satisfied and represent them on the same pair of axes.

(b) if the parking charge is UGX 4,000 for a car and UGX 20,000 for a lorry, find out how many vehicles of each type he should accept in order to maximise his income.

(c) if the charges were changed to UGX 8,000 for a car and UGX 15,000 for a lorry, find out how many vehicles of each kind you would advise him to accept.

Solution:

(a) Parking space: 10x + 30y ≤ 300

x + 3y ≤ 30 (on simplifying i.e divide through by 10)

Number of vehicles: x + y ≤ 20 x ≥y

Additional inequalities: Since it is not a must for either a car or lorry to park,

x ≥ 0 and y ≥ 0.

Exercise 3.3

1) A gardener has 100 square metres of land on which he wants to plant cabbages and beans. However, he knows the following:

Cabbages Beans

Work and material costs (UGX per square metre) 9,000 6,000

Earnings (UGX per square metre) 2,000 1,000

The gardener is to invest UGX 78,000 and he does not want to use more than 60 square metres of the garden for cabbages. How much of the cabbages and beans should he plant in order to get as much earnings as possible?

2) A businessman wishes to sell two models of home computers, model A and model B, at costs of UGX 450,000 and UGX 720,000, respectively. Model A yields a profit of UGX 81,000 and model B yields a profit of UGX 90,000. The businessman estimates that the total monthly demand will not exceed 25 computers. Find the number of units of each model that should be stocked in order to maximise profit, assuming that the businessman does not want to invest more than UGX 14.4 million in the computer inventory.

3) The directors of a Day and Boarding Mixed secondary school estimated that the total cost of running the school per term is UGX 115,000,000. The school is to cater for a maximum of 220 boarding learners and that the total number of learners must not exceed 400. Each boarding learner will pay UGX 500,000 and each day-scholar will pay UGX 230,000 per term. Find the minimum number of boarding learners required for the school to be able to run profitably for a term.

4) A restaurant offers two kinds of fried tilapia: full and half. It costs UGX 3,000 and UGX 5,000 to have half and full tilapias ready for consumption, respectively. The quantity of half plus two times that of full tilapias is not to exceed 20. At the same time, the quantity of full tilapia is not to exceed twice that of half tilapia. The restaurant makes a profit of UGX 1,000 and UGX 1,500 on half and full tilapias each, respectively. Find the quantity of each kind of fried tilapia that should be made so as to obtain maximum profits, if the restaurant is ready to invest UGX 60,000.

5) A company wishes to maximise its profit from two products. The first product yields a profit of UGX 150 per unit and the second one yields a profit of UGX 200 per unit. From the research done and the available resources, the following constraints have been indicated.

(a) The combined production level should not exceed 1,200 units per month.

(b) The demand for the second product is at most half of that of the first one.

(c) The production level of the first product can exceed three times that of the second one by at most 600 units. Find how many units of each product the company must produce in order to maximise its profits.

6)Two buses, a 50-seater and 70-seater, are to be used by a construction company to transport workers to a site. The number of workers required at the site must not exceed 350. Each trip made by a 50-seater or 70-seater bus costs UGX 30,000. The money available for transportation is UGX 180,000. The number of trips made by the 50-seater bus must not exceed that made by the 70-seater.

(a) If all the available money for transport is to be used, list all possible numbers of trips that each bus will make (Assume that for each trip made, the bus is full to capacity).

(b) Find the greatest number of workers that can be transported.

Revison Questions

a) Minimise 6x+5y, subject to x 2 0, 2y 2 x + 5, and x + y < 11.

b) Find the maximum and minimum values of the objective function 3x + 9y, subject to the following constraints: x ≥ 0, y ≥ 0, x + 2y ≤ 4 and x – y ≤1

Topic Summary

In this topic, you have learnt: 34

1. how to form linear inequalities from real-life situations, represent them on a graph, and identify the required region.

2. that the common phrases used in linear programming include:

(a) at least, for example, “The profit p he makes per day is at least UGX 100,000”. This can be written as p≥ 100,000.

(b) not exceeding, for example, “The number, s of students (s) attending lessons today does not exceed 60”. This can be written as s≤ 60.

(c) at most, for example, “I failed, at most, five questions”. This can be written as q ≤ 5, where q represents the number of questions I failed.

(d) exceeding, for example, million people”. This can be written as p > 30 million “The population, p of Uganda exceeds 30

(e) not more than, for example, “I have budgeted to spend not more than UGX 5,000 today”. This can be written as e≤ 5,000, where e denotes the amount of money that I have budgeted to spend today.

(f) between, for example, “They will be given between UGX 500,000 and UGX 700,000 to begin their business”. This can be written as 500,000 < x>”. (h) up to, Mathematically represented as “s”.