(i) Consider the unconstrained geometric programme GP

$$\text { minimise } g(t)=\sum_{i=1}^{n} c_{i} \prod_{j=1}^{m} t_{j}^{a_{i j}}$$

subject to $t_{j}>0 \quad j=1, \ldots, m$.

State the dual problem to GP. Give a careful statement of the AM-GM inequality, and use it to prove the primal-dual inequality for GP.

(ii) Define min-path and max-tension problems. State and outline the proof of the max-tension min-path theorem.

A company has branches in five cities $A, B, C, D$ and $E$. The fares for direct flights between these cities are as follows:

\begin{tabular}{l|lllll} & $\mathrm{A}$ & $\mathrm{B}$ & $\mathrm{C}$ & $\mathrm{D}$ & $\mathrm{E}$ \ \hline $\mathrm{A}$ & $-$ & 50 & 40 & 25 & 10 \ $\mathrm{~B}$ & 50 & $-$ & 20 & 90 & 25 \ $\mathrm{C}$ & 40 & 20 & $-$ & 10 & 25 \ $\mathrm{D}$ & 25 & 90 & 10 & $-$ & 55 \ $\mathrm{E}$ & 10 & 25 & 25 & 55 & $-$ \end{tabular}

Formulate this as a min-path problem. Illustrate the max-tension min-path algorithm by finding the cost of travelling by the cheapest routes between $D$ and each of the other cities.