Back to the on-screen lesson ·
The basis written so it can be read: identity columns, a right-hand column of values, and a negated objective row.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to write the starting tableau of a program with slack variables and a negated objective row, read the current basis, its values and its objective value straight off it, decide from the objective row whether a variable may enter and which one the usual rule chooses, and name the three tableau states at which the method stops.
You can form the basic solution of a chosen basis. The tableau is that arithmetic written down once so the next basis can be reached by row operations instead of by solving a fresh system.
The tableau is the constraint equations and the objective, written so that the basic variables have been eliminated from everything else. The objective row carries the negated coefficients of the non-basic variables; each such number is a reduced cost, the gain per unit of bringing that variable in from zero. The variable chosen to rise is the entering variable.
Write the standard form with its slack columns forming an identity matrix, and put the negated objective underneath. The identity names the basis, the right-hand column gives its values, and the corner of the objective row gives the objective. Everything about the current corner is legible without any further work.
The convention. For a maximisation the objective row is stored negated, so a negative entry means improvement is still available and the size of the entry is the gain per unit. When no entry is negative, no variable can improve the objective, and the basis is optimal — not by inspection of the region, but because no adjacent corner is better and convexity makes that enough.
Choosing. Any negative entry may enter. The usual rule takes the most negative, which is the steepest rate; it is a heuristic, because a steep rate may buy very few units. Correctness does not depend on it, and Bland's rule deliberately chooses badly in order to guarantee termination.
Another way: steps
Another way: example
Workshop: rows $2, 5, 1, 0 \mid 100$ and $3, 2, 0, 1 \mid 60$, objective row $-30, -50, 0, 0 \mid 0$. The most negative entry is $-50$, so $x_2$ enters first.
The sign convention is read backwards, so a positive objective-row entry is taken as an invitation and the method walks downhill. The other error is treating the reduced cost as the variable's profit: after the first pivot it is the profit net of what the variable displaces, and the two numbers differ.
Rows $2, 5, 1, 0 \mid 100$ and $3, 2, 0, 1 \mid 60$: the slack columns are an identity, so the basis is $\{s_1, s_2\}$.
The identity names the basis.
The right-hand column gives their values: $s_1 = 100$, $s_2 = 60$, and every non-basic variable is zero, so $x_1 = x_2 = 0$.
The values are already there.
The objective row's corner is $0$: the plan that makes nothing earns nothing. Two negative entries remain, so it is not optimal.
And so is the value.
No entry is negative, so nothing can improve the objective: this basis is optimal.
Read the signs.
The optimal value is $1200$, and the two zeros sit under the basic variables, as they always do.
Maximise $4x + 3y$ subject to $2x + y \le 17$ and $6x + 5y \le 33$, $x, y \ge 0$. Fill in the starting tableau.
| $x$ | $y$ | $s_1$ | $s_2$ | Right-hand side | |
|---|---|---|---|---|---|
| First constraint | |||||
| Second constraint | |||||
| Objective row |
A maximisation tableau has objective row entries $-9$ under $x$ and $-4$ under $y$, and zero under both slacks. Which variable enters the basis?
The objective row entry under $x$ is $-5$. By how much does the objective rise for each unit of $x$ brought in from zero?
Answer:
The objective is to maximise $8x + 3y$, and the standard form adds slacks $s_1$ and $s_2$. Write the starting tableau's objective row, columns $x$, $y$, $s_1$, $s_2$.
This task has no paper form; do it on a device.
A tableau with $2$ constraint rows is not yet optimal. Put the steps of one iteration into order.
Number the steps in order (write the number in the box):
Select every tableau state at which the simplex method stops and reports.
This task has no paper form; do it on a device.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Maximise $5x + 3y$ subject to $3x + y \le 13$ and $2x + 2y \le 38$, $x, y \ge 0$. Fill in the starting tableau.
| $x$ | $y$ | $s_1$ | $s_2$ | Right-hand side | |
|---|---|---|---|---|---|
| First constraint | |||||
| Second constraint | |||||
| Objective row |
You can build a starting tableau and read a basis, its values and its optimality off it. Say in your own words what a negative entry in the objective row is telling you.
7. Your turn: the objective row is $0, 0, 4, 7 \mid 1200$. What does it say?, step 2