BFS After Adding Slack and Surplus Variables
BFS After Adding Slack and Surplus Variables
BFS questions usually hide the important variables: the slacks and surpluses.
Example
Original:
\[x_2+2x_3\le5.\]Standard-form row:
\[x_2+2x_3+s_1=5, \qquad s_1\ge0.\]At $x_2=0,x_3=1$:
\[s_1=5-0-2=3.\]Original:
\[3x_1+5x_2+x_3\ge10.\]Standard-form row:
\[3x_1+5x_2+x_3-s_2=10, \qquad s_2\ge0.\]At $x_1=3,x_2=0,x_3=1$:
\[s_2=3(3)+5(0)+1-10=0.\]Exam warning
If a surplus variable comes out negative, the original point violates the $\ge$ constraint.
If a slack variable comes out negative, the original point violates the $\le$ constraint.
Exam checkpoint
For BFS questions, convert to standard form before checking the point. A candidate in original variables must be lifted with slack and surplus variables before testing basis columns.