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*> 0 for all

_{i}*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*in

_{i}, i*I*} with ∑

_{I}

*m*=

_{i}*M*that maximizes

*S*({

*m*}) = ∑

_{i}_{I}

*s*(

*m*) = ∑

_{i}_{I}

*a*/(

_{i}m_{i}*m*+

_{i}*c*). Note that in OTVS we imposed the tighter restriction

_{i}*m*≥ 0.

_{i}**Lemma.** Consider the space of all distributions {*m _{i}*,

*m*> −

_{i}*c*in

_{i}, i*I*} with ∑

_{I}

*m*=

_{i}*M*. The limit of

*S*({

*m*}) when min({

_{i}*m*+

_{i}*c*}) → 0 is −∞.

_{i}**Proof.**∑

_{I}

*s*(

*m*) can be split into its positive terms, whose sum is bounded by ∑

_{i}_{I}

*a*, and its negative terms, among which at least one tends to −∞.

_{i}**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 ∑

_{I}

*m*=

_{i}*M*, for some fixed

*δ*>0.

**Theorem.** Let *d _{i}* =

*∂*

*s*(

*m*)/∂

_{i}*m*=

_{i}*a*/(

_{i}c_{i}*m*+

_{i}*c*)

_{i}^{2}. If {

*m*} is a solution to GOTVS(

_{i}*I*) , then

*d _{j}* =

*d*, for all

_{k}*j*,

*k*in

*I*.

**Proof.**If

*d*>

_{j}*d*, we could then obtain a net gain in S({

_{k}*m*}) by transferring some quantity

_{i}*δ*from

*m*to

_{k}*m*.

_{j}**Corollary.** GOTVS(*I*) has a unique solution of the form

*m _{i}* =

*k*√(

*a*) −

_{i}c_{i}*c*,

_{i}*i*in

*I*,

*k* = (*M*+∑* _{I}c_{j}*)/∑

*√(*

_{I}*a*).

_{j}c_{j}**Proof.**Solve

*d*=

_{i}*a*/(

_{i}c_{i}*m*+

_{i}*c*)

_{i}^{2}= 1/

*k*

^{2},

*i*in

*I*, with the additional constraint ∑

*=*

_{I}m_{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*} be a solution to OTVS and define

_{i}*t*= (∂s(

_{i}*m*)/∂

_{i}*m*)

_{i}_{mi=0}=

*a*

_{i}/

*c*. For all

_{i}*j*,

*p*in

*I*, if

*t*≥

_{j}*t*and

_{p}*m*> 0 then

_{p}*m*> 0.

_{j}**Proof.** Let us suppose *m _{j}* = 0; as

*t*= (∂s(

_{j}*m*)/∂

_{j}*m*)

_{j}_{mj=0}≥

*t*=

_{p}*a*/

_{p}*c*>

_{p}*a*/(

_{p}c_{p}*m*+

_{p}*c*)

_{p}^{2}= ∂s(

*m*)/∂

_{p}*m*transferring some quantity

_{p},*δ*from

*m*to

_{p}*m*would yield a solution without negative components and with greater

_{j}*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.

**OTVS**({*a _{i}*}, {

*c*},

_{i}*M*)

*m*

_{}_{1},...,

*m*← 0

_{n}*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

end for

*t*downward and maintain the running numerator and denominator of the value that

_{i}*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*would be negative, we know we've gotten to the cutoff index

_{i}*τ*and that the

*k*calculated so far is the actual one, so we just use it for computing the final values of {

*m*}.

_{i}
## No comments :

## Post a Comment