Syllabus (MATHEMATICS)

Course Type: MAJ-8

Semester: 6

Course Code: BMTMMAJ08T

Course Title: Linear Programming Problems & Game Theory

(L-P-Tu): 5-0-1

Credit: 6

Practical/Theory: Theory

Course Objective: To be done.

Learning Outcome: Course Outcomes (CO): The whole course will have the following outcomes: Upon successful completion of this course, students will be able to CO1: solve linear programming problems (LPP) using appropriate techniques and optimization solvers, interpret the

Syllabus:

Unit -1: Linear Programming Problems [Credit: 4, 60L]

• Canonical & Standard form of L.P.P, Basic solutions, feasible, basic feasible & optimal solutions, Reduction of a feasible solution to basic feasible solution, Hyperplanes and Hyperspheres, Convex sets and their properties, convex functions, Extreme points, Convex feasible region, Convex polyhedron, Polytope, Graphical solution of L. P.P.
• Fundamental theorems of L.P.P., Improved basic feasible solutions, Bounded and Unbounded solution, Condition of optimality, Simplex method, Simplex algorithm, Artificial variable technique (Big M method, Two phase method), Inversion of a matrix by Simplex method. Degeneracy in L.P.P. and its resolution.
• Duality in L.P.P.: Concept of duality, Fundamental properties of duality, Fundamental theorem of duality, Duality & Simplex method.
• Dual Simplex method, modified dual simplex method, and revised simplex method.
• Transportation Problem (T.P.): Matrix form of T.P., the transportation table, Initial basic feasible solutions (different methods like North West corner, Row minima, Column minima, Matrix minima & Vogel’s Approximation method), Loops in T.P. table and their properties, Optimal solutions, Degeneracy in T.P., Unbalanced T.P.
• Assignment Problem, Mathematical justification for optimal criterion, optimal solution by Hungarian Method, Travelling Salesman Problem.

Unit -2: Game Theory [Credit: 1, 15 L]

• Theory of Games: Introduction, Two person zero-sum games, Minimax and Maximin principles, Minimax and Saddle point theorems, Mixed Strategies games without saddle points, Minimax (Maximin) criterion, The rules of Dominance, Solution methods of games without Saddle point; Algebraic method, Matrix method, Graphical method and Linear Programming method.

Reading References:

1. Mokhtar S. Bazaraa, John J. Jarvis and Hanif D. Sherali, Linear Programming and Network Flows, 2nd Ed., John Wiley and Sons, India, 2004.
2. F.S. Hillier and G.J. Lieberman, Introduction to Operations Research, 9th Ed., Tata McGraw Hill, Singapore, 2009.
3. Hamdy A. Taha, Operations Research, An Introduction, 8th Ed., Prentice-Hall India, 2006.
4. G. Hadley, Linear Programming, Narosa Publishing House, New Delhi, 2002.
5. Ghosh & Chakraborty, An Introduction to Linear Programming & Game Theory, Maulik Library
6. Karak, P. M., Linear Programming with Game Theory, New Central Book Agency
7. Sharma, J. K., Operations Research – Theory and Applications
8. Swarup, Gupta & Man Mohan – Operations Research