Operation Research & Supply Chain (ME-703 (A)) - Unit 1 Short Notes

UNIT 1: OPERATION RESEARCH & SUPPLY CHAIN (ME-703 A)

Based on analysis of RGPV past papers (Jun 2025, Dec 2024, May 2024, Nov 2023).

I. LINEAR PROGRAMMING (LP) & SIMPLEX METHOD

A. LP Problem Formulation

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

• Objective Function: Linear function to be Maximized (profit) or Minimized (cost).

  • General form: Max/Min \( Z = c_1x_1 + c_2x_2 + ... + c_nx_n \)

• Constraints: Linear inequalities/equations representing resource limits (manhours, materials, demand).

• Non-negativity: \( x_1, x_2, ... \ge 0 \).

• Standard Form (for Maximization):

  1. Objective: Max \( Z \).

  2. All constraints: \( \le \) type.

  3. RHS \( b_i \ge 0 \).

  4. Convert \( \ge \) or \( = \) constraints using slack, surplus, and artificial variables.

[!TIP]

Common Pitfall: Forgetting non-negativity constraints. Always state \( x_i \ge 0 \).

B. Simplex Method

Objective: Solve LP in standard form by moving from one corner point (basic feasible solution) to an adjacent one, improving \( Z \) each iteration until optimal.

Step-by-Step Procedure:

1. Convert to Standard Form: Add slack/surplus/artificial variables.

2. Set up Initial Simplex Tableau:

   • Rows: Constraints.

   • Columns: Coefficients of all variables (decision + slack/surplus/artificial) + RHS (b).

   • Basic Variables: Initially, slack/artificial variables. Their columns form an identity matrix.

3. Calculate Net Evaluation Row (\( C_j - Z_j \)):

   • \( Z_j = \sum (\text{Cost of basic var}_i \times \text{Coeff of var}_j \text{ in row}_i) \)

   • \( C_j - Z_j \): Indicates potential increase in \( Z \) if non-basic var \( j \) enters.

4. Entering Variable: Most positive \( C_j - Z_j \) (for maximization).

5. Leaving Variable: Minimum Ratio Test: \( \frac{\text{RHS}}{\text{Pivot Column Coefficient}} \) (only for positive pivot column coeffs). Smallest ratio determines row to leave.

6. Pivot Operation:

   • Make pivot element = 1 (divide pivot row by pivot element).

   • Use row operations to make all other elements in pivot column = 0.

7. Repeat steps 3-6 until all \( C_j - Z_j \le 0 \) → OPTIMAL.

8. Read Solution:

   • RHS column gives values of basic variables.

   • Non-basic variables = 0.

   • Optimal \( Z \) = value in \( Z_j \) column for the row of objective function.

Special Cases:

• Degeneracy: A basic variable's value = 0 in a tableau. Resolution: Use artificial variables (Big-M Method) or perturbation (add tiny \( \epsilon \)) to avoid cycling.

• Infeasibility: No feasible solution exists. Identified if an artificial variable remains positive in the final tableau.

• Unbounded Solution: All coefficients in entering variable's column \( \le 0 \) → \( Z \) can increase indefinitely.

[!TIP]

Exam Focus: Be flawless with tableau setup, pivot calculations, and reading final solution (including shadow prices from final tableau's RHS under slack columns).

II. TRANSPORTATION PROBLEMS (TP)

A. Problem Structure

• Objective: Minimize total transportation cost \( \sum \sum c_{ij} x_{ij} \).

• Balanced TP: Total supply = Total demand.

• Unbalanced TP:

  • Supply > Demand → Add Dummy Destination with zero cost.

  • Demand > Supply → Add Dummy Origin with zero cost.

• IBFS Requirement: Exactly \( (m+n-1) \) allocated cells (non-zero \( x_{ij} \)) in an \( m \times n \) matrix.

B. Initial Basic Feasible Solutions (IBFS)

1. North-West Corner Rule (NWCR):

   • Start at cell (1,1).

   • Allocate as much as possible: \( x_{11} = \min(\text{Supply}_1, \text{Demand}_1) \).

   • Cross out exhausted row/column, move to next cell (right or down).

   • Simple but often costly.

2. Least Cost Method (LCM):

   • Allocate to cell with minimum cost \( c_{ij} \).

   • Adjust supply/demand, cross out exhausted row/column.

   • Repeat until all allocations done.

3. Vogel's Approximation Method (VAM) – Heavily Featured:

   • For each row & column, calculate Penalty = |Second smallest cost - Smallest cost|.

   • Allocate to cell with smallest cost in row/column having highest penalty.

   • Adjust supply/demand, recalculate penalties for affected rows/columns.

   • Result: IBFS often near-optimal.

C. Optimality Test & Solution Improvement

1. Stepping Stone Method:

   • For each unoccupied cell, trace a closed loop (alternating + and -).

   • Calculate Opportunity Cost (\( \Delta_{ij} \)): Sum of costs in + cells minus sum in - cells.

   • If all \( \Delta_{ij} \ge 0 \) → Optimal.

   • If any \( \Delta_{ij} < 0 \), select most negative. Allocate as much as possible to that cell (minimum allocation in loop) and adjust loop allocations.

2. Modified Distribution (MODI / u-v) Method – Preferred for Exams:

   • For occupied cells: \( u_i + v_j = c_{ij} \).

   • Set \( u_1 = 0 \) (or any arbitrary value), solve for all \( u_i, v_j \).

   • For unoccupied cell (i,j): \( \Delta_{ij} = c_{ij} - (u_i + v_j) \).

   • Optimality: All \( \Delta_{ij} \ge 0 \).

   • Improvement: Select most negative \( \Delta_{ij} \), find loop, reallocate.

D. Special Cases in TP

• Degeneracy: Number of allocated cells < \( m+n-1 \).

  • Resolution: Allocate a very small quantity (\( \epsilon \)) to an unoccupied cell with smallest cost to achieve \( m+n-1 \) allocations. Treat \( \epsilon \) as zero in cost calculations but keep it in allocations for loop tracing.

• Penalty / Unfulfilled Demand:

  • Add penalty cost to each destination's column in cost matrix.

  • Solve as standard minimization TP. Dummy allocation indicates unmet demand.

• Maximization TP:

  • Convert to minimization: Subtract all costs from a large constant (e.g., max cost in matrix + 1) or multiply by -1.

  • Solve as minimization problem.

[!TIP]

Key Skill: VAM for IBFS and MODI for optimality are must-practice. Degeneracy resolution with \( \epsilon \) is frequently asked.

III. SUPPLY CHAIN MANAGEMENT (SCM) FUNDAMENTALS

A. Core Concepts & Flows

• Inbound Logistics: Activities from raw material suppliers to manufacturing plant (procurement, receiving, storage, internal movement). Focus: Cost-effective sourcing, supplier relationships.

• Outbound Logistics: Activities from manufacturing plant to end customer (warehousing, order fulfillment, transportation, delivery). Focus: Customer service, delivery speed, channel management.

B. Key Phenomena & Strategies

• Bull-Whip Effect:

  • Definition: Demand variability amplifies as one moves upstream (from retailer to manufacturer).

  • Causes: Demand forecasting, order batching, price fluctuations, rationing & gaming.

  • Consequences: Excess inventory, poor capacity utilization, increased costs, product obsolescence.

  • Mitigation: Vendor Managed Inventory (VMI), Continuous Replenishment, reducing lead times, stabilizing prices, sharing POS data.

• Cross-Docking:

  • Concept: Inbound trucks unload goods; goods are sorted and directly loaded onto outbound trucks with minimal or no storage.

  • Process: Receiving → Sorting → Shipping.

  • Advantages: Reduced inventory holding costs & handling, faster throughput, lower warehouse space needs.

  • Disadvantages: Requires high coordination, accurate forecasting, synchronized transportation, not suitable for all products.

C. Evolution & Integration

• MRP (Material Requirements Planning): Focuses on dependent demand (components for finished goods). Uses BOM, inventory records, and master production schedule.

• MRP II (Manufacturing Resource Planning): Extends MRP to integrate all manufacturing resources (labor, machines, finance). Closed-loop system.

• ERP (Enterprise Resource Planning): Integrates all enterprise functions (finance, HR, SCM, CRM) into a single system. Real-time data across departments.

• SCM (Supply Chain Management): Strategic coordination of all firms & functions in the supply chain to deliver value. ERP provides the information backbone for SCM.

• Role of Outsourcing: Focus on core competencies, reduce costs, access expertise, increase flexibility (e.g., 3PL/4PL providers).

• Link with E-Business: E-commerce platforms (B2B, B2C) enable online ordering, tracking, and collaboration. E-business provides the digital infrastructure for supply chain visibility and integration (e.g., EDI, web portals).

[!TIP]

Exam Focus: Bull-Whip (causes/mitigation) and Cross-Docking (pros/cons) are very high frequency. Be ready to contrast MRP vs. ERP vs. SCM.

IV. INVENTORY MANAGEMENT MODELS

A. Economic Order Quantity (EOQ) Model

• Assumptions:

  • Constant, known demand rate (\( D \)).

  • Instantaneous replenishment (order arrives all at once).

  • No shortages allowed.

  • Fixed ordering/setup cost (\( S \)) per order.

  • Constant holding/carrying cost (\( h \)) per unit per year.

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

  • \( \frac{d(TC)}{dQ} = -\frac{DS}{Q^2} + \frac{h}{2} = 0 \)

• Key Formulas:

  • Optimal Order Quantity (EOQ):

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

*   **Optimal Number of Orders per Year**: \( N^* = \frac{D}{Q^*} \)

*   **Cycle Time (Time between orders)**: \( T^* = \frac{Q^*}{D} \) (in years) or \( \frac{365}{N^*} \) days.

*   **Minimum Average Total Cost**: \( TC_{min} = \sqrt{2DS h} \)

B. EOQ with Quantity Discounts

• Price-Break Model: Unit purchase cost \( c \) decreases as order quantity \( Q \) increases.

• Decision Rule:

  1. Calculate EOQ using lowest cost \( c \) (ignoring discounts). Call it \( Q_1 \).

  2. If \( Q_1 \) falls in a discount break, calculate Total Cost \( TC = \frac{D}{Q}S + \frac{Q}{2}h + Dc \) at \( Q_1 \) and at the minimum quantity of all lower-priced breaks.

  3. Choose \( Q \) with lowest TC among feasible candidates.

  4. If \( Q_1 \) is below a discount break, calculate TC at \( Q_1 \) and at the minimum quantity of that break. Choose minimum.

C. Inventory Classification & Analysis

• ABC Analysis:

  • Principle: Classify items based on annual consumption value (Unit Cost × Annual Usage).

  • Procedure:

    1. Compute annual consumption value for each item.

    2. Arrange items in descending order of consumption value.

    3. Calculate cumulative % of total consumption value.

    4. Classify:

       • A-items: ~70-80% value, ~10-20% items → Tight control, frequent review.

       • B-items: ~15-25% value, ~20-30% items → Normal control.

       • C-items: ~5% value, ~50-60% items → Simple controls, bulk ordering.

  • Advantages: Focuses managerial attention, optimizes inventory investment, reduces costs.

• VED Analysis (Vital, Essential, Desirable):

  • Principle: Classify based on criticality/importance to operations (not monetary value).

  • Categories:

    • V (Vital): Shortage stops production/sales. (e.g., key spare part). Tight control, high safety stock.

    • E (Essential): Important but not vital. Shortage causes serious problems. Moderate control.

    • D (Desirable): Not critical. Shortage causes minor inconvenience. Loose control, low safety stock.

  • Application: Often used with spare parts in maintenance, pharmaceuticals, defense inventory. Compared to ABC: ABC is financial, VED is functional/operational. Often used together (e.g., ABC-VED matrix).

[!TIP]

Exam Focus: EOQ derivation is fundamental. For discounts, always compute TC at EOQ and at each price break's minimum Q. ABC vs VED comparison is a 7-mark favorite.

V. QUEUING THEORY (M/M/1)

A. Basic Components

• Arrival Process: Poisson with rate \( \lambda \) (customers/unit time).

• Service Mechanism: Exponential with rate \( \mu \) (customers/unit time). Single server (M/M/1).

• Queue Discipline: FIFO (First-In-First-Out) assumed unless specified.

• Population Size: Infinite (unlimited source).

• System Capacity: Infinite (no limit on queue length).

B. Key Parameters & Performance Measures (M/M/1)

• Utilization Factor: \( \rho = \frac{\lambda}{\mu} \) (Must be < 1 for steady state).

• Probability of n customers in system: \( P(n) = (1 - \rho) \rho^n \)

• Average number in system: \( L = \frac{\rho}{1 - \rho} \)

• Average number in queue: \( L_q = \frac{\rho^2}{1 - \rho} \)

• Average time in system: \( W = \frac{1}{\mu - \lambda} \)

• Average waiting time in queue: \( W_q = \frac{\lambda}{\mu(\mu - \lambda)} \)

• Probability that service time > t (Exponential service): \( P(T > t) = e^{-\mu t} \)

[!TIP]

Exam Focus: Memorize \( \rho, L, L_q, W, W_q \) formulas for M/M/1. For exponential service probability, directly use \( e^{-\mu t} \). Ensure \( \lambda \) and \( \mu \) are in same time units.

VI. PROJECT MANAGEMENT (PERT/CPM)

A. Network Construction

• Activity-on-Arrow (AOA): Arrows represent activities, circles (nodes) represent events (milestones). Dummy activities (zero duration) used to maintain logic.

• Activity-on-Node (AON): Nodes represent activities, arrows represent precedence/dependency. More common, simpler.

• Rules:

  • Network must have single start and single end node.

  • No activity can start until all its predecessors finish (finish-to-start).

  • Must not have loops or dangling activities.

B. Critical Path Method (CPM)

• Deterministic times (single time estimate per activity).

• Forward Pass (Top-left to bottom-right):

  • Earliest Start Time (EST): \( ES_i = \max(EF_j) \) for all immediate predecessors \( j \).

  • Earliest Finish Time (EF): \( EF_i = ES_i + t_i \).

  • Start node \( ES = 0 \).

• Backward Pass (Bottom-right to top-left):

  • Latest Finish Time (LFT): \( LF_i = \min(LS_j) \) for all immediate successors \( j \).

  • Latest Start Time (LS): \( LS_i = LF_i - t_i \).

  • End node \( LF = \text{Project Duration} \).

• Float/Slack:

  • Total Float (TF): \( TF_i = LS_i - ES_i = LF_i - EF_i \). Time an activity can be delayed without delaying project.

  • Free Float (FF): \( FF_i = \min(ES_j) - EF_i \). Time an activity can be delayed without delaying early start of any successor.

• Critical Path: Path with zero Total Float. Longest path through network. Determines minimum project duration.

C. Program Evaluation and Review Technique (PERT)

• Probabilistic times (three estimates):

  • Optimistic (a): Minimum time if everything goes well.

  • Most Likely (m): Most realistic estimate.

  • Pessimistic (b): Maximum time if major problems occur.

• Expected Time (te):

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

• Variance (σ²):

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

• Project Duration & Probability:

  1. Calculate \( t_e \) for all activities.

  2. Perform CPM forward/backward passes on \( t_e \) to find critical path and expected project time (Te).

  3. Project variance \( \sigma_{p}^2 = \sum \sigma^2 \) (only for activities on critical path).

  4. Project standard deviation: \( \sigma_p = \sqrt{\sigma_{p}^2} \).

  5. To find probability of completion by due date \( T_d \):

     • \( Z = \frac{T_d - T_e}{\sigma_p} \)

     • Use Standard Normal Table to find \( P(Z) \).

D. PERT vs. CPM

E. Phases of Project Management

1. Conceptualization: Define project scope, objectives, feasibility.

2. Planning: Develop WBS, schedule (PERT/CPM), resource allocation, budget.

3. Scheduling: Assign time estimates, sequence activities, create network, determine critical path.

4. Execution: Coordinate resources, manage teams, implement plan.

5. Closure: Handover, documentation, lessons learned, release resources.

[!TIP]

Exam Focus: Drawing clean AON networks is crucial. For PERT probability, identify the critical path based on te, sum variances only on that path, then compute Z-score. Common mistake: Summing variances of all activities.

VII. OTHER OPERATION RESEARCH TOPICS

A. Game Theory

• Pure Strategy: Player selects one specific action.

• Mixed Strategy: Player selects actions according to pre-determined probabilities.

• Basic Assumptions: Rational players, known payoffs, simultaneous moves (usually), self-interest.

• Dominance Rule:

  • Row Dominance: Row A dominates Row B if \( a_{ij} \ge b_{ij} \) for all j (maximizer) and > for at least one j.

  • Column Dominance: Column A dominates Column B if \( a_{ij} \ge a_{ik} \) for all i (minimizer) and > for at least one i.

  • Action: Delete dominated rows/columns to reduce payoff matrix.

B. Heuristic & Meta-Heuristic Algorithms

• Need: For NP-hard problems where exact methods (like Simplex) are too slow for large instances.

• Heuristics: Problem-specific, quick, "good enough" solutions (e.g., Nearest Neighbor for TSP).

• Meta-Heuristics: General frameworks that can be adapted to many problems.

  • Genetic Algorithms: Mimic evolution (selection, crossover, mutation).

  • Simulated Annealing: Mimics metal cooling, accepts worse moves to escape local optima.

  • Tabu Search: Uses memory (tabu list) to avoid cycling and explore new areas.

C. Analysis of Variance (ANOVA)

• Context: Used to compare means of multiple groups (e.g., testing different machine setups).

• Basic Idea: Partition total variability into between-group and within-group variation.

• F-statistic: \( F = \frac{\text{Mean Square Between}}{\text{Mean Square Within}} \). Compare to critical F-value to test if group means differ significantly.

• Note: Not a core calculation topic in OR, but mentioned in context of experimental design for process optimization.

[!TIP]

Exam Focus: Game theory questions are usually short (dominance rule, pure/mixed definitions). Meta-heuristics require only conceptual explanation (idea, not math). ANOVA is rarely asked as calculation.

Final Exam Strategy:

1. Step-marked questions: Present clear, numbered steps (especially Simplex, VAM, MODI, PERT).

2. Definitions: Start 7-mark theory questions with crisp definitions.

3. Diagrams: Draw neat network diagrams (AON) and supply chain flow diagrams where relevant.

4. Formulas: Box final formulas (EOQ, PERT te, M/M/1 measures).

5. Time Management: Allocate time based on marks (e.g., 14m Simplex ~25 mins).