Lineáris programozás alapok

Itt egy lineáris programozás feladat…
Ezek a korlátozó feltételek…
Olyan egyenlőtlenségek, amelyek a síkban egy egyenes valamelyik oldalát adják meg.
Azok a pontok, amelyek mindegyik feltételnek megfelelnek, itt helyezkednek el.

Ezt úgy hívjuk, hogy a lehetséges megoldások halmaza.

Ez a pont itt például egy lehetséges megoldás.

Vagy éppen ez a másik pont is egy lehetséges megoldás.

De ez a pont nem egy lehetséges megoldás.

A lehetséges megoldások között van néhány olyan, amik az egyenesek metszéspontjaiban vannak.

Ezeket bázismegoldásnak nevezzük.
De van rájuk egy nagyon extrém elnevezés is…
Ezek a pontok a lehetséges megoldások halmazának extremális pontjai.

És most lássuk, hogy a lehetséges megoldások közül melyik lesz a legjobb…

Ezt a célfüggvény fogja nekünk megmondani.

Ezek itt a célfüggvény szintvonalai.

Minél följebb toljuk ebbe az irányba a célfüggvényt, annál nagyobb lesz.

És minél lejjebb toljuk, annál kisebb.

Vagyis a célfüggvény itt még nem olyan nagy...

Itt van az utolsó pillanat, amikor a célfüggvény még érintkezik a lehetséges megoldások halmazával...

A lehetséges megoldások halmazán belül tehát a célfüggvény itt lesz maximális.

Ezt hívjuk optimális megoldásnak.

Az optimális megoldás most egyben bázismegoldás is.

Ezért nagyon frappánsan úgy hívjuk,  hogy optimális bázismegoldás.

Hogyha a korlátozó feltételeken nem változtatunk...

De a célfüggvényen igen...

Akkor megeshet, hogy ehhez a célfüggvényhez már egy másik optimális bázismegoldás tartozik.

És a legviccesebb dolog még csak most jön...

Nézzük meg, hogy mi történik olyankor, ha a célfüggvény  szintvonalai éppen párhuzamosak az egyik egyenessel.

Mondjuk párhuzamos például ezzel...

Ilyenkor két optimális bázismegoldás is van.

És ennek a szakasznak minden pontja optimális megoldás.

Mivel pedig egy szakasz végtelen sok pontból áll...

A feladatnak végtelen sok optimális megoldása van.

Egy ilyen síkbeli lineáris programozás feladatnak tehát vagy egy optimális megoldása tud lenni...

Amikor a célfüggvény szintvonalai egyik egyenessel sem párhuzamosak.

Ilyenkor az optimális megoldás egyben optimális bázismegoldás.

Vagy az is lehet, hogy a célfüggvény szintvonalai párhuzamosak valamelyik egyenessel.

Ilyenkor két optimális bázismegoldás van és végtelen sok optimális megoldás.

Nézzük meg, hogy mik lesznek ebben az esetben az optimális megoldások.

Az optimális bázismegoldásokat ránézésre meg tudjuk mondani…

És felírhatjuk őket vektoros alakban is.

A többi optimális megoldást pedig így kapjuk:
 

Egy légitársaság Európán belüli és tengerentúli járatokat is indít egy repülőtérről. Naponta összesen 14 darab járat indítására van lehetőségük. Az Európán belül repülő gépek naponta kétszer is tudnak fordulni, míg a tengerentúli járatok csak egyszer. Naponta 18 pilótát és 60 utaskísérőt tudnak szolgálatba állítani. Az Európán belül repülő gépekre 2 pilóta és 4 utaskísérő szükséges, a tengerentúlra repülő gépekre 3 pilóta és 12 utaskísérő.

Hány darab Európán belül repülő és hány darab tengerentúlra közlekedő gépet működtessenek, ha az európai járatokon 2500 euró, a tengerentúli járatokon pedig 8000 euró profit keletkezik egy fordulóval és a cél a profitot maximalizálása?

Az Európán belül repülő gépek száma legyen x darab…
A tengerentúlra repülő gépek száma pedig y darab.

Sőt, létezik még egy ennél is jobb elnevezés…
Ezeknél az LP feladatoknál az x és y helyett inkább az x1 és x2 jelöléseket szoktuk használni.

Most pedig nézzük, mit kezdhetnénk ezzel a feladattal…
Hát igen, meg kéne oldani…

Jönnek a korlátozó feltételek.

Van x1 darab gép, ami kétszer is fordulhat…
És x2 darab, ami csak egyszer.
Összesen pedig 14 járat indulhat.

Az első feltétel meg is van.

Aztán itt jönnek a pilóták…
Nincs belőlük túl sok…

Meg is van a második korlátozó feltétel…

És az utaskísérők…

 
Most pedig ábrázoljuk a korlátozó feltételeket.

Meg is van a lehetséges megoldások halmaza.
És most jöhet a célfüggvény…
 
Itt is működik a trükk…
Csak ki kell találni ide valamilyen számot.

Teljesen mindegy, hogy milyen számot.
A 40 ezer mondjuk jó lesz.

Itt jönnek a célfüggvény szintvonalai…

És ez lesz az optimális megoldás.

A jelek szerint 3 darab gépnek kell Európán belül közlekednie, és 4 gépnek a tengerentúlra.

Ja, mondjuk az Európán belüli járatok naponta kétszer fordulnak…

Egy csokigyárban kétféle csokimasszát gyártanak. Az egyik a magas kakaótartalmú, a másik a krémesebb. A főbb alapanyagokból rendelkezésre álló készletek: 196 tonna kakaómassza, 576 tonna kakaóvaj, 88 tonna tejpor, 320 tonna cukor. Az egyéb összetevők korlátlanul rendelkezésre állnak.
A magas kakaótartalmú csokimasszához tonnánként 0,28 tonna kakaómassza, 0,48 tonna kakaóvaj és 0,2 tonna cukor szükséges. A krémesebb csokimasszához tonnánként 0,14 tonna kakaómassza, 0,36 tonna kakaóvaj, 0,08 tonna tejpor és 0,4 tonna cukor szükséges. 
Hány tonnát gyártsanak az egyik és a másik csokimasszából, ha azt szeretnék, hogy az összmennyiség a lehető legnagyobb legyen?

darab gép Európán belül
.
A magas kakaótartalmúból x1 tonnát gyártanak…
A krémesebből pedig x2 tonnát.

És most jöhetnek a korlátozó feltételek…

Kezdjük az első összetevővel, ami a kakaómassza…
 

Aztán jöhet a kakaóvaj…

Meg is van a lehetséges megoldások halmaza.

És a célfüggvény pedig…

És ez lesz az optimális megoldás.

A pont koordinátái pedig…
Hát igen, ezt most nem tudjuk ránézésre megmondani.

Az biztos, hogy a piros és a kék egyenes metszéspontja.
Vagyis meg kell oldanunk ezt az egyenletrendszert.

Egyenletrendszereket rengeteg módon meg lehet oldani.

Az egyik megoldási módszer, hogy kifejezzük valamelyik ismeretlent…

És aztán ezt visszarakjuk a másik egyenletbe.