Unit 1: Introduction & linear programming

Operations research is the application of scientific methods, techniques and tools to problems involving the operations of systems, to provide optimal solutions (Churchman, Ackoff and Arnoff). Evolution: began in Britain during World War II for radar deployment and convoy routing; after the war it spread to industry and government.

Techniques: linear programming, transportation and assignment, game theory, sequencing, queuing, inventory models, PERT/CPM, simulation and decision theory. Applications: production planning, product mix, distribution, scheduling, finance and marketing.

Linear programming (LP) optimises (maximises or minimises) a linear objective function subject to linear constraints. Characteristics: objective function, decision variables, constraints, non-negativity, linearity, divisibility and certainty.

The simplex method (George Dantzig) solves LPPs with any number of variables by moving from one corner point (basic feasible solution) to a better one.

• Add slack variables for ≤ constraints, surplus and artificial variables for ≥ and = constraints (Big-M method).
• Choose the key column (most negative Cj − Zj for maximisation) and key row (minimum ratio), pivot, and repeat until all Cj − Zj ≤ 0.

Duality: every LP (primal) has a dual. If the primal maximises with m constraints and n variables, the dual minimises with n constraints and m variables; their optimal values are equal. Dual variables are shadow prices — the value of one more unit of each resource.