Operation Research (CE-604 (D)) - Unit 5 Short Notes

UNIT 5: Advanced Topics in Operations Research

1. Foundations of Operations Research

Definition & Scope

Operations Research (OR) is an interdisciplinary science applying analytical methods (mathematical modeling, statistics, algorithms) to optimize decision-making in complex systems.
Scope: Resource allocation, scheduling, logistics, strategic planning.

Phases of an OR Study

1. Problem Formulation: Define objectives, constraints, and decision variables.

2. Model Building: Develop mathematical representation (deterministic/stochastic).

3. Solution: Apply analytical/numerical methods to find optimal/near-optimal solutions.

4. Validation: Test model robustness and sensitivity.

5. Implementation: Deploy solution in real environment; monitor performance.

Modeling in OR

• Types:

  • Deterministic: All parameters known (e.g., LP).

  • Stochastic: Probabilistic parameters (e.g., queuing).

  • Static: Time-independent.

  • Dynamic: Time-dependent (multi-stage).

• Steps: Problem identification → Data collection → Model selection → Solution → Testing.

Characteristics of OR Models

• Simplicity vs. realism trade-off.

• Quantifiable objectives and constraints.

• Adaptability to changing conditions.

Limitations

• Data quality dependency.

• Oversimplification of human factors.

• High computational cost for large-scale problems.

[!TIP]

Exam Focus: Distinguish deterministic vs. stochastic models; list OR phases in order.

2. Linear Programming (LP)

Formulation

• Decision Variables: Quantities to determine (e.g., \(x_1, x_2\)).

• Objective Function: Maximize profit or minimize cost (linear).

• Constraints: Linear inequalities/equalities (resource limits).

• Assumptions:

  • Linearity: Proportionality and additivity.

  • Divisibility: Variables continuous.

  • Certainty: Coefficients known.

  • Non-negativity: \(x_i \ge 0\).

Solution Methods

• Graphical Method: For 2 variables; find feasible region, corner points.

• Simplex Method: Iterative tableau; moves from BFS to BFS improving objective.

  • Steps: Convert to standard form → Initial BFS (slack vars) → Pivot operations → Optimality test (all \(c_j - z_j \le 0\) for max).

Handling Constraints

• Big-M Method: Introduce artificial variables with large penalty \(M\).

• Two-Phase Method:

  • Phase I: Minimize sum of artificial vars to find initial BFS.

  • Phase II: Drop artificial vars, solve original LP.

Special Cases

• Degeneracy: BFS with one/more basic vars = 0. Resolved by perturbation (ε) or cycling rules.

• Unbounded Solution: Objective can increase indefinitely; occurs if entering var has all negative coefficients in column.

• Multiple Optimal Solutions: \(c_j - z_j = 0\) for non-basic var; alternate optima exist.

• Infeasible Solution: No feasible point; artificial var remains positive in Phase I.

Key Terminology

• Basic Feasible Solution (BFS): Solution satisfying constraints, with \(n\) basic vars (from \(m\) constraints) set by solving \(Bx_B = b\).

• Optimal Solution: BFS maximizing/minimizing objective.

• Slack/Surplus Variables: Added to \(\le\) (slack) or \(\ge\) (surplus) constraints to convert to equality.

[!TIP]

Common Pitfall: In simplex, if all \(c_j - z_j \ge 0\) for min problem, solution is optimal. Always check feasibility first.

3. Transportation and Assignment Problems

Transportation Problem

• Formulation: Minimize cost of shipping \(m\) origins to \(n\) destinations with supply/demand.

  • Balanced: Total supply = Total demand.

  • Unbalanced: Add dummy row/col with zero cost.

• Initial BFS Methods:

  • Northwest Corner: Start top-left, allocate min(supply, demand).

  • Least Cost: Allocate to cell with lowest cost.

  • Vogel’s Approximation (VAM): Penalty-based; most accurate initial solution.

• Optimality Test (MODI):

  • Compute \(u_i, v_j\) such that \(c_{ij} - (u_i + v_j) = 0\) for basic cells.

  • If all \(c_{ij} - (u_i + v_j) \ge 0\) (min), solution optimal.

  • Else, select most negative cell for allocation; adjust loop.

Degeneracy in Transportation

• Occurs when number of allocations \(< m+n-1\).

• Resolution: Assign tiny ε to zero-cell to complete allocations; treat as basic.

Assignment Problem

• Special case of TP: \(m = n\), one-to-one assignment, minimize cost/maximize profit.

• Hungarian Method:

  1. Row reduction: Subtract min of each row.

  2. Column reduction: Subtract min of each column.

  3. Cover zeros with min lines; if lines \(= n\), optimal; else adjust matrix.

  4. Repeat until \(n\) lines cover all zeros.

Travelling Salesman Problem (TSP)

• Formulated as assignment with additional subtour elimination constraints.

• Solution Approaches:

  • Branch and Bound: Systematically enumerate tours with bounds.

  • Heuristics: Nearest neighbor, Christofides algorithm.

[!TIP]

Exam Focus: Know VAM steps and MODI optimality condition; Hungarian method for assignment.

4. Inventory Theory

Deterministic Models: EOQ

• Assumptions: Constant demand \(D\), fixed ordering cost \(S\), holding cost \(H\) per unit/time, instantaneous replenishment.

• Derivation: Minimize TC \(= \frac{D}{Q}S + \frac{Q}{2}H\).

• EOQ Formula:

  \[ \boxed{Q^* = \sqrt{\frac{2DS}{H}}} \]

• Total Cost at EOQ: \(TC^* = \sqrt{2DSH}\).

• Number of Orders: \(N = \frac{D}{Q^*}\).

• Cycle Time: \(T = \frac{Q^*}{D}\).

• With Shortages: Allow backorders; holding cost \(H\), shortage cost \(P\).

  \[ Q^* = \sqrt{\frac{2DS}{H} \cdot \frac{H+P}{P}}, \quad \text{Max shortage} = Q^* \sqrt{\frac{H}{H+P}} \]

Stochastic Models

• Single-Period (Newsvendor): Balance overage (\(C_o\)) and underage (\(C_u\)) costs.

  \[ Q^* = F^{-1}\left(\frac{C_u}{C_u + C_o}\right) \]

  where \(F\) is demand CDF.

• Multi-Period (s, S): Order up to \(S\) when inventory \(\le s\).

• Safety Stock & Reorder Point:

  \[ \text{ROP} = \text{Lead time demand} + \text{Safety stock}, \quad \text{SS} = z \cdot \sigma_{LT} \]

  \(z\) from normal table, \(\sigma_{LT}\) std dev of lead time demand.

Cost Components

• Ordering Cost (\(S\)): Fixed per order.

• Holding Cost (\(H\)): Per unit per time (storage, insurance).

• Shortage Cost (\(P\)): Per unit short (lost sales, penalty).

[!TIP]

Common Error: In EOQ, ensure \(D, S, H\) use consistent time units (e.g., annual).

5. Queuing Theory

System Structure

• Arrival Process: Poisson (rate \(\lambda\)) or general.

• Service Mechanism: Exponential (rate \(\mu\)) or general; \(c\) servers.

• Queue Discipline: FIFO, LIFO, priority, random.

• Capacity: Finite/infinite.

• Population: Finite/infinite source.

Performance Measures

• Utilization: \(\rho = \frac{\lambda}{c\mu}\) (for \(c\) servers).

• Average Number in System: \(L\) (including service).

• Average Number in Queue: \(L_q\).

• Average Time in System: \(W\).

• Average Waiting Time: \(W_q\).

• Probability of Delay: \(P_w\) (probability customer waits).

• Relationships: \(L = \lambda W\), \(L_q = \lambda W_q\).

Standard Models (Kendall’s Notation: A/B/c)

• M/M/1: Poisson arrivals, exponential service, 1 server.

  \[ \rho = \frac{\lambda}{\mu}, \quad L_q = \frac{\rho^2}{1-\rho}, \quad W_q = \frac{\rho}{\mu-\lambda} \]

• M/M/c: \(c\) servers.

  \[ P_0 = \left[\sum_{n=0}^{c-1} \frac{(\lambda/\mu)^n}{n!} + \frac{(\lambda/\mu)^c}{c!(1-\rho)}\right]^{-1}, \quad L_q = \frac{P_0 (\lambda/\mu)^c \rho}{c!(1-\rho)^2} \]

Service Disciplines

• FIFO: First-come-first-served (most common).

• LIFO: Last-in-first-out (stack).

• Priority: Preemptive (interrupt) or non-preemptive.

• Random: Service order random.

Problem Solving Examples

• Repairman Problem: M/M/1 with \(\lambda\) = arrival rate, \(\mu\) = service rate. Idle time = \(1 - \rho\).

• Postal Clerk: Time-dependent \(\lambda(t)\); use instantaneous rates or average.

[!TIP]

Key: For M/M/1, all formulas derived from \(P_n = (1-\rho)\rho^n\). Ensure \(\rho < 1\) for steady state.

6. Network Analysis (Project Management)

PERT vs. CPM

• CPM: Deterministic activity times; cost-time trade-off (crashing).

• PERT: Probabilistic times (O, M, P); focuses on time uncertainty.

Network Diagram

• AON (Activity-on-Node): Nodes = activities, arrows = precedence.

• AOA (Activity-on-Arrow): Arrows = activities, nodes = events.

