Convex Sets, Hyperplanes, and Various Hulls

338 ACTIVITY 7: Convex Sets, Hyperplanes, and Various Hulls

WHY:

This activity is designed to help you understand how to recognize a convex set and draw a hyperplane and the linear, affine, conical, and convex hull of a set of points. We will model objective functions in linear programming as hyperplanes, and the feasible region as the intersection of halfspaces which are bounded by hyperplanes. When solving linear programming problems we will make extensive use of the convexity of the feasible region. We will use conical and convex hulls to formulate the finite basis theorem which we use to prove that we have reached an optimal solution.

LEARNING OBJECTIVES:

Gain an understanding of what makes a set convex.
Discover the connection between Hyperplane, Subspace, and the solution space of a system of equations.
Gain an understanding of Linear, Affine, Conical and Convex Hulls.

PERFORMANCE CRITERIA:

Quality of the answers to the Critical Thinking Questions.
- Completeness
- Clarity
- Depth
Level of understanding of the models in the Maple workspace.
- Depth of insight
- Success in completing Maple activity

INFORMATION:

Line Segment: The line segment joining two points X1 and X2 is the set (tX1 + (1-t)X2) for 0<=t<=1.
Convex Set: S is convex if for any two distinct points of S the line segment joining these points is contained completely in S.
Hyperplane: The set of points satisfying the equation CTX = k is called a hyperplane. A hyperplane divides space into upper and lower Halfspaces.
Linear Hull: The linear hull L(S) of a set S is the set of all linear combinations of vectors in S. It is the same as the space spanned by the vectors in S.
Affine Hull: The affine hull Aff(S) of a set S is the set of all affine combinations of vectors in S. It is the lowest dimensional hyperplane which passes through all the points of S. (I.e. in R3, if S has one point Aff(S) is the point; if S has two points, Aff(S) is the line determined by them; if S has three noncolinear points, Aff(S) is the plane determined by them; if S contains at least four noncoplanar points, Aff(S) is all of R3.)
Conical Hull: The conical hull Coni(S) of a set S is the set of all conical combinations of vectors in S. Coni(S) is the smallest cone with vertex at the origin containing the points of S.
Convex Hull: The convex hull Conv(S) of a set S is the set of all convex combinations of vectors in S. Conv(S) is the smallest convex set containing the points of S. The convex hull of a finite set of points is called a Convex Polytope.
Convex Polyhedron: A convex polyhedron is the intersection of halfspaces. The feasible region of a linear programming problem is a convex polyhedron. Bounded convex polyhedra are convex polytopes. The direction vectors of an unbounded convex polyhedron are vectors in the direction of its bounding rays. Note that a convex polytope has no direction vectors.

RESOURCES:

Chapter 2, Strategic Mathematics
MAPLE help system
Activity7 workspace
30 minutes

PLAN:

Choose roles if you have not already done so.
Assess the team's understanding of the terms listed in the information section.
Execute the model in the Activity7 MAPLE workspace by launching MAPLE and then opening Activity7 as Maple text. Have the recorder write down what happened at each step and any discoveries the team made as the model was executed.
Use the model to answer the critical thinking questions.

MODEL:

Get into the MAPLE text Activity7 under Public\Courses\Math\Math338 and execute each line. Here are some general rules about working with Maple workspaces:

Each command line ends with a semicolon if the results are to be evaluated and displayed, or a colon if the results ane not to be displayed.
A variable or function definition is indicated by the symbol := (colon equal)
A command may be selected, edited, and re-executed by pressing Enter or Return. The new results replace the old ones.
A command may be copied onto the scratchpad and placed after a new prompt. In this case, the old results remain on the worksheet at their original location.
To rotate a plot to get a better understanding of its shape, place the mouse on the 3-d graph in the plot, hold down the mouse button, and drag the mouse.
To plot the graph of a function of two variables, use the plot3d function. (See example z = x^2/4 + y^2/9 in the workspace.). For this option and the next you need to give the command with(plots): before using 3D options.
To plot the line segment joining two points in R3: {(1-t)(x1,y1,z1) + t(x2,y2,z2)} = {x1 + t(x2 - x1), y1 + t(y2 - y1), z1 + t(z2 - z1)}, use the spacecurve function.
To plot graphs in R2, use the plot or pointplot functions. To plot more than one graph on the same set of axes, assign each plot to a variable and then display all the variables. (See example in the workspace).

CRITICAL THINKING QUESTIONS:

These will be provided in class.

Math 338 Activity 7 -- Revised 9/15/98