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

UNIT 4: Advanced Topics in Operations Research and Supply Chain Management

1. Linear Programming (LP)

1.1 Formulation of LP Problems

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

• Objective Function: Linear function to be maximized (profit, revenue) or minimized (cost, time).

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

• Constraints: Linear inequalities/equations representing resource limits (man-hours, materials, capacity).

  • Form: \(a_{11}x_1 + a_{12}x_2 + ... \le, =, \ge b_1\)

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

[!TIP] Exam Focus: Past papers consistently ask to formulate an LP from a word problem (e.g., Jun 2025, Dec 2024, May 2024). Identify variables, write objective clearly, and translate each condition into a constraint.

1.2 Simplex Method: Step-by-Step Procedure

Converts LP to standard form (maximize \(Z\), constraints as =, RHS ≥ 0, all variables ≥ 0) by adding slack/surplus/artificial variables.

Tableau Setup:

1. Write objective row as \(Z - c_1x_1 - ... = 0\).

2. Basic variables (slack/artificial) form the initial basis.

3. Pivot Column: Most negative coefficient in objective row (for maximization).

4. Pivot Row: Minimum non-negative ratio (RHS / pivot column element).

5. Pivot Element: Intersection cell. Perform row operations to make it 1 and other elements in column 0.

6. Repeat until no negative coefficients in objective row (for maximization).

1.3 Interpretation of Final Tableau

• Solution: RHS column gives values of basic variables. Non-basic variables = 0.

• Optimal Objective Value: Value in bottom-right cell (Z).

• Shadow Price (Dual Value): Coefficient in objective row for a slack variable (if present). Indicates marginal value of one additional unit of that resource.

1.4 Special Cases

• Multiple/Optimal Solutions: Zero coefficient in objective row for a non-basic variable in final tableau.

• Unbounded Solution: All pivot column elements ≤ 0 when a negative coefficient exists in objective row.

• Infeasible Solution: Artificial variable remains positive in final optimal tableau.

2. Transportation Problems

2.1 Definition & Structure

• Sources (Origins): Factories with supply \(s_i\).

• Destinations: Markets with demand \(d_j\).

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

• Decision Variable: \(x_{ij}\) = units shipped from source \(i\) to dest \(j\).

2.2 Balanced vs Unbalanced

• Balanced: \(\sum s_i = \sum d_j\).

• Unbalanced: Add Dummy Row/Column with zero cost to absorb excess supply/demand.

• Penalty for Unmet Demand: Add dummy column with cost = penalty (e.g., Jun 2025 question). Treat as regular destination.

2.3 Initial Basic Feasible Solution (IBFS)

• North-West Corner (NWC) Rule: Start at top-left cell (1,1). Allocate as much as possible, move right/down. Simple but often costly.

• Vogel’s Approximation Method (VAM):

  1. Calculate penalty (difference between two smallest costs) for each row/column.

  2. Allocate to cell with lowest cost in row/col with highest penalty.

  3. Adjust supply/demand, cross-out satisfied row/col, recalc penalties.

  4. Most accurate IBFS (closer to optimal), preferred in exams.

• Least Cost Method (LCM): Allocate to cell with lowest cost among all, adjust, repeat.

2.4 Optimality Test: MODI Method (u-v Method)

1. For IBFS with \(m+n-1\) allocations, find dual variables \(u_i, v_j\):

   • Set \(u_1 = 0\) (or any).

   • \(u_i + v_j = c_{ij}\) for all occupied cells.

2. Calculate improvement index \(\Delta_{ij} = c_{ij} - (u_i + v_j)\) for all empty cells.

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

4. If any \(\Delta_{ij} < 0\), select most negative. Form closed loop by moving horizontally/vertically through occupied cells. Adjust allocations (+/- \(\theta\)) along loop. Repeat.

2.5 Degeneracy

• Definition: IBFS has fewer than \(m+n-1\) positive allocations (some basic variables = 0).

• Resolution: Allocate a very small quantity \(\epsilon\) (e.g., 0.001) to an empty cell to make it basic, maintaining feasibility. Use in MODI loop calculations.

2.6 Special Cases

• Maximization: Convert to minimization by subtracting all costs from a large constant \(M\) (e.g., \(M - c_{ij}\)).

• Prohibited Routes: Assign very high cost \(M\) (e.g., \(10^6\)).

3. Inventory Management (EOQ Models)

3.1 Basic EOQ Model

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

• Derivation: Minimize \(TC = \frac{DS}{Q} + \frac{QH}{2}\).

• Optimal Order Quantity:

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

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

• Key Calculations:

  • Number of orders/year = \(D / Q^*\)

  • Cycle time (time between orders) = \(365 / (D/Q^*)\) days (if D annual).

  • Total Annual Cost = \( \frac{DS}{Q^*} + \frac{Q^*H}{2} + PD \) (P = unit purchase price).

  • Average Inventory = \(Q^*/2\).

[!TIP] Exam Focus: Dec 2024, May 2024, Nov 2023 all had EOQ calculations. Ensure units consistency (e.g., if H is % of price, use \(H = i \times P\)).

3.2 EOQ with Quantity Discounts

• All-Units Discount: Entire order qualifies for lower price if \(Q \ge\) breakpoint.

• Incremental Discount: Only units above breakpoint get lower price.

• Procedure:

  1. Compute \(Q^*\) for each price break using \(H = i \times P\) (if holding cost is % of price).

  2. Check if \(Q^*\) falls within its price break's valid range. If not, use breakpoint quantity.

  3. Calculate Total Cost \(TC\) for each viable \(Q\) (including purchase cost \(PD\)).

  4. Choose \(Q\) with lowest TC.

3.3 EOQ with Planned Shortages (Backordering)

• Shortages allowed with backorder cost \(B\) per unit per year.

• Optimal Order Quantity:

  \[ Q^* = \sqrt{\frac{2DS}{H} \left( \frac{H+B}{B} \right)} \]

• Maximum Backorder Level:

  \[ B_{\max} = Q^* \left( \frac{B}{H+B} \right) \]

• When shortages not allowed: \(B \to \infty\), formula reduces to basic EOQ.

4. Supply Chain Management (SCM) Concepts

4.1 Bull-Whip Effect

• Definition: Demand distortion upstream (from retailer to manufacturer) where order variability > consumer demand variability.

• Causes:

  1. Demand Forecasting: Using past orders, not actual sales.

  2. Order Batching: Large, infrequent orders.

  3. Price Fluctuations: Forward buying during promotions.

  4. Rationing & Gaming: Shortage-induced over-ordering.

• Mitigation:

  • Information Sharing (POS data, EDI).

  • Vendor Managed Inventory (VMI).

  • Continuous Replenishment.

  • Eliminate incentives causing batching/gaming.

4.2 Logistics in SCM

• Inbound Logistics: Flow from suppliers to firm.

  • Activities: Procurement, receiving, inbound transportation, storage.

  • Importance: Ensures smooth production, reduces stockouts, lowers input costs.

• Outbound Logistics: Flow from firm to customers.

  • Activities: Finished goods storage, order processing, outbound transportation, delivery, customer service.

  • Importance: Directly impacts customer satisfaction, market reach, and revenue.

• Flows:

  • Material Flow: Physical movement of goods.

  • Information Flow: Orders, forecasts, inventory status (bidirectional).

  • Money Flow: Payments, credit, settlement (reverse direction).

4.3 Cross-Docking

• Definition: Inbound shipments are directly transferred to outbound trucks with minimal/no storage.

• Advantages:

  • Reduced inventory holding cost & space.

  • Faster response time, reduced handling.

  • Lower risk of obsolescence.

• Disadvantages:

  • Requires excellent coordination, real-time info systems.

  • High investment in docking infrastructure & IT.

  • Risk of delays propagating through network.

  • Not suitable for all products (needs predictable, high-volume flow).

4.4 Integration & Evolution

• MRP (Material Requirements Planning): Internal focus. Explodes BOM to schedule production/purchases based on MPS (Master Production Schedule). Dependent demand.

• ERP (Enterprise Resource Planning): Integrates all internal functions (MRP, finance, HR, sales) into a single database. Real-time info across departments.

• SCM: Extends integration externally to suppliers, distributors, customers. Manages end-to-end flows for competitive advantage.

• E-Business Linkage:

  • E-Procurement: Online purchasing, auctions.

  • E-Logistics: Online tracking, electronic bills of lading.

  • Information Visibility: Real-time data sharing across chain.

• Outsourcing & 3PL:

  • 3PL (Third-Party Logistics): Outsourcing logistics operations (transport, warehousing) to experts.

  • Benefits: Focus on core competencies, cost savings, expertise, scalability.

4.5 Expenditure & Opportunities in SCM

• Key Expenditures:

  • Technology: ERP, WMS, TMS, IoT, RFID.

  • Infrastructure: Warehouses, distribution centers, transportation fleet.

  • Human Resources: Skilled planners, logistics managers.

• Strategic Opportunities:

  • Cost Reduction: Via optimization, consolidation, 3PL.

  • Service Improvement: Faster delivery, reliability, customization.

  • Responsiveness: Agile supply chain to handle volatility.

4.6 Inventory Analysis Tools

• ABC Analysis:

  • Classify items by Annual Usage Value = (Annual Demand) × (Unit Cost).

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

  • B-items: ~20% of value, ~20-30% of items. Moderate control.

  • C-items: ~10% of value, ~50-70% of items. Loose control, simple methods.

• VED Analysis (for spare parts/criticality):

  • V (Vital): No stock = production stops. Highest priority.

  • E (Essential): High stockout cost, but some alternatives.

  • D (Desirable): Low impact if out of stock.

• Advantages of ABC/VED:

  • Focuses management attention & resources on critical items.

  • Optimizes inventory investment.

  • Simplifies control policies.

5. Queuing Theory

5.1 Basic Concepts

• Arrival Process: Pattern of customers entering system (e.g., Poisson).

• Service Mechanism: Number of servers, service time distribution (e.g., Exponential).

• Queue Discipline: Service order (FCFS, LCFS, priority).

• System Capacity: Finite/infinite waiting room.

• Notation: Kendall's Notation \(A/B/c\) (e.g., M/M/1: Poisson arrivals, Exponential service, 1 server).

5.2 Poisson Arrival Process

• Probability of \(k\) arrivals in time \(t\):

  \[ P(k) = \frac{e^{-\lambda t} (\lambda t)^k}{k!} \]

  where \(\lambda\) = average arrival rate (per unit time).

5.3 Exponential Service Time

• PDF: \(f(t) = \mu e^{-\mu t}, t \ge 0\)

  where \(\mu\) = average service rate.

• Probability service time > t:

  \[ P(T > t) = e^{-\mu t} \]

  \boxed{P(T > t) = e^{-\mu t}}

5.4 Single-Server Queue (M/M/1) - Performance Measures

• Traffic Intensity: \(\rho = \lambda / \mu\) (must be \(\rho < 1\) for stability).

• Average number in system: \(L = \rho / (1 - \rho)\)

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

• Average time in system: \(W = 1 / (\mu - \lambda)\)

• Average waiting time in queue: \(W_q = \lambda / (\mu(\mu - \lambda))\)

• Probability of 0 customers: \(P_0 = 1 - \rho\)

5.5 Solving Probability Problems (Exam Pattern)

• Given: Average service rate \(\mu\) (e.g., "20 customers served per hour" → \(\mu = 20\)/hr).

• Find: \(P(\text{service time} > t)\) → Use \(P(T > t) = e^{-\mu t}\).

  • Example (Nov 2023, Dec 2024): \(\mu = 20\)/hr, \(t = 15\) min = 0.25 hr → \(P = e^{-20 \times 0.25} = e^{-5}\).

• Find: \(P(k \text{ arrivals in interval } t)\) → Use Poisson formula with \(\lambda t\).

6. Project Management (PERT/CPM)

6.1 Phases of Project Management

1. Initiation: Define project, feasibility.

2. Planning: Scope, WBS, schedule (PERT/CPM), resources, budget.

3. Execution: Coordinate people/resources, implement plan.

4. Monitoring & Controlling: Track progress, manage changes, control costs/schedule.

5. Closure: Formal acceptance, handover, lessons learned.

6.2 Network Diagram Construction

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

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

• Drawing Rules:

  • No crossing arrows (use dummy nodes if needed).

  • Clear numbering (1,2,3...).

  • One start node, one end node.

  • Arrows point forward/downward.

6.3 PERT Time Estimates

• Optimistic (a): Best-case scenario (if everything goes right).

• Most Likely (m): Normal, realistic estimate.

• Pessimistic (b): Worst-case scenario (if everything goes wrong).

• Expected Time:

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

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

• Variance:

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

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

6.4 Critical Path Method (CPM)

• Forward Pass (from start):

  • Earliest Start (ES): Max of all predecessors' EF.

  • Earliest Finish (EF): \(ES + \text{duration}\).

• Backward Pass (from end):

  • Latest Finish (LF): Min of all successors' LS.

  • Latest Start (LS): \(LF - \text{duration}\).

• Slack/Float: \(LS - ES\) or \(LF - EF\).

  • Critical Activity: Slack = 0. Lies on Critical Path (longest path through network).

  • Critical Path: Path with zero total slack; any delay delays project.

6.5 PERT vs CPM

6.6 Project Completion Probability

• Project Mean Duration (\(T_E\)): Sum of \(t_e\) on critical path.

• Project Variance (\(V\)): Sum of \(\sigma^2\) on critical path (variance of sum = sum of variances for independent activities).

• Assuming Normal Distribution:

  \[ Z = \frac{D - T_E}{\sqrt{V}} \]

  where \(D\) = due date/target time.

• Find \(P(Z \le \text{calculated value})\) from standard normal table. Probability of completion by due date = \(P(Z \le z)\).

[!TIP] Common Pitfall: Only activities on the critical path contribute to project variance. Non-critical paths have slack, so their uncertainty doesn't affect project finish time directly.

7. Game Theory (Basic)

7.1 Strategies

• Pure Strategy: Player chooses one specific action (row/column) with certainty.

• Mixed Strategy: Player randomizes over actions, choosing each with a probability.

7.2 Dominance Rule

• Definition: Strategy A dominates Strategy B if it yields equal or better payoff against all opponent strategies, and strictly better against at least one.

• Reduction: Dominated strategies can be eliminated from payoff matrix, simplifying game.

7.3 Basic Assumptions

1. Rational Players: Each seeks to maximize own payoff.

2. Known Payoffs: All players know the payoff matrix.

3. Simultaneous Moves: Players choose without knowledge of opponent's choice (or independent choices).

4. Constant Sum (in zero-sum games): One's gain = other's loss.

8. Heuristic and Metaheuristic Algorithms

8.1 Heuristics

• Definition: Problem-specific, rule-of-thumb methods for quick, "good enough" solutions.

• Examples:

  • TSP: Nearest Neighbor, Cheapest Insertion.

  • Bin Packing: First-Fit, Best-Fit.

• Advantages: Fast, simple, easy to implement, intuitive.

• Disadvantages: No optimality guarantee, solution quality varies, problem-specific.

8.2 Metaheuristics

• Definition: General, high-level frameworks that guide heuristics to explore solution space, balancing exploration (new areas) and exploitation (local improvement).

• Examples:

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

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

  • Tabu Search: Uses memory (tabu list) to avoid cycling, explores neighborhoods.

• Advantages: Flexible, applicable to wide range of problems, often finds near-optimal solutions for complex NP-hard problems.

• Disadvantages: Parameter tuning needed, computationally intensive, no guarantee of optimality.

8.3 Applications in OR

• Scheduling: Job shop, flow shop.

• Routing: Vehicle Routing Problem (VRP), Traveling Salesman Problem (TSP).

• Combinatorial Optimization: Bin packing, set covering, facility location.