A4.11

Algorithms and Networks
Part II, 2004

(i) Consider an unrestricted geometric programming problem

ming(t),t=(t1,,tm)>0,\min g(t), \quad t=\left(t_{1}, \ldots, t_{m}\right)>0,

where g(t)g(t) is given by

g(t)=i=1ncit1ai1tmaimg(t)=\sum_{i=1}^{n} c_{i} t_{1}^{a_{i 1}} \ldots t_{m}^{a_{i m}}

with nmn \geq m and positive coefficients c1,cnc_{1} \ldots, c_{n}. State the dual problem of ()(*) and show that if λ=(λ1,,λn)\lambda^{*}=\left(\lambda_{1}^{*}, \ldots, \lambda_{n}^{*}\right) is a dual optimum then any positive solution to the system

t1ai1tmaim=1ciλiv(λ),i=1,,n,t_{1}^{a_{i 1}} \ldots t_{m}^{a_{i m}}=\frac{1}{c_{i}} \lambda_{i}^{*} v\left(\lambda^{*}\right), \quad i=1, \ldots, n,

gives an optimum for primal problem ()(*). Here v(λ)v(\lambda) is the dual objective function.

(ii) An amount of ore has to be moved from a pit in an open rectangular skip which is to be ordered from a supplier.

The skip cost is £36£ 36 per 1 m21 \mathrm{~m}^{2} for the bottom and two side walls and £18£ 18 per 1 m21 \mathrm{~m}^{2} for the front and the back walls. The cost of loading ore into the skip is £3£ 3 per 1 m31 \mathrm{~m}^{3}, the cost of lifting is £2£ 2 per 1 m31 \mathrm{~m}^{3}, and the cost of unloading is £1£ 1 per 1 m31 \mathrm{~m}^{3}. The cost of moving an empty skip is negligible.

Write down an unconstrained geometric programming problem for the optimal size (length, width, height) of skip minimizing the cost of moving 48 m348 \mathrm{~m}^{3} of ore. By considering the dual problem, or otherwise, find the optimal cost and the optimal size of the skip.