The Trial of Bland’s Rule

Defendant: Bland’s Rule

Charge: Allowing cycling to occur

The prosecutor introduces evidence that a sequence of tableaus T₀, T₁, …, T_k occurred one after the other in pivoting using Bland’s Rule. He points out that T_k = T₀, therefore cycling occurred.

In these pivots some variables, which we’ll call the participants, entered and left the basis at least once each. No other variables entered or left. The highest numbered participant is x_t. The defence calls x_t as a witness.

Defence Attorney (Perry Mason): Please indicate a pivot where you entered the basis.

x_t: The one starting in this tableau.

Perry Mason: Let the record show the witness indicated one of the tableaus, which for convenience I’ll call T_E. And why did you enter the basis at that pivot?

x_t: I had to. Mr. Bland said the entering variable has to be the lowest-numbered one with a negative entry in the objective row.

All the variables with a number less than mine had positive or 0 entries in the objective row, but mine was negative.

Perry Mason: And now please indicate a pivot where you left the basis.

x_t: The one starting in this tableau.

Perry Mason: Let the record show the witness indicated one of the tableaus, which for convenience I’ll call T_L. And why did you leave the basis at that pivot?

x_t: Again, I had to. Another participant, x_s, was entering the basis. We calculated the ratios: mine was 0, since I had an entry of 0 in the right-hand-side and a positive entry in the x_s column.

Perry Mason: And what about the other participants? Didn’t they also have right-hand-side entries of 0?

x_t: Yes, since these were degenerate pivots, when they were basic they always had right-hand-side entries of 0.

Perry Mason: So why wasn’t any of them chosen as entering variable instead of you?

x_t: Mr. Bland said in case of a tie for least ratio, to choose the lowest-numbered variable with that ratio. So they would have been chosen instead of me if they had a ratio. But none of them did: all the other participants that were basic had negative or 0 entries in the x_s column.

Perry Mason: Thank you, you may step down. The defence now calls tableau T_E as a witness.

(T_E takes the stand)

Perry Mason: As a tableau, you have within you all the information about solutions to this linear programming problem, is that correct?

T_E : Yes, sir, I do.

Perry Mason: Now I want to ask you what would happen to the objective

in a situation where x_t decreased, all the other participants either increased or stayed the same, and all nonbasic variables that were not participants stayed the same?

Prosecutor: I object, that is a hypothetical question.

Perry Mason: Your Honor, this is mathematics, where we have hypothetical questions all the time.

Judge: Objection overruled. The witness will answer the question.

T_E : My objective row shows what happens to the objective if you changed the values of nonbasic variables. Since x_t is supposed to decrease, and it has a negative entry there, that would decrease the objective. All the other participants that are nonbasic in me have a positive or 0 entry there. If you increased them and the entry was positive, that would decrease the objective even more. If the entry was 0 or they stayed the same, that would have no effect. So the answer is that the objective would decrease.

Perry Mason: Thank you, you may step down. The defence now calls tableau T_L as a witness.

(T_L takes the stand)

Perry Mason: One of your nonbasic variables is x_s, is that correct?

T_E : Yes, it’s the one that I chose as entering variable.

Perry Mason: x_t has testified that it had a positive entry in your x_s column. What would happen to the value of x_t if x_s increased and all other nonbasic variables stayed the same?

T_E : That would make x_t decrease.

Perry Mason: And what would happen to the other participants?

T_E : Those that are basic have negative or 0 entries in my x_s column, so they would either increase or stay the same.

Perry Mason: And x_s and the other nonbasic ones?

T_E : You said, x_s increases and the others stay the same.

Perry Mason: And what about the objective?

T_E : Since x_s has a negative entry in the objective row, the objective would increase.

Perry Mason: So according to what you’re telling us, this is a situation

where x_t decreases, all the other participants either increase or stay the same, and all nonbasic nonparticipants stay the same, and the objective would increase?

T_E : That’s correct.

Perry Mason: Your Honor, we just heard testimony from tableau T_L that contradicts this witness. T_L said if x_t decreased, all the other participants either increased or stayed the same, and all nonbasic nonparticipants stayed the same, then the objective would decrease, and T_E says in this case it would increase. They can’t both be right. The prosecution’s case contains a contradiction!

Judge: In Mathematics, when we reach a contradiction we conclude that some of our assumptions must have been wrong. Case dismissed. The defendant is free to go.