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