Operation Research (CE-604 (D)) Unit 2 Notes

UNIT 2: OPERATION RESEARCH (CE-604(D))

1. FOUNDATIONS OF OPERATION RESEARCH

Definition and Nature of Operation Research (O.R.)

Definition: O.R. is the application of scientific methods, techniques, and tools to the analysis of complex systems involving the allocation of scarce resources, with the objective of providing optimal or near-optimal solutions to decision-making problems.
Nature: It is interdisciplinary, systems-oriented, and uses quantitative approaches. It focuses on finding best solutions under given constraints, not just any solution.

Phases/Steps of an O.R. Study

Problem Formulation & Definition: Clearly state the problem, objectives, constraints, and identify decision variables.
Model Construction: Develop a mathematical or symbolic representation (model) of the real-world problem.
Model Solution: Apply analytical or computational methods (e.g., Simplex, Hungarian) to derive an optimal solution.
Model Validation & Testing: Check the model's robustness and sensitivity to input changes. Ensure it accurately represents reality.
Implementation of Results: Put the optimal solution into practice and monitor its performance.

Modeling in O.R.

Definition: A model is an abstract representation of a real system used for analysis and prediction.
Types:
- Iconic: Physical replica (e.g., a scale model).
- Analogic: Uses one property to represent another (e.g., electrical circuit for traffic flow).
- Mathematical: Uses equations, inequalities, and functions (most common in OR).
Steps in Modeling: Formulation → Data Collection → Solution → Validation → Implementation.
Characteristics of a Good Model: Simplicity, validity, cost-effectiveness, and ease of solution.
Limitations: Data quality issues, model assumptions may not hold, difficulty in quantifying all factors, and resistance to implementation.

[!TIP] Exam Focus: Be prepared to list all 5 phases in order and distinguish between model types with examples.

2. LINEAR PROGRAMMING (LP)

Fundamental Concepts

Definition: Technique for optimizing (maximizing or minimizing) a linear objective function subject to linear equality/inequality constraints and non-negativity restrictions.
Components:
- Decision Variables ($$\displaystyle x_1, x_2, ... $$): Quantities to be determined.
- Objective Function ($Z$): Linear function of decision variables to be optimized.
- Constraints: Linear inequalities/equations representing resource limits.
- Non-negativity: $$\displaystyle x_j \ge 0 $$ for all $j$.
Assumptions:
- Linearity: Proportionality and additivity in objective & constraints.
- Divisibility: Variables can take fractional values.
- Certainty: All coefficients are known with certainty.
- Non-negativity: Variables cannot be negative.

Formulation of LPP from Word Problems

Identify decision variables.
Construct the objective function (maximize profit/minimize cost).
Identify and write all constraints.
Add non-negativity constraints.

Graphical Method

Used for problems with two decision variables.
Steps:
1. Plot each constraint as a line (equality).
2. Identify the feasible region (common area satisfying all constraints, usually a polygon).
3. Locate corner points (extreme points) of the feasible region.
4. Evaluate the objective function $Z$ at each corner point.
5. The optimal solution is the corner point giving the best $Z$ value.
Solution Types:
- Feasible Solution: Satisfies all constraints.
- Infeasible: No point satisfies all constraints.
- Unbounded: Feasible region is open-ended in the direction of optimization; $Z$ can increase/decrease indefinitely.
- Multiple Optimal Solutions: Entire edge of the feasible region gives the same optimal $Z$ value.

[!TIP] Common Pitfall: If the objective function lines are parallel to a constraint edge on the boundary of the feasible region, you have multiple optimal solutions.

Simplex Method

Standard Form:
- Maximization: $$\displaystyle \text{Max } Z = c^T x $$ subject to $Ax \le b$, $x \ge 0$.
- Convert $\le$ to equality by adding slack variables ($$\displaystyle s_i \ge 0 $$).
- Convert $\ge$ by subtracting surplus variables and adding artificial variables ($$\displaystyle a_i \ge 0 $$) for Phase-I/ Big-M.
- Convert $$\displaystyle = $$ by adding artificial variables.
Iterative Procedure:
1. Optimality Test: Check $$\displaystyle c_j - z_j \le 0 $$ (for Max) in the tableau. If all $\le 0$, current solution is optimal.
2. Pivot Column Selection: Choose entering variable with most positive $$\displaystyle (c_j - z_j) $$ (for Max).
3. Pivot Row Selection: Compute minimum ratio test ($$\displaystyle \frac{\text{RHS}}{\text{Pivot Column Coefficient}} $$ for positive coefficients). The row with minimum ratio determines the leaving variable.
4. Pivot Operation: Use elementary row operations to make the pivot element = 1 and all other elements in the pivot column = 0.
5. Repeat until optimality condition is met.
Interpretation of Final Tableau:
- Solution values for basic variables are in the RHS column.
- Shadow Prices (Dual Values): Row corresponding to RHS in the final tableau (under $$\displaystyle c_j - z_j $$ row) give the marginal value of one additional unit of each resource.
- Reduced Costs: $$\displaystyle (c_j - z_j) $$ for non-basic variables indicate the amount by which the objective coefficient must improve before that variable enters the basis.

Special Cases in Simplex

Degeneracy: A basic variable becomes zero in a simplex iteration.
- Cause: Tie for minimum ratio during pivot row selection.
- Consequence: Potential for cycling (infinite loop without improvement), stalling.
- Resolution: Use lexicographic rule or introduce artificial variables (Big-M/Two-Phase ensures non-degeneracy).
Unbounded Solution: Identified when, for the entering variable, all coefficients in its column are $\le 0$. The minimum ratio test cannot be performed. The feasible region is unbounded in the direction of optimization.
Alternative Optimal Solutions: Identified when, at optimality, a non-basic variable has $$\displaystyle (c_j - z_j) = 0 $$. The variable can enter the basis without changing $Z$, leading to another optimal solution.

Big-M Method & Two-Phase Method

Purpose: To handle artificial variables introduced for $\ge$ and $$\displaystyle = $$ constraints.
Big-M Method:
1. For each artificial variable $$\displaystyle a_i $$, add $$\displaystyle -M \cdot a_i $$ (for Max) or $$\displaystyle +M \cdot a_i $$ (for Min) to the objective function, where $M$ is a very large positive number.
2. Proceed with standard simplex steps. Artificial variables must leave the basis in the final solution (their value = 0).
Two-Phase Method:
1. Phase-I: Minimize sum of all artificial variables. If minimum sum > 0, problem is infeasible. If minimum sum = 0, proceed to Phase-II.
2. Phase-II: Use the feasible basis from Phase-I (with artificial variables removed) and solve the original objective function.

Duality in Linear Programming

Definition: Every primal LP problem has a corresponding dual LP problem.
Primal-Dual Relationship (Primal: Max, Dual: Min):

| Primal (Max) | Dual (Min) | | :--- | :--- | | Objective: Max $$\displaystyle Z = c^T x $$ | Objective: Min $$\displaystyle W = b^T y $$ | | Constraints: $Ax \le b$ | Constraints: $$\displaystyle A^T y \ge c $$ | | Variables: $x \ge 0$ | Variables: $y \ge 0$ |
Rules for Constructing Dual:
1. Primal constraints become dual variables ($$\displaystyle y_j $$).
2. Primal RHS ($$\displaystyle b_i $$) become dual objective coefficients.
3. Primal objective coefficients ($$\displaystyle c_j $$) become dual RHS.
4. Primal variable $$\displaystyle x_j $$ becomes dual constraint $j$.
5. $\le$ primal constraint $$\displaystyle \rightarrow $$ $\ge$ dual variable; $\ge$ primal constraint $$\displaystyle \rightarrow $$ $\le$ dual variable; $$\displaystyle = $$ primal constraint $$\displaystyle \rightarrow $$ unrestricted dual variable.
6. Unrestricted primal variable $$\displaystyle \rightarrow $$ $$\displaystyle = $$ dual constraint.
Economic Interpretation: Dual variables ($$\displaystyle y_j $$) are shadow prices—marginal value of one additional unit of resource $j$.
Fundamental Duality Theorems:
1. Weak Duality: For any feasible primal $x$ and dual $y$, $$\displaystyle c^T x \le b^T y $$ (Max primal, Min dual).
2. Strong Duality: If either primal or dual has an optimal solution, so does the other, and optimal objective values are equal: $$\displaystyle Z^* = W^* $$.
3. Complementary Slackness: At optimality, $$\displaystyle x_j (c_j - a_j^T y) = 0 $$ and $$\displaystyle y_i (b_i - a_i x) = 0 $$.

[!TIP] Exam Focus: Be able to construct the dual from a given primal (and vice-versa) by following the relationship table. Interpret shadow prices from the final simplex tableau.

3. TRANSPORTATION PROBLEM (TP)

Definition and Mathematical Model

Problem: Minimize total transportation cost of moving a single commodity from $m$ origins (supplies) to $n$ destinations (demands).
Model:
- Let $$\displaystyle c_{ij} $$ = cost to transport one unit from origin $i$ to destination $j$.
- Let $$\displaystyle x_{ij} $$ = units transported from $i$ to $j$.
- $$\displaystyle \text{Min } Z = \sum_{i=1}^{m} \sum_{j=1}^{n} c_{ij} x_{ij} $$
- Subject to:
  
  $$\displaystyle \sum_{j=1}^{n} x_{ij} = a_i $$ (Supply at $i$)
  
  $$\displaystyle \sum_{i=1}^{m} x_{ij} = b_j $$ (Demand at $j$)
  
  $$\displaystyle x_{ij} \ge 0 $$
- Balanced Problem: $$\displaystyle \sum a_i = \sum b_j $$. If unbalanced, add a dummy row/column with zero cost.

Initial Basic Feasible Solution (IBFS) Methods

All methods allocate $m+n-1$ basic variables (if no degeneracy).
North-West Corner Rule (NWCR):
1. Start at top-left cell (1,1).
2. Allocate as much as possible: $$\displaystyle x_{11} = \min(a_1, b_1) $$.
3. Adjust supply/demand. If $$\displaystyle a_1 $$ exhausted, move down; if $$\displaystyle b_1 $$ exhausted, move right; if both exhausted, move diagonally.
4. Repeat until all allocations are made.
Least Cost Method (LCM) / Matrix Minima Method:
1. Find cell with minimum $$\displaystyle c_{ij} $$.
2. Allocate $\min$(remaining supply, remaining demand) to that cell.
3. Cross out exhausted row/column, adjust, and repeat.
Vogel's Approximation Method (VAM):
1. For each row and column, compute penalty = difference between two smallest costs.
2. Select row/column with highest penalty.
3. Allocate in its cell with minimum cost.
4. Adjust, recalculate penalties, and repeat.
- Note: VAM generally gives IBFS closer to optimal than NWCR or LCM.

Optimality Test

Modified Distribution (MODI) / UV Method:
1. For IBFS with $m+n-1$ allocations, find $$\displaystyle u_i $$ and $$\displaystyle v_j $$ such that $$\displaystyle u_i + v_j = c_{ij} $$ for all basic cells.
2. Compute opportunity costs (unused cells): $$\displaystyle \Delta_{ij} = c_{ij} - (u_i + v_j) $$.
3. Optimality Check: If all $$\displaystyle \Delta_{ij} \ge 0 $$, solution is optimal.
4. If any $$\displaystyle \Delta_{ij} < 0 $$, solution is not optimal. Select cell with most negative $$\displaystyle \Delta_{ij} $$ for allocation.
5. Form a closed loop for the selected cell, adjust allocations (+/-), and repeat.
Stepping Stone Method:
1. For each unoccupied cell, trace a closed loop (only horizontal/vertical moves) through occupied cells.
2. Add $+$ and $-$ alternately at corners.
3. Compute improvement index = sum of $+$ costs minus sum of $-$ costs.
4. If all indices $\ge 0$, optimal. If any negative, select most negative cell, adjust loop, and repeat.

Special Cases in Transportation

Degeneracy: Number of allocated cells $$\displaystyle < m+n-1 $$.
- Cause: Simultaneous exhaustion of a row and column during allocation.
- Resolution: Allocate a very small quantity ($$\displaystyle \epsilon > 0 $$) to an unallocated cell to make basic cells = $m+n-1$. Treat $\epsilon$ as zero for cost calculation.
Unbalanced Problem: $$\displaystyle \sum a_i \ne \sum b_j $$. Add dummy row (if supply < demand) or dummy column (if supply > demand) with zero cost.
Maximization Problem: Convert to minimization by subtracting all costs from a large constant (e.g., $$\displaystyle M = \max(c_{ij}) $$). Use $$\displaystyle c'_{ij} = M - c_{ij} $$.
Prohibited Routes: Assign a very high cost ($M$) to the prohibited cell. It will not be allocated in optimal solution.

[!TIP] Exam Focus: VAM is often asked for IBFS. MODI method is preferred for optimality test over Stepping Stone due to fewer calculations. Always check for degeneracy first.

4. ASSIGNMENT PROBLEM & TRAVELING SALESMAN PROBLEM (TSP)

Assignment Problem

Model: Special case of TP where $$\displaystyle m = n $$ (square matrix) and each origin must be assigned to exactly one destination, and vice versa. It is a 0-1 integer programming problem.
Objective: Minimize total cost (or maximize profit) of assignment.
Hungarian Method (for Minimization):
1. Row Reduction: Subtract minimum of each row from all elements in that row.
2. Column Reduction: Subtract minimum of each column from all elements in that column.
3. Cover All Zeros: Find minimum number of horizontal/vertical lines to cover all zeros.
  - If number of lines = $n$, an optimal assignment exists among zeros. Go to Step 5.
  - If lines $$\displaystyle < n $$, go to Step 4.
4. Adjust Matrix:
  - Find smallest uncovered element ($k$).
  - Subtract $k$ from all uncovered elements.
  - Add $k$ to all elements at intersection of covering lines.
  - Go back to Step 3.
5. Make Optimal Assignment: Select a zero, assign it, cross out its row and column. Repeat until all rows/columns are assigned.
Handling Variations:
- Maximization: Convert to minimization by subtracting all elements from the maximum element in the matrix.
- Unbalanced ($m \ne n$): Add dummy row/column with zero cost.
- Prohibited Assignments: Assign a very high cost ($M$) to prohibited cells.

Traveling Salesman Problem (TSP)

Definition: A salesman must visit $n$ cities exactly once and return to the starting city, minimizing total travel distance/cost.
Solution using Hungarian Method with Subtour Elimination:
1. Formulate as an assignment problem (cost matrix $$\displaystyle c_{ij} $$).
2. Solve using Hungarian method to get an initial assignment (may result in subtours—multiple disconnected cycles).
3. Subtour Elimination: Add constraints to prevent subtours. This transforms it into an integer programming problem. In practice, for small $n$, solve assignment, check for subtours, and iteratively add constraints (e.g., $$\displaystyle x_{ij} + x_{ji} \le 1 $$ for cities in different subtours) and re-solve.
Branch and Bound (Brief): Systematic enumeration of feasible solutions, using bounds to prune sub-problems that cannot yield a better solution than the current best.

[!TIP] Exam Focus: Hungarian method steps are crucial. For TSP, understand that the assignment solution gives a set of cycles; the optimal solution must be a single cycle covering all cities.

5. QUEUING THEORY

Basic Concepts & System Components

Queue: Customers waiting in line for service.
Service Facility: Server(s) providing service.
Key Parameters:
- Arrival Rate ($\lambda$): Average number of customers arriving per unit time.
- Service Rate ($\mu$): Average number of customers a server can serve per unit time.
- Server Utilization ($\rho$): $$\displaystyle \rho = \frac{\lambda}{c\mu} $$ for $c$ servers. Must be $$\displaystyle \rho < 1 $$ for stable system.
Performance Measures:
- $L$: Average number of customers in the system (waiting + being served).
- $$\displaystyle L_q $$: Average number of customers in the queue.
- $W$: Average time a customer spends in the system.
- $$\displaystyle W_q $$: Average time a customer spends waiting in queue.
- $$\displaystyle P_n $$: Probability of having exactly $n$ customers in the system.
- $$\displaystyle P_{wait} $$: Probability that an arriving customer has to wait (system not empty).
Service Disciplines:

| Discipline | Definition | Example | | :--- | :--- | :--- | | FIFO (FCFS) | First customer to arrive is first served. | Supermarket checkout. | | LIFO (LCFS) | Last customer to arrive is served first. | Stack of plates, emergency vehicles. | | Priority | Customers assigned priorities; highest priority served first. Can be preemptive (interrupt current service) or non-preemptive. | Hospital emergency room. | | Random | Service order chosen randomly. | Some call centers. |

Queuing Models (M/M/1, M/M/c)

Assumptions (Kendall's Notation: M/M/1):
- M (Markovian): Poisson arrivals (inter-arrival times exponential).
- M (Markovian): Exponential service times.
- 1: Single server.
- Additional: FCFS discipline, infinite system capacity, infinite population.
M/M/1 Model Formulas:

$$\rho = \frac{\lambda}{\mu} \quad (\text{must be } \rho < 1)$$

$$P_n = (1 - \rho) \rho^n \quad \text{(Steady-state probability)}$$

$$L = \frac{\rho}{1 - \rho}$$

$$L_q = \frac{\rho^2}{1 - \rho}$$

$$W = \frac{1}{\mu - \lambda}$$

$$W_q = \frac{\lambda}{\mu(\mu - \lambda)}$$

*   **Little's Law**: $$\displaystyle L = \lambda W $$ and $$\displaystyle L_q = \lambda W_q $$ (holds for most stable systems).

M/M/c Model (Multiple Servers):
- $c$: Number of identical servers.
- $$\displaystyle \rho = \frac{\lambda}{c\mu} $$ (individual server utilization).
- $$\displaystyle P_0 = \left[ \sum_{n=0}^{c-1} \frac{(\lambda/\mu)^n}{n!} + \frac{(\lambda/\mu)^c}{c! (1 - \rho)} \right]^{-1} $$
- $$\displaystyle L_q = \frac{(\lambda/\mu)^c \rho}{c! (1 - \rho)^2} P_0 $$ (Erlang's formula).
- $$\displaystyle L = L_q + \frac{\lambda}{\mu} $$
- $$\displaystyle W_q = \frac{L_q}{\lambda} $$, $$\displaystyle W = W_q + \frac{1}{\mu} $$
- Note: For exams, you may be given formulas or asked to derive state equations. Focus on applying given formulas.

Queuing Cost Analysis

Objective: Minimize total expected cost = Cost of waiting (per customer per unit time) $$\displaystyle \times L_q $$ + Cost of service (per server per unit time) $\times c$.
Trade-off: More servers ($c \uparrow$) reduce $$\displaystyle L_q $$ but increase service cost.

[!TIP] Exam Focus: Identify the queuing model from the problem description (arrival/service distributions, number of servers). Memorize M/M/1 formulas. For M/M/c, you may be provided formulas. Always check $$\displaystyle \rho < 1 $$ for stability.

6. INVENTORY MODELS

Inventory Costs

Ordering Cost ($S$): Fixed cost per order (independent of order size).
Carrying/Holding Cost ($H$): Cost to hold one unit in inventory for one period (includes storage, insurance, capital cost).
Shortage/Stock-out Cost ($P$): Cost per unit of unsatisfied demand (lost sales, backorder cost).
Setup Cost: Similar to ordering cost, for production setups.
Purchase Cost: $C \times D$ (often constant if price per unit is fixed).

Deterministic Models: Economic Order Quantity (EOQ)

Basic EOQ Model Assumptions:
- Demand rate $D$ is known, constant, and continuous.
- Replenishment is instantaneous (order arrives all at once).
- No shortages allowed.
- Ordering cost $S$ and holding cost $H$ are constant.
EOQ Formula:

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

Total Annual Cost (TC):

$$TC = \text{Purchase Cost} + \text{Ordering Cost} + \text{Holding Cost}$$

$$TC = CD + S\left(\frac{D}{Q}\right) + H\left(\frac{Q}{2}\right)$$

At $$\displaystyle Q = Q^* $$: $$\displaystyle TC^* = CD + \sqrt{2DSH} $$

Other Metrics:
- Number of orders per year: $$\displaystyle N = \frac{D}{Q^*} $$
- Time between orders (cycle time): $$\displaystyle T = \frac{1}{N} = \frac{Q^*}{D} $$
- Reorder Point (ROP): If lead time $L$ is constant, $$\displaystyle ROP = D \times L $$.
EOQ with Finite Production Rate (Production lot size model):
- Production rate $$\displaystyle P > D $$.
- $$\displaystyle Q^* = \sqrt{\frac{2DS}{H \left(1 - \frac{D}{P}\right)}} $$
- Maximum inventory level = $$\displaystyle Q^* \left(1 - \frac{D}{P}\right) $$.

Stochastic Inventory Models

Need: Demand and/or lead time are uncertain.
Safety Stock (Buffer Stock): Extra inventory held to prevent stock-outs during lead time uncertainty.
Service Level: Probability that demand during lead time will not exceed inventory on hand. $(1 - \text{Probability of Stock-out})$.
Reorder Point (ROP) with Safety Stock:

$$ROP = \text{Expected Demand during Lead Time} + \text{Safety Stock}$$

$$Safety Stock = z \times \sigma_{LT}$$

where $z$ = standard normal value for desired service level, $$\displaystyle \sigma_{LT} $$ = standard deviation of demand during lead time.

Newsboy/Vendor Model (Single Period):
- One-time ordering decision for perishable/seasonal item.
- Overage Cost ($$\displaystyle C_o $$): Cost of having one unit left unsold (purchase cost - salvage value).
- Underage Cost ($$\displaystyle C_u $$): Cost of one unit of shortage (lost profit = selling price - purchase cost).
- Optimal Order Quantity:

$$Q^* = F^{-1}\left(\frac{C_u}{C_u + C_o}\right)$$

    where $F$ is the cumulative distribution function of demand.

*   Order until marginal benefit of ordering one more unit (avoiding underage) equals marginal cost (risk of overage).

[!TIP] Exam Focus: EOQ derivation is less likely; focus on applying the formula and calculating TC, N, T. For stochastic models, understand how to calculate safety stock using z-score and standard deviation.

7. NETWORK ANALYSIS (PERT/CPM)

Project Management Concepts

Activity: Task requiring time/resources.
Event (Node): Point in time signifying start/end of activities.
Dummy Activity: Zero-duration activity used to show dependency/logic.
Predecessor/Successor: Activity before/after another in sequence.

Network Diagram Construction

Activity-on-Node (AON) / Precedence Diagramming Method (PDM): Standard in modern software. Activities are nodes; arrows show dependencies.
Rules:
- No activity can start until all its predecessors are complete (FS relationship by default).
- Use dummies only when necessary to show correct logic.
- Avoid crossing arrows if possible.

Critical Path Method (CPM)

Forward Pass (Calculate Earliest Times):
- $$\displaystyle EST_j $$ (Earliest Start Time of activity $j$) = max($$\displaystyle EFT_i $$) over all immediate predecessors $i$.
- $$\displaystyle EFT_j = EST_j + t_j $$ (duration).
- Start with $$\displaystyle EST = 0 $$ for first activity(s).
Backward Pass (Calculate Latest Times):
- $$\displaystyle LFT_j $$ (Latest Finish Time) = min($$\displaystyle LST_k $$) over all immediate successors $k$.
- $$\displaystyle LST_j = LFT_j - t_j $$.
- Start with $$\displaystyle LFT = EFT $$ of final activity(s) (project completion time).
Float/Slack:
- Total Float (TF): $$\displaystyle TF_j = LST_j - EST_j = LFT_j - EFT_j $$. Time an activity can be delayed without delaying project.
- Free Float (FF): $$\displaystyle FF_j = EST_k - EFT_j $$ (where $k$ is immediate successor). Time an activity can be delayed without delaying early start of any successor.
- Critical Activity: $$\displaystyle TF = 0 $$ (and usually $$\displaystyle FF = 0 $$).
Critical Path: Longest path through the network (sum of durations of critical activities). Determines minimum project completion time.

Program Evaluation and Review Technique (PERT)

Used for uncertain activity times (research, development projects).
Three-Time Estimates:
- $O$: Optimistic time (best case).
- $M$: Most likely time.
- $P$: Pessimistic time (worst case).
Expected Time ($$\displaystyle T_e $$):

$$\boxed{T_e = \frac{O + 4M + P}{6}}$$

Variance ($$\displaystyle \sigma^2 $$) for an activity:

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

Critical Path with Probabilistic Times:
1. Compute $$\displaystyle T_e $$ for each activity.
2. Perform forward/backward pass to find critical path based on $$\displaystyle T_e $$.
3. Project Completion Time ($$\displaystyle T_{CE} $$): Sum of $$\displaystyle T_e $$ on critical path.
4. Project Variance ($$\displaystyle \sigma_{CP}^2 $$): Sum of variances of activities on the critical path.
Probability of Project Completion by Time $T$:
- Assume project completion time follows Normal distribution with mean $$\displaystyle T_{CE} $$ and standard deviation $$\displaystyle \sigma_{CP} = \sqrt{\sigma_{CP}^2} $$.
- Compute Z-score: $$\displaystyle Z = \frac{T - T_{CE}}{\sigma_{CP}} $$
- Find probability from standard normal table: $$\displaystyle P(T_{project} \le T) = \Phi(Z) $$.

[!TIP] Exam Focus: Always calculate both EST/EFT and LST/LFT. The critical path is where EST = LST (or EFT = LFT). For PERT, remember the formulas for $$\displaystyle T_e $$ and $$\displaystyle \sigma^2 $$. The critical path in PERT is determined by expected times, but variance is summed only along that path.

8. GAME THEORY

Basic Terminology

Game: Competitive situation involving players.
Players: Decision-makers (e.g., two-person game).
Strategies: Possible courses of action available to a player.
Payoff: Gain/loss to a player for a specific combination of strategies.
Payoff Matrix: Tabular representation of payoffs. Rows = Player A's strategies, Columns = Player B's strategies.
Zero-Sum Game: One player's gain is exactly the other's loss. Total payoff = 0. (Focus for exams).
Non-Zero-Sum Game: Sum of payoffs is not zero.
Pure Strategy: Player chooses one specific strategy.
Mixed Strategy: Player chooses strategies with certain probabilities.
Value of the Game ($V$): Expected payoff to Player A when both play optimally.

Solving Two-Person Zero-Sum Games

Saddle Point (Pure Strategy Solution):
- Definition: An entry $$\displaystyle a_{ij} $$ that is minimum in its row and maximum in its column.
- Procedure:
  1. For each row, find row minimum (Player A's security level if they choose that row).
  2. Maximize these row minima → Maximin.
  3. For each column, find column maximum (Player B's loss if they choose that column).
  4. Minimize these column maxima → Minimax.
- If Maximin = Minimax, a saddle point exists at their intersection. The game has a value $$\displaystyle V = \text{Maximin} = \text{Minimax} $$.
- Optimal Strategies: Player A plays the row with maximin; Player B plays the column with minimax.
Dominance Property (Reduction of Payoff Matrix):
- Row Dominance: Row $i$ dominates row $k$ if $$\displaystyle a_{ij} \ge a_{kj} $$ for all $j$, and $$\displaystyle > $$ for at least one $j$. (For Player A maximizing, dominated row can be deleted).
- Column Dominance: Column $i$ dominates column $k$ if $$\displaystyle a_{ji} \le a_{jk} $$ for all $j$, and $$\displaystyle < $$ for at least one $j$. (For Player A maximizing, dominated column can be deleted).
- Application: Repeatedly apply dominance to reduce matrix size before solving.
Mixed Strategy (No Saddle Point):
- Concept: Players randomize over strategies with probabilities to make opponent indifferent.
- 2x2 Game Solution (Algebraic Method):
  
  Let Player A play row 1 with prob $p$, row 2 with $1-p$.
  
  Player B's expected payoff if they play Col 1: $$\displaystyle E_1 = a_{11}p + a_{21}(1-p) $$
  
  If they play Col 2: $$\displaystyle E_2 = a_{12}p + a_{22}(1-p) $$
  
  For Player A to be indifferent (and Player B to mix), set $$\displaystyle E_1 = E_2 = V $$.
  
  Solve for $p$ and $V$.
  
  Similarly, find $q$ (prob Player B plays Col 1) from Player A's indifference.
- m x 2 or 2 x n Game (Graphical Method):
  - Plot expected payoff lines for the opponent's pure strategies as a function of your mixing probability.
  - The upper envelope (for maximizing player) gives the maximum expected payoff for each $p$.
  - The minimax point (lowest point on upper envelope) gives optimal mixed strategy and game value.
- General m x n Game: Can be formulated as an LP. For exams, reduction via dominance is key.

Key Concepts

Fair Game: $$\displaystyle V = 0 $$ (no inherent advantage to either player).
Payoff Matrix Structure: Always state which player's payoff is represented (usually row player/Player A).

[!TIP] Exam Focus: First check for saddle point (Maximin = Minimax). If not, use dominance to reduce matrix. For 2x2 without saddle point, use algebraic method. Be careful with sign conventions (usually row player maximizes).

9. ADDITIONAL TOPICS & APPLICATIONS

Minimal Spanning Tree (MST)

Definition: A tree (connected, no cycles) spanning all nodes in a network with minimum total edge length/cost.
Application: Connecting all nodes (e.g., cable laying, pipeline design) with minimal cost.
Prim's Algorithm:
1. Start with an arbitrary node.
2. At each step, add the cheapest edge connecting a node in the tree to a node outside.
3. Repeat until all nodes are included.
- Result is an MST.

Formulation of Linear Programming Problems from Real-World Scenarios

General Steps:
1. Define decision variables clearly (e.g., $$\displaystyle x_i $$ = units of product $i$ to produce).
2. Write objective function (e.g., Max profit = $$\displaystyle \sum (\text{profit per unit}) \times x_i $$).
3. Identify all constraints (resource limits: labor hours, machine hours, raw material; demand limits; market constraints; non-negativity).
4. Ensure linearity and proportionality.
Example - Police Scheduling (from past paper):
- Variables: $$\displaystyle x_{ij} $$ = 1 if officer $i$ works on day $j$, 0 otherwise.
- Objective: Min $$\displaystyle \sum_{i,j} x_{ij} $$ (total officers scheduled) or Min days off.
- Constraints: $$\displaystyle \sum_i x_{ij} \ge \text{required}_j $$ for each day $j$.
- Constraints: Each officer works exactly 5 days, no consecutive days off (can be formulated with additional binary constraints).

Interpretation of Final Simplex Tableau

Optimal Solution: Values of basic variables in RHS column.
Shadow Prices: Coefficients in the $$\displaystyle c_j - z_j $$ row corresponding to slack/artificial variables (original RHS constraints). They indicate the marginal value of relaxing that constraint by one unit.
Reduced Costs: $$\displaystyle (c_j - z_j) $$ for non-basic variables. If positive (for Max), the objective coefficient must increase by that amount for the variable to enter the basis. If zero, alternative optimal solutions exist.

Network Analysis in EIA Context

Application of network diagrams (like PERT/CPM) to map impact pathways in Environmental Impact Assessment.
Shows sequence of activities (project actions) leading to environmental changes and ultimate impacts.
Helps identify critical pathways and cumulative effects.

[!TIP] Exam Focus: Practice formulating LPPs from word problems (production mix, diet, blending, scheduling). Understand how to read shadow prices and reduced costs from the final simplex tableau. For MST, know Prim's algorithm steps.

Account

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