Flashcards
Answer
Graphical Method
The graphical method solves a two-variable linear programming problem by drawing its feasible region and moving the objective contour line until the best feasible point is reached.
It is the geometric version of linear programming.
See
-
Plotting Linear Inequalities
- How each constraint becomes a boundary line and a half-plane.
-
Feasible Regions
- How all constraints combine into the set of feasible solutions.
-
Objective Contour Lines
- How the objective function is represented by parallel lines.
-
Cost Vector and Direction of Improvement
- How the vector $c$ tells us the direction in which the objective increases.
-
Vertex Optimality
- Why an LP optimum can be found at a vertex when it exists.
-
Multiple Optima
- What happens when an entire edge has the same optimal value.
-
Graphical Infeasibility
- How to detect that no point satisfies all constraints.
-
Graphical Unboundedness
- How to detect that the objective improves forever.
When the Method Applies
The graphical method is practical when the LP has two decision variables:
\[x=(x_1,x_2)\]Each constraint can then be drawn in the plane.
For three variables, objective contours become planes.
For more than three variables, we need algorithms such as simplex or computational solvers.
General Two-Variable LP
A typical problem is:
\[\max c_1x_1+c_2x_2\]subject to:
\[a_{11}x_1+a_{12}x_2\le b_1\] \[a_{21}x_1+a_{22}x_2\le b_2\] \[\cdots\] \[x_1,x_2\ge 0\]The same method works for minimization and for constraints with $\ge$ or $=$.
Core Idea
The graphical method separates the problem into two parts:
- draw all feasible points
- choose the feasible point with the best objective value
The feasible points form the feasible region.
The objective values are represented by parallel contour lines:
\[c_1x_1+c_2x_2=k\]Changing $k$ slides the line through the plane.
Standard Procedure
- Draw the boundary line of each inequality.
- Use a trial point to choose the feasible side.
- Intersect all feasible sides.
- Draw one objective contour line.
- Determine the direction of improvement.
- Slide the contour line in that direction.
- Stop at the last feasible point or edge.
- Compute the coordinates and objective value.
Example
Consider:
\[\max x_1+x_2\]subject to:
\[x_1+2x_2\le 10\] \[2x_1+x_2\le 16\] \[-x_1+x_2\le 3\] \[x_1,x_2\ge 0\]The feasible region is the intersection of five half-planes:
- one for each of the three main inequalities
- one for $x_1\ge 0$
- one for $x_2\ge 0$
The objective contour lines are:
\[x_1+x_2=k\]For maximization, we move these lines in the direction of:
\[c=\begin{bmatrix}1\\1\end{bmatrix}\]The final feasible point is the intersection of:
\[x_1+2x_2=10\]and:
\[2x_1+x_2=16\]Solving:
\[x_1+2x_2=10\] \[2x_1+x_2=16\]gives:
\[x_1^*=\frac{22}{3},\qquad x_2^*=\frac{4}{3}\]So:
\[x^*=\begin{bmatrix}\frac{22}{3}\\\frac{4}{3}\end{bmatrix}\]and:
\[z^*=x_1^*+x_2^*=\frac{26}{3}\]Candidate Solutions
In a bounded polygonal feasible region, the candidates are usually the vertices.
A vertex is a corner point formed by the intersection of active boundary lines.
Instead of checking every feasible point, we can check the vertices.
Possible Outcomes
A graphical LP can have:
| Outcome | Meaning |
|---|---|
| Unique optimum | one best feasible point |
| Multiple optima | a whole edge or face is optimal |
| Infeasible problem | no feasible point exists |
| Unbounded problem | objective improves forever |
Common Mistakes
A common mistake is to optimize over the whole plane instead of the feasible region.
The objective function alone may be unbounded over $\mathbb{R}^2$.
The constraints are what make the optimization meaningful.
Another common mistake is to shade the wrong side of a boundary line.
Use a trial point every time.
Checklist
You understand the graphical method if you can:
- draw each constraint as a half-plane
- find the feasible region
- draw objective contour lines
- identify the direction of improvement
- find the final point or edge touched by the contour line
- compute the optimal solution and optimal value
- recognize infeasible and unbounded cases
See Also
- Linear Programming
- Half-Spaces and Hyperplanes
- Feasible Solutions
- Standard Form
-
Simplex Method
Added exam practice
- Graphical Problems Without Nonnegativity
- Graphical Mixed Max Min Problems
- Graphical Infeasible and Unbounded Drills
- Graphical Drill Set
Exam checkpoint
For graphical questions, first check whether nonnegativity is explicitly stated. Then draw half-planes, list vertices, evaluate the objective, and state finite optimum, infeasibility, multiple optima, or unboundedness.