\documentclass[a4paper,12pt]{article}

\begin{document}

\parindent=0pt

QUESTION

\begin{description}

\item[(a)]
Consider the linear programming problem

\begin{center}
\begin{tabular}{lll}
maximize&$z_P=\sum\limits^n_{j=1} c_jx_j$\\subject to&$x_j \geq
0$&$j=1,\ldots,n$\\&$\sum\limits^n_{j=1} a_{ij}x_j \le
b_i$&$i=1,\ldots,m.$
\end{tabular}
\end{center}

\vskip 0.05 in

Write down the dual problem.  If the original problem has an
optimal solution, what can you say about the optimal value of the
dual objective?  Prove your result.


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

\begin{tabular}{ll}
maximize&$z = 11x_1 +2x_2 +22x_3+24x_4$\\subject to&$x_1 \geq 0$,
$x_2 \geq 0$, $x_3 \geq 0$, $x_4 \geq 0$\\&$8x_1 + 4x_2 + 7x_3 -
6x_4 \leq 20 $\\&$5x_1 + 2x_2 + 3x_3 + 5x_4 = 24 $\\&$6x_1 + 3x_2
- 4x_3 - 2x_4  = 17$.
\end{tabular}


Analyze whether your conclusion remains the same if the objective
is changed to minimize $z$ instead of maximize $z$.

\end{description}

ANSWER


\begin{description}

\item[(a)]
Dual is

\begin{tabular}{ll} minimize&$Z_D=\sum_{i=1}^mb_iy_i$\\
subject to&$y_i\geq0\ i=1,\ldots,m$\\ &$\sum_{i=1}^ma_{ij}y_i\geq
c_j\ j=\,\ldots n$
\end{tabular}

The duality theorem states that $max\ z_P=min\ z_D$ if the
original problem has an optimal solution.

Using matrix notation, the original problem is

\begin{tabular}{ll}
maximize&$z_P=\mathbf{c}^T\mathbf{x}$\\ subject
to&$A\mathbf{x}\leq\mathbf{b},\ \mathbf{x}\geq\mathbf{0}$
\end{tabular}

where $s$ is a vector of slack variables and the dual is

\begin{tabular}{ll}
minimize&$z_D=\mathbf{b}^T\mathbf{y}$\\ subject to
&$A^T\mathbf{y}\geq\mathbf{c},\ \mathbf{y}\geq\mathbf{0}$
\end{tabular}

Let the $Z_P$ row for the final simplex table for the original
problem be

$$z_P+\mathbf{\overline{c}}^T\mathbf{x}+\mathbf{\overline{d}}^T\mathbf{s}=z*$$

where $\mathbf{\overline{c}}\geq\mathbf{0}$ and
$\mathbf{\overline{d}}\geq\mathbf{0}$. Clearly it must be obtained
from the original row $z_P\ \mathbf{c}^T\mathbf{x}=0$ by adding $
\mathbf{d}^T(A\mathbf{x}+\mathbf{s}-\mathbf{b})$ to give

$$z_P+(-\mathbf{c}^T+\mathbf{d}^TA)\mathbf{x}+\mathbf{d}^T\mathbf{s}=\mathbf{d}^T\mathbf{b}$$

Thus

$$z*=\mathbf{d}^T\mathbf{b}$$

and

$$\mathbf{\overline{c}}^T=-\mathbf{c}^T+\mathbf{d}^TA$$

Transposing gives

$$\mathbf{\overline{c}}+\mathbf{c}\ A^T\mathbf{d}$$

Consider the dual solution $\mathbf{y}=\mathbf{d}\ge q\mathbf{0}$.
It is feasible because

$$A^T\mathbf{y}=A^T\mathbf{d}=\mathbf{c}+\mathbf{\overline{c}}\geq\mathbf{c}$$

since $\mathbf{\overline{c}}\geq\mathbf{0}$.

Also
$$z_P=\mathbf{c}^T\mathbf{x}\leq\mathbf{y}^TA\mathbf{x}\leq\mathbf{y}^T\mathbf{b}=\mathbf{b}^T\mathbf{y}=z_D$$

for any feasible solutions $\mathbf{x}$ and $\mathbf{y}$. Thus if
feasible solutions yield $z_P=z_D$, they must be optimal.

\item[(b)]
For the proposed solution, $z=62\ s_1=4$ where $s_1$ is the slack
variable for the first constraint.

The dual problem is

\begin{tabular}{ll}
minimize&$z_D=20y_1+24y_2+17y_3$\\ subject to&$y_1\geq0$\\
&$8y_1+5y_2+6y_3-t_1=11$\\ &$4y_1+2y_2+3y_3-t_2=2$\\
&$7y_1+3y_2-4y_3-t_3=22$\\ &$-6y_1+5y_2-2y_3-t_4=24$
\end{tabular}

where $t_1\geq0,\ t_2\geq0,\ t_3\geq0,\ t_4\geq0$ are slack
variables.

Using complementary slackness, $y_1=0,\ t_2=0,\ t_4=0$

\begin{eqnarray*}
2y_2+3y_3&=&2\\ 5y_2-2y_3&=&24\\
\end{eqnarray*}

$y_2=4,\ y_3=-2$.

This yields $t_1=-3,\ t_3=-2$ so the solution is not optimal.

The minimize objective can be represented as

$$\textrm{minimize }z'=-11x_1-2x_2-22x_3-24x_4$$

so the $z'=-62$ for the proposed solution.

The dual is the same except that the right hand sides of the
constraints change sides. Complementary slackness yields the same
values, so

\begin{eqnarray*}
2y_2+3y_3&=&-2\\ 5y_2-2y_3&=&-24
\end{eqnarray*}

This yields $y_2=-4,\ y_3=2,\ t_1=3,\ t_3=2$.

Since $z_D=-62=z'$, we have an optimal solution.

\end{description}





\end{document}