Linearno programiranje
Ű
6. korak: Izračunamo vrednosti ciljne funkcije v vseh ogliščih konveksnega poligona: (0, 200), (200, 0) in (150, 100):
Metode optimiziranja so danes nekaj povsem vsakdanjega in se jih ponavadi niti ne zavedamo. Ko gremo v trgovino, imamo s seboj seznam stvari (v spominu ali napisane na papirju), ki jih bomo kupili, radi bi jih seveda dobili po najbolj ugodni ceni, ves čas pa nas opominja misel, da je v denarnici omejena količina denarja.
f(x, y) = 6,5 ∙ 0 + 7 ∙ 200 = 1400 f(x, y) = 6,5 ∙ 200 + 7 ∙ 0 = 1300 f(x, y) = 6,5 ∙ 150 + 7 ∙ 100 = 1675
IČI
IČI
Rešitev primera zahteva še nekaj razlage, saj ciljne funkcije pri reševanju sploh še nismo omenili.
1. korak: Izberemo in imenujemo spremenljivke, prvi komplet naj bo x, drugi komplet pa y. 2. korak: Napišemo ciljno funkcijo f(x, y) = 6,5x + 7y. 3. korak: Napišemo omejitve:
150 100 1675
RA
100 80 1210
200 0 1300
0 200 1400
Na kokošji farmi pitajo piščance z dvema vrstama hrane. Piščanec mora na dan pojesti vsaj 8 enot hrane A in vsaj 15 enot hrane B. Na tržišču je mogoče kupiti hrano dveh proizvajalcev. Prvi prodaja paket X, ki vsebuje 2 enoti A in 3 enote B in stane 19 denarjev, drugi pa ponuja paket Y, ki vsebuje 2 enoti A in 4 enote B po 24 denarjev. Koliko posameznih paketov naj dnevno kupi farma, da bo strošek najmanjši? 1. korak: Imamo dve spremenljivki, število paketov X naj bo x in število paketov Y naj bo y. 2. korak: Ciljna funkcija je f(x, y) = 19x + 24y, iščemo pa njeno najmanjšo vrednost. 3. korak: Omejitve: A B
X 2 3
x ≥ 0, y ≥ 0 število enih in drugih kompletov mora biti nenegativno
2x + 2y ≥ 8
2x + 3y ≤ 600 omejitev za zvezke
3x + 4y ≥ 15
x + y ≤ 500
omejitev za mape
x≥0
2x + y ≤ 400
omejitev za peresa
y≥0
4. korak: Narišemo premice in označimo polravnine v istem koordinatnem sistemu.
100 100 1350
NA
Zaloga 600 500 400
100 50 1000
LO V
Komplet 2 3 1 1
Zgled 2
0 0 0
DE
RA
NA
Komplet 1 2 1 2
LO V
Zvezki Mape Peresa
x y c = f(x, y)
ZL
Graf ciljne funkcije f(x, y) = 6,5x + 7y je premica 6,5x + 7y = c, ki se imenuje nivojnica funkcije. Če za konstanto c izberemo različne pozitivne vrednosti, dobimo snop premic, ki so na sliki narisane z rdečo barvo.
ZL
Pred začetkom šolskega leta v trgovini načrtujejo prodajo šolskih potrebščin. V skladišču imajo 600 zvezkov, 500 map in 400 peres, iz katerih bodo naredili dve vrsti paketov. V prvem bosta dva zvezka, mapa in dve peresi, v drugem pa trije zvezki, mapa in pero. Cena prvega kompleta je 6,50 evra, drugi pa bo stal 7 evrov. Koliko posameznih kompletov morajo pripraviti, da bo zaslužek največji?
CA
CA
Očitno je v zadnjem primeru iztržek največji. Zato je optimalno pakiranje 150 prvih in 100 drugih kompletov.
V optimiziranju torej nastopajo ciljna funkcija in omejitve. Če je ciljna funkcija linearna in če imajo omejitve obliko linearne enačbe ali neenačbe, tako optimiziranje imenujemo linearno programiranje. Zgled 1
275
5. korak: Presek vseh množic imenujemo dopustno oz. izvršljivo območje, ki je vedno konveksna množica.
Spoznali boste:
DE
274
Y 2 4
Minimum 8 15
4. korak: Narišemo polravnine v istem koordinatnem sistemu in označimo njihov presek.