Operations Research

Transportation Problem

The transportation problem is a special type of linear programming problem that deals with finding the optimal way to transport goods from a set of sources (like factories or warehouses) to a set of destinations (like retail stores or customers). The goal is to minimize the total transportation cost while satisfying the supply at each source and the demand at each destination.

Key Components:

• Sources: Locations where the goods originate.
• Destinations: Locations where the goods are needed.
• Supply: The quantity of goods available at each source.
• Demand: The quantity of goods required at each destination.
• Transportation Cost: The cost of transporting one unit of goods from a specific source to a specific destination.

Mathematical Formulation:

Let x_ij be the number of units transported from source i to destination j.

Minimize Total Cost = Σ_i Σ_j c_ij x_ij

Subject to:

• Σ_j x_ij ≤ S_i (Supply constraint for each source i)
• Σ_i x_ij ≥ D_j (Demand constraint for each destination j)
• x_ij ≥ 0 (Non-negativity constraint)

Where c_ij is the cost per unit from source i to destination j, S_i is the supply at source i, and D_j is the demand at destination j.

Balanced vs. Unbalanced Transportation Problem:

A transportation problem is balanced if the total supply equals the total demand (ΣS_i = ΣD_j). If they are not equal, it is unbalanced. An unbalanced problem can be balanced by introducing a dummy source or a dummy destination with zero supply or demand and zero transportation costs.

Methods for Finding Initial Basic Feasible Solution:

Before finding the optimal solution, we need an initial basic feasible solution (IBFS). Common methods include:

• North-West Corner Method: Starts allocation from the top-left cell of the transportation table and proceeds row by row or column by column. It's simple but often yields a poor initial solution.
• Least Cost Method (or Matrix Minima Method): Allocates as much as possible to the cell with the lowest transportation cost first, then moves to the next lowest cost cell, considering supply and demand constraints. It generally gives a better initial solution than the North-West Corner Method.
• Vogel's Approximation Method (VAM): This is usually the best method for obtaining a good initial solution. It calculates the "penalty" or "opportunity cost" for each row and column by finding the difference between the two lowest costs. Allocations are made to the cell with the lowest cost in the row/column with the highest penalty.

Methods for Finding Optimal Solution:

Once an IBFS is obtained, we use methods to check for optimality and improve the solution if it's not optimal:

• Stepping Stone Method: A method that iteratively improves the solution by identifying negative cost cycles in the transportation tableau.
• Modified Distribution (MODI) Method: A more efficient method than the Stepping Stone method. It uses dual variables (potentials) to evaluate unoccupied cells and identify potential cost reductions.

Queuing Theory (Waiting Line Theory)

Queuing theory is the mathematical study of waiting lines, or queues. It analyzes systems where customers (or jobs, or requests) arrive, wait for service, receive service, and then leave. The objective is to balance the cost of providing service with the cost of waiting.

Key Components:

• Arrival Process: Describes how customers arrive. Often modeled using a Poisson distribution.
• Service Mechanism: Describes how service is provided. This includes the number of servers and the service time distribution (often exponential).
• Queue Discipline: The rule by which customers are selected for service (e.g., First-Come, First-Served (FCFS), Last-Come, First-Served (LCFS), Priority).
• System Capacity: The maximum number of customers allowed in the system (finite or infinite).
• Calling Population: The size of the group from which customers arrive (finite or infinite).

Kendall's Notation:

A standard notation used to classify queuing models: A/B/c/K/N/D

• A: Arrival distribution (M for Markovian/Poisson, D for Deterministic, G for General)
• B: Service time distribution (M, D, G)
• c: Number of parallel servers
• K: System capacity (default is infinite)
• N: Calling population size (default is infinite)
• D: Queue discipline (FCFS, LCFS, SI for Service In Random Order, PR for Priority)

The most common model is M/M/1 (Poisson arrivals, exponential service times, single server, infinite capacity, infinite population, FCFS discipline).

Key Performance Measures:

• λ (Lambda): Average arrival rate (customers per unit time).
• μ (Mu): Average service rate (customers per unit time, per server).
• ρ (Rho): Server utilization factor (traffic intensity) = λ / (cμ). For stability, ρ < 1.
• L_s: Average number of customers in the system (waiting + being served).
• L_q: Average number of customers in the queue (waiting).
• W_s: Average time a customer spends in the system (waiting + service).
• W_q: Average time a customer spends waiting in the queue.

Common Queuing Models and Formulas (M/M/1):

For the M/M/1 model (λ < μ):

• Utilization: ρ = λ / μ
• Average number in system: L_s = λ / (μ - λ) = ρ / (1 - ρ)
• Average number in queue: L_q = λ² / (μ(μ - λ)) = ρ² / (1 - ρ)
• Average time in system: W_s = 1 / (μ - λ)
• Average time in queue: W_q = λ / (μ(μ - λ)) = ρ / (μ(1 - ρ))

Little's Law states: L_s = λW_s and L_q = λW_q. This holds for any stable queue.

M/M/c Model (Multiple Servers):

This model involves c parallel servers. Formulas for L_s, L_q, W_s, W_q are more complex and involve probabilities of zero or more customers in the system.

Utilization: ρ = λ / (cμ)

The probability of having n customers in the system (P_n) depends on ρ and the ratio λ/μ.

Decision Theory

Decision theory provides a framework for making optimal decisions under conditions of uncertainty. It involves identifying possible alternatives, possible future states of nature, and the outcomes (payoffs) associated with each combination of alternative and state of nature.

Key Components:

• Decision Alternatives: The choices available to the decision-maker.
• States of Nature: Future events beyond the decision-maker's control that can affect the outcome.
• Payoff: The outcome (profit, cost, utility) resulting from a particular decision alternative and a particular state of nature.
• Decision Criteria: Rules used to select the best decision alternative based on the payoffs and the decision-maker's attitude towards risk.

Types of Decision Environments:

• Decision Making Under Certainty: Each state of nature has only one possible outcome. (Rarely encountered in real-world business).
• Decision Making Under Risk: The probability of each state of nature occurring is known.
• Decision Making Under Uncertainty: The probabilities of the states of nature are unknown.

Decision Criteria (Under Uncertainty):

When probabilities are unknown, several criteria can be used:

• Maximax Criterion (Optimistic): Choose the alternative that maximizes the maximum possible payoff. Selects the best of the best.
• Maximin Criterion (Pessimistic): Choose the alternative that maximizes the minimum possible payoff. Selects the best of the worst.
• Minimax Regret Criterion (Savage Criterion): Choose the alternative that minimizes the maximum possible regret. Regret is the difference between the payoff you received and the maximum payoff you could have received for that state of nature.
• Laplace Criterion (Equally Likely): Assumes all states of nature are equally likely and chooses the alternative with the maximum average payoff.

Decision Criteria (Under Risk):

When probabilities are known:

• Expected Monetary Value (EMV): Calculate the weighted average of payoffs for each alternative, using the probabilities of the states of nature as weights. Choose the alternative with the highest EMV (for profit) or lowest EMV (for cost).
• Expected Opportunity Loss (EOL): Similar to Minimax Regret but uses probabilities. Calculate the expected regret for each alternative and choose the one with the minimum EOL. EOL is often used to measure the efficiency of a decision rule.
• Expected Value of Perfect Information (EVPI): The difference between the expected payoff under certainty (using the best possible decision for each state of nature) and the EMV of the best decision under risk. It represents the maximum amount a decision-maker would pay for perfect information. EVPI = Expected Payoff with Perfect Information - Maximum EMV.

Decision Trees:

Decision trees are graphical tools used to visualize and analyze sequential decisions under risk. They use nodes (squares for decisions, circles for chance events) and branches to represent alternatives, states of nature, probabilities, and payoffs. Analysis proceeds from right to left, using EMV to determine optimal decisions at each decision node.

Program Evaluation and Review Technique (PERT) and Critical Path Method (CPM)

PERT and CPM are project management techniques used for planning, scheduling, and controlling complex projects. They help determine the minimum time required to complete a project and identify the activities that are critical to meeting that completion time.

Key Concepts:

• Activities: Specific tasks or steps required to complete the project.
• Events/Nodes: Points in time that mark the beginning or end of an activity.
• Network Diagram: A graphical representation of the project, showing the sequence of activities and their dependencies. There are two main types:
• Activity-on-Arrow (AOA): Activities are represented by arrows, and events by nodes.
• Activity-on-Node (AON) / Precedence Diagramming Method (PDM): Activities are represented by nodes, and dependencies by arrows. This is more common today.
• Precedence Relationships: The order in which activities must be performed (e.g., Finish-to-Start, Start-to-Start, Finish-to-Finish, Start-to-Finish).

CPM vs. PERT:

• CPM: Assumes activity times are deterministic (fixed and known). Used for projects with well-defined tasks, like construction.
• PERT: Assumes activity times are probabilistic (estimated using three time estimates: optimistic, most likely, pessimistic). Used for research and development projects where uncertainty is high.

Time Estimates (PERT):

For each activity, PERT uses three time estimates:

• Optimistic Time (t_o): The shortest possible time to complete the activity.
• Most Likely Time (t_m): The time most realistically expected to complete the activity.
• Pessimistic Time (t_p): The longest possible time to complete the activity.

Expected Activity Time (t_e): Calculated using a weighted average:

t_e = (t_o + 4t_m + t_p) / 6

Activity Variance (σ²): Measures the uncertainty in the activity time:

σ² = [(t_p - t_o) / 6]²

Activity Standard Deviation (σ): The square root of the variance.

Calculations for Both PERT and CPM:

The following time calculations are performed for each activity:

• Earliest Start Time (ES): The earliest an activity can begin, based on the completion of its preceding activities.
• Earliest Finish Time (EF): The earliest an activity can be completed. EF = ES + Activity Time (t_e for PERT, or deterministic time for CPM).
• Latest Finish Time (LF): The latest an activity can be completed without delaying the project completion time.
• Latest Start Time (LS): The latest an activity can begin without delaying the project completion time. LS = LF - Activity Time.

Calculating ES and EF:

ES for the first activity is usually 0. For any subsequent activity, its ES is the maximum EF of all its immediate predecessors.

EF = ES + Activity Time

Calculating LF and LS:

LF for the last activity is its EF (the project completion time). For preceding activities, LF is the minimum LS of all activities that immediately follow it.

LS = LF - Activity Time

Calculating Slack (or Float):

Slack is the amount of time an activity can be delayed without affecting the project completion date.

Slack = LF - EF = LS - ES

Critical Path:

The critical path is the sequence of activities with zero slack. These activities are critical because any delay in them will directly delay the entire project. The length of the critical path determines the minimum project completion time.

Project Completion Time Probability (PERT):

The total project variance is the sum of the variances of the activities on the critical path.

Project Standard Deviation (σ_project) = √(Sum of variances of critical activities)

We can then calculate the probability of completing the project by a certain date using the normal distribution (Z-score):

Z = (Target Date - Project Completion Time) / σ_project

Resource Leveling and Crashing:

Resource Leveling: Adjusting the project schedule to resolve resource conflicts and reduce fluctuations in resource demand, potentially extending the project duration.

Crashing: Shortening the project duration by adding resources or performing activities in parallel, usually increasing costs. It involves identifying critical activities with the lowest cost per unit of time reduction.

Example Scenario (AON):

Consider activities A, B, C, D, E with dependencies and times:

• A (3 days) - Starts first
• B (2 days) - Depends on A
• C (4 days) - Depends on A
• D (5 days) - Depends on B
• E (2 days) - Depends on C and D

Forward Pass (ES, EF):

• A: ES=0, EF=0+3=3
• B: ES=EF(A)=3, EF=3+2=5
• C: ES=EF(A)=3, EF=3+4=7
• D: ES=EF(B)=5, EF=5+5=10
• E: ES=max(EF(C), EF(D)) = max(7, 10) = 10, EF=10+2=12

Project Duration = 12 days. Critical Path is A → B → D → E.

Backward Pass (LF, LS): (Assuming project must finish by day 12)

• E: LF=12, LS=12-2=10
• D: LF=LS(E)=10, LS=10-5=5
• C: LF=LS(E)=10, LS=10-4=6
• B: LF=LS(D)=5, LS=5-2=3
• A: LF=min(LS(B), LS(C)) = min(3, 6) = 3, LS=3-3=0

Slack:

• A: LF-EF = 3-3 = 0
• B: LF-EF = 5-5 = 0
• C: LF-EF = 10-7 = 3
• D: LF-EF = 10-10 = 0
• E: LF-EF = 12-12 = 0

Activities A, B, D, E form the critical path as they have zero slack.