Monthly Archives: October 2013

Dynamic Linear Programming

My department is exploring the pros and cons of different technologies for use in teaching our classes. Two teachers shared ways to use Desmos and GeoGebra in lessons using inequalities on one day; we explored the same situation using the TI-Nspire in the following week’s meeting.  For this post, I’m assuming you are familiar with solving linear programming problems.  Some very nice technology-assisted exploration ideas are developed in the latter half of this post.

My goal is to show some cool ways we discovered to use technology to evaluate these types of problems and enhance student exploration.  Our insights follow the section considering two different approaches to graphing the feasible region.  For context, we used a dirt-biker linear programming problem from NCTM’s Illuminations Web Pages.

DirtBikes

Assuming x = the number of Riders built and = the number of Rovers built,  inequalities for this problem are

linear1

We also learn on page 7 of the Illuminations activity that Apu makes a $15 profit on each Rider and $30 per Rover.  That means an Optimization Equation for the problem is Profit=15x+30y.

GRAPHING THE FEASIBLE REGION:

Graphing all of the inequalities simultaneously determines the feasible region for the problem.  This can be done easily with all three technologies, but the Nspire requires solving the inequalities for y first.  Therefore, the remainder of this post compares the Desmos and GeoGebra solutions.  Because the Desmos solutions are easily accessible as Web pages and not separate files, further images will be from Desmos until the point where GeoGebra operates differently.

Both Desmos and GeoGebra can graph these inequalities from natural inputs–inputing math sentences as you would write them from the problem information:  without solving for a specific variable.  As with many more complicated linear programming problems, graphing all the constraints at once sometimes makes a visually complicated feasible region graph.

linear2

So, we decided to reverse all of our inequalities, effectively  shading the non-feasible region instead.  Any points that emerged unshaded were possible solutions to the Dirt Bike problem (image below, file here).  All three softwares shift properly between solid and dashed lines to show respective included and excluded boundaries.

linear3

Traditional Approach – I (as well as almost all teachers, I suspect) have traditionally done some hand-waving at this point to convince (or tell) students that while any ordered pair in the unshaded region or on its boundary (all are dashed) is a potential solution, any optimal solution occurs on the boundary of the feasible region.  Hopefully teachers ask students to plug ordered pairs from the feasible region into the Optimization Equation to show that the profit does vary depending on what is built (duh), and we hope they eventually discover (or memorize) that the maximum or minimum profit occurs on the edges–usually at a corner for the rigged setups of most linear programming problems in textbooks.  Thinking about this led to several lovely technology enhancements.

INSIGHT 1:  Vary a point.

During our first department meeting, I was suddenly dissatisfied with how I’d always introduced this idea to my classes.  That unease and our play with the Desmos’ simplicity of adding sliders led me to try graphing a random ordered pair.  I typed (a,b) on an input line, and Desmos asked if I wanted sliders for both variables.  Sure, I thought (image below, file here).

linear7

— See my ASIDE note below for a philosophical point on the creation of (a,b).
— GeoGebra and the Nspire require one additional step to create/insert sliders, but GeoGebra’s naming conventions led to a smoother presentation–see below.

BIG ADVANTAGE:  While the Illuminations problem we were using had convenient vertices, we realized that students could now drag (a,b) anywhere on the graph (especially along the boundaries and to vertices of the feasible region) to determine coordinates.  Establishing exact coordinates of those points still required plugging into equations and possibly solving systems of equations (a possible entry for CAS!).  However discovered, critical coordinates were suddenly much easier to identify in any linear programming question.

HUGE ADVANTAGE:  Now that the point was variably defined, the Optimization Equation could be, too!  Rewriting and entering the Optimation Equation as an expression in terms of a and b, I took advantage of Desmos being a calculator, not just a grapher.  Notice the profit value on the left of the image.

linear6

With this, users can drag (a,b) and see not only the coordinates of the point, but also the value of the profit at the point’s current location!  Check out the live version here to see how easily Desmos updates this value as you drag the point.

From this dynamic setup, I believe students now can learn several powerful ideas through experimentation that traditionally would have been told/memorized.

STUDENT DISCOVERIES:

  1. Drag (a,b) anywhere in the feasible region.  Not surprisingly, the profit’s value varies with (a,b)‘s location.
  2. The profit appears to be be constant along the edges.  Confirm this by dragging (a,b) steadily along any edge of the feasible region.
  3. While there are many values the profit could assume in the feasible region, some quick experimentation suggests that the largest and smallest profit values occur at the vertices of the feasible region.
  4. DEEPER:  While point 3 is true, many teachers and textbooks mistakenly proclaim that solutions occur only at vertices.  In fact, it is technically possible for a problem to have an infinite number optimal solutions.  This realization is discussed further in the CONCLUSION.

ASIDE:  I was initially surprised that the variable point on the Desmos graph was directly draggable.  From a purist’s perspective, this troubled me because the location of the point depends on the values of the sliders.  That said, I shouldn’t be able to move the point and change the values of its defining sliders.  Still, the simplicity of what I was able to do with the problem as a result of this quickly led me to forgive the two-way dependency relationships between Desmos’ sliders and the objects they define.

GEOGEBRA’S VERSION:

In some ways, this result was even easier to create on GeoGebra.  After graphing the feasible region, I selected the Point tool and clicked once on the graph.  Voila!  The variable point was fully defined.  This avoids the purist issue I raised in the ASIDE above.  As a bonus, the point was also named.

linear4Unlike Desmos, GeoGebra permits multi-character function names.  Defining Profit(x,y)=15x+30y and entering Profit(A) allowed me to see the profit value change as I dragged point A as I did in the Desmos solution. The Profit(A) value was dynamically computed in GeoGebra as a number value in its Algebra screen.  A live version of this construction is on GeoGebraTube here.

linear5

At first, I wasn’t sure if the last command–entering a single term into a multivariable term–would work, but since A was a multivariable point, GeoGebra nicely handled the transition.  Dragging A around the feasible region updated the current profit value just as easily as Desmos did.

INSIGHT 2:  Slide a line.

OK, this last point is really an adaptation of a technique I learned from some of my mentors when I started teaching years ago, but how I will use it in the future is much cleaner and more expedient.  I thought line slides were a commonly known technique for solving linear programming problems, but conversations with some of my colleagues have convinced me that not everyone knows the approach.

Recall that each point in the feasible region has its own profit value.  Instead of sliding a point to determine a profit, why not pick a particular profit and determine all points with that profit?  As an example, if you wanted to see all points that had a profit of $100, the Optimization Equation becomes Profit=100=15x+30y.  A graph of this line (in solid purple below) passes through the feasible region.  All points on this line within the feasible region are the values where Apu could build dirt bikes and get a profit of $100.  (Of course, only integer ordered pairs are realistic.)

linear8

You could replace the 100 in the equation with different values and repeat the investigation.  But if you’re thinking already about the dynamic power of the software, I hope you will have realized that you could define profit as a slider to scan through lots of different solutions with ease after you reset the slider’s bounds.  One instance is shown below; a live Desmos version is here.

linear9

Geogebra and the Nspire set up the same way except you must define their slider before you define the line.  Both allow you to define the slider as “profit” instead of just “p”.

CONCLUSIONS:

From here, hopefully it is easy to extend Student Discovery 3 from above.  By changing the P slider, you see a series of parallel lines (prove this!).  As the value of P grows, the line goes up in this Illuminations problem.  Through a little experimentation, it should be obvious that as P rises , the last time the profit line touches the feasible region will be at a vertex.  Experiment with the P slider here to convince yourself that the maximum profit for this problem is $165 at the point (x,y)=(3,4).  Apu should make 3 Riders and 4 Rovers to maximize profit.  Similarly (and obviously), Apu’s minimum profit is $0 at (x,y)=(0,0) by making no dirt bikes.

While not applicable in this particular problem, I hope you can see that if an edge of the feasible region for some linear programming problem was parallel to the line defined by the corresponding Optimization Equation, then all points along that edge potentially would be optimal solutions with the same Optimization Equation output.  This is the point I was trying to make in Student Discovery 4.

In the end, Desmos, GeoGebra, and the TI-Nspire all have the ability to create dynamic learning environments in which students can explore linear programming situations and their optimization solutions, albeit with slightly different syntax.  In the end, I believe these any of these approaches can make learning linear programming much more experimental and meaningful.

Advertisements

Common numerators

As long as I’m leveraging Five Triangles posts, here is another recent one worth discussing.

Too often, I think students believe that the only way to compare fractions is to find common denominators.  In this problem, three of the four given denominators are big enough primes that the common denominator approach would result in some painful enough by-hand computations.

But the pattern in the numerators screams for attention.  Why not find some common numerators and compare the fractions that way?  That approach cracks the problem pretty efficiently.

As a bonus, the common numerator approach also shows that the four given fractions are surprisingly close to each other in size.

Keep thinking …

Two Squares, Two Triangles, and some Circles

Here’s another fun twist on another fun problem from the Five Triangles ‘blog.  A month ago, this was posted.

What I find cool about so many of the Five Triangles problems is that most permit multiple solutions.  I also like that several Five Triangles problems initially appear to not have enough information.  This one is no different until you consider the implications of the squares.

I’ve identified three unique ways to approach this problem.  I’d love to hear if any of you see any others.  Here are my solutions in the order I saw them.  The third is the shortest, but all offer unique insights.

Method 1: Law of Cosines

This solution goes far beyond the intended middle school focus of the problem, but it is what I saw first.  Sometimes, knowing more gives you additional insights.

Because DEF is a line and EF is a diagonal of a square, I know m\angle CEF=45^{\circ}, and therefore m\angle CED=135^{\circ}.  \Delta CEF is a 45-45-90 triangle with hypotenuse 6, so its leg, CE has measure \frac{6}{\sqrt{2}}=3\sqrt{2}.  Knowing two sides and an angle in \Delta DEC means I could apply the Law of Cosines.

DC^2 = 4^2 + (3\sqrt{2})^2 - 2\cdot (3\sqrt{2}) \cdot \cos(135^{\circ})=58

Because I’m looking for the area of ABCD,  and that is equivalent to DC^2, I don’t need to solve for the length of DC to know the area I seek is 58.

Method 2: Use Technology

I doubt many would want to solve using this approach, but if you don’t see (or know) trigonometry, you could build a solution from scratch if you are fluent with dynamic geometry software (GeoGebra, TI-Nspire, GSP).  My comfort with this made finding the solution via construction pretty straight-forward.

  1. Construct segment EF with fixed length 6.
  2. Build square CEGF with diagonal EF.  (This can be done several ways.  I was in a transformations mood, so I rotated EF 90^{\circ} to get the other endpoints.)
  3. Draw line EF  and then circle with radius 4 through point E.
  4. Mark point D as the intersection of circle and line EF outside CEGF .
  5. Draw a segment through points and C.  (The square of the length of CD is the answer, but I decided to go one more step.)
  6. Construct square ABCD with sides congruent to CD.  (Again, there are several ways to do this.  I left my construction marks visible in my construction below.)
  7. Compute the area of ABCD.

Here is my final GeoGebra construction.

Squares1

Method 3: The Pythagorean Theorem

Sometimes, changing a problem can make it much easier to solve.

As soon as I saw the problem, I forwarded it to some colleagues at my school.  Tatiana wrote back with a quick solution.  In the original image, draw diagonal, CG, of square CEGF. Because the diagonals of a square perpendicularly bisect each other, that creates right \Delta DHC with legs 3 and 7.  That means the square of the hypotenuse of \Delta DHC (and therefore the area of the square) can be found via the Pythagorean Theorem.

DC^2 = 7^2+3^2 = 58

Method 4: Coordinate Geometry

OK, I said three solutions, and perhaps this approach is completely redundant given the Pythagorean Theorem in the last approach, but you could also find a solution using coordinate geometry.

Because the diagonals of a square are perpendicular, you could construct ECFG with its center at the origin.  I placed point C at (0,3) and point E at (3,0).  That means point D is at (7,0), making the solution to the problem the square of the length of the segment from (0,3) to (7,0).  Obviously, that can be done with the Pythagorean Theorem, but in the image below, I computed number i in the upper left corner of this GeoGebra window as the square of the length of that segment.

Squares2

Fun.

Scaling the Solar System

Too often, people throw around numbers without even thinking about the tremendous differences in the scales of those numbers.  Here’s the result of an exploration I did this week with my  afternoon math club of 4th and 5th graders to get a perspective on just how big our solar system really is.  They call themselves mc^2.

My school has an three foot diameter iGlobe in the middle of its lower school entry hall.  The group decided to see if they could use the school’s iGlobe to create a scaled model of the solar system.  After some quick research, they learned that the earth was about 8000 miles in diameter and the sun was about 875,000 miles wide.  I challenged them to put that in perspective.

They first tried to think in terms of the iGlobe model they already had.  Some quick division convinced them that a relatively sized sun would be about 109 iGlobes wide.  When I asked them how they could get a handle on just how big that was, one suggested measuring off 109 iGlobes across the field outside.  That’s when another realized that 109 iGlobes = 109 yards = about one football field plus an end zone.  Eyes widened.  After all, the sun doesn’t look nearly that big in the sky!

Since we couldn’t move the iGlobe from its perch, I asked them to come up with a different way to relate these sizes.  That’s when one student realized that if we could call the iGlobe our unit, why not any other object?  He grabbed some Cuisenaire rods, called the Earth one of the square centimeter singles, and started explaining.

OK, that was a nice connection and it gave the students a chance to get some perspective on the size of the Earth.  But I still wasn’t convinced they really got just how enormous the scales were here.  That’s when I asked if they could use the same Sun-Earth model to place the Earth cube in its proper relative position to their Sun diameter.  They found the average distance from the Earth to the Sun (93 million miles), converted that to their new scale, and paced off the distance. NOTE:  It gets pretty small at the end, so I recommend a full-screen view, but it will still be pretty small.

At the end of the video, it’s very difficult to see the running student throw his hands in the air, much less the little tiny Earth cube he’s still holding.  But that’s the point.  Distances across our solar system are mind-bogglingly large.  Sending probes from our little Earth cube to any other object requires a tremendous feat of engineering.  Maybe this is a good first step in helping these students come to grips with the enormity of the scaling of the universe.