338 ACTIVITY 8: Direction Vectors and the Finite Basis Theorem

WHY:

This activity is designed to help you understand the finite basis theorem better. This theorem is the key to proving the Extreme Point Theorem which allows us to solve a linear programming problem by evaluating the objective function at the extreme point of the feasible region. This result will greatly simplify the process for solving linear programming problems since any process with a finite number of steps can be programmed into a computer.

INFORMATION:

Extreme Point

An Extreme Point of a feasible region cannot be in the interior of a line segment joining any two point in the feasible region.

Direction Vector

A Direction Vector for a feasible region is a vector in the direction of one of the bounding rays of the feasible region. A bounded feasible region (polytope) does NOT have any direction vectors. To determine a direction vector, subtract two points on the bounding ray.

Finite Basis Theorem

The Finite Basis Theorem states that any convex polyhedron can be written as the sum of the convex hull of its extreme points and the conical hull of its direction vectors. The sum of two sets is the set of all sums of pairs of points, one from each set.

LEARNING OBJECTIVES:

1. Discover how to plot a feasible region and find its extreme points and direction vectors using Maple.
2. Discover the geometric and algebraic meanings of the Finite Basis Theorem.
3. Understand the role of visualization in learning.

PERFORMANCE CRITERIA:

1. Quality of the answers to the Critical Thinking Questions.
   • Completeness
   • Clarity
   • Depth
2. Level of ability to be able to find Direction Vectors and clearly explain the Finite Basis Theorem.

RESOURCES:

1. Chapter 2, Strategic Mathematics
2. 30 minutes

PLAN:

1. Choose roles if you have not already done so.
   
   
2. Get into the Maple workspace Activity8 by launching MAPLE and then opening Activity8 under Public\Courses\Math\Math338 as Maple text. Have the recorder write down what happened at each step and any discoveries the team made as the model was executed.
   
   
3. The corner points of a feasible region are called EXTREME POINTS. These are very important in solving math programming problems. Find the extreme points in the model from the graph and then plot the convex hull of the extreme points.
   
   
4. Find the direction vectors of the bounding rays of the feasible region and plot the conical hull of these direction vectors.
   
   
5. Cut out the conical hull of the direction vectors from a piece of paper and place its origin at the initial point of the convex hull of the extreme points. Then move the origin of the cutout along the convex hull.
   
   
6. Answer the critical thinking questions.

MODEL:

Plot the graph of the feasible region determined by the following constraints. Find and plot the direction vectors of the bounding rays and the extreme points for this region. Write out the finite basis theorem as it applies to this problem.

          3x -  y >= 2
           x + 2y >= 5
            x >= 3,  y >= 0

CRITICAL THINKING QUESTIONS:

These will be provided in class.

Return to the List of Activities