OPERATIONS RESEARCH

WEEK 9

SUBJECT: FURTHER MATHEMATICS

CLASS: SSS1

TOPIC: OPERATIONS RESEARCH

CONTENT:

• Definition, History and nature of operations research
• Steps in operations research
• Models of operations research:

i. Linear programming models

ii. Transportation models (least cost and North Westcorner)

iii. Assignment models

• Practical application of the models.

Definition, History and nature of operations research

Operations research is called decision science or management science. It is the application of scientific especially mathematical methods to the study and analysis of complex decision making problems. It also means a mathematical science which is concerned with determining the maximum (of profit, performance or yield) or minimum (of loss, risk or cost) of some real – world objective.

In a nutshell, operations research is an area of study which applies mathematics and statistics to problems of management, industry, business, commerce, organization and production.

There are many techniques that operations research employs from other mathematical sciences such as mathematical modelling, statistical analysis and mathematical optimization to mathematical treatment of a process, problem or operation to determine its purpose with a view to gaining maximum efficiency. The common characteristic of operations research is maximization of profit, performance or yield on one hand or minimization of loss, risk or cost on the other hand. The use of operations research was first known in 1945. Operations research originated in the effort of military planners during the second world war as a formal discipline. Charles Babbage used the principles or techniques of operations research intuitively (able to understand situations without being told) in his research into the cost of transportation and sorting of mail which led to England’s universal “penny cost” in 1840.

A Scientist, Percy Bridgman also used operations research techniques to solve problems in physics and made attempt to extend it to social sciences. Scientists in the United Kingdom and United States of America began to look for ways of making better decisions in such areas as logistics and training schedules during the Second World War.

Around the same period about 1000 men and women were engaged in operations research activities in the United Kingdom and about 200 operations research Scientist worked for the British Army in logics, planning and training schedules. Operations research was no longer limited to military operational activities as a result of growing awareness and its attendant expanded techniques but was extended to encompass logistics, training infrastructures and equipment procurement.

There are many problems addressed by operations research which include: 1. Project training 2. Critical path analysis 3. Network optimization 4. Facility allocation 5. Assignment problem 6. Optimal search 7. Routing 8. Supply chain management 9. Transportation problem 10. Scheduling 11. Queuing models.

It is also widely used in government where evidenced – based policy is to be used.

CLASS ACTIVITY:

1. Define operations research.
2. Mention techniques operations research employs from other mathematical sciences.
3. Write out the common attribute of operations research
4. When was operations research first used?
5. Where did operations research originated.
6. List out the Scientist that used operations research techniques or principles to solve problems.
7. Mention problems addressed by operations research.

STEPS IN OPERATIONS RESEARCH.

There are many steps involved in the application of operations research in solving problems real world. These steps are:

1. Identification of the management decision problem of the real world.
2. Formulation of a model for the real world problem. This step may involve the following procedures:
3. Identification of the parameters and variables which are involved in the problem;
4. Selection of the most influential variables that will make the model as simple as possible;
5. Classification of the variables into controllable and non – controllable;
6. Making verbal or written statements about the relationship between the variables based upon known principles9 we may need to make some assumptions about the behaviour of non – controllable variables);
7. Performance of symbolic manipulation:- manipulation through solving certain equations or in-equations, repeat of a set of steps or a process or using statistical methods to optimize – certain measures;
8. Interpretation of the model conclusion in terms of the characteristics of the real world problems;
9. Test and evaluation of result;
10. Implementation of the result;
11. Revision of the test as and when necessary.

The steps of operations research can be illustrate in the flow chart:

Problem Identification

Model formation of real world problem

Performance of symbolic manipulations

Test and valuation of results

Implementation of the results

Interpretation of model conclusion

Revision of the test as and when necessary

CLASS ACTIVITY:

