KURZUS: Informatikai rendszerek alapjai

MODUL: Matematikai számítások Excellel

3. lecke: Termelési és optimalizálási feladatok megoldása Solverrel

Cél: Mint ahogy az előző lecke bevezetésénél is írtuk, ipari-gazdasági környezetben gyakran találkozunk olyan problémákkal, amelyeknek a megoldása valójában lineáris egyenletrendszerek megoldását jelenti, vagy arra vezethető vissza. A mostani leckében tárgyalt termelési és optimalizálási feladatok is ebbe a csoportba tartoznak.

Ezekhez a problémákhoz az Excel Solver bővítménye az előző leckében már bemutatott nagyon hatékony támogatást nyújtja. Mindezt Ön is jól tudja majd a saját munkájában alkalmazni, ha megismeri a megfelelő feladattípusokat és azok megoldási módszereit.

Fontos azonban hangsúlyozni, hogy a mi tananyagunkban a megoldáshoz szükséges modellt a hallgatóság lényegében készen kapja (a feladat már ismert, csak esetleg más "csomagolásban" vagy kisebb módosításokkal szerepelt). A megoldás tehát a valós életben az itt megköveteltnél komplikáltabb és időigényesebb is lehet. Az ilyen - az általunk most elvártnál általánosabb - problémamegoldó-képesség kifejlesztéséhez a leckében javasoltnál jóval nagyobb idő- és energiaráfordítás szükséges.

Megjegyezzük, hogy az Excel program mellett más - akár erősebb - szoftverek is használhatók ilyen típusú problémák megoldásához (pl. a MATLAB rendszer is), de ezt mi a jegyzetben nem tárgyaljuk.

Követelmények: Ön akkor sajátította el megfelelően a tananyagot, ha (az Excel segítségével)

  • saját szavaival képes definiálni a lineáris programozás feladatát és következő alapfogalmait: tevékenységi/döntési változók, lineáris egyenlet vagy egyenlőtlenségrendszer a korlátozó feltételekkel, célfüggvény, optimális megoldás (egy vagy több), érzékenységvizsgálat;
  • meg tudja határozni, hogy az adott (lineáris programozási) feladat a megismertek közül melyik feladattípusba tartozik;
  • adott matematikai modell esetén meg tudja határozni, hogy melyek azok a konstansok, korlátozó feltételek, amelyeket meg kell adni a Solveres megoldáshoz;
  • a leckében szereplő feladattípusokra - a konkrét kísérőszöveg elemzésével - ténylegesen be is tudja állítani a Solver ablakában a szükséges paramétereket;
  • képes a beállítás után a feladat Solveres megoldására és az eredmények értelmezésére.

Időszükséglet: A tananyag elsajátításához (a feladatok megoldásával együtt) hozzávetőlegesen 3 órára lesz szüksége.

Kulcsfogalmak

  • Lineáris egyenlet vagy egyenlőtlenségrendszer, matematikai modell;
  • Tevékenységi/döntési változók, célfüggvény;
  • Optimális megoldás (adott feltételek mellett);
  • Érzékenységvizsgálat.
A lineáris programozásról általában, alapfogalmak

Ebben a leckében termelési és optimalizálási feladatokat fogunk megoldani az Excel segítségével. Az érintett témakör a lineáris programozás tudományterület része. (A lecke végén röviden a nemlineáris feladatok megoldására is kitérünk, ill. találkozhatunk még ilyen jellegű feladattal a függvényábrázolással foglalkozó leckében is.) A "programozás" megnevezés itt nem a hagyományos értelemben tekintendő - tehát nem futtatható programkód készítése a cél, hanem egy optimumszámítási feladat megoldása.

A lineáris programozás feladata: korlátozottan rendelkezésre álló gazdasági erőforrások lehető legjobb (optimális) elosztása egymással versenyző tevékenységek között a minél nagyobb gazdasági haszon elérése céljából.

Egy adott feladat megoldása az alábbiak szerint érhető el. A konkrét problémát szinte mindig szövegesen megfogalmazva kapjuk meg, ebből kell "kihámozni" a számunkra lényeges információkat. Ezután egy matematikai modellt (tömör, formális leírás) kell készíteni a feladatról, és ez alapján meg kell határozni a megoldás módját. A következő teendő a Solver felparaméterezése és a tényleges gépi megoldás. Végül - ha szükséges - elemeznünk kell a megoldás jellemzőit, ill. a megoldhatóság korlátait (például hogy a bemenő paraméterek milyen mértékű változása esetén marad érvényben a megoldás).

A matematikai modell idealizált reprezentációt ad a feladatról (közelíti a valóságot), matematikai jelekkel és szimbólumokkal. Több előnye is van a szöveges leírással szemben, például:

  • Tömören írja le a problémát, könnyen módosítható;
  • Könnyebb benne áttekinteni az ok-okozati összefüggéseket;
  • Egyidejűleg tudjuk kezelni az összes kapcsolatot;
  • Nyilvánvalóan látszik, ha még további adatok kellenek az elemzéshez;
  • Jól támogatja a számítógépes megvalósítást.

A modell elemei a következők:

  • Tevékenységi/döntési változók (változnak a megoldás során, jelölés általában: x);
  • Állandók, konstansok;
  • Egyenletek, egyenlőtlenségek (korlátozó feltételek a fenti konstansok és változók felhasználásával, A és b értelmezhető a már ismert módon);
  • Célfüggvény (haszon mérőszáma; pl. maximális haszon, minimális költség/selejt; jelölés általában: c).

Jegyezze meg a matematikai modell elemeit és meghatározásukat!

A modell felállítása gyakran nem egyszerű, hasonló feladatok megoldásánál szerzett rutin segíthet. Összpontosítsunk a következő kérdésekre: Milyen ráfordítási értékek és korlátozások vannak a feladatban? Hogyan írjuk fel a célfüggvényt?

A modell alapján a lineáris programozási feladatok típusokba sorolhatók (az osztályozás alapja: elméleti lineáris programozás, ezek közül néhány fontosabb:

  • Maximumfeladat: a célfüggvény maximuma az optimum (maximális haszon);
  • Minimumfeladat: a célfüggvény minimuma az optimum (minimális önköltség);
  • Normálfeladat: olyan maximumfeladat, ahol a konstans oszlop együtthatói nemnegatívak;
  • Egészértékű feladat (csak egész megoldások jöhetnek szóba).

Megjegyzés: Informatika tananyagunknak nem része, de érdekes - és komplex, bonyolult - terület az optimalizálási feladatok számítógép nélküli, papír-ceruza módszerrel történő megoldása. Speciálisan, egyszerűbb esetekben használható a grafikus megoldás (kétváltozós feladatoknál általában ez könnyen kivitelezhető). Általánosan alkalmazható hatékony megoldó eljárás az ún. szimplex módszer, amikor bázisvektor-transzformációval több lépésben jutunk el a megoldásig. A részletek iránt érdeklődőknek a lineáris programozással és operációkutatással foglalkozó szakirodalmat ajánljuk.

A gépi megoldás technikáját és módszereit a konkrét példáknál mutatjuk be majd részletesen.

Most csak összefoglalóan leírjuk, hogy - mint már tudjuk - a gépi megoldás célja is egy (sokszor többváltozós) lineáris célfüggvény optimumának megkeresése. Eközben a változókra többféle korlátozást kell betartani (ezeket meg kell adni az Excelben). A korlátozások a következők lehetnek:

  • A változók bizonyos lineáris kombinációi korlátosak;
  • A változók nem negatívok;
  • A változók egészek;
  • A változók binárisak (csak 0 vagy 1 értéket vehetnek fel).

A kapott (optimális) megoldást gyakran fontos tovább elemezni. Érdekes lehet például, hogy

  • Az optimum egyedi vagy többes (ilyenkor más optimális megoldás is létezik, egyet találtunk meg),
  • Az optimum globális (abszolút) vagy csak lokális (utóbbi esetben valószínűleg jobb optimum is található)
  • Ha az optimum nem globális, hogyan tudunk jobb optimumot találni?

Végül, az utolsó lépésben célszerű lehet megvizsgálni az alkalmazhatóság korlátait. Ez az ún. érzékenységvizsgálat egy olyan elemző eljárás, amelynek során felderítjük, hogy milyen hatással vannak a megtalált megoldásra a modell paramétereinek értékeiben (A, b és c) bekövetkezett változások. Például: hogyan változtatja meg az optimális megoldást, ha új feltételt írunk a modellbe, vagy módosítjuk a célfüggvény együtthatóit?

Nálunk most (az Informatikai rendszerek alapjai, ill. a Számítási módszerek tárgyból) az alábbiak szerint oldjuk meg a feladatokat, ill. várjuk el a feladatok megoldását:

  • A matematikai modell (lényegében) adott (vagy ténylegesen adott, vagy a bemutatott példákhoz nagyon hasonlít);
  • A számítógépes megvalósítást és megoldást kell megtanulni (Excelben, Solverrel).

Ez utóbbihoz tudni kell az adatok korrekt begépelését/megadását (korlátozó feltételek, célfüggvény) és a Solver felparaméterezését, beállításait (pontosság, iterációs lépésszám). A tényleges megoldás után pedig mindenkinek képesnek kell lenni értelmezni az eredményt, azaz

  • Fel kell ismerni az esetleges hibákat (sokszor a Solver kiírja, de pl. tervezési hiba miatt akár nagyságrendi eltérés is lehet);
  • És ehhez esetleg korlátozott érzékenységi elemzést el kell tudni végezni.

Az Excel nagyon hatékony eszközökkel támogatja az érzékenységvizsgálatot, de ezt mi csak érintőlegesen tárgyaljuk.

A lineáris programozási feladatok megoldása
1. Példa - gépes termékgyártás

Egy vállalat kétféle termék gyártását akarja bevezetni. A két termék gyártása három gépen történik (munkafázisokban). Az első termék egy darabjának megmunkálásához szükséges gépidők rendre 1, 1, 1 gépóra; a második termék egységének gépidőszükséglete pedig rendre 2, 3, 1 gépóra. Az egyes gépek rendelkezésre álló kapacitása 25, 33, 20 gépóra (egy adott időszakban). Az egyes termékek várható eladási egységára rendre 3 és 5 pénzegység. Milyen termékösszetételben gyártson a vállalat, ha maximális árbevételre törekszik úgy, hogy a gyártás során a gépek kapacitását nem lépheti túl? (Félkész termék nem gyártható.)

A matematikai modell felállításához jelölje x 1 és x 2 az egyes termékekből gyártandó mennyiséget (döntési változók). Az egyenleteket/egyenlőtlenségeket a gépekre írjuk fel, pl. az első gépre vonatkozóan: ha 1 óra alatt 1 db első termék készül el, akkor x 1 db termék megmunkálásához 1 x 1 óra kell. Hasonlóan a második termékre: x 2 db termék megmunkálásához 2 x 2 óra szükséges. A rendelkezésre álló kapacitás 25 óra, ezt nem léphetjük túl. A kész egyenlőtlenségrendszer és a célfüggvény:

x 1 +2 x 2 25
x 1 +3 x 2 33
x 1 + x 2 20
x 1 ;  x 2 0
3 x 1 +5 x 2 max

Az Excelben történő megoldást több különféle módon mutatjuk be, az egyszerűbbtől a bonyolultabbakig haladva.

Az 1. terv szerint helyezzük el az adatokat a táblázatban a következő módon.

A gépes termékgyártási feladat 1. adatelrendezése
1. ábra

A döntési változók (módosuló cellák) az A oszlopban szerepelnek, alkalmas kezdőértékkel, ez például egynek választható. A célfüggvény kötelezően egyetlen cellában, a célcellában helyezkedik el. Ennek a cellának olyan képletet kell tartalmaznia, amely a módosuló celláktól függ. A gépkapacitásra vonatkozó feltételek a táblázatban többféle módon is megadhatók. Most először válasszuk azt az egyszerű megközelítést, hogy a korlátozások bal oldalát a B oszlop celláiba írjuk be.

Idézze fel az előző leckében tanultakat a Solver paramétereiről.

Ezután indítsuk el a Solvert. A célérték beállítása nyilvánvaló. A gépkapacitási egyenlőtlenségek (korlátozások) bal oldala hivatkozással adandó meg (most egyesével, külön-külön), a jobb oldali konstansokat be kell írni. Szintén a korlátozásoknál adandó meg, hogy x 1 és x 2 nem negatív. (A nem korlátozott változók nemnegatívvá tétele kapcsolót is lehetne használni ehelyett.) Az egészkorlátozás beállításánál figyeljünk arra, hogy az int kulcsszót kell kiválasztani, és utána az Excel írja be az "egész" szócskát.

Megjegyzés: Hasonló módon állítható be az a feltétel is, ha a döntési változók csak binárisak lehetnek (ez most ennél a feladatnál nyilván nem szükséges, de később használni fogjuk).

Mivel a megoldandó feladat lineáris, ezért szimplex megoldási módszert célszerű beállítani. (Most más módszerek is megadnák az optimumot.)

A Solver beállításai a gépes termékgyártási feladat 1. adatelrendezéséhez
2. ábra

Az egyéb beállításoknál megadható pontosságra a célszerű beállítás (nálunk): 1E-10 és 1E-15 közötti értékek.

A Solverrel azonnal megkapjuk az optimumot (70 pénzegységnyi maximális eladás).

A gépes termékgyártási feladat 1. adatelrendezéséhez tartozó megoldás
3. ábra

A megoldás megtalálása után kérhetünk jelentéseket a megoldás körülményeiről (érzékenység, korlátok). Ebből láthatjuk például, hogy a 2. gépre vonatkozó feltétel jobb oldalán szereplő 33 valójában igen nagymértékben megnövelhető lenne.

A leírás alapján Ön is próbálja ki a megoldást. Külön említés nélkül ugyanígy járjon el a következő példákkal is.

A Solver beállításai a gépes termékgyártási feladat 1. adatelrendezéséhez
4. ábra

A 2. tervnél már fejlettebb megközelítést alkalmazunk, szeretnénk gyorsítani a munkát. Olyan táblázatot készítünk, amelyben az egyenlőtlenség-rendszer együtthatói direkt módon szerepelnek, így a korlátozó feltételek összevonva is megadhatók. Megjegyezzük, hogy az a x 1 +b x 2 alakú (több tag is lehet) lineáris kombinációk a szorzatösszeg függvénnyel is beírhatók.

A gépes termékgyártási feladat 2. adatelrendezése (Szorzatösszeg függvénnyel is)
5. ábra

A Solver felparaméterezése ez esetben a fentiek szerint jóval egyszerűbb lesz, a megoldás persze természetesen ugyanaz.

A Solver beállításai a gépes termékgyártási feladat 2. adatelrendezéséhez
6. ábra
A megoldás a gépes termékgyártási feladat 2. adatelrendezéséhez
7. ábra

A 3. terv csak kisebb módosítást jelent az előzőhöz képest, itt a lineáris kombinációkat egybevontuk az Mszorzat függvény felhasználásával. A kezdőmennyiségek vektorát a mátrixszorzás előtt transzponálni kell. A Solveres megoldás ugyanúgy történik, mint az előbb.

A gépes termékgyártási feladat 3. adatelrendezése (Mszorzat függvénnyel)
7. ábra
2. Példa - növényvédő szerek

Egy vegyészeti termékeket gyártó vállalatnál növényvédő szereket is készítenek, amelyek poralakban kerülnek forgalomba. A vállalat ötfajta növényvédő szert állít elő. Ezek a következők: BCM, Fundasol SOWP, Chinofurgin, Fundasol 25EC és Furoxon. A termékek előállítása (az alap- és segédanyagokból) ugyanazon a keverőgépen történik. A fajlagos időnorma termékenként a keverőgépen 2,5; 1,5; 3; 4; 4 óra/tonna. A keverőgép kapacitása 1000 óra. A termékek előállításához tízféle ható- és segédanyag szükséges. Ezekből négy anyag (A, B, C, D) felhasználása korlátozott. A növényvédő szerek fajlagos igénye ezekből az anyagokból (kg/tonnában) valamint a rendelkezésre álló mennyiségek (tonnában) a következő táblázatban találhatók.

Adatok a 2. lineáris programozási feladathoz:

AnyagokNövényvédő szerekFelhasználható
/korlátozás
BCMFSOWPCHFF25ECFX
A500000065000
B005050050060000
C50250505012000
D02555006000

Az egyes növényvédő szerek tonnánkénti nyeresége rendre: 6000, 2000, 2500, 4000, illetve 3500 Ft. Hány tonnát állítson elő az egyes növényvédő szerekből a vegyészeti termékeket gyártó vállalat, ha a maximális nyereség a cél?

A feladat matematikai modellje:

500 x 1 65000
50 x 3 +500 x 4 +500 x 5 60000
50 x 1 +25 x 2 +50 x 4 +50 x 5 12000
25 x 2 +5 x 3 +50 x 4 6000
2,5 x 1 +1,5 x 2 +3 x 3 +4 x 4 +4 x 5 1000
6000 x 1 +2000 x 2 +2500 x 3 +4000 x 4 +3500 x 5 max
x 1 ;   x 2 ;   x 3 ;  x 4 ;  x 5 0

Az időnorma és nyereség sorokat értelemszerűen kell a megadott adatokkal kitölteni. A Gyártás sorba kerülnek majd a megoldás ( x 1 ,   x 2 , x 3 , x 4 , x 5 ) értékei. Ezt a sort töltsük ki valamilyen induló adatokkal, pl. csupa 1-gyel. A Korlátozás oszlopot a fenti táblázat szerint töltsük ki és írjuk ide még az időkorlátot is (1000 óra).

A Tényleges oszlopba az A, B, C, D, időnorma, nyereség sorok 6×5-os mátrixának és az x _ -eket tartalmazó sorvektor transzponáltjának mátrixszorzata kerül! (Ez az előző feladatnál megismert 3. elrendezésnek felel meg, természetesen az egyszerűbb elrendezés szerinti Szorzatösszeg függvény is használható lenne.)

Helyezzük el az együttható-táblázatot és a célfüggvény együtthatóit a C5:G10 tartományban. Módszernek a Szimplex LP-t válasszuk.

Most már nekifoghatunk a Solverrel történő megoldásnak.

  • A célfüggvény értékét a maximalizálandó $I$10 célcella tartalmazza.
  • Módosuló cellák a tényleges termelést leíró x vektor elemei, azaz a $C$11:$G$11 cellák.
  • Korlátozás: az x vektor minden eleme nem negatív: $C$11:$G$11 0.
  • Korlátozás: a tényleges adatok zöld hátterű tartalmai nem haladhatják meg a korlátozás oszlop szürke hátterű tartalmait: $I$5:$I$9 $H$5:$H$9.

A modell és a megoldás a következő ábrán látható. (A pontosság választható 1E-15-nek.)

A 2. lineáris programozási feladat modellje és megoldása
9. ábra

Oldja meg a feladatot olyan módosítással is, hogy a megadáshoz a Szorzatösszeg függvényt használja, illetve hogy csak egész megoldások megengedhetők!

Figyelje meg, hogy ez esetben az optimum valamivel rosszabb lesz. (Kevesebb hasznot tudunk elérni.)

Végezzen kísérletet azzal, hogy kisebb pontossági értékeket ad meg a Solvernek! Hogyan módosul az optimum?

3. Példa - bútorgyártás

Egy kis bútoripari szövetkezet irodák számára gyárt asztalokat, székeket és könyvespolcokat. A faanyagot saját gépeiken szabják le.

  • A gépek napi kapacitása 100 munkaóra. Egy asztal, szék és könyvespolc anyagának leszabása 0,8, 0,4, illetve 0,5 órát igényel.
  • A szövetkezet festésre és fényezésre 650 munkaórát fordíthat naponta. Az egyes termékek festésének és fényezésének munkaidő-szükséglete 5, 3, illetve 2 munkaóra.
  • A kész bútorokat egy 150 m2-es raktárban tárolják. Raktáron kívül bútort tárolni nem szabad. Így a szövetkezet naponta csak annyi bútort gyárthat, amennyi elfér a 150 m2-es raktárban. A termékek fajlagos helyigénye a raktárban rendre: 1, 0,5 és 1,125 m2.
  • A jelenlegi piaci helyzetben az asztalok 300, a székek 160, a polcok 250 Ft nyereséget hoznak darabonként.

Mennyit gyártson a bútoripari szövetkezet az egyes irodabútorokból, hogy nyeresége maximális legyen? (A nem teljesen készre gyártott bútornak is van értelme, mivel a termelés a következő nap is folytatódik.)

A feladatot a következő egyenlőtlenségrendszer és célfüggvény jellemzi:

x 1 ;   x 2 ;   x 3 0
0,8 x 1 +0,4 x 2 +0,5 x 3 100
5 x 1 +3 x 2 +2 x 3 650
x 1 +0,5 x 2 +1,125 x 3 150
300 x 1 +160 x 2 +250 x 3 max

A feladatot jellemző értékeket a következő módon célszerű elhelyezni egy táblázatban:

A 3. lineáris programozási feladat adatelrendezése
10. ábra

A gyártás sorban elhelyeztük az x 1 ,   x 2 , x 3 termelés hipotetikus értékeit a tény oszlopban pedig mátrixszorzás segítségével kiszámítottuk a jelenlegi felhasználás és a célfüggvény értékeit:

{ =MSZORZAT(C4:E7; TRANSZPONÁLÁS(C8:E8))}

A Solver feladata lesz a gyártási értékek olyan változtatása, hogy a célfüggvény maximális legyen, miközben a tényértékek nem haladhatják meg a korlátozásokat.

A Solver paraméterezésénél a célcella és a változó cellák megadása egyértelmű, a korlátozó feltételek megadása pedig az ábra szerint direkt módon történik. A feladat lineáris, ezért szimplex megoldási módszert választunk. A Solver beállítását és a kapott eredményt a következő ábrákon láthatjuk:

A Solver beállításai a 3. lineáris programozási feladathoz
11. ábra
A 3. lineáris programozási feladat megoldása
11. ábra

Oldja meg a feladatot olyan módosítással is, hogy a megadáshoz a Szorzatösszeg függvényt használja, illetve hogy csak egész megoldások megengedhetők!

4. Példa - gerendavágás

1000 darab 7 méteres gerendából 1,5 és 2,5 méteres oszlopokat vágunk. Legalább négyszer annyi 1,5 méteres oszlopra van szükségünk, mint 2,5 méteresre. Hogyan vágjuk fel az 1000 darab 7 méteres gerendát, hogy a hulladékképződés minimális legyen?

(Nyilvánvaló, hogy egy 7 méteres gerenda feldarabolásakor legfeljebb 1 méternyi hulladék keletkezhet.)

A megoldáshoz azt kell végiggondolni, hogy a felvágás az alábbi módszerekkel történhet:

Kész oszlop hosszaHulladék
2,5 m1,5 m
1. módszer210,5
2. módszer130
3. módszer041

Jelölje x 1 ,   x 2 ,   x 3 az egyes módszerek alkalmazásainak darabszámát.

Ekkor 2 x 1 + x 2 +0 x 3 darab 2,5 méteres és x 1 +3 x 2 +4 x 3 darab 1,5 méteres oszlop lesz. A hosszabb oszlopok darabszámának 4-szerese nem haladhatja meg a rövidebb oszlopokét.

Ezzel a feladat matematikai modellje:

x 1 + x 2 + x 3 =1000
4( 2 x 1 + x 2 +0 x 3 )( x 1 +3 x 2 +4 x 3 )0
0,5 x 1 +0 x 2 + x 3 min

Az ismeretlenek értékeinek helyét most célszerű a sorok végén kijelölni, így ha a fenti táblázatot jobbról kiegészítjük az x _ vektorral és alulról a keletkezett darabok számaival (2,5 méteres, 1,5 méteres, hulladék), akkor a Solver könnyedén paraméterezhető lesz:

  • Az Összesen sorba (C7:E7) a felette lévő és aktuális oszlopbeli értékek, valamint az F oszlopbeli értékek (4-6 sorbeli) szorzatösszege kerül.
  • Az F7 cellába a felette álló értékek összege kerül.
  • A C9 cellában a C7 négyszeresére hivatkozunk és a C10 cellában a D7 -1-szeresére hivatkozunk.
  • Az induló alkalmazás értékeket állítsuk 1-re!

A probléma lineáris, ezért válasszuk a szimplex megoldási módszert. A pontosságot állítsuk 1E-10-re.

A 4. lineáris programozási feladat paraméterezése és megoldása
13. ábra

Oldja meg a feladatot más pontossági értékek választásával is! Összegezze a tapasztalatokat!

Nemlineáris feladatok

Nemlineáris feladatoknál a célfüggvény nem írható fel olyan "szép" módon, ahogy a fentiekben láthattuk (pl. négyzetes kifejezéssel kell dolgoznunk). Ilyen típusú problémák az Informatika tárgy törzsanyagában csak 1-2 esetben szerepelnek (lásd még a függvényábrázolás leckét), ezért kisebb terjedelemben foglalkozunk velük. Most az optimalizálási feladatnál csak egy konkrét példát nézünk meg.

Példa

Legyen adott egy ellipszis, amelynek centruma az origó, x tengely irányú féltengelyének hossza 2, az y tengely irányú féltengelyének a hossza pedig 1. Legyen adott továbbá egy kör, amelynek a középpontja a (0; 1) pont, sugara 2. Tekintsük azt a tartományt, amelynek pontjai az ellipszislap és a körlap közös pontjai. Határozzuk meg a tartomány azon pontját, amely a (2; 1) ponthoz legközelebb esik!

A feladat formális, matematikai megfogalmazása a következő.

Az ellipszis egyenlete:

x 2 2 2 + y 2 1 2 =1

A kör egyenlete:

x 2 + (y1) 2 = 2 2

Ennek megfelelően a nemlineáris optimalizálási feladat a következő:

A távolság minimális: ( x2 ) 2 + ( y1 ) 2   min

Nem vagyunk az ellipszisen kívül: x 2 +4 y 2 40

Nem vagyunk a körön kívül:   x 2 + y 2 2y30 0

Az x, y értékeket az ellipszis (0; 1) pontjából indíthatjuk, az F2, F3 cellákba a korlátozó feltételekhez szükséges kifejezéseket írjuk, a célfüggvény kifejezését pedig az F4 cellában helyezzük el. A pontosság legyen 1E-14.

Nemlineáris programozási feladat adatelrendezése és megoldása
14. ábra

A megoldás helyessége egyszerű ábra rajzolásával ellenőrizhető.

Önellenőrző kérdések

1. Keresse meg a saját számítógépének Microsoft Office rendszerkönyvtárán belül található Solvsamp.xls mintafájlt! Tanulmányozza át a példafeladatokat és a megoldási ötleteket, készítsen a füzetébe jegyzeteket! Próbálja önállóan is megoldani a feladatokat!

2. Vegye fel a következő táblázatot Excel 2010-ben egy új munkalapra és oldja meg az alábbi feladatokat!

CsokoládéDarabÖsszeg
Mogyorós7333
Mazsolás1457
Kókuszos5514
Epres1444
Karamellás7546

Kaptunk 22222 Ft-ot, amiből szeretnénk a lehető legtöbbet csokoládé vásárlására költeni.

Végezze el az előző táblázat alapján a következő számításokat!

Készítse el a célfüggvényt! Mennyit költünk összesen csokoládéra, ha a darabszámot nem módosítjuk?

Melyik kulcsszó segítségével tudjuk beállítani az egész korlátozást Solverben?

Számolja ki a Solver segítségével, hogy mennyi pénzt tudunk elkölteni maximum csokoládéra!

Figyeljen arra, hogy a darab csak nem negatív egész szám lehet. Emellett azt is vegye figyelembe, hogy 22222 Ft-nál többet nem tudunk elkölteni!

A Solvert állítsa alaphelyzetbe, majd csak a feladatban leírt paraméterek módosítsa!

A Solver számítási pontossága 1E-10 legyen! Megoldási módszerként a Szimplex LP-t használja!

3. Pistikének van 3000 Ft-ja, amit Hupikék törpikék kártyára szeretne költeni. A törpöknek ismert az ára és az energia értéke, amit a Törpök.xlsx táblázatban foglaltunk össze. Melyik kulcsszó segítségével tudjuk beállítani a Solverben, hogy a váltózó cellákban csak a 0, 1 értékek jelenhessenek meg?

Számolja ki a Solver segítségével, hogy hány kártyát tud venni Pistike a 3000 Ft-jából, ha a lehető legnagyobb energiával rendelkező csapatot akarja összeállítani!

Fontos: A Solvert állítsa alaphelyzetbe, majd csak a feladatban leírt paramétereket módosítsa!
A Solver számítási pontossága 1E-10 legyen! Megoldási módszerként a Szimplex LP-t használja!

Hány kártyát tud venni?

db

Mennyi pénze marad a 3000 Ft-ból?

Ft

4. Csodaturmix a gall druida négy fő összetevőből, a krokodilkönnyből, a fürjtojásból, a gekkónyálból és a sárkánypikkelyből állítja össze harcosai részére az erőt hozó csodaitalt. Ezekből rendre 5555 csepp, 10000 darab, csepp és 1000 darab van a raktáron. Messzeszaglix italába mindegyik összetevőből 13 egység kell. Tragikomix itala 7 csepp gekkónyálból és 1 darab sárkánypikkelyből készül. Sokadikix italának elkészítéséhez 12 csepp krokodilkönny és 11 csepp gekkónyál szükséges. Töpszlix varázsitalába a krokodilkönnyből 25 csepp, a sárkánypikkelyből pedig 4 darab kell. A harcosok mindig csak egész, teljesen teletöltött pohár italt isznak meg, amitől Messzeszaglix 13, Tragikomix 9, Sokadikix 14 ésTöpszlix 7 órára tudja megnövelni az erejét.

Hozzon létre egy új munkalapot Csodaturmix néven és vegye fel rá a feladat modelljét! Határozza meg, hogy melyik italból mennyit készítsen a druida, hogy a lehető legtovább maradjanak erősek a harcosok összesen!

Fontos: A Solvert állítsa alaphelyzetbe, majd csak a feladatban leírt paramétereket módosítsa!
A Solver számítási pontossága 1E-10 legyen! Megoldási módszerként a Szimplex LP-t használja!

Hány korlátozó feltétel vonatkozik a módosuló cellákra?

Hány pohár erőitalt kap Sokadikix?