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.

About these ads

8 responses to “Dynamic Linear Programming

  1. I love this! I love that you combined desmos with illuminations. Wonderfully helpful post.

  2. Even though GeoGebra can graph inequalities, another way to do this is to graph the LINES that form the boundaries, find all of the points of intersection that will form the vertices of the feasible region, then create a polygon with these points. The advantage is that when you attach point A to the polygon is stays in the polygon and you can drag it with impunity–it will not leave the region.

    • What a GREAT idea, Doug! I really like how this simplifies testing the profit as you move point A along an edge or at a feasible region vertex.

      Your approach takes advantage of a significant difference between the three softwares. Desmos can’t do this because it doesn’t have a geometry feature. I tried this on the Nspire, but it defines a polygon as the perimeter. Only GeoGebra defines a polygon as the perimeter + the interior, and this is exactly what you leveraged to attach point A to the feasible region.

      The only potential limitation I can envision for this approach would be if the feasible region was unbounded. In such a case, you could define a polygon on a portion of the interior of the feasible region or use the original free-floating point A approach.

      This is also a perfect example of implications resulting from differences in the way something is defined. All three platforms can handle the problem, but GeoGebra’s polygon definition gives it a lovely advantage, in my opinion.

  3. Chris, the profit function is not constant along the edges. Indeed that it is not constant means you can increase profit by moving to a vertex at the one end of the segment, assuming you are not already at a vertex.

    • True, for this problem.

      But in a different problem situation, it is conceivable that the profit function could be parallel to an edge of the feasible region. In such a situation, every point on the parallel edge would have the same profit.

      Whether or not those points are optimal depends on the remainder of the geometric relationship the feasible region and the profit function.

      • Agreed that the profit function could be constant on one of the boundary segments. Change your profit function to Profit(x,y)=20x+30y in this problem. However, we should point out that the max still occurs at a vertex, this time at two of them. That the profit is also a max at any point along one of the boundary segments does not contradict the vertex theorem.

      • Agreed. I just find it interesting that even more solutions are *possible*. Thanks for the input.

  4. This is cool, Chris, and it’s exactly what we’re teaching in Algebra II right now. We’re doing two variables graphically first and then we’ll extend to multiple variables in a spreadsheet and use the Excel solver to find the solutions.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s