Unit 1: Introduction & deterministic models

Operations research (OR) is the application of scientific methods, techniques and tools to problems involving the operations of a system so as to provide those in control with optimum solutions (Churchman, Ackoff and Arnoff). It originated in military operations during World War II.

• Scope: production planning, inventory, transportation and logistics, finance (portfolio), marketing (media selection), HR (assignment), project scheduling.
• Objectives: optimise (maximise profit or minimise cost) under constraints; improve decision quality.
• Limitations: models simplify reality; data may be unavailable; costly; managers may not understand models; non-quantifiable factors ignored.

Linear programming (LP) optimises a linear objective function subject to linear constraints and non-negativity.

• Components: decision variables, objective function, constraints, non-negativity.
• Assumptions: linearity (proportionality, additivity), divisibility, certainty, finiteness.

• Corner points: (0, 0) Z = 0; (40, 0) Z = 1,600; (0, 40) Z = 2,400; intersection of 2x + 3y = 120 and 2x + y = 80 → y = 20, x = 30 → Z = 1,200 + 1,200 = 2,400. Two corners give the same Z — multiple optimal solutions (objective is parallel to the carpentry constraint).
• Special cases: multiple optima, unbounded solution, infeasible problem, redundant constraint.

• Convert inequalities to equations: add slack (≤), subtract surplus and add artificial variables (≥ or =).

• Big-M method: artificial variables are given a very large penalty −M in a maximisation objective (+M for minimisation) so they leave the basis; if an artificial variable remains positive in the final table, the problem is infeasible.
• Two-phase method: alternative to Big-M — first minimise the sum of artificial variables.
• Duality: every LP (primal) has a dual; optimal values are equal; dual values give shadow prices of resources.

Minimise the cost of transporting goods from m sources (supply) to n destinations (demand).

• Balanced problem: total supply = total demand; else add a dummy row/column with zero cost.
• Methods for initial basic feasible solution (IBFS): North-West Corner Rule, Least Cost Method, Vogel's Approximation Method (VAM) — VAM usually gives the best start.
• A non-degenerate solution has m + n − 1 allocations; fewer = degeneracy (add ε).
• Optimality test: MODI (u–v) method — compute ui + vj = cij for occupied cells; for unoccupied cells, Δij = cij − (ui + vj); if all Δij ≥ 0 the solution is optimal; otherwise form a closed loop and reallocate.

Assign n jobs to n persons (one each) to minimise total cost or time.

• Variations: maximisation (convert by subtracting from the largest), unbalanced (add dummy), restricted assignments (infinite cost), multiple optimal solutions.

Travelling salesman problem

A salesman visits each city once and returns home with minimum total distance — solved as an assignment problem with no self-assignment (diagonal = ∞) and the additional constraint that the solution must form a single complete tour (no sub-tours); if the assignment gives sub-tours, the next best zero is tried.