21MA1502 – OPERATIONS RESEARCH

Panimalar Engineering College

UNIT I – LINEAR MODELS
Part-A
1. What is Operations Research? [Dec 2010]
A scientific method of providing executive departments with a quantitative basis for decisions
regarding operations under their control.
2. What are the situations where operations research will be applicable? [June 2012, June
2013]
Some major areas are: Product selection, Production planning, Plant location, Implementation of
projects, Resource allocation, Purchase and inventory management, Replacement decisions,
Competitive strategies, etc.
3. What are the characteristics of LPP?[Dec 2013]
The presence of a set of decision variables, an objective function made up of these decision
variables, a set of constraints, and a set of non-negativity restrictions.
4. Write the standard form of LPP. [June 2010]
Maximize/Minimize Z=c1x1+c2x2+- - - +cnxn
Subject to a11x1+a12x2+- - - +a1nxn = b1
a21x1+a22x2+- - - +a2nxn = b2
- - - - - - - -- - - - - - - - - - - - - - - - -
am1x1+am2x2+- - - +amnxn =bm
x 1, x2, - - -, xn ≥ 0
5. Define feasible solution. [April 2011]
A set of 𝑥1 , 𝑥2 , -----, 𝑥𝑛 values which satisfy all the constraints and also the non-negativity
restrictions.
6. Define basic feasible solution.
A basic solution which also satisfies the non-negativity restrictions.
7. Define infeasible solution.
When all the constraints of a LP problem cannot be simultaneously satisfied by any set of values
of the decision variables, we call it an infeasible solution.
8. What is artificial variable?
A variable added to the LHS of ≥ and = type constraints in order to get an initial basic feasible
solution to an LP problem.
9. What is meant by ‘unrestricted variable’ in LP?
A variable which can take either positive, negative or zero values without any restrictions.
10. How do you convert a ≤ type constraint into ≥ type?
By multiplying both sides of the constraint with minus sign.
11. Distinguish between the graphical and simplex methods of solving LP problems.
Graphical method can be used only for LP problems having two decision variables. Simplex
method can be used for problems having any number of variables (two or more).
12. How do you identify multiple optimal solutions in the Simplex method?
When the (𝐶𝑗 − 𝐸𝑗 ) value of a non-basic variable is zero and those of others are negative, this
indicates multiple optimal solutions. By introducing the non-basic variable with zero (𝐶𝑗 − 𝐸𝑗 )
value as the entering variable at the next stage, we get the alternate optimal solution.
13. How do you identify that an LPP has no feasible solution in Simplex method?
In the Simplex method when we employ artificial variables, one or more artificial variables
remains as a basic variable in the optimal table.
14. What do you understand by degeneracy in LPP?
A situation where one or more basic variables acquire zero value in the Simplex table.
15. Define the dual of LPP.
For every LP problem, there is a related LP involving the same data in a different format and
closely related optimal solutions. The original LP is called Primal and the related LP, its Dual.
 Panimalar Engineering College
16. State advantages and disadvantages of OR. [April 2011]
Advantages: Better control; Better systems; Better decisions. Disadvantages: Dependence on
computers; Non-quantifiable factors; Ignores complexities of human behavior.
17. Write down the main phases of OR. [April 2011]
1.Formulate the problem; 2. Construct a model to represent the system under study; 3. Derive a
solution from the model; 4. Test the model and the solution derived from it; 5.Establish control
over the solution; 6. Implement the solution.
18. What is meant by optimum solution? [April 2011]
The best among the various feasible solutions which optimisesthe objective function.
19. When can dual simplex method be applied? [June 2011]
The dual simplex method is used to solve problems whose primal is optimal but infeasible.
In this method the solution starts optimum, but infeasible and remains infeasible until the true
optimum is reached, at which stage the solution becomes feasible. The advantage of this method
is avoiding introducing artificial variables in the constraints along with the surplus variables, as
all ≥ constraints are converted to ≤ constraints.
20. What is sensitivity analysis? [April 2010, Dec 2012]
Once the optimal solution to a linear programming problem has been attained, it may be
desirable to study how the current solution changes when the parameters of the problem get
changed. The study of the effect of changes in the values of the parameters on the optimal
solution is called sensitivity analysis or postoptimality analysis. The objective is to determine
how sensitive the optimal solution is to changes in the values of these parameters.
21. Why are slack and surplus variables used while solving LPP using simplex method?[June
2013]
Slack and surplus variables are used to convert the inequality to equality in the LPP.
22. Write the dual of the problem [Dec 2013]
𝑴𝒊𝒏𝒊𝒎𝒊𝒛𝒆 𝒇 = 𝟑𝒙𝟏 + 𝒙𝟑 + 𝟐𝒙𝟓
Subject to 𝒙𝟏 + 𝒙𝟑 − 𝒙𝟒 + 𝒙𝟓 = −𝟏
𝒙𝟐 − 𝟐𝒙𝟑 + 𝟑𝒙𝟒 + 𝟐𝒙𝟓 = −𝟐 𝒙𝒊 > 𝟎, 𝒊 = 𝟏 𝒕𝒐 𝟓
Ans: 𝑀𝑎𝑥 𝑊 = −𝑦1 – 2𝑦2
Subject to 𝑦1 − 2𝑦2 ≤ 1
𝑦1 + 2𝑦2 ≤ 2
𝑦1 ≤ 3, 𝑦1 , 𝑦2 , 𝑦3 ≥ 0.
23. What is an unbounded solution?[June 2014]
The objective function value can be increased/decreased infinitely without any limitation.
24. What is the role of Operation Research in improving productivity?[Dec 2014]
If the productivity ratio of an organization is more than 1, the organization is in a comfortable
position. There are several strategies for improving productivity such as Increased output for the
same input, Decreased input for the same output, Increase in the output is more than the increase
in the input, Decrease in the input is more than the decrease in the output, increase in the output
with decrease in the input.
25. Explain briefly the Primal-Dual relationship.[Dec 2014]
The dual model of a Linear Programming problem consists of an alternative modeling instance
that allows us to recover the information of the original problem commonly known as primal
model. Therefore it is sufficient to solve one of them (primal or dual) to obtain the optimal
solution and the optimal value of the equivalent problem (primal or dual as applicable).
26. State the limitation of a graphical method.[June 2015]
Graphical method is applicable only for two decision variables.
27. How does dual simplex method differ from simplex method?[June 2015]
 Panimalar Engineering College
Simplex method maintains feasibility and moves towards optimality. Dual simplex method
maintains optimality and moves towards feasibility.
28. What is Sensitivity Analysis? [Apr/May -2017 ,Nov/Dec-2017]
Sensitivity Analysis deals with finding out the amount by which we can change the input data
for the output of our linear programming model to remain comparatively unchanged.

PART-B
1. An animal feed company must produce 200kg of a mixture consisting of ingredients x1and x2
respectively. 𝑥1 costs Rs.3/- per kg and 𝑥2 Rs.8/- per kg. Not more than 80 kg of 𝑥 1 can be used
and at least 60kg of 𝑥2 must be used. Determine how much of each ingredient should be used to
minimize cost. [Dec 2012]
2. A person wants to decide the constituents of a diet which will fulfill his daily requirements of
proteins, fat and carbohydrates at the minimum cost. The choice is to be made from four
different types of foods. The yields per unit of these foods are given below:
Yield Per Unit
Food Type Cost Per Unit
Proteins Fats Carbohydrates
1 3 2 6 45
2 4 2 4 40
3 8 7 7 85
4 6 5 4 65
Minimum
800 200 300
Requirement
Formulate the LPP for the problem. [June 2015]
3. A plant manufactures two products A and B. The profit contribution of each product has been
estimated as Rs.300 for product A and Rs.400 for product B. Each product passes through three
departments of the plant. The time required for each product and total time available in each
department are as follows.
Available hours
Hours Required
during the month
Department Product A Product B
I 2 3 1600
II 3 2 1500
III 1 1 700
The company has a contract to supply at least 300 units of product B per month. Formulate the
problem as a linear programming model and solve the by using graphical method. [June 2013]
4. Solve the following LP problem graphically:
Minimize 𝑍 = 20𝑥 + 10𝑦
subject to 𝑥 + 2𝑦 ≤ 40
3𝑥 + 𝑦 ≥ 30
4𝑥 + 3𝑦 ≥ 60; 𝑥, 𝑦 ≥ 0. [April 2010]
5. Find the maximum value of 𝑍 = 2𝑥 + 3𝑦 subject to 𝑥 + 𝑦 ≤ 30; 𝑦 ≥ 3; 𝑦 ≤ 12;
0 ≤ 𝑥 ≤ 20. Solve graphically. [June 2010]
6. Solve following LPP graphically: Minimize 𝑍 = 3𝑥 + 2𝑦 subject to 𝑥 − 𝑦 < 1; 𝑥 + 𝑦 > 3 and
𝑥, 𝑦 > 0 [June 2015]
7. Using Simplex method solve:
𝑀𝑎𝑥 𝑍 = 3𝑥1 + 2𝑥2 + 5𝑥3
subject to 𝑥1 + 2𝑥2 + 𝑥3 ≤ 43, 3𝑥1 + 2𝑥3 ≤ 46, 𝑥1 + 4𝑥2 ≤ 42 and 𝑥1 , 𝑥2 , 𝑥3 ≥ 0.
8. Solve the following LP problem using simplex method:
𝑀𝑎𝑥 𝑍 = 10𝑦1 + 15𝑦2 + 20𝑦3
Subject to 2𝑦1 + 4𝑦2 + 6𝑦3 ≤ 24, 3𝑦1 + 9𝑦2 + 6𝑦3 ≤ 30, 𝑦1 , 𝑦2 , 𝑦3 ≥ 0.
 Panimalar Engineering College
