DSES DQE Question on Deterministic OR, Fall 1994.

Question: Consider the linear programming problem

$$\begin{array}{lrcrcrcrcrclr} \min & x_1 & + & x_2 & + & x_... ... %5 & & &&& x_i & \geq & 0, && i & = & 1,...,5. \end{array}$$

In what follows, assume that the problem $(P)$ has an optimal solution $\bar{x}$, where $\bar{x}_1$, $\bar{x}_2$ and $\bar{x}_3$ are basic. You do not need to find $\bar{x}$.

1. What is the dual to this linear program?
2. Use complementary slackness to find an optimal solution $\bar{y}$ to the dual problem.
3. Looking purely at the optimal dual solution you found above, can you conclude that no optimal primal solution will have $x_4>0$? What about $x_5$?
4. The optimal dual solution $\bar{y}$ is not unique: there are other optimal solutions of the form $\bar{y}+\lambda[-1,-2,1]^T$. What is the largest possible value of $\lambda$? Do these other optimal solutions imply anything about the values of $\bar{x}_1$, $\bar{x}_2$ and $\bar{x}_3$? Do they imply anything about the values of $x_4$ and $x_5$ in any optimal solution to $(P)$?

Answer:

1. 
   
   $$\begin{array}{lrcrcrcl} \max & y_1 & + & y_2 & + & 3y_3 \\... ...eq & 4 \\ & -y_1 & - & y_2 & + & y_3 & \leq & 3 \end{array}$$
   
   

2. Since there is an optimal basic feasible solution (bfs) with $x_1$, $x_2$ and $x_3$ basic, there must be an optimal dual solution where the first three constraints hold at equality. Thus, we find an optimal dual solution by solving the equations
   
   $$\begin{array}{rcrcrcl} -y_1 & + & y_2 &&& = & 1 \\ && y_2 & + &2y_3 & = & 1 \\ y_1 &&& + & y_3 & = & 1 \end{array}$$
   
   
   Solving these equations gives $\bar{y}_1=2$, $\bar{y}_2=3$, $\bar{y}_3=-1$. It can be verified that this solution is dual feasible.
3. Every primal optimal solution is complementary to every dual optimal solution. Thus, any primal optimal solution must be complementary to $\bar{y}$. The dual constraint corresponding to $x_4$ is
   
   $$3y_1+ 2y_3 \leq 4$$
   
   
   This constraint is satisfied at equality by the dual solution $\bar{y}$ found above. Therefore, primal solutions with $x_4>0$ may satisfy complementary slackness with respect to $\bar{y}$ and so such solutions may be primal optimal.

   However, the dual solution $\bar{y}$ satisfies the last constraint strictly; thus, no primal optimal solution can have $x_5>0$.

4. Any primal optimal solution is complementary to any dual optimal solution. If we let $c$ denote the primal objective function, $A$ denote the primal constraint matrix, and $z$ denote the dual slacks, then along the given dual set of optimal solutions we have
   
   $$z = c-A^Ty = \left[ \begin{array}{ccc} 0 & + & \lambda \\ ... ...\ 0 & + & \lambda \\ 9 & - & 4 \lambda \end{array} \right]$$
   
   
   This is dual feasible for $0 \leq \lambda \leq 9/4$, and $z_1>0$, $z_4>0$, $z_5>0$ for $0<\lambda <9/4$. Thus, by complementary slackness, we must have $x_1=x_4=x_5=0$ in any primal optimal solution. Therefore, $\bar{x}_1=0$. We can not conclude anything about $\bar{x}_2$ or $\bar{x}_3$