Topics Covered

On this page

1. 1. General Linear Programming Problem (GLP)
2. 2. Slack, Surplus and Artificial Variables
3. 3. Standard Form and Canonical Form
4. 4. Types of Solutions
5. 5. Simplex Algorithm — Computational Procedure
6. 6. Structure of the Simplex Tableau
7. 7. Worked Example — Maximisation
8. 8. Worked Example — Minimisation
9. 9. Three-Variable Example
10. 10. Interpreting the Final Tableau
11. Key Take-aways

1. General Linear Programming Problem (GLP)

Matrix Form

2. Slack, Surplus and Artificial Variables

2.1 Slack Variable (for ≤ constraint)

Convert an inequality \(a_{i1} x_1 + \cdots + a_{in} x_n \le b_i\) to an equality by adding a non-negative slack variable \(s_i\):

The slack represents unused resource. Its objective coefficient is 0.

2.2 Surplus Variable (for ≥ constraint)

Convert \(\sum a_{ij} x_j \ge b_i\) to equality by subtracting a non-negative surplus variable \(s_i\):

The surplus represents the amount by which a requirement is exceeded. Objective coefficient is 0.

2.3 Artificial Variable

For = constraints (or after introducing surplus to ≥ constraints), the simplex needs an obvious starting basis. Add an artificial variable \(A_i \ge 0\) with a very large objective penalty (Big-M, see Unit 4).

2.4 Unrestricted Variable

If a variable \(x_j\) can take any real value, replace it by \(x_j = x_j' - x_j''\) with \(x_j', x_j'' \ge 0\).

3. Standard Form and Canonical Form

3.1 Standard Form

An LPP is in standard form when:

1. The objective is to maximise \(Z\) (a minimisation problem becomes Max(\(-Z\))).
2. All constraints are equalities with non-negative right-hand sides \(b_i \ge 0\).
3. All decision variables are non-negative.

3.2 Canonical Form

An LPP is in canonical form when:

1. The objective is to maximise \(Z\).
2. All constraints are \(\le\) with non-negative right-hand sides.
3. All decision variables are non-negative.

Conversion rules:

• Min \(Z\) → Max \(-Z\).
• \(\ge\) constraint × (−1) ⇒ \(\le\) constraint.
• = constraint ⇒ two constraints (\(\le\) and \(\ge\)).
• Unrestricted \(x_j\) → \(x_j' - x_j''\).

4. Types of Solutions

• Solution — any \(\mathbf{x}\) satisfying the constraints \(A\mathbf{x} = \mathbf{b}\).
• Basic solution — set \(n - m\) of the variables to zero (non-basic) and solve the remaining \(m \times m\) system. The \(m\) chosen variables form the basis.
• Basic feasible solution (BFS) — a basic solution where all variables are non-negative.
• Degenerate solution — a basic feasible solution in which at least one basic variable is zero.
• Optimum basic feasible solution — a BFS that optimises \(Z\); this is what the simplex method finds.

Key theorem: If an LPP has an optimal solution, it has an optimal basic feasible solution. So the simplex method need search only among the finite set of BFSs (vertices).

5. Simplex Algorithm — Computational Procedure

5.1 Algorithm Steps (Maximisation)

1. Convert to standard form by adding slack variables.
2. Initial BFS: set decision variables to 0; slacks = b. Construct the initial simplex tableau.
3. Optimality test: compute \(z_j - c_j\) (or \(c_j - z_j\)) for each non-basic variable.
   • For Max: if all \(c_j - z_j \le 0\), current BFS is optimal — STOP.
   • Otherwise, pick the variable with the most positive \(c_j - z_j\) — this is the entering variable.
4. Ratio test: for each row with a positive coefficient in the entering column, compute \(\theta_i = b_i / a_{ij}^*\). The row with the smallest non-negative ratio determines the leaving variable (and the pivot element).
5. Pivot: perform row operations to make the pivot element 1 and all other entries in the entering column 0. Update the tableau.
6. Go back to step 3.

For Minimisation: either convert to Max \(-Z\), or use \(z_j - c_j\) test where we look for the most negative entry.

6. Structure of the Simplex Tableau

The tableau is a tabular bookkeeping format:

cB	Basis	xB	c₁	c₂	…	cn	θ (ratio)
cB1	xB1	b₁	a₁₁	a₁₂	…	a1n	θ₁
cB2	xB2	b₂	a₂₁	a₂₂	…	a2n	θ₂
Zj		Z = cB·b	z₁	z₂	…	zn
cj − Zj			c₁−z₁	c₂−z₂	…	cn−zn

• c_B: objective coefficients of the current basic variables.
• Basis: the basic variables in the current solution.
• x_B: their values (= b column).
• z_j = c_B·a_j: implied unit value of variable \(x_j\).
• c_j − z_j: net contribution to Z per unit increase of \(x_j\).

7. Worked Example — Maximisation

Step 1 — Standard form

Add slacks \(s_1, s_2\):

Step 2 — Initial tableau

cB	Basis	xB	x₁ (3)	x₂ (2)	s₁ (0)	s₂ (0)	θ
0	s₁	4	1	1	1	0	4/1 = 4
0	s₂	6	1	3	0	1	6/1 = 6
Zj		0	0	0	0	0
cj−Zj			3	2	0	0

Most positive \(c_j - z_j = 3\) ⇒ \(x_1\) enters. Ratios: 4 and 6 ⇒ row 1 leaves (s₁ exits). Pivot element = 1 (row 1, x₁ column).

Step 3 — Pivot & Iteration 2

R₁ stays (pivot already 1); R₂ → R₂ − R₁:

cB	Basis	xB	x₁ (3)	x₂ (2)	s₁ (0)	s₂ (0)	θ
3	x₁	4	1	1	1	0	4/1 = 4
0	s₂	2	0	2	−1	1	2/2 = 1
Zj		12	3	3	3	0
cj−Zj			0	−1	−3	0

All \(c_j - z_j \le 0\) (the largest is \(0\), and \(x_2\)'s entry is \(-1\)), so no non-basic variable can improve \(Z\) — the tableau is optimal.

Optimal solution: \(x_1 = 4,\; x_2 = 0,\; s_1 = 0, s_2 = 2;\; Z_{\max} = 12\).

8. Worked Example — Minimisation

Strategy

Convert to standard form by introducing surplus variables and then artificial variables (since they're ≥ constraints with no obvious starting basis). This invokes the Big-M method covered in Unit 4. Alternatively, convert to Max \(-Z\):

For an LPP with all "≤" constraints and non-negative b, just convert Min to Max (−Z), add slacks and apply the standard simplex.

9. Three-Variable Example

Add slacks \(s_1, s_2, s_3\) and start with BFS \(s_1 = 60, s_2 = 40, s_3 = 80\), Z = 0.

Most positive \(c_j - z_j\) = 4 ⇒ \(x_2\) enters. Ratios 60/4 = 15, 40/1 = 40, 80/3 ≈ 26.67. Smallest is 15 ⇒ \(s_1\) leaves. Pivot, iterate, and eventually find optimum.

(Result after two further iterations: \(x_1 = 0,\; x_2 = 20/3 \approx 6.67,\; x_3 = 50/3 \approx 16.67,\; Z = 230/3 \approx 76.67\), with the first two constraints binding. Detailed tableau steps follow the same procedure as Section 7.)

10. Interpreting the Final Tableau

• Basic variables give the optimal values.
• Slack values indicate unused resources (zero slack ⇒ binding constraint).
• The values in the \(c_j - z_j\) row for slack variables give the shadow prices (cost of one more unit of resource) — see Unit 5 on duality.

Key Take-aways

• Standard form: Max Z, equality constraints, non-negative variables and b's.
• Slack (for ≤), surplus (for ≥), artificial (for = or ≥) and unrestricted-variable trick are basic transformations.
• Simplex moves from vertex to adjacent vertex improving Z; terminates in finite steps.
• Entering variable: most positive \(c_j - z_j\) (Max). Leaving variable: smallest non-negative ratio.
• Stopping criterion: all \(c_j - z_j \le 0\) (Max) or \(\ge 0\) (Min).