How unit 1 is examined
This unit covers the origin, phases and methodology of OR, then LP formulation with the graphical method, the simplex method, and duality with the dual simplex method; no question from the supplied papers is tagged here, so every topic is taught as a likely fresh question.
Origin, Phases, Methodology, Scope and Limitations of OR
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>
Definition. <mark>Operations Research is the application of scientific and mathematical methods, through a team approach, to build models that help management take optimal decisions on the operations of an organisation.</mark>
Key points.
- OR began in Britain in 1937-39, when scientists led by A. P. Rowe studied radar and the deployment of scarce military resources in World War II.
- After the war it moved into industry, and G. B. Dantzig's simplex method of 1947 gave it a general tool for optimisation.
- OR is a team approach, model-based, and aims at the optimum for the whole system rather than for one department.
- The phases are problem definition, model construction, solution of the model, validation, implementation and control.
- The scope covers production planning, inventory, transportation, assignment, scheduling, queuing, replacement, finance and marketing.
- The limitations are that the models simplify reality, data is costly to collect, the mathematics is complex, and managers may resist the results.
- OR helps decision making by giving a quantitative basis: it lists alternatives, states the objective and constraints, and picks the best alternative instead of relying on judgement.
Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u1-01" viewBox="0 0 492.8 80" width="492.8" height="80" role="img" aria-label="Phases of OR. D = define problem, M = construct model, S = solve model, V = validate model, I = implement and control; a failed validation returns to the model"><style>#dsfig-u1-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u1-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u1-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u1-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u1-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u1-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u1-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u1-01 .t{fill:#16181D;font-weight:500}#dsfig-u1-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u1-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u1-01 .dot{fill:#16181D}#dsfig-u1-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u1-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u1-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u1-01 .ah{fill:#454C5A}#dsfig-u1-01 .ah.hi{fill:#2340B8}#dsfig-u1-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u1-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u1-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u1-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u1-01 .e{stroke:#B1B7C3}html.dark #dsfig-u1-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u1-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u1-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u1-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u1-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u1-01 .t{fill:#E6E8ED}html.dark #dsfig-u1-01 .t.inv{fill:#0F1115}html.dark #dsfig-u1-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u1-01 .dot{fill:#E6E8ED}html.dark #dsfig-u1-01 .ann{fill:#8FA3FF}html.dark #dsfig-u1-01 .lbl{fill:#858D9C}html.dark #dsfig-u1-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u1-01 .ah{fill:#B1B7C3}html.dark #dsfig-u1-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u1-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u1-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u1-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah1" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh1" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M59,40 L122.2,40" marker-end="url(#ah1)"/><path class="e" d="M162.2,40 L225.4,40" marker-end="url(#ah1)"/><path class="e" d="M265.4,40 L328.6,40" marker-end="url(#ah1)"/><path class="e" d="M368.6,40 L431.8,40" marker-end="url(#ah1)"/><path class="e" d="M330.6,40 L164.2,40" marker-end="url(#ah1)"/><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">D</text><circle class="n" cx="143.2" cy="40" r="18"/><text class="t" x="143.2" y="40" dy=".35em" text-anchor="middle">M</text><circle class="n" cx="246.4" cy="40" r="18"/><text class="t" x="246.4" y="40" dy=".35em" text-anchor="middle">S</text><circle class="n" cx="349.6" cy="40" r="18"/><text class="t" x="349.6" y="40" dy=".35em" text-anchor="middle">V</text><circle class="n" cx="452.8" cy="40" r="18"/><text class="t" x="452.8" y="40" dy=".35em" text-anchor="middle">I</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Phases of OR. D = define problem, M = construct model, S = solve model, V = validate model, I = implement and control; a failed validation returns to the model</figcaption></figure>
Answer frame. Open with the definition; draw the phase diagram; then develop the phases in order, with one sentence each on what is done; close with scope and one limitation.
Linear Programming: Introduction, Formulation, Graphical Solution
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>
Definition. <mark>Linear programming is a technique to optimise (maximise or minimise) a linear objective function subject to linear constraints in the form of equalities or inequalities, with non-negative variables.</mark>
Key points.
- The four assumptions are proportionality, additivity, certainty and divisibility of the variables, along with a single objective.
- Formulation has four steps: identify the decision variables, write the objective function, write the constraints from the resources, and add non-negativity $x_j \ge 0$.
- The general form is maximise $Z = \sum c_j x_j$ subject to $\sum a_{ij} x_j \le b_i$ and $x_j \ge 0$.
- The graphical method suits two variables: plot each constraint line, shade the common feasible region, then evaluate $Z$ at every corner point.
- The fundamental theorem says the optimum, if it exists, lies at a corner (extreme) point of the feasible region.
- Special cases: alternative optima when the objective is parallel to a constraint, an unbounded solution when the region is open in the improving direction, and infeasibility when no region is common.
Example. A firm makes products A and B with profits Rs 40 and Rs 30 per unit. Material limits $x_1 + x_2 \le 12$ and labour limits $2x_1 + x_2 \le 16$.
Maximise $Z = 40x_1 + 30x_2$ subject to $x_1 + x_2 \le 12$, $2x_1 + x_2 \le 16$, $x_1, x_2 \ge 0$.
| Corner | $(x_1, x_2)$ | $Z = 40x_1 + 30x_2$ |
|---|---|---|
| O | (0, 0) | 0 |
| P | (8, 0) | 320 |
| Q | (4, 8) | 400 |
| R | (0, 12) | 360 |
Q is the intersection of the two lines: subtracting gives $x_1 = 4$, then $x_2 = 8$. Optimum: $x_1 = 4$, $x_2 = 8$, $Z_{max} = 400$.
Answer frame. Open with the definition of LPP; define the variables and write the objective and constraints; draw the axes with the constraint lines and shade the feasible region; tabulate $Z$ at each corner; close with the boxed optimum.
Standard Form and the Simplex Method
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>
Definition. <mark>The simplex method is an iterative algebraic procedure that moves from one basic feasible solution to an adjacent one with a better objective value until no further improvement is possible.</mark>
Key points.
- In standard form all constraints are equations, all right-hand sides are non-negative and all variables are non-negative.
- A slack variable is added to a $\le$ constraint, a surplus variable is subtracted from a $\ge$ constraint, and an artificial variable is added to a $\ge$ or $=$ constraint to get a starting basis.
- Slack and surplus variables have zero cost in the objective; artificial variables get $-M$ in a maximisation problem (Big-M method).
- A minimisation problem is converted by maximising $Z' = -Z$, since $\min Z = -\max(-Z)$.
- The entering variable is the one with the most negative $z_j - c_j$ (the key column).
- The leaving variable has the minimum positive ratio $b_i / a_{ik}$ (the key row); the pivot element is where they meet.
- The solution is optimal when every $z_j - c_j \ge 0$ (maximisation); an artificial variable left in the basis at a positive value means infeasibility.
Steps.
Step 1: Convert to standard form with slack, surplus and artificial variables.
Step 2: Write the initial table with the slack variables as the basis.
Step 3: Find the entering column, the most negative z_j - c_j.
Step 4: Find the leaving row by the minimum positive ratio b_i / a_ik.
Step 5: Divide the pivot row by the pivot, and clear the pivot column in other rows.
Step 6: Repeat from Step 3 until all z_j - c_j are non-negative.
Example. The same problem: maximise $40x_1 + 30x_2$ with $x_1 + x_2 + s_1 = 12$ and $2x_1 + x_2 + s_2 = 16$.
Initial table (basis $s_1, s_2$). Most negative is $-40$, so $x_1$ enters; ratios are $12/1 = 12$ and $16/2 = 8$, so $s_2$ leaves.
| Basis | $x_1$ | $x_2$ | $s_1$ | $s_2$ | RHS |
|---|---|---|---|---|---|
| $s_1$ | 1 | 1 | 1 | 0 | 12 |
| $s_2$ | 2 | 1 | 0 | 1 | 16 |
| $z_j - c_j$ | -40 | -30 | 0 | 0 | 0 |
After iteration 1 (basis $s_1, x_1$). Now $-10$ is negative, so $x_2$ enters; ratios are $4/(1/2) = 8$ and $8/(1/2) = 16$, so $s_1$ leaves.
| Basis | $x_1$ | $x_2$ | $s_1$ | $s_2$ | RHS |
|---|---|---|---|---|---|
| $s_1$ | 0 | 1/2 | 1 | -1/2 | 4 |
| $x_1$ | 1 | 1/2 | 0 | 1/2 | 8 |
| $z_j - c_j$ | 0 | -10 | 0 | 20 | 320 |
After iteration 2 (basis $x_2, x_1$). All $z_j - c_j \ge 0$, so it is optimal.
| Basis | $x_1$ | $x_2$ | $s_1$ | $s_2$ | RHS |
|---|---|---|---|---|---|
| $x_2$ | 0 | 1 | 2 | -1 | 8 |
| $x_1$ | 1 | 0 | -1 | 1 | 4 |
| $z_j - c_j$ | 0 | 0 | 20 | 10 | 400 |
Optimum: $x_1 = 4$, $x_2 = 8$, $Z_{max} = 400$, matching the graphical corner Q.
Answer frame. Open with the definition; convert to standard form and write the initial table; state the entering and leaving rules at each table; show two or three tables; close with the optimal values.
Pitfall: Forgetting that a minimisation problem is maximised as $-Z$, or forgetting to change the sign of the final $Z$.
Duality and the Dual Simplex Method
<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>
Definition. <mark>Every linear programme (the primal) has an associated linear programme (the dual) built from the same data, and their optimal objective values are equal.</mark>
Key points.
- For a maximisation primal with $\le$ constraints, the dual is a minimisation with $\ge$ constraints; the primal right-hand sides become dual costs, and the primal costs become dual right-hand sides.
- Each primal constraint gives one dual variable, and each primal variable gives one dual constraint; the coefficient matrix is transposed.
- The dual of the dual is the primal, and an equality constraint gives an unrestricted dual variable.
- By strong duality, if one problem has an optimum, so does the other, with $Z_{max} = W_{min}$; if one is unbounded the other is infeasible.
- Economic interpretation: the dual variable $y_i$ is the shadow price, the worth of one extra unit of resource $i$ to the objective.
- The dual simplex method is used when the table is optimal ($z_j - c_j \ge 0$) but infeasible (some RHS is negative), as after adding a constraint.
- The leaving row is the most negative RHS; the entering column has the minimum $|(z_j - c_j)/a_{rj}|$ among negative entries $a_{rj}$ in that row; stop when all RHS are non-negative.
Example (dual of the graphical problem). Primal: maximise $40x_1 + 30x_2$, with $x_1 + x_2 \le 12$ and $2x_1 + x_2 \le 16$.
Dual: minimise $W = 12y_1 + 16y_2$ subject to $y_1 + 2y_2 \ge 40$, $y_1 + y_2 \ge 30$, $y_i \ge 0$. From the last simplex table above, $y_1 = 20$ and $y_2 = 10$ (the $z_j - c_j$ under $s_1$ and $s_2$), so $W = 12(20) + 16(10) = 400 = Z_{max}$.
Example (dual simplex). Minimise $Z = 2x_1 + x_2$ subject to $3x_1 + x_2 \ge 3$, $4x_1 + 3x_2 \ge 6$, $x_1 + 2x_2 \le 3$.
Multiply the $\ge$ rows by $-1$ and add slacks $s_1, s_2, s_3$: the initial RHS is $-3, -6, 3$. The row $s_2$ (RHS $-6$) leaves. The ratios are $2/4 = 0.5$ for $x_1$ and $1/3$ for $x_2$, so $x_2$ enters. Then $s_1$ (RHS $-1$) leaves, and $x_1$ enters. All RHS are then non-negative.
Optimum: $x_1 = 3/5$, $x_2 = 6/5$, $Z_{min} = 12/5$. Check: $2(0.6) + 1.2 = 2.4$.
Answer frame. For duality: open with the definition; write the primal and its dual side by side using the transposition rules; state the strong duality theorem; close with the shadow-price meaning. For the dual simplex: state when it applies; show the leaving row and entering column rules; work the tables; close with the optimum.
Last-minute revision
- OR is the scientific, model-based approach to optimal management decisions; it began in Britain in World War II.
- Phases: define, model, solve, validate, implement and control.
- LP has a linear objective, linear constraints and $x_j \ge 0$; assumptions are proportionality, additivity, certainty and divisibility.
- The graphical optimum lies at a corner point: for the worked problem, (4, 8) with $Z = 400$.
- Slack is added for $\le$, surplus is subtracted for $\ge$, and an artificial variable carries $-M$.
- Simplex is optimal when all $z_j - c_j \ge 0$ for maximisation.
- The entering column is the most negative $z_j - c_j$; the leaving row has the minimum positive ratio.
- $\min Z = -\max(-Z)$.
- Strong duality: primal optimum equals dual optimum, $Z_{max} = W_{min}$.
- Dual variables are shadow prices; the dual of the dual is the primal.
- The dual simplex keeps optimality and restores feasibility, choosing the row first and then the column.
Memory hooks
- Phases: "Define, Model, Solve, Validate, Implement".
- Simplex: "Enter the most negative, leave by minimum ratio".
- Slack, Surplus, Artificial: "S for less-than, S minus for greater-than, A for a start".
- Dual simplex: "Row first (most negative RHS), then column (minimum ratio)".
- Duality: primal rows become dual columns, and max becomes min.
Coverage checklist
- Origin & Development of OR, Different Phases of OR study, Methodology of OR, Scope and Limitations of OR, OR in decision making: covered, no past questions.
- Linear Programming: Introduction – Mathematical formulation of a problem – Graphical solutions: covered, no past questions.
- standard forms the simplex method for maximization and minimization problems: covered, no past questions.
- Interpretation of Duality, Dual simplex Method: covered, no past questions.