Operations Research
|
|
GAYATRI
VIDYA PARISHAD COLLEGE
FOR DEGREE AND PG COURSES (AUTONOMOUS) Affiliated
to Andhra University || Accredited by NAAC and NBA VISAKHAPATNAM |
DEPARTMENT OF COMPUTER APPLICATIONS (MCA)
OPERATIONS RESEARCH
SYLLABUS
UNIT-I:
Overview
of Operations Research Types of OR Models - Phases of
Operations Research– OR Techniques, Introduction to Linear Programming problem:
Formulation of Linear Programming
Problem, Graphical Solution; Standard Form of LPP, Basic Feasible Solutions –
Unrestricted Variables, Simplex Algorithm- Artificial Variables -Big M Method-
Two Phase Simplex Method-Degeneracy-Alternative Optimal, Unbounded
Solutions-Infeasible Solutions, Primal And Dual Problems And Their Relations,
Dual Simplex Method.
UNIT-II:
Transportation
Problems: Initial Solutions- Northwest Corner Rule- Lowest
Cost Method, Vogel’s Approximation Method- Optimum Solutions of TPP- Degeneracy
in Transportation-Transportation Algorithms, Assignment Problem, Assignment
Problem as LPP, Hungarian Method- Travelling Salesman Problem- Solutions of
TSP, Sequencing Problems, N-Jobs Two Machine Problems- N-Jobs K Machines
Problems
UNIT-III:
Network
models: Network Representation of a Project- CPM and PERT -
Critical Path Calculations- Time – Cost Optimizations- PERT Analysis and
Probability Considerations- Resource Analysis in Network Scheduling.
Replacement Problems-Individual and Group Replacement Policy- Reliability;
System Failure Problems Inventory Theory-Factors Effecting Inventory-EOQ
Inventory Problems with and Without Shortages.
UNIT-IV:
Non-Linear
Programming: Dynamic Programming- Recursive Nature
of Dynamic Programming – Forward and Backward Recursion- Solutions of LPP As
Dynamic Programming Technique Integer Programming: Branch and Bound Algorithms.
UNIT-V:
Simulation:
Introduction to Simulation, Simulation Models- Event Type Simulations,
Generation of Random Numbers-Monte-Carle Simulation. Game theory: Two Person Zero Sum Games
- Mixed Strategy Games and their Algorithms. Dominance principle, Graphical, algebraic method and linear programming
approach of solving two-person zero sum games.
Course outcomes:
CO1: Understand, formulate and solve real-world
linear programming problems using various techniques
CO2: Develop skills to formulate and solve
Transportation and Assignment problems using different mathematical techniques
CO3: Apply network representation for project
management, and utilize CPM and PERT for critical path calculation
CO4: Analyze and apply various decision-making tools in uncertain situations
CO5: Practice various methods of solving game theory related problems and simulation methods for analyzing complex systems.
MODEL PAPER
|
|
GAYATRI VIDYA PARISHAD COLLEGE FOR DEGREE AND PG COURSES
(AUTONOMOUS) |
||||
|
Affiliated
to Andhra University || Accredited by NAAC and NBA |
|||||
|
VISAKHAPATNAM |
|||||
Master of Computer Applications 1st Year
Semester I
OPERATIONS RESEARCH (MODEL PAPER)- Code:1.1.4
(w.e.f
2024-25 admitted batch)
TIME: 3 Hrs. SECTION
– A Max. Marks.60M
Answer the following Questions 5 x2: l0M
1.
What
are various phases of operation research? [C.O – 1]
2.
Write
an algorithm for North West corner method [C.O – 2]
3.
What
are the uses of PERT and CPM techniques? [C.O – 3]
4.
Explain
the steps of dynamic programming technique. [C.O – 4]
5.
What
are the advantages and limitations of simulation? [C.O – 5]
SECTION – B
Answer the following Questions 5x10: 50M
6.
(A) Write the
graphical method and solve the following L.P.P [C.O –
1]
Max Z
= 6 x1 + 4 x2
Subject
to: 2x1+3x2 £120; 2x1+ x2 £ 60; x1, x2 ³ 0
O.R
(B) Solve the
following linear programming problem Using Big M method. [C.O
– 1]
Minimize Z
= 10x1+15x2 + 20x3 Subject to 2 x1+4x2
+6 x3 ³ 24; 3 x1+9x2 + 6x3
³30;
x1,
x2, x3 ³ 0
7.
(A). Apply Vogel’s
Approximation Method to obtain initial
basic feasible solution of the
transportation problem [C.O – 2]
|
|
D |
E |
F |
G |
Availability |
|
A |
11 |
13 |
17 |
14 |
250 |
|
B |
16 |
18 |
14 |
10 |
300 |
|
C |
21 |
24 |
13 |
10 |
400 |
|
Demand |
200 |
225 |
275 |
250 |
|
O.R
(B) Solve the following
Assignment problem using Hungarian method. The matrix entries are processing time in hours. [C.O – 2]
|
Operator |
|||||
|
Job |
10 |
12 |
15 |
12 |
8 |
|
7 |
16 |
14 |
14 |
11 |
|
|
13 |
14 |
7 |
9 |
9 |
|
|
12 |
10 |
11 |
13 |
10 |
|
|
8 |
13 |
15 |
11 |
15 |
|
8.
(A) Given the following data (in months) [C.O – 3]
Activity a m b
1-2 0.8 1.0 1.2
2-3 3.7 5.6 9.9
2-4 6.2 6.6 15.4
3-4 2.1 2.7 6.1
4-5 0.8 3.4 3.6
5-6 0.9 1.0 1.1
i)
Construct the project network.
ii)
Determine the critical path, expected project completion
time.
iii)
What is the probability that the project will
complete two months later expected.
O.R
(B) Describe the basic characteristics of an
inventory system. [C.O – 3]
A company uses annually
12000 units of a raw material costingrs.1.25 per unit placing each order costs
45 paisa and the carrying costs are 15% per year unit of the average inventory
find the Economic Order Quantity.
9.
(A) Solve
the following linear programming problem optimally using dynamic programming. Maximize Z= 3x1+5 x2 [C.O – 4]
Subject
to x1£ 4; x2 £ 6; 3x1 +2x2£ 18; x1, x2 ³ 0;
O.R
(B) Solve the following integer programming
problem using branch and bound method. [C.O – 4]
Max Z = x1+ 4 x2
subject
to constraint 2x1+ 4x2 ≤ 7, 5 x1 + 3 x2 ≤
15 ; x1,x2³0 and are integers.
10. (A) Explain
steps for generation of random numbers with example [C.O
– 5]
O.R
(B) Solve the following game using dominance
property. [C.O – 5]
Origin and historical development of Operations Research.
1) Brief History of Operations Research:
During the second world war the military personnel of allied powers were required to deploy ammunition, troops and machinery in strategic and tactical manner to cause maximum loss and destruction to the enemy, while using minimum amounts of the resources at their disposal. In a war intelligent, strategic deployment and quality of the forces counts and not its numerical strength is a well-known fact.
One can find reference to this in the epic Mahabharata and in the following two verses of sage Veda Vyasa in Bhagavad Gita.
Dhrustvatu Pandavaneekam Vyudham
Duryodhana stada
Acharya mupasangamya raja vachanamabraveeth.
Pasyetam Pandu putranam acharya mahateem chamum
Vyudham Drupada putrena tava sishyena dheemata.
(Oh king, having seen the army of Pandavas arrayed on the battle field in a strategic form Duryodhana went to his teacher and spoke thus.
Look at the great army of the sons of Pandu and its strategic arrangement by your intelligent student and son of Drupada.)
To achieve the task entrusted to them in second world war in an objective manner scientists and specialists from various disciplines were organized into small teams to assist the military management. The systematic and scientific approaches adopted by these teams for solving the above problems by studying the operations of the systems involved led to the development of Operations Research or Operational Research.
2)
The term Operations Research was
coined by Mc Closky and Treften in 1940.
3)
This subject gained prominence during second world war when military
managements of allied powers formed interdisciplinary teams of scientists from
various fields to solve the tactical and operational problems of military.
4)
The new approach to systematic and scientific study of the operations of the
systems was called Operations Research
or Operational Research.
5) After the war the industrial and business
managements saw the usefulness of the interdisciplinary, systematic and
scientific approach of solving complex problems by military and adopted it for
solving the business and industrial problems. This led to tremendous
development of the subject during post world war period.
6)
In 1957 The International Federation of
Operations Research Societies was formed.
OPERATIONS RESEARCH’S DEVELOPMENT IN INDIA.
1)
In 1949 a unit of Operations Research was started at Regional Research
Laboratory at Hyderabad.
2) In 1953 Operations Research unit was started
in Indian Statistical Institute at Kolkatta.
3)
In 1955 Operational Research Society of
India was formed.
4)
In 1959 Operational Research Society of India became a member of The International Federation of Operations
Research Societies and the first conference of Operations Research Society
of India was held in New Delhi.
5)
In 1963 publication of OPSEARCH the
official journal of Operational Research
Society of India was started.
6)
Prof. P.C.Mahalnobhis, the founder
director of the Indian Statistical Institute at Kolkatta used the techniques of
operations research while formulating the second five year plan. He utilized
these techniques to forecast the trends of demand, availability of resources,
schedule the complex schemes necessary for development of the country’s
economy.
7) Operations Research is the attack of
modern science on problems of likely hood that arise in the management and
control of men, machines, material and money in their natural environment. Its
special technique to invent a strategy of control by measuring, comparing and
predicting the probable behavior of a scientific model of the situation.
Some Definitions of Operations Research.
1) “Operations Research is
scientific knowledge through interdisciplinary team effort for the purpose of determining
the best utilization of limited resources.”
-- H.A.Taha.
2)
“Operations Research is a scientific
approach to problems solving for executive management.”
--H.M.Wagner.
3)” Operations Research is the art of giving
bad answers to problems that otherwise have worse answers.”
--T.L.Saaty.
4)
“Operations Research is the method of
providing the executive departments with a quantitative basis for decisions
under their control.”
--
P.M. Morse and G.E.Kimball.
5)” Operations Research is the application of
scientific methods, techniques and tools to problems involving the operations
of a system so as to provide those in control of the systems with optimum
solutions to the problems.”
-- Churchman, Arkoff and Arnoff.
SCOPE OF OPERATIONS RESEARCH
1)
Directing Authority:
Operations Research helps
the directing authority in optimum allocation of various limited resources such
as men, material, machines, capital etc.
2)
Production Management:
Operations Research helps
the production department in finding the optimum product mix, product
scheduling and sequencing, in determining the size and number of production
runs, in design, selection and location of production facilities.
3) Materials Management:
Operations Research is of tremendous use in deciding when to buy, how much to buy and how often to buy.
4) Marketing Management:
Operations Research techniques are widely used in decisions about minimum per unit price of the unit, selection media for advertisement, location of distribution points to sell and choice of customers to sell etc.
5) Human Resources Management:
Operations Research is very much utilized by HR department in making decisions about the size of the work force to be maintained in variable workload, optimum manner of sequencing of personnel to various jobs, recruitment of skilled persons at minimum cost etc.
6) Financial Management:
Operations Research is useful in determining optimum replacement of policies, profit plan for the company, long range capital requirement, ways and means of generation of the required capital.
6) Agriculture Sector
In the field of agriculture, OR is helpful to decide what crops are to be raised, the extent of area in which they should be raised, what should be the procurement price of the crop etc.
7) Health Sector
OR is helpful in the health care sector to solve problems of allocation of beds and other resources to meet the medical exigencies.
The
following are the basic characteristics of operations research.
1)
Interdisciplinary team approach.
2)
Use of techniques of scientific research to find the optimum solution. It
utilizes a systematic approach for the study of the different aspects of the
problem in a logical manner.
3) Optimization of total output by maximizing
the profit or minimizing the cost.
4)
Mathematical models are used for quantitative measurement.
Note:
1)
Operations Research cannot give specific
answers to the problems, but improves the quality of the decisions taken.
2) Operations Research is
a tool that helps the decision maker to be objective in choosing the
alternatives from among many that are feasible or can be conceived.
Other examples:
1)
Recent floods in
Rayalaseema region of Andhra Pradesh the problem of evacuation of the affected
people.
2)
Formulating the time
table after introducing cluster system.
3)
Crowd management during
Chandanotsavam at Simhachalam.
Distinguishing Characteristics or Main features of Operations Research.
1)
The primary focus of Operations Research is decision making. However, complex may be the situations the main
steps involved for the above purpose can be enumerated as follows.
Step-1: Identification of the problem.
To define the
problem in a clear, precise and concise manner. To identify the parameters
involved, the input data required.
Step-2: Effectiveness
criterion (Objective Criterion)
To establish a
criterion to measure the effectiveness of various decision alternatives.
We should always
establish an effectiveness criterion which can evaluate the effectiveness of
various possible courses of action and helps us in choosing the best or next to
the best alternative depending on the situation.
Step-3: Feasible solutions.
To find or list
out the different courses of action to be followed.
We should find the
various possible alternatives that are available in a given situation. We
should be able to identify the major courses of action at the least.
Step-4: Reliance on Mathematical model.
To determine the
model to be used connecting the parameters involved, the uncontrolled variables
and the data gathered.
Step-5: Reliance on Scientific Approach:
Solving the model
to select the best or Optimal alternative.
In solving the model
formulated in step-4 to find the optimum solution, the process of reasoning
should be formalized so that another person with the same input gets the same
solution. For this purpose, stress is on using scientific and systematic
approach and not to place much reliance on hunch or intuition.
2) Interdisciplinary Approach:
The complex managerial problems involve several dimensions like
physical, economical, engineering, psychological etc. To solve such problems
the approach adopted should be a blend of different dimensions with the active
involvement and participation of people having expertise in the above fields.
Use of Computers:
The
complex nature of the problem, the huge amount of data required, the
computations required for evaluating the effectiveness of the different
decision alternatives make it essential to use digital computers.
Phases or Methodology of Operations Research.
The systematic and
scientific methods used in operations research comprise of the following three
phases.
(1) Judgment Phase:
In
the judgment phase we come to grip with the crux of a real-world problem that
was observed and analysed for some reasonable period of time, we identify the
goal that is to be achieved along with the variables that are helpful in
reaching this goal. Formulation of an appropriate model is also considered in
this phase.
(2) Research Phase:
In the second
phase attention is paid to observations and data collection for a better
understanding of the problem, formulation of the hypothesis and testing of the
validity of the hypothesis is also considered.
(3) Action Phase:
In the last phase
recommendations for decision making in the process to which the problem is
related are considered.
Importance of Model Building or Model Building
is the essence of Operations Research Approach.
A model of a real-world
phenomenon can be considered as a vehicle which is helpful for arriving at
right decisions in a well-structured way. To construct a model one has to
understand the complexities of the situation, the attending uncertainties a
decision maker has to consider, the logical frame work that can be used and
finally the various alternatives or options and their possible consequences. It
also requires consideration of input data requirements for taking valid and
meaningful decisions.
The
models used in operations research can be classified taking in to consideration
their structure, the environment in which they operate and the degree of
abstractness.
Models by their structure:
Depending on the
structure of the model used these models can be further classified into (1)
Iconic models, (2) Analogue models and (3) Mathematical models.
(1) Iconic models:
These are scaled
up or scaled down models of real-world objects like toy Aeroplan etc. these are
easy to describe but are very difficult to manipulate.
(2) Analogue models
These are somewhat more abstract than iconic models. They use one set of properties to describe another set of properties. Network of roads may be considered as network of water pipes, describing a production process by a flow chart can be considered as examples of analogue models.
(3) Mathematical Models:
In these models’
mathematical symbols are used to depict the real-world situation and the
relationship between its important components. These are the most abstract
models and are formulated to capture the crux of the decision-making problem.
Achieving a proper balance between reality and manageability of a model
requires considerable expertise and for that reason model building is a
difficult task.
Models by environment:
Based on the
environment in which a model has to operate models can be classified into (1)
Deterministic, (2) Probabilistic and (3) Dynamic models.
(1) Deterministic Models:
In classical economic order quantity
models when we assume that the demand for the item is completely known, Lead
time is fixed we get deterministic models.
(2) Probabilistic Models:
In real world
demand for a product is never known with certainty. For that reason, we assume
that is a random variable following a particular type of probability
distribution. In such situations we get probabilistic models.
(3) Dynamic Models:
When the demand is
a random variable whose value changes from one time point to another, we get
dynamic models.
Depending
on the degree of abstractness obtained a model can be classified as (1)
Descriptive models, (2) Predictive models and (3) Normative models.
(1) Descriptive models:
These are mainly used to describe the essential features of an observed phenomenon.
(2) Predictive models:
Sometimes the main idea of building a model is to predict what is going to happen in the future if the same set of underlying conditions prevail. Time series analysis and regression analysis can be considered as examples of this.
(3) Normative models:
After having seen a model explain a real-world situation satisfactorily for a number of times one may want to standardize it to describe future situations. Use of linear programming for product mixing, profit maximization or cost minimization can be considered as examples for this.
Methods of solving Operations Research Models:
Three
types of methods are used for solving operations research models.
(1) Analytical methods:
Solutions of the model are obtained by solving the model analytically using classical optimization techniques like differentiation.
Usage of iterative procedures where we start with an initial solution and try to obtain a better solution. The procedure is continued till no further improvement can be made in the objective criterion nor is it economically justified.
(3) Monte Carlo method:
These methods use the concept of probability and sampling. They comprise of making sample observations and finding probability distributions for the variables of interest. Using these probability distributions and random numbers we generate sequences of values of interest and fit an appropriate mathematical function to these values.
@@@
***
Artificial Variable and Two Phase Simplex Method
%%%
###
$$$
Comments
Post a Comment