\documentclass[a4paper,12pt]{article}

\begin{document}

\parindent=0pt

QUESTION

\begin{description}

\item[(a)]
Explain two approaches by which linear programming is used to
tackle multi-objective linear programming problems.

\item[(b)]
Describe three alternative pivoting rules in linear programming,
and state the situations for which they are most appropriate.

\item[(c)]
From given observations $(x_1,y_1),\ldots,(x_n,y_n)$, it is
required to find values of $a$ and $b$ to be used in the linear
model $y=ax+b$. The values of $a$ and $b$ are to be chosen so that
$$\sum^n_{i=1} |y_i - ax_i - b|$$ is minimized.  Give a linear
programming formulation of this problem.


\item[(d)]
Solve the following linear programming problem using the dual
simplex method.

\begin{tabular}{ll}
 Minimize&$z = 15x_1
+ 6 x_2 + 22x_3$\\ subject to&$x_1 \geq 0$, $x_2 \geq 0$, $x_3
\geq 0$\\&$5x_1 + 2x_2 + 7x_3 \geq 7 $\\&$6x_1 + 3x_2 + 5x_3  \geq
9$.
\end{tabular}

Find all other optimal solutions.

\end{description}

ANSWER


\begin{description}

\item[(a)]
If $z_1,\ldots,z_r$ are the objective functions to be maximised,
one approach is to minimize the composite objective

$$\alpha_1z_1+\ldots+\alpha_rz_r$$

for suitable weights $\alpha_1,\ldots,\alpha_r$.

Another approach is to evaluate the trade-offs by maximizeing$z_1$
subject to $z_2\geq k_2,\ldots z_r\geq k_r$ for varying values of
the constants $k_2,\ldots,k_r$.

\item[(b)]

\begin{itemize}

\item
The standard pivoting rule is to select a pivot column with the
smallest (negative) objective coefficient.

\item
Bland's smallest subscript rule chooses the pivot column so that
the entering variable has the smallest subscript amoung candidates
with a negative objective coefficient. If there is a choice (equal
ratios) the leaving variable is chosen so that it has the smallest
subscript. This rule is used to avoid cycling in degenerate
problems.

\item
The largest increase pivoting rule chooses a pivot column so that
the corresponding pivot element gives the largest increase in the
objective function. This helps to overcome badly scaled variables.

\end{itemize}

\item[(c)]

\begin{tabular}{ll}
Minimize&$z=u_1+v_1+\ldots+u_n+v_n$\\ subject to&$u_0\geq0,\ldots
u_n\geq0$\\ &$v_1\geq0,\ldots,v_n\geq0$\\ &$ax_1+b+u_1-v_i=y_1$\\
&\vdots\\ &$ax_n+b+u_n-v_n=y_n$
\end{tabular}

\item[(d)]
Introduce slack variables $s_1\geq0,\ s_2\geq0$, and maximize
$z'=z$

\begin{tabular}{c|cccccc|c}
Basic&$z'$&$x_1$&$x_2$&$x_3$&$s_1$&$s_2$&\\ \hline
$s_1$&0&$-5$&$-2$&$-7$&1&0&$-7$\\
$s_2$&0&$-6$&$-3$&$-5$&0&1&$-9$\\ \hline &1&15&6&22&0&0&0\\
Ratio&&$\frac{5}{2}$&2&$\frac{22}{5}$\\
\end{tabular}

\begin{tabular}{c|cccccc|c}
Basic&$z'$&$x_1$&$x_2$&$x_3$&$s_1$&$s_2$&\\ \hline
$s_1$&0&$-1$&0&$-\frac{11}{3}$&1&$-\frac{2}{3}$&$-1$\\
$x_2$&0&2&1&$\frac{5}{3}$*0&$-\frac{1}{3}$&3\\ \hline
&1&3&0&12&0&2&$-18$\\ Ratio&&3&&$\frac{36}{5}$&&3
\end{tabular}

\begin{tabular}{c|cccccc|c}
Basic&$z'$&$x_1$&$x_2$&$x_3$&$s_1$&$s_2$&\\ \hline
$x_1$&0&1&0&$\frac{11}{3}$&$-1$&$\frac{2}{3}$&1\\
$x_2$&0&0&1&$-\frac{17}{3}$&2&$-\frac{5}{3}$&1\\ \hline
&1&0&0&1&3&0&$-21$
\end{tabular}

Optimal solution is $x_1=1,\ x_2=1,\ x_3=0,\ z=21$. To obtain an
alternative optimal solution, perform an ordinary simplex
iteration.


\begin{tabular}{c|cccccc|c}
Basic&$z'$&$x_1$&$x_2$&$x_3$&$s_1$&$s_2$&\\\hline
$s_2$&0&$\frac{3}{2}$&0&$\frac{11}{2}$&$-\frac{3}{2}$&1&$\frac{3}{2}$\\
$x_2$&0&$\frac{5}{2}$&1&$\frac{7}{2}$&$-\frac{1}{2}$&0&$\frac{7}{2}$\\
\hline &1&0&0&1&3&0&$-21$
\end{tabular}

An alternative optimal solution is $x_1=0,\ x_2=\frac{7}{2},\
x_3=0,\ z=21$

Any optimal solution is of the form

$$(x_1,x_2,x_3)=\lambda(1,1,0)+(1-\lambda)(0,\frac{7}{2},0)$$

for $0\leq\lambda\leq1$.

\end{description}




\end{document}