A3.10
(i) Consider the unconstrained geometric programme GP
subject to .
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 and . The fares for direct flights between these cities are as follows:
\begin{tabular}{l|lllll} & & & & & \ \hline & & 50 & 40 & 25 & 10 \ & 50 & & 20 & 90 & 25 \ & 40 & 20 & & 10 & 25 \ & 25 & 90 & 10 & & 55 \ & 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 and each of the other cities.