Linear Programming

ELATE PHASE II

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.