The simplex algorithm
The simplex method with tableaux for a maximisation problem: choosing the entering variable and the pivot, one iteration, the stopping rule, reading the solution and the path from vertex to vertex.
- 24 cards
- 4 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
A few cards from the deck
Simplex algorithm: what is it?
Show the answer
A method for solving a linear programme that moves from one vertex of the feasible region to a neighbouring vertex of better value, until no improvement is possible.
It starts from a basic feasible solution (the origin, when every constraint is a ≤ with a non-negative right-hand side) and in practice examines only a small share of the vertices.
Here is the workshop's initial tableau (objective 30x + 20y). Which cell is the pivot of the first iteration (largest-gain rule)?
```text
x y e1 e2 | b
L1 2 1 1 0 | 100
L2 1 1 0 1 | 80
z -30 -20 0 0 | 0`- Column x, row L1 (the coefficient 2)
- Column x, row L2 (the coefficient 1)
- Column y, row L2 (the coefficient 1)
- Column y, row L1 (the coefficient 1)
Show the answer
Column x, row L1 (the coefficient 2)
−30 is the most negative coefficient, so x enters. Ratios: 100 / 2 = 50 for L1 and 80 / 1 = 80 for L2. The smaller is 50: L1 gives the pivot.
At each iteration, the … variable is chosen in the objective row, and the … variable by the smallest ratio of right-hand side to positive coefficient in the column.
Show the answer
At each iteration, the entering variable is chosen in the objective row, and the leaving variable by the smallest ratio of right-hand side to positive coefficient in the column.
Choosing the smallest ratio keeps every right-hand side non-negative: the new solution stays feasible.
Simplex tableau: what is it?
Show the answer
A table that stores the constraints written as equalities, with the variables' coefficients, the right-hand sides and, in the last row, the objective.
For a maximum, the objective row is written z − c·x: a negative coefficient signals a possible gain, and the last cell gives the objective's value.