88

GRT INSTITUTE OF ENGINEERING AND TECHNOLOGY

DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

CS6704 RESOURCE MANAGEMENT TECHNIQUES LTPC3003

UNIT I LINEAR PROGRAMMING 9

Principal components of decision problem – Modeling phases – LP Formulation and

graphic solution – Resource allocation problems – Simplex method – Sensitivity analysis.

UNIT II DUALITY AND NETWORKS 9

Definition of dual problem – Primal – Dual relationships – Dual simplex methods –

Post optimality analysis – Transportation and assignment model - Shortest route problem.

UNIT III INTEGER PROGRAMMING 9

Cutting plan algorithm – Branch and bound methods, Multistage (Dynamic)

programming.

UNIT IV CLASSICAL OPTIMISATION THEORY 9

Unconstrained external problems, Newton – Ralphson method – Equality constraints

– Jacobean methods – Lagrangian method – Kuhn – Tucker conditions – Simple problems.

UNIT V OBJECT SCHEDULING: 9

Network diagram representation – Critical path method – Time charts and resource
leveling – PERT.

TOTAL: 45 PERIODS

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.

CS6704 RESOURCE MANAGEMENT TECHNIQUES

 89
GRT INSTITUTE OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

UNIT-I LINEAR PROGRAMMING

PART-A

1. What are the various types of models?

 Iconic (or) physical models
 Analogue (or) schematic models
 Symbolic (or) mathematical models.

2. What is an analogue model?

Analogue model can represent dynamic situation. They are analogues to the characteristic
of the system under study. They use one set of properties to represent some other set of
properties of the system. After the model is solved the solution is reinterpreted in terms of the
original system.

3. What is an iconic model?

Iconic model are the pictorial representation of real systems and have the appearance of
the real structure. Examples such models are city maps, houses, blue prints etc.

4. Name some characteristics of a good model.

 It should be simple and coherent.
 It is should be open to parametric type of treatment.
 There should be less number of variable.
 Assumption made in the model should be clearly mentioned and should be as small
as possible.

5. Explain the principles of modeling?

 Models should be validated prior to implementation.
 Models are only aids in decision making.
 Models should not be complicated. They should be as simple as possible.
 Models should be accurate as possible.

6. What do you mean by a general LPP?

The general LPP is given by

CS6704 RESOURCE MANAGEMENT TECHNIQUES

 90
GRT INSTITUTE OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

(1) is called the objective function.

(2) is the constraints
(3) is called non-negativity constraints.

7. Define a feasible region?

A region in which all the constraints are satisfied simultaneously is called a feasible region.

8. Define a feasible solution.

Any solution to a LPP which satisfies the non-negativity restrictions of the LPP is called the
feasible solutions.

9. What is a redundant constraint?

A constraint that does not from boundary of feasible region and has impact on the solution
of the problem, remodel of which does not alter the solution is called redundant constraints.

10. Define optimal solution.

Any feasible solution which optimizes [minimizes (or) maximizes] the objective function
is called its optimal solution.

11. Define basic solution.

Given a system of m linear equations with n variables, any solution which is obtained by
solving for ‘m’ variables keeping the remaining (n-m) variables as zero is called a basic
solution.

12. Define degenerate solution.

A basic feasible solution is said to be degenerate if one or more basic variables are zero.

13. Define unbounded solutions.

If the value of the objective function Z can be increased (or) decreased indefinitely such
solutions are called unbounded solutions.

14. What do you mean by canonical form of a LPP?

In canonical if the objective functions is of maximization, then all the constraints other
than non negativity conditions are type. Similarly if the objective function is of
minimization then all the constraints are type.

15. What are the slack and surplus variables?

The non negative variable which is added to LHS of the constraints to convert the

inequality into an equation is called slack variables . Where are called

slack variable

CS6704 RESOURCE MANAGEMENT TECHNIQUES

 91
GRT INSTITUTE OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

The non negative variable which is subtracted to LHS of the constraints to convert the

inequality into an equation is called surplus variables . Where are called

surplus variable

16. What is key column and key row?

 Key column is the column which gives the entering variable column
 Key row is the row which gives the leaving variable row.

17. What are the methods used to solve an LPP involving artificial variables.
 Big M-method (or) penalty cost method
 Two phase simplex method

18. Define artificial variables.

Any non-negative variable which is introduced in the constraint in order to get the
initial basic feasible solution is called artificial variable.

19. When does an LPP possess a pseudo optimal solution?

An LPP possess a Pseudo-optimal solution if at least one artificial variable is in the basis
at positive level even though the optimal conditions are satisfied.

20. What is degeneracy?

The concept of obtaining a degenerate basic feasible solution in a LPP is known as
degeneracy.

UNIT-II DUALITY AND NETWORKS

PART-A
1. What dual of LPP.
For every LPP there is a unique LPP associate with it involving the same data and closely
related optimal solution. The original problem is then called the primal problem while the
other is called its dual problem.

2. What are the advantages of duality?

 If primal contains a large number of constraints and a smaller number of variables,
then the process Of computations can be considerably reduced by converting it into
the dual problem.
 Since the optimal solution to the objective function is the same for both primal and
dual, a dual solution can be used to check the accuracy of the primal solution.

3. State the feasibility condition in dual simplex method.

CS6704 RESOURCE MANAGEMENT TECHNIQUES

 92
GRT INSTITUTE OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

In dual simplex method in finding the variable which enters the basis we find
. If there is no ratio with negative denominator then the procedure
does not have a feasible solution.

4. Find the dual of the following LPP.

5. Write the dual of the following primal LPP

6. What do you understand by transportation problem?

We transport a commodity from the source to a destination in such a way that the total
transportation cost is minimum.

7. Test any 3 approaches used with transportation problem for determining the stating
solution.
 North-West corner rule
 Least cost method(matrix minima)
 Vogel’s approximation method

8. Define balanced transportation problem?

Any transportation problem is said to be balanced if

(i.e) If the total supply = total demand

9. What do you mean by degeneracy in transportation problem?

If the number of occupied cells in a transportation is less than then it is
called a degenerate in transportation.

10. How do you convert an unbalanced transportation problem into a balanced one?
The unbalanced transportation can be converted into a balanced on by adding a dummy
row with cost zero and the excess demand is interred as a rim requirement if total supply is

CS6704 RESOURCE MANAGEMENT TECHNIQUES

 93
GRT INSTITUTE OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

less than total demand. On the other hand if the total supply is greater than total demand we
introduced a dummy column with cost zero and the excess supply is entered as a rim
requirement for the dummy destination.

11. Define unbalanced Transportation problem?

Any Transportation problem is said to be unbalanced if

12. What is an Assignment problem?

The problem of assigning the number of jobs to equal number of facilities (machines or
persons or destination) at a minimum cost or maximum profit is called an Assignment
problem.

13. Give two applications of Assignment problem?

 If ‘n’ jobs have to be assigned to ‘n’ workers or machines with unit time of
performing the job we can use assignment model to get minimum cost.
 Travelling salesman problem. (Ie) a salesman has to visit a number of cities not
visiting the same city twice and return to the starting place.

14. Define balanced Assignment problem?

If the number of rows is equal to the number of column in the cost matrix of the
Assignment problem is called an Assignment problem.

15. State the difference between Transportation and Assignment problem?

Transportation problem Assignment problem

1. The cost matrix is not necessarily a square The cost matrix is must be square matrix
matrix

2. Supply and demand at any source at any Supply and demand at any source at any
destination may be positive quantity destination will be 1

[Link] allocation can take any positive will be take only two possible values 1
values satisfies the rim requirements. or 0

16. When is an Assignment problem said to be unbalanced?

If the cost matrix or profit matrix is not a square matrix then the problem is said to be
unbalanced Assignment problem.

17. Write the mathematical formulation of Assignment problem?

CS6704 RESOURCE MANAGEMENT TECHNIQUES

 94
GRT INSTITUTE OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

The Assignment problem can be expressed as

is the cost of assigning machine to the job subject to

UNIT-III INTEGER PROGRAMMING

PART-A

1. What do you mean by integer programming problem?

An LPP 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.

2. Define a pure integer programming problem?

In a LPP if all the variables in the optimal solution are restricted to assume non negative
integer values, then it is called a pure integer programming problem.

3. Define mixed integer programming problem?

In an LPP if only some of the variables in the optimal solution are restricted to assume non
negative integer values while the remaining variables are free to take any non negative values
then it is called a mixed integer programming problem.

4. Differentiable between pure and mixed integer programming problem?

In a pure IPP all the variables in the optimal solution are restricted to non negative integer
values where as the mixed integer programming problem only some of the variable in the
optimal solution are restricted to assumed non negative integer values.

5. Give some applications of integer programming problem?

 In product mix problem
 Sequencing and routing problem
 All allocations problem involving the allocation of goods, men and machines.
6. What are the methods used in solving Integer programming problem?
There are 2 methods , namely
 Cutting method (Gomary’s cutting plane algorithm)
 Search method (Branch and Bound technique)

7. Explain Gomarian constraint or fractional cut constraint.

A new constraint introduced to the problem such that the new set of feasible solution
includes all the original feasible integer solutions but does not include the optimum non

CS6704 RESOURCE MANAGEMENT TECHNIQUES

 95
GRT INSTITUTE OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

integer solution initially found. This new constraint is called fractional cut or Gomarian’s
constraint

8. Where is Branch and Bound method used?

This method is an enumeration method which is used when all the feasible integer points
are not enumerated.

9. What is the fractional part of the negative number ?

The fractional part of the negative number is given by . The number can be

expressed as

10. What is the fractional part of ?

The fractional part can be expressed as . The fractional part of .

11. Explain the importance of Integer programming problem?

All the decision variables were allowed to take any non negative real values as it is quite
possible and appropriate, to have fractional values in many solutions and which are
meaningless in the content of the actual decision problem. This is the main reason why IPP is
so important for marginal decisions.

12. What is dynamic programming?

Many decisions making problems involve a process that takes place in multiple stages in
such a way that at each stage, the process is dependent on the strategy chosen. Such types of
problems are called dynamic programming problem.

13. Define the following terms in dynamic programming: Stage, State, State variables.
STAGE: Stage may be defined as the portion of the problem that possesses a set of
mutually exclusive alternatives from which the best alternatives is to be selected.
STATE: States are various possible conditions of the system at a stage of the problem.
STATE VARIABLE: The current situation of the system at a stage is described by a set
of variable called state variables.

14. Give a few applications of dynamic programming problem.

 It is used to determine the optimal combinations of adverting media and the frequency
of adverting.
 Spare part level determination to guarantee high efficiency of utilization of expensive
equipment
 It has been used to determine the inventory level and for formulating the inventory
recording.

CS6704 RESOURCE MANAGEMENT TECHNIQUES

 96
GRT INSTITUTE OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

 Other areas of applications scheduling methods Markovin decision, decision models,

infinite stage system, probabilistic decision problems etc.

15. State Bellman’s principle of optimality.

An optimal policy has the property that whatever be the initial state and initial decisions
the remaining decisions must constitute an optimal policy for the state resulting from the first
decisions
UNIT-IV
CLASSICAL OPTIMSATION THEORY
1. What is non linear programming problem?
Non linear programming problem is an extension of linear programming. The objective
function may be non linear, but the set of constraints may be linear or non linear. Such
problem are called as non linear problem.

2. What is the use of classical optimization theory?

Classical optimization theory uses differential calculus to determine points of maxima and
minima for unconstrained and constrained functions.

3. What are the methods of equality constraints?

 Jacobian method
 Lagrangean method

4. Write the condition for maximum of the function?

A function is a maximum at if
for all h.

5. Write the condition for minimum of the function?

A function is a minimum at if ,
for all h

6. State the order of convergence and convergence condition for Newton’s Raphson
method .
The order of convergence is 2. Condition for convergence is

7. Write the iterative formula of Newton’s Raphson method.

8. Show that the N.R formula to find can be expressed in the form

, n = 0, 1, 2, ……
If ,then is the equation to be solved.

CS6704 RESOURCE MANAGEMENT TECHNIQUES

 97
GRT INSTITUTE OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

Let ,
By N.R rule, if is the nth iterate,

, n = 0 , 1, 2,….

9. What is mean by unconstrained optimization?

An unconstrained optimizations problem is one where you only have to be concerned
with the objective function you are trying to optimize

10. Write the methods unconstrained optimization?

 FUNCTION OF ONE VARIABLE
 General ideas of optimization
 First and second order conditions
 Local and global extremum
FUNCTIONS OF SEVERAL VARIABLES
 First and second order conditions
 Local and global extremum
11. Define Hessian matrix
.

12. Define Lagrangian form non linear programming problem.

13. Write the necessary conditions for Khun-Tucker method?

For Maximization problem

