What do I mean by the following?
"Also, you should understand that all the theorems in section 3.2 apply
to primal/dual pairs where one of the problems is in standard form.
If you want to apply the ideas of section 3.2 to a primal/dual pair
that is not of this form (e.g. many of the examples in section 3.1)
then you have to relate the given primal/dual pair to a related
primal/dual pair for which the theory of section 3.2 applies."
The problem is that parts of chapter 3 are very poorly written. Given
a problem like:
Consider the following linear programming problem (LP1):
minimize x_1 + x_2
subject to
x_1 + x_2 => -1
- x_1 + x_2 <= 3
x_1 unconstrained, x_2 >= 0.
What is (LP2), the dual problem? An optimal solution of (LP1) is
(-2,1). Using complementary slackness and other theorems from section 3.2,
find an optimal solution of (LP2).
How do you correctly solve this problem? Since (LP1) isn't in
standard form, you have to do the following:
1) Find (LP1a), a linear programming problem which is in standard form and is equivalent to (LP1).
2) Translate the given optimal solution of (LP1) into an optimal
solution of (LP1a).
3) Find (LP2a), a linear programming problem which is the dual of (LP1a), and use complementary slackness to
find a candidate for optimal solution of (LP2a).
4) Check that your candidate is feasible and has the correct objective
function value and is therefore an optimal solution of (LP2a)
(by Theorem 3.6).
5) Observe that (LP2a) is equivalent to (LP2) and so the optimal solution
of (LP2a) that you've found can be translated into one of (LP2).
Yeah, it's pain, but since section 3.2 is only for primal/dual pairs
where one of the problems is in standard form, it's what you have to
do. Please note that in previous years I wasn't especially rigorous
in grading the complementary slackness problems. But this year I've
been careful in class and in class notes and am being careful above.
So don't hold the previous year's solutions as full, correct
solutions.