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; · ·
...
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]