CS6704 RESOURCE MANAGEMENT TECHNIQUES

 98
GRT INSTITUTE OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

14. Write the sufficient conditions for Khun-Tucker method?

UNIT-V OBJECT SCHEDULING

PART-A

1. What do you mean by a project?

A project is defined as a combination of inter-related activities all of which must be
executed in a certain order for completion.

2. What are the two basic planning and control techniques in a network analysis?
 Program Evaluation Review Technique (PERT)
 Critical Path Method(CPM)

3. What are the 3 main phases of a project?

Planning, Scheduling and Control.

4. What is a network?
It is the graphic representation of locality and sequentially connected arrows and nodes
representing activities and events of a project.

5. What are the 3 common errors in the construction of network?

 Formation of loops
 Dangling
 Redundancy

6. What is dangling in a network?

To disconnect an activity before the completion of all activities in a network diagram is
known as dangling.

CS6704 RESOURCE MANAGEMENT TECHNIQUES

 99
GRT INSTITUTE OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

7. What are the 3 types of floats?

 Total float
 Free float
 Independent float

8. Define total float?

The amount of time by which the completion of an activity could be delayed beyond the
earliest expected completion time without affecting the overall project duration time is called
the total float.

9. Define critical activity.

An activity is said to be critical if a delay in its start will cause a further delay in the
completion of the enter project.

10. What is the critical path?

The sequence of critical activities in a network is called the critical path.

11. Distinguish between PERT and CPM.

PERT CPM
 Event oriented  Activity oriented
 Probabilistic  Deterministic
 Three time estimates namely  Time is fixed
optimistic, pessimistic, most likely
are given  No limitations of resources
 Resources such as labour equipments,
materials are limited

12. Define the expected variance of a project length?

The expected variance of a project length also called the variance of the critical path is the
sum of the variance of all the critical activities.

13. Write down at least two main assumptions in PERT network calculation?
 The activity durations are independent
 The activity durations follow -distribution

14. Define crashing?

The process of reducing the activity duration by putting an extra effort is called crashing
the activity.

15. Define the cost time slope of an activity?

The cost slope indicating the increase in cost per unit and reduction in time, is defined as

CS6704 RESOURCE MANAGEMENT TECHNIQUES

 100
GRT INSTITUTE OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

16. Define crash time and crash cost.

The crash time represents the minimum duration time, that is possible and any attempts to
further crash would only raise the activity cost without reducing the time. The activity cost
corresponding to the crash time is called the crash cost.

17. What is resource scheduling?

Resource scheduling implies the task of allocation of resources to various activities in such
a manner that the allocation is considered as acceptable under the given situation.

18. What is Resource leveling?

Resource leveling refers to the scheduling of the activities within the limits of the available
floats in such a way that the variants in resource requirements are minimized.

19. What is resource smoothing?

Resource smoothing involves rescheduling of the activities of a project in such a way as to
utilize the resource in a fairly uniform manner and achieving the minimum project duration.

20. Define optimum duration of a project?

Optimum duration of project is the duration for which the total cost associated with it is
minimum.

21. Define the least duration of a project.

Least duration of a project is the minimum duration beyond which no more crashing of
the activity as possible. The total cost associated with it is not necessarily minimum.

PART – B

UNIT-I LINEAR PROGRAMMING

1. A manufacturer produces two types of models M1 and M2 .Each model of the type M1
requires 4 hours of grinding and 2 hours of polishing. Where as each model of the type M2
requires 2 hours of grinding and 5 hours of polishing. The manufacturer has 2 hours grinders
and 3 publishers. Each grinder’s works 40 hours week and each polisher works for 60 hours a
week. Profit on M1 model is Rs.3.00 and on model M2 is 4.00. Whatever is produced in a
week is sold in the market. How should the manufacturer allocate his production capacity to
the two types of models, so that the may make the maximum profit in a week?

2. A company manufacturer two products A and B. These products are processed in the same
machine. It takes 10 minutes to process one unit of product A and 2 minutes for each unit of

CS6704 RESOURCE MANAGEMENT TECHNIQUES

 101
GRT INSTITUTE OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

product B and the machine operates for a maximum of 35 hours in a week. Product A
requires 1 kg and B requires 0.5 kg of raw material per unit, the supply of which is 600 Kg
per week. Market constraint on product B is known to be minimum of 800 units every week.
Product A costs Rs.5 per unit and sold at Rs.10. Products B costs Rs.6 per unit and can be
sold in the market at a unit price of Rs. 8. Determine the number of units of A and B per
week to maximize the profit.

