Operations Research
From transcript: 20ME710 Operations Research (D)
Cheat sheet
Formulas
LP standard: max c·x s.t. Ax ≤ b, x≥0 ; simplex / dual ideas
Shadow price = dual variable — worth of one more resource unit
Transportation: supply–demand balanced; NW corner / Vogel / MODI
Assignment: Hungarian method — special transportation
CPM: ES, EF, LS, LF ; float = LS−ES ; critical path float=0
PERT: te=(a+4m+b)/6 ; σ²=((b−a)/6)² ; project variance sum on CP
EOQ = √(2 D S / H) ; reorder point = d L (+ safety stock)
Queuing M/M/1: ρ=λ/μ ; L=ρ/(1−ρ) ; W=1/(μ−λ)
Game theory 2×2 saddle / mixed strategies
Dynamic programming: Bellman optimality — stages & states
LP standard: max cᵀx s.t. Ax ≤ b, x ≥ 0
Simplex: pivot to improve objective until optimal
Assignment: Hungarian method
EOQ: Q* = √(2DS/H)
PERT: te = (a + 4m + b)/6
Definitions
- Feasible region
- Points satisfying all constraints
- Optimal basic feasible
- Vertex solution in LP (simplex)
- Degeneracy
- Zero basic variable — cycling risk
- Critical path
- Longest path — determines project duration
- Slack / float
- Delay allowed without delaying project
- EOQ
- Order quantity minimizing order+holding cost
- Safety stock
- Buffer against demand/lead-time uncertainty
- Utilization ρ
- Arrival rate / service capacity
- Shadow price
- Objective change per unit RHS relaxation
Topic-wise short notes
LP, transportation, networks
- Graphical LP 2-var; sensitivity on RHS/obj coefficients.
- Network models: shortest path, max flow, MST.
- Transshipment & unbalanced transportation with dummy.
Inventory & project OR
- ABC analysis for SKU attention.
- Crashing: cost slope to shorten critical activities.
- Resource leveling vs resource-constrained scheduling.
Decision tools
- AHP / weighted scoring for multi-criteria (informal OR).
- Simulation when queues/networks too complex for closed form.
- Sensitivity: what if demand ±20% — always ask.
Exam traps & quick notes
- Frame decisions as decision vars + objective + constraints.
- Line balancing & scheduling = OR mindset on the shop floor.
- Gantt + CPM for AeroJC / production planning stories.
- LP assumes linearity, divisibility, certainty — state when violated.
- Integer requirements need ILP — rounding LP can be wrong.
- CPM deterministic; PERT adds uncertainty on activity times.
- Inventory: include shortage costs if relevant; quantity discounts.
- Queues: stability needs ρ<1.
Comprehensive notes
LP, transportation, networks
Graphical 2-var LP; Big-M; transport/transshipment; shortest path / max flow intuition.
External: NPTEL OR ↗ PuLP Python LP ↗
Inventory & project OR
EOQ variants, queuing M/M/1 basics, CPM/PERT crashing.
External: OR-Tools ↗
Linear programming
Decision vars, objective, constraints; graphical 2-var; simplex idea; sensitivity/shadow prices.
External: NPTEL ↗ Engineering Toolbox ↗
Networks, inventory, projects
Transport/assignment; EOQ; CPM/PERT (te=(a+4m+b)/6); crashing. Shop scheduling intuition.
External: NPTEL ↗ Engineering Toolbox ↗
Interview Q&A for this subject
Q: What is a shadow price?
A: Improvement in objective per unit increase of a binding constraint RHS — within validity range.
External: ASQ / quality ↗ MIT OCW ↗