Section 4.4 Summary of Chapter 4
We recall that at each corner or extreme point solution, this solution lies on the intersection of bounding hyperplanes of the feasible region. We also note that the orthogonal vector for the objective plane may be written as a linear combination of the orthogonal vectors for these bounding hyperplanes, and in particular, the coefficients of the linear combination are exactly the negative of the in the corresponding tableau.
In some sense what tells us is how much increases if the corresponding decreases by one, i.e. the bound associated with were relaxed by one. This gives us a way of determining how relaxing each of the constraints compare to each other, and their relative value to each other. So in the case of Exploration 4.1.1, We have
We have that the normal vector for the objective plane, may be written as and lowering by 1 decreases the objective by 3, and lowering by 1. decreases it by 2.
But should we pivot to
Then and decreasing by 1 increases the objective by and decreasing by 1 increases the objective by Note that this is equivalent to saying how much value would be gained should there by one more newt eye or frog respectively.
This inspires us to define the dual problem of a primal maximization problem in Definition 4.1.5, where the are the weights or coefficients of the normal vectors for bounding hyperplanes of the feasible region. We may define the to be the slack variable for each dual constraint so that or equivalently:
and we have feasibility if and only if each
We then note that by reformulating the primal and dual problem using matrix algebra, then for feasible we have that
which is the statement of the Weak Duality Theorem Proposition 4.2.3. In particular, if for feasible then both are optimal.
It turns out the converse to this statement is true as well. To show this, we suppose that achieves optimality at
We let depending on which variable is the coefficient for, and by letting each other we have that
We note that since the above tableau satisfies the conditions for an optimal basic solution, each Since the above equality is an equality of functions of by comparing coefficients of we have and is a feasible solution. Then we also have that The left hand side is the optimal value for and the right hand side is the current value of for this choice of So by Proposition 4.2.3, we prove the Strong Duality Theorem Theorem 4.2.4.
We then note that the dual problem may be recorded simultaneously as the primal problem within the same tableau
and that by using similar arguments as we did in Chapter 2, we may establish conditions for determining the feasibility, optimality, and boundedness if the dual problem. A basic dual variable is feasible if and only if each and if we had a but each for that problem, then the problem is infeasible, since this inequality can never be satisfied. If the basic dual is feasible then it is also optimal if and only if However, if the basic dual is feasible but there is a row where then the dual region is unbounded, and if additionally then the dual problem is unbounded below. These boundedness conditions are sufficient but not necessary, the reader is encouraged to come up with their own counterexamples to necessity.
We conclude by observing that if a primal problem has an unconstrained variable, the corresponding dual variable must be zero, since the associated hyperplane is not a bounding hyperplane. Similarly, if we had an equality constraint in the primal with corresponding slack set to zero, the corresponding dual is allowed to be unconstrained, since it is no longer relevant whether pivoting away from this plane improves the primal objective.