UNIT 1: Operations Research and Supply Chain Fundamentals

1.0 Linear Programming (LP)

1.1 Problem Formulation

Translation of real-world decisions into a mathematical model.

Core Components:

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

2. Objective Function: The goal to be maximized or minimized.

   • Maximize: \(Z = c_1x_1 + c_2x_2 + ... + c_nx_n\)

   • Minimize: \(Z = c_1x_1 + c_2x_2 + ... + c_nx_n\)

3. Constraints: Limitations expressed as linear inequalities/equalities.

   • \(\le\) (≤) for "at most" resources.

   • \(\ge\) (≥) for "at least" requirements.

   • \(=\) for exact equality.

4. Non-negativity: \(x_j \ge 0\) for all \(j\) (physical quantities cannot be negative).

Formulation Steps:

1. Identify decision variables.

2. Construct the objective function.

3. Identify and formulate all constraints.

4. Add non-negativity restrictions.

[!TIP] Exam Focus: Past papers consistently ask to formulate an LP model from a word problem (e.g., resource allocation, profit maximization with labor/material constraints). Always define variables clearly first.

1.2 Simplex Method

An iterative algorithm for solving LP problems in standard form.

Standard Form Conversion:

• Maximization objective.

• All constraints are equalities (\(\le\) becomes + slack variable, \(\ge\) becomes - surplus variable + artificial variable).

• All variables \(\ge 0\).

Key Tableau Terms:

• Cj: Profit coefficient of each variable in the objective.

• Zj: Sum of (Cj of basic variables) × (corresponding column values in the row).

• Cj – Zj: Indicator row. For maximization, optimality is reached when all (Cj – Zj) ≤ 0.

• Entering Variable: The non-basic variable with the most positive (Cj – Zj) value.

• Leaving Variable: Determined by the Minimum Ratio Test (only for positive pivot column entries): \(\frac{\text{Quantity (RHS)}}{\text{Pivot Column Value}}\).

Handling Infeasibility: Artificial Variables

• Big-M Method: Assign a very large negative penalty (-M) to artificial variables in the objective for maximization. Remove them after they leave the basis.

• Two-Phase Method:

  • Phase I: Minimize the sum of all artificial variables. If optimal sum > 0, problem is infeasible.

  • Phase II: Use the feasible basis from Phase I (without artificial variables) to solve the original objective.

Special Cases from Optimal Tableau:

• Unbounded Solution: All entries in the pivot column \(\le 0\) → solution can increase infinitely.

• Multiple Optimal Solutions: At least one non-basic variable has (Cj – Zj) = 0.

• Infeasibility: Artificial variable remains in the basis at the end of Phase I.

[!TIP] Common Pitfall: The optimality condition is (Cj – Zj) ≤ 0 for MAXIMIZATION. For minimization, it's (Cj – Zj) ≥ 0. Always check the problem type.

1.3 Sensitivity Analysis (Implicit)

Examines how changes in parameters affect the optimal solution.

• Shadow Price (Dual Value): The change in optimal \(Z\) per unit increase in a constraint's RHS. Found in the Zj row under the slack/surplus column of that constraint. Valid only within the allowable range.

• Allowable Increase/Decrease: The range over which a coefficient (objective or RHS) can change without altering the optimal solution's basis. Found in the sensitivity report.

2.0 Transportation Problems

2.1 Problem Structure

• Origins (Rows): \(m\) sources with supply \(a_i\).

• Destinations (Columns): \(n\) sinks with demand \(b_j\).

• Cost Matrix: \(c_{ij}\) = cost to transport one unit from origin \(i\) to destination \(j\).

• Balanced: \(\sum a_i = \sum b_j\). Unbalanced: \(\sum a_i \neq \sum b_j\).

  • If \(\sum a_i > \sum b_j\): Add dummy destination with 0 cost and demand = \(\sum a_i - \sum b_j\).

  • If \(\sum a_i < \sum b_j\): Add dummy origin with 0 cost and supply = \(\sum b_j - \sum a_i\).

2.2 Initial Basic Feasible Solution (IBFS) Methods

A feasible solution has exactly \((m+n-1)\) occupied cells (basic variables) with non-zero allocations.

2.3 Optimality Test: MODI (Modified Distribution) Method

1. For an IBFS with \(m+n-1\) allocations, find dual variables \(u_i\) (for rows) and \(v_j\) (for columns) such that \(u_i + v_j = c_{ij}\) for all occupied cells.

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

2. Compute improvement indices \(\Delta C_{ij} = c_{ij} - (u_i + v_j)\) for all empty cells.

3. Optimality Check:

   • If all \(\Delta C_{ij} \ge 0\) (for minimization), solution is optimal.

   • If any \(\Delta C_{ij} < 0\), solution is not optimal. Select the most negative \(\Delta C_{ij}\) to enter the basis.

2.4 Degeneracy

• Definition: An IBFS or solution during iteration has fewer than \((m+n-1)\) positive allocations.

• Causes:

  1. In IBFS: Simultaneous exhaustion of a row supply and column demand during allocation (NWCR/VAM).

  2. During optimality test: An empty cell has \(\Delta C_{ij} = 0\) (indicates multiple optima, can cause degeneracy in next iteration).

• Resolution (to proceed with MODI):

  • Epsilon (ε) Method: Allocate a very small quantity (ε > 0) to one of the zero-cost empty cells to make the number of occupied cells = \(m+n-1\). Treat ε as a positive allocation in calculations.

  • Perturbation Method: Add a tiny perturbation (e.g., 0.0001) to all costs, resolve to get a non-degenerate start.

2.5 Transportation with Penalties (Unbalanced with Shortage Cost)

• Scenario: Some demand may be unfulfilled, incurring a penalty per unit.

• Formulation:

  1. Add a dummy origin (if total supply < total demand) with supply = total shortage capacity.

  2. For each destination \(j\) with potential shortage, the cost in the dummy origin row is the penalty cost \(p_j\).

  3. Solve the balanced transportation problem. Allocations to dummy origin represent unfulfilled demand.

• Decision: If optimal solution allocates to dummy origin for a destination, it's cheaper to pay the penalty than to fulfill that demand from real origins.

3.0 Inventory Management

3.1 Economic Order Quantity (EOQ) Model

Basic model for independent demand with instantaneous replenishment.

Assumptions:

• Constant, known demand rate (\(D\) units/year).

• 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 & Formula:

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

\[ TAC = \frac{D}{Q}S + \frac{Q}{2}H + DC \]

Minimize TAC w.r.t. \(Q\) by differentiation:

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

Key Calculations:

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

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

• Minimum Total Annual Cost (excluding purchase): \(TAC_{min} = \sqrt{2DSH}\)

• Maximum Inventory Level: \(Q^*\)

[!TIP] Exam Trap: Ensure units are consistent. If \(H\) is given per month, convert \(D\) to monthly or \(H\) to yearly. \(H\) is often a percentage of unit cost \(C\): \(H = i \times C\), where \(i\) is carrying cost rate.

3.2 EOQ Variations

Quantity Discounts:

• All-Units Discount: Discount applies to entire order quantity if \(Q \ge\) discount breakpoint.

• Incremental Discount: Discount applies only to units above the breakpoint.

• Decision Rule:

  1. Calculate EOQ using lowest unit cost (\(C_{min}\)).

  2. If EOQ is feasible (within discount range), compute TAC at EOQ.

  3. If EOQ is not feasible (below breakpoint), compute TAC at each breakpoint quantity.

  4. Choose the quantity with lowest TAC.

Finite Production Rate (EPQ):

• Used when production rate \(P > D\). Inventory builds gradually.

• Formula: \(EPQ = \sqrt{\frac{2DS}{H(1 - D/P)}}\)

• Maximum inventory \(= EPQ \times (1 - D/P)\)

3.3 ABC Analysis

Selective inventory control based on annual consumption value.

Steps:

1. Compute Annual Usage Value for each item: \( \text{Usage Value} = \text{Annual Demand} \times \text{Unit Cost} \).

2. Rank items in descending order of usage value.

3. Calculate Cumulative Percentage of total usage value.

4. Classify:

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

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

   • C-items: Remaining ~5% of value, ~50-70% of items. Loose control, simple systems.

3.4 VED Analysis

Selective control based on criticality (not value). Used for spare parts.

• V (Vital): Essential for operation. Stockout causes production halt. High priority, high safety stock.

• E (Essential): Important but not immediately critical. Stockout causes serious disruption. Medium priority.

• D (Desirable): Not critical. Stockout causes minor inconvenience. Low priority, low safety stock.

3.5 Advantages of ABC & VED

• Focused Control: Resources (managerial attention, capital) allocated according to importance.

• Cost Reduction: Reduces holding costs by avoiding overstocking C-items.

• Improved Availability: Ensures high availability for critical A/V items.

• Simplified Management: Reduces number of items requiring detailed monitoring.

4.0 Queuing Theory

4.1 Basic Model Components (M/M/1)

• Arrival Process: Poisson with rate \(\lambda\) (customers/unit time). Inter-arrival times are exponential with mean \(1/\lambda\).

• Service Mechanism: Exponential service times with rate \(\mu\) (customers/unit time). Mean service time = \(1/\mu\).

• Queue Discipline: Usually FCFS (First-Come-First-Served).

• System Capacity: Infinite (theoretical M/M/1).

• Population Size: Infinite.

Key Parameter: Traffic Intensity

\[ \rho = \frac{\lambda}{\mu} \quad \text{(must be } \rho < 1 \text{ for steady-state)} \]

4.2 Performance Measures (Steady-State)

For M/M/1:

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

• \(L\) = Average number of customers in the system (waiting + being served): \(L = \frac{\rho}{1-\rho}\)

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

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

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

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

4.3 Probability Calculations

• Exponential Service Time: Probability service time > \(t\):

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

• Poisson Arrivals: Probability of \(n\) arrivals in time \(t\):

  \[ P(n \text{ arrivals in } t) = \frac{(\lambda t)^n e^{-\lambda t}}{n!} \]

[!TIP] Exam Pattern: Questions often ask for probability of service time exceeding a given value (use exponential formula) or number of arrivals in an interval (use Poisson formula). Convert time units to match rate \(\lambda\) or \(\mu\).

4.4 Queue Disciplines

• FCFS/FIFO: First-Come-First-Served. Most common, fair.

• LCFS/LIFO: Last-Come-First-Served. Used in stack-based systems.

• Priority Scheduling: Customers have priorities (preemptive or non-preemptive).

• Random Selection: Service chosen randomly from queue.

5.0 Project Management (PERT/CPM)

5.1 Network Diagram Construction

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

• Activity-on-Node (AON): Nodes represent activities, arrows represent logical dependencies. More common, no dummies needed.

• Logical Relationships (Precedence):

  • FS (Finish-to-Start): Successor starts after predecessor finishes. (Most common).

  • SS (Start-to-Start): Successor starts after predecessor starts.

  • FF (Finish-to-Finish): Successor finishes after predecessor finishes.

  • SF (Start-to-Finish): Successor finishes after predecessor starts. (Rare).

5.2 Critical Path Method (CPM)

Deterministic activity times.

Forward Pass (Calculate Earliest Times):

• \(ES_i\) (Earliest Start of activity \(i\)) = max(\(EF\) of all immediate predecessors).

• \(EF_i = ES_i + t_i\) (where \(t_i\) = duration).

• Project duration \(T_E = \max(EF \text{ of all terminal activities})\).

Backward Pass (Calculate Latest Times):

• \(LF_i\) (Latest Finish of activity \(i\)) = min(\(LS\) of all immediate successors).

• \(LS_i = LF_i - t_i\).

• For terminal activities, \(LF = T_E\).

Float/Slack:

• Total Float (TF): \(TF_i = LS_i - ES_i = LF_i - EF_i\).

• Free Float (FF): \(FF_i = ES \text{ of next activity} - EF_i\).

• Critical Path: Path where TF = 0 for all activities. Longest path through the network. Determines project duration.

5.3 Program Evaluation and Review Technique (PERT)

Probabilistic activity times (for research/uncertain projects).

Three Time Estimates:

• \(t_o\) (Optimistic): Time if everything goes perfectly.

• \(t_m\) (Most Likely): Most realistic estimate.

• \(t_p\) (Pessimistic): Time if major problems occur.

Expected Time & Variance:

\[ t_e = \frac{t_o + 4t_m + t_p}{6} \]

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

Project Duration & Variance:

• \(T_E\) (Expected project duration) = sum of \(t_e\) along the critical path.

• Project variance \(V\) = sum of \(\sigma^2\) along the critical path (assuming independence).

5.4 Project Completion Probability

Assumes project duration follows Normal distribution (Central Limit Theorem).

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

where \(D\) = due date or target completion time.

• If \(D > T_E\): Probability of finishing by date \(D\) = \(P(Z \leq z)\).

• If \(D < T_E\): Probability of finishing by date \(D\) = \(P(Z \leq z)\) (will be < 0.5).

Use standard normal table to find probability.

[!TIP] Key Insight: The critical path can change if an activity on a near-critical path has a very high variance. PERT probability calculations always use the critical path's \(T_E\) and \(V\).

5.5 PERT vs. CPM

6.0 Supply Chain Management (SCM) Concepts

6.1 Bullwhip Effect

Amplification of demand variability as orders move upstream (from retailer to manufacturer).

Causes:

1. Demand Forecast Updating: Each echelon forecasts based on orders, not end-customer demand.

2. Order Batching: Large, infrequent orders to reduce ordering costs.

3. Price Fluctuations: Forward buying during promotions/discounts.

4. Rationing & Gaming: Suppliers allocate based on orders, not true demand; customers inflate orders.

Mitigation Strategies:

• VMI (Vendor Managed Inventory): Supplier manages inventory at customer's location.

• CPFR (Collaborative Planning, Forecasting, Replenishment): Sharing data and joint planning.

• Reduce Lead Times: Faster response reduces need for inventory buffer.

• Stabilize Prices: Eliminate forward buying.

• Order Smoothing: Smaller, more frequent orders.

Uses/Impacts: Understanding it helps reduce inventory costs, improve coordination, and increase supply chain efficiency.

6.2 Logistics in SCM

• Inbound Logistics: Activities from supplier to company (procurement, transportation, receiving, warehousing).

  • Importance: Directly impacts cost of goods sold, supplier relationships, and production continuity.

• Outbound Logistics: Activities from company to customer (distribution, delivery, customer service).

  • Importance: Determines customer satisfaction, market reach, and final product cost.

6.3 Cross-Docking

Direct transfer of inbound goods to outbound transportation with minimal or no storage.

Process:

1. Receiving: Inbound trucks unload.

2. Sorting/Consolidation: Goods sorted by destination.

3. Shipping: Loaded directly onto outbound trucks.

Advantages:

• Reduced inventory holding costs & space.

• Reduced handling & damage.

• Faster delivery, improved customer service.

• Lower working capital requirement.

Disadvantages:

• Requires excellent coordination and information systems.

• High investment in docking & material handling equipment.

• Risk of congestion if inbound/outbound schedules mismatch.

• Not suitable for all products (e.g., needing quality check, long storage).

6.4 Evolution: MRP → MRP II → ERP → SCM

6.5 Role of Inventory in Logistics

• Buffer against Uncertainty: Demand fluctuations, supply delays.

• Decoupling: Separates stages of production/distribution (allows each to operate independently).

• Economies of Scale: Larger production/order batches reduce per-unit costs.

• Trade-off: Holding Cost (capital, space, obsolescence) vs. Stockout Cost (lost sales, emergency orders). Goal is to optimize total cost for a given service level.

6.6 Outsourcing in SCM

Contracting non-core activities to third-party specialists (3PL/4PL).

Importance/Benefits:

• Focus on core competencies.

• Access to expertise, technology, and networks.

• Cost reduction (economies of scale, lower labor costs).

• Flexibility to scale operations up/down.

• Improved service levels through specialization.

Risks:

• Loss of direct control.

• Dependency on vendor (single source risk).

• Potential quality issues.

• Confidentiality/security risks.

• Hidden costs.

6.7 Flow in SCM

Three integrated flows:

1. Material Flow: Physical movement of goods from raw materials to end customer.

2. Money Flow: Financial transactions (payments, credit, settlements) opposite to material flow.

3. Information Flow: Data on orders, forecasts, inventory status, shipments. Bi-directional and drives the other two flows. Integration of all three is key to SCM efficiency.

7.0 Game Theory (Basic)

7.1 Pure and Mixed Strategies

• Pure Strategy: A player chooses a specific action with certainty (100% probability).

• Mixed Strategy: A player chooses among available actions according to a probability distribution (e.g., play A with 0.6, B with 0.4).

7.2 Basic Assumptions

• Rational Players: Each player aims to maximize their own payoff.

• Known Payoffs: The payoff matrix is common knowledge.

• Strategic Interdependence: One player's payoff depends on the joint action of all players.

• Simultaneous or Sequential Moves: (Often simultaneous in basic models).

• Constant-Sum or Non-Constant-Sum: Total payoff may be fixed (zero-sum) or variable.

7.3 Dominance Rule

• Dominant Strategy: A strategy that yields a higher payoff than any other strategy, regardless of what the opponent does.

• Dominated Strategy: A strategy that yields a lower payoff than some other strategy, regardless of what the opponent does.

• Iterative Elimination: Remove strictly dominated rows/columns iteratively to simplify the game. May lead to a dominant strategy equilibrium (if one exists for both players).

8.0 Heuristic and Metaheuristic Algorithms

8.1 Heuristics

• Definition: Problem-specific, rule-based procedures that provide good (but not necessarily optimal) solutions quickly.

• Examples:

  • Nearest Neighbor (TSP): Start at a city, go to nearest unvisited city.

  • Savings Algorithm (Vehicle Routing): Start with each customer on a separate route, merge routes if saving in distance.

• Pros: Fast, simple, easy to implement.

• Cons: No optimality guarantee, may get stuck in local optimum.

8.2 Metaheuristics

• Definition: High-level, problem-independent frameworks that guide the search process to explore the solution space effectively and escape local optima. They use heuristics as building blocks.

• Examples:

  • Genetic Algorithms (GA): Inspired by evolution (selection, crossover, mutation).

  • Simulated Annealing (SA): Inspired by metal cooling; accepts worse moves with decreasing probability.

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

  • Ant Colony Optimization (ACO): Inspired by ant foraging; uses pheromone trails.

• Pros: Good for large, complex, NP-hard problems; flexible; often finds near-optimal solutions.

• Cons: Computationally intensive; parameter tuning required; no guarantee of optimality.

8.3 Applications

• Scheduling: Job shop, flow shop.

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

• Portfolio Optimization.

• Network Design.

• Anywhere exact methods (like simplex) are too slow for large instances.

9.0 Network Logics in Project Management

9.1 Logical Relationships (Dependencies)

Defines the sequence of activities.

• FS (Finish-to-Start): B cannot start until A finishes. (Most common: A → B).

• SS (Start-to-Start): B cannot start until A starts. (e.g., Pour foundation → Cure foundation).

• FF (Finish-to-Finish): B cannot finish until A finishes. (e.g., Write code → Test code).

• SF (Start-to-Finish): B cannot finish until A starts. (Rare, e.g., Start night shift → Finish day shift).

Lag & Lead:

• Lag: Delay between dependencies. (e.g., FS + 5 days: Wait 5 days after predecessor finishes).

• Lead: Overlap/Acceleration. Negative lag. (e.g., FS - 2 days: Successor can start 2 days before predecessor finishes).

9.2 Diagramming Conventions

• Avoid Dummies (in AON): Use correct logical relationships instead.

• Maintain Correct Precedence: Ensure all immediate predecessors are correctly linked.

• Activity Duration Placement: Clearly shown on the node (AON) or arrow (AOA).

• Consistency: Use the same convention throughout the network.