\documentclass[a4paper,12pt]{article}

\begin{document}

\parindent=0pt

QUESTION

\begin{description}

\item[(a)]
State the Duality Theorem of linear programming, and use it to
prove the Theorem of Complementary Slackness.

\item[(b)]
 Use duality theory to determine whether $x_1 = 3$,
$x_2= 0$,  $x_3= -2$, $x_4 = 0$, is an optimal solution of the
linear programming problem

\begin{tabular}{ll}
maximize&$z = 10x_1 -8x_2 +8x_3+15x_4$\\subject to&$x_1 \geq 0$,
$x_2 \geq 0$\\&$7x_1 - 2x_2 + 3x_3 + 7x_4 \leq 15 $\\&$8x_1 + 5x_2
+ 4x_3 - 2x_4 \leq 18 $\\&$4x_1 + 3x_2 - 2x_3 - 3x_4  = 16$.
\end{tabular}

Analyze whether your conclusion alters if the objective is changed
to $$z' = 10x_1 -5x_2 +8x_3+17x_4$$ but the constraints are
unaltered.

\item[(c)]
If a linear programming problem has a unique optimal solution,
then is the dual guaranteed to have a unique optimal solution?
Justify your answer by providing either a proof or a counter
example.

\end{description}

ANSWER


\begin{description}

\item[(a)]
The duality theorem states that:

\begin{itemize}

\item
if the primal problem has an optimal solution, then so has the
dual, and $z_p=z_D$;

\item
if the primal problem is unbounded, then the dual is infeasible;

\item
if the primal problem is infeasible, then the dual is either
infeasible or unbounded.

\end{itemize}

Consider the following primal and dual problems

\begin{tabular}{llll}
Maximize&$z_p=\mathbf{c}^T\mathbf{x}$&Minimize&$z_D=\mathbf{
b}^T\mathbf{y}$\\ subject
to&$\mathbf{x}\geq\mathbf{)},\mathbf{s}\geq\mathbf{0}$&subject
to&$\mathbf{y}\geq\mathbf{)},\mathbf{t}\geq\mathbf{0}$\\
&$A\mathbf{x}+\mathbf{s}=\mathbf{b}$&&$A^T\mathbf{y}-\mathbf{
t}=\mathbf{c}$
\end{tabular}

For optimal solution, complementary slackness states that
$y_is_i=0\ (i=1,\ldots,m),\ t_jx_j=0\ (j=1,\ldots n)$.

For feasible solutions of the primal and dual, we have

$$z_p=\mathbf{c}^T\mathbf{x}=(\mathbf{y}^TA-\mathbf{t}^T)\mathbf{
x}=\mathbf{y}^T(\mathbf{b}-\mathbf{s})-\mathbf{t}^T\mathbf{x}=
z_D-\mathbf{y}^T\mathbf{s}-\mathbf{t}^T\mathbf{x}$$

For an optimal solution of the primal and the dual, $z_D=z_D$ so

$$\mathbf{y}^T\mathbf{s} + \mathbf{t}^T\mathbf{x}=0$$

Since variables are non-negative this implies that

$$y_is_i=0,\ i=1,\ldots,m$$

$$t_jx_j=0,\ j=1,\ldots,n$$


\item[(b)]
For the given solution $z=14,\ s_1=0,\ s_2=2$, where $s_1,s_2$ are
the two slack variables.

The dual problem is

\begin{tabular}{ll}
minimize&$z_D=15y_1+18y_2+16y_3$\\ subject to&$y_1\geq0,\
y_2\geq0$\\ &$7y_1+8y_2+4y_3\geq10$\\ &$-2y_1+5y_2+3y_3\geq-8$\\
&$3y_1+4y_2-2y_3=8$\\ &$7y_1-2y_2-3y_3=15$
\end{tabular}

Complementary slackness gives $y_2=0,\ t_1=0$ where $t_1,t_2$ are
the slack variables for the dual. Therefore

\begin{eqnarray*}
7y_1+4y_3&=&10\\ 3y_1-2y_3&=&8\\ 7y_1-3y_3&=&15
\end{eqnarray*}

The first two equations yield $y_1=2$ and $y_3=-1$, which does not
satisfy the third equation. Therefore the given solution is not
optimal.

For the modified problem, the first, third and fourth constraints
are satisfied for the new right hand sides of 10, 8,17
respectively. However, the left hand side of constraint 2 is $-7$,
which is less than the new right hand side of $-5$, so the
solution is still non optimal.

\item[(c)]
An obvious counter-example is when the primal is degenerate. For
example

\begin{tabular}{ll}
maximize&$z=2x_1+3x_2$\\ subject to&$x_1\geq0,x_2\geq0$\\
&$x_1+2x_2\leq2$\\ &$2x_1+x_2\geq3$
\end{tabular}

has $x_1=2,\ x_2=0,\ z=4$ as a unique optimal solution, but its
dual

\begin{tabular}{ll}
minimize&$z_D=2y_1+4y_2$\\ subject to&$y_1\geq0,y_2\geq0$\\
&$y_1+2y_2\geq2$\\ &$2y_1+y_2\geq3$
\end{tabular}

Has $y_1=2,\ y_2=0,\ z=4$ and $y_1=\frac{4}{3},\ y_2=\frac{1}{3},\
z=4$ as alternative optimal solutions.

\end{description}



\end{document}