9. Solve the following LP problem using Simplex method:
Maximize 𝑍 = 3𝑥 + 2𝑦 + 5𝑧
subject to 𝑥 + 𝑦 + 𝑧 ≤ 9; 2𝑥 + 3𝑦 + 5𝑧 ≤ 30; 2𝑥 − 𝑦 − 𝑧 ≤ 8; 𝑥, 𝑦, 𝑧 ≥ 0. [April 2010]
10. Use penalty method to solve the following LP problem:
Minimize 𝑍 = 5𝑥 + 3𝑦 subject to
2𝑥 + 4𝑦 ≤ 12, 2𝑥 + 2𝑦 = 10, 5𝑥 + 2𝑦 ≥ 10 and 𝑥, 𝑦 ≥ 0.
11. Solve the following LPP through Big-M Method:
Minimize 𝑍 = 5𝑥1 − 6𝑥2 − 7𝑥3
subject to 𝑥1 + 5𝑥2 − 3𝑥3 ≥ 15;5𝑥1 − 6𝑥2 + 10𝑥3 ≤ 20; 𝑥1 + 𝑥2 + 𝑥3 = 5;
𝑥1 , 𝑥2 , 𝑥3 ≥ 0.[June 2014]
12. Solve the following LP problem using Simplex method.
Maximize 𝑍 = 3𝑥1 − 𝑥2
subject to 2𝑥1 + 𝑥2 < 2; 𝑥1 + 3𝑥2 > 3; 𝑥2 < 4 and 𝑥1 , 𝑥2 > 0.[Dec 2014]
13. Solve the following LP problem using two-phase method:
𝑀𝑖𝑛 𝑍 = 10𝑥1 + 6𝑥2 + 2𝑥3
subject to – 𝑥1 + 𝑥2 + 𝑥3 ≥ 1, 3𝑥1 + 𝑥2 − 𝑥3 ≥ 2, 𝑥1 , 𝑥2 , 𝑥3 ≥ 0.
14. Use two phase method to
Minimize 𝑍 = 𝑥1 + 𝑥2
subject to 2𝑥1 + 𝑥2 ≥ 4; 𝑥1 + 7 𝑥2 ≥ 7; 𝑥1 , 𝑥2 ≥ 0. [June 2012]
15. Solve the following LPP by two-phase simplex method:
Maximize 𝑍 = −4𝑎 − 3𝑏 − 9𝑐
subject to 2𝑎 + 4𝑏 + 6𝑐 > 15; 6𝑎 + 𝑏 + 6𝑐 > 12; 𝑎, 𝑏, 𝑐 ≥ 0. [June 2015]
16. Solve the following LPP by dual simplex method:
𝑀𝑖𝑛 𝑍 = 5𝑥 + 6𝑦
subject to 𝑥 + 𝑦 ≥ 2; 4𝑥 + 𝑦 ≥ 4; 𝑥, 𝑦 ≥ 0. [June 2011]
17. Solve the following linear programming problem using its dual:
Maximize 𝑍 = 5𝑥1 − 2𝑥2 + 3𝑥3
subject to 2𝑥1 + 2𝑥2 − 𝑥3 ≥ 2, 𝑥2 + 3𝑥3 ≤ 5, 𝑥1 , 𝑥2 , 𝑥3 ≥ 0 .[June 2013]
18. Solve the following LPP by dual simplex method:
Minimize 𝑍 = 2𝑥1 + 𝑥2
subject to 3𝑥1 + 𝑥2 ≥ 3; 4𝑥1 + 3𝑥2 ≥ 6; 𝑥1 + 2𝑥2 ≤ 3; 𝑥1 , 𝑥2 ≥ 0. [June 2014]
19. Use a Dual Simplex method to solve the following LP problem.
Minimize 𝑍 = 2𝑥1 + 2𝑥2 + 4𝑥3
subject to 2𝑥1 + 3𝑥2 + 5𝑥3 ≥ 2; 3𝑥1 + 𝑥2 − 7𝑥3 ≤ 3; 𝑥1 + 4𝑥2 − 6𝑥3 ≤ 5
𝑥1 , 𝑥2 , 𝑥3 ≥ 0. [Dec 2014]
20. Consider the LPP
𝑀𝑎𝑥 𝑍 = 5𝑥1 + 12𝑥2 + 4𝑥3
Subject to 𝑥1 + 2𝑥2 ≤ 5 ; 5𝑥1 − 𝑥2 + 2𝑥3 = 2 ; 𝑥1 , 𝑥2 , 𝑥3 ≥ 0
(a) Solve the LPP
5 7
(b) Discuss the effect of changing the requirement vector from ( ) to ( ), on the optimal
2 2
solution.
 Panimalar Engineering College
UNIT – II
BRANCH AND BOUNDED, TRANSPORTATION MODELS
PART-A
1. Define Integer Programming problem (IPP).
Integer Programming problem is a special type of LP problem in which some or all of the
decision variables are restricted to take only integer values.
2. Differentiate between pure and mixed integer programming problems. [June 2012, Dec
2012,June 2013]
Pure IPP is one where all decision variables need to be integers. Mixed IPP is one in which only
some decision variables need to be integers.
3. Explain the importance of IPP.
In LPP, all decision variables can take any non-negative real (continuous or fractional) values;
e.g. it is possible to use 6.38 kg of raw material, 5.62 machine hours, etc. But in some situations,
especially in business and industry, the decision variables can take only integer values; it is
meaningless to produce 8.13 chairs or 6.85 tables, etc. IPP is a technique developed for the case
of LPP with the additional restriction that the decision variables must have integer values.
4. What is meant by mixed integer programming problem? [Dec 2010]
An IPP in which only some of the decision variables need to be integers, while the remaining
can bave non-integer (i.e. decimal or fractional) values.
5. Why not round off to integer values instead of resorting to IPP? Explain.
Rounding off the non-integer values to integers in the optimal solution of the Simplex method
does not guarantee that this solution will satisfy all the constraints. Further, there is also no
guarantee that the rounded down solution will remain optimal. Hence the need for IPP.
6. Explain Gomory’s constraint in an IPP.
Gomory’s constraint is an additional constraint introduced in an integer programming problem
to eliminate non-integer solutions without losing any integer valued solution.
7. Discuss the role of cutting plane algorithm. [June 2010]
In integer programming problems, when the optimal solution is non-integer, the cutting plane
algorithm helps to remove the fractional portions to obtain an integer solution.
8. Describe a situation where we encounter transportation problem.
A number of units of a commodity are to be transported from various sources to various
destinations so that the supplies and demands are met at minimum overall transportation cost.
9. Mention the methods of obtaining an initial basic feasible solution to a transportation
problem.[Nov 2011, Dec 2012]
(i) NW Corner method, (ii) Least Cost method, and (iii) VA method.
10. What is degeneracy in a transportation model? [June 2012,June 2013,Dec 2014]
When the number of allocations (basic variables or occupied cells) is less than (m+n-1) where m
is the number of rows and n is the number of columns, then degeneracy arises.
11. How is degeneracy handled in MODI method?
By assigning a negligible value (Δ or epsilon) in one (or more, if required) empty cells located
in independent position and treating it as an occupied cell.
12. How many basic variables occur in a balanced transportation problem with 3 rows and 3
columns?
3+3-1=5 basic variables.
13. Define Unbalanced transportation problem.[June 2015]
A transportation problem in which the total demand and total supply are not equal.
14. What does VAM stand for?
Vogel’s Approximation Method, a very efficient method of obtaining an initial basic feasible
solution to a transportation problem.
 Panimalar Engineering College
15. Find an initial basic feasible solution to the following transportation problem by North
West Corner method.
DESTINATIONS
P Q R S Supply
A 14 25 45 05 06
SOURCES B 65 18 30 10 08
C 20 03 18 12 16
Demand 04 07 06 13
AP-04, AQ-02, BQ-05, BR-03, CR-03, CS-13.

