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

UNIT 4: OPERATIONS RESEARCH – SHORT NOTES

Based on RGPV CE-604(D) Past Papers (May 2023 & May 2022)

I. FOUNDATIONS OF OPERATIONS RESEARCH

Definition: Operations Research (OR) is a scientific, quantitative approach to decision-making that uses mathematical models, statistics, and algorithms to find optimal or near-optimal solutions to complex problems.

Phases of OR:

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

2. Model Building: Develop a mathematical representation (e.g., LP, simulation).

3. Solution: Apply analytical or numerical methods to solve the model.

4. Validation: Test model accuracy and robustness.

5. Implementation: Apply solution in real-world context; monitor results.

Modeling in OR:

• Types:

  • Mathematical: Equations (e.g., LP, EOQ).

  • Simulation: Mimics system behavior over time.

  • Graphical: Visual representation for 2-variable problems.

• Steps: Abstraction → Formulation → Solution → Testing → Validation.

Characteristics:

• Interdisciplinary (math, engineering, economics).

• Systems approach (holistic view).

• Quantitative, objective-driven.

Limitations:

• Data quality and availability issues.

• Model simplicity vs. reality trade-off.

• Implementation challenges (human factors, cost).

[!TIP]

Exam Focus: Phases and modeling steps are frequently asked in 7-mark questions. Use examples like "police scheduling" to illustrate formulation.

II. LINEAR PROGRAMMING (LP)

LP Formulation:

• Objective Function: Maximize or minimize linear function (e.g., profit, cost).

• Constraints: Linear inequalities/equalities representing limits.

• Decision Variables: Unknowns to be determined (≥ 0).

• Example:

  Police scheduling: Minimize officers subject to daily requirements.

Simplex Method:

1. Convert to standard form (maximize, ≤ constraints, slack variables).

2. Identify basic feasible solution (BFS).

3. Iterate:

   • Compute net evaluation (C_j – Z_j).

   • Select entering variable (most positive for max).

   • Compute ratios (b_i/a_ij > 0) for leaving variable.

   • Pivot to new BFS.

4. Optimality Test: All C_j – Z_j ≤ 0 (max) → optimal.

Special Cases:

• Big-M Method: For ≥ or = constraints.

  • Add artificial variables with large penalty M in objective.

  • Minimize: Z = … + M·(sum of artificial variables).

  • Drive artificial variables to zero.

• Two-Phase Method: Phase 1 minimizes sum of artificial variables; Phase 2 removes them.

• Unbounded Solution: All ratios infinite → Z → ∞.

• Infeasibility: No BFS exists (e.g., contradictory constraints).

Transportation Problem:

• Formulation:

  • Balanced: Total supply = total demand.

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

• Initial Feasible Solutions:

  | Method | Approach | Cost Focus | |-----------------|-----------------------------------|------------| | Northwest Corner| Allocate from top-left cell | Ignored | | Least Cost | Allocate to lowest cost cell | Yes | | Vogel’s Approximation | Penalty-based (difference between two lowest costs) | Yes |

• Degeneracy:

  • Meaning: Allocations < (m + n – 1) in a basic solution.

  • Consequence: May cause cycling (infinite loops in optimality test).

  • Resolution:

    1. Allocate a very small ε (e.g., 0.001) to a zero-cell to make it basic.

    2. Use MODI method (modified distribution method) to adjust.

[!TIP]

Common Pitfall: In simplex, forgetting non-negativity or miscomputing ratios. In transportation, degeneracy often overlooked—always check allocations count.

III. INVENTORY MODELS

Deterministic EOQ Model:

• Assumptions:

  • Constant demand rate (D).

  • Fixed ordering cost (S).

  • Constant holding cost (H = i·C, where i = carrying rate, C = unit cost).

  • Instantaneous replenishment.

  • No shortages.

• EOQ Formula:

$$ Q^* = \sqrt{\frac{2DS}{H}} $$

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

• Total Cost:

$$ TC = \frac{D}{Q}S + \frac{Q}{2}H + DC $$

• Reorder Point (ROP):

$$ ROP = d \cdot L $$

(d = daily demand, L = lead time).

• Example (SBC alarm clocks, May 2022):

  D = 1000 units/year, S = $$\displaystyle 10/order, H = $$0.50/unit/year →

$$ Q^* = \sqrt{\frac{2 \times 1000 \times 10}{0.5}} = \sqrt{40000} = 200 \text{ units} $$

Stochastic Inventory Models:

• Newsvendor Model: Single-period with uncertain demand.

  • Critical ratio: \( \frac{C_u}{C_u + C_o} \) (underage vs. overage cost).

  • Order quantity where cumulative demand distribution = critical ratio.

• (Q, r) Models: Continuous review; order fixed Q when inventory ≤ r.

  • Balances ordering, holding, and shortage costs.

  • Service Level: Probability of no stockout (e.g., 95%).

[!TIP]

Exam Alert: EOQ calculations are common. Ensure units consistency (e.g., H in $/unit/year if D is yearly).

IV. QUEUING THEORY

Queuing System Components (Kendall’s notation: A/B/c/K/N/Z):

• A: Arrival distribution (M = Markov/Poisson, D = deterministic, G = general).

• B: Service distribution.

• c: Number of servers.

• K: System capacity (∞ if unlimited).

• N: Population size (∞ if infinite).

• Z: Queue discipline (FIFO, LIFO, PRI, RAND).

Characteristics:

• Arrival Process: Poisson (exponential inter-arrival) common.

• Service Mechanism: Exponential (M), deterministic, general.

• Queue Discipline:

  | Discipline | Description | Example | |------------|------------------------------|-----------------------| | FIFO | First-In-First-Out | Supermarket line | | LIFO | Last-In-First-Out | Stack (plates) | | Priority | Based on urgency/class | Emergency room | | Random | Service order random | Lottery system |

• Performance Measures:

  • λ = arrival rate, μ = service rate per server.

  • Utilization factor: ρ = λ / (cμ) (must be < 1 for stability).

  • Average queue length: L_q.

  • Average waiting time: W_q.

  • Little’s Law: L = λW (applies to system, not just queue).

M/M/1 Model (Single server, infinite capacity):

• Formulas:

$$ \rho = \frac{\lambda}{\mu} $$

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

$$ L = \frac{\rho}{1 - \rho}, \quad W = \frac{1}{\mu - \lambda} $$

• Idle time = 1 – ρ.

M/M/c Model (c servers):

• Compute P₀ (probability of zero customers):

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

• Then L_q, W_q via standard formulas.

Example Problems (from past papers):

1. Repairman (May 2023):

   • Exponential service (mean = 30 min → μ = 2/hour).

   • Poisson arrivals (10 per 8-hour day → λ = 10/8 = 1.25/hour).

   • ρ = λ/μ = 1.25/2 = 0.625 → idle time = 1 – 0.625 = 0.375 (3 hours/day).

2. Postal Clerk (May 2022):

   • Service time = 3 min → μ = 20/hour.

   • Inter-arrival: 12 min (λ = 5/hour) and 5 min (λ = 12/hour).

   • Compute ρ, L_q, W_q for each period.

[!TIP]

Key Check: Always verify ρ < 1; otherwise system unstable (queue → ∞). For M/M/c, use c = number of servers.

V. NETWORK MODELS

PERT/CPM:

• Network Diagram:

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

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

• Critical Path:

  • Longest path through network.

  • Activities with zero total float.

  • Determines project completion time.

• Forward Pass (Early Start/Finish):

  • ES = max(EF of predecessors).

  • EF = ES + duration.

• Backward Pass (Late Start/Finish):

  • LF = min(LS of successors).

  • LS = LF – duration.

• Float/Slack:

  • Total Float (TF): LS – ES or LF – EF.

  • Free Float (FF): ES of successor – EF (no delay to successors).

• PERT Probabilistic Time:

  • Three estimates:

    • Optimistic (a), Most likely (m), Pessimistic (b).

  • Expected time:

$$ t_e = \frac{a + 4m + b}{6} $$

Variance:  

$$ \sigma^2 = \left( \frac{b - a}{6} \right)^2 $$

• Example (May 2022): Given activities, predecessors, durations → draw network, find critical path, compute ES/EF/LS/LF, slack.

Minimal Spanning Tree (MST):

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

• Applications: Pipeline/cable layout, network design.

• Algorithms:

  • Prim’s: Start at a node, add cheapest edge to new node.

  • Kruskal’s: Sort edges by weight, add without forming cycles.

Traveling Salesman Problem (TSP):

• Definition: Find shortest tour visiting each city exactly once and returning to start.

• Solution Approaches:

  • Brute force: (n-1)!/2 permutations (infeasible for large n).

  • Heuristics: Nearest neighbor, cheapest insertion.

  • Integer Programming: Binary variables x_ij = 1 if edge i→j used.

    Minimize ∑∑ c_ijx_ij subject to degree constraints and subtour elimination.

[!TIP]

Critical Path: Always start forward pass from project start (ES=0). For PERT, compute expected times first, then critical path.

VI. GAME THEORY

Basic Concepts:

• Pay-off Matrix: Rows = Player A strategies, columns = Player B strategies; entries = payoffs to A.

• Strategies:

  • Pure: Specific choice.

  • Mixed: Probability distribution over strategies.

• Zero-Sum Game: One player’s gain = other’s loss (∑ payoffs = 0).

• Two-Person Game: Exactly two players (common in OR).

Solution Methods:

1. Saddle Point:

   • Maximin (A’s security level) = Minimax (B’s security level).

   • Value of game (v): Common payoff at saddle point.

   • Optimal pure strategies: Row/column containing saddle point.

   • Check: Maximin = Minimax → saddle exists.

2. Dominance:

   • Row dominance: If row i ≤ row j for all columns, row i is dominated (remove j for max player).

   • Column dominance: If column i ≥ column j for all rows, column i is dominated (remove i for min player).

   • Reduce matrix iteratively before saddle point search.

3. Mixed Strategy (if no saddle):

   • For 2×2 games, solve:

     For A (max):

$$ p_1 = \frac{d - b}{a + d - b - c}, \quad p_2 = 1 - p_1 $$

 Value:  

$$ v = \frac{ad - bc}{a + d - b - c} $$

 (where matrix = [a b; c d]).  

Fair Game: Zero-sum game with value v = 0.

Example Terms from Past Papers:

• Pay-off matrix: Tabular representation of outcomes.

• Saddle point: Cell where row minimum = column maximum.

• Zero-sum game: Competitive, constant-sum.

[!TIP]

Exam Sequence: First check for dominance → reduce matrix → find maximin/minimax. If equal, saddle point; else mixed strategy (if asked).

VII. PROJECT MANAGEMENT & ANALYSIS TOOLS

CPM Details:

• Crashing: Reduce activity duration at increased cost.

  • Cost-time trade-off: Crash cost per unit time = (Crash cost – Normal cost) / (Normal time – Crash time).

  • Crash critical path activities with lowest crash cost first.

• Resource Leveling: Adjust activity start times to smooth resource usage (may extend project).

Link to EIA: Network analysis (PERT/CPM) can schedule EIA tasks (scoping, impact studies, reporting).

[!NOTE]

Crashing and resource leveling appeared implicitly in network questions; focus on critical path first.

VIII. APPLICATION & CASE STUDIES

• EOQ: SBC alarm clocks (May 2022) – calculate optimal order quantity.

• Queuing:

  • Repairman (May 2023): Exponential service, Poisson arrivals → idle time.

  • Postal clerk (May 2022): Time-dependent arrival rates → compute L_q, W_q.

• LP: Police scheduling (May 2022) – formulate LP for officer shifts.

• Network: Construction/R&D projects – draw network, find critical path.

IX. SHORT NOTE TOPICS (Direct from Past Papers)

PERT (Program Evaluation and Review Technique):

• Probabilistic time estimates (three estimates).

• Used for R&D, uncertain activity times.

• Expected time = (a + 4m + b)/6.

Pay-off Matrix:

• Table of outcomes for each strategy pair.

• Foundation of game theory.

Saddle Point:

• Cell where row minimum = column maximum.

• Gives optimal pure strategies and game value.

Zero-Sum Game:

• One player’s gain equals other’s loss.

• Constant-sum (often normalized to zero).

Basic Feasible Solution (BFS):

• In LP, solution with m basic variables (m = constraints) satisfying all constraints, non-basic = 0.

• Corresponds to corner point of feasible region.

Optimal Solution:

• BFS that maximizes/minimizes objective.

• Found via simplex optimality test.

Unbounded Solution:

• Objective can increase/decrease indefinitely (e.g., all entering variables have non-positive ratios in max problem).

• Indicates flawed model or missing constraints.

Service Disciplines:

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

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

• Priority: High-priority customers served first (e.g., emergency).

• Random: Service order random (e.g., lottery).

X. PROBLEM-SOLVING BLUEPRINT

[!CAUTION]

Common Errors:

• Simplex: Forgetting to update tableau after pivot.

• Queuing: Using λ instead of μ in denominator.

• Network: Miscalculating ES/EF due to wrong predecessor order.

• EOQ: Mixing holding cost units (e.g., % of cost vs. $/unit).

Final Note: Practice with past paper problems (May 2023 & May 2022) to internalize steps. Focus on definitions, formulas, and step-by-step solutions as per marking patterns.