UNIT 5: Operations Research and Supply Chain Management

Short Notes for RGPV ME-703(D) - Based on Past Paper Analysis

I. Linear Programming (LP)

Formulation of LP Problems

• Decision Variables: Quantities to be determined (e.g., units of product A, B).

• Objective Function: Linear function to maximize (profit) or minimize (cost).

$$\text{Maximize/Minimize } Z = c_1x_1 + c_2x_2 + \dots + c_nx_n$$

• Constraints: Linear inequalities/equations representing resource limits.

$$a_{11}x_1 + a_{12}x_2 + \dots \le, =, \ge b_1$$

• Non-negativity: $$\displaystyle x_1, x_2, \dots, x_n \ge 0 $$.

• Slack/Surplus Variables: Added to ≤ / ≥ constraints to convert to equality. Slack (≤) adds +s; surplus (≥) subtracts –s.

[!TIP]

Exam Focus: LP formulation questions (14 marks) appear every semester. Always define variables clearly, write objective, list constraints with units, and state non-negativity.

Simplex Method

1. Standard Form Conversion:

   • Maximization → Maximize $Z$.

   • All constraints → ≤ type (add slack variables).

   • RHS $$\displaystyle b_i \ge 0 $$ (if not, multiply by –1).

   • Example: $$\displaystyle 3x_1 + 2x_2 \le 6 $$ becomes $$\displaystyle 3x_1 + 2x_2 + s_1 = 6 $$, $$\displaystyle s_1 \ge 0 $$.

2. Initial Basic Feasible Solution (BFS): Set non-basic variables = 0, solve for basic variables (slack variables initially).

3. Pivot Operation:

   • Entering variable: Most positive $$\displaystyle (C_j - Z_j) $$ for maximization.

   • Leaving variable: Minimum positive ratio $$\displaystyle \frac{\text{RHS}}{\text{pivot column coefficient}} $$ (θ-ratio test).

   • Update tableau via row operations.

4. Optimality Test: All $$\displaystyle (C_j - Z_j) \le 0 $$ for maximization → optimal.

5. Big-M / Two-Phase: Used for ≥ or = constraints (artificial variables). Big-M penalizes artificial variables with large $M$ in objective.

[!TIP]

Common Pitfalls: Forgetting to compute $$\displaystyle Z_j $$ row correctly; mishandling negative RHS in initial BFS; not checking for degeneracy.

II. Transportation Problems

Problem Structure

• Balanced: Total supply = Total demand.

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

• Cost Matrix $$\displaystyle C_{ij} $$, Supply $$\displaystyle a_i $$, Demand $$\displaystyle b_j $$.

Initial Basic Feasible Solution Methods

Optimality Test: MODI / u-v Method

1. For allocated cells: $$\displaystyle u_i + v_j = c_{ij} $$. Set $$\displaystyle u_1 = 0 $$, solve for all $$\displaystyle u_i, v_j $$.

2. Compute unallocated cell potentials: $$\displaystyle \Delta_{ij} = c_{ij} - (u_i + v_j) $$.

3. Optimal if all $$\displaystyle \Delta_{ij} \ge 0 $$ (minimization).

   If any $$\displaystyle \Delta_{ij} < 0 $$, not optimal → select most negative for reallocation.

Degeneracy in Transportation

• Definition: Number of allocated cells $$\displaystyle < (m + n - 1) $$ in a BFS.

• Cause: Tie in allocation steps, zero-cost cells allocated artificially.

• Resolution:

  • ε (epsilon) method: Allocate tiny ε ($\approx 0$) to a zero-cost unallocated cell to make $(m+n-1)$ allocations.

  • Proceed with MODI; ε will not affect cost but resolves degeneracy.

Special Cases

• Penalties for Unfulfilled Demand: Add dummy destination with penalty cost as its row cost.

  Example: Penalty Rs.2 for J → dummy cost = 2 for all factories to J.

• Prohibited Routes: Assign very high cost ($M$) or mark as ∞; avoid allocation.

• Maximization: Convert to minimization by subtracting all costs from a large constant (e.g., $$\displaystyle C' = \text{max}(C) - C $$).

[!TIP]

Exam Focus: VAM (initial solution) + MODI (optimality) + degeneracy resolution are high-frequency (Dec 24, May 24, Nov 23). Penalties problem appeared in Jun 2025.

III. Inventory Management Models

Economic Order Quantity (EOQ) Model

Assumptions:

• Constant demand rate $D$ (units/year).

• Fixed ordering/setup cost $S$ (Rs/order).

• Constant holding cost $H$ (Rs/unit/year).

• Instantaneous replenishment, no shortages.

Derivation:

Total Annual Cost (TAC) = Ordering Cost + Holding Cost

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

Minimize TAC w.r.t. $Q$:

$$\frac{d(TAC)}{dQ} = -\frac{DS}{Q^2} + \frac{H}{2} = 0 \quad \Rightarrow \quad Q^* = \sqrt{\frac{2DS}{H}}$$

Key Formulas:

• EOQ: $$\displaystyle Q^* = \sqrt{\frac{2DS}{H}} $$

• Number of orders/year: $$\displaystyle N = \frac{D}{Q^*} $$

• Time between orders: $$\displaystyle T = \frac{1}{N} = \frac{Q^*}{D} $$ (years)

• Total Annual Cost: $$\displaystyle TAC^* = \sqrt{2DSH} $$

[!TIP]

Unit Consistency: Ensure $D$, $H$ in same time unit (year/month). If $H$ given as % of cost, $$\displaystyle H = i \times C $$ (where $i$ = carrying rate, $C$ = cost/unit).

EOQ with Price Discounts

• All-units discount: Entire order qualifies for discount if $Q \ge$ breakpoint.

• Incremental discount: Only units above breakpoint get discounted price.

• Procedure:

  1. Compute EOQ at each price break (using $$\displaystyle H = i \times \text{price} $$).

  2. If EOQ feasible (within price break range), compute TAC.

  3. If EOQ not feasible, use breakpoint quantity.

  4. Compare TACs at all feasible $Q$ → choose minimum.

Inventory Classification

Advantages: Focuses control efforts, reduces inventory costs, improves resource allocation.

[!TIP]

Exam Focus: EOQ calculations (all parts) are guaranteed every paper. ABC/VED comparison (Jun 2025) – know definitions and advantages.

IV. Queuing Theory

Basic Concepts & Kendall’s Notation

• A/B/c: Arrival process (A), Service time (B), Number of servers (c).

  e.g., M/M/1 = Poisson arrivals, Exponential service, 1 server.

• Parameters:

  Arrival rate $\lambda$ (customers/unit time), Service rate $\mu$ (customers/unit time).

  Traffic intensity: $$\displaystyle \rho = \lambda / \mu $$ (must be $$\displaystyle \rho < 1 $$ for steady state).

M/M/1 Performance Measures

$$L_q = \frac{\rho^2}{1-\rho} \quad \text{(mean queue length)}$$

$$L = L_q + \rho = \frac{\rho}{1-\rho} \quad \text{(mean number in system)}$$

$$W_q = \frac{L_q}{\lambda} = \frac{\rho}{\mu(1-\rho)} \quad \text{(mean waiting time in queue)}$$

$$W = W_q + \frac{1}{\mu} = \frac{1}{\mu(1-\rho)} \quad \text{(mean time in system)}$$

Probability Distributions

• Exponential Service Time: $$\displaystyle P(T > t) = e^{-\mu t} $$

  Example: $$\displaystyle \mu = 20 $$ customers/hour → $$\displaystyle P(\text{service} > 15 \text{ min}) = e^{-20 \times 0.25} = e^{-5} $$.

• Poisson Arrivals: $$\displaystyle P(k \text{ arrivals in time } t) = \frac{e^{-\lambda t} (\lambda t)^k}{k!} $$.

Queue Disciplines

• FIFO/FCFS: First-In-First-Out (most common).

• LIFO/LCFS: Last-In-First-Out (stack).

• SIRO: Service In Random Order.

• Priority: Based on urgency/class.

• SPT: Shortest Processing Time first (minimizes average $$\displaystyle W_q $$).

[!TIP]

Exam Focus: Probability calculations using exponential/Poisson (Jun 2025, Dec 2024, Nov 2023). Always convert time units consistently (hours ↔ minutes).

V. Project Management (PERT/CPM)

Network Diagram

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

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

• Logical Relationships: FS (Finish-Start), SS (Start-Start), FF, SF.

Critical Path Method (CPM)

1. Forward Pass:

   • $ES$ (Earliest Start) = max($EF$ of predecessors).

   • $$\displaystyle EF = ES + \text{duration} $$.

2. Backward Pass:

   • $LF$ (Latest Finish) = min($LS$ of successors).

   • $$\displaystyle LS = LF - \text{duration} $$.

3. Float/Slack:

   • Total Float = $$\displaystyle LS - ES = LF - EF $$.

   • Critical Activity: Float = 0.

   • Critical Path: Longest path (max duration) with zero float.

PERT (Probabilistic)

• Three Time Estimates:

  • $a$ = optimistic (best case)

  • $m$ = most likely

  • $b$ = pessimistic (worst case)

• Expected Time:

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

• Variance:

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

• Project Variance: Sum of variances on critical path ($$\displaystyle \sigma_{cp}^2 $$).

Project Completion Probability

Assuming normal distribution:

$$Z = \frac{T_d - T_{expected}}{\sigma_{cp}}$$

$$\displaystyle P(T \le T_d) = \Phi(Z) $$ from standard normal table.

Example: $$\displaystyle T_{expected}=60 $$, $$\displaystyle \sigma_{cp}=3 $$, $$\displaystyle T_d=66 $$ → $$\displaystyle Z=2 $$ → $P \approx 0.977$.

PERT vs. CPM

Phases of Project Management (Jun 2025)

1. Initiation → 2. Planning → 3. Execution → 4. Monitoring & Controlling → 5. Closure.

[!TIP]

Exam Focus: Critical path (forward/backward pass) and PERT probability calculations (Nov 2023) are common. Distinguish PERT/CPM clearly in comparisons.

VI. Supply Chain Management (SCM) Concepts

SCM Fundamentals

• Definition: Coordination of material, information, and financial flows across supply chain (suppliers → manufacturers → distributors → customers).

• Objectives: Reduce costs, improve service, increase responsiveness, optimize inventory.

• Key Flows:

  Material Flow: Physical goods upstream/downstream.

  Information Flow: Orders, forecasts, schedules (bidirectional).

  Financial Flow: Payments, credit, consignments (downstream).

Logistics in SCM

Bull-Whip Effect

• Definition: Demand variability amplifies as we move upstream (retailer → wholesaler → manufacturer → supplier).

• Causes:

  1. Demand forecast updating (each tier forecasts independently).

  2. Order batching (periodic large orders).

  3. Price fluctuations (forward buying).

  4. Rationing/gaming (shortage-induced over-ordering).

• Mitigation:

  • Information sharing (POS data, EDI).

  • Vendor Managed Inventory (VMI).

  • Eliminate incentives for forward buying.

  • Reduce lead times.

Cross Docking

• Process: Inbound trucks → unload → sort → directly load onto outbound trucks without long-term storage.

• Advantages:

  • Reduces inventory holding & handling costs.

  • Faster throughput, less damage.

  • Lower warehousing space needed.

• Disadvantages:

  • Requires high coordination & real-time info.

  • High infrastructure/IT investment.

  • Not suitable for all products (needs predictable demand).

MRP → MRP II → ERP Evolution

Competitive Advantages of MRP: Reduced inventory, better customer service, improved scheduling, cost control.

Outsourcing in SCM

• Reasons: Focus on core competencies, cost reduction, access to expertise, capacity flexibility.

• Benefits: Lower fixed costs, improved service, risk sharing.

• Risks: Loss of control, quality issues, dependency, knowledge leakage, hidden costs.

SCM & E-business

• E-procurement: Online purchasing (reverse auctions, catalogs).

• E-logistics: Real-time tracking, electronic bills of lading.

• Integration Benefits: Faster transactions, reduced paperwork, better visibility, global sourcing.

[!TIP]

Exam Focus: Bull-whip (causes/mitigation), cross docking (process/advantages/disadvantages), MRP→ERP evolution, inbound/outbound logistics – all frequent.

VII. Advanced OR Topics (Less Frequent)

Game Theory

• Assumptions: Rational players, fixed payoffs, simultaneous/sequential moves.

• Payoff Matrix: Rows = Player A strategies, Columns = Player B strategies.

• Pure Strategy: Saddle point exists if $$\displaystyle \max(\min \text{ row}) = \min(\max \text{ col}) $$. Value of game = saddle point.

• Mixed Strategy: Probabilistic choice when no saddle point. Solve using:

  For 2×2: $$\displaystyle p = \frac{d - b}{a+b-c-d} $$ for Player A, etc.

• Dominance Rule:

  • Row dominance: If $$\displaystyle a_{ij} \ge a_{kj} $$ for all $j$, row $k$ dominates row $i$ → delete row $i$.

  • Column dominance: If $$\displaystyle a_{ij} \ge a_{ik} $$ for all $i$, column $k$ dominates column $j$ → delete column $j$.

Heuristic & Metaheuristic Algorithms

• Heuristic: Problem-specific rule-of-thumb (e.g., nearest neighbor for TSP). Fast, not optimal.

• Metaheuristic: General framework exploring large search spaces (NP-hard problems).

  Examples:

  • Genetic Algorithms: Evolution-inspired (selection, crossover, mutation).

  • Simulated Annealing: Mimics annealing process (temperature cooling).

  • Tabu Search: Uses memory (tabu list) to avoid local optima.

• When to Use: Complex, non-linear, combinatorial problems where exact methods fail.

Network Logics

• Precedence Relationships: Activity B cannot start until Activity A finishes (FS relationship).

• Event-Based (AOA): Nodes represent milestones/events; arrows are activities. Requires dummy activities for merging/splitting.

• Activity-Based (AON): Nodes represent activities; arrows show precedence. More flexible, no dummies needed.

[!TIP]

Exam Focus: Game theory (pure/mixed, dominance) and PERT/CPM network logics appeared in Jun 2025. Know how to construct networks with correct dependencies.

Final Note: This summary covers all topics from the approved outline with emphasis on past exam frequency. For LP/Transportation, practice full numerical solutions. For SCM, focus on definitions, flows, and concepts like Bull-whip/Cross-docking. Always box final formulas.