HIGHER NATIONAL DIPLOMA
IN
INFORMATION TECHNOLOGY
STUDY PACK
OPERATIONS RESEARCH
(Version: January 2004)
COPYRIGHTS RESERVED
HIGHER NATIONAL DIPLOMA IN INFORMATION TECHNOLOGY
SUBJECT: OPERATIONS RESEARCH
CODE: 710 / 04 /S02
AIM OF THE SUBJECT:
1. To provide various mathematical tools for analysis of systems in the Business environment.
2. To provide techniques which would be needed in analysis of Business Systems to managerial decision-making.
3. To provide tools to solve complex business problems.
4. To represent the concepts of “efficiency” and “scarcity in well defined mathematical model of a given situation.
5. To provide Science Techniques of the derivation of computational methods for solving such models.
DESIGN LENGTH:
THEORY 190: HOURS
LABORATORY 10: HOURS
TOTAL 200: HOURS
HIGHER NATIONAL DIPLOMA IN INFORMATION TECHNOLOGY
SUBJECT: OPERATIONS RESEARCH
CODE: 710 / 04 /S02
UNIT 1 APPROXIMATIONS
HOURS: 20
OBJECTIVE
At the end of the unit the student should be able to:
Apply given Technologies in estimating solutions in Business environment.
1.1 Newton-Raphson iteration method for solving polynomial equations.
1.2 Trapezium Rule for approximating a definite integral.
1.3 Simpson Rule for approximating a definite integral
1.4 Maclaurin Series expansion.
HIGHER NATIONAL DIPLOMA IN INFORMATION TECHNOLOGY
SUBJECT: OPERATIONS RESEARCH
CODE: 710 / 04 /S02
UNIT 2 LINEAR PROGRAMMING
HOURS: 20
OBJECTIVE
To formulate and solve linear programming models using the Graphical and other techniques.
2.1 Model formulation.
2.2 Solution of L.P model by graphical and simplex method.
2.3 Duality and the Dual Simplex method.
2.4 Sensitivity Analysis using the Simplex method.
2.5 Assignment problem.
2.6 Transportation problem.
UNIT 3: NON-LINEAR FUNCTIONS:
HOURS: 20.
OBJECTIVE
To develop an optimization theory using differential calculus to determine maximum and minimum points for Non Linear Functions.
3.1 Overview of differentiation and integration.
3.2 Continuous functions and partial derivatives.
3.3 Necessary and sufficient conditions for extreme points.
3.3.1 The gradient vector
3.3.2 The Hessian matrix
HIGHER NATIONAL DIPLOMA IN INFORMATION TECHNOLOGY
SUBJECT: OPERATIONS RESEARCH
CODE: 710 / 04 /S02
UNIT 4 PROJECT MANAGEMENT WITH PERT/CPM
HOURS: 20
OBJECTIVE
To select a method which is appropriate in a given situation to find the shortest route between two given nodes in a network and determine the route and its length.
4.1 Introduction.
4.2 The project network diagram.
4.3 Critical Path Analysis.
4.4 Determination of the critical path.
4.5 Project activity crushing.
4.6 Probabilistic time duration of activities.
UNIT 5: RANDOM VARIABLES AND THEIR PROBABILITY:
HOURS: 20.
OBJECTIVE
To appreciate the properties of a probability function and be able to apply it in Business environment.
5.1 Introduction
5.2 Probability density functions (pdf)
5.3 Discrete random variables.
5.4 Continuous random variables.
5.5 Cumulative density functions (CDF)
5.6 Relations among probability distributions
5.7 Joint probability distributions with two variables
HIGHER NATIONAL DIPLOMA IN INFORMATION TECHNOLOGY
SUBJECT: OPERATIONS RESEARCH
CODE: 710 / 04 /S02
UNIT 6 DECISION THEORY
HOURS: 20
OBJECTIVE
Apply the concept of optimistic approach, conservative approach, and minimax regret approach to decision-making problems.
6.1 Decisions under risk
6.1.1 Expected value criterion
6.1.2 Expected profit with perfect information
6.1.3 Minimizing expected loss.
6.1.4 Expected value of perfect information
6.1.5 Decision trees in multistage decision-making
6.2 Decisions under uncertainty
6.2.1 Laplace criterion
6.2.2 Minimax/Maximin criterion
6.2.3 Savage Minimax Regret criterion
6.2.4 Hurwicz criterion
UNIT 7: THEORY OF GAMES:
HOURS: 20
OBJECTIVES:
Use analytical criteria for decisions under uncertainty with the assumptions that “nature” is the opponent.
7.1 Pure strategy games
7.1.1 Two-Person Zero Sum games
7.1.2 Saddle point solutions
7.2 Mixed strategy games
7.2.1 Solution of games by Linear Programming.
7.2.2 Graphical solution of (2*n) and (m*2) games.
7.2.3 Solution of (m*n) games by the Simplex methods.
UNIT 8: INVENTORY MODELLING:
HOURS: 20
OBJECTIVES:
To determine the reorder point and cost of inventory for a given model.
8.1 Generalized inventory model
8.2 Deterministic Models.
8.3 The Economic Order Quantity (EOQ) model
8.4 Inventory with backordering
8.5 Economic Production Quantity model
8.6 Probabilistic models
8.7 Continuous Review model.
UNIT 8: REGRESSION ANALYSIS AND CORRELATION:
HOURS: 20
OBJECTIVES:
To identify the relationships between variables and forecast future trends.
9.1 Simple Linear Regression Analysis.
9.1.1 Scatter plots and Line of best fit.
9.1.2 Least Squares equation regression model.
9.1.3 Forecasting using Regression techniques.
9.1.4 Making inferences about parameters a and b.
9.2 Correlation Coefficient.
9.2.1 Coefficient of determination.
9.2.2 Interpret the value of the correlation coefficient.
UNIT 10 INTRODUCTION TO QUEUEING THEORY
HOURS: 20
OBJECTIVE:
To identity a Queuing problem and calculate parameters related to the queue.
10.1 Queuing processes of Single Server models.
10.2 Definitions and Notations.
10.3 Relationships between
10.3.1 Expected Waiting Time per Customer in the system.
10.3.2 Expected Waiting Time per Customer in the queue.
10.3.3 Expected Number of Customer in the system.
10.3.4 Expected Number of Customer in the Queue.
UNIT 2 LINEAR PROGRAMMING
HOURS: 20
LINEAR PROGRAMMING
Is a technique used to determine how best to allocate personnel, equipment, materials,
finance, land, transport e.t.c. , So that profit are maximized or cost are minimized or other optimization criterion is achieved.
Linear programming is so called because all equations involved are linear. The variables in the problem are Constraints. It is these constraints, which gives rise to linear equations or Inequalities.
The expression to the optimized is called the Objective function usually represented by an equation.
Question 1:
A furniture factory makes two products: Chairs and tables. The products pass through 3 manufacturing stages; Woodworking, Assembly and Finishing.
The Woodworking shop can make 12 chairs an hour or 6 tables an hour.
The Assembly shops can assembly 8 chairs an hour or 10 tables an hour.
The Finishing shop can finish 9 chairs or 7 tables an hour.
The workshop operates for 8 hours per day. If the contribution to profit from each Chair is $4 and from each table is $5, determine by Graphical method the number of tables and chairs that should be produced per day to maximize profits.
Solution:
Let number of chairs be X.
Let number of tables be Y.
Objective Function is:
P = 4X + 5Y.
Constraints:
WW: X/12 + Y/6 <= 8
X + 2Y <= 96 when X=0 Y= 48 when Y=0 X= 96
AW: X/8 + Y/10 <= 8
5X + 4Y <= 320 when X=0 Y=80 when Y=0 X=64
FNW: X/9 + Y/7 <= 8
7X + 9Y <= 504 when X=0 Y=56 when Y=0 X=72
X>=0 Y>=0
100
90
80
70
60
50
40
30
20 P------à this gives the maximum point
10
0
10 20 30 40 50 60 70 80 90 100
Question 2:
Mr. Chabata is a manager of an office in Guruwe; he decides to buy some new desk and chairs for his staff.
He decides that he need at least 5 desk and at least 10 chairs and does not wish to have more than 25 items of furniture altogether. Each desk will cost him $120 and each chair will cost him $80. He has a maximum of $2400 to spend altogether.
Using the graphical method, obtain the maximum number of chairs and desk Mr. Chabata can buy.
Solution:
Let X represents number of Desk.
Let Y represents number of Chairs.
Objective Function is:
P = 120X + 80Y.
Constraints:
X >= 5
Y>= 10
X + Y <= 25
30
25
20
PàPoint P (10,15) gives the maximum point
15
10
5
0
5 10 15 20 25 30 35 40
The Optimum Solution = 120 * 10 + 80 * 15
= 1200 + 1200
= 2400
Question 3:
A manufacturer produces two products Salt and Sugar. Salt has a contribution of $30 per unit and Sugar has $40 per unit. The manufacturer wishes to establish the weekly production, which maximize the contribution. The production data are shown below:
Production UnitMachine Hours / Labour Hours / Materials in Kg
Salt / 4 / 4 / 1
Sugar / 2 / 6 / 1
Total available per unit / 100 / 180 / 40
Because of the trade agreement sales of Salt are limited to a weekly maximum of 20 units and to honor an agreement with an old established customer, at least 10 units of Sugar must be sold per week.
Solution:
Let X represents Salt.
Let Y represents Sugar.
Objective Function is:
P = 30X + 40Y.
Constraints:
4X + 2Y <= 100 {machine hours}
4X + 6Y <= 180 {Labour hours}
X + Y <= 40 {material}
Y>= 10
X<= 20
X>=0; Y>=0;
SOLVING LINEAR PROGRAMMING USING SIMPLEX METHOD:
The graphical outlined above can only be applied to problems containing 2 variables. When 3 or more variables are involved we use the Simplex method. Simplex comprises of series of algebraic procedures performed to determine the optimum solution.
In Simplex method we first convert inequalities to equations by introducing a Slack variable.
A Slack variable represents a spare capacity in the limitation.
Ø STEPS TO FOLLOW IN SIMPLEX METHOD:
i. Obtain the pivot column as the column with the most positive indicator row.
ii. Obtain pivot row by dividing elements in the solution column by their corresponding pivot column entries to get the smallest ratio. Element at the intersection of the pivot column and pivot row is known as pivot elements.
iii. Calculate the new pivot row entries by dividing pivot row by pivot element. This new row is entered in new tableau and labeled with variables of new pivot column.
iv. Transfer other row into the new tableau by adding suitable multiplies of the pivot row (as it appears in the new tableau) to the rows so that the remaining entries in the pivot column becomes zeroes.
v. Determine whether or not this solution is optimum by checking the indicator row entries of the newly completed tableau to see whether or not they are any positive entries. If they are positive numbers in the indicator row, repeat the procedure as from step 1.
vi. If they are no positive numbers in the indicator row, this tableau represents an optimum solution asked for, the values of the variables together with the objective function could then be stated.
Question 1:
Maximize Z = 40X + 32Y
Subject to:
40X +20Y <= 600
4X + 10Y <= 100
2X + 3Y <= 38 Using the Simplex method
Solution:
To obtain the initial tableau, we rewrite the Objective Function as:
Z = 40X + 32Y
Introducing Slack variables S1, S2, S3 in the 3 inequalities above we get:
40X + 20Y + S1 = 600
4X + 10Y + S2 = 100
2X + 3Y + S3 = 38
X >= 0
Y >=0.
TABLEAU 1:
Pivot Element
X Y S1 S2 S3 Solution
S1 20 1 0 0 600
S2 4 10 0 1 0 100
S3 2 3 0 0 1 38
Z 40 32 0 0 0 0 Indicator Row
Pivot Column
TABLEAU 2:
X Y S1 S2 S3 Solution
X 0.5 0.025 0 0 15
S2 0 8 -0.1 1 0 40
S3 0 2 -0.05 0 1 8
Z 0 12 -1 0 0 -600
TABLEAU 3:
X Y S1 S2 S3 Solution
X 1 0 0.0375 0 -0.25 13
S2 0 0 0.1 1 -4 8
Y 0 0.025 0 0.5 4
Z 0 0 -0.7 0 -6 -648 Indicator Row
Pivot Column
Conclusion:
Since they are no positive number in the Z row the solution is Optimum. Hence for maximum Z, X = 13 and Y = 4 giving Z = 648.
NB:
a) If when selecting a pivot column we have ties in the indicator row, we then select the pivot column arbitrary.
b) If all the entries in the selected pivot column are negative then the objective function is unbound and the maximum problem has no solution.
c) A minimization problem can be worked as a maximization problem after multiply the objective function and the inequalities by –1.
d) Inequalities change their signs when multiplied by negative number.
Question 2:
Maximize Z = 5X1 + 4X2
Subject to:
2X1 +3X2 <= 17
X1 + X2 <= 7
3X1 + 2X2 <= 18 Using the Simplex method
Solution:
Max Z = 5X1 + 4X2
Subject to:
2X1 + 3X2 + S1 = 17
X1 + X2 + S2 = 7
3X1 + 2X2 + S3 = 18
X1 >= 0
X2>=0.
TABLEAU 1:
X1 X2 S1 S2 S3 Solution
S1 2 3 1 0 0 17
S2 1 1 0 1 0 7
S3 2 0 0 1 18
Z 5 4 0 0 0 0 Indicator Row
Pivot Column
TABLEAU 2:
X1 X2 S1 S2 S3 Solution
S1 0 5/3 1 0 -2/3 5
S2 0 1/3 0 1 -1/3 1
X1 2/3 0 0 1/3 6
Z 0 2/3 0 0 -5/3 -30
TABLEAU 3:
X1 X2 S1 S2 S3 Solution
X2 0 3/5 0 -2/5 3
S2 0 0 -1/5 1 -1/5 0
X1 1 0 -2/5 0 9/15 4
Z 0 0 -2/5 0 -7/5 -32
Pivot Column
Conclusion:
Since they are no positive number in the Z row the solution is Optimum. Hence for maximum Z, X1= 4 and X2 = 3 giving Z = 32.
Question 3:
A company can produce 3 products A, B, C. The products yield a contribution of $8, $5 and $10 respectively. The products use a machine, which has 400 hours capacity in the next period. Each unit of the products uses 2, 3 and 1 hour respectively of the machine’s capacity.
There are only 150 units available in the period of a special component, which is used singly in products A and C.
200 kgs only of a special Alloy is available in the period. Product A uses 2 kgs per unit and Product C uses 4kgs per units. There is an agreement with a trade association to produce no more than 50 units of product in the period.
The Company wishes to find out the production plan which maximized contribution.
Solution:
Maximize Z = 8X1 + 5X2+ 10X3
Subject to:
2X1 + 3X2 + X3 <= 400 {machine hour}
X1 + X3 <= 150 {component}
2X1 + 4X3 <= 200 {Alloy}
X2 <=50 {Sales}
X1 >= 0
X2 >= 0
X3 >= 0.
Introducing slack variables:
Maximize Z = 8X1 + 5X2+ 10X3
Subject to:
2X1 + 3X2 + X3 + S1= 400
X1 + X3 + S2 = 150
2X1 + 4X3 + S3 = 200
X2 + S4 =50
X1 >= 0
X2 >= 0
X3 >= 0.
TABLEAU 1: