A3.10

Algorithms and Networks
Part II, 2002

(i) Consider the unconstrained geometric programme GP

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

subject to tj>0j=1,,mt_{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,DA, B, C, D and EE. The fares for direct flights between these cities are as follows:

\begin{tabular}{l|lllll} & A\mathrm{A} & B\mathrm{B} & C\mathrm{C} & D\mathrm{D} & E\mathrm{E} \ \hline A\mathrm{A} & - & 50 & 40 & 25 & 10 \  B\mathrm{~B} & 50 & - & 20 & 90 & 25 \ C\mathrm{C} & 40 & 20 & - & 10 & 25 \ D\mathrm{D} & 25 & 90 & 10 & - & 55 \ E\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 DD and each of the other cities.