Question 1 (Tuesday, May 19)
When passing from the first to the second dictionary in the [example of degeneracy] letting
into the basis, there are only two possible leaving variables. If we choose
as our entering variable instead of
, we will still get a degeneracy in the dictionary (we'll get (*)
). The objective function will become
, which means
must enter, but by (*) we see it enters without changing its value so the objective function will not change on the third step.
This means that methods to cancel out degeneracies should affect both the entering and leaving variable.
Question 2 (Wednesday, May 20 Thursday, May 21)
a.
b. Geometrically, the given LP is degenerate as the point
is on the face (the boundary) of three inequalities. Thus, you can perturb it to make sure you never stall. However, in this case this is unnecessary as algebraically we won't see the degeneracy: The first dictionary reads
and so is not degenerate. The second, after pivoting
with
:
Note the objective function did increase from 0 to 2, and there is still no degeneracy in the dictionary (as we didn't reach the degenerate vertex). Then, by pivoting
with
:
And the objective function increased to 5, which is its optimal value.
c*. In dimension 2, a degeneracy always consists of one constraint that is "behind" two other constraints and so will never be used (in the above example this is the second constraint). Thus we can simply delete it which is much simpler than perturbing the dictionaries.
Question 3 (Friday, May 22)
To decide if the LP is feasible we'll use the two phase method:
We next pivot
with
:
We next pivot
with
:
Thus there is a feasible solution: