Flashcards
Answer
Simplex Method
The simplex method solves a linear program by moving from one basic feasible solution to an adjacent one, improving the objective until optimality or unboundedness is detected.
Standard Setup
Use standard form:
\[\min c^Tx\]subject to
\[Ax=b,\qquad x\ge 0.\]At a basis $B$, the current BFS is $x_B=B^{-1}b$, $x_N=0$.
One Iteration
- Compute reduced costs.
- If all reduced costs are nonnegative, stop: optimal.
- Choose a nonbasic variable with negative reduced cost to enter.
- Compute $u=B^{-1}A_j$.
- Apply the minimum ratio test.
- Replace the leaving column with $A_j$.
- Repeat.
Reduced Cost
For variable $x_j$,
\[\bar c_j=c_j-c_B^TB^{-1}A_j.\]For minimization, $\bar c_j<0$ means increasing $x_j$ decreases the objective.
Step Length
If $u=B^{-1}A_j$, then basic variables change as
\[x_B(\theta)=x_B-\theta u.\]The largest feasible step is
\[\theta^*=\min_{i:u_i>0}\frac{x_{B(i)}}{u_i}.\]Stopping Cases
- If all $\bar c_j\ge 0$, the current BFS is optimal.
- If some $\bar c_j<0$ and $u_i\le 0$ for all $i$, the problem is unbounded below.
Checklist
You should be able to compute reduced costs, choose entering/leaving variables, pivot, and detect optimality or unboundedness.
See Also
- Standard Form
- Basic Feasible Solutions
- Reduced Costs
-
Revised Simplex Method
Added exam practice
- Reduced Cost and Optimality Worked Example
- Simplex Starting From a Given BFS
- Two Iterations of Revised Simplex
- Two Iterations of Full Tableau Simplex
- Two Simplex Iterations Drill Set
Exam checkpoint
For simplex questions in minimization form, negative reduced costs indicate possible improvement. Use $u=B^{-1}A_j$, apply the ratio test only to positive components of $u$, then update the basis.