3. A firm manufacturer 3 products A,B and C. The profits are Rs.3, Rs.2 and Rs.4
respectively. The firm has 2 machines and given below is the required processing time in
minutes for each machine on each product.

Machines Product-wise processing time

A B C
M1 4 3 5
M2 3 2 4
Machines M1 and M2 have 2000 and 2500 machine minutes respectively. The firm must
manufacturer 100 units of A’s 200 units of B’s and 50 units C’s but not more than 150 units
of A’s. Set up an LPP to maximize the profit.

4. A farmer has a 100 acre farm. He can sell all tomatoes, lettuce or radishes and can get a
price of Rs. 1.00 per kg for tomatoes, Rs.0.75 a heap of Lettuce and Rs. 2.00 per kg for
radishes. The average yield per acre is 2000 kg of tomatoes, 3000 heaps of lettuce and 1000
kg of radishes. Fertilizers are available at Ra. 0.50 and the amount required per acre 100 kg
each for, tomatoes and lettuce and 50 kg for radishes. Labor required souring, cultivating and
harvesting per acre is 5 man-days for tomatoes and radishes and 6 man-days for lettuce. A
total of 400 man-day. Formulate the maximize the farmers total profit

5. A company desires to devote the excess capacity of the 3 machines, lathe, shaping and
milling machine of make 3 products A,B and C. The available time per month for these
machines is tabulated below.

Machine lathe shaping milling

Available 200 hrs 100hrs 180 hrs
time/month
The time taken to produce each unit of the products A,B and C on the machines is displayed
in the table below

machine Time taken(hours)

Lathe Shaping milling
Product A 6 2 4
Product B 2 2 -
Product C 3 - 3
The profit per product would be Rs. 20, Rs.16 and Rs. 12 respectively on products A, B and
C. Formulate a LPP to find the optimum product mix.

6. Solve the following LPP by graphical method

CS6704 RESOURCE MANAGEMENT TECHNIQUES

 102
GRT INSTITUTE OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

7. Solve the following LPP by the graphical method

8. A company manufacturer 2 types of printed circuits. The requirements of transistors,

resistors and capacitors for each type of printed circuits along with other data are given
below.

circuit Stock
available
A B
Transistor 15 10 180
Resistor 10 20 200
Capacitor 15 20 210
Profit Rs.5 Rs.8
How many circuits of each type should the company produce from the stock to earn
maximum profit.

9. Apply graphical method to solve the LPP

10. Use simplex method to solve the LPP

CS6704 RESOURCE MANAGEMENT TECHNIQUES

 103
GRT INSTITUTE OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

11. Solve the following

12. Use simplex method to

13. Solve the following LPP by simplex method

14. Use penalty method to

15. Using simplex method

UNIT-II
DUALITY AND NETWORKS

1. Write down the dual of the following LPP and it

CS6704 RESOURCE MANAGEMENT TECHNIQUES

 104
GRT INSTITUTE OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

2. Apply the principle of duality to solve the LPP

3. Using dual simplex method solve the LPP

4. Use dual simplex method to solve the LPP

5. Find the initial solution to the following transportation problem using VAM

destination D1 D2 D3 D4 Supply
factory
F1 3 3 4 1 100
F2 4 2 4 2 125
F3 1 5 3 2 75
Demand 120 80 75 25 300

6. Solve the following transportation problem

destination P Q R S Supply
source
A 21 16 25 13 11
B 17 18 14 23 13
C 32 17 18 41 19
Demand 6 10 12 15 43

CS6704 RESOURCE MANAGEMENT TECHNIQUES

 105
GRT INSTITUTE OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

7. Solve the following transportation problem starting with the initial solution obtained by
VAM.

D1 D2 D3 D4 Supply
O1 2 2 2 1 3
O2 10 8 5 4 7
O3 7 6 6 8 5
Demand 4 3 4 4 15
8. Solve the transportation problem when the unit transportation costs, demands and suppliers
are as given below.

Destination D1 D2 D3 D4 Supply
origin
O1 6 1 9 3 70
O2 11 5 2 8 55
O3 10 12 4 7 70
Demand 85 35 50 45
9. Using the following cost matrix determine a) optimal job assignment b). The cost of
assignments

