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

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

\item[(c)]
For the linear programming problem

\begin{tabular}{lll}
 maximize&$\sum^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 \leq b_i$&$i=1,\ldots,m$,
\end{tabular}

the optimal value of the objective function is $z^*$ and
$y_1^*,\ldots,y_m^*$ are optimal values of the dual variables. Let
$z^{**}$ denote the optimal value of the objective function for
the linear programming problem

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

$$z^{**} \le z^* + \sum^m_{i=1} \delta_iy^*_i.$$

You may use the Duality Theorem in your proof.

\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{center}
\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{0},\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}
\end{center}

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}^Tx=z_D-\mathbf{y}^T\mathbf{s}-\mathbf{t}^T\mathbf{x}$$

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

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

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

\item[(b)]
The solution $x_1=0,\ x_2=1,\ x_3=0,\ x_4=4$ yeilds $z=37\ s_1=3,\
s_2=0$.

The dual problem is

\begin{tabular}{ll}
minimize&$z_D=15y_1+18y_2+17y_3$\\ subject to &$y_1\geq0,\
y_2\geq0,$\\ &$6y_1+3y_2+5y_3\geq4$\\ &$8y_1+3y_2+5y_3\geq1$\\
$3y_1+7y_2+8y_3\geq7$\\ &$y_1+4y_2+3y_3\geq9$
\end{tabular}

If the given solution is optimal, then we can use the
complementary slackness conditions.

$y_1s_1=0$ implies $y_1=0$

$x_2t_2=0$ implies $t_2=0$

$x_4t_4=0$ implies $t_4=0$

Thus,

\begin{eqnarray*}
2y_2+5y_3&=&1\\ 4y_2+3y_3&=&9
\end{eqnarray*}

so

$$y_2=3,\ y_3=-1$$

and

$$t_1=0,\ t_3=6$$

Therefore, the solution is feasible.

Since $z_D=37=z$ the proposed solution is optimal.

\item[(c)]
Using matrix notation, the relevant problems are

\begin{tabular}{llllll}
(P)&Maximize&$\mathbf{c}^T\mathbf{x}$&(P)&Maximize&$\mathbf{c}^T\mathbf{x}$\\
&subject to&$\mathbf{x}\geq0$&&subject
to&$\mathbf{x}\geq\mathbf{0}$\\
&&$A\mathbf{x}\leq\mathbf{b}$&&&$A\mathbf{x}\leq\mathbf{b}+\mathbf{\delta}$
\end{tabular}

and the dual of (P) is

\begin{tabular}{lll}
(D)&Minimize&$\mathbf{b}^T\mathbf{y}$\\ &subject
to&$\mathbf{y}\geq\mathbf{0}$\\ &&$A^T\mathbf{y}\geq\mathbf{c}$
\end{tabular}

From the duality theorem,

$$z*=\mathbf{b}^T\mathbf{y}*=(\mathbf{y}*)\mathbf{b}$$

Let $\mathbf{x}=\mathbf{x}*$ be an optimal solution of (P'). Then

$$x**=\mathbf{c}^T\mathbf{x}*\leq(y*)^TAx*\leq(y*)^T(\mathbf{b}+
\mathbf{\delta})=z*+\sum_{i=1}^ms_iy_i*$$

\end{description}




\end{document}