Optimalisering med Brute Force:

Vi skal laga eit program som finn maksimum av funksjonen $ f(x) = - x^2 + 5x $ , der x er mellom 0 og 5. Dette skal vi gjera med ein såkalt Brute Force (rå kraft) -algoritme. Det betyr at vi skal rekna ut "alle" verdiane til funksjonen i definisjonsmengda, og deretter finna den største y-verdien med funksjonen max.

På same måten som med nullpunkt av funksjonar, så er det ikkje alltid mulig å finna eit ekstremalpunkt eksakt med rekning. Men her har vi valgt ein funksjon som er grei. Først finn vi den deriverte og set den lik null: $f'(x) = 0$ , dvs. $-2x+5 = 0$. Dette gir oss vår fasit: $x = 2.5$.

Men la oss først plotta funksjonen $f(x)$. Merk at vi her ikkje fyller listene x og y på forhånd med dummytal, men heller lagar ei tom liste som vi fyller på etter kvart vha. append.

In [7]:
# Importerer nødvendige biblioteker
import matplotlib.pyplot as plt

def f(x):
    return -x**2+5*x 

#Vi definerer først to tomme lister som skal fyllast etter kvart
x = []
y = []

# Løkke som fyller listene våre:
for i in range(6):
    x.append(i)
    y.append(f(i))
    
# Utskrift av data
plt.grid() # Lagar rutenett
plt.xlabel('$x$') # Merkjer x-aksen
plt.ylabel('$f(x)$') # Merkjer y-aksen
plt.plot(x, y, 'bo-.')
plt.show()

Vi ser med ein gong at vi ikkje kjem til å finna det riktige maksimalpunktet til $f(x)$. Tross alt har vi bare rekna ut 6 funksjonsverdiar, og ingen av disse treff makspunktet. Men vi fortset likevel med å finna maksimum av dei y-verdiane vi har å rutta med:

In [2]:
ymaks = max(y) # Finn toppunktet til f(x)
ymaksindex = y.index(ymaks) # Finn x-verdi vha index.
xmaks = x[ymaksindex] # Finn tilsvarande x-verdi.

print("Den største verdien av f(x) er ca.:",ymaks) 
print("Då er x lik",xmaks) 

Den største verdien av f(x) er ca.: 6
Då er x lik 2

Vi må opplagt rekna ut verdiar med mindre mellomrom. Men kor lite må mellomrommet vera? 0.1? 0.01? Det er umulig å svara på. For, som antyda ovanfor: vi kan aldri rekna ut alle verdiar! Men vi rekna ut så mange vi vil. Så la oss laga programmet vårt meir generelt. Vi vil for det første at programmet rekna med ein gitt nøyaktighet, som vi kan kalla dx. Vi vil også kunna bestemma kor stort intervall programmet skal søkja vha venstre og høgre grense:

In [3]:
fra = 0 # Venstre grense for definisjonsmengde
til = 5 # Høgre grense for definisjonsmengde
dx = 0.2 # Nøyaktighet. Denne bør gå opp i bredden

Om vi vil, kan vi leggja inn kode som les disse inn frå brukar, men dette får halda no. Vidare treng vi å rekna ut antalet punkt vi treng, basert på disse tala. Så vi definerer ein ny variabel bredde som er differansen mellom til og fra, og så finn vi antalet punkt som bredde dividert med dx pluss ein:

In [4]:
bredde = til - fra
N = int(bredde/dx + 1) #Antal punkt. Vi legg til ein for å få med "til"-punktet

Legg merke til at vi legg til 1 her fordi vi skal ha med begge endepunkta. Og vi gjer om N til eit heiltal (int) fordi vi skal bruka det som i ei løkke. Men vi er ikkje ferdige enno. No treng vi ein måte å rekna ut aktuell x-verdi inne i løkka. Dette vil bli ein funksjon av fra, dx og kor lang i løkka vi har komt. Vi startar med verdien fra, og så aukar vi talet med dx for kvar iterasjon:

In [5]:
# Løkke som fyller listene våre:
for n in range(N):
    xverdi = fra + dx*n
    x.append(xverdi)
    y.append(f(xverdi))

Tellevariabelen vår er n. Så hvis feks. n = 10, dx = 0.6 og fra er 0, så blir xverdi lik 0 + 0.6 * 10 = 6. Då er programmet vårt ferdig:

In [6]:
# Importerer nødvendige biblioteker
import matplotlib.pyplot as plt

def f(x):
    return -x**2+5*x  

#Vi definerer først to tomme lister som skal fyllast etter kvart
x = []
y = []

fra = 0 #Venstre grense for definisjonsmengde
til = 5 #Høgre grense for definisjonsmengde
dx = 0.2 #Nøyaktighet. Denne bør gå opp i bredde
bredde = til - fra
N = int(bredde/dx + 1) #Antal punkt. Vi legg til ein for å få med "til"-punktet

# Løkke som fyller listene våre:
for n in range(N):
    xverdi = fra + dx*n
    x.append(xverdi)
    y.append(f(xverdi))
    
# Utskrift av data
plt.xlabel('$x$') # Merkjer x-aksen
plt.ylabel('$f(x)$') # Merkjer y-aksen
plt.plot(x, y, 'bo-.')
plt.show()

ymaks = max(y) # Finn toppunktet til f(x)
ymaksindex = y.index(ymaks) # Finn indeksen til den største y-vedrien vha index.
xmaks = x[ymaksindex] # Finn tilsvarande x-verdi.

print("Den største verdien av f(x) er ca",ymaks) 
print("Då er x lik",xmaks)

Den største verdien av f(x) er ca 6.24
Då er x lik 2.4000000000000004

Vi får fremdeles ikkje fasitsvaret. Men no kan vi komma så nær vi vil ved å velja dx liten nok. Men når vi aukar nøyaktigheten, så aukar også antal punkt vi reknar ut. Så spørsmålet som melder seg då er: Er dette ein effektiv algoritme? Kanskje fins det betre algoritmar enn denne? Det kan henda at for akkurat dette problemet, så er brute force ein grei metode. Men det fins problem der andre metodar er betre.

Oppgaver

  1. Kjør programmet over med andre verdiar for fra, til og dx. Får du det same svaret?
  2. Ei bedrift produserer og selgjer ei vare. Kostnadane til bedriften er gitt ved $K(x) = 8.5x^2 + 25x + 11900$, der $x$ er antall enheter som blir produsert. Inntektene er gitt ved $I(x) = 790x$. Lag eit program som finn ut den vareproduksjonen som gir størst overskudd.
  3. Et A4-ark kan brettast til ein boks ved å bretta opp kantane som er igjen etter å ha klipt ut kvadrater med sidelengde x i kvart hjørne av arket. For kva x er volumet størst?
  4. Lag eit program som finn arealet av det største rektangelet som kan innskrivast i ein rettvinkla trekant med sidene 3m, 4m og 5m. (Hint: Sjå på hypotenusen som ei rett linje på formen $l=ax+b$)