闪电代写 -代写CS作业_CS代写_Finance代写_Economic代写_Statistics代写_代码代做_IT代写_加急帮助

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

APM236

Homework 3

(1) Let a > 0 be a positive number and consider the polyhedron P = {x e R3 I x2 s , x1 +x2 +x3 s a, x1 , x2 , x3 > 0}. Draw the given polyhedron in standard form and after converting it to canonical form ﬁnd all basic directions Dj at the BFS x = (0, , ).

(2) Consider the LPP of maximizing x1 -5x2 +x3 subject to the constraints 2x1+4x2+6x3 s 12, x3 > 0, x1 > 0, and 2 > x2 > 0.

(a) Graph the feasible set in R3 .

(b) Using the canonical form of this problem, ﬁnd all basic feasible solutions (BFS). Hint: based on your graph from part (a), how many BFS are there?

(c) Let A denote the vertex (0, 0, 0) and B the vertex (2, 2, 0) of the feasible set. Find all basic directions at each of these vertices/BFS.

(d) For each of the basic directions you foud in part (c), ﬁnd the corresponding reduced cost.

(3) Consider the polyhedron P = {x e R4 I Ax = b, x > 0}, where A = 、 and b = ╱ 7(15)、

Here we are assuming 1 < a < 2.

(a) Find all BFS of P and indicate which is degenerate and which is non-degenerate. (b) Graph the feasible set in R2 . Note: here m = 2 and n = 4 so n - m = 2.

(4) Let P = {x e R100 I Ax = b, x90 , . . . , x96 > 0, x98 - x99 + x100 = 0} be a polyhedron, where A is an m x 100 matrix (1 s m < 100) with linearly independent rows and xi are the components of the vector x.

(a) For which values of m is it possible that P has a degenerate BFS? Explain. (b) Suppose x e P is a degenerate BFS. How small can m be? Explain.

(5) Consider the following polyhedron in canonical form {x e Rn I Ax = b, x > 0},

where A is an m x n matrix with linearly independent rows. Suppose that two diﬀerent choices of bases (that is of a set of linearly independent columns) lead to the same basic feasible solution (BFS). Show that the BFS is degenerate.

(6) For each k e N, deﬁne the set Bk to be the collection of all k x k matrices with nonnegative entries whose rows and columns each sum to one. For example, the following matrix is in

B3:

M = ╱

．5/10

5/10

4/10

1/10

、

4/10．

Recall from HW2 and tutorial that Bk is a polytope called the Birkhoﬀ polytope of order k, and it has interesting applications in probability, geometry, and statistics.

(a) Find all the BFS of B3 . Hint: start by representing a 3 x 3 matrix

╱

(x31

x12

x22

x32

、

x33 ．

as the "ect4T x = (x11 , x12 , x13 , x21 , x22 , x23 , x31 , x32 , x33 ) in R9 . Now write the con- straints of B3 in canonical form. You can assume that you know there are exactly 6 BFS (this means it is enough to guess 6 choices for sets of linearly independent columns that give these 6 BFS and you do not need to try all the other possibilities of choosing linearly independent columns).

(b) Recall that a BFS is an extreme point of B3 . Prove that every matrix M in B3 is a convex combination of the extreme points of B3 and then explicitly write M above as a convex combination of the 6 BFS you found in part (a).

(7) Let B2 to be Birkhoﬀ polytope of order 2, that is the collection of all 2 x 2 matrices with nonnegative entries whose rows and columns each sum to one. Suppose cij are real numbers such that c12 = c21 > c11 > c22 . Consider the following LPP:

maximize: c11x11 + c12x12 + c21x21 + c22x22

subject to: 、 e B2

x11 , x12 , x21 , x22 > 0

(a) Write this problem in canonical form {x = (x11 , x12 , x21 , x22 ) e R4 I Ax = b, x > 0}. Hint: A should be a 3 x 4 matrix (after you eliminate one row which is linearly

dependent on the others).

(b) List all BFS.

(d) For the maximizer x* , show that for all basic directions Dj at x* the reduced cost c DjT s 0.

The last problem is for practice only and is not to be turned in.

(8) This problem is about what happens to degeneracy of extreme points (and basic solutions) as we change the form of the LPP. Recall that a point x e P in the polyhedron P c Rn is an extreme point if n linearly independent constraints are active at x. The extreme point x is degenerate if there are additional active constraints at x, otherwise it is non-degenerate.

(a) Let A be an m x n matrix (we are not assuming the rows are necessarily linearly independent) and consider the polyhedron P = {x e Rn : Ax s b}. Recall that after introducing slack variables it becomes = {(x, u) e Rn x Rm : Ax + u = b, u > 0}. Suppose x e P is an extreme point where l of the constraints in P are active. How many of the constraints are active at (x, u) e ? Explain.