Essential Concepts in Operations Research: Theory and Techniques
Characteristics and components of Game Theory
Game Theory : Mathematical framework for analyzing strategic decision-making situations where outcome depends on actions of multiple decision makers.
Characteristics:
1. Multiple Decision Makers:Called players, Each has conflicting interests, Rational decision makers
2. Strategies:Complete plan of action, Available alternatives for each player, Pure vs mixed strategies 3. Payoffs: Outcomes resulting from strategy combinations, Usually represented in payoff matrix, Can be profits, costs, utilities 4. Information: Complete or incomplete information, Perfect or imperfect information
Components of a Game:
1. Players:, Participants in the game, Can be individuals, companies, countries 2. Strategies:Pure Strategy: Specific definite course of action, Mixed Strategy: Probabilistic combination of pure strategies
3. Payoff Matrix: Shows outcomes for each combination of strategies, Rows represent Player A’s strategies, Columns represent Player B’s strategies 4. Solution:Optimal strategy for each player, Equilibrium point
Game Theory Types with Examples
Two-Person Zero-Sum Games
These are competitive games involving two players where one’s gain equals the other’s loss, so the total payoff is always zero. The game is represented in a payoff matrix showing the gain of one player (say A) and loss of the other (B). Example:
[ 2 -1 ]
[ -3 4 ] If A selects Row 1 and B selects Column 1, A gains 2 and B loses 2.
Pure Strategy Games (Saddle Point)
In pure strategies, players consistently choose one strategy. The solution exists if there is a saddle point, which occurs when the maximin (maximum of row minima) equals the minimax (minimum of column maxima).
Example:[ 3 1 ]
[ 2 4 ] Row minima = (1, 2), so maximin = 2.
Column maxima = (3, 4), so minimax = 3.
Since maximin ≠ minimax, no saddle point. If equal, that value would be the game’s solution.
Dominance Principle
This method simplifies the matrix by removing dominated strategies (a row or column always giving worse payoffs than another). It reduces large games into smaller ones before solving. Example:
[ 2 5 3 ]
[ 4 6 5 ] Row 1 is dominated by Row 2 (all elements smaller), so Row 1 can be eliminated.
Mixed Strategy Games (2×2 case)
When no saddle point exists, players adopt mixed strategies, choosing options with certain probabilities to minimize losses or maximize gains. Probabilities are found by equating expected payoffs of the opponent. Example:
[ 2 -1 ]
[ -3 4 ] Player A plays Row 1 with probability p=0.5 and Row 2 with 0.5.
Player B plays Col 1 with q=0.5 and Col 2 with 0.5.
Value of the game = 0.5.
Mixed Strategies (m×2 or 2×n, Graphical/Algebraic)
For larger games, if one player has only two strategies, the problem can be solved using the graphical method. The expected payoffs are plotted against the probability of one player’s strategy, and the intersection point gives the equilibrium mixed strategy and value of the game. Example:
[ 2 6 ]
[ 4 2 ]
[ 5 3 ] Player B has 2 strategies, so expected payoffs for A’s strategies are plotted against B’s probability. The lowest envelope of these lines gives the solution.
Kendall’s Notation for Queueing Model:
is a widely used system for describing and categorizing different types of queueing models or systems. Queueing theory is a branch of operations research and applied mathematics that deals with the study of waiting lines or queues in various real-world situations, such as customer service, traffic engineering, and computer systems. Kendall’s Notation provides a standardized way to represent key characteristics of a queueing system using a compact notation.
The notation consists of three or four components:
1. A/B/c/d notation: – A
Arrival process, describing how customers arrive at the queue (e.G., M for Poisson arrivals, D for deterministic arrivals).
– B:
Service process, indicating how customers are served (e.G., M for exponential service times, D for deterministic service times).
– c:
Number of service channels (servers) available to process customers.
– d (optional): Maximum queue length or system capacity (finite or infinite).
For example, in the notation “M/M/1,” it signifies a system with Poisson arrivals (M), exponential service times (M), and a single server (1). In “M/M/1/K,” the ‘K’ indicates a finite system capacity, meaning there can be at most ‘K’ customers in the queue.
Queuing theory,also known as the theory of queues, is a branch of operations research and applied mathematics that studies the behavior of waiting lines or queues in various real-world scenarios. Queues are a common occurrence in everyday life, from people waiting in line at a grocery store to data packets queuing up in a computer network. Queuing theory provides a systematic framework for analyzing and optimizing the performance of systems involving waiting and congestion.
Components of a Queuing System (Major Points):
1.Arrival/Input Process – Source of customers and arrival rate (λ)
2.Queue/Waiting Line – Where customers wait; includes queue discipline (FIFO, LIFO, Priority) 3.Service Mechanism – Server(s) providing service; service rate (𝜇) 4.Number of Servers – Single or multiple 5.System Capacity – Maximum customers allowed
6.Exit/Departure – Customers leave after service 7. Population Source – Finite or infinite number of potential customers
Tools and techniques of operational research
Operational Research (OR)
is a discipline that uses mathematical and analytical methods to solve complex decision-making problems in various fields, including management, engineering, logistics, economics, and more. Here are some of the key tools and techniques commonly used in operational research:
Operational Research (OR) encompasses a diverse set of tools and techniques used to solve complex decision-making problems.
1.
Linear Programming (LP): is a mathematical optimization method for solving problems with linear relationships. It’s used for resource allocation, production planning, and logistics optimization.
2. Integer Programming (IP):- It extends LP by allowing decision variables to take integer values, addressing problems where solutions must be discrete, such as project scheduling.
3. Queuing Theory: analyzes waiting lines and is crucial for optimizing customer service in areas like call centers, healthcare, and traffic management.
4. Simulation: involves creating models of real-world systems to understand their behavior and optimize performance, commonly used in manufacturing, transportation, and healthcare.
5. Dynamic Programming (DP): breaks complex problems into smaller, simpler subproblems, making it ideal for optimizing sequences and decisions over time, such as project management and inventory control.
Duality in LP is a concept that plays a crucial role in optimization theory and has several important advantages/importance:
1.Optimality Verification:
#Duality allows checking if a solution to the primal problem is optimal. #If the optimal values of the primal and dual problems are equal, it confirms the solution’s correctness.
2.Sensitivity and Resource Insight:
#Dual variables (shadow prices) indicate the marginal value of resources or constraints. #Helps understand how changes in resources or coefficients affect the optimal solution.
3.Bounding and Benchmarking:
#Duality provides upper and lower bounds for the objective values. #The difference (duality gap) indicates how close a solution is to optimality.
4.Efficiency in Computation:
#The dual problem is often smaller or simpler than the primal, making computations faster for large-scale problems.
5.Decision-Making and Problem Formulation:
#Solving the dual can guide resource allocation, pricing, or other strategic decisions. #It can also inspire new optimization formulations or improve existing algorithms.
EOQ (Economic Order Quantity)
EOQ is the order quantity that minimizes the total inventory costs, which consist of ordering costs and holding (carrying) costs. It is the most economical batch size to order when restocking inventory.
Components of EOQ: #Demand (D):
The total demand for the product over a specific time period, usually a year.
#Ordering Cost (S)
The cost incurred each time an order is placed. This includes costs like paperwork, processing, and transportation.
#Holding Cost per Unit (H)
The cost incurred to hold one unit of
inventory for a year. This includes costs such as storage, insurance, and opportunity cost of tied-up capital.
EOQ Formula:
The EOQ is calculated using the EOQ formula:
EOQ = √((2 * D * S) / H)
Objective:**
The primary objective of using EOQ is to find the order quantity that minimizes the total annual inventory cost, which is the sum of ordering costs and holding costs.
ABC Classification of Inventory Management (ABC Analysis):
ABC classification is a widely used technique in inventory management to categorize items or products into three categories (A, B, and C) based on their importance or value. This classification helps organizations allocate resources and prioritize their inventory management efforts more
effectively.
– A-Class Items:
These are the most important and valuable items in terms of cost, revenue, or criticality. Typically, A-class items represent a small portion of the total inventory but contribute significantly to the overall value or profit. They require close monitoring and tight control.
– B-Class Items:
B-class items are moderately important and occupy a middle ground between A and C items in terms of value and significance. They constitute a larger portion of the inventory than A-class items but are not as critical. They need regular monitoring but may not require the same level of attention as A-class items.
– C-Class Items:
C-class items are the least important and valuable items in the inventory. They represent a significant portion of the inventory in terms of quantity but contribute less to the overall value or profit. C-class items are typically low-cost items with lower significance, and they may require minimal management effort.
ABC classification allows organizations to allocate resources and
management focus appropriately, ensuring that the most critical items
receive the most attention while optimizing inventory costs.