1. OPTIMIZACIJSKI PROBLEM

optimizacijski problem, linearno programiranje, grafično reševanje LP z dvema spremenljivkama

definicija optimizacijski problem

Optimizacijski problem je trojica (Ω,f,opt), kjer je

• Ω … množica dopustnih rešitev

• f:Ω→R … ciljna (kriterijska) funkcija

• opt∈{min,max,inf,sup} … tip ekstrema

Če velja Ω=∅, je problem nedopusten, sicer pa je dopusten.

definicija optimalna rešitev

Optimalna rešitev (Ω,f,max) je x*∈ Ω, da velja ∀x∈Ω: f(x) ≤ f(x*). Vrednosti f(x*) pravimo optimalna vrednost.

Podobno, če opt=min.

kaj so nedopustni, dopustni, neomejeni, omejeni: optimalni in neoptimalni

nedopustni problem je problem, za katerega je Ω = Ø

dopustni problem je problem, za katerega Ω ≠ Ø

omejene probleme delimo na dve vrsti problemov:

1. optimalni problem za maksimum ali minimum je množica Ω zaprta, npr.

max x

p.p. x ≤ 2

2. neoptimalni problem za maksimum ali minimum je množica Ω odprta, npr.

min x

p.p. x>3

definicija linearno programiranje

Linearni program (LP) je optimizacijski problem, kjer so ciljna funkcija in vsi pogoji linearni.

definicija linearni program v standardni obliki

Linearni program je v standardni obliki, če

• iščemo max

• so vsi pogoji ≤

• so vse spremenljivke vecje ali enake 0

  
  

dokaži trditev:

vsak linearni program lahko ekvivalentno zapišemo v standardni obliki

zapiši trditev, kaj velja za linearni program

Naj bo Π =( Ω,f,max) linearni program. Potem velja:

1. Ω je konveksna množica.

2. Množica optimalnih rešitev Π je konveksna množica.

dokaži trditev:

Naj bo Π =( Ω,f,max) linearni program. Potem velja:

1. Ω je konveksna množica.

2. Množica optimalnih rešitev Π je konveksna množica.

1. Ω je presek polprostorov (in hiperravnin), torej je konveksna množica.

2. Če optimalnih rešitev ni, potem je množica optimalnih rešitev prazna, torej konveksna. Sicer naj bo c optimalna vrednost. Potem je množica optimalnih rešitev enaka

{x∈Ω | f(x)=c}

in je zato konveksna množica.

kaj velja za grafično reševanje linearnega programa z dvema spremenljivkama

Množica dopustnih rešitev Ω je politop (lahko neomejen). Množica optimalnih rešitev je lice tega politopa (oglišče, stranica, stranska ploskev, itd.). Optimalna vrednost (če obstaja) je vedno dosežena (tudi) v oglišču.