Back to the on-screen lesson ·
How far the entering variable may go, which row makes way, and the row operations that rewrite the tableau.
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 run the ratio test over the positive entries of an entering column, name the leaving row and the value the entering variable takes, carry out the pivot that rewrites the tableau for the new basis, read the new objective value, and recognise a column with no positive entry as a proof that the program is unbounded.
You can build a tableau and choose an entering column from the objective row. What is missing is how far the entering variable may go, and which basic variable makes way for it.
The ratio test divides each row's right-hand side by that row's entry in the entering column, over positive entries only. The row with the smallest ratio holds the leaving variable. The pivot is the row operation that makes the entering column a column of the identity, so the new basis can be read as before.
Raising the entering variable from zero changes every basic variable. In a row whose entering-column entry is $a_i > 0$, the basic variable falls by $a_i$ per unit and reaches zero after $b_i / a_i$ units. That quotient is the ratio for the row, and the smallest of them is how far the entering variable may travel while everything stays non-negative.
Rows with a zero or negative entry give no ratio: their basic variables stay put or grow, so they impose no limit. If no row gives a ratio at all, nothing stops the entering variable and the program is unbounded — the ratio test is where that is discovered.
The pivot then rewrites the tableau for the new basis: divide the leaving row by its entering-column entry, and subtract multiples of it from every other row, the objective row included. One pass of row operations, and the next corner is readable.
Another way: steps
Another way: picture
Stand at a corner and start walking along one edge — the edge the entering variable opens. Each constraint you are standing on is a wall you are sliding away from; the first new wall you meet is the row with the smallest ratio, and you stop there, at the next corner.
Negative entries are included in the ratio test, which produces a negative ratio and, if it is taken as the minimum, a move to an infeasible point. The other error is forgetting that the objective row is pivoted too: leaving it alone gives a tableau whose basis is right and whose optimality test is about the previous basis.
Entering $x_2$ with column $(5, 2)$ against right-hand sides $(100, 60)$: ratios $100/5 = 20$ and $60/2 = 30$.
Both entries positive.
The smaller is $20$, so the first row leaves: $s_1$ goes and $x_2$ enters at the value $20$.
Smallest ratio wins.
Pivoting divides row one by $5$ and clears the $x_2$ column elsewhere; the objective rises from $0$ to $50 \times 20 = 1000$.
One pass of row operations.
Neither entry is positive, so neither row gives a ratio.
No candidate at all.
Nothing limits the entering variable, so the program is unbounded and the method stops there.
The entering column holds $4$ in the first row and $3$ in the second, against right-hand sides $20$ and $24$. Fill in each row's ratio.
| Right-hand side | Entering column entry | Ratio | |
|---|---|---|---|
| First row | 20 | 4 | |
| Second row | 24 | 3 |
The ratio test gives $21 \div 3$ in the first row and $20 \div 2$ in the second. What value does the entering variable take?
Answer:
The constraint rows read $x + 2y = 5$ and $3x + y = 16$, with columns $x$, $y$ and the right-hand side. Pivot on the $x$ entry of the first row and write both rows afterwards.
This task has no paper form; do it on a device.
The ratio test gives $8$ in the first row and $3$ in the second. Which row leaves the basis?
The objective stands at $41$. The entering variable has reduced cost $5$ and the ratio test allows it to reach $6$. Complete the reading of the tableau after the pivot.
The entering variable becomes e, and the objective becomes z.
The entering column holds $3$ in the first row, with right-hand side $9$, and $-8$ in the second. How far may the entering variable move? Give the interval.
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.
The entering column holds $5$ in the first row and $5$ in the second, against right-hand sides $40$ and $45$. Fill in each row's ratio.
| Right-hand side | Entering column entry | Ratio | |
|---|---|---|---|
| First row | 40 | 5 | |
| Second row | 45 | 5 |
You can run the ratio test, pivot a tableau and read the new corner and objective. Say in your own words why a negative entry in the entering column imposes no limit.
7. Your turn: the entering column is $(-2, -3)$ with right-hand sides $(12, 18)$. Which row leaves?, step 2