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).
Eksempel
Et eksempel kan være systemet
Legg merke til skrankene 7 og 8 som er ikke-negativitetsskranker. Disse antas ofte implisitt, men er fornuftig å ta med siden man normalt skal programmere det lineære systemet inn i et eller annet modelleringsverktøy på datamaskinen. Vi ønsker å være så presise som mulig. Eksemplet gir følgende grafisk fremstilling:
Figur 1: Eksempel på lineært system
Det skraverte området er det vi kaller for mulighetsområdet, og er de tilegnelsene vi kan gi beslutningsvariablene uten at det bryter med skrankene 4 til 8. Vi kaller alle disse tilegnelsene for mulige løsninger, mens tilegnelsene som er utenfor kalles for umulige løsninger. En løsning trenger altså hverken være optimal eller gyldig for å kalles en løsning. Alle hjørnene på mulighetsområdet kaller vi for hjørneløsningene. Disse er sentral fordi en eller annen optimal løsning finnes alltid i en av disse. Vi kan altså ha flere optimale løsninger som har til felles at de har samme optimal verdi når tilegnede beslutningsvariablene brukes på objektfunksjonen. Når det kommer til hjørneløsninger så kan det også finnes optimale løsninger som ikke finnes i hjørnene, men langs en av kantene. En kant defineres her som en linje mellom to nærliggende hjørner.
La oss velge en objektfunksjon
Vi ønsker altså å maksimere funksjon 9 gitt skrankene 4 til 8. Altså prøver vi å finne de tallene vi må tilegne beslutningsvariablene, , for at objektfunksjonen,
, skal være størst mulig uten å falle utenfor mulighetsområdet? Man kan grafisk løse dette ved å tilegne et rimelig tall til objektfunksjonen og parallellforskyve linjen slik at den når grensen til mulighetsområdet. Dette inntreffer i en av hjørneløsningene eller parallelt langs en av kantene. Er det en enkelt hjørneløsning så er dette punktet den optimale løsningen, mens hvis det skjer langs en kant så kan man velge et punkt langs kanten eventuelt på en av selveste hjørneløsningene på endene.
Figur 2: Eksempel på optimering av lineært problem
Vi kan her se at forskyvingen stopper ved og
som gir
. Dette resultatet kan også løses analytisk ved hjelp av simpleksmetoden.