IEOR 253 - Spring 2024
Homework 3
Due Date: 4/8/2024 (Monday) at 5:00 PM
Problem 1: Monotonicity of the optimal value function (lecture on single-leg
capacity control dynamic program with sequential arrival). In the class, we discussed
the DP formulation of the n-class optimal booking problem with sequential arrivals. In this
problem, you are asked to show some monotonicities of the value function.
• Jt(x)− Jt(x− 1) is non-decreasing in t, ∀x.
• Jt(x)− Jt(x− 1) is non-increasing in x, ∀t.
Hint : The second property implies the first property. To prove the second property, given
Dt, consider the discrete concavity of Ht(Dt, x) = max0≤u≤min{Dt,x} ptu + Jt−1(x − u) in x,
i.e., Ht(Dt, x+ 1)−Ht(Dt, x) ≤ Ht(Dt, x)−Ht(Dt, x− 1) for any x ∈ Z+ for any t.
Problem 2: KKT conditions of the dual problem. Derive the KKT conditions for the
program we studied in class,
min J˜µT (x)
s.t. µ ≥ 0
with variable µ ∈ Rm. In particular, show that an optimal solution µ∗ to this program must
satisfy
T∑
t=1
n∑
j=1
P (Rt,j ≥ (µ∗)⊺Aj)Ai,j ≤ xi, ∀i, (1)
T∑
t=1
n∑
j=1
P (Rt,j ≥ (µ∗)⊺Aj) (µ∗)⊺Aj = (µ∗)⊺x. (2)
Problem 3: Constant fare prices and deterministic linear program. Consider the
network revenue management model we discussed in class. Suppose that the fare prices are
constant (deterministic), that is,
Rt =

r1e1 w.p. p1
r2e2 w.p. p2
...
...
rnen w.p. pn
0 w.p. 1−∑nj=1 pj.
Let D ∈ Rn be a vector with components Dj = E[
∑T
t=1Rt,j/rj]. Show that the optimal
value of the program
max r⊺y,
s.t. Ay ≤ x,
0 ≤ y ≤ D,
with variable y ∈ Rn is equal to J˜µ∗T (x). In addition, the optimal dual solution of the capacity
constraints of the previous deterministic linear program is an optimal solution of the problem
minµ≥0 J˜
µ
T (x).
Problem 4: Prove the following result in the derivation of the asymptotic optimality of
the bid-price control policy discussed in the lecture. Let X be a random variable with finite
first and second order moments, i.e., E[X] = µ < +∞, E[(X − E[X])2] = σ2 < +∞. Let
x+ = max{x, 0}. Prove the following: ∀m ∈ R,
E[(X −m)+] ≤
√
σ2 + (m− µ)2 − (m− µ)
2
.
Hint : You can without loss of generality let m = 0.