Matematisk programmering er en matematisk metode for å bestemme de optimale (eller beste) verdiene til en størrelse, gitt noen betingelser. Det er vanlig å skille mellom diskret optimering og kontinuerlig optimering. Matematisk programmering kalles også optimering eller optimalisering.

Faktaboks

Også kjent som

optimering, optimalisering

Eksempler

Diskret optimering

Anta at man har et antall byer som man ønsker å besøke én og bare én gang. Man skal starte og ende turen i samme by. Det finnes mange mulige reiseruter, men målet er å finne den korteste reiseruten. Størrelsen som skal optimeres, er total reiselengde, og kriteriet er at man skal besøke hver by bare én gang og starte og ende samme sted.

Når antall byer blir stort, er dette et svært vanskelig problem. Dette kalles handelsreisendeproblemet (engelsk the traveling salesman problem).

Kontinuerling optimering

Anta man har en snor med fast lengde. Det å finne en form på snoren slik at den omslutter et område med størst mulig areal, er en oppgave som kan løses med kontinuerlig optimering.

Et annet eksempel er å se på funksjonen \(f(x)=x^2\), definert for alle \(x\), som beregner arealet av et kvadrat med sidekant \(x\). Her ønsker man å finne den minste verdien for funksjonen. Her ser man at den minste verdien er \(0\) (som antas for \(x=0\)), siden et kvadrat aldri kan være negativt, og funksjonen er null akkurat når \(x\) har verdien null.

Lineær programmering

Eksempel på simpleks-metoden
Det mulige området er skravert, og det optimale punktet er \(A\).
Eksempel på simpleks-metoden
Lisens: CC BY SA 3.0

En vanlig type matematisk programmering er lineær programmering. Her er funksjonen som skal optimeres, i tillegg til alle bibetingelsene, lineære funksjoner. I dette tilfellet fins den kjente simpleks-metoden, som ble utviklet av amerikaneren George Dantzig (1914–2005) i 1947. Ved dynamisk programmering brukes en flertrinns avgjørelsesmetode.

Eksempel

En bonde har et jorde på inntil \(20\) arealenheter som han kan dyrke med hvete eller rug. Anta han dyrker et \(H\) arealenheter hvete og \(R\) arealenheter rug. Da blir \(H+R<20\). Anta at han må minst dyrke \(4\) arealenheter rug og mellom \(2\) og \(8\) arealenheter hvete, det vil si \(R>4\) og \(2<H<8\). Hvis fortjenesten er 2000 kroner per arealenhet for hvete og 1000 kroner per arealenhet for rug, hvor mye hvete og rug skal bonden dyrke for å optimalisere fortjenesten? Fortjenesten \(F\) er altså gitt ved funksjonen \(F=2000H+1000R\).

Simpleks-metoden sier at den optimale løsningen må ligge i et av hjørnene på figuren. Ved sammenligning kan man se at verdien i punktet \(A\) er størst.

Anvendelser

Særlig lineær programmering, men også andre typer matematisk programmering, brukes i praksis for eksempel i oljeindustrien, ved utarbeiding av timeplaner i skolen og ved makroøkonomisk planlegging. Matematisk programmering kan omfatte tusener av variable og betingelser, slik at datamaskiner må brukes for beregningene.

Betegnelsen programmering har imidlertid ikke noe å gjøre med programmering av datamaskiner. Dette ordet ble tidligere brukt i den amerikanske hæren med betydningen «logistikk».

Les mer i Store norske leksikon

Kommentarer

Kommentarer til artikkelen blir synlig for alle. Ikke skriv inn sensitive opplysninger, for eksempel helseopplysninger. Fagansvarlig eller redaktør svarer når de kan. Det kan ta tid før du får svar.

Du må være logget inn for å kommentere.

eller registrer deg