4.optimal sotarge on tapes theorem

4. If l1≤l2≤…≤ln, then the ordering ij=j, 1≤j≤ n, minimizes ∑ ∑ lij over all possible permutations of the ij. K=1 j=1

Proof: Let I=i1,i2,…in be any permutation of the index set {1,2,…,n} then
n k n
d(I)= ∑ ∑ lij =∑ (n-k+1)lik
K=1 j=1 K=1

If there exist a and b such that alib,then interchanging ia and ib results in a permutation I’ with


d(I’}= ∑(n-k+1) lik + (n-a+1) lib +(n-b+1) lia
k
k≠a
k≠b


Subtracting d (I’) from d (I), we obtain

d(I)-d(I’)= (n-a+1)( lia - lib)+(n-b+1)( lib - lia)
= (b-a) ( lia - lib )
> 0
Hence ,no permutation that is not in nondecreasing order of the li‘s can have minimum d. It is easy to see that all permutations in nondecreasing order of the li’s have the same value. Hence the ordering defined by ij=j, 1≤j≤ n , minimizes the d values.