Skip to main content

Chapter 8 Linear Systems

Squirrel eating: Adam Jones/Photo Researchers, Inc.

Linear programming is an application of linear systems developed in the 1940s to solve complex optimization problems during wartime operations. Today, linear programming is used in scheduling and allocation of resources, in shipping and telecommunications networks, and in the selection of stocks and bonds for portfolios. In 1980, the computer scientist Laszlo Lovasz said, “If one would take statistics about which mathematical problem is using up most of the computer time in the world, ... the answer would probably be linear programming.”

George Dantzig (1914–2005) invented the simplex method for solving linear programming problems in 1947. His first application of the method was to determine an adequate diet of least cost. This problem involved 9 equations in 77 unknowns and took 120 days to solve using the desk calculators available at the time.

In this chapter, we use a graphing technique to solve problems in two unknowns. For example, the diet of the Columbian ground squirrel consists of two foods: grass and forb (a type of flowering weed). Small animals spend most of their time foraging for food, but they must also be alert for predators. Which foraging strategy favors survival: Should the squirrel try to satisfy its dietary requirements in minimum time, thus minimizing its exposure to predators and the elements, or should it try to maximize its intake of nutrients?

feasible set with different times
feasible set with different energy consumed

Using linear programming, Gary Belovsky of Notre Dame University identified the optimal amounts of forb and grass for each foraging strategy. We can compare those solutions to the squirrel's actual diet to see which strategy the squirrel favors.

Investigation 8.1 Interpolating Polynomials

In Chapter 6, we learned to fit a quadratic function through three points on its graph. A polynomial whose graph passes through a given set of points is called an interpolating polynomial. Because polynomials are easy to evaluate and manipulate, they are often used to approximate more complicated functions and to describe the shapes of curves.

In this Investigation, we find interpolating polynomials of degrees \(1\text{,}\) \(2\text{,}\) and \(3\) to approximate the function \(f(x) = \dfrac{12}{x}\text{.}\)

    1. Graph the function \(f(x) = \dfrac{12}{x}\) in the window

      \begin{align*} \text{Xmin} \amp = -2 \amp\amp \text{Xmax} = 7.4\\ \text{Ymin} \amp = -5 \amp\amp \text{Ymax} = 20 \end{align*}
    2. Complete the table of values.

      \(x\) \(1\) \(2\) \(3\) \(4\) \(5\) \(6\)
      \(f(x)\) \(\hphantom{0000}\) \(\hphantom{0000}\) \(\hphantom{0000}\) \(\hphantom{0000}\) \(\hphantom{0000}\) \(\hphantom{0000}\)
  1. First we will find a linear polynomial \(P_1(x) = ax + b\) that matches \(f(x)\) at \(x = 1\) and \(x=6\text{.}\) We must find constants \(a\) and \(b\) so that \(P_1(1) = f(1)\) and \(P_1(6) = f(6)\text{.}\)

    1. The two conditions above translate into equations about \(a\) and \(b\text{.}\) The constants \(a\) and \(b\) must satisfy the system

      \begin{align*} a \cdot 1 + b \amp = f (1)\\ a \cdot 6 + b \amp = f (6) \end{align*}

      Solve the system and find the polynomial \(P_1(x)\text{.}\)

    2. Graph \(P_1(x)\) in the same window with \(f(x)\text{.}\)

  2. Next, we will find a quadratic polynomial \(P_2(x) = ax^2 + bx + c\) that matches \(f(x)\) at \(x = 1\text{,}\) \(2.5\text{,}\) and \(6\text{.}\)

    1. Write and solve a system of equations for the constants \(a\text{,}\) \(b\text{,}\) and \(c\text{.}\)

    2. Graph \(P_2(x)\) in the same window with \(f(x)\text{.}\)

  3. We can also find a cubic polynomial \(P_3(x) = ax^3 + bx^2 + cx + d\) that matches \(f(x)\) at \(x = 1\text{,}\) \(3\text{,}\) \(4\text{,}\) and \(6\text{.}\)

    1. Write a system of equations for \(a\text{,}\) \(b\text{,}\) \(c\text{,}\) and \(d\text{.}\) We will see how to solve such a system later in this chapter. For now, we will use the calculator's cubic regression feature.

    2. Enter the coordinates of \(P_3(x)\) evaluated at \(x=1\text{,}\) \(3\text{,}\) \(4\text{,}\) and \(6\) into \(L_1\) and \(L_2\) under the STAT EDIT menu. Then, from the STAT CALC menu, choose 6: CubicReg and press ENTER.

    3. Graph \(P_3(x)\) in the same window with \(f(x)\text{.}\)

  4. How well does each interpolating polynomial approximate the function \(f(x)\text{?}\) Graph the "error function," \(E_n(x)\text{,}\) for each polynomial on the interval \([-2, 7.4]\text{.}\)

    \begin{align*} E_1(x) \amp = f(x) - P_1(x)\\ E_2(x) \amp = f(x) - P_2(x)\\ E_3(x) \amp = f(x) - P_3(x) \end{align*}

    (You will have to choose a suitable \(y\)-window for each error function.) What is the maximum error on the interval \([-2, 7.4]\) for each approximating polynomial?