Optimization

The Shortest Path

Consider a line \( L \) with the equation:

\[ a x + b y + c = 0 \]

Suppose there are two points \( A \) and \( B \) on the same side of line \( L \). We wish to find a point \( P \) on line \( L \) such that the total distance \( AP + PB \) is minimized. In simple words, we want to find the location of \( P \) on \( L \) such that the path from \( A \) to \( B \) via \( P \) is the shortest.

Theorem: Given a line \( L: a x + b y + c = 0 \) and two points \( A \) and \( B \) on the same side of \( L \), the point \( P \) on \( L \) that minimizes the total distance \( AP + PB \) is the intersection of \( L \) with the line segment joining \( A \) and the reflection \( B' \) of \( B \) across \( L \).

Proof:

Suppose \( P \) is somewhere on the line \( L \). Take the reflection \( B' \) of \( B \) in the line \( L \). Join \( AB' \) and \( PB' \). By symmetry, \( PB = PB' \).

Now, in triangle \( \Delta APB' \), by the triangle inequality:

\[ AP + PB' \geq AB' \]

Since \( PB = PB' \), we have:

\[ AP + PB \geq AB' \]

The equality holds when points \( A \), \( P \), and \( B' \) are collinear. Thus, the minimum value of \( AP + PB \) is achieved when \( P \) is the intersection of line \( L \) and line \( AB' \).

Therefore, the point \( P \) that minimizes the total distance \( AP + PB \) is the intersection of line \( L \) with the line segment \( AB' \), where \( B' \) is the reflection of \( B \) across \( L \).

Hence, the optimal point \( P \) on line \( L \) is the intersection of \( L \) and the line joining \( A \) and the reflection \( B' \) of \( B \).

Fermat's Principle:

Fermat's principle states that the path taken by a ray of light between two points is the one that can be traversed in the least time.

If a ray of light starts from point \( A \) and strikes a mirror \( L \) at point \( P \) to reach point \( B \), then point \( P \) is such that the total distance \( AP + PB \) is minimized. Thus, to minimize \( AP + PB \), we follow the path of light, ensuring it adheres to Fermat's principle of least time. This means the angles of incidence and reflection are equal, confirming that the path taken is indeed the shortest.

Two Mirrors

Consider two lines \(L_1\) and \(L_2\) intersecting at an acute angle. Let points \(A\) and \(B\) lie in the acute region formed by \(L_1\) and \(L_2\). We aim to determine the points \(M\) on \(L_1\) and \(N\) on \(L_2\) such that the total path length \(AM + MN + NB\) is minimized. This is equivalent to finding the shortest path from \(A\) to \(B\) via points \(M\) on \(L_1\) and \(N\) on \(L_2\).

To achieve this, we trace the path of light, which follows the principle of reflection. Reflect point \(A\) across line \(L_1\) to obtain its image \(A'\). Similarly, reflect point \(B\) across line \(L_2\) to obtain its image \(B'\). Draw a straight line connecting \(A'\) and \(B'\). This line intersects \(L_1\) at point \(M\) and \(L_2\) at point \(N\).

Thus, the points \(M\) and \(N\) where the line segment \(A'B'\) intersects \(L_1\) and \(L_2\), respectively, are the optimal locations that minimize the total path length \(AM + MN + NB\).

Example

Given lines \(L_1: 2x - y = 0\) and \(L_2: y = 0\), and points \(A = (5, 5)\) and \(B = (10, 1)\), find the points \(M\) on \(L_1\) and \(N\) on \(L_2\) such that the path \(AM + MN + NB\) is minimized.

Solution:

First, find the reflection \(A'\) of \(A(5, 5)\) in \(L_1: 2x - y = 0\).

\[ \begin{aligned} \frac{x - 5}{2} &= \frac{y - 5}{-1} = -\frac{2(5)}{5} = -2 \\ \implies x - 5 &= 2(-2) = -4 \implies x = 1 \\ \implies y - 5 &= -1(-2) = 2 \implies y = 7 \\ \implies A' &= (1, 7) \end{aligned} \]

Next, find the image \(B'\) of \(B(10, 1)\) in \(L_2: y = 0\). The reflection of \((10, 1)\) across \(y = 0\) is \((10, -1)\), so \(B' = (10, -1)\).

Equation of \(A'B'\):

Using points \(A'(1, 7)\) and \(B'(10, -1)\), the slope \(m\) of the line \(A'B'\) is:

\[ \begin{aligned} m &= \frac{-1 - 7}{10 - 1} = \frac{-8}{9} \\ \implies y - 7 &= -\frac{8}{9}(x - 1) \\ 9(y - 7) &= -8(x - 1) \\ \implies 9y - 63 &= -8x + 8 \\ \implies 8x + 9y &= 71 \end{aligned} \]

Finding \(M\):

\(M\) is the intersection of \(A'B'\) and \(L_1: y = 2x\). Substituting \(y = 2x\) into \(8x + 9y = 71\):

\[ \begin{aligned} 8x + 9(2x) &= 71 \\ \implies 8x + 18x &= 71 \\ \implies 26x &= 71 \\ \implies x &= \frac{71}{26} \\ \implies y &= 2x = \frac{71}{13} \\ \implies M &= \left(\frac{71}{26}, \frac{71}{13}\right) \end{aligned} \]

Finding \(N\):

\(N\) is the intersection of \(A'B'\) and \(L_2: y = 0\). Substituting \(y = 0\) into \(8x + 9y = 71\):

\[ \begin{aligned} 8x &= 71 \\ \implies x &= \frac{71}{8} \\ \implies N &= \left(\frac{71}{8}, 0\right) \end{aligned} \]

Therefore, the points \(M\) and \(N\) that minimize the path \(AM + MN + NB\) are \(M = \left(\frac{71}{26}, \frac{71}{13}\right)\) and \(N = \left(\frac{71}{8}, 0\right)\).

Given points \(A\) and \(B\) on the \(x\)-axis and line \(y = 2x\) respectively, such that the perimeter of triangle \(ABC\) with \(C(3, 4)\) is minimized.

Solution:

We follow the light path. A ray of light starting from \(C\) and coming back to \(C\) after reflection from the \(x\)-axis and \(y = 2x\).

Step 1: Find the images of \(C\)

The image of \(C\) in the \(x\)-axis is \(C'(3, -4)\).

For the image of \(C\) in \(y = 2x\), we use the reflection formula:

\[ \frac{x - 3}{2} = \frac{y - 4}{-1} = -\frac{2(6 - 4)}{5} = -\frac{4}{5} \]

\[ \implies x - 3 = 2\left(-\frac{4}{5}\right) = -\frac{8}{5} \implies x = \frac{7}{5} \]

\[ \implies y - 4 = -\left(-\frac{4}{5}\right) = \frac{4}{5} \implies y = \frac{24}{5} \]

Thus, the image \(C''\) is \(\left(\frac{7}{5}, \frac{24}{5}\right)\).

Step 2: Equation of the line joining \(C'\) and \(C''\)

Using points \(C'(3, -4)\) and \(C''\left(\frac{7}{5}, \frac{24}{5}\right)\), the slope \(m\) is:

\[ m = \frac{\frac{24}{5} + 4}{\frac{7}{5} - 3} = \frac{\frac{24}{5} + \frac{20}{5}}{\frac{7}{5} - \frac{15}{5}} = \frac{\frac{44}{5}}{-\frac{8}{5}} = -\frac{11}{2} \]

Thus, the equation of the line is:

\[ \frac{y + 4}{x - 3} = -\frac{11}{2} \]

\[ \implies 2(y + 4) = -11(x - 3) \]

\[ \implies 2y + 8 = -11x + 33 \]

\[ \implies 11x + 2y = 25 \]

Step 3: Find intersection points \(A\) and \(B\)

For \(A\) on the \(x\)-axis (\(y = 0\)):

\[ 11x + 2(0) = 25 \]

\[ \implies x = \frac{25}{11} \implies A = \left(\frac{25}{11}, 0\right) \]

For \(B\) on the line \(y = 2x\):

\[ 11x + 2(2x) = 25 \]

\[ \implies 11x + 4x = 25 \]

\[ \implies 15x = 25 \]

\[ \implies x = \frac{5}{3} \implies y = 2x = \frac{10}{3} \]

Thus, \(B = \left(\frac{5}{3}, \frac{10}{3}\right)\).

Therefore, the points \(A\) and \(B\) that minimize the perimeter of triangle \(ABC\) are \(A = \left(\frac{25}{11}, 0\right)\) and \(B = \left(\frac{5}{3}, \frac{10}{3}\right)\).