Maksimeringsproblem
Moderators: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
La [tex]\sigma[/tex] være en permutasjon av [tex]\{ 1,2,...,n \}[/tex] slik at [tex]a_{\sigma(1)} \geq a_{\sigma(2)} \geq ... \geq a_{\sigma(n)}[/tex].
I summen ser vi at hver differanse av hvert par av elementer [tex]a_i,a_j[/tex] oppstår èn gang, så summen er lik
[tex]\sum_{i=1}^n\sum_{j=i}^n a_{\sigma(i)}-a_{\sigma(j)} \\ = (n-1)a_{\sigma(1)}-a_{\sigma(2)}-...-a_{\sigma(n)} \\ + (n-2)a_{\sigma(2)}-a_{\sigma(3)}-...-a_{\sigma(n)} \\ +... \\ + a_{\sigma(n-1)}-a_{\sigma(n)} \\ = \sum_{i=1}^n a_{\sigma(i)}\left( (n-i)-(i-1)\right)=\sum_{i=1}^n a_{\sigma(i)}(n+1-2i)[/tex]
Denne optimerer vi dersom vi lar [tex]a_{\sigma(i)} = 1[/tex] når [tex]n+1-2i \geq 0 \Leftrightarrow i=\lfloor \frac{n+1}{2} \rfloor[/tex] og 0 ellers.
Lar vi [tex]k=\lfloor \frac{n+1}{2} \rfloor[/tex], er den største summen altså
[tex]\sum_{i=1}^n n+1-2i = (n+1)k-k(k+1)=k(n-k)=\lfloor \frac{n+1}{2} \rfloor(n-\lfloor \frac{n+1}{2} \rfloor)[/tex].
I summen ser vi at hver differanse av hvert par av elementer [tex]a_i,a_j[/tex] oppstår èn gang, så summen er lik
[tex]\sum_{i=1}^n\sum_{j=i}^n a_{\sigma(i)}-a_{\sigma(j)} \\ = (n-1)a_{\sigma(1)}-a_{\sigma(2)}-...-a_{\sigma(n)} \\ + (n-2)a_{\sigma(2)}-a_{\sigma(3)}-...-a_{\sigma(n)} \\ +... \\ + a_{\sigma(n-1)}-a_{\sigma(n)} \\ = \sum_{i=1}^n a_{\sigma(i)}\left( (n-i)-(i-1)\right)=\sum_{i=1}^n a_{\sigma(i)}(n+1-2i)[/tex]
Denne optimerer vi dersom vi lar [tex]a_{\sigma(i)} = 1[/tex] når [tex]n+1-2i \geq 0 \Leftrightarrow i=\lfloor \frac{n+1}{2} \rfloor[/tex] og 0 ellers.
Lar vi [tex]k=\lfloor \frac{n+1}{2} \rfloor[/tex], er den største summen altså
[tex]\sum_{i=1}^n n+1-2i = (n+1)k-k(k+1)=k(n-k)=\lfloor \frac{n+1}{2} \rfloor(n-\lfloor \frac{n+1}{2} \rfloor)[/tex].
Ser fint ut dette.
Man kan også løse problemet ved å fiksere alle variablene unntatt [tex]a_i[/tex] og så betrakte uttrykket som en funksjon av [tex]a_i[/tex]. Da absoluttverdifunksjonen er konveks antar dette uttrykket maksimum på endepunktene av intervallet, og derfor må [tex]a_i=0[/tex] eller [tex]a_i=1[/tex]. Dette gjelder opplagt for alle [tex]i[/tex], så det eneste som gjenstår er å avgjøre hvor mange av variablene som skal være 0 og hvor mange som skal være 1, og selvfølgelig stå igjen med samme svar.
Man kan også løse problemet ved å fiksere alle variablene unntatt [tex]a_i[/tex] og så betrakte uttrykket som en funksjon av [tex]a_i[/tex]. Da absoluttverdifunksjonen er konveks antar dette uttrykket maksimum på endepunktene av intervallet, og derfor må [tex]a_i=0[/tex] eller [tex]a_i=1[/tex]. Dette gjelder opplagt for alle [tex]i[/tex], så det eneste som gjenstår er å avgjøre hvor mange av variablene som skal være 0 og hvor mange som skal være 1, og selvfølgelig stå igjen med samme svar.