Operations Research
Comprehensive summary — IEM Year 2, University of Groningen
Based on: H&L textbook chapters 3–7, 9–10, 12 · Lecture notes (lec 1–8) · 2021 Resit · 2020 Extra
exercises
Contents
1. LP Formulation & Graphical Method
2. Simplex Method — Tabular Form
3. Sensitivity Analysis
4. Integer & Binary Programming
5. Network Optimisation
6. Transportation & Assignment Problems
7. Queueing Theory
8. Inventory Theory
9. Exam Tactics & Formula Reference
1
, 1. LP Formulation & Graphical Method
1.1 The four components
• Decision variables x₁, x₂, …, xₙ — quantities you control
• Objective function Z = c₁x₁ + … + cₙxₙ (maximise or minimise)
• Functional constraints — resource-usage inequalities / equalities
• Non-negativity xⱼ ≥ 0 (always write these explicitly)
Standard form (max): max Z = c₁x₁ + … + cₙxₙ
s.t. aᵢ₁x₁ + … + aᵢₙxₙ ≤ bᵢ for i = 1…m
xⱼ ≥ 0 for j = 1…n
1.2 Key solution concepts
Term Definition
Feasible solution Satisfies all constraints
Infeasible solution Violates at least one constraint
Feasible region Set of all feasible solutions — convex polygon for LP
Optimal solution Best feasible value of Z
CPF solution Corner-point feasible solution — vertex of the feasible region
1.3 Graphical method (2 variables only)
• Plot each constraint boundary; shade the feasible side
• Evaluate Z at every corner point (CPF solution)
• The best value is optimal — at least one CPF achieves it
• Multiple optima: any convex combination of the two optimal corners is also optimal
Common formulation mistakes
• Forgetting xⱼ ≥ 0 — write them every time
• Pushing the objective line the wrong way: for max, push in direction of increasing Z
Operations Research — University of Groningen IEM 2
, 2. Simplex Method — Tabular Form
2.1 Augmented form & slack variables
Convert every ≤ constraint to an equality by adding a slack variable sᵢ ≥ 0:
aᵢ₁x₁ + … + aᵢₙxₙ + sᵢ = bᵢ
At iteration 0, the slack variables form the initial basis and equal the RHS values.
Concept Definition
Basic variable (BV) In the current basis; value given by its equation RHS
Non-basic variable (NBV) Set to zero; there are n−m of them at any BFS
Basic feasible solution All BVs ≥ 0 — corresponds to a CPF solution
Degree of freedom n−m; setting n−m variables to 0 gives a basic solution
2.2 Tableau setup — prototype example
max Z = 3x₁ + 5x₂ s.t. x₁ ≤ 4, 2x₂ ≤ 12, 3x₁ + 2x₂ ≤ 18, x₁,x₂ ≥ 0
Augmented form: add s₁, s₂, s₃. Initial basis: {s₁, s₂, s₃}.
BV Z x₁ x₂ s₁ s₂ s₃ RHS
Z 1 −3 −5 0 0 0 0
s₁ 0 1 0 1 0 0 4
s₂ 0 0 2 0 1 0 12
s₃ 0 3 2 0 0 1 18
2.3 Four iteration steps
• Step 1 — Optimality test: if all Z-row coefficients ≥ 0, current BFS is optimal → stop
• Step 2 — Enter: column with the most negative Z-row coefficient (pivot column)
• Step 3 — Leave (min ratio test): divide RHS by each positive pivot-column entry; smallest ratio →
pivot row (that BV leaves)
• Step 4 — Pivot: Gauss-Jordan row ops so pivot element = 1 and all other pivot-column entries = 0
Ratio test — what to ignore
• Only use rows where the pivot-column entry is strictly > 0
• If ALL pivot-column entries ≤ 0: Z is unbounded — no finite optimum
• Tie in ratio test → degenerate solution; pick either row
2.4 Handling = and ≥ constraints
Constraint Transformation Initial BV
≤ Add slack sᵢ ≥ 0 sᵢ
= Add artificial Rᵢ ≥ 0 Rᵢ
≥ Subtract surplus sᵢ ≥ 0; add artificial Rᵢ ≥ 0 Rᵢ
Negative RHS Multiply both sides by −1 (reverses inequality) —
Operations Research — University of Groningen IEM 3
Comprehensive summary — IEM Year 2, University of Groningen
Based on: H&L textbook chapters 3–7, 9–10, 12 · Lecture notes (lec 1–8) · 2021 Resit · 2020 Extra
exercises
Contents
1. LP Formulation & Graphical Method
2. Simplex Method — Tabular Form
3. Sensitivity Analysis
4. Integer & Binary Programming
5. Network Optimisation
6. Transportation & Assignment Problems
7. Queueing Theory
8. Inventory Theory
9. Exam Tactics & Formula Reference
1
, 1. LP Formulation & Graphical Method
1.1 The four components
• Decision variables x₁, x₂, …, xₙ — quantities you control
• Objective function Z = c₁x₁ + … + cₙxₙ (maximise or minimise)
• Functional constraints — resource-usage inequalities / equalities
• Non-negativity xⱼ ≥ 0 (always write these explicitly)
Standard form (max): max Z = c₁x₁ + … + cₙxₙ
s.t. aᵢ₁x₁ + … + aᵢₙxₙ ≤ bᵢ for i = 1…m
xⱼ ≥ 0 for j = 1…n
1.2 Key solution concepts
Term Definition
Feasible solution Satisfies all constraints
Infeasible solution Violates at least one constraint
Feasible region Set of all feasible solutions — convex polygon for LP
Optimal solution Best feasible value of Z
CPF solution Corner-point feasible solution — vertex of the feasible region
1.3 Graphical method (2 variables only)
• Plot each constraint boundary; shade the feasible side
• Evaluate Z at every corner point (CPF solution)
• The best value is optimal — at least one CPF achieves it
• Multiple optima: any convex combination of the two optimal corners is also optimal
Common formulation mistakes
• Forgetting xⱼ ≥ 0 — write them every time
• Pushing the objective line the wrong way: for max, push in direction of increasing Z
Operations Research — University of Groningen IEM 2
, 2. Simplex Method — Tabular Form
2.1 Augmented form & slack variables
Convert every ≤ constraint to an equality by adding a slack variable sᵢ ≥ 0:
aᵢ₁x₁ + … + aᵢₙxₙ + sᵢ = bᵢ
At iteration 0, the slack variables form the initial basis and equal the RHS values.
Concept Definition
Basic variable (BV) In the current basis; value given by its equation RHS
Non-basic variable (NBV) Set to zero; there are n−m of them at any BFS
Basic feasible solution All BVs ≥ 0 — corresponds to a CPF solution
Degree of freedom n−m; setting n−m variables to 0 gives a basic solution
2.2 Tableau setup — prototype example
max Z = 3x₁ + 5x₂ s.t. x₁ ≤ 4, 2x₂ ≤ 12, 3x₁ + 2x₂ ≤ 18, x₁,x₂ ≥ 0
Augmented form: add s₁, s₂, s₃. Initial basis: {s₁, s₂, s₃}.
BV Z x₁ x₂ s₁ s₂ s₃ RHS
Z 1 −3 −5 0 0 0 0
s₁ 0 1 0 1 0 0 4
s₂ 0 0 2 0 1 0 12
s₃ 0 3 2 0 0 1 18
2.3 Four iteration steps
• Step 1 — Optimality test: if all Z-row coefficients ≥ 0, current BFS is optimal → stop
• Step 2 — Enter: column with the most negative Z-row coefficient (pivot column)
• Step 3 — Leave (min ratio test): divide RHS by each positive pivot-column entry; smallest ratio →
pivot row (that BV leaves)
• Step 4 — Pivot: Gauss-Jordan row ops so pivot element = 1 and all other pivot-column entries = 0
Ratio test — what to ignore
• Only use rows where the pivot-column entry is strictly > 0
• If ALL pivot-column entries ≤ 0: Z is unbounded — no finite optimum
• Tie in ratio test → degenerate solution; pick either row
2.4 Handling = and ≥ constraints
Constraint Transformation Initial BV
≤ Add slack sᵢ ≥ 0 sᵢ
= Add artificial Rᵢ ≥ 0 Rᵢ
≥ Subtract surplus sᵢ ≥ 0; add artificial Rᵢ ≥ 0 Rᵢ
Negative RHS Multiply both sides by −1 (reverses inequality) —
Operations Research — University of Groningen IEM 3
