Friday,7thSept2007ObjectiveStudentswillextrude,revolve星期五9月第七2007目标的学生将挤出旋转.ppt

1、Linear Programming independent research project Nick Yates 30th April 2008,Motivation,Linear programming = optimize a (linear) function given various (linear) constraints Applications business (maximize profit, with resources available) engineering (design a prototype with best possible performance,

2、 subject to constraints on size and material cost) Big Ideas Graphical method Simplex method,Linear Program Standard Form,Maximize objective function Subject to constraints,Duality,Minimize related objective function Subject to constraints,Example: Graphical Method,Graph all constraints (inequalitie

3、s) Creates polygon if 2D, polytope if more Find all vertices Maximal (optimal) value will be at a vertex So just evaluate your objective function z at every vertex!,Example: Graphical Method,Our original system of constraints is graphed here, overlapping in a triangle. z(0,0) = 2(0)+0 = 0 z(1,0) = 2

4、(1)+0 = 2 z(0,.2) = 2(0)+.2 = .2,Example: Simplex Method,Add new “slack” variables to simplify constraints Now pick a starting point, identify a variable that can be increased, and use (matrix) row operations to move around variables (xs and ws),Benefits of Simplex Method,Similar in theoryslides alo

5、ng edges of polytope from vertex to vertex Dont have to draw the graph This is especially important for linear programs with more than 3 variablessince we cant see in 4 dimensions!,Lesson Plan,Use in an Algebra 2 class Focus on Graphical Method (Simplex Method too complicated and abstract) Review gr

6、aphing inequalities Begin with real-world apps as motivation Provide several partly-done and highly-structured examples to ease into full-length project,Lesson Plan,You set up a tutoring service in math and engineering for eleventh grade students in CIM and Algebra 2. You charge $10 an hour for math

7、 help and $15 an hour for engineering help. You wish to take on no more than eight students total (math + engineering). Only three engineering students are In need of your services, while lots of math students are. Set up a table Write the objective function P for profit (or pay). Graph the constraints on graph paper. Find the four vertices. Evaluate the objective function at each vertex. What is the most money you can make? How many of each type of student have