闪电代写 -代写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

Due on Crowdmark: Sat Feb 18, before 9pm

(1) Recall from HW2 Q6 the problem of maximizing 1x1+ 0x2+ 1x3 subject to the constraints 6x1 + x2 + 4x3 < 12, x1 > 0, x3 > 0, and 6 > x2 > 0.

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

(b) Solve the maximization problem by calculating the value of the objective function at

all the BFS. Note: see the extreme point theorem [KB] Thm 1.7.

(2) Let a > 0 be a positive number and consider the polyhedron P = ex ∈ R3 | x1 + x2 + x3 > a, x2 < , x1 , x2 , x3 > 0}. Draw the given polyhedron in standard form and after convert- ing it to canonical form ﬁnd all the BFS.

(3) Consider the Even-Odd game with the payoﬀ function A(x, y) given by 北 y 1 2

X = e1, 2} Y = e1, 2} A : 1 3 0

2 -4 2

Find the value V of this game and the optimal strategies of player I and player II.

(4) Consider the polyhedron P = ex ∈ R4 | Ax = b, x > 0}, where A = 、 and b = ╱ 7(15)、

Here we are assuming 1 < a < 2.

(a) Graph the feasible set in R2 and label the extreme points. Note: here m = 2 and n = 4

so n - m = 2.

(b) Find all BFS of P and indicate which is degenerate and which is non-degenerate. Note: here, since this problem is in canonical form, you can use the characterization of de- generacy for canonical form.

(5) Let P = ex ∈ R100 | Ax = b, x90 , . . . , x100 > 0, x98 + x99 - x100 = 101} be a polyhedron, where A is an m × 100 matrix (1 < m < 100) with linearly independent rows and xi are the components of the vector x. Use the deﬁnition of degenerate BFS to answer the following:

(a) For which values of m is it possible that P has a degenerate BFS? Explain. (b) For which values of m must P have a degenerate BFS? Explain.

(6) Consider the following polyhedron in canonical form ex ∈ Rn | Ax = b, x > 0},

where A is an m × 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.

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

M = ╱、

(5/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 × 3 matrix

╱、

(x31 x32 x33 ．

as the "ect4A 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).

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 ∈ 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 × n matrix (we are not assuming the rows are necessarily linearly independent) and consider the polyhedron P = ex ∈ Rn : Ax < b}. Recall that after introducing slack variables it becomes = e(x, u) ∈ Rn × Rm : Ax + u = b, u > 0}. Suppose x ∈ P is an extreme point where l of the constraints in P are active. How many of the constraints are active at (x, u) ∈ ? Explain.