Resource Management Techniques
Resource Management Techniques
Resource Management Techniques
Dr. M. GOPIKRISHNAN
PROFESSOR
Department of Computer Science and
Engineering
ANNA UNIVERSITY, CHENNAI-25
SYLLABUS COPY
REGULATION 2013
CS6704 RESOURCE MANAGEMENT TECHNIQUES LTPC 3 00 3
OBJECTIVES:
The student should be made to:
Be familiar with resource management techniques.
Learn to solve problems in linear programming and Integer programming.
Be exposed to CPM and PERT.
UNIT I LINEAR PROGRAMMING 9
Principal components of decision problem – Modeling phases – LP Formulation and graphic
solution – Resource allocation problems – Simplex method – Sensitivity analysis.
1
DETAILED LESSON PLAN
TEXT BOOK:
1. H.A. Taha, “Operation Research”, Prentice Hall of India, 2002.
REFERENCES:
1. Paneer Selvam, „Operations Research‟, Prentice Hall of India, 2002
2. Anderson „Quantitative Methods for Business‟, 8th Edition, Thomson Learning,
2002.
3. Winston „Operation Research‟, Thomson Learning, 2003.
4. Vohra, „Quantitative Techniques in Management‟, Tata Mc Graw Hill, 2002.
5. Anand Sarma, „Operation Research‟, Himalaya Publishing House, 2003.
Hours
Cumulative Books
Sl. No Unit Topic / Portions to be Covered Required /
Hrs Referred
Planned
UNIT I - LINEAR PROGRAMMING
1 1 Linear Programming - Introduction 1 1 TB1
Principal components of decision
2 1 1 2 TB1
problem
3 1 Modeling phases 1 3 TB1
11 2 Primal 1 11 TB1
2
Hours
Cumulative Books
Sl. No Unit Topic / Portions to be Covered Required /
Hrs Referred
Planned
3
Hours
Cumulative Books
Sl. No Unit Topic / Portions to be Covered Required /
Hrs Referred
Planned
34 Kuhn 1 34 TB1
4
35 4 Tucker conditions 1 35 TB1
40 5 PERT 1 43 TB1
4
UNIT-I – LINEAR PROGRAMMING
Principal components of decision problem – Modeling phases – LP Formulation and
graphic solution – Resource allocation problems – Simplex method – Sensitivity
analysis.
PART-A
1. What is linear programming?
Linear programming is a technique used for determining optimum utilization of
limited resources to meet out the given objectives. The objective is to maximize the profit
or minimize the resources(men, machine, materials and money).
3. A firm manufactures two types of product A and B and sells them at profit of Rs2
on type A and Rs3 on type B. Each products is processed on two machines M1 and
M2.Type A requires 1 minute of processing time onM1 and 2 minutes on M2 Type
B requires 1 minute of processing time on M1 and 1 minute on M2.Machine M1 is
available for not more than 6 hours 40 minutes while machine M2 is available for
10 hours during working day. Formulate the problem as a LPP so as to maximize
the profit.
Maximize z= 2 x1+3x2.
Subject to the constraints:
x1+x2 <=400
2x1+x2<=600
x1,x2 >=0
5
4. Define feasible solution.
Any Solution to a LPP which satisfies the non negativity restrictions of LPP‟s
called the feasible solution.
6
9.Define basic solution.
Given a system of m linear equations with n variables(m<n).The solution obtained
by setting(n-m) variables equal to zero and solving for the remaining m variables is called
abasic solution.
7
13. What is sensitivity analysis? What does it signify? What is the purpose of
sensitivity analysis?
After formulating mathematic model to linear programming problems and then
attaining the optimal solution of the problem, it may be required to study the effect of
changes in the different parameters of the problem,on the optimum solution, that is it may
be desirable to see the sensitiveness of the feasible optimal solution corresponding to the
variations in the parameters. The investigations that deal with changes in the optimal
solutions due to discrete variations in the parameters aij,bj and cj are called sensitivity
analysis.The purpose of sensitivity analysis is to find, how to preserve , to a minimum
,the additional computational efforts which arise in solving the problem as a new one.
8
PART B
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
UNIT-II – DUALITY AND NETWORKS
PART-A
1.What are the methods used in transportation problem to obtain the initial basic
feasible solution.
North-west corner rule
Lowest cost entry method
Vogel‟s approximation method.
3. Define unbounded assignment problem and describe the steps involved in solving
it?
If the number of rows is not equal to the number of column in the given cost
matrix the problem is said to be unbalanced. It is converted to a balanced one by adding
the dummy row or dummy column with zero cost.
7. Explain the steps in the Hungarian method used for solving assignment problems.
Step1: Subtract the smallest cost element of each row from all the elements in the
row of the given cost matrix.
Step2: Subtract the smallest cost element of each column from all the elements in
the column of the resulting cost matrix obtained by step1.
Step3:Assigning zeros
Step4:Apply optimal test
Step5:Cover all the zeros by drawing a minimum number of straight lines.
Step 6: Determine the smallest cost element not covered by the straight
lines.Subtract this smallest cost element from all the uncovered elements and add
55
this to all those element which are lying in the intersection of these straight lines
and do not change the remaining elements which lie on the straight lines.
Step 7: Repeat step (1) to (6),until optimum assignment is attained.
And 𝑥𝑖𝑗 =0 or 1.
56
(D) minimize b T y
subject to AT y ≥ c, 0 ≤ y.
13. What is the difference between regular simplex method and dual simplex
method?
The Simplex method will be the basic technique, exactly where linear
programming techniques are usually derived. Within dual simplex the first
schedule will be primal infeasible, due to the fact some all RHS tend to be non
positive.
In simplex method our aim is to find optimality condition using feasibility
condition.But in dual method we are trying to achieve feasibility condition using
optimality condition.
57
14. What do you mean by shadow prices?
Shadow prices are the estimated price of a good or service for which no market
price exists.
58
PART-B
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
UNIT-III – INTEGER PROGRAMMING
Cutting plan algorithm – Branch and bound methods, Multistage (Dynamic)
programming.
PART A
1. What is integer programming? What are the types?
A linear programming problem in which some or all of the variables in the optimal
solution are restricted to assume non-negative integer values is called an integer
programming problem or integer linear programming.
Types : Mixed IPP,Pure IPP
135
𝟐
4. Write down the Gomory’s fractional cut corresponding to the equation 𝐱 𝟏 + 𝟑 𝐱 𝟑 −
𝟏 −𝟐
x = That appears in the non-integer optimal simplex table of an integer
𝟑 4 𝟑
programming problem.
−2 2 −2
x3 − x4 + s1 =
3 3 3
136
It is used to determine the optimal combination of advertising media (TV, Radio,
Newspapers) and frequency of advertising.
It can be used in replacement theory to determine at which age the equipment is to be
replaced for optimal return from the facilities.
Spare part level determination to guarantee high efficiency utilization of expensive
equipment.
11. Why not round off the optimum values instead of resorting to IP? (MAY ’08)
There is no guarantee that the integer valued solution (obtained by simplex method)
will satisfy the constraints. i.e. ., it may not satisfy one or more constraints and as such
the new solution may not feasible. So there is a need for developing a systematic and
efficient algorithm for obtaining the exact optimum integer solution to an IPP.
137
13. What is cutting method?
A systematic procedure for solving pure IPP was first developed by R.E.Gomory
in 1958. Later on, he extended the procedure to solve mixed IPP, named as cutting plane
algorithm, the method consists in first solving the IPP as ordinary LPP.By ignoring the
integrity restriction and then introducing additional constraints one after the other to cut
certain part of the solution space until an integral solution is obtained.
138
16. A manufacturer of baby dolls makes two types of dolls, doll X and doll Y.
Processing of these dolls is done on two machines A and B. Doll X requires 2 hours
on machine A and 6 hours on Machine B. Doll Y requires 5 hours on machine A and
5 hours on Machine B. There are 16 hours of time per day available on machine A
and 30 hours on machine B. The profit is gained on both the dolls is same. Format
this as IPP?
Let the manufacturer decide to manufacture x1 the number of doll X
and x2 number of doll Y so as to maximize the profit. The complete
formulation of the IPP is given by
Maximize Z = x1+x2
Subject to 2 x1 + 5 x2 ≤16
6 x1+ 5 x2 ≤30
and ≥0 and are integers.
139
PART-B
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
UNIT-IV – CLASSICAL OPTIMISATION THEORY
PART-A
1. Write down the sufficient condition for the Extrema?
A sufficient condition for a stationary point 𝑋0 to be extremum is that the Hessian
matrix H evaluated at is
i) Positive definite when 𝑋0 is a minimum point.
ii) Negative definite when 𝑋0 is a maximum point
171
6. What is the order of Convergence for fixed point iteration?
The Convergence is linear and the convergence is of order 1.
c.∅𝑖 𝑔𝑖 (X1,X2,…Xn)=0,i=1,2,…m
d. 𝑔𝑖 (X1,X2,…Xn)≤ 0,i=1,2,…m
172
PART B
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
UNIT-V – OBJECT SCHEDULING
Network diagram representation – Critical path method – Time charts and resource
levelling – PERT.
PART-A
1. Define project. What are the three main phases of project
A project is defined as a combination of interrelated activities,all of which must be
executed in a certain order to achieve a set of goal.
Phases of project: Planning, Scheduling and Control
3.What are the two basic planning and controlling techniques in a network analysis?
Critical Path Method (CPM)
Programme Evaluation and Review Technique (PERT)
196
cases rule of thumb is insufficient. It must be combined with other rules to take into
additional factors or exceptional circumstances. A collection of such rules for solving a
particular problem is called a heuristic program,
7.What are the two main costs for a project? Illustrate with examples.
Direct costs are the costs directly associated with each activity such as machine
costs, labour costs etc for each activity.
Indirect costs are the costs due to management services ,rentals, insurance
including allocation of fixed expenses, cost of security etc.
197
duration were known with certainty.
2.PERT is usually used for projects in 2.CPM is used for projects involving
which time estimates are uncertain. well known activities of repetitive in
Example: R &D activities which are nature.
usually non-repetitive.
3.Emphasis is given to important stages 3.CPM is suited to establish a trade off
of completion of task rather than the for optimum balancing between
activities required to be performed to schedule time and cost of the project.
reach a particular event or task in the
analysis of network ie.,PERT network
is essentially an event-oriented network.
4.PERT is Probabilistic 4.CPM is Deterministic
10. What is the formula to compute the cost slope for each activity?
Cost slope = (Crash cost-Normal cost)/(Normal duration-Crash duration)
199
PART-B
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
Question Paper Code: 80307
PART B – (5 * 16 = 80 Marks )
217
𝟖𝒙𝟏 + 𝟐𝒙𝟐 ≤ 𝟏6
𝟑𝒙𝟏 − 𝟐𝒙𝟐 ≥ 𝟔
and 𝒙𝟏 , 𝒙𝟐 ≥ 𝟎
(OR)
B) Solve the following LPP by simplex method. (Pg. No. 42) (16)
𝐌𝐚𝐱 𝒁 = 𝟒𝒙𝟏 + 𝒙𝟐 + 𝟑𝒙𝟑 + 𝟓𝒙𝟒
Subject to 𝟒𝒙𝟏 − 𝟔𝒙𝟐 − 𝟓𝒙𝟑 + 𝟒𝒙𝟒 ≥ −𝟐𝟎
𝟑𝒙𝟏 − 𝟐𝒙𝟐 + 𝟒𝒙𝟑 + 𝒙𝟒 ≤ 𝟏0
8𝒙𝟏 − 𝟑𝒙𝟐 + 𝟑𝒙𝟑 + 𝟐𝒙𝟒 ≤ 𝟐0
𝒙𝟏 , 𝒙𝟐, 𝒙𝟑, 𝒙𝟒, ≥ 𝟎
12. A) Using dual simplex method solves the LPP. (Pg. No. 75) (16)
𝐌𝐚𝐱 𝒁 = − 𝟑𝒙𝟏 − 𝟐𝒙𝟐
Subject to
𝒙𝟏 + 𝒙𝟐 ≥ 𝟏
𝒙𝟏 + 𝒙𝟐 ≤ 7
𝒙𝟏 + 𝟐𝒙𝟐 ≥ 𝟏𝟎
𝒙𝟐 ≤ 3
and 𝒙𝟏 , 𝒙𝟐 ≥ 𝟎
(OR)
B) Consider the problem of assigning four sales persons to four
different sales regions as shown in the following table such that the
total sales is maximized. (Pg. No. 129) (16)
Sales Region
1 2 3 4
1 10 22 12 14
Salesman 2 16 18 22 10
3 24 20 12 18
4 16 14 24 20
The cell entries represent annual sales figures in lakhs of rupees. Find
the optimal allocation of the sales persons to different regions.
218
13. A) Solve the following LPP. (Pg. No. 160) (16)
Minimize 𝐙 = −𝟐𝒙𝟏 − 𝟑𝒙𝟐
Subject to 𝟐𝒙𝟏 + 𝟐𝒙𝟐 ≤ 𝟕
𝒙𝟏 ≤ 𝟐
𝒙𝟐 ≤ 𝟐 and 𝒙𝟏 , 𝒙𝟐 ≥ 𝟎 are Integer
(OR)
(OR)
219
B) Solve the non-linear programming problem by Khun-Tucker
conditions. (Pg. No. 194) (16)
Minimize f(x) = 𝒙𝟐𝟏 + 𝒙𝟐𝟐 + 𝒙𝟐𝟑
Subject to 𝒈𝟏 𝒙 = 𝟐𝒙𝟏 + 𝒙𝟐 − 𝟓 ≤ 𝟎
𝒈𝟐 𝒙 = 𝒙𝟏 + 𝒙𝟐 − 𝟐 ≤ 𝟎
𝒈𝟑 𝒙 = 𝟏 − 𝒙𝟏 ≤ 𝟎
𝒈𝟒 𝒙 = 𝟐 − 𝒙𝟐 ≤ 𝟎
𝒈𝟓 𝒙 = −𝒙𝟑 ≤ 𝟎
(OR)
220
B) Consider the data of a project summarized in the following table:
(Pg. No. 205)
B 1 2 3
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 5
J K, G 6 7 8
________________________
221
Question Paper Code: 71693
222
PART B – (5 * 16 = 80 marks )
(OR)
12. A) Using dual simplex method solves the LPP. (Pg. No. 69) (16)
Minimize Z =2x1+x2
Subject to
3x1+x2 ≥3
4x1+3x2 ≥ 6
x1+2x2 ≥ 3
and x1,x2 ≥ 0
(OR)
B) Solve the transportation problem: (Pg. No. 103) (16)
1 2 3 4 Supply
I 21 16 25 13 11
II 17 18 14 23 13
III 32 27 18 41 19
Demand 6 10 12 15
223
13. A) Find the optimum integer solution to the following linear
programming problem: (Pg. No. 144) (16)
Minimize 𝐙 = 𝒙𝟏 + 𝟐𝒙𝟐
Subject to 𝟐𝒙𝟐 ≤ 𝟕
𝒙𝟏 + 𝒙𝟐 ≤ 𝟕
𝟐𝒙𝟏 = 𝟏𝟏
and 𝒙𝟏 , 𝒙𝟐 ≥ 𝟎 are Integer
(OR)
B) Use branch and bound method to solve the following: (Pg. No. 165)
(16)
Maximize 𝐙 = 𝟐𝒙𝟏 + 𝟐𝒙𝟐
Subject to 𝟓𝒙𝟏 + 𝟑𝒙𝟐 ≤ 𝟖
𝒙𝟏 + 𝟐𝒙𝟐 ≤ 𝟒.
And𝒙𝟏 , 𝒙𝟐 ≥ 𝟎 are Integer
(OR)
B) Solve the non linear programming problem by Lagrangian
multiplier method. (Pg. No. 183) (16)
Minimize Z = 𝒙𝟐𝟏 + 𝟑𝒙𝟐𝟐 + 𝟓𝒙𝟐𝟑
Subject to 𝒙𝟏 + 𝒙𝟐 + 𝟑𝒙𝟑 = 𝟐
𝟓𝒙𝟏 + 𝟐𝒙𝟐 + 𝒙𝟑 = 𝟓
𝒙𝟏 , 𝒙𝟐 , 𝒙𝟑 ≥ 𝟎
224
15. A) 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. (Pg. No. 205)
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 the schedule of these activities? (16)
___________________________
225