\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= 0$, $x_4 = 2$, is an optimal solution of the linear
programming problem

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


Does your conclusion remain the same if the objective is changed
to

$$\textrm{maximize }z'=10x_1-12x_2+22x_3+x_4$$

but the constraints are unaltered?

\item[(c)]
Consider a linear programming problem having constraints of the
form

\begin{center}
\begin{tabular}{ll}
$x_j \geq 0$&for $i=1,\ldots,n$\\
$\displaystyle\sum\limits^n_{j=1} a_{ij}x_j = b_i$& for
$i=1,2$.
\end{tabular}
\end{center}


An alternative linear programming problem is identical, except
that the last constraint is replaced by

$$\sum_{j=1}^n(a_{ij}+a_{2j})x_j=b_1+b_2$$

i.e., the first equation is added to the second, which yields an
equivalent problem. Given that these two linear programming
problems have optimal solutions, analyze how the optimal values of
the dual variables of the two problems are related.

\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}\geq0,\mathbf{s}\geq\mathbf{0}$&subject
to&$\mathbf{y}\geq\mathbf{0},\mathbf{t}\geq\mathbf{0}$\\
&$A\mathbf{x}+\mathbf{s}=\mathbf{b}$&
&$A^T\mathbf{y}-\mathbf{t}=\mathbf{c}$
\end{tabular}

For optimal solutions, 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 the dual, we have
$c_j=1,\ldots,n$

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

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

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

Since variables are non-negative this implies that

\begin{eqnarray*}
y_is_i&=&0\ i=1,\ldots,m\\ t_jx_j&=&0\ j=1,\ldots,n
\end{eqnarray*}

\item[(b)]
If $s_1,s_2$ are slack variables for the first two constraints
then $s_1=0,\ s_2=1$ for the proposed solution.

The dual problem is

\begin{tabular}{ll}
minimize&$z_d=16y_1+24y_2+16y_3$\\ subject to
&$y_1\geq0,y_2\geq0$\\ &$4y_1+5y_2+2y_3-t_1=10$\\
&$-3y_1+6y_2+2y_3-t_2=-13$\\ &$7y_1+y_2-3y_3-t_3=25$\\
$2y_1+4y_2+5y_3-t_4=1$
\end{tabular}

for slack variables $t_1\geq0,\ t_2\geq0,\ t_3\geq0,\ t_4\geq0$.

If the proposed solution is optimal, then we can use complementary
slackness to obtain

$$t_1=0,\ t_4=0,\ y_2=0$$

The first and last dual constraints become

\begin{eqnarray*}
4y_1+2y_3&=&10\\ 2y_1+5y_3&=&1
\end{eqnarray*}

Solving yields $y_1=3,\ y_3=-1$ and we obtain $t_2=2,t_3=-1$.

We require that $t_3\geq0$, so the solution is not optimal.

For the modified objective, computations are the same, except that
$t_2=1,t_3=2$, so the dual solution is feasible.

Since $z=32=z_D$, both solutions are optimal.

\item[(c)]
Let the rows of the two original constraints be $\mathbf{a}_1T,\
\mathbf{a}_2^T$.

The original problem is of the form

\begin{tabular}{ll}
Maximize&$\mathbf{c}^T\mathbf{x}$\\ subject
to&$\mathbf{a}_1^T\mathbf{x}=b_1$\\
&$\mathbf{a}_2^T\mathbf{x}=b_2\ \mathbf{x}\geq0$
\end{tabular}

The dual is

\begin{tabular}{ll}
Minimize&$b_1y_1+b_2y_2$\\ subject
to&$\left(\begin{array}{cc}a_1&a_2\end{array}\right)\left(
\begin{array}{c}y_1\\y_2\end{array}\right)\geq\mathbf{c}$
\end{tabular}

The dual of the alternative problem is

\begin{tabular}{ll}
Minimize&$b_1y_1'+(b_1+b_2)y_2'$\\ subject
to&$\left(\begin{array}{cc}\mathbf{a}_1&\mathbf{a}_1+\mathbf{a}_2
\end{array}\right)\left(\begin{array}{c}y_1'\\y_2'\end{array}\right) \geq\mathbf{c}$
\end{tabular}

Clearly the values $y_2'=y_2\ y_1'=y_1-y_2$ give the same
objective function value and left-hand side of the constraints

\end{description}



\end{document}