Lineær programmering og optimering – eksempel, del II.

« Del I

Et viktig ledd i å kunne løse lineære problemer er å kunne oversette problemene til matematiske modeller. Det er ikke alltid opplagt hvordan man bør modellere problemet og det finnes noen ganger flere veier man kan gå for å finne en optimal løsning. For å bli god i modellering trenger man hovedsakelig trening. Her skal vi ta for oss ett eksempel på både modellering og grafisk løsing. I neste innlegg vil ta for oss simplex-metoden som er en analytisk algoritme for å løse lineære systemer.

Når vi leser en oppgave i lineær programmering så er det greit å merke seg nøkkelinformasjon, samt notere seg egenskaper ved problemet i tabeller.

Continue reading

Lineær programmering og optimering – innføring, del I.

Del II »

Lineær optimering handler om det å velge verdier for et lineært system av beslutningsvariabler på en slik måte at den optimerer en objektfunksjon. Et lineært system er en mengde likninger og ulikeheter som beskriver det man kaller for skrankene til systemet, mens objektfunksjonen er en funksjon som beskriver hva man får ut av systemet. En skranke er en begrensning for hvilke verdier beslutningsvariablene kan ha. Et system kan ha flere funksjoner som beskriver egenskaper ved den, men bare en objektfunksjon som man skal prøve å optimere. Når man snakker om å optimere så er det normalt et ønske om å maksimere eller minimere objektfunksjonen. At systemet er lineært betyr at likningene og ulikhetene, det vil si skrankene, utgjør kun en sum av konstanter og vektede variabler. Den tar en av formene

hvor er konstanter og er beslutningsvariabler.

Beslutningsvariablene er variablene vi ønsker å velge slik at man optimerer objektfunksjonen. Med bare to beslutningsvariabler kan vi representere dette grafisk med to dimensjoner. Av konvensjon velger vi på førsteaksen (horisontal akse) og for andreaksen (vertikal akse).

Continue reading