OPERATIONS RESEARCH MAKAUT MBA SECOND SEM

MODULE-1

Chapter 1: Linear Programming

1.1.

Linear Programming Problems(LPP)

13

1.1.1.

Meaning and Definition

13

1.1.2.

General Mathematical Model of LPP

13

1.1.3.

Assumptions of Linear Programming Model

14

1.1.4.

Components of Linear Programming Problem

14

1.1.5.

Applications of Linear Programming(LP)

15

1.1.6.

Formulation of Linear Programming Model

15

1.1.7.

Methods of Solving LP Problems

18

1.2.

Graphical Solution

18

1.2.1.

Introduction

18

1.2.2.

Graphical Solution Method of LPP/Steps of Graphical Methods of LPP

19

1.2.3.

Maximisation Problems

19

1.2.4.

Minimisation Problems

21

1.2.5.

Mixed Constraints Problems

24

1.2.6.

Special Types of LPP in Graphical Method

25

1.2.6.1.

Infeasibility

25

1.2.6.2.

Unboundedness

26

1.2.6.3.

Multiple Optimal Solutions

26

1.3.

Simplex Method

27

1.3.1.

Introduction

27

1.3.2.

Steps of Simplex Algorithm

27

1.3.3.

Slack, Surplus Variables and Artificial Variables

28

1.3.4.

Maximisation Problems

28

1.3.5.

Minimisation Problems

31

1.3.6.

Big-M Method/Primal-Penalty Method

33

1.3.7.

Special Types of LPP in Simplex Method

35

1.3.7.1.

Infeasibility

35

1.3.7.2.

Unboundedness

37

1.3.7.3.

Multiple Optimal Solutions

38

1.3.7.4.

Degeneracy

38

1.4.

Duality

40

1.4.1.

Introduction

40

1.4.2.

Primal and Dual Problem

40

1.4.3.

Relationship between Primal and Dual

40

1.4.4.

Principles of Duality

41

1.4.5.

Economic Interpretation of Duality

43

1.4.5.1.

Economic Interpretation of Dual Variables

43

1.4.5.2.

Economic Interpretation of Dual Constraints

43

1.5.

Post Optimality /Sensitivity Analysis

44

1.5.1.

Introduction

44

1.5.2.

Effects on an LP Model by Sensitivity Analysis

44

1.5.3.

Graphical Approach to Sensitivity Analysis

44

1.5.3.1.

Changes in Objective Function Coefficients

45

1.5.3.2.

Changes in Right-Hand-Side(RHS) Values (Constraints)

45

1.5.3.3.

Shadow Prices

46

1.5.4.

Simplex Method Approach to Sensitivity Analysis

46

1.5.4.1.

Addition of Variables

47

1.5.4.2.

Deletion of Variables

47

1.5.4.3.

Addition of Constraints

49

1.5.4.4.

Deletion of Constraints

49

1.6.

Exercise

50

Chapter 2: Transportation Problems

2.1.

Transportation Problems (TP)

53

2.1.1.

Introduction

53

2.1.2.

Mathematical Formulation of Transportation Problem

53

2.1.3.

Assumptions in Transportation Problem

54

2.1.4.

Terminologies Used in Transportation Problem

54

2.1.5.

Transportation Algorithm

55

2.1.6.

Applications of Transportation Model

55

2.1.7.

Transportation Methods for Finding Initial Solutions

55

2.1.7.1.

North-West Corner Method (NWCM)

55

2.1.7.2.

Least Cost / Matrix Minima Method

58

2.1.7.3.

Vogel’s Approximation Method (VAM)

60

2.1.8.

Test for Optimality Using Modified Distribution Method (MODI) Method

62

2.1.8.1.

Steps of MODI Method

63

2.1.8.2.

Loops in Transportation Table

64

2.1.9.

Special Cases in Transportation Problems

71

2.1.9.1.

Balanced Transportation Problems

72

2.1.9.2.

Unbalanced Transportation Problems

73

2.1.9.3.

Minimisation Transportation Problems

76

2.1.9.4.

Maximisation Transportation Problem

77

2.1.9.5.

Degeneracy in Transportation Problems

82

2.2.

Exercise

84

Chapter 3: Assignment Problems

3.1.

Assignment Problems

85

3.1.1.

Introduction

85

3.1.2.

Mathematical Statement of the Problem

85

3.1.3.

Applications of Assignment Model

85

3.1.4.

Hungarian Method of Solution

86

3.1.5.

Special Cases in Assignment Problems

87

3.1.5.1.

Balanced Assignment Problems

88

3.1.5.2.

Unbalanced (Non Square Matrix) Assignment Problems

89

3.1.5.3.

Minimisation Assignment Problems

91

3.1.5.4.

Maximisation Assignment Problems

93

3.1.5.5.

Multiple Optimal Solutions

95

3.1.5.6.

Restrictions on Assignment Problems/ Restricted Assignment Problems

98

3.1.5.7.

Traveling Salesman’s Model (Or Routing Problem)

100

3.1.6.

Difference between Transportation and  Assignment Problem

101

3.2.

Exercise

102

Chapter 4: Theory of Games

4.1.

Theory of Games/Game Theory

104

4.1.1.

Introduction

104

4.1.2.

Concept of Game

104

4.1.3.

Competitive Situations

104

4.1.4.

Terminology of Game

105

4.1.5.

Assumptions of Game

105

4.1.6.

Saddle Point

105

4.1.7.

Value of Game

106

4.1.8.

Strategies of Game

106

4.1.8.1.

Pure Strategy

107

4.1.8.2.

Mixed Strategy

107

4.1.9.

Solutions of Game

107

4.1.10.

Advantages of Game Theory

107

4.1.11.

Disadvantages of Game Theory

108

4.1.12.

Application of Game Theory

108

4.1.13.

Types of Game

108

4.2.

Two Person Zero-Sum Game

109

4.2.1.

Introduction

109

4.2.2.

Payoff Matrix

109

4.2.3.

Assumptions of  Two Person Zero Sum Game

110

4.2.4.

Pure Strategies - Games with Saddle Points: Minimax & Maximin Criteria

110