Historical Background

Operations Research emerged during World War II when military planners needed scientific methods for complex strategic and tactical problems. After the war, these techniques were adopted by industries for operational efficiency.

Real-World Applications

• Manufacturing optimization
• Supply chain and logistics management
• Financial portfolio management
• Healthcare systems optimization
• Transportation scheduling
• Resource allocation in various industries

Standard Form Example

Maximize: Z = 3x + 4y

Subject to:

• x + 2y ≤ 10
• 3x + y ≤ 15
• x, y ≥ 0

1. Graphical Method (for 2 variables)

1. Plot the constraints on a coordinate system
2. Identify the feasible region (area satisfying all constraints)
3. Find corner points (vertices) of the feasible region
4. Evaluate the objective function at each corner point
5. Select the point giving the optimal objective value

2. Simplex Method

A systematic algebraic procedure for finding the optimal solution by moving from one feasible corner point to another while improving the objective function value.

3. Interior Point Methods

Algorithms that reach an optimal solution by traversing the interior of the feasible region rather than along its edges.

Practical Example: Product Mix Problem

Scenario: A furniture manufacturer produces chairs and tables. Each chair requires 5 hours of carpentry and 2 hours of finishing. Each table requires 10 hours of carpentry and 3 hours of finishing. The workshop has 100 hours available for carpentry and 36 hours for finishing per week. The profit is $25 per chair and $30 per table.

Formulation:
Let x = number of chairs produced
Let y = number of tables produced

Maximize: Z = 25x + 30y (profit)

Subject to:

• 5x + 10y ≤ 100 (carpentry constraint)
• 2x + 3y ≤ 36 (finishing constraint)
• x, y ≥ 0 (non-negativity)

Solution:
Using the simplex method or graphical method, we find the optimal solution is x = 12 chairs and y = 4 tables, giving a maximum profit of $420.

Example Formulation

Maximize: Z = 5x + 7y

Subject to:

• 2x + 3y ≤ 12
• 3x + 2y ≤ 12
• x, y ≥ 0 and integer

1. Branch and Bound

A systematic approach that:

1. Solves the LP relaxation (ignoring integer constraints)
2. If the solution has non-integer values, branches the problem into subproblems by adding constraints
3. Continues branching and solving until finding the optimal integer solution

2. Cutting Plane Method

Adds constraints ("cuts") to the LP relaxation to eliminate non-integer solutions, gradually forcing the solution toward integer values.

3. Branch and Cut

A hybrid approach combining branch and bound with cutting planes for improved efficiency.

4. Dynamic Programming

For certain integer programming problems, especially those with a recursive structure.

Practical Example: Facility Location Problem

Scenario: A company needs to decide which of 3 potential warehouse locations to open to serve 5 customers with minimum cost. Each warehouse has a fixed opening cost and variable costs to serve each customer.

Formulation:
Let y_j = 1 if warehouse j is opened, 0 otherwise
Let x_ij = 1 if customer i is served by warehouse j, 0 otherwise

Minimize: Z = Σ f_jy_j + Σ c_ijx_ij (fixed costs + variable costs)

Subject to:

• Σ x_ij = 1 for all i (each customer must be served)
• x_ij ≤ y_j for all i,j (can only serve from open warehouses)
• x_ij, y_j ∈ {0,1} (binary variables)

1. Shortest Path Problem

Finding the path between two nodes with minimum total distance or cost.

Solution Methods:

• Dijkstra's Algorithm: For networks with non-negative arc costs
• Bellman-Ford Algorithm: Can handle negative arc costs (but not negative cycles)

2. Minimum Spanning Tree

Finding a tree (a connected subgraph with no cycles) that connects all nodes with minimum total cost.

Solution Methods:

• Kruskal's Algorithm: Starts with no edges and adds the lowest-cost edge that doesn't create a cycle
• Prim's Algorithm: Starts with a single node and gradually grows the tree

3. Maximum Flow Problem

Determining the maximum flow that can be sent from a source to a sink through a network with capacity constraints.

Solution Methods:

• Ford-Fulkerson Algorithm: Iteratively finds augmenting paths and increases flow
• Edmonds-Karp Algorithm: A specific implementation of Ford-Fulkerson

4. Minimum Cost Flow Problem

Finding the cheapest way to send a specified amount of flow through a network with capacity and cost on each arc.

Solution Methods:

• Network Simplex Algorithm: A specialized version of the simplex method
• Successive Shortest Path Algorithm: Repeatedly finds shortest paths and pushes flow

5. Transportation Problem

Determining how to distribute goods from multiple sources to multiple destinations at minimum cost.

Solution Methods:

• Northwest Corner Method: A simple method to find an initial basic feasible solution
• Vogel's Approximation Method: A more sophisticated approach for initial solution
• Modified Distribution (MODI) Method: An optimality test and improvement procedure

6. Assignment Problem

Assigning n workers to n jobs in the most efficient way.

Solution Methods:

• Hungarian Algorithm: An efficient combinatorial optimization algorithm

Practical Example: Critical Path Method (CPM) for Project Scheduling

Scenario: A construction project consists of several activities with specified durations and precedence relationships. We need to determine the minimum project completion time and identify critical activities.

Activity	Duration (days)	Predecessors
A	5	-
B	3	-
C	4	A
D	6	B
E	2	C, D

Solution Process:

1. Create a network diagram showing activities and their dependencies
2. Calculate earliest start (ES) and earliest finish (EF) times by forward pass
3. Calculate latest start (LS) and latest finish (LF) times by backward pass
4. Calculate float (slack) for each activity: LS - ES or LF - EF
5. Identify critical activities (those with zero float)
6. The critical path is the sequence of critical activities, and its length determines the minimum project duration

Result: The critical path is A → C → E with a project duration of 11 days.

Basic Queue Performance Measures

• λ: Average arrival rate
• μ: Average service rate per server
• ρ = λ/(cμ): System utilization (traffic intensity)
• L_q: Average number of customers in queue
• L_s: Average number of customers in system
• W_q: Average waiting time in queue
• W_s: Average time spent in system

Little's Law: L = λW (The average number in the system equals the arrival rate times the average time in the system)

1. M/M/1 Queue (Single Server, Exponential Arrivals and Service)

Formulas (for stable systems where ρ < 1):

• ρ = λ/μ
• L_s = ρ/(1-ρ)
• L_q = ρ²/(1-ρ)
• W_s = 1/(μ-λ)
• W_q = λ/[μ(μ-λ)]

2. M/M/c Queue (Multiple Servers, Exponential Arrivals and Service)

A more complex model with c servers that requires special formulas involving Erlang's C formula.

3. M/G/1 Queue (General Service Times)

Pollaczek-Khinchin Formula for average waiting time:

W_q = (λ × E[S²]) / (2 × (1 - ρ))

where E[S²] is the second moment of service time.

4. G/G/1 Queue (General Arrivals and Service)

Requires approximation formulas or simulation for analysis.

Practical Example: Bank Teller Analysis

Scenario: A bank has a single teller. Customers arrive at an average rate of 15 per hour (Poisson distribution). The teller takes an average of 3 minutes to serve each customer (exponentially distributed).

Solution:

• Arrival rate: λ = 15 customers/hour
• Service rate: μ = 60/3 = 20 customers/hour
• Traffic intensity: ρ = λ/μ = 15/20 = 0.75
• Average number in system: L_s = ρ/(1-ρ) = 0.75/(1-0.75) = 3 customers
• Average waiting time in queue: W_q = ρ/(μ-λ) = 0.75/(20-15) = 0.15 hours = 9 minutes
• Average time in system: W_s = 1/(μ-λ) = 1/(20-15) = 0.2 hours = 12 minutes

Analysis: With a single teller, customers wait an average of 9 minutes in the queue before being served. If this is deemed too long, the bank might consider adding a second teller.

1. Economic Order Quantity (EOQ) Model

Basic model assuming constant demand rate, instantaneous replenishment, and no stockouts.

2. Production Order Quantity (POQ) Model

Extension of EOQ where replenishment is not instantaneous but occurs at a finite rate.

3. EOQ with Planned Shortages

Allows for planned stockouts when it is cheaper to have occasional shortages than to hold excess inventory.

4. Quantity Discount Model

Incorporates price discounts for larger order quantities.

5. Probabilistic Inventory Models

Models with uncertain demand, including:

• Newsvendor (Single-Period) Model: For perishable items or single selling seasons
• Continuous Review (Q,R) Model: Orders Q units when inventory level drops to reorder point R
• Periodic Review (s,S) Model: Reviews inventory at fixed intervals and orders up to S when level is below s

Practical Example: EOQ Model Application

Scenario: A retail store sells 10,000 units of a product annually. The ordering cost is $50 per order. The annual holding cost is $2 per unit. The unit purchase price is $20.

Solution:

Given:
D = 10,000 units/year
S = $50 per order
H = $2 per unit per year
P = $20 per unit

Step 1: Calculate EOQ
Q* = √(2DS/H) = √(2 × 10,000 × 50 / 2) = √500,000 = 707 units

Step 2: Calculate number of orders per year
N = D/Q* = 10,000/707 ≈ 14.14 orders/year

Step 3: Calculate time between orders
T* = Q*/D = 707/10,000 = 0.0707 years ≈ 25.8 days

Step 4: Calculate total annual cost
TC = PD + (D/Q*)S + (Q*/2)H
TC = 20 × 10,000 + (10,000/707) × 50 + (707/2) × 2
TC = 200,000 + 707 + 707 = $201,414

Conclusion: The store should order 707 units every 25.8 days, resulting in a total annual inventory cost of $201,414 (including purchase cost).

Random Number Generation

Simulation often requires generating random numbers from specific probability distributions:

• Uniform Distribution: Basic random numbers between 0 and 1
• Other Distributions: Generated using techniques like inverse transform, acceptance-rejection, etc.

Common techniques:

• Inverse Transform: If F(x) is the CDF, then F^-1(U) gives a random variate from the distribution, where U is uniform(0,1)
• Box-Muller Transform: For generating normal random variables
• Acceptance-Rejection: For complex distributions without closed-form inverse CDFs

1. Entities and Attributes

Entities are the objects being processed in the system (customers, products). Attributes are their characteristics (arrival time, service needs).

2. Activities and Events

Activities consume time (service, transport). Events are instantaneous occurrences that change the system state (arrival, departure).

3. State Variables

Variables that describe the system at any point in time (queue length, server status).

4. Random Variates

Random values drawn from probability distributions to model uncertainty.

5. Statistical Analysis

Techniques to analyze simulation outputs, including:

• Confidence intervals
• Hypothesis testing
• Variance reduction techniques
• Warm-up period determination
• Run length determination

Practical Example: Bank Simulation

Scenario: A bank has two tellers. Customers arrive according to a Poisson process with a mean of 20 per hour. Service times follow an exponential distribution with a mean of 5 minutes.

Simulation Approach:

1. Generate random inter-arrival times using an exponential distribution with mean 3 minutes (60/20)
2. Generate random service times using an exponential distribution with mean 5 minutes
3. Track the system state (queue length, teller status) as customers arrive and depart
4. Collect statistics on waiting times, queue lengths, and teller utilization

Pseudocode for Discrete-Event Simulation:

Initialize:
  Clock = 0
  TellerStatus = [IDLE, IDLE]
  Queue = empty
  EventList = [first customer arrival]
  Statistics = initialize all counters

While simulation time not reached:
  Get next event E from EventList
  Advance Clock to E.time
  If E is an arrival:
    Schedule next arrival
    If any teller is IDLE:
      Assign customer to idle teller
      Schedule a departure
    Else:
      Add customer to Queue
  If E is a departure:
    Mark teller as IDLE
    If Queue not empty:
      Get next customer from Queue
      Assign to freed teller
      Schedule a departure
  Update statistics

Calculate final statistics and results
            

Sample Results:

• Average waiting time: 4.2 minutes
• Maximum queue length: 7 customers
• Teller utilization: 83%

Conclusion: With two tellers, the system appears stable but has moderate waiting times. Management might consider adding a third teller during peak hours.

1. Expected Value Criterion

Select the alternative with the highest expected value (or lowest expected cost).

EV(Alternative i) = Σ P(j) × V(i,j) for all states of nature j

Where P(j) is the probability of state j, and V(i,j) is the value of alternative i in state j.

2. Expected Utility Criterion

Incorporates the decision maker's risk attitude by using utility functions instead of monetary values.

EU(Alternative i) = Σ P(j) × U(V(i,j)) for all states of nature j

Where U() is the utility function.

3. Mean-Variance Analysis

Considers both the expected return and the variance (risk) of each alternative.

1. Maximin (Pessimistic) Criterion

Select the alternative with the best worst-case outcome.

Maximin value = max[min V(i,j) over all j] over all i

2. Maximax (Optimistic) Criterion

Select the alternative with the best best-case outcome.

Maximax value = max[max V(i,j) over all j] over all i

3. Hurwicz Criterion

A weighted average of the Maximin and Maximax values, with α representing the optimism index.

Hurwicz value = α × max V(i,j) + (1-α) × min V(i,j) for alternative i

4. Minimax Regret Criterion

Select the alternative that minimizes the maximum regret (opportunity loss).

1. Compute the regret matrix: R(i,j) = max V(k,j) over all k - V(i,j)
2. Find the maximum regret for each alternative: max R(i,j) over all j
3. Select the alternative with the minimum maximum regret

5. Laplace Criterion (Principle of Insufficient Reason)

Assume all states of nature are equally likely and compute the expected value.

Laplace value = (Σ V(i,j) over all j) / n for alternative i, where n is the number of states

Decision Trees

A graphical representation of decision problems with sequential decisions and uncertain events:

• Decision Nodes: Points where the decision maker chooses among alternatives (represented by squares)
• Chance Nodes: Points where nature determines the outcome (represented by circles)
• Terminal Nodes: Final outcomes with associated payoffs

Decision trees are analyzed by backward induction (folding back), starting from the terminal nodes and working backward to find the optimal decision strategy.

Practical Example: Investment Decision

Scenario: An investor is considering three investment options: Stock A, Bond B, or Mutual Fund C. The payoff depends on the economic condition (Boom, Normal, or Recession).

Investment / Economy	Boom (30%)	Normal (50%)	Recession (20%)
Stock A	$20,000	$12,000	-$5,000
Bond B	$8,000	$8,000	$8,000
Mutual Fund C	$15,000	$10,000	$2,000

Analysis with Expected Value Criterion:

• E[Stock A] = 0.3 × $20,000 + 0.5 × $12,000 + 0.2 × (-$5,000) = $6,000 + $6,000 - $1,000 = $11,000
• E[Bond B] = 0.3 × $8,000 + 0.5 × $8,000 + 0.2 × $8,000 = $8,000
• E[Mutual Fund C] = 0.3 × $15,000 + 0.5 × $10,000 + 0.2 × $2,000 = $4,500 + $5,000 + $400 = $9,900

Decision: Stock A has the highest expected value at $11,000, so it would be the optimal choice under the expected value criterion.

Analysis with Maximin Criterion:

• Worst case for Stock A: -$5,000
• Worst case for Bond B: $8,000
• Worst case for Mutual Fund C: $2,000

Decision: Bond B has the best worst-case scenario at $8,000, so it would be the optimal choice for a risk-averse investor using the maximin criterion.

1. Strategic Form (Normal Form) Games

Represented as a matrix showing players, strategies, and payoffs.

2. Extensive Form Games

Represented as a tree showing the sequence of moves and information sets.

• Subgame Perfect Equilibrium: Nash equilibrium that represents rational play in every subgame
• Backward Induction: Method for finding subgame perfect equilibria in finite games of perfect information

3. Repeated Games

The same game played multiple times, allowing for strategies based on past behavior.

• Finite Repetition: Game played a known, finite number of times
• Infinite Repetition: Game played indefinitely, allowing for cooperation through the threat of future punishment
• Folk Theorem: In infinitely repeated games, any individually rational outcome can be sustained as an equilibrium

Practical Example: Prisoner's Dilemma

Scenario: Two suspects are separated and offered a deal. If one confesses and the other doesn't, the confessor goes free while the other receives a severe sentence. If both confess, they receive moderate sentences. If neither confesses, they receive light sentences for a lesser charge.

Analysis:

• For Prisoner 1:
  • If Prisoner 2 stays silent, Prisoner 1 is better off confessing (0 > -1)
  • If Prisoner 2 confesses, Prisoner 1 is better off confessing (-5 > -10)
  • Confessing is a dominant strategy for Prisoner 1
• Similarly, confessing is a dominant strategy for Prisoner 2
• Nash Equilibrium: (Confess, Confess) with payoff (-5, -5)
• Pareto Optimal Outcome: (Silent, Silent) with payoff (-1, -1)

Conclusion: This illustrates the tension between individual rationality and collective optimality. Even though both prisoners would be better off cooperating (staying silent), the Nash equilibrium is for both to defect (confess).

Business Application: This game structure applies to many business scenarios like:

• Pricing competition between duopolists
• Advertising spending decisions
• Research and development investments
• Environmental compliance

1. Top-Down Approach (Memoization)

1. Formulate the problem recursively
2. Implement the recursive solution
3. Add memoization (caching) to store results of solved subproblems
4. Retrieve results from cache when subproblems are encountered again

2. Bottom-Up Approach (Tabulation)

1. Identify the order of subproblems from smallest to largest
2. Create a table to store solutions to subproblems
3. Fill the table in a bottom-up manner (from smallest to largest subproblems)
4. Construct the final solution from the completed table

1. 1D DP (Linear State)

Problems where the state can be represented with a single variable.

Examples: Fibonacci sequence, climbing stairs problem

2. 2D DP (Matrix State)

Problems where the state needs two variables.

Examples: Grid traversal, edit distance, longest common subsequence

3. Interval DP

Problems involving intervals or subarrays.

Examples: Matrix chain multiplication, optimal binary search tree

4. Tree DP

Problems involving tree structures.

Examples: Maximum independent set in trees

5. State Compression DP

Using bit manipulation to represent states efficiently.

Examples: Traveling salesman problem, subset sum problems

Recursive Formulation

The heart of dynamic programming is finding a recursive relation. For example:

• Fibonacci: F(n) = F(n-1) + F(n-2) with F(0) = 0, F(1) = 1
• Longest Common Subsequence: LCS(i,j) = 1 + LCS(i-1,j-1) if X[i] = Y[j], else max(LCS(i-1,j), LCS(i,j-1))
• Knapsack Problem: DP[i][w] = max(val[i-1] + DP[i-1][w-wt[i-1]], DP[i-1][w]) if wt[i-1] ≤ w, else DP[i-1][w]

Practical Example: Knapsack Problem

Scenario: A thief has a knapsack with capacity W = 10 kg. There are n = 4 items with values [20, 30, 15, 25] and weights [2, 5, 3, 4] kg. The thief wants to maximize the value of items stolen without exceeding the knapsack capacity.

Dynamic Programming Approach:

1. Define subproblem: DP[i][w] = maximum value that can be obtained using a subset of first i items with a knapsack of capacity w
2. Recursive relation:
   • If w < weight[i-1], item i cannot be included: DP[i][w] = DP[i-1][w]
   • Otherwise, choose maximum of:
     • Include item i: value[i-1] + DP[i-1][w-weight[i-1]]
     • Exclude item i: DP[i-1][w]
3. Base case: DP[0][w] = 0 for all w, DP[i][0] = 0 for all i

Implementation:

// Create DP table with n+1 rows and W+1 columns
DP = new array[5][11] initialized with 0

// Fill DP table bottom-up
for i from 1 to 4:
    for w from 1 to 10:
        if weight[i-1] <= w:
            DP[i][w] = max(value[i-1] + DP[i-1][w-weight[i-1]], DP[i-1][w])
        else:
            DP[i][w] = DP[i-1][w]

// Final answer is in DP[n][W]
// DP[4][10] = 60
            

Solution: The maximum value is 60, achieved by taking items 1, 2, and 4 (values 20, 15, and 25) with weights 2, 3, and 4 kg, totaling 9 kg.

Reconstructing the Solution:

i = 4, w = 10
while i > 0 and w > 0:
    if DP[i][w] != DP[i-1][w]:  // Item i was included
        print "Include item", i
        w = w - weight[i-1]
    i = i - 1
            

Operations Research Quiz

Test your knowledge with this interactive quiz covering key OR concepts!