16. Find an initial basic feasible solution to the following transportation problem by Least
Cost method.
DESTINATIONS
P Q R S Supply
A 06 01 09 03 70
SOURCES B 11 05 02 08 55
C 10 12 04 07 90
Demand 85 35 50 45
AQ-35, AS-35, BP-05, BR-50, CP-80, CS-10.
17. Explain the assignment model as a special case of a transportation model.
The assignment model is a special case of the transportation model wherein the supply at each
‘source’ and the demand at each ‘destination’ are equal to one.
18. Explain the differences between transportation and assignment problems. [June 2010,
Dec2013, June 2014]
(i) While the transportation model involves transport of a commodity from various sources to
destinations at minimum overall cost, assignment model is concerned with assigning of jobs to
machines, jobs to workers, salesmen to territories, etc. (ii) The assignment model is a special
case of the transportation model wherein the supply at each ‘source’ and the demand at each
‘destination’ are equal to one.
19. Define transhipment problem. [June 2010, Dec 2012,June2013]
In the transportation model, items are shipped directly from various sources to destinations. In
the transhipment problem, it becomes more economical if the shipment passes through some
intermediate (transient) nodes between the sources and destinations.
20. What is assignment problem? [April 2011]
The assignment problem is a special case of the transportation problem in which the objective is
to assign tasks (jobs, origins or sources) to an equal number of facilities (machines or persons or
destinations) at minimum cost (or maximum profit).
21. Explain how a maximization problem is solved using assignment model.
A maximization problem is converted into minimization problem by either of two methods: (a)
multiplying all elements with minus sign, (b) identifying the largest element in matrix and
subtracting all elements from it. The converted minimization problem is solved by the
Hungarian method.
22. Define unbalanced assignment problem [June 2011,Dec 2014]
An assignment problem in which the number of rows is not equal to the number of columns.
23. What do you understand by restricted assignment? How do you overcome it?
When some particular tasks (jobs, origins) cannot be assigned to particular facilities (machines,
persons), we call it a restricted assignment problem. The problem can be overcome by assigning
very large value in restricted cells and solving by Hungarian method.
24. Give the areas of application of assignment problems
Ans. Assigning of jobs to workers, jobs to machines, workers to machines, salesmen to
territories, crew to duties, , etc. on one-to-one basis to minimize cost or maximize profit.
 Panimalar Engineering College
25. If each entry increases by 3 in a 4X4 assignment problem, what happens to the optimal
value?
The optimal value (minimum total cost) increases by 3 × 4 = 12.
26. What is a travelling salesman problem? [June 2010]
Starting from a city, a salesman has to visit a number of cities, visiting each city only once
before returning to the starting city and covering the entire trip in the minimum
distance/time/cost.
27. How does a travelling salesman problem differ from an assignment problem?
In assignment problem, the rows and columns represent different entities, e.g. jobs and
machines, jobs and workers, etc. In travelling salesman problem, both rows and columns
represent the same entity, i.e. cities/ towns, etc. The long diagonal in travelling salesman
problem does not contain any entries. The optimal assignment solution must satisfy the
travelling salesman condition, otherwise it should be suitably modified to do so.
28. What is meant by balanced problem in case of a) transportation problem and b)
assignment problem?[Dec 2013]
a) If the sum of the supplies of all the sources is equal to the sum of the demands of all the
destinations then the problem is termed as transportation problem
b)If the number of rows is equal to the number of columns then the problem is termed as
balanced assignment problem.
29. Least cost method is superior to North-West corner method in obtaining starting solution.
Why? [June 2014]
In North West corner method, the objective is not included in the process. North West Corner
method can yield an initial basic feasible solution but shipping cost is very high. So Least cost
method is superior to North-West corner method in obtaining starting solution.
30. Which will be the first basic variable in case of North West Corner Method and Least
Cost Method?[June 2015]
In North West Corner method the cell in the north-west corner of the table will be the first basic
variable and in Least Cost method the cell with the least cost element will be the first basic
variable.
PART-B
1. Solve the following integer programming problem by Gomory’s method:
Maximize 𝑍 = 7𝑥1 + 5𝑥2
subject to 𝑥1 + 𝑥2 ≤ 4; 5𝑥1 + 3𝑥2 ≤ 15; 𝑥1 , 𝑥2 ≥ 0 and integers.
2. Solve the following integer programming problem:
Maximize 𝑍 = 5 𝑥1 + 8 𝑥2
subject to 𝑥1 + 2 𝑥2 ≤ 8, 4 𝑥1 + 𝑥2 ≤ 10, 𝑥1 , 𝑥2 ≥ 0 and integers.
3. Solve the following integer programming problem optimally:
Maximize 𝑍 = 2𝑥 + 5𝑦
subject to 3𝑥 + 6𝑦 ≤ 24; 6𝑥 + 12𝑦 ≤ 18; 2𝑥 + 8𝑦 ≤ 20;
𝑥, 𝑦 ≥ 0 and integers. [June 2010]
4. Solve the following integer programming problem by cutting plane algorithm:
Maximize 𝑍 = 𝑥1 + 2 𝑥2
subject to 𝑥1 + 2 𝑥2 ≤ 12; 4 𝑥1 + 3 𝑥2 ≤ 14; 𝑥1 , 𝑥2 are non-negative integers. [Dec 2012].
5. Solve 𝑀𝑎𝑥 𝑍 = 𝑥 + 4𝑦 subject to 2𝑥 + 4𝑦 ≤ 7; 5𝑥 + 3𝑦 ≤ 15, where 𝑥, 𝑦 are integers.
6. Solve the following mixed integer problem by the branch and bound technique:
Maximize 𝑍 = 𝑥1 + 𝑥2
subject to 2𝑥1 + 5𝑥2 ≤ 16; 6𝑥1 + 5𝑥2 ≤ 30; 𝑥2 ≥ 0 and integer , 𝑥1 ≥ 0.[June 2013]
7. Find the optimum integer solution to the following LPP;
Maximize 𝑍 = 7 𝑥1 + 9𝑥2
subject to − 𝑥1 + 3𝑥2 ≤ 6; 7 𝑥1 + 𝑥2 ≤ 35; 𝑥1 , 𝑥2 ≥ 0 and integers. [June 2014]
 Panimalar Engineering College
8. Find the optimum integer solution to the following LPP
Maximize 𝑍 = 3𝑥1 + 7𝑥2
subject to 3𝑥1 + 4𝑥2 ≤ 19; 3𝑥1 + 6𝑥2 ≤ 21; 𝑥1 , 𝑥2 non-negative integers.[June 2015]
9. Solve the following integral programming problem using the branch and bound method.
Minimize 𝑍 = 3𝑥1 + 2.5𝑥2
Subject to 𝑥1 + 2𝑥2 > 20; 3𝑥1 + 2𝑥2 > 50; and 𝑥1 , 𝑥2 ≥ 0 and integers. [Dec 2014]
10. Find the optimal solution to the following transportation problem and the cost is in rupees.
Warehouses
Available
W1 W2 W3 W4 W5
F1 7 6 4 5 9 40
F2 8 5 6 7 8 30
Factories F3 6 8 9 6 5 20
F4 5 7 7 8 6 10
Required 30 30 15 20 5 100 (Total)
11. A product is manufactured by four factories A, B, C, D. The unit production cost in them are
Rs.2, Rs.3, Re.1 and Rs.5 respectively. Their production capacities are 50, 70, 30 and 50 units
respectively. These factories supply the product to four stores, the demands of which are 25, 35,
105 and 20 units. Unit transportation cost, in rupees, from each factory to each store is given in
the table, Determine the extent of deliveries from each factory to each store so that total
production and transportation cost is minimum. [June, 2011].
Stores
Factories 1 2 3 4
A 2 4 6 11
B 10 8 7 5
C 13 3 9 12
D 4 6 8 3
12. Find the basic feasible solution of the following transportation problem by VAM. Also find the
optimal transportation plan. [June 2010]
1 2 3 4 5 Available

A 4 3 1 2 6 80

B 5 2 3 4 5 60

C 3 5 6 3 2 40

D 2 4 4 5 3 20

Required 60 60 30 40 10 200

13. A military equipment is to be transported from three origins to four destinations. The supply at
the origins, the demand at the destinations and time of shipment is shown in the table below.
Determine the initial basic feasible solution s to this transportation problem using least cost and
Vogel’s approximation methods.[June 2013]
 Panimalar Engineering College
Destination

D1 D2 D3 D4 Availability

O1 5 2 4 3 22

Origin
O2 4 8 1 6 15

O3 4 6 7 5 8

Demand 7 12 17 9
14. A company has three plants A,B and C, 3 warehouses X,Y and Z. The number of units available
at the plants, demand of the warehouses and the unit cost of transportation are given below. Find
the allocation so that the total transportation cost is minimum.[June 2014]
X Y Z Supply

A 5 1 7 10

B 6 4 6 80

C 3 2 5 15

Demand 75 20 50
15. Goods has to be transported from sources S1, S2 and S3 to the destinations D1,D2 and D3. The
transportation cost per unit, capacities of the sources and requirements of the destinations are
given in the following table. Define a transportation schedule so that cost is optimum.[Dec
2014]
Destinations
D1 D2 D3 Supply
S1 8 5 6 120
Source S2 15 10 12 80
S3 3 9 10 150
Demand 150 80 50
16. Solve the following transportation problem to minimize the total transportation cost for shifting
the goods from factories (A, B and C) to warehouses (P, Q and R) where unit transportation
cost, availability and demand at factories and warehouses respectively are given in the following
matrix. Find the allocation so that the total transportation cost is minimum.[June 2015]
Warehouse
P Q R Availability
A 1 2 0 30
Factory
B 2 3 4 35
C 1 5 6 35
Demand 30 40 30
 Panimalar Engineering College
17. A company has five jobs to be done on five machines, any job can be done on any machine. The
costs of doing the jobs on different machines are given below. Assign the jobs to machines so as
to minimize the total cost.
MACHINES
A B C D E
I 13 8 16 18 19
JOB II 9 15 24 9 12
III 12 9 4 4 4
IV 6 12 10 8 13
V 15 17 18 12 20
18. At the end of a cycle schedule a trucking firm has a surplus of one vehicle in each of the cities
1,2,3,4 and 5 and a deficit of one vehicle in each of the cities A,B,C,D,E and F. The costs in
rupees, of transportation and handling between the cities are given below. Find the assignment
of surplus vehicles to deficit cities, which results in minimum total cost. [Jan 2011]
A B C D E F
1 134 116 167 233 194 97
2 114 195 260 166 175 130
3 129 117 48 94 66 101
4 71 156 92 143 114 136
5 97 134 125 83 142 118
19. Four salesmen are to be assigned to four districts. Estimates of sales revenue are as below:
DISTRICT
A B C D
1 320 350 400 280
SALESMAN 2 400 250 300 200
3 420 270 340 300
4 250 390 410 350
Find out the assignment pattern to maximize the sales revenue.
20. Solve the following assignment problems to minimize time.[June 2013]
Job
J1 J2 J3 J4 J5
M1 2 9 3 7 1
M2 6 8 7 6 1
Men
M3 4 6 5 3 1
M4 4 2 7 3 1
M5 5 3 9 5 1
21. Company has one surplus truck in each of the cities A,B,C,D and E and one deficit truck in each
of the cities 1,2,3,4,5 and 6. The distance between the cities (in km) is shown in below matrix.
Find the assignment of trucks from cities in surplus to cities in deficit so that the distance
covered vehicles is minimum.[Dec 2014]
 Panimalar Engineering College
To Cities (Deficit)
1 2 3 4 5 6
A 12 10 15 22 18 8
B 10 18 25 15 16 12
From
Cities C 11 10 3 8 5 9
(Surplus) 12
D 6 14 10 13 13
E 8 12 11 7 13 10
22. A company is faced with the problem of assigning 4 machines to 6 different jobs (one machine
to one job only). The profits are estimated as follows. Solve the problem to maximize the total
profits. [Dec 2010]

Job Machine
A B C D
1 3 6 2 6
2 7 1 4 4
3 3 8 5 8
4 6 4 3 7
5 5 2 4 3
6 5 7 6 4
23. Six salesmen are to be allocated to six regions. The earning of each salesman (Rupees in
thousands) at each region is given below. Find an allocation for maximum total earnings. [June
2014]
Region
Salesman 1 2 3 4 5 6
A 15 35 0 25 10 45
B 40 5 45 20 15 20
C 25 60 10 65 25 10
D 25 20 35 10 25 60
E 30 70 40 5 40 50
F 10 25 30 40 50 15
24. Solve the following Traveling Salesman problem:
TO CITY
1 2 3 4 5
1 ∞ 11 17 14 13
FROM 2 12 ∞ 16 13 14
CITY 3 11 16 ∞ 12 11
4 11 15 14 ∞ 16
5 17 15 14 15 ∞
25. Solve the following transhipment problem involving 4 sources and 2 destinations. The supplies
at the sources S1, S2, S3 and S4 are 200, 250, 200 and 450 units respectively. The demands at
the destinations D1 and D2 are 550 and 550 units respectively. The transportation costs per unit
between different sources and destinations are given in the following table.
 Panimalar Engineering College
DESTINATION
𝑆1 𝑆2 𝑆3 𝑆4 𝐷1 𝐷2

𝑆1 0 6 24 7 24 10
𝑆2 10 0 6 12 5 20
SOURCE
𝑆3 15 20 0 8 45 7
𝑆4 18 25 10 0 30 6
𝐷1 15 20 60 15 0 10
𝐷2 10 25 25 23 4 0
26. Solve the following assignment problem by branch and bound algorithm The cell entries
represent processing times in hours of the job i assigned to operator j.[April 2010]
Operator j
1 2 3 4
1 13 5 8 10
Job i 2 9 15 18 10
3 12 14 10 10
4 10 14 9 12
27. A company has 4 territories and four salesmen for assignment. The territories are not equally
rich in their sales potential. It is estimated that a typical salesman operating in each territory
would bring the following annual sales.
Territory I II III IV

Annual Sales in Rs 60000 50000 40000 30000

The four salesmen are also considered to differ in their ability, it is estimated that working under
same condition, their yearly sales would be proportionately as follows
Salesman A B C D

Proportion 0.1 0.2 0.3 0.4

If the criteria is to maximize expected sales, what is your intuitive answer and verify your
answer with Hungarian method. [June 2015]
 Panimalar Engineering College
UNIT – III
NETWORK MODELS
PART-A
1. What is meant by critical path? [Nov/Dec 2016]
The critical path of a network gives the shortest time in which the whole project can be completed.It
is the chain of activities with the longest time duration.Any delay in any of the activities results in
the delay of the completion of the project.
2. Define PERT and CPM? [Nov/Dec 2017]
PERT: Project Scheduling with Uncertain Activity Times is called Project evaluation and research
technique. In PERT activities are shown as a network of precedence relationships using activity-on-
arrow network construction.
CPM: Project Scheduling with Known Activity Times and considering Time-Cost Trade-Offs is
called Critical path method. In CPM activities are shown as a network of precedence relationships
using activity-on-node network construction.
3. Define path and length in a network
A path through a project network is one of the routes following the arcs from the START node to
the FINISH node. The length of a path is the sum of the (estimated) durations of the activities on the
path.
4. Define critical path
The path of least float is called a Critical Path. The (estimated) project duration equals the length of
the longest path through the project network. This longest path is called the critical path. (If more
than one path tie for the longest, they all are critical paths.)
Is that the sequence of activities and events where there is no “slack” i.e.. Zero slack
5. What do you mean by network?
• A Network is a symbolic representation of the essential characteristics of a project.
• Network technique is a tool of project management. PERT and CPM are the widely applied
techniques.
6. What do you mean by an activity?
Any individual operation which utilizes resources and has an end and a beginning is called activity.
An arrow is commonly used to represent an activity with its head indicating the direction of
progress in the project. These are classified into four categories
Predecessor activity– Activities that must be completed immediately prior to the start of another
activity are called predecessor activities.
Successor activity–Activities that cannot be started until one or more of other activities are
completed but immediately succeed them are called successor activities.
Concurrent activity–Activities which can be accomplished concurrently are known as concurrent
activities. It may be noted that an activity can be a predecessor or a successor to an event or it may
be concurrent with one or more of other activities.
Dummy activity–An activity which does not consume any kind of resource but merely depicts the
technological dependence is called a dummy activity.
7. What is a dummy activity?
An activity which does not consume any kind of resource but merely depicts the technological
dependence is called a dummy activity. The dummy activity is inserted in the network to clarify the
activity pattern in the following two situations
➢ To make activities with common starting and finishing points distinguishable
➢ To identify and maintain the proper precedence relationship between activities that is not
connected by events.
For example, consider a situation where A and B are concurrent activities. C is dependent on A and
D is dependent on A and B both. Such a situation can be handled by using a dummy activity as
shown in the figure
 Panimalar Engineering College

8. What is dangling in a network?

To disconnect an activity before the completion of all activities in a network diagram is known as
dangling. As shown in the figure activities (5 – 10) and (6 – 7) are not the last activities in the
network. So the diagram is wrong and indicates the error of dangling.

9. If the critical path of a network is 1-2-4-6-7 and the variances of 1-2 , 2-3, 2-4, 4-5, 4-6, 2-6,
4-7 and 6-7 are 3,6,5,7,6,10,1,2. What is the variance of the project length
Variance of 1-2 = 3
2-4 = 5
4-6= 6
6-7= 2
Total Variance = 16
10. What is resource levelling in network analysis?
Resource leveling is a technique for resolving resource conflicts by delaying tasks.Resource
leveling is a technique in project management that over looks resource allocation and resolves
possible conflict arising from over allocation.
11. What do you mean by slack time?
Difference between the latest time and the earliest time of an event is the slack time for that event .
Positive slack : Slack is the amount of time an event can be delayed without delaying the project
completion
12. Can the total float be negative?
Yes , total float can be negative. Negative float, also known as negative slack, is the amount of time
beyond a project’s scheduled completion that a task within the project requires.
13. What is free float?
The amount of time a schedule activity can be delayed without delaying the early start date of any
successor or violating a schedule constraint.
Free Float=Earliest start time of the next activity – Earliest completion time of the activity
14. What is total float?
The amount of time by which an activity can delayed without delaying the project finish date.
Total float= LS (Late Start) – ES (Early Start) or LF (Late Finish) – EF (Early Finish)
15. What is interfering float?
The part of total float which is not free is called interfering float.
Interfering float= total float – free float
16. What is independent float?
Independent float is the amount of time which can be used without affecting the head and the tail
events.
Independent float= Earliest start time of the next activity-Latest finish time of the preceding
activity-duration of the activity.
 Panimalar Engineering College
17. List out the applications of PERT/CPM?
• Construction of a dam or a canal system in a region
• Construction of a building or highway
• Maintenance or overhaul of airplanes or oil refinery
• Space flight
• Cost control of a project using PERT / COST
• Designing a prototype of a machine
• Development of supersonic planes
18. What are the basic steps in PERT/CPM
a) Planning b) Scheduling c)Allocation of resources d) Controlling
19. What is an event? List the various event types?
An event represents a point in time signifying the completion of some activities and the beginning
of new ones. This is usually represented by a circle in a network which is also called a node or
connector.
The events are classified in to three categories
1. Merge event – When more than one activity comes and joins an event such an event is
known as merge event.
2. Burst event – When more than one activity leaves an event such an event is known as
burst event.
3. Merge and Burst event – An activity may be merge and burst event at the same time as with
respect to some activities it can be a merge event and with respect to some other activities it may be
a burst event.
20. Define the Fulkerson’s rule for numbering the events?
a) Identify the “initial event” and assign it number ‘1’. Initial event is the starting point of any
project. Defining from the angle of a network diagram, initial event is the event, which has one
or more arrows emerging from it and no arrow entering it.
b) Delete all the emerging arrows from the initial event (event 1). This will create one or more
“new initial events”. Number these new initial events as 2,3,4,… etc.
c) Delete all the emerging arrows from the new initial events, which will create a new set of new
initial events. Assign numbers to these initial events starting from the number that has so far
been assigned.
d) Follow the above procedure till the end of the network is reached. The last event of the network
is the one from which no arrow emerges and into which one or more arrows enters. The last
event is assigned with the highest number in the network.
21. State the rules for network construction? [Apr/May 2017]
• Each activity is represented by one and only one arrow.
• Time flows from left to right.
• Arrows should be straight and not curved
• Arrows should not cross each other where crossing cannot be avoided, bridging should be
done
22. Draw the network for the project whose activities and their precedence relationship are as
given below. [Apr/May 2017]
Activities A B C D E F G H I

Precedence - A A - D B,C.E F E G,H

23. Distinction between PERT and CPM. [Apr/May 2018]

PERT CPM
1. PERT is used for non-repetitive jobs 1. CPM is used for repetitive job like building
like planning the assembly of the space. a house
2. it is a probabilistic model. 2. It is a deterministic model.
 Panimalar Engineering College
3. It is event-oriented as the results of 3. It is activity-oriented as the result or
analysis are expressed in terms of events calculations are considered in terms of
or distinct points in time indicative of activities or operations of the project.
progress. 4. It is applied mainly for construction and
4. It is applied mainly for planning and business problems.
scheduling research programmes. 5. CPM does not incorporate statistical analysis
5. PERT incorporates statistical analysis in determining time estimates, because time is
and thereby determines the probabilities precise and known.
concerning the time by which each 6. It is difficult to use CPM as a control device
activity or entire project would be for the simple reason that one must repeat the
completed. entire evaluation of the project each time the
6. PERT serves as useful control device as changes are introduced into the network
it assists management in controlling a
project by calling attention to such delays

24. If there are five activities P,Q,R,S and T such that P,Q,R have no immediate predecessors but S
and T have immediate predecessors P,Q and Q,R respectively. Represent this situation by a
network. [Nov/Dec 16]
3
P S
D1

1 Q 2 5

D2
R T
4

25. Define pessimistic time estimate in PERT [Apr/May 2018]

Pessimistic time, expressed as ‘tp’ represents estimate of maximum possible time by which an
activity can be completed assuming that things may not be in accordance with the plan and there
can be incidence of difficulties in carrying out the activity.
PART B
1. Compare and contrast PERT & CPM. [Nov/Dec 2017], Under what conditions would you
recommend scheduling by PERT? State the circumstances where CPM is better
technique?
2. Following are the manpower requirements for each activity in a project.
Activity Normal Time Manpower Required
0-1 2 4
1-2 3 3
1-3 4 3
2-4 2 5
3-5 4 3
3-6 3 4
4-7 6 3
5-7 6 6
6-8 5 2
7-9 4 2
8-9 4 9
(a) Draw the network diagram of the project activities
(b) Rearrange the activities suitably for reducing the existing total manpower requirements.
 Panimalar Engineering College
(c) If only 9 men are available for the execution of the project, then rearrange the activities
suitable for leveling the manpower resource.
3. a) Construct an activity on arrow network based on the activity descriptions below. Label
activities in the network by their activity letters and node numbers. Remove any redundant
dependencies and label dummy activities DUMMY1, DUMMY2, etc.
b) Construct a precedence network based on the same activity descriptions below. Label
activities in the network by their activity letters and node numbers. Remove all redundant
dependencies and arrange activities in proper sequence steps.
• Activities H, R2, T1 start the project.
• Activity T2 can start when Activities H, E1 and S are completed.
• Activity E1 also depends on Activity R2.
• Activity X follows Activity H and precedes Activity L.
• Activity E is preceded by Activities T2 and P1.
• The predecessors to Activity G are Activities L, T2 and P1.
• The successors to Activity T1 are Activities E1, S, W and D2.
• Activity P1 cannot begin until Activity W is finished.
• Activity P2 and F follow Activities W and D2, and precede Activities E and R1.
• Activity O2 depends on T2 and P1 , and precedes Activity L.
4. A project schedule has the following characteristics
Activity 0-1 0-2 1-3 2-3 2-4 3-4 3-5 4-5 4-6 5-6
Key 2 3 2 3 3 0 8 7 8 6
(i). Construct Network diagram.
(ii). Compute Earliest time and latest time for each event.
(iii). Find the critical path. Also obtain the Total float, Free float and slack time and
independent float.
5. 5. A project schedule has the following characteristics.
Activity 1-2 1-3 2-4 3-4 3-5 4-9 5-6 5-7 6-8 7-8 8-10 9-10
Time 4 1 1 1 6 5 4 8 1 2 5 7
(i). Construct Network diagram
(ii). Compute Earliest time and latest time for each event.
(iii). Find the critical path. Also obtain the Total float, Free float and slack time and
independent float.
6. A small project is composed of seven activities whose time estimates are listed in the table as
follows:
Activity Preceding Activities Duration
A ---- 4
B ---- 7
C ---- 6
D A,B 5
E A,B 7
F C,D,E 6
G C,D,E 5
(i). Draw the network and find the project completion time.
(ii). Calculate the three floats for each activity.
7. Calculate the total float, free float and independent float for the project whose activities are
given below: find the Critical Path also
Activity 1-2 1-3 1-5 2-3 2-4 3-4 3-5 3-6 4-6 5-6
Key 8 7 12 4 10 3 5 10 7 4
 Panimalar Engineering College
8. Draw the network for the following project and compute the earliest and latest times for each
event and also find the critical path.
Activity 1-2 1-3 2-4 3-4 4-5 4-6 5-7 6-7 7-8
Immediate
--- --- 1-2 1-3 2-4 2-4&3-4 4-5 4-6 6-7&5-7
Predecessor
Time 5 4 6 2 1 7 8 4 3
9. The following table lists the jobs of a network with their time estimates:
Duration
Job (𝑖, 𝑗)
Optimistic (to) Most likely (tm) Pessimistic (tp)
1-2 3 6 15
1-6 2 5 14
2-3 6 12 30
2-4 2 5 8
3-5 5 11 17
4-5 3 6 15
6-7 3 9 27
5-8 1 4 7
7-8 4 19 28
10. A small project is composed of 7 activities, whose time estimates are listed in the table below.
Activities are identified by their beginning (i) and (j) node numbers.

Duration
Job (𝑖, 𝑗)
Optimistic (to) Most likely (tm) Pessimistic (tp)
1-2 1 1 7
1-3 1 4 7
1-4 2 2 8
2-5 1 1 1
3-5 2 5 14
4-6 2 5 8
5-6 3 6 15
(i). Draw the project network and identify all the paths through it.
(ii). Find expected duration and variance for each activity. What is the expected project length?
(iii). Calculate the variance and standard deviation of the project length. What is the probability that
the project will be completed at least 4 weeks earlier than expected time?
11. The following table lists the jobs of a network along with their time estimates.
Activity 1-2 1-3 2-4 3-4 3-5 4-9 5-6 5-7 6-8 7-8 8-10 9-10
Time 4 1 1 1 6 5 4 8 1 2 5 7
(i). Draw the project network.
(ii). Calculate the length and variance of the critical path after estimating the earliest and
latest event times for all nodes.
(iii). Find the probability of completing the project before 41 days?
12. A project schedule has the following characteristics as shown in Table
Activity Name Time(days) Activity Name Time(days)
1-2 A 4 5-6 G 4
1-3 B 1 5-7 H 8
2-4 C 1 6-8 I 1
3-4 D 1 7-8 J 2
3-5 E 6 8-10 K 5
4-9 F 5 9-10 L 7
 Panimalar Engineering College
(i) Construct PERT network.
(ii) Compute TE and TL for each activity.
(iii) Find the critical path
13. An R & D project has a list of tasks to be performed whose time estimates are given in the
Table, as follows
Activity Activity Name 𝑇0 𝑡𝑚 (in days) 𝑡𝑝
(𝑖, 𝑗)
1-2 A 4 6 8
1-3 B 2 3 10
1-4 C 6 8 16
2-4 D 1 2 3
3-4 E 6 7 8
3-5 F 6 7 14
4-6 G 3 5 7
4-7 H 4 11 12
5-7 I 2 4 6
6-7 J 2 9 10
a. Draw the project network.
b. Find the critical path.
c. Find the probability that the project is completed in 19 days. If the probability is less than
20%, find the probability of completing it in 24 days.
14. A project has the following time schedule. Construct a PERT network and compute critical path.
Activity Time (Months)
1-2 2
1-3 2
1-4 1
2-5 4
3-6 8
3-7 5
4-6 3
5-8 1
6-9 5
7-8 4
8-9 3
15. Consider the problem of project scheduling as shown in the following table.
Activity Duration (weeks) Manpower requirement
1-2 5 8
1-3 4 10
1-4 6 8
2-4 10 10
2-5 4 7
3-5 4 4
4-6 8 12
5-6 9 6
Obtain a schedule which will minimize the peak manpower requirement and also smooth out
period to period variations in manpower requirement.
16. A project consists of activities from A to J as shown in the following table. The immediate
predecessor(s) and the duration in weeks of each of the activities are given in the same table.
Draw the project network and find the critical path and the corresponding project completion
time. Also, find the total float as well as free float for each of the non-critical activities.
[Nov/Dec 16]
 Panimalar Engineering College
Activity Immediate predecessor Duration(Months)
A - 4
B - 3
C A,B 2
D A,B 5
E B 6
F C 4
G D 3
H F,G 7
I F,G 4
J E,H 2
17. Consider the data of a project summarized in the following table: [Nov/Dec 16]
Activity Immediate Duration(Months)
predecessor a m b
A - 4 4 10
B - 1 2 9
C - 2 5 14
D A 1 4 7
E A 1 2 3
F A 1 5 9
G B,C 1 2 9
H C 4 4 4
I D 2 2 8
J E,G 6 7 8
(i) Construct the project network
(ii) Find the expected duration and the variance of each activity
(iii) Find the critical path and the expected project completion time.
(iv) What is the probability of completing the project on or before 35 weeks?
18. The following table indicates the details of a project. The duration are in day “a” refers to
optimistic time, “m” refers to most likely time and “b” refers to pessimistic time duration.
[Nov/Dec 2017]
Duration(days)
Activity
a m b
1-2 2 4 5
1-3 3 4 6
1-4 4 5 6
2-4 8 9 11
2-5 6 8 12
3-4 2 3 4
4-5 2 5 7
i) Draw the network
ii) Find the critical path
iii) Determine the expected standard deviation of the completion time
19. The following indicates the details of a project. The durations are in days. ‘a’ refers to
optimistic time, ‘m’ refers to most likely time, and ‘b’ refers to pessimistic time duration
[Apr/May 2017]
 Panimalar Engineering College
Activity 1-2 1-3 1-4 2-4 2-5 3-4 4-5

a 2 3 4 8 6 2 2

m 4 4 5 9 8 3 5

b 5 6 6 11 12 4 7

(i) Draw the network

(ii) Find the critical path
(iii) Determine the expected standard deviation of the completion time
20. A project schedule has the following characteristics: [Apr/May 2017]
Activity 1-2 1-4 1-7 2-3 3-6 4-5 4-8 5-6 6-9 7-8 8-9

Duration 2 2 1 4 1 5 8 4 3 3 5

(i) Construct a PERT network and find the critical path and the project duration
(ii) Activities 2-3, 4-5, 6-9 each requires one unit of the same key equipment to complete it.
Do you think availability of one unit of the equipment in the organization is sufficient for
completing the project without delaying it, if so what is schedule of these activities
21. Draw the network from the following activity and find the critical path and total duration of the
project [Apr/May 2018]
Activity Immediate predecessor Duration(Months)
A - 3
B - 8
C A 9
D B 6
E C 10
F C 14
G C,D 11
H F,G 10
I E 5
J I 4
K H 1

22. A project has the following activities and other characteristics: Time estimate ( in weeks)
[Apr/May 2018]
Activity Immediate Duration(weeks)
predecessor Most Most Most
Optimistic(a) Likely(m) Pessimistic(b)
A - 4 7 16
B - 1 5 15
C A 6 12 30
D A 2 5 8
E C 5 11 17
F D 3 6 15
G B 3 9 27
H E,F 1 4 7
I G 4 19 28

Required:
 Panimalar Engineering College
i) Draw the PERT network diagram
ii) Identify the critical path
iii) Prepare the activity schedule for the project
iv) Determine the mean project completion time
v) Find the probability that the project is completed in 36 weeks
22. Find the shortest path.

23. Suppose it is desired to establish a cable communication network that links major cities, which
is shown in the figure. Determine how the cities are connected such that the total cable mileage
is minimized. (minimum spanning Tree)

24. Consider the following network and determine the amount of flow between the networks.

25. There are five jobs, each of which is to be processed through two machines 𝑀1 , 𝑀2 in the order
𝑀1 𝑀2 . Processing hours are as follows :
Job 1 2 3 4 5
𝑀1 3 8 5 7 4
𝑀2 4 10 6 5 8
Determine the optimum sequence for the five jobs, and minimum total elapsed time. Find also
the idle time of machines 𝑀1 and 𝑀2 .
 Panimalar Engineering College
26. Find the sequence that minimizes the total elapsed time required to complete the following tasks
on the machines in the order 1 − 2 − 3. Find also the minimum total elapsed time (hours) and
the idle times on the machines.
Task A B C D E F G
𝑀𝑎𝑐ℎ𝑖𝑛𝑒 1 3 8 7 4 9 8 7
𝑀𝑎𝑐ℎ𝑖𝑛𝑒 2 4 3 2 5 1 4 3
𝑀𝑎𝑐ℎ𝑖𝑛𝑒 3 6 7 5 11 5 6 12
27. Compute the minimum total elapsed time needed to process jobs 1 and 2 on five machines
𝑀1 , 𝑀2 , 𝑀3 , 𝑀4 and 𝑀5 given the following data :

Job 1 Sequence 𝑀1 𝑀2 𝑀3 𝑀4 𝑀5
Time(hrs) 2 3 4 6 2
Job 2 Sequence 𝑀3 𝑀1 𝑀4 𝑀5 𝑀2
Time(hrs) 4 5 3 2 6

UNIT – IV
QUEUEING MODELS
PART-A
1. Mention the characteristics of a queueing system.[June 2013,Dec 2014]
Queue length, arrival pattern, service pattern, waiting time, queue discipline, no. of servers,
customers’ behaviour, capacity of system, size of calling population, and number of servers.
2. List applications of queueing models [Dec 2010]. Identify few queueing systems [June
2011]
Sale of train tickets, patients waiting at doctor’s clinic, customers at bank, aircraft awaiting
landing, ships awaiting berthing, letters on a typist’s desk, etc.
3. What is queueing theory? What types of questions are sought to be answered in analyzing
a queueing system?
Queuing theory is concerned with analysis of situations where queueing occurs. It answers
questions regarding the size of the facility to accommodate waiting customers, time spent by
customers waiting in queue, number of service facilities to be provided, the order of offering
service to customers, etc.
4. List the components of a queueing system. [June 2010]
Calling population, arrivals, queue, service facility, departures.
5. What is meant by queue discipline?
‘Queue discipline’refers to the manner of choosing customers for providing service. Some
possibilities are: First-in-first-out (FIFO), Last-in-first-out (LIFO), First-in-last-out (FILO),
Service in random order (SIRO), etc.
6. What are the possible behaviors of customers in queueing theory?
Normal behavior, baulking, reneging, and jockeying.
7. What is meant by ‘jockeying’?
In multi-server queuing systems, the tendency of customers to switch between different queues
based on their perception of which queue is moving faster.
8. What is meant by ‘reneging’?
The tendency of a customer to leave a queue midway on the assumption that he is not likely to
get service in the available time or resource at the counter.
9. What is meant by ‘baulking’?
The tendency of a customer to avoid joining a queue for the same reasons mentioned under
‘reneging’.
10. What is meant by ‘queue length’?
The number of persons waiting in queue at any given point of time.
 Panimalar Engineering College
11. Explain Kendall’s notation for queueing models.[Dec 2013, June 2014]
The notation was developed by D.Kendall in 1953 to explain various possible types of queueing
situations. It is in the form (A/B/C): (D/E/F) where
A- arrival rate distribution D- Queue discipline
B- service rate distribution E- Maxm. no. of customers permitted in the system
C- number of servers F- Size of the calling source of customers.
12. Distinguish between transient and steady states in queueing theory.
Transient state: When the behaviour of the system is dependent on time. It usually occurs at the
early stages of operation of the system. Steady state: When the behaviour of the system becomes
independent of time.
13. Distinguish between jockeying and reneging. [June 2010]
In multi-server queuing systems, jockeying is the tendency of customers to switch between
different queues based on their perception of which queue is moving faster.Reneging is the
tendency of a customer to leave a queue midway on the assumption that he is not likely to get
service in the available time or resource at the counter.
14. Define simulation.
The representation of reality in some physical form or in some form of mathematical equations
may be called simulation.
15. What are the advantages of simulation?
(i) Less complicated mathematically.
(ii) Flexible.
(iii) Modified to suit the changing environments of the real situation.
(iv) Can be used for training purposes.
(v) May be less expensive in quite a few real-world situations.
16. What are the limitations of simulation?
(i) Quantification of the variables may be difficult.
(ii) Simulation may not be cheap always.
(iii) Simulation may not be less time consuming always.
(iv) Simulation may not yield optimum results.
(v) Large number of variables makes simulation unwieldy and more difficult.
17. Explain Monte-Carlo simulation.
Monte-Carlo technique involves the selection of random observations with in the simulation
model. It is constrained for application involving random numbers to solve deterministic and
stochastic problems. The underlying principle of this technique is
(i) Replace the actual statistical universe by another universe described by some assumed
probability distributions.
(ii) Sample from this theoretical population by means of random numbers.
18. What are the uses of simulation?
Simulation is used for solving :
(i) Inventory problems.
(ii) Queueing problems.
(iii) Training programmes.
PART-B
1. In a public telephone booth, arrivals are on the average of 15 per hour. An average call takes 3
minutes. If there is just one phone, find [i] the expected number of callers at the booth, [ii]
expected waiting time of a caller, and [iii] the proportion of the time the booth is busy.
2. Customers arrive at a one-window drive-in according to Poisson distribution with mean of 10
minutes. The service time per customer is exponential with mean of 6 minutes. Find [i] the
expected number of customers at the drive-in, [ii] the expected waiting time of a customer.
3. The city council of a small town has decided to build a tennis court in the central park. Players
are expected to arrive on the average of 10 sets of players per 12-hour day. Playing time is
 Panimalar Engineering College
exponentially distributed with a mean of 1 hour. What are the expected queueing statistics
assuming the basic single-server model?
4. Trucks at a single platform weigh-bridge arrive according to Poisson distribution. The time
required to weigh a truck follows exponential distribution. The mean arrival rate is 12 trucks per
day and mean service rate is 18 trucks per day. Determine
(i) the probability that there are o trucks in the system.
(ii) the average number of trucks waiting for service.
(iii) the average time a truck waits for weighing service to begin.
(iv) the probability that an arriving truck will have to wait for service.
5. In a railway marshalling yard, goods trains arrive at a rate of 30 trains per day. Assume
exponential distribution for inter-arrival time and service time of average 36 mins. Find the
average number of trains in the queue.
6. Customers arrive at a one-window drive-in bank according to a poisson distribution with mean
10 per hour. Service time per customer is exponential with mean 5 minutes. There are three
spaces in front of the window, including that for the car being serviced. Other arriving cars can
wait outside these three spaces.
i) What is the probability that an arriving customer can enter one of the three spaces in front
of the window?
ii) How long is an arriving customer expected to wait in the queue?
7. A petrol station has two pumps. The service time follows the exponential distribution with mean
6 minutes and cars arrive for service in a Poisson process at the rate of 14 cars per hour. Find
the probability that a customer has to wait for service. What is the average time of customers in
queue? [June 2014]
8. A Supermarket has two sales girls at the sales counters, if the service time for each customer is
exponential with a mean of 4 minutes and 16 people arrive in poison fashion at the rate of 10 an
hour, then calculate the:
i) Probability of having to wait for service
ii) Expected percentage of idle time for each sales girl
iii) If a customer has to wait, what is the expected length of his waiting line?(Dec 2014)
9. A TV repairman finds that the time he spent on his job has an exponential distribution with
mean 30 minutes. If he repairs the set in the order it arrives, and the arrival rate is approximately
Poisson, with an average rate of 10 per 8 hour day, what is the expected idle time of repairman
each day? How many jobs are ahead of average before the job just brought in?
10. A telephone exchange has two long distance operators. The telephone company finds that
during the peak load long distance calls arrive in a Poisson fashion at an average rate of 15 per
hour. The length of service on these calls is approximately distributed with mean 5 minutes.
1. What is the probability that subscriber will have to wait for his long distance call during
the peak hours of the day?
2. If the subscriber will wait and be serviced in turn, what is the expected waiting time in
queue?[June 2015]
11. Workers come to tool store room to receive special tools (required by them) for accomplishing
a particular project assigned to them. The average time between two arrivals is 60 seconds and
the arrivals are assumed to follow Poisson distribution. The average service time ( of the total
room attendant) is 40 seconds. Determine) average queue length, ii) average length of non-
empty items, iii) average number of workers in system including the worker being attended,
iv) mean waiting time of an arrival, v) average waiting time of an arrival (worker) who waits,
vi) the type of policy to be established. In other words, determine whether to go in for an
additional tool store room for the attendant which will minimize the combined cost of
attendants’ idle time and the cost of workers’ waiting time. The charge of a skilled worker is
Rs.50 per hour and that of store room attendant is Rs.20 per hour.[June 2013]
 Panimalar Engineering College
12. An automobile production line turns out about 100 cars a day, but deviations occur owing to
many cases. The production is more accurately described by the probability distribution given
below :

Production/day Probability
95 0.03
96 0.05
97 0.07
98 0.10
99 0.15
100 0.20
101 0.15
102 0.10
103 0.07
104 0.05
105 0.03
1.00
Finished cars are transported across the bay at the end of each day by ferry. If the ferry has
space for only 101 cars, what will be the average number of cars waiting to be shipped
and what will be the average number of empty spaces on the ship?

UNIT-5
DECISION MODELS
PART-A
1. What is Game theory?
A mathematical analysis of competitive situations involving two or more participants where the
outcomes are affected by the actions of a participant as well as those of others.
2. Define the term ‘Game’.
An activity between two or more players involving actions by each one of them (according to a
set of rules) that results in some gain (positive, negative or zero) for each.
3. What is two-person zero-sum game?[Dec 2014]
A game of two players in which the gains of one player are equal to the losses of the other.
4. What is Payoff Matrix?
A table showing the gains/losses to the player on the left hand side against various courses of
action employed by both players in a two-person zero-sum game.
5. What is Maximin principle?
The principle maximizes the minimum guaranteed gains of Player A with respect to different
alternatives of A, irrespective of B’s alternatives.
6. What is Minimax principle?
The principle minimizes the maximum possible losses of Player B with respect to different
alternatives of B, irrespective of A’s alternatives.
7. Define the term ‘Strategy’.
The predetermined rule by which a player decides his course of action.
8. What is Pure Strategy?
If a player selects a particular course of action alone, ignoring his remaining alternatives, then
the chosen course of action is known as Pure Strategy.
 Panimalar Engineering College
9. What is Mixed Strategy? [June 2010]
If a player employs more than one course of action, then the player is said to follow a Mixed
Strategy.
10. What is Saddle Point? [June 2011, June 2012,June 2013, June 2014, Dec 2014]
In a game, if the maximin value is equal to the minimax value, then the game has a saddle point.
The intersecting cell corresponding to these values is the saddle point. If the game has a saddle
point, then each player adopts a pure strategy.
11. What is Value of a game?
It is the expected pay-off of play when all the players of the game follow their optimal
strategies.
12. State the conditions for applying graphical solutions to gaming. [June2013]
Conditions for applying graphical solutions to gaming are nx2 or 2xn matrix.
13. What is dominance property in Game Theory? [Apr 2011]
In some games, it is possible to reduce the size of the payoff matrix by eliminating redundant
rows or columns because one of the pure strategies of either player is inferior to at least one of
the remaining ones. The superior strategies are said to dominate the inferior ones.
14. Define zero sum game. [Dec 2010]
A game in which the sum of payments to all players that win is exactly equal to the loss of
players that lose,e.g. two candidates fighting an election.
15. Indicate the differences between linear programming and integer programming
problem.[Dec 2013]
In linear programming, decision variables are non-negative values which are restricted to be
zero or more than zero which can be also a fractional value.
Problems associated with simply rounding off linear programming solutions is dealt with
Integer programming problem.
16. State any 2 applications of game theory, preferably from management field.[Dec 2013]
Firms struggling to maintain the market shares
Launching advertisement campaigns by companies marketing competing product
17. Differentiate between pure and mixed strategies. [June 2015]
Pure strategy is a pre-determined plan of action based on which games are played which does
not change during the game. Mixed strategy is a case when the strategy gets changed while the
game is in progress.
19. What is the Replacement Problem?
It deals with situations where an item needs to be replaced either due to decreased efficiency or
due to breakdown. The idea is to determine the optimal policy that results in the lowest overall
minimum cost of replacing the item.
20. What are the two broad types of replacement models?
Models for items that deteriorate over time, and models for items that fail suddenly.
21. Explain the replacement policy for items that deteriorate over time.
When items such as equipment, vehicles, etc. deteriorate over time, the maintenance costs
progressively become larger and larger, making it uneconomical to maintain the item over an
indefinite period. Hence the objective is to determine the optimal age of the equipment (from
the overall cost point of view) at which it should be replaced.
22. What is meant by group replacement policy? [June 2010, June 2012, June 2014]
For items that fail suddenly, the cost of system breakdown may be disproportionate to the value
of the failed item. Moreover, group replacement may be cheaper than individual replacement.
These two aspects are considered in this type of replacement policy.
23. Distinguish between individual replacement and group replacement. [June 2010]
 Panimalar Engineering College
For items that fail suddenly, individual replacement is the policy of replacing individual items
as and when they fail. Group replacement is the policy of replacing the entire lot of items at
fixed intervals, and in addition, replacing individual items as and when they fail.
24. What is meant by Present Worth Factor?
Present Worth Factor (PWF) is the present value of one rupee spent n years from now. It is
equal to (1+r)-n where r is the rate of interest.
25. What is the significance of ‘r’ in a replacement model? [Dec 2010, June 2011]
The ‘r’ stands for the rate of interest, which in turn determines the discount rate [1/(1+r)] used
for calculating the present value of future expenditures on the maintenance and running of
machinery/equipment.
26. What are the two replacement policies considered in group replacement
models?(June2013)
Individual replacement or group replacement.
27. Why do equipments need replacement?[Dec 2013]
Decline in the value of the service rendered by the equipment , increased operating cost of the
equipment, increased maintenance cost of the equipment or a combination of these costs makes
uneconomical to continue production with the same equipment. Hence the equipments are to be
periodically replaced.
28. Define Economic Life of Equipment.[Dec 2014]
Economic Life can be simply defined as the period of time during which a fixed asset
competitively produces a good or service of value.
29. In a store with one cashier, nine customers arrive on the average of every five minutes and
the cashier can serve them ten in five minutes. Find utilization factor.[June 2015]
Arrival rate λ = 108 per hour, Service rate µ = 120 per hour, Utilization Factor 𝜌 = λ/ µ = 0.9
30. If the money carries an interest rate of 10% per year, what will be the value of one rupee
after two years?(June 2015)
Value of one rupee after 2 years = (1 + 𝑟)𝑛 = (1 + 0.1)2 = Rs 1.21
PART-B
1. Players A and B play a game in which each player has three coins (25p, 50p and 100p). Each of
them selects a coin without the knowledge of the other. If the sum of the two coin values is an
even number, A wins B’s coin. If that sum is an odd number, B wins A’s coin.
[i] Develop a payoff matrix with respect to player A.
[ii] Find the optimal strategies for the two players and the value of the game. [June 2010]
2. Solve the following 2 X n game by the method of sub-games: [June 2010]
Player B

B1 B2 B3

A1 1 3 11
Player A
A2 8 5 2

3. Reduce the following game by dominance and find the game value. [Dec 2012]
Player B
I II III IV
I 3 2 4 0
II 3 4 2 4
Player A III 4 2 4 0
IV 0 4 0 8
 Panimalar Engineering College
4. Solve the game whose payoff matrix is given below: [Dec 2010]
Player B

B1 B2 B3 B4

A1 5 -10 9 0
Player A A2 6 7 8 1

A3 8 7 15 2

A4 3 4 -1 4

5. Use the dominance rule to reduce the following game to either 2 x n or m x 2 game and then
solve it graphically. [June 2011]
Player B

B1 B2 B3 B4

A1 19 6 7 5
Player A A2 7 3 14 6

A3 12 8 18 4

A4 8 7 13 -1

6. Reduce the following game by dominance and find the game value.[June 2013]
Player B
I II III IV
I 3 2 4 0
Player A II 3 4 2 4
III 4 2 4 0
IV 0 4 0 8
7. Solve the following game;[June 2014]
Player B

3 -2 4
Player A -1 4 2

2 2 6

8. Solve the following game by LP method.[Dec 2014]

Player B

1 -1 -1

Player A -1 -1 3

-1 2 -1
 Panimalar Engineering College
9. i)State the rules of dominance
ii) Solve the following game [June 2015]
Player B
1 7 2
Player A 6 2 7
5 1 6
10. An establishment has an installation of 1,000 bulbs of a certain type. Failure rates based on past
data are as follows:

End of week 𝑖 1 2 3 4 5
Probability of failure
0.10 0.15 0.25 0.20 0.30
during ‘𝑖’th week
Cost of replacement an individual bulb is Rs.3, but if the entire lot is replaced, it costs Re.1 per
bulb. The entire lot is replaced at fixed intervals and individual bulbs as and when they fail.
Determine the optimal replacement policy.
11. A machine costs Rs.5,000. The maintenance cost of nth year is given by 𝐶𝑛 = 500(𝑛 − 1). If
money is worth 5% per year, after how many years will it be economical to replace machine?
12. The cost of a machine is Rs.16,100 and its scrap value is Rs.1,100. The maintenance costs are:
Year 1 2 3 4 5 6 7 8

Maintenance
300 450 600 800 1000 1200 1500 2000
cost (Rs.)

When should the machine be replaced? [June 2010]

13. The probability 𝑃𝑛 of failure just before age ‘𝑛’ (in months) is shown below for 1000 bulbs. If
the individual replacement cost is Re.1 and the group replacement cost is Rs.0.3 per item, find
the optimal replacement policy.[Dec 2010]
𝑛 1 2 3 4 5

𝑃𝑛 0.3 0.1 0.1 0.2 0.3

14. A desktop publisher finds from his previous records that the cost per year of using an ink-jet
printer whose purchase price is Rs.7000 is as given below:

Year 1 2 3 4 5 6 7 8

Running 1100 1300 1500 1900 2400 2900 3500 4100

cost (Rs.)

Resale Price 3100 1600 850 475 300 300 300 300
(Rs.)

At what age the ink-jet printer should be replaced?[June 2013]

15. The following failure rates have been observed for a certain type of light bulbs;
End of week 1 2 3 4 5 6 7

Probability of
0.05 0.13 0.25 0.43 0.68 0.88 0.96
failure of date

The cost of replacing an individual failed bulb is Rs.12.50. The cost of group replacement is
Rs.3 per bulb. Determine whether individual replacement or group replacement is best suited for
this situation.[June 2014]
 Panimalar Engineering College
16. The cost of machine is Rs.6100 and its scrap value is Rs.100. The maintenance cost from
experience as follows :
Year 1 2 3 4 5 6 7 8

Maintenance 100 250 400 600 900 1200 1600 1800

When should machine be replaced? [Dec 2014]

17. A machine costs Rs.15,000 and running costs for different years are given. Find optimum
replacement period if capital is worth 10% and machine has no salvage value. [June 2015]
Year 1 2 3 4 5 6 7

Running Cost Rs. 2500 3000 4000 5000 6500 8000 10000