Plot Legend: The filled in dots (which you can mouse over to see their values) represent basic solutions. If they are black, they are basic infeasible solutions. If they are green, they are basic feasible solutions. (Bonus Question: Why do we refer to these points as basic solutions?) The blue line is an instance of our objective function, i.e. our objective function set equal to a given constant. The feasible set is green if bounded, yellow if unbounded, and not shown if empty. If the feasible set is not one point, it consists of innumerably infinite feasible solutions, but only those solutions that intersect the green optimal iteration of the objective function are optimal feasible solutions.
Answers to questions:
Question 1: Can we have any basic solutions with only one half-space plotted? No, we cannot. Basic solutions are where constraints intersect in the space spanned by our decision variables. If there is only one constraint, there cannot be any intersections because one line cannot intersect with itself.
Question 2: Can we have a LP in canonical inequality form with an unbounded feasible set? We can! Make the coefficients on a variable in the first constraint negative.
Question 3: Can an optimal iteration of the objective function ever bisect the feasible set (Hint: can the blue line ever go through the green region)? No, it can't. This is a result of the proof given in lecture that any optimal solution must lie on the border of the feasible set. Formally, we can say that because the derivative of each binding constraint with respect to each variable in the objective function is a constant and therefore monotonic, any reduction in slack (i.e. move towards the border of the feasible region) will result in the same vector of change in the objective value. If you want some fun, try to make the optimal iteration of the objective function spin around the feasible set by adjusting the objective function values.
Question 4: Can we have a non-basic optimal feasible solution? We can, but if and only if our objective function is parallel to a binding constraint. To better understand this, try to change the values of the objective function to see why we cannot have a non-basic optimal feasible solution if the objective function is not parallel to a binding constraint (Hint: the basic solutions are the circles on the plot that you can mouseover. Other solutions are simply unlabeled points in the feasible set).
Question 5: Can we have an unbounded feasible set with a finite optimal solution? We can. Try switching between maximization and minimization as our objective function and remember that minimizing a function is equivalent to maximizing its negative.
Question 6: What condition is necessary to be able to plot an optimal iteration of the objective function if there is an unbounded solution set? There must either be a single optimal solution or a line of optimal solutions along the border of the feasible region. This only happens when the objective function is parallel to a binding constraint.
Extra Questions for the Interested Reader: Is the feasible region of a LP always a geometric simplex? (Hint: In two dimensions, is the feasible region always a triangle?) Can a concave feasible set ever be formed using linear constraints? What are the implications of having a concave feasible set? If a concave feasible set is possible under some form of constraint, how can a computer test for convexity?