Linear Programming Homework 3.pdf

Document Content and Description Below

Problem 1 (4 points, Exer. 41 in Linear Programming Exercises): Let P 2 Rn×n be a matrix with the following two properties: • all elements of P are nonnegative: pij ≥ 0 for i = 1; · · · ; n ... and j = 1; · · · ; n. • the columns of P sum to one: Pn i=1 pij = 1 for j = 1; · · · ; n. Show that there exists a y 2 Rn such that P y = y; y ≥ 0; nX i =1 yi = 1: Remark (the following are not related to the probem solution). This result has the following application. We can interpret P as the transition probability matrix of a Markov chain with n states: if s(t) is the state at time t (i.e., s(t) is a random variable taking values in f1; · · · ; ng), then pij is defined as pij = Pr(s(t + 1) = ijs(t) = j): Let y(t) 2 Rn be the probability distribution of the state at time t, i.e., yi(t) = Pr(s(t) = i): Then the distribution at time t + 1 is given by y(t + 1) = P y(t). The result in this problem states that a finite state Markov chain always has an equilibrium distribution y. Solution: Suppose there exists no such y. From Farkas’s Lemma, there exist z 2 Rn and w 2 R such that (P − I)T z + w1 ≥ 0; w < 0; i.e., PT z > z:Since the elements of P are nonnegative with unit column sums, we must have (PT z)i ≤ max j zj; which contradicts z < PT z. Problem 2 (4 points, Exer. 46 in Linear Programming Exercises): For the following two LPs, check (and prove whether) the proposed solution is optimal, by using duality: 1. For the LP minimize 47x1 + 93x2 + 17x3 − 93x4 subject to 26666664 −1 −6 1 3 −1 −2 7 1 0 3 −10 −1 −6 −11 −2 12 1 6 −1 −3 37777775 266664 x1 x2 x3 x4 377775 ≤ 26666664 −3 5 −8 −7 4 37777775 Is x = (1; 1; 1; 1) optimal? 2. For the LP maximize 7x1 + 6x2 + 5x3 − 2x4 + 3x5 subject to 266664 1 3 5 −2 3 4 2 −2 1 1 2 4 4 −2 5 3 1 2 −1 −2 377775 26666664 x1 x2 x3 x4 x5 37777775 ≤ 266664 4 3 5 1 377775 ; xi ≥ 0; i = 1 : : : 5 Is x = (0; 4=3; 2=3; 5=3; 0) optimal? Solution: 1. Clearly, x∗ = (1; 1; 1; 1) is feasible: it satisfies the first four constraints with equality and the fifth constraint with strict inequality. To prove that x∗ is optimal, we construct a dual optimal z∗ as a certificate of the optimality. z∗ must satisfy: AT z∗ + c = 0; z∗ ≥ 0; zk∗(bk − aT k x∗) = 0; k = 1; : : : ; 5: From the complementarity conditions we see that z5∗ = 0, and the dual equality constraints reduce to a set of four equations in four variables 266664 −1 −1 0 −6 −6 −2 3 −11 1 7 −10 −2 3 1 −1 12 377775 266664 z∗ 1 z∗ 2 z∗ 3 z∗ 4 377775 + 266664 47 93 17 −93 377775 = 0:These equations have a unique solution (3; 2; 2; 7; 0). Therefore, z∗ = (3; 2; 2; 7; 0): This implies that the optimality condition holds, and x∗ = (1; 1; 1; 1) is optimal. 2. We consider the given problem as the dual problem and we can form the primal problem as minimize cT y subject to Ay ≤ b y ≤ 0; where A = 26666664 1 4 2 3 3 2 4 1 5 −2 4 2 −2 1 −2 −1 3 1 5 −2 37777775 ; b = 26666664 −7 −6 −5 2 −3 37777775 ; c = 266664 −4 −3 −5 −1 377775 : Let us suppose ~ x = (0; 4=3; 2=3; 5=3; 0)T is dual optimal, and ~ y is primal optimal. Then according to the optimality condition, we have x~i(b − Ay~)i = 0; i = 1; : : : ; 5; cT y~ = −bT x; ~ where the first constraints are according to the complementary slackness and the second constraint is due to the strong duality. We can solve the above equations, which contain four equations and four variables. Then we can get the solution: ~ y = (−1; −1; 0; −1)T . Obviously, ~ y is not primal feasible, since the last constraint of Ay ≤ b is not satisfied. Therefore, ~ x = (0; 4=3; 2=3; 5=3; 0)T is not optimal. [Show More]

Last updated: 2 years ago

Preview 1 out of 8 pages