Linear Programming Homework 3

Document Content and Description Below

Linear Programming Homework 3 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 [Show More]

Last updated: 1 year ago

Preview 1 out of 8 pages