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.

 Characteristics of Operations Research.

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.

 Models by degree of abstractness

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.

 (2) Numerical methods:

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.

@@@


Simplex Method


***

Artificial Variable and Two Phase Simplex Method


%%%


Dynamic Programming


###

Game theory and Simulation


$$$



CPM, PERT and Network Models




Comments

Popular posts from this blog

Question Bank

Transportation Problems