Matematika 1 GTK epizód tartalma:
Már mutatjuk is, hogyan néznek ki a korlátozó feltételek, mit jelent a lehetséges megoldások halmaza, mik azok az extremális pontok, hogyan néz ki a célfüggvény és hogyan kapjuk meg az optimális megoldást. Azt is megnézzük, hogy mi a különbség az optimális megoldás és az optimális bázismegoldás között, mikor lesz az optimális megoldás extremális pont és mikor nem. Aztán jön egy izgalmas eset, amikor a célfüggvény szintvonalai párhuzamosak az egyik határoló egyenessel, és így két extremális pont is optimális bázismegoldás lesz, a köztük lévő szakasz minden pontja pedig optimális megoldás. Vagyis ebben az esetben két darab optimális bázismegoldás és végtelen sok optimális megoldás lesz.
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: