Mathematics > QUESTIONS & ANSWERS > Linear Programming Homework 3.pdf (All)
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
Buy this document to get the full access instantly
Instant Download Access after purchase
Buy NowInstant download
We Accept:
Can't find what you want? Try our AI powered Search
Connected school, study & course
About the document
Uploaded On
Jul 26, 2022
Number of pages
8
Written in
This document has been written for:
Uploaded
Jul 26, 2022
Downloads
0
Views
40
In Scholarfriends, a student can earn by offering help to other student. Students can help other students with materials by upploading their notes and earn money.
We're available through e-mail, Twitter, Facebook, and live chat.
FAQ
Questions? Leave a message!
Copyright © Scholarfriends · High quality services·