Operational Research Cheatsheet

Cheatsheet Content

1. Introduction to Operational Research (OR) Definition: Application of advanced analytical methods to help make better decisions. Phases of an OR Study: Problem Definition Model Construction Solution Derivation Model Validation Implementation of Results Key Components: Objective Function, Decision Variables, Constraints. 2. Linear Programming (LP) Objective: Maximize or minimize a linear function subject to linear constraints. Standard Form: Maximize $c^T x$ Subject to $Ax \le b$ And $x \ge 0$ Components: Decision Variables: $x_j$ (quantities to be determined) Objective Function: $\sum c_j x_j$ (function to maximize/minimize) Constraints: $\sum a_{ij} x_j (\le, =, \ge) b_i$ (limitations/requirements) Non-negativity: $x_j \ge 0$ 2.1 Graphical Method (for 2 variables) Plot constraints as equalities to define lines. Determine feasible region (area satisfying all constraints). Plot objective function as a series of parallel lines ($Z = k$). Find the corner point in the feasible region that yields the optimal $Z$. 2.2 Simplex Method Iterative algorithm for solving LPs. Steps: Convert to Standard Form (add slack/surplus variables). Form initial simplex tableau. Identify entering variable (most negative in Z-row for maximization). Identify leaving variable (minimum ratio test). Perform pivot operations to update tableau. Repeat until all Z-row coefficients are non-negative (maximization). Slack Variable: $s_i \ge 0$, converts $\le$ to $=$. E.g., $x_1+x_2 \le 5 \Rightarrow x_1+x_2+s_1=5$. Surplus Variable: $s_i \ge 0$, converts $\ge$ to $=$. E.g., $x_1+x_2 \ge 5 \Rightarrow x_1+x_2-s_1=5$. Artificial Variable: $A_i \ge 0$, used for $\ge$ and $=$ constraints in initial basic feasible solution. Penalized in objective function (M for maximization, -M for minimization). 3. Duality in Linear Programming Every LP (Primal) has a corresponding Dual LP. Primal-Dual Relationship: Max Primal $\Leftrightarrow$ Min Dual Number of Primal variables = Number of Dual constraints Number of Primal constraints = Number of Dual variables Primal objective coefficients $\Leftrightarrow$ Dual RHS Primal RHS $\Leftrightarrow$ Dual objective coefficients Constraint types flip: $\le \Leftrightarrow \ge$, $=$ (unrestricted dual var), $\ge$ (non-positive dual var) Strong Duality Theorem: If primal has an optimal solution, then dual also has an optimal solution, and their optimal objective values are equal. 4. Transportation Problem Special type of LP for minimizing cost of transporting goods from sources to destinations. Balanced Problem: Total supply = Total demand. Methods for Initial Basic Feasible Solution: North-West Corner Rule: Simple, but often not optimal. Least Cost Method: Better initial solution, allocates to lowest cost cells first. Vogel's Approximation Method (VAM): Usually best initial solution, calculates penalties. Optimality Test: Stepping Stone Method / MODI Method. 5. Assignment Problem Special case of transportation problem where sources and destinations are equal, and each source must be assigned to exactly one destination. Hungarian Algorithm: Subtract smallest element from each row. Subtract smallest element from each column. Cover all zeros with minimum number of lines. If lines = matrix size, optimal assignment found. Else, find smallest uncovered element, subtract from all uncovered, add to elements at line intersections. Repeat from step 3. 6. Network Models 6.1 Shortest Path Problem Find path with minimum total length between two nodes. Dijkstra's Algorithm: For non-negative edge weights. Bellman-Ford Algorithm: For negative edge weights (can detect negative cycles). 6.2 Maximum Flow Problem Find maximum amount of flow that can be sent from a source to a sink through a network. Ford-Fulkerson Algorithm: Uses augmenting paths. Max-Flow Min-Cut Theorem: Max flow = Min capacity of a cut. 6.3 Minimum Spanning Tree (MST) Problem Find a subset of edges that connects all vertices, without cycles, and with minimum total edge weight. Prim's Algorithm: Grows a tree from an arbitrary starting node. Kruskal's Algorithm: Adds edges in increasing order of weight, avoiding cycles. 7. Project Management (CPM/PERT) CPM (Critical Path Method): Deterministic activity durations. PERT (Program Evaluation and Review Technique): Probabilistic activity durations. Key Concepts: Activity: Task requiring time and resources. Event/Node: Start/completion of activities. Predecessor: Activity that must be completed before another starts. Critical Path: Longest path through the network; determines project duration. Activities on this path have zero slack. Slack/Float: Amount of time an activity can be delayed without delaying the project. 7.1 Time Calculations Earliest Start (ES): Max of EF of all immediate predecessors. Earliest Finish (EF): ES + Activity Duration. Latest Finish (LF): Min of LS of all immediate successors. Latest Start (LS): LF - Activity Duration. Total Float (TF): LS - ES or LF - EF. Free Float (FF): Amount an activity can be delayed without affecting ES of any successor. 7.2 PERT Specifics Expected Time ($T_e$): $\frac{T_o + 4T_m + T_p}{6}$ Variance ($\sigma^2$): $\left(\frac{T_p - T_o}{6}\right)^2$ $T_o$: Optimistic time, $T_m$: Most likely time, $T_p$: Pessimistic time. Project variance is sum of variances of critical path activities. Use Normal Distribution for project completion probability. $Z = \frac{\text{Desired Time} - \text{Expected Project Time}}{\sqrt{\text{Project Variance}}}$ 8. Inventory Management Objective: Determine optimal ordering policies to minimize total inventory costs. Costs: Ordering cost, Holding cost, Shortage cost. 8.1 Economic Order Quantity (EOQ) Model Assumptions: Constant demand, instant replenishment, no shortages. Optimal Order Quantity ($Q^*$): $\sqrt{\frac{2DO}{H}}$ Total Annual Cost (TC): $\frac{D}{Q}O + \frac{Q}{2}H$ $D$: Annual demand, $O$: Ordering cost per order, $H$: Holding cost per unit per year. 8.2 EOQ with Quantity Discounts Calculate $Q^*$ for each discount price. If $Q^*$ is feasible for its price range, calculate TC. If $Q^*$ is not feasible, use the lowest quantity in that price range. Compare TCs for all feasible $Q^*$ and adjusted quantities to find overall minimum. 9. Queueing Theory Analysis of waiting lines (queues). Notation (Kendall's): (Arrival Process / Service Process / Number of Servers) Commonly M/M/1 (Poisson arrivals, Exponential service, 1 server). Key Metrics (for M/M/1): Arrival Rate: $\lambda$ Service Rate: $\mu$ System Utilization ($\rho$): $\frac{\lambda}{\mu}$ Probability of 0 customers ($P_0$): $1 - \rho$ Average number in system ($L_s$): $\frac{\lambda}{\mu - \lambda}$ Average number in queue ($L_q$): $\frac{\lambda^2}{\mu(\mu - \lambda)}$ Average time in system ($W_s$): $\frac{1}{\mu - \lambda}$ Average time in queue ($W_q$): $\frac{\lambda}{\mu(\mu - \lambda)}$ 10. Decision Analysis Making decisions under uncertainty. Decision Tree: Visual representation of decision points, chance events, and outcomes. Decision Criteria: Maximax: Optimistic; choose alternative with highest possible payoff. Maximin: Pessimistic; choose alternative with highest minimum payoff. Minimax Regret: Minimize the maximum regret (opportunity loss). Expected Monetary Value (EMV): Choose alternative with highest weighted average payoff (if probabilities are known). Expected Value of Perfect Information (EVPI): EVwPI - EMV_best. (EVwPI = Expected value with perfect information)