1
$\begingroup$

A power house, $P$, is on one bank of a straight river $W$ meters (m) wide, and a factory, $F$, is on the opposite bank $L$ meters downstream from $P$. The cable has to be taken across the river, under water at a cost of $\$CW/\mathrm{m}$. On land the cost is $\$CL/\mathrm{m}$. What is the minimum cost?

Any help will be appreciated...

$\endgroup$
  • $\begingroup$ One way can be also: L*CL+W*\sqrt{(CW^2-CL^2)} $\endgroup$ – marchetto Feb 12 '14 at 12:35
1
$\begingroup$

Set this up as a non linear programming problem.

1.Variables:

$x_L=$the meters of cable to be used on land, $x_W=$the meters of cable to be used under water

2.Objective Function: You want to minimize the total cost that is $$z=\min_{x_L,x_W}CL\cdot x_L + CW \cdot x_W$$

3.Restrictions $$L^2+W^2=x_{L}^2+x_{W}^2-2x_Lx_w\cos(\gamma)$$ where $\gamma$ is the angle between the sides $x_L$ and $x_W$. The explanation of this condition is the following. You have a triangle with edges $P$, $F$ and another edge, say $D$ at the point where your cable meets the coast where $F$ is. Now, consider the right angle triangle with sides $W$, $L$ and $\sqrt{L^2+W^2}$. (Do you see it?). Begin to move edge $D$ towards $F$. The new triangle(s) has(ve) not sides $W$, $L$ and $\sqrt{L^2+W^2}$ anymore, but $x_W$, $x_L$ and $\sqrt{L^2+W^2}$ instead. The side that remains unaffected is the straight line between $P$ and $F$.

Note now that you have also an angle that is constant and can be determined. Consider the following description. As already mentioned, you have a staight line (the hypotenuse) from P to F. The length of this diagonal is equal to $L^2+W^2$ due to Pythagoras law (draw a shape). Then you can move along the coast and reduce $x_L$ but increase $x_W$. Note though, that the angle between the coast line (where F is) and the diagonal remains unaffected. Call this angle $\alpha$. In the right angle triangle with sides $W$, $L$ and $\sqrt{L^2+W^2}$ we can easily calculate $\alpha$, since $\sin(\alpha)=\frac{W}{\sqrt{L^2+W^2}}$. Then the law of sines implies that $$\frac{\sqrt{L^2+W^2}}{\sin(\gamma)}=\frac{x_W}{\sin(\alpha)}$$ Solving for $\sin(\gamma)$ and by substituting we find that $$\sin(\gamma)=\frac{W}{x_W}.$$ Therefore $$\cos(\gamma)=\sqrt{1-\sin^2(\gamma)}=\sqrt{1-\frac{W^2}{x_W^2}}.$$ So you have the nonlinear restriction

(1) $L^2+W^2=x_{L}^2+x_{W}^2-2x_Lx_w\sqrt{1-\frac{W^2}{x_W^2}}$

and the restrictions:

(2) $x_L \ge 0$ (nonnegativity condition)

(3) $x_W \ge W$ (you have to cross the river)

To sum up: $$z=\min_{x_L,x_W}CL\cdot x_L + CW \cdot x_W$$ under the restrictions

(1) $L^2+W^2=x_{L}^2+x_{W}^2-2x_Lx_w\sqrt{1-\frac{W^2}{x_W^2}}$

(2) $x_L \ge 0, \, x_W \ge W$

Now use Excel NLP solver to solve it, or KKT conditions if you have the time.

$\endgroup$
1
$\begingroup$

There are two ways of routing the cable -

  1. Completely through water (if CW is not too high than CL) and
  2. Maximum by land and then only the width of the river by water (if CW is too high than CL).

The costs are respectively C1= {(L^2+W^2)^.5}*CW {using pythagorus theorem} and C2= (CW*W + CL*L)

Hence, minimum cost = Min(C1,C2).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.