17CS653 Operations research syllabus for CS

Introduction, Linear Programming:

Introduction: The origin, natureand impact of OR; Defining the problem and gathering data; Formulating amathematical model; Deriving solutions from the model; Testing the model;Preparing to apply the model; Implementation .

Introduction to Linear Programming Problem (LPP):

Prototype example, Assumptions of LPP, Formulation of LPP and Graphical method various examples.

Simplex Method – 1:

The essence of the simplex method; Setting up the simplex method; Types of variables, Algebraof the simplex method; the simplex method in tabular form; Tie breaking inthe simplex method, Big M method, Two phase method.

Simplex Method – 2: Duality Theory -

The essence of duality theory, Primaldual relationship, conversion of primal to dual problem and vice versa. The dual simplex method.

Transportation and Assignment Problems:

The transportation problem, Initial Basic Feasible Solution (IBFS) by North West Corner Rule method, Matrix Minima Method, Vogel’s Approximation Method. Optimal solution by Modified Distribution Method (MODI). The Assignment problem; A Hungarian algorithm for the assignment problem. Minimization and Maximization varieties in transportation and assignment problems.

Game Theory:

Game Theory: The formulation of twopersons, zero sum games; saddle point, maximin and minimax principle, Solving simple games- a prototype example;Games with mixed strategies; Graphical solution procedure.

Metaheuristics:

The nature of Metaheuristics, Tabu Search, SimulatedAnnealing, Genetic Algorithms.

Course outcomes:

The students should be able to:

• Explain optimization techniques for various problems.
• Understand the given problem as transportation and assignment problem and solve.
• Illustrate game theory for decision support system.

Question paper pattern:

• The question paper will have TEN questions.
• There will be TWO questions from each module.
• Each question will have questions covering all the topics under a module.
• The students will have to answer FIVE full questions, selecting ONE full question from each module.

Text Books:

1. D.S. Hira and P.K. Gupta, Operations Research, (Revised Edition), Published by S. Chand & Company Ltd, 2014

Reference Books:

1. S Kalavathy, Operation Research, Vikas Publishing House Pvt Limited, 01-Aug-2002

2. S D Sharma, Operation Research,KedarNath Ram Nath Publishers.