Page 264 - A First Course In Stochastic Models

LINEAR PROGRAMMING APPROACH 257

program; see Derman (1970) and Hordijk and Kallenberg (1984):

Minimize c i (a)x ia
i∈I a∈A(i)
subject to

x ja − p ij (a)x ia = 0, j ∈ I,
a∈A(j) i∈I a∈A(i)

x ia = 1,
i∈I a∈A(i)
(s) (s)
α x ia ≤ β , s = 1, . . . , L,
ia
i∈I a∈A(i)
x ia ≥ 0, a ∈ A(i) and i ∈ I.

Denoting by {x } an optimal basic solution to this linear program and letting the
∗
ia

∗
∗
set S 0 = {i | x > 0}, an optimal stationary randomized policy π is given by
a ia

∗
∗
x / x , a ∈ A(i) and i ∈ S 0 ,
∗ ia d id
π (i) =
a arbitrary, otherwise.
Here the unichain assumption is essential for guaranteeing the existence of an
optimal stationary randomized policy.
Example 6.1.1 (continued) A maintenance problem
Suppose that in the maintenance problem a probabilistic constraint is imposed on
the fraction of time the system is in repair. It is required that this fraction is no
more than 0.08. To handle this constraint, we add to the previous linear program
for the maintenance problem the constraint
N−1

x i1 + x N2 + x N+1,2 ≤ 0.08.
i=2
The new linear program has the optimal solution

x 10 = 0.5943, x ∗ 20 = 0.2971, x ∗ 30 = 0.0286, x 31 = 0.0211,
∗
∗
∗
∗
x 41 = 0.0177, x ∗ 52 = x ∗ 62 = 0.0206 and the other x = 0.
ia
The minimal cost is 0.4423 and the fraction of time the system is in repair is exactly
0.08. The LP solution corresponds to a randomized policy. The actions 0, 0, 1, 2
and 2 are prescribed in the states 1, 2, 4, 5 and 6. In state 3 a biased coin is tossed.
The coin shows up heads with probability 0.0286/(0.0286 + 0.0211) = 0.575. No
preventive repair is done if heads comes up, otherwise a preventive repair is done.