Wednesday, October 17, 2007

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 ai,ci > 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 {mi, mi > −ci, i in I} with ∑Imi = M that maximizes S({mi}) = ∑Is(mi) = ∑Iaimi/(mi+ci). Note that in OTVS we imposed the tighter restriction mi ≥ 0.

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

Proof.Is(mi) can be split into its positive terms, whose sum is bounded by ∑Iai, 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 {mi, mi ≥ −ci+δ,i in I} with ∑Imi = M, for some fixed δ>0.

Theorem. Let di = s(mi)/∂mi = aici/(mi+ci)2. If {mi} is a solution to GOTVS(I) , then

dj = dk, for all j,k in I.

Proof. If dj > dk, we could then obtain a net gain in S({mi}) by transferring some quantity δ from mk to mj.

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

mi = k√(aici) − ci, i in I,

where

k = (M+∑Icj)/∑I√(ajcj).

Proof. Solve di = aici/(mi+ci)2 = 1/k2, i in I, with the additional constraint ∑Imi = 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 {mi} be a solution to OTVS and define ti = (∂s(mi)/∂mi)mi=0 = ai/ci. For all j,p in I, if tjtp and mp > 0 then mj > 0.

Proof. Let us suppose mj = 0; as tj = (∂s(mj)/∂mj)mj=0tp = ap/cp > apcp/(mp+cp)2 = ∂s(mp)/∂mp, transferring some quantity δ from mp to mj would yield a solution without negative components and with greater S than {mi}.

Corollary. Let σ: II 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({ai}, {ci}, M)
m1,...,mn ← 0
knumM
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
········knumknum + cσ(i)
········kdenkden + √(aσ(i)cσ(i))
····end if
end for
kknum/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 ti 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 mi 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 {mi}.

No comments :

Post a Comment