# Problem 1:

Consider the following feasible set:

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 , maximize the following objective function:

# Problem 2:

The *permutahedron, , *is an example of a feasible set. The vertices of the permutahedron are given by permutations of (we’ll talk more about these in the coming weeks). I have listed the vertices of the permutahedron 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 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