Olinjär optimering

Linjär optimering

I kurserna Matte 1 och Matte 2 har vi gått igenom hur vi kan använda linjära funktioner och räta linjens ekvation. Låt oss snabbt repetera hur vi kan beskriva linjära samband med hjälp av räta linjens ekvation.

Sammanfattning och repetition av viktiga regler till räta linjen. 

Innan vi går in på linjär optimering så ska vi repetera två exempel på hur vi löser linjära olikheter. Vill du repetera mer finns det i Matte 1.

Vi börjar med att lösa en ekvation med olikhet algebraiskt.

$$\frac{2x+5}{-3}> 2$$

Vi börjar med att multiplicera med -3 på båda sidor, och eftersom det är ett negativt tal måste vi vända på olikhetstecknet. 

$$\frac{-3(2x+5)}{-3}< 2\cdot (-3)$$

$$2x+5 < -6 $$

$$2x < $$

$$x < -5,5$$

Nästa exempel kollar vi på hur vi löser olikheter med hjälp av grafer, det kommer vi använda mest i detta avsnitt. Graferna nedan visar två funktioner \(f(x)= x^2+2 \) (blå parabel) och \(g(x)=x+4 \) (röd linje)

I punkterna är f=g, första punkten är x = -1 och andra x = 2. 

f > 0 för alla värden på x då parabeln ligger ovanför x-axeln. 

g = 0 när x = -4, alltså är g > 0 om x > -4 och g < 0 om x <

Linjär optimering

Linjär optimering handlar ifall att optimera en fuktion \(z\). Denna funktion existerar en linjär funktion inom flera variabler. Allmänt skriver vi funktionen som

$$z=\sum_{k=1}^nc_kx_k$$

Det generella linjära optimeringsproblemet går ut på att minimera ovan nämnda funktion, under bivillkoren:

$$\begin{align}\begin{cases}a_{1,1}x_1+a_{1,2}x_2+\dots+a_{1,n}x_n\leq b_1\\a_{2,1}x_1+a_{2,2}x_2+\dots+a_{2,n}x_n\leq b_2\\ \vdots\\a_{m,1}x_1+a_{m,2}x_2+\dots+a_{m,n}x_n\leq b_m\end{cases}\end{align}$$

Alla \(x_k\) står för dem olika beslut som är kapabel tas samt konstanterna \(c_k\) är kostnaderna för varenda beslut. Bivillkoren går för att skriva många mer kompakt med hjälp av matriser. 

Låt A artikel matrisen bestående av elementen \(a_{i,j}\), \(x\) får företräda kolumnvektorn tillsammans med elementen \(x_1,\dots,x_n\) och \(b\) är kolumnvektorn med elementen \(b_1,\dots,b_n\). Då kan oss skriva angående bivillkoren som

$$Ax\leq b$$

Bivillkoren utformar ett plats i \(n\) dimensioner. allmänt kan detta sammanfattas som:

$$\begin{align}\begin{cases}\min \sum_{k=1}^nc_kx_k\\ \text{s.a. }Ax\leq B\end{cases}\end{align}$$

där s.a. står för "sådant att".

Linjär optimering i numeriskt värde dimensioner

För

  • olinjär optimering

    • Optimeringslära

    Optimeringslära, optimeringsteori eller optimering (läs mer om optimering i allmän betydelse) är den matematiska lära som beskriver olika metoder för hur ett optimalt värde, det vill säga ett maximum eller ett minimum, kan erhållas ur en funktion givet vissa förutsättningar samt givet vissa restriktioner, så kallade bivillkor.

    Inom optimeringsläran används olika så kallade modeller, matematisk programmering, för att ställa upp och lösa olika konkreta problem. Linjära optimeringsproblem behandlas med hjälp av linjärprogrammering (linjär-programmering som förkortas LP), icke-linjära optimeringsproblem med hjälp av icke-linjärprogrammering (icke-linjär-programmering, förkortat NP av engelskans Non-linear Programming) och heltaliga optimeringsproblem med hjälp av heltalsprogrammering (förkortat IP av engelskans Integer Programming).

    Inom optimeringsområdet grafer och nätverk optimeras sådant som maximalflöden, minimikostnadsflöden, billigaste väg, billigaste uppspännande träd (exempelvis el‑nät) samt sådana problemkomplex som går under beteckningen handelsresandeproblemet.

    Se även

    [redigera | redigera wikitext]