BFS and Reduced Cost Drill Set
BFS and Reduced Cost Drill Set
Core workflow
For a candidate point:
original variables
→ standard-form variables
→ compute slack/surplus values
→ check feasibility
→ identify a basis B
→ check B is invertible
→ compute reduced costs
→ decide optimality
Worked problem 1 — feasible but not BFS
Original:
\[\max x_1-5x_2+4x_3\]subject to
\[3x_1-2x_2+x_3=10,\] \[x_2+2x_3\le5,\] \[3x_1+5x_2+x_3\ge10,\] \[x\ge0.\]Check $\bar x=(3,0,1)^T$.
Step 1 — standard form
\[\min -x_1+5x_2-4x_3\]subject to
\[3x_1-2x_2+x_3=10,\] \[x_2+2x_3+s_1=5,\] \[3x_1+5x_2+x_3-s_2=10,\] \[x_1,x_2,x_3,s_1,s_2\ge0.\]Step 2 — lift the point
At $(3,0,1)$:
\[s_1=5-0-2=3,\] \[s_2=3(3)+5(0)+1-10=0.\]So
\[\hat x=(3,0,1,3,0)^T.\]It is feasible.
Step 3 — check BFS
The positive variables are $x_1,x_3,s_1$. Their columns are
\[A_1=\begin{bmatrix}3\\0\\3\end{bmatrix},\quad A_3=\begin{bmatrix}1\\2\\1\end{bmatrix},\quad A_{s_1}=\begin{bmatrix}0\\1\\0\end{bmatrix}.\]These columns are linearly dependent because rows 1 and 3 of the selected matrix are identical after selecting these columns:
\[\begin{bmatrix} 3&1&0\\ 0&2&1\\ 3&1&0 \end{bmatrix}.\]Therefore $\bar x$ is feasible but not a BFS.
Worked problem 2 — BFS and optimal
Original:
\[\max 5x_1-5x_2\]subject to
\[x_1+x_2+x_3=4,\] \[-x_1+3x_2-6x_3\le-4,\] \[-3x_1+4x_2+4x_3\ge2,\] \[x\ge0.\]Check $\bar x=(2,0,2)^T$.
Standard form
Convert to minimization:
\[\min -5x_1+5x_2\]subject to
\[x_1+x_2+x_3=4,\] \[-x_1+3x_2-6x_3+s_1=-4,\] \[-3x_1+4x_2+4x_3-s_2=2,\] \[x_1,x_2,x_3,s_1,s_2\ge0.\]At $(2,0,2)$:
\[s_1=10, \qquad s_2=0.\]Thus
\[\hat x=(2,0,2,10,0)^T.\]Use basis $B=[A_1,A_3,A_{s_1}]$:
\[B=\begin{bmatrix} 1&1&0\\ -1&-6&1\\ -3&4&0 \end{bmatrix}, \qquad \det(B)=-7\ne0.\]So the point is a BFS.
For $c=(-5,5,0,0,0)^T$ and $c_B=(-5,0,0)^T$,
\[\bar c^T=c^T-c_B^TB^{-1}A=(0,5,0,0,5/7).\]All reduced costs are nonnegative, so the BFS is optimal for the minimization form. Therefore $(2,0,2)$ is optimal for the original maximization problem.
Worked problem 3 — reduced costs from a basis
Consider
\[\min -3x_1-2x_2\]subject to
\[x_1+x_2+s_1=4,\] \[2x_1+x_2+s_2=5,\] \[x_1,x_2,s_1,s_2\ge0.\]Start with basis $B=[A_{s_1},A_{s_2}]=I$.
Then
\[x_B=(4,5)^T.\]Reduced costs:
\[\bar c_1=-3, \qquad \bar c_2=-2, \qquad \bar c_{s_1}=0, \qquad \bar c_{s_2}=0.\]Because $\bar c_1<0$ and $\bar c_2<0$, the current BFS is not optimal. The best entering variable by most negative reduced cost is $x_1$.
Practice problems
For each problem, verify the BFS and compute reduced costs.
- $\min -3x_1-2x_2$ with $x_1+x_2+s_1=4$, $2x_1+x_2+s_2=5$, basis ${s_1,s_2}$.
- Same problem, basis ${s_1,x_1}$.
- $\min 2x_1+3x_2+4x_3+x_4$ subject to $2x_1+x_2+x_3=1$, $x_1+3x_2+0.5x_4=2$, basis ${x_1,x_2}$.
- Convert the third constraint of a $\ge$ row using a surplus variable, then test the candidate point.
- Create one example where a feasible point is not a BFS because the positive columns are dependent.
Exam checkpoint
Practice under exam timing. Write the full pipeline: model, standard form if needed, BFS/reduced costs if asked, simplex iterations if asked, final objective value and interpretation.
Additional BFS/reduced-cost drills with answer keys
6. Optimal basis check
Problem:
\[\min 2x_1+3x_2+4x_3+x_4\]subject to
\[2x_1+x_2+x_3=1,\] \[x_1+3x_2+0.5x_4=2,\] \[x\ge0.\]Check basis $B=[A_1,A_2]$.
Answer:
\[B^{-1}b=(1/5,3/5)^T.\]So
\[x=(1/5,3/5,0,0).\]Reduced costs:
\[\bar c=(0,0,17/5,3/5).\]The basis is feasible and optimal.
7. Nonoptimal basis check
Same problem, check basis $B=[A_3,A_4]$.
Answer:
\[x_B=(1,4)^T,\]so the BFS is
\[x=(0,0,1,4).\]Reduced costs:
\[\bar c=(-8,-7,0,0).\]This BFS is feasible but not optimal.
8. Degenerate BFS recognition
Consider
\[x_1+x_2+s_1=1, \qquad x_1+s_2=0, \qquad x\ge0.\]With basis $B=[A_{s_1},A_{s_2}]$, compute $x_B$.
Answer:
\[x_B=(1,0)^T.\]The BFS is feasible and degenerate because one basic variable is zero.
9. Infeasible candidate after lifting
Original constraint:
\[x_1+2x_2\le5.\]Candidate: $(x_1,x_2)=(4,2)$.
Answer:
Slack is
\[s=5-4-4=-3.\]Since $s<0$, the candidate is infeasible and cannot be a BFS.
10. Surplus-variable feasibility check
Original constraint:
\[3x_1+x_2\ge10.\]Candidate: $(2,1)$.
Answer:
Surplus is
\[s=3(2)+1-10=-3.\]Since the surplus variable would be negative, the candidate violates the original $\ge$ constraint.