1. Define operations research.
2. Write out the common attribute of operation research.
3. Where did operations research originated.
4. List out the Scientists that used operations research techniques or principles to solve problems.
5. Mention problems addressed by operations research.
6. Draw the flow chart that illustrate steps of operations research.
7. Mention all the steps of operations research.
8. Draw the flow chart that illustrate steps of operations research.

MODELS OF OPERATIONS RESEARCH

Definition and brief explanation of models of operations research A model is an abstraction of reality. The map is an abstraction of reality. The map of Nigeria is an example of a model of the real shape of the entity called Nigeria. The maps of all the continents of the world in the globe is another example of a model of a planet called Earth. A model can also be formulated mathematically through an equation. An operations research model is an idealized representation of a real life solutions to real world problems.

SIMULTANEOUS INEQUALITIES AND PRACTICAL APPLICATION

The solution set of a system of linear inequalities in two variables can be found by graphing the inequalities and sharing the region of their intersection (if any) of the graphs of the solution sets of each inequality. We now illustrate with the following

Example 1: Find the solution set of:

X + y < 2

3x – y = ≥ 6

Solution:

We draw the graph of each inequalities and shade as shown above the region that satisfy each inequality.

A

2

-6

2

The solution set of the two simultaneous inequalities is the intersection of the two shaded portions which is represented by the double shaded area A.

1. Show the region which satisfies simultaneously the inequalities

2x + 3y ≤ 8

X – 2y ≥ -3

X ≥ 0

Y ≤ 0

Solution

The graph satisfying the inequality simultaneous is the shaded region enclosed by the polygon ABCD as shown in the figure below.

2

4

C(4,0)

B(4,0)

D(0,0)

-3

It can be verified that the vertices A, B, C and D are respectively (0, ), (1, 2), (4,0) and (0,0) as follow:

A(0, ) is obtained by solving x – 2y = -3 and x = 0 simultaneously

B(1, ) is obtained by solving x – 2y = -3 and 2x + 8y = 8 simultaneously

C(4, ) is obtained by solving simultaneously 2x + 8y = 8 and y = 0 and D(0,0) is the origin.

Note that any point in the shaded region satisfies all the inequalities

LINEAR PROGRAMMING MODELS AND PRACTICAL APPLICATION Linear programming Models: It is one of the mathematical model constructed to solve problems involving decision – making. If we wish to obtain the optimum value of a linear function subject to constraints expressed as linear equations or in equations. Linear programming provides the method of achieving that. For simple problems involving two variables, the graphical method may be consider.

Examples 1:

Maximize P = 2x + 3y subject to the constraints of the inequalities.

3x + 2y = 5

2x + 3y = 4

x ≥ 0, y ≥ 0

Solution

3

3

Q

Consider the Q region called feasible region bounded by the polygon whose vertices are O, A, B, C. The point o has coordinates (0,0)

The vertex A has coordinate (0, ) and is obtained by solving simultaneously the equation: 3x + 2y = 5 and x = 0

B( ) is obtained by solving the equations 3x + 2y = 5 and 2x + 3y = 4 simultaneously.

Coordinates of the vertex C (0, ) is obtained by solving the equation 3x + 2y = 5 and y = 0 simultaneously.

Hence we have O(0,0) , A(0, ), B() and C(0, ) as the vertices of the polygon, we call the matrix corner points

At O(0,0); P = 2(0) + 3(0) = 0

At A(0,); P = 2(0) + 3() = 7.5

At B(); P = 2() + 3() = 4

At C(); P = 2(+ 3() = 3.33

The maximum value occurs at the corner point A(0,)

Hence maximum value of p = 7.5

Example 2:

A carpentry workshop produces two types of furniture A and B which are first processed by a cutting machine and then sent to another machine for finishing.

Types A and B require 10man hours and 6 man hours respectively by the cutting machine while types A and B also require 5man hours and 4 man hours of finishing.

Cutting requires up to 1000 man hours per week while finishing requires up to 600 man hours per week.

Given that x and y are the units of type A and B furniture produced respectively.

1. Write down four inequalities in terms of x and y satisfying all the conditions in this problem.
2. Illustrate these inequalities graphically.

Solution

C(100,0)

100

B(16,126)

200

A(0,200)

126

16

yy

Let the cutting machine = x

Also the finishing machine = y

The constraint of cutting is

10x + 5y = 1000

The constraint of finishing is

6x + 4y = 600

The production is given by

P = x + y

Hence there is need to maximize

P = x + y

Subject to the constraints

10x + 5y = 1000

6x + 4y = 600

X > 0 , y > 0

Using the above figure, the corner points have coordinate

0(0,0); A (0,200); B(16,126) and C(100,0).

At 0(0,0); P = 0 + 0

At A(0,200); P = 0+ 200 =200

At B(16,126); P = 16+ 126 =142

At C(100,0); P = 100 + 0 =100

Class Activity

1. Explain linear programming model.
2. Illustration graphically (by shading) the region P of all points (x,y) which satisfy simultaneously the following inequalities

Use your graph to find the region

1. The minimum values of x and y
2. The maximum values of x and y
3. The maximum and minimum value of

TRANSPORTATION MODELS AND PRACTICAL APPLICATION.

Transportation models

Transportation models are another class of programming problems in operations research. It is a problem in which goods are transported from specified set of destinations based on the supply and demand of the source and destination respectively, such that the total cost of transportation is minimized.

Two types of transportation problems are:

1. Balanced transportation problem: In this problem, the sum of all the supplies is equal to the sum of demands of all the destinations.
2. Unbalanced transportation problem: This type of problem is when the sum of all the supplies from all the sources is not equal to the sum of the demands of all the destinations.

Three most popular techniques or methods for solving transportation problems are:

1. Northwest corner cell method
2. Least cost cell method
3. Vogel’s approximation method

In secondary school level we shall consider northwest corner cell method and least cost cell method for the solution of our transportation problem each method can be illustrate as worked.

Example 1

The transportation costs in thousands of naira, the available stock of supplies from three sources and the demands at three destinations are shown below:

I

II

III

A

B

C

Demand

Sources

Supply

5

8

7

Destinations

3	8	5
4	4	2
6	5	8
6	9	5

 

 

Using the northwest corner cell method:

1. Find how much units of stocks should be transported from each source to each destination.
2. Find the minimum total transportation cost.

SOLUTION:

(a)

Destinations

I	II	III	Supply
3	8	5	5
4 Sources B	4	2	8
6 C	5	8	7
6 Demand	9	5

We observe that total supplies are equal to the total demands. Let us proceed to the next stage now;

The explanation from the above table is as follow;

We start from Northwest corner or upper left corner.

We increase the cost from A to III to I. Then source A to I, II and III will be equal to 5 and so forth.

(b)Minimum Transportation cost

 

Least cost cell method.

Example 2:

The costs of transportation in thousands of naira, the available stocks of goods at three difference sources and the requirements at three different destinations are shown below:

Requirement

11

13

A

B

C

P3

Q

R³

Sources

Available stock

10

12

8

6

¹⁰

²

⁶

⁵

11	14	7
17	8	14
9	23	3

 

Using the least cost method

Example 1:

1. Find how much units of stock of good that should be transported from each source to each destination;
2. Find the minimum total transportation cost.

Solution (a) ::

Requirement

PQR

Sources

A B C

Available stock

Destination

3

3

1

2

10

6

5

11	14	7	10/0
17	8	14	12/0
9	23	3	8/0
6	11	13	30

 

In this method, you start your increase or decrease of stock from the least value e.g the least value in this table is 3.

 

ASSIGNMENT MODEL AND PRACTICAL APPLICATION

Assignment models

An assignment problem is a special type of transportation problem whereby each source has the capacity to satisfy the demand of any of its destinations. The assignment problem can be classified into two namely:

1. Balanced assignment problem.
2. Unbalanced assignment problem.

In balanced assignment problem, the number of rows (Jobs) is equal to number of columns (operators) while in an unbalanced assignment problem the number of rows is not equal to the number of columns.

We have many ways of solving the assignment problems but one way that saves time and labour is called Hungarian method and this method provides easy solution of an assignment problem through row and column reduction of a matrix but the optimization of the solution on the basis of iteration. This Hungarian method is also known as Reduction matrix method or Flood’s technique.

Example 1:

Four operations A,B,C and D are assigned to four machines I,II,III and IV as shown below:

I II III IV
A B C D	9	4	12	14
	2	8	17	2
	9	6	1	1
	4	10	8	6

Assign operators to machines so that total cost is minimized.

Solution:

Step 1:- Subtract the minimum element of each row from all the elements, e.g from row A, 4 is the least element, subtract it from all the elements in row A.

 

A B C D	I II III IV
	5	0	8	10 0
	0	6	15	0
	8	5
		6	4	2

 

Step II- put on one zero in the table of each row or column

Step III- cross (x) all the other zeros in the same column indicating that the assignment cannot be made there.

Step IV- From the table, one can observe that there is one assignment in each row and in each column.

An optimal assignment in this dispensation can be obtain as follow:

Row A, Column II

Row B, Column I

Row C, Column III

Row D, Column I

Hence optimal assignment plan is:

Location A, Contractor II

Location B, Contractor I

Location C, Contractor IV

Location D, Contractor I

 

I II III IV
A B C D	9	4(1)	12	14
	2(1)	8	17	2
	9	6	1(1)	1
	4(1)	10	8	6

Total minimum cost

 

 

 

Class Activity

1. Explain assignment problem.
2. List two classes of assignment problem we have discussed
3. Outline ways of solving assignment problem.
4. Assign jobs to operators in the assignment problem shown in the table below

Operators

Jobs

A B C D	I II III IV
	12	4	7	9
	8	14	17	9
	11	13	9	9
	9	13	8	11

PRACTICE QUESTIONS:

1. What is a model of Operations Research?
2. Using a scale of 2cm to 1 unit on each axis, illustrate graphically the region R of the plane defined by the following inequalities

Use your diagram to determine on the region R, the maximum and the minimum value

1. Illustrate graphically, the region R of all points which satisfy the inequalities

Use your graph to find in the region R the maximum value; minimum value of

1. The costs in thousand of naira, the source availabilities and the destination requirement of a transportation problem are given in the table below

Destination

Sources

Requirement 25 20 18 12

Availability

P Q R S	1 2 3 4
	8	3	6	6
	5	5	7	6
	6	4	4	3
	5	1	5	3

25

20

3

3

Using the northwest corner cell method?

(a)Write down the transportation plan;

(b)Find the least total cost of transportation plan.

1. Four different operators for each machine in hundreds of naira are indicated in the table below

 

A Operators B C D	6	8	12	7
	9	6	10	7
	5	8	11	8
	11	5	9	4

a. Assign operators to machines so that total cost is minimized

Machines

b. Calculate the minimum total cost.

ASSIGNMENT

1. In what year was operation research first used?
2. Operations research originated from where?
3. Name the Scientists that used operations research.
4. Draw the flow – chart that illustrate steps of operations research.
5. Study about models operations research, linear programming transportation (least cost and not west corner) and assignment practical application of the models.

REFERENCE TEXTS:

1. Further mathematics project 1 by M. R. Tuttuh- Adegun et al 5^th revised edition.
2. New further mathematics scholastic series by T. R. Moses.
3. NPS Further Mathematics Project by Tuttuti-Adegun M. R
4. Further mathematics by Egbe E and Co
5. Additional Mathematics for W. A by J. F Talbert and Co
6. New Further Mathematics Scholastic Series by T. R Moses; Spectrum Books Limited
7. Hidden Facts in Further Mathematics by