In this section, we examine pivoting with primal-dual tableau’s. We will compare (in a good way!) to what we did in Section 2.1.
Activity4.3.1.
Noting that the dual variables \(y_i\) are non-negative weights attached to the hyperplanes defined by \(t_i=0\text{,}\) and the slack variables for the dual problem \(s_j\) are the weights associated with the planes \(-x_j=0\text{,}\) we can encode all this information in the Primal-Dual Tucker Tableau:
\(x_1\)
\(\cdots\)
\(x_m\)
\(-1\)
\(y_1\)
\(a_{11}\)
\(\cdots\)
\(a_{1m}\)
\(b_1\)
\(=-t_1\)
\(\vdots\)
\(\vdots\)
\(\ddots\)
\(\vdots\)
\(\vdots\)
\(\vdots\)
\(y_n\)
\(a_{n1}\)
\(\cdots\)
\(a_{nm}\)
\(b_n\)
\(=-t_n\)
\(-1\)
\(c_1\)
\(\cdots\)
\(c_m\)
\(d\)
\(=f\)
\(=s_1\)
\(\cdots\)
\(=s_m\)
\(=g\)
(The additional dividing lines in the top left and bottom right seperate the primal decision-slack variables from the dual decision-slack variables.)
(a)
Write out the sufficient conditions for the tableau to determine:
The primal problem is feasible.
The dual problem is feasible.
The feasible primal problem is unbounded above.
The feasible dual problem is unbounded below.
The primal problem is infeasible.
The dual problem is infeasible.
The primal problem has a feasible optimal solution.
Consider the dual solution. What does that mean in the context of the time spent by the painter and the sculptor?
Activity4.3.3.
(a)
If a primal problem is infeasible, what could be true of the dual problem?
The dual problem has an optimal solution.
The dual problem is unbounded below.
The dual problem is infeasible.
(b)
For each of the possibilities discussed in (a), fill in the tableau below to achieve this criteria or explain why it is not possible.
\(x_1\)
\(x_2\)
\(-1\)
\(y_1\)
\(-1\)
\(?\)
\(?\)
\(=-t_1\)
\(y_2\)
\(1\)
\(?\)
\(?\)
\(=-t_2\)
\(?\)
\(?\)
\(?\)
\(?\)
\(=f\)
\(=s_1\)
\(=s_2\)
\(=g\)
Activity4.3.4.
We now consider unconstrained and equality constrained primal-dual problems.
(a)
Suppose for a pair of primal-dual solutions if \(x_j\) were allowed to be be any value including negative values, What must be true about \(s_j\text{?}\) (If \(x_j\) is unconstrained, what can we say about the hyperplane \(-x_j=0\) as a bounding hyperplane?)
\(s_j\) could be any value as well.
\(s_j\geq 0\text{.}\)
\(s_j\leq 0\text{.}\)
\(s_j=0\text{.}\)
\(s_j\neq 0\text{.}\)
(b)
Suppose for a pair of primal-dual solutions if \(t_i=0\text{.}\) What must be true about \(y_i\text{?}\) (If we increase \(b_i\) can we predict if that helps or hurts \(f\text{?}\) Does it matter?)
\(y_i\) could be any value as well.
\(y_i\geq 0\text{.}\)
\(y_i\leq 0\text{.}\)
\(y_i=0\text{.}\)
\(y_i\neq 0\text{.}\)
Activity4.3.5.
(a)
Solve the following non-canonical primal-dual problem:
\(\ec{x_1} \)
\(x_2\)
\(x_3\)
\(-1\)
\(\ec{y_1}\)
\(0\)
\(-1\)
\(-1\)
\(-1\)
\(=-0\)
\(y_2\)
\(-1\)
\(-3\)
\(4\)
\(0\)
\(=-t_2\)
\(y_3\)
\(-1\)
\(2\)
\(-3\)
\(0\)
\(=-t_2\)
\(-1\)
\(-1\)
\(0\)
\(0\)
\(0\)
\(=f\)
\(=0\)
\(s_2\)
\(=s_3\)
\(=g\)
(b)
Enter the primal-problem and use Sage to confirm the solution:
