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

Unit 3: Operations Research (CE-604(D)) - Exam-Focused Short Notes

1. Introduction to Operations Research

Definition: Operations Research (OR) is a scientific, analytical approach to decision-making. It uses mathematical models, statistics, and algorithms to find optimal or near-optimal solutions to complex problems involving the allocation of scarce resources.

Phases of OR (May 2023):

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

2. Constructing a Mathematical Model: Translate the problem into equations/inequalities (e.g., LP, network).

3. Deriving a Solution: Use analytical or numerical methods (e.g., Simplex, PERT) to solve the model.

4. Testing the Model and Solution: Validate the model with real data; perform sensitivity analysis.

5. Implementing the Solution: Apply the solution in the real-world context and establish controls.

Characteristics of OR (May 2022):

• Interdisciplinary: Uses mathematics, economics, engineering, psychology.

• System-Oriented: Considers the entire system and interdependencies.

• Scientific: Uses quantitative data and scientific methods.

• Optimization: Seeks the best solution from feasible alternatives.

• Team Approach: Often requires collaboration between OR experts and managers.

Limitations of OR Models (May 2022):

• Model Simplification: Real-world complexities are often simplified.

• Quantification Difficulty: Some factors (e.g., morale, brand value) are hard to quantify.

• Data Requirements: Requires accurate, extensive data which may be unavailable.

• Implementation Gap: The optimal solution may face resistance from personnel.

• Cost: Model development and solution can be expensive and time-consuming.

Steps of Modeling (May 2023):

1. Observation: Identify the problem area and system boundaries.

2. Definition: Clearly state objectives, constraints, and decision variables.

3. Formulation: Build the mathematical model (e.g., objective function, constraints).

4. Solution: Apply appropriate solution techniques.

5. Validation & Testing: Check model validity and robustness.

6. Implementation: Apply the solution and monitor results.

Exam Tip: Be prepared to distinguish between phases (process stages) and steps of modeling (technical model-building steps).

2. Linear Programming (LP)

Formulation of LP Problems:

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

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

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

• Constraints: Linear inequalities/equations representing resource limits.

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

• Non-negativity: $$\displaystyle x_i \ge 0 $$ for all $i$.

Simplex Method (May 2022):

An iterative algorithm to find the optimal BFS. Steps:

1. Convert inequalities to equations using slack ($+s$) for $\le$ and surplus ($-s$) for $\ge$ variables.

2. Find an initial Basic Feasible Solution (BFS) (usually slack variables as basics).

3. Optimality Test: Calculate $$\displaystyle z_j - c_j $$ for non-basic variables in the tableau.

   • For Maximization: If all $$\displaystyle z_j - c_j \ge 0 $$, current solution is optimal.

   • For Minimization: If all $$\displaystyle z_j - c_j \le 0 $$, current solution is optimal.

4. Pivot Operation: If not optimal, select entering variable (most positive $$\displaystyle z_j-c_j $$ for max) and leaving variable (minimum positive ratio test). Perform row operations to update tableau.

5. Repeat until optimal.

Handling Inequalities:

• $\le$ constraint: Add slack variable ($s \ge 0$).

• $\ge$ constraint: Subtract surplus variable ($s \ge 0$) and often add an artificial variable ($a \ge 0$) for initial BFS (used in Big-M/Two-Phase).

Big-M Method (for Minimization with ≥ constraints - May 2022):

Used to handle ≥ constraints by penalizing artificial variables in the objective function. Steps for Minimization:

1. Convert to standard form: For $\ge$ constraint, subtract surplus and add artificial variable $$\displaystyle a_i $$.

2. Modify objective: $$\displaystyle Z_{new} = Z_{original} + M \cdot \sum a_i $$, where $M$ is a very large positive number.

3. Apply Simplex. In optimality test, treat $M$ as a large coefficient. Artificial variables must exit the basis ($$\displaystyle a_i=0 $$) for a feasible solution.

4. If any $$\displaystyle a_i > 0 $$ in optimal tableau, problem is infeasible.

Basic Feasible Solution (BFS) (May 2022):

A solution where:

• Number of basic variables = number of constraints.

• Basic variables satisfy all constraints.

• All basic variables $\ge 0$.

• Non-basic variables are set to zero.

• Corresponds to a corner point of the feasible region.

Optimal Solution (May 2022):

A feasible solution that maximizes (or minimizes) the objective function. In Simplex, reached when all $$\displaystyle z_j-c_j $$ satisfy optimality condition.

Unbounded Solution (May 2022):

Occurs when the objective function can increase (max) or decrease (min) indefinitely. In Simplex, indicated if all entries in the pivot column are $\le 0$ (for max) during ratio test.

Transportation Problem (TP):

Formulation: Minimize total shipping cost from $m$ origins (supply) to $n$ destinations (demand). Methods for Initial BFS:

1. Northwest Corner Rule: Start top-left, allocate as much as possible, move right/down.

2. Least Cost Method: Allocate to cell with lowest cost first.

3. Vogel's Approximation Method (VAM): Allocate based on penalty costs (most accurate).

Degeneracy in Transportation (May 2022):

• Cause: Initial or subsequent BFS has fewer than $(m+n-1)$ positive allocations (occupied cells).

• Consequence: Loop formation issue during MODI method; cycling possible.

• Resolution: Introduce a very small epsilon ($\epsilon$) allocation in an unoccupied cell to make $(m+n-1)$ allocations, then proceed.

Application: Police Scheduling Problem (May 2022) – LP Formulation:

• Variables: $$\displaystyle x_i $$ = number of officers starting on day $i$ (Mon-Sun).

• Objective: Minimize total officers $$\displaystyle \min Z = \sum_{i=1}^{7} x_i $$.

• Constraints: Daily requirement met by officers working that day and the previous 4 days (5-day work week). E.g., for Monday: $$\displaystyle x_{\text{Mon}} + x_{\text{Sun}} + x_{\text{Sat}} + x_{\text{Fri}} + x_{\text{Thu}} \ge 18 $$.

• Non-negativity: $$\displaystyle x_i \ge 0 $$.

3. Network Models

PERT / CPM (May 2022, 2023)

Network Diagram Construction:

• Activity: Task represented by an arrow (A->B).

• Event/Node: Start/end point of activities, represented by a circle.

• Dummy Activity: Zero duration arrow used to show dependency without consuming resources/time.

Forward Pass (Earliest Times):

1. Start at node 0: $$\displaystyle E_0 = 0 $$.

2. For each node $j$: $$\displaystyle E_j = \max_{i} (E_i + t_{ij}) $$.

3. $$\displaystyle E_{\text{last}} $$ = Expected Project Completion Time.

Backward Pass (Latest Times):

1. Start at last node: $$\displaystyle L_{\text{last}} = E_{\text{last}} $$.

2. For each node $i$: $$\displaystyle L_i = \min_{j} (L_j - t_{ij}) $$.

Critical Path Determination (May 2022):

Path where $$\displaystyle E_i = L_i $$ for all nodes. Activities with zero Total Slack.

• Total Slack (TS): $$\displaystyle TS_{ij} = L_j - E_i - t_{ij} $$. Latest start - Earliest start.

• Free Slack (FS): $$\displaystyle FS_{ij} = E_j - E_i - t_{ij} $$. Does not delay successor.

Exam Tip: Critical path has zero total slack. Free slack can be zero or positive on critical path if multiple parallel paths exist.

Expected Project Completion Time (Probabilistic - May 2022):

For each activity, use three time estimates:

• $$\displaystyle t_o $$: Optimistic

• $$\displaystyle t_m $$: Most likely

• $$\displaystyle t_p $$: Pessimistic Expected Time: $$\displaystyle t_e = \frac{t_o + 4t_m + t_p}{6} $$ Variance: $$\displaystyle \sigma^2 = \left(\frac{t_p - t_o}{6}\right)^2 $$

Project completion time $T$ is sum of $$\displaystyle t_e $$ on critical path. Project variance $$\displaystyle \sigma_p^2 $$ is sum of variances on critical path. Probability of completion by time $T'$: $$\displaystyle Z = \frac{T' - T}{\sqrt{\sigma_p^2}} $$, use standard normal table.

Travelling Salesman Problem (TSP) (May 2023)

• Problem: Find the shortest possible route that visits each city exactly once and returns to the start.

• Solution Approaches:

  • Brute Force: Check all $(n-1)!/2$ permutations (impractical for $$\displaystyle n>10 $$).

  • Heuristics: Nearest Neighbor, Cheapest Insertion (quick, near-optimal).

  • Exact Methods: Branch and Bound, Cutting Plane (guaranteed optimal, computationally heavy).

Minimal Spanning Tree (MST) (May 2023)

Connects all nodes with minimum total edge weight and no cycles. Algorithms:

1. Kruskal's: Sort edges by weight. Add smallest edge that doesn't form a cycle until $n-1$ edges.

2. Prim's: Start from any node. Grow tree by adding cheapest edge connecting tree to a new node. Applications: Network design (telecom, pipelines), cluster analysis.

4. Inventory Models

Deterministic: Economic Order Quantity (EOQ) (May 2022, 2023)

Assumptions:

• Demand rate $D$ is constant and known.

• Lead time is zero or constant.

• No stockouts (backorders not allowed).

• Order quantity $Q$ arrives instantaneously.

• Ordering cost $S$ per order is fixed.

• Holding cost $h$ per unit per year is fixed.

• Unit purchase cost $c$ is constant (no discounts).

Derivation & Formula:

Total Annual Cost: $$\displaystyle TC = \frac{D}{Q}S + \frac{Q}{2}h + Dc $$

Minimize $TC$ w.r.t $Q$. Differentiate and set to zero.

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

• $D$ = Annual demand (units/year)

• $S$ = Ordering cost (Rs/order)

• $h$ = Holding cost (Rs/unit/year)

Key Results at EOQ:

• Number of orders/year = $$\displaystyle D/Q^* $$

• Time between orders = $$\displaystyle Q^*/D $$ years

• Maximum inventory level = $$\displaystyle Q^* $$

• Average inventory = $$\displaystyle Q^*/2 $$

• Total Annual Cost at EOQ: $$\displaystyle TC_{min} = \sqrt{2DS h} + Dc $$

Exam Tip: If holding cost is given as a percentage of unit cost ($i\%$), then $$\displaystyle h = i \times c $$.

EOQ with Price Breaks:

• Compute EOQ for each price bracket.

• Feasible EOQ = one that falls within its price bracket's quantity range.

• Calculate $TC$ at feasible EOQ and at minimum quantity of all lower price brackets.

• Choose $Q$ with lowest $TC$.

Stochastic Inventory Models (May 2023)

Need: Demand or lead time is uncertain. Newsvendor Model (Single-period):

• For perishable goods (newspapers, fashion).

• Balance overage cost ($$\displaystyle c_o $$) vs underage cost ($$\displaystyle c_u $$).

• Critical Ratio: $$\displaystyle CR = \frac{c_u}{c_u + c_o} $$

• Optimal Order Quantity $$\displaystyle Q^* $$: The smallest $Q$ such that $P(D \le Q) \ge CR$.

• $D$ = random demand with known distribution.

Continuous Review (s, Q) Model:

• Reorder Point (ROP) $s$: Inventory level triggering an order of fixed $Q$.

• $$\displaystyle s = \text{Expected demand during lead time} + \text{Safety Stock} $$.

• Safety Stock depends on desired service level and demand/lead time variability.

5. Queuing Theory

Queuing System Components (May 2023, 2022):

1. Arrival Process: Pattern of customers entering (e.g., Poisson rate $\lambda$).

2. Service Mechanism: Number of servers ($s$), service time distribution (e.g., Exponential with mean $1/\mu$).

3. Queue Discipline: Order of service (FIFO, LIFO, Priority).

4. Capacity: Maximum number of customers allowed in system (finite/infinite).

5. Population: Source of customers (finite/infinite).

Kendall's Notation (May 2023): $A/B/s$

• $A$: Arrival distribution (M=Markovian/Poisson, D=Deterministic, G=General).

• $B$: Service distribution (M, D, G).

• $s$: Number of servers.

• Example: M/M/1 = Poisson arrivals, Exponential service, 1 server.

Service Disciplines (May 2022):

• FIFO (First-In-First-Out): "First come, first served." Most common.

• LIFO (Last-In-First-Out): "Last come, first served." (Stack).

• Priority Service: Customers have priorities (e.g., emergency).

• Random Service: Next customer chosen randomly from queue.

Single-Server Model: M/M/1 (May 2023, 2022)

• Arrival rate $\lambda$, service rate $\mu$ ($$\displaystyle \mu > \lambda $$ for stability).

• Utilization Factor: $$\displaystyle \rho = \lambda / \mu < 1 $$.

• Formulas:

$$L = \frac{\rho}{1-\rho} \quad \text{(Avg. number in system)}$$

$$L_q = \frac{\rho^2}{1-\rho} \quad \text{(Avg. number in queue)}$$

$$W = \frac{1}{\mu - \lambda} \quad \text{(Avg. time in system)}$$

$$W_q = \frac{\lambda}{\mu(\mu - \lambda)} \quad \text{(Avg. waiting time in queue)}$$

$$P_n = (1-\rho)\rho^n \quad \text{(Prob. of exactly n customers)}$$

Exam Tip: For M/M/1, $$\displaystyle L = L_q + \rho $$ and $$\displaystyle W = W_q + 1/\mu $$. Always check $$\displaystyle \rho < 1 $$ for a steady-state solution.

Numerical Problem Approach (May 2023: Repairman; May 2022: Postal Clerk):

1. Identify $\lambda$ (arrival rate), $\mu$ (service rate).

2. Compute $$\displaystyle \rho = \lambda/\mu $$.

3. Apply formulas directly. For repairman idle time: $$\displaystyle P(\text{idle}) = 1 - \rho $$.

6. Game Theory

Basic Concepts (May 2023, 2022)

• Pay-off Matrix: Tabular representation of payoffs for each combination of strategies. Rows = Player A (maximizer), Columns = Player B (minimizer).

• Two-Person Zero-Sum Game (May 2023): One player's gain is the other's loss. Total payoff is zero.

• Saddle Point (May 2022, 2023): Element that is minimum in its row and maximum in its column. Value $V$ of the game. Pure strategy solution exists.

• Fair Game: Value of the game $$\displaystyle V = 0 $$.

• Rule of Dominance (May 2022): If a strategy yields a worse payoff than another strategy for a player against all opponent's strategies, it is dominated and can be deleted.

Solution Methods:

• Pure Strategies: Find saddle point by comparing row minima and column maxima.

  • Maximin (Player A) = Min of row maxima.

  • Minimax (Player B) = Max of column minima.

  • If Maximin = Minimax = $V$, saddle point exists at that cell.

• Mixed Strategies (if no saddle point): Players randomize over strategies. Solve using:

  • 2x2 Game: Algebraic method (solving equations).

  • m x n Game: Graphical method (for 2 strategies of one player) or Simplex method (general).

7. Allocation and Assignment Problems

Allocation Problem (May 2023: Strawberry Crates)

• Formulation as LP:

  • Variables: $$\displaystyle x_{ij} $$ = crates allocated to store $j$ from total supply.

  • Objective: Maximize total expected profit $$\displaystyle \max \sum_{i}\sum_{j} p_{ij} x_{ij} $$.

  • Constraints:

    • Total crates allocated = Supply: $$\displaystyle \sum_{j} x_{ij} = \text{Total Crates} $$ (for each source $i$ if multiple sources).

    • Demand limits per store: $$\displaystyle \sum_{i} x_{ij} \le \text{Max crates store } j \text{ can sell} $$.

    • $$\displaystyle x_{ij} \ge 0 $$.

• Solution Methods: Can be solved as Transportation Problem (if supply=demand) or general LP (Simplex).

Assignment Problem (Special case of TP):

• $n$ jobs, $n$ persons. Cost matrix $$\displaystyle c_{ij} $$.

• Objective: Minimize total cost (or maximize profit) with one job per person.

• Methods: Hungarian Algorithm (most efficient), or as TP with $$\displaystyle m=n $$.

Application: Police Scheduling (May 2022) – LP Formulation: (See detailed formulation in Transportation Problem section above)

• Variables: $$\displaystyle x_d $$ = officers starting on day $d$.

• Objective: $$\displaystyle \min \sum_{d=1}^{7} x_d $$.

• Constraints: For each day $k$: $$\displaystyle x_k + x_{k-1} + x_{k-2} + x_{k-3} + x_{k-4} \ge \text{Officers needed on day } k $$ (indices modulo 7).

• $$\displaystyle x_d \ge 0 $$ and integer (often solved as LP and rounded).