• Dummy Activity: Zero duration; used to resolve precedence in AOA.

Critical Path Method (CPM)

• Forward Pass:

  • \(ES_i = \max(EF_{\text{predecessors}})\)

  • \(EF_i = ES_i + t_i\)

• Backward Pass:

  • \(LF_i = \min(LS_{\text{successors}})\)

  • \(LS_i = LF_i - t_i\)

• Float/Slack:

  • Total Float \(TF = LS - ES = LF - EF\).

  • Free Float \(FF = ES_{\text{successor}} - EF_i\) (no delay to successors).

• Critical Path: Activities with \(TF = 0\); longest path through network.

PERT: Probabilistic Estimates

• Expected Time:

  \[ \boxed{TE = \frac{O + 4M + P}{6}} \]

• Variance:

  \[ \boxed{\sigma^2 = \left(\frac{P - O}{6}\right)^2} \]

• Project Time: Sum of \(TE\) on critical path.

• Probability Calculation:

  \[ Z = \frac{T - T_E}{\sigma_{CP}}, \quad \text{where } \sigma_{CP} = \sqrt{\sum \sigma_i^2 \text{ on CP}} \]

  Use normal table for \(P(T \le T_{\text{target}})\).

Project Crashing

• Reduce activity time by adding resources at extra cost.

• Steps: Compute crash cost per unit time; crash critical activities with lowest cost until non-critical becomes critical or cost prohibitive.

[!TIP]

Critical Path: Always check for multiple critical paths; crashing may shift critical path.

7. Game Theory

Basic Concepts

• Game: Strategic interaction with players, strategies, payoffs.

• Two-Person Zero-Sum: One’s gain = other’s loss; payoff matrix \(A\) for row player.

• Pure Strategy: Specific choice.

• Mixed Strategy: Probability distribution over strategies.

Solution Methods

• Saddle Point:

  • Maximin (row player): Maximize minimum payoff per row.

  • Minimax (column player): Minimize maximum payoff per column.

  • If maximin = minimax = \(v\), saddle point exists; value \(v\) is game value.

• Dominance:

  • Row dominance: \(a_{ik} \ge a_{jk}\) for all \(k\) → row \(i\) dominates \(j\).

  • Column dominance: \(a_{ki} \le a_{kj}\) for all \(i\) → column \(i\) dominates \(j\).

  • Reduce matrix by deleting dominated rows/columns.

• Fair Game: Value \(v = 0\) (no inherent advantage).

Mixed Strategy (2×2 without Saddle Point)

• Let row player play strategy 1 with prob \(p\), strategy 2 with \(1-p\).

• Column player indifferent:

  \[ p \cdot a_{11} + (1-p) \cdot a_{12} = p \cdot a_{21} + (1-p) \cdot a_{22} \]

  Solve for \(p\).

• Expected Payoff: \(E = p \cdot (\text{col1 payoff}) + (1-p) \cdot (\text{col2 payoff})\).

Key Terminology

• Payoff Matrix: Represents outcomes for row player.

• Saddle Point: Entry that is min in row and max in column.

• Fair Game: \(v = 0\).

[!TIP]

2×2 Game: If no saddle point, use algebraic method; for larger games, use linear programming or iterative methods.

8. Advanced Topics and Applications

Minimal Spanning Tree (MST)

• Definition: Subset of edges connecting all nodes with minimum total weight, no cycles.

• Applications: Network design, clustering, circuit layout.

• Algorithms:

  • Kruskal’s: Sort edges by weight; add smallest edge that doesn’t form cycle.

  • Prim’s: Start from arbitrary node; add cheapest edge connecting tree to new node.

Dynamic Programming (DP)

• Principle: Break problem into stages; optimal policy has optimal substructure.

• Components:

  • Stages: Sequence of decisions.

  • States: Conditions at each stage.

  • Decision Policy: Rule mapping states to decisions.

  • Recursive Relation: \(f_n(s) = \max_{d} \{ r_n(s,d) + f_{n-1}(s') \}\).

• Resource Allocation Example: Allocate \(k\) resources to \(n\) activities to maximize return.

• Recursion:

  • Forward: Start from initial state.

  • Backward: Start from final stage (common).

Formulation of Real-World Problems as LPs

• Workforce Scheduling (Police):

  • Variables: \(x_i\) = officers starting on day \(i\).

  • Constraints: \(\sum_{i \in \text{cover } j} x_i \ge \text{req}_j\) for each day \(j\).

  • Objective: Minimize \(\sum x_i\).

• Blending Problems: Mix raw materials to meet quality specs at min cost; linear constraints on components.

[!TIP]

DP: Identify state variable (e.g., remaining resources) and recursive payoff function. For MST, Kruskal’s uses union-find for cycle detection.