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

1.1 Introduction to Operations Research

Definition & Objective:

Operations Research (OR) is a scientific method for decision-making that uses quantitative techniques to allocate scarce resources optimally. Its primary objective is to provide rational, data-driven solutions to complex operational problems in business, industry, and defense.

Scope:

Applied in logistics, scheduling, inventory control, network design, project management, and strategic planning.

Characteristics of OR Models:

• Simplified representation of a real-world system.

• Objective function to maximize or minimize (e.g., profit, cost).

• Constraints that limit the decision variables.

• Quantitative and often mathematical.

Limitations of OR Models:

• Model risk: Simplifications may deviate from reality.

• Data dependency: Requires accurate, quantifiable data.

• Implementation gap: Solutions may face human/organizational resistance.

• High cost: For complex model development and computation.

Phases of OR Study:

1. Problem Identification: Define the problem, objectives, and constraints.

2. Model Building: Develop a mathematical/analytical model.

3. Solution: Apply algorithms (e.g., Simplex, shortest path) to solve the model.

4. Validation & Testing: Check model robustness and sensitivity.

5. Implementation: Deploy the solution in the real system.

Modeling Process Steps:

1. Observe the problem.

2. Define the system and variables.

3. Formulate assumptions.

4. Develop the model (equations/inequalities).

5. Solve and interpret.

6. Validate and implement.

Types of Models:

[!TIP]

Exam Focus: Distinguish deterministic vs. stochastic and static vs. dynamic with examples (e.g., EOQ is deterministic static; inventory with uncertain demand is stochastic).

1.2 Linear Programming (LP)

1.2.1 Formulation of Linear Programming Problems

General Form:

Maximize (or Minimize)

$$ Z = c_1x_1 + c_2x_2 + \dots + c_nx_n $$

subject to

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

$$ \vdots $$

$$ a_{m1}x_1 + a_{m2}x_2 + \dots + a_{mn}x_n \le (\ge, =) b_m $$

$$ x_1, x_2, \dots, x_n \ge 0 $$

Components:

• Decision variables ($$\displaystyle x_j $$): Quantities to determine.

• Objective function ($Z$): Linear function to optimize.

• Constraints: Linear inequalities/equalities.

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

Example Formulations:

• Resource Allocation: Maximize profit given limited labor/material.

• Blending: Mix raw materials to meet quality specs at min cost.

• Scheduling: Assign tasks to minimize total completion time.

[!TIP]

Common Pitfall: Forgetting non-negativity or misinterpreting "≤" vs. "≥" from problem statements.

1.2.2 Solution Methods

Simplex Method:

1. Convert inequalities to equations using slack/surplus variables.

2. Find an initial Basic Feasible Solution (BFS).

3. Optimality Test: Check $$\displaystyle c_j - z_j \ge 0 $$ (maximization) in the objective row. If all ≥ 0, current solution is optimal.

4. Pivot Operation: Select entering variable (most negative $$\displaystyle c_j - z_j $$) and leaving variable (minimum positive ratio test).

5. Iterate until optimal.

Key Conditions:

• Optimality: All $$\displaystyle c_j - z_j \le 0 $$ for minimization, $\ge 0$ for maximization.

• Multiple Solutions: If a non-basic variable has $$\displaystyle c_j - z_j = 0 $$ at optimum, alternate optimal solutions exist.

Big-M Method for Artificial Variables:

Used when initial BFS is not obvious (e.g., "≥" or "=" constraints).

1. Add artificial variables $$\displaystyle a_i $$ with high penalty M in objective.

   • Maximize: $$\displaystyle Z = \dots - M(a_1 + a_2 + \dots) $$

   • Minimize: $$\displaystyle Z = \dots + M(a_1 + a_2 + \dots) $$

2. Apply simplex; artificial variables must exit the basis for feasible solution.

3. If any artificial variable remains positive in final tableau → infeasible.

[!TIP]

Exam Trick: In Big-M, use -M for maximization and +M for minimization to penalize artificial variables.

1.2.3 Special Cases in LP

Degeneracy in Transportation:

Occurs when a basic cell's allocation becomes zero during allocation. Resolved by modifying allocations (e.g., add ε to zero cell and subtract from another in loop) to proceed.

1.2.4 Transportation and Assignment Problems

Transportation Problem Formulation:

• $m$ origins (supply $$\displaystyle s_i $$), $n$ destinations (demand $$\displaystyle d_j $$).

• Cost $$\displaystyle c_{ij} $$ per unit from origin $i$ to $j$.

• Minimize total cost: $$\displaystyle \sum_{i=1}^{m} \sum_{j=1}^{n} c_{ij} x_{ij} $$

• Subject to: $$\displaystyle \sum_j x_{ij} = s_i $$, $$\displaystyle \sum_i x_{ij} = d_j $$, $$\displaystyle x_{ij} \ge 0 $$.

Assignment Problem: Special case where $$\displaystyle m = n $$ and each $$\displaystyle s_i = d_j = 1 $$. Minimize total assignment cost. Solved by Hungarian Method.

[!TIP]

Past Paper Focus: Degeneracy meaning and resolution in transportation (May 2022).

1.3 Network Models

1.3.1 Project Management: CPM/PERT

Network Diagram:

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

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

Critical Path Method (CPM):

1. Forward Pass: Calculate Earliest Start Time (EST) and Earliest Finish Time (EFT).

   • $$\displaystyle EFT(i) = EST(i) + t_i $$

   • $$\displaystyle EST(j) = \max\{EFT(i)\} $$ for all predecessors $i$ of $j$.

2. Backward Pass: Calculate Latest Start Time (LST) and Latest Finish Time (LFT).

   • $$\displaystyle LFT(i) = \min\{LST(j)\} $$ for all successors $j$ of $i$.

   • $$\displaystyle LST(i) = LFT(i) - t_i $$.

3. Critical Path: Path with zero total slack. Activities on CP determine project duration.

4. Slack/Float:

   • Total Slack (TS): $$\displaystyle TS(i) = LST(i) - EST(i) $$.

   • Free Slack (FS): $$\displaystyle FS(i) = EST(\text{successor}) - EFT(i) $$.

PERT (Three-Time Estimates):

• Optimistic ($a$), Most Likely ($m$), Pessimistic ($b$).

• Expected time: $$\displaystyle t_e = \frac{a + 4m + b}{6} $$

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

• Project completion time = sum of $$\displaystyle t_e $$ on critical path.

[!TIP]

Exam Pattern: Draw network, find CP, EST/EFT/LST/LFT, TS/FS (May 2022, 2023).

1.3.2 Minimal Spanning Tree (MST)

Concept: Connects all nodes in a network with minimum total edge weight, without cycles.

Algorithms:

• Kruskal's: Sort edges by weight; add smallest edge that doesn't form a cycle.

• Prim's: Start from any node; add cheapest edge connecting tree to new node.

Applications: Network design, cluster analysis.

1.3.3 Traveling Salesman Problem (TSP)

Formulation: Find shortest possible route visiting each city exactly once and returning to start. NP-hard.

Solution Approaches:

• Heuristics: Nearest neighbor, cheapest insertion.

• Exact: Branch-and-bound, dynamic programming (for small $n$).

• LP Relaxation: Solve assignment problem, then add subtour elimination constraints.

1.4 Inventory Models

1.4.1 Deterministic Models: EOQ

Assumptions:

• Constant demand rate $D$.

• Fixed ordering cost $S$.

• Constant holding cost $H$ per unit per year.

• Instantaneous replenishment.

• No stockouts.

Derivation:

Total Cost (TC) = Ordering Cost + Holding Cost

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

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

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

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

Total Cost at EOQ:

$$ TC^* = \sqrt{2DSH} $$

Reorder Point (ROP):

$$ ROP = d \times L $$

where $d$ = daily demand, $L$ = lead time.

[!TIP]

Past Paper Example (May 2023): $$\displaystyle D=6000 $$/yr, $$\displaystyle S=150 $$, $$\displaystyle H=15 $$/unit/month → Convert $H$ to yearly: $$\displaystyle 15 \times 12 = 180 $$. Then $$\displaystyle Q^* = \sqrt{\frac{2 \times 6000 \times 150}{180}} $$.

1.4.2 Stochastic Inventory Models

• Newsvendor Model: Single-period with uncertain demand. Balances overage vs. underage costs.

  • Critical ratio: $$\displaystyle \frac{c_u}{c_u + c_o} $$ → find quantile of demand distribution.

• Continuous Review (s, Q): Order fixed $Q$ when inventory drops to reorder level $s$.

• Periodic Review (R, S): Review every $R$ periods, order up to $S$.

1.5 Queuing Theory

1.5.1 Components & Characteristics

Notation: Kendall's A/B/s

e.g., M/M/1: Poisson arrivals, exponential service, 1 server.

1.5.2 Service Disciplines

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

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

• Priority Service: Classes with different priorities.

• Random Service: Service order random (e.g., lottery).

1.5.3 Queuing Models: M/M/1

Assumptions:

• Poisson arrivals ($\lambda$), exponential service ($\mu$), 1 server, infinite capacity, FIFO.

Steady-State Condition: $$\displaystyle \rho = \frac{\lambda}{\mu} < 1 $$.

Performance Measures:

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

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

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

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

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

$$ \text{Server idle time} = 1 - \rho $$

[!TIP]

Past Paper Problem (May 2022): Repairman idle time → compute $1-\rho$. Postal clerk (May 2022, 2023) → compute $$\displaystyle L_q $$, $$\displaystyle W_q $$.

1.5.4 Numerical Problems

Given $\lambda$, $\mu$:

1. Check $$\displaystyle \rho < 1 $$.

2. Compute $$\displaystyle P_n $$, $$\displaystyle L_s $$, $$\displaystyle L_q $$, $$\displaystyle W_s $$, $$\displaystyle W_q $$ using formulas above.

1.6 Game Theory

1.6.1 Introduction to Competitive Games

• Zero-Sum Game: One's gain = other's loss. Total payoff = 0.

• Non-Zero-Sum: Gains/losses not necessarily balanced.

• Two-Person Game: Players A (rows) and B (columns).

• Pure Strategy: Specific chosen action.

• Mixed Strategy: Probability distribution over actions.

1.6.2 Pay-off Matrix

Rows: Player A's strategies.

Columns: Player B's strategies.

Entry $$\displaystyle a_{ij} $$: Payoff to A (and -$$\displaystyle a_{ij} $$ to B in zero-sum).

1.6.3 Solution Concepts

Saddle Point:

• Entry that is min in its row and max in its column.

• Value of game $v$ = saddle point value.

• Fair game: $$\displaystyle v = 0 $$.

Rule of Dominance:

• Row Dominance: If row $i$ ≤ row $j$ for all columns, row $i$ is dominated → delete row $j$.

• Column Dominance: If column $i$ ≥ column $j$ for all rows, column $i$ is dominated → delete column $i$.

• Reduces matrix size.

[!TIP]

Past Questions (May 2023): Pay-off matrix, saddle point, rule of dominance, fair game.

1.6.4 Solution Methods for Larger Games

• Iterative Methods: Fictitious play, iterated dominance (brief mention).

• Linear Programming Approach: Convert to LP for mixed strategies.

• Graphical Method: For 2×n or m×2 games.