All Basic Feasible Solutions in 2D
All Basic Feasible Solutions in 2D
In two-variable graphical problems, BFSs correspond to feasible vertices after conversion to standard form.
Workflow
- Draw all boundary lines.
- Find all intersections of pairs of active constraints.
- Keep only feasible intersections.
- Each feasible vertex is an extreme point.
- In standard form, each extreme point corresponds to at least one BFS.
Example
\[\max x_1+x_2\]subject to
\[x_1+2x_2\le10,\] \[2x_1+x_2\le16,\] \[-x_1+x_2\le3,\] \[x_1,x_2\ge0.\]Feasible vertices:
\[(0,0),\quad (0,3),\quad (4,3),\quad \left(\frac{22}{3},\frac43\right),\quad (8,0).\]Objective values for $x_1+x_2$:
| point | value |
|---|---|
| $(0,0)$ | 0 |
| $(0,3)$ | 3 |
| $(4,3)$ | 7 |
| $(22/3,4/3)$ | $26/3$ |
| $(8,0)$ | 8 |
The optimum is
\[\left(\frac{22}{3},\frac43\right), \qquad z^*=\frac{26}{3}.\]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.