Test 2 Study Guide

Posted on by
  • Know the steps for solving linear programming problems in two variables
  1. Find constraints (this is a list of inequalities) and objective function
  2. Graph feasible set. (Suggestion: Find the x and y intercepts of each constraint line), and list the vertices of the feasible set.
  3. Test each vertex in the objective function until you find the optimum (minimum or maximum) vertex.
  • Be able to carry out each of the steps above
  • For applicable linear programming problems: Be able to eliminate all but two variable by using an equation from the word problem (As in the shipping example we did recently.)
  • Be able to explain why an interior point in the feasible set is never optimal
  • Know how you can find a vertex of the feasible set when it has three variables
    • Be able to solve a linear system, and verify the solution (the intersection point) is feasible or not feasible
  • Know the steps involved in the Simplex Method
  • Given a recipe for the set of vertices of a feasible set, a recipe for finding the neighbors of a vertex, the objective function and a starting vertex, you should be able to carry out the Simplex Method
  • Know the definition of a set and a subset
    • Be able to explain the difference between a set and a list
    • Be able to list all of the subsets of a given set

Practice Problems :: Simplex Method

Posted on by

Problem 1:

Consider the following feasible set:

  • $latex x \ge -1 \text{ and } x\le 1$
  • $latex y \ge -1 \text{ and } y\le 1$
  • $latex z \ge -1 \text{ and } z\le 1$
  • $latex w \ge -1 \text{ and } w\le 1$

The vertices of this feasible set have four coordinates, and each coordinate is either equal to positive one or negative one. For example (1,-1,1,1) is a vertex of the feasible set.

Two vertices are neighbors if they agree in all but one coordinate. For example, (1,1,1,1) is a neighbor of (1,-1,1,1).

Starting with the vertex (1,-1,1,1) as $latex v_0$, maximize the following objective function: $latex -2x-y+3z+4w$

Problem 2:

The permutahedron, $latex P_n$, is an example of a feasible set. The vertices of the permutahedron are given by permutations of $latex n$ (we’ll talk more about these in the coming weeks). I have listed the vertices of the permutahedron $latex P_3$ below:

  • (1,2,3)
  • (2,1,3)
  • (1,3,2)
  • (2,3,1)
  • (3,1,2)
  • (3,2,1)

Correction:

The neighbors a vertex are obtained by swapping entries that are adjacent in value.

  • For example: (1,2,3) and (2,1,3) are neighbors. But (3,1,2) and (2,1,3) are also neighbors. In the second example, I am looking at the entries whose values are 3 and 2, and swap.

Problem 2 part 1: Show that each vertex of $latex P_3$ has exactly two neighbors. (Thus, this feasible set is a polygon, even though it naturally lives in 3-space.)

Problem: 2 part 2: Use the simplex method, starting at the vertex (1,2,3) to maximize the objective function $latex 2x+4y+z$