A little operations research into TV programming: analytical solution

We derive an analytical solution to the optimum TV scheduling (OTVS) problem posed at a prior entry. In the rest we assume a_i,c_i > 0 for all i=1,...,n. We begin by solving a generalization of OTVS that is amenable to a more regular treatment following techniques similar to those of Variational Calculus, and then seek ways to constrain this problem so as to find solutions to OTVS itself.

Definition. Given I a subset of {1,...,n}, the generalized OTVS problem on I, GOTVS(I), consists of finding a resource distribution {m_i, m_i > −c_i, i in I} with ∑_Im_i = M that maximizes S({m_i}) = ∑_Is(m_i) = ∑_Ia_im_i/(m_i+c_i). Note that in OTVS we imposed the tighter restriction m_i ≥ 0.

Lemma. Consider the space of all distributions {m_i, m_i > −c_i, i in I} with ∑_Im_i = M. The limit of S({m_i}) when min({m_i+c_i}) → 0 is −∞.

Proof. ∑_Is(m_i) can be split into its positive terms, whose sum is bounded by ∑_Ia_i, and its negative terms, among which at least one tends to −∞.

Corollary. GOTVS(I) has a solution.

Proof. Given the result above, GOTVS(I) is equivalent to finding a maximum value of the continuous function S inside the compact set {m_i, m_i ≥ −c_i+δ,i in I} with ∑_Im_i = M, for some fixed δ>0.

Theorem. Let d_i = ∂s(m_i)/∂m_i = a_ic_i/(m_i+c_i)². If {m_i} is a solution to GOTVS(I) , then

d_j = d_k, for all j,k in I.

Proof. If d_j > d_k, we could then obtain a net gain in S({m_i}) by transferring some quantity δ from m_k to m_j.

Corollary. GOTVS(I) has a unique solution of the form

m_i = k√(a_ic_i) − c_i, i in I,

where

k = (M+∑_Ic_j)/∑_I√(a_jc_j).

Proof. Solve d_i = a_ic_i/(m_i+c_i)² = 1/k², i in I, with the additional constraint ∑_Im_i = M.

Now, solving OTVS reduces to finding a solution to GOTVS(I) with no negative components for some maximal subset I of {1,...,n}. It turns out that finding the support of the solution to OTVS is fairly simple:

Theorem. Let {m_i} be a solution to OTVS and define t_i = (∂s(m_i)/∂m_i)_mi=0 = a_i/c_i. For all j,p in I, if t_j ≥ t_p and m_p > 0 then m_j > 0.

Proof. Let us suppose m_j = 0; as t_j = (∂s(m_j)/∂m_j)_mj=0 ≥ t_p = a_p/c_p > a_pc_p/(m_p+c_p)² = ∂s(m_p)/∂m_p, transferring some quantity δ from m_p to m_j would yield a solution without negative components and with greater S than {m_i}.

Corollary. Let σ: I → I be a permutation of I such that t_σ(1) ≥ t_σ(2) ≥ ··· ≥ t_σ(n). There is some τ in {1,...,n} such that the support of solutions to OTVS is {σ(1),...,σ(τ)}; moreover, t_σ(τ) is strictly greater than t_σ(τ+1) (except, of course, if τ = n).

Corollary. The solution to OTVS is unique.

The following pseudocode sketches an algorithm for computing OTVS.

OTVS({a_i}, {c_i}, M)
m₁,...,m_n ← 0
knum ← M
kden ← 0
τ ← n
compute σ
for i = 1 to n
····if (knum+c_σ(i))/(kden+√(a_σ(i)c_σ(i))) > c_σ(i)/√(a_σ(i)c_σ(i)) then
········τ ← i−1
········break
····else
········knum ← knum + c_σ(i)
········kden ← kden + √(a_σ(i)c_σ(i))
····end if
end for
k ← knum/kden
for i = 1 to τ
····m_σ(i) ← k√(a_σ(i)c_σ(i)) −c_σ(i)
end for

The idea is as follows: we keep visiting indices from the highest t_i downward and maintain the running numerator and denominator of the value that k would take if the elements visited so far were exactly those comprising the support of the solution to OTVS. When we come upon an element for which its computed m_i would be negative, we know we've gotten to the cutoff index τ and that the k calculated so far is the actual one, so we just use it for computing the final values of {m_i}.