JOB

1 2 3 4 5

A 10 3 3 2 8

B 9 7 8 2 7

mechanics C 7 5 6 2 4

D 3 5 8 2 4

E 9 10 9 6 10

10. A company has 5 jobs to be done on five machines. Any jobs can be done on any
machine. The costs of doing the jobs on different machines are given below. Assign the jobs
for different machines so as to minimize the total cost

MACHINES

1 2 3 4 5

A 13 8 16 18 19

B 9 15 24 9 12

CS6704 RESOURCE MANAGEMENT TECHNIQUES

 106
GRT INSTITUTE OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

JOBS C 12 9 4 4 4

D 6 12 10 8 13

E 15 10 18 12 20

11. Solve the following assignment problem in order to minimize the total cost. The cost
matrix given below gives the assignment cost when different operators are assigned to
various machines

OPERATORS

I II III IV V

A 30 25 33 35 36

B 23 29 38 23 26

MACHINES C 30 27 22 22 22

D 25 31 29 27 32

E 27 29 30 24 32

12. A company has 4 machines to do 3 jobs. Each job can be assigned to only one machine.
The cost of each job on each machine is given below. Determine the job assignment that will
minimize the total cost.

MACHINES

W X Y Z

A 18 24 28 32

JOB B 8 13 17 18

C 10 15 19 22

13. A travelling salesman has to visit 5 cities. He wishes to start from a particular city visit
each city once and then returns to his starting point. Cost of going from one city to another is
shown below. You are required to find the least cost route

TO CITY

A B C D E

I 4 10 14 2

II 12 6 10 4

CS6704 RESOURCE MANAGEMENT TECHNIQUES

 107
GRT INSTITUTE OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

FROM CITY III 16 14 8 14

IV 24 8 12 10

V 2 6 4 16

14. A machine operator processes five types of items on his machine each week and must
choose a sequence for them. The setup cost per change depends on the items presently on the
machine and the setup to be made according to the following table

TO ITEM

A B C D E

A 4 7 3 4

B 4 6 3 4

FROM ITEM C 7 6 7 5

D 3 3 7 7

E 4 4 5 7

15. A salesman has to visit five cities A, B, C, D and E. The distance (in hundred miles)
between the five cities is a follows: TO

A B C D E

A - 7 6 8 4

B 7 - 8 5 6

FROM C 6 8 - 9 7

D 8 5 9 - 8

E 4 6 7 8 -

UNIT-III

INTEGER PROGRAMMING

1. Find the optimum integer solution to the following LPP

2. Find an optimum integer solution to the following LPP

CS6704 RESOURCE MANAGEMENT TECHNIQUES

 108
GRT INSTITUTE OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

3. Solve the integer programming problem

4. Solve the integer programming problem

5. Consider the problem

Solve the problem as a continuous linear program; then show that it is impossible to obtain
feasible integer solution by using simple rounding. Solve the problem using any integer
problem algorithm.

6. Solve

7. Solve the following mixed integer problem by the branch and bound technique:

CS6704 RESOURCE MANAGEMENT TECHNIQUES

 109
GRT INSTITUTE OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

8. Solve the following mixed integer problem by the branch and bound technique:

9. Use branch and bound algorithm to solve

10. Solve by branch and bound method

11. A firm has divided its marketing area into three zones. The amount of sales depends upon
the number of salesmen in each zone. The firm has been collecting the data regarding sales
and salesmen in each area over a number of past years. The information is summarized in
below table. For the next year firm has only 9 salesmen and the problem is to allocate these
salesmen to three different zones so that the total sales are maximum.

No. of Zone 1 Zone 2 Zone 3

salesmen
0 30 35 42
1 45 45 54
2 60 52 60
3 70 64 70
4 79 72 82
5 90 82 95
6 98 93 102
7 105 98 110
8 100 100 110

CS6704 RESOURCE MANAGEMENT TECHNIQUES

 110
GRT INSTITUTE OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

9 90 100 110
12. The owner of a chain of four grocery stores has purchased six crates of fresh strawberries.
The following table gives the estimated profits at each store when it is allocated various
number of boxes

STORES
1 2 3 4
0 0 0 0 0
NUMBER 1 4 2 6 2
OF 2 6 4 8 3
BOXES 3 7 6 8 4
4 7 8 8 4
5 7 9 8 4
6 7 10 8 4
The owner does not wish to split crates between stores, but is willing to make per allocations.
Find the allocation of six crates so as to maximize the profits.

13. Use dynamic programming to solve the following LPP.

14. Solve the following LPP by the method of dynamic programming:

15. Solve the following LPP by dynamic programming:

UNIT-IV

CS6704 RESOURCE MANAGEMENT TECHNIQUES

 111
GRT INSTITUTE OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

CLASSICAL OPTIMIZATION THEORY

1. Solve the following NLPP.

2. Obtain the necessary and sufficient conditions for the optimal solution of the following
problem. What is the optimal solution?

3. Use the method of Lagrangean multipliers to solve the following NLPP. Does the solution
maximize or minimize the objective function?

4. Solve the non-linear programming problem given below:

5. Solve the following NLPP using Khun-Tucker conditions

6. Solve the following NLPP:

CS6704 RESOURCE MANAGEMENT TECHNIQUES

 112
GRT INSTITUTE OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

7. Use the Khun-Tucker conditions to solve the following non-linear programming problem:

8. Use the Khun-Tucker conditions to solve the following non-linear programming problem:

9. Consider the linear program

10. Find the real positive root of by Newton’s method correct to 6 decimal
places.

11. Find a root of by N.R method correct to three decimal places

12. Using N.R method, solve start with .

13. Write down Newton-Raphson formula for finding where a is a positive number and
hence find

14. Find the iterative formula for finding the value of where N is a real number, using

Newton-Raphson method. Hence evaluate 1/26 correct to 4 decimal places.

UNIT-V

OBJECT SCHEDULING

1. Construct a network for each of the projects whose activities and their precedence
relationship are given below.
Activity A B C D E F G H I J K
predecessor - - - A B B C D E H,I F,G

CS6704 RESOURCE MANAGEMENT TECHNIQUES

 113
GRT INSTITUTE OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

2. A, B and C can start simultaneously A < D, I; B < G, F; D < G,F ; C < E; E < H, K; F <
H,K;
G, H < J.
3. A project scheduling 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(days) 4 1 1 1 6 5 4 8 1 2 5 7
From the above information you are required to
i). construct a network diagram
ii). Complete the earliest event time and latest event time.
iii). Determine the critical path and total project duration
iv). Compute total and free float for each activity.
4. A small maintenance project consists of the following jobs whose precedence relationships
are given below:

Job 1-2 1-3 2-3 2-5 3-4 3-6 4-5 4-6 5-6 6-7
Duration 15 15 3 5 8 12 1 14 3 14
days
i).Draw an arrow diagram representing the project .
ii). Find the total float for each activity.
iii). Find the critical path and the total project duration.
5. The following table shows the jobs of a project with their duration in days. Draw the
network and determine the critical path. Also calculate all the floats.

Jobs 1-2 1-3 1-4 2-5 3-7 4-6 5-7 5-8 6-7 6-9 7-10 8-10 9-10 10-11 11-12
Duration 10 8 9 8 16 7 7 7 8 5 12 10 15 8 5

6. A project consists of a series of tasks labeled A, B, C,….H, I with the following constraints
A < D,E ; B, D < F; C < G; B < H; F, G < I; W < X,Y means X and Y cannot start until W is
completed. You are required to construct a network using this notation. Also find the
minimum time of completion of the project when the time of completion of each task is given
as follows:
Task A B C D E F G H I
Time 23 8 20 16 24 18 19 4 10
(days)

7. The following table shows the jobs of a network along with their time estimation.
Job 1-2 1-6 2-3 2-4 3-5 4-5 6-7 5-8 7-8
a(days) 1 2 2 2 7 5 5 3 8
m(days) 7 5 14 5 10 5 8 3 17
b(days) 13 14 26 8 19 17 29 9 32
Draw the project network and find the probability of the project completing in 40 days.

8. Construct the network for the project whose activities and the 3 time estimates of these
activities (in weeks) are given below. Compute

CS6704 RESOURCE MANAGEMENT TECHNIQUES

 114
GRT INSTITUTE OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

i). Expected duration of each activity

ii). Expected variance of each activity.
iii). Expected variance of the project length

Activity 1-2 2-3 2-4 3-5 4-5 4-6 5-7 6-7 7-8 7-9 8-10 9-10
to 3 4 2 3 1 3 4 6 2 1 4 3
tm 4 2 3 4 3 5 5 7 4 2 6 5
tp 5 3 4 5 5 7 6 8 6 3 8 7

9. A small projects is composed of seven activities whose time estimates are listed in the
table as follows:

Activity 1-2 1-3 2-4 2-5 3-5 4-6 5-6

a 1 1 2 1 2 2 3
m 1 4 2 1 5 5 6
b 7 7 8 1 14 8 15
i). Draw the project network.
ii). Find the expected duration and variance of each activity
iii). Calculate the earliest and latest occurrence for each event and the expected project length
iv). Calculate the variance and standard deviation of project length.
v). what is the probability that the project will be completed ?
a). 4 weeks earlier than expected
b). Not more than 4 weeks later than expected ?
c). If the project due date is 19 weeks, what is the probability of meeting the due date?.
10. The following table shows the jobs of network along with their time estimates. The time
estimates are in days.
Jobs 1-2 1-6 2-3 2-4 3-5 4-5 5-8 6-7 7-8
a 3 2 6 2 5 3 1 3 4
m 6 5 12 5 11 6 4 9 19
b 15 14 30 8 17 15 7 27 28
a). Draw the project network.
b). Find the critical path.
c). Find the probability of the project being completed in 31 days.
11. Assuming that the expected times are normally distributed find the probability of meeting
the scheduled time as given for the network.

Activity 1-2 1-3 2-4 3-4 4-5 3-5

a 2 9 5 2 6 8
m 5 12 14 5 6 17
b 14 15 17 12 12 20
Scheduled project completion time 30 days. Also find the date on which the project manager
can complete the project with a probability of 0.90.
12. Determine the optimum project duration and cost for the following data:

Activity Normal Crash

CS6704 RESOURCE MANAGEMENT TECHNIQUES

 115
GRT INSTITUTE OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

Time(days) Cost Time(days) cost

1-2 8 100 6 200
1-3 4 150 2 350
2-4 2 50 1 90
2-5 10 100 5 400
3-4 5 100 1 200
4-5 3 80 1 100
Indirect cost is Rs. 70 per day.
13. The following table gives the activities of a construction of project along with other
relevant information.
i). what is the normal project length and the minimum project length?
ii). Determine the minimum crashing cost of schedule ranging from normal length down to
and including the minimum length schedule
Activity Normal Crash Cost of
duration duration crashes
1-2 9 6 20
1-3 8 5 25
1-4 15 10 30
2-4 5 3 10
3-4 10 6 15
4-5 2 1 40
iii). What is the optimal length schedule duration of each job for your solution? Overhead of
the project is Rs. 60 per day

14. The table below provides costs and estimates for a seven activity project.

Activity Time estimate Direct cost estimate

normal crash normal crash
A 1-2 2 1 10 15
B 1-3 8 5 15 21
C 2-4 4 3 20 24
D 3-4 1 1 7 7
E 3-5 2 1 8 15
F 4-6 5 3 10 16
G 5-6 6 2 12 36
i). Draw the project network corresponding to normal time.
ii). Determine the critical path, normal duration and cost of the project.
iii). Crash the activities so that the project completion time reduces to 9 weeks?
15. The following time cost table (time in weeks and cost in rupees) applies to a project. Use
it to arrive at the network associated with completing the project in minimum time with
minimum cost.
Activity Normal Crash
Time Cost Time Cost
1-2 2 800 1 1400
1-3 5 1000 2 2000
1-4 5 500 3 1800

CS6704 RESOURCE MANAGEMENT TECHNIQUES

 116
GRT INSTITUTE OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

2-4 1 500 1 500

2-5 5 1500 3 2100
3-4 4 2000 3 3000
3-5 6 1200 4 1600
4-5 5 900 3 1600

CS6704 RESOURCE MANAGEMENT TECHNIQUES

 117
GRT INSTITUTE OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

CS6704 RESOURCE MANAGEMENT TECHNIQUES

 118
GRT INSTITUTE OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

CS6704 RESOURCE MANAGEMENT TECHNIQUES

 119
GRT INSTITUTE OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

CS6704 RESOURCE MANAGEMENT TECHNIQUES

 120
GRT INSTITUTE OF ENGINEERING AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

CS6704 RESOURCE MANAGEMENT TECHNIQUES