Matematika | Felsőoktatás » Ferenczy Antal - Optimalizálási feladatok

http://www.doksihu Optimalizálási feladatok Összeállította: Ferenczy Antal PhD http://www.doksihu 1. Bevezetés A XXI. század minden jövőjét tervező szereplőjétől megköveteli, hogy mindennapi teendőit a lehető legjobban megtervezze. Ez vonatkozik elsősorban a munkára, de az élet szinte valamennyi területére is. Ehhez kívánunk segítséget adni, amikor az Alkalmazott informatika c. tárgy keretein belül ismertetjük az optimum-számítás alapvető fogalmait és szemléltetésként az ún. lineáris programozási módszer alkalmazását az élelmiszergazdaság területén. A stabil életvitelnek, a legalább veszteség nélküli gazdálkodásnak alapvető feltétele, hogy minden tevékenységünket a lehető legjobban megtervezzük, mivel csak így van remény arra, hogy nyugodt, kiegyensúlyozott munkás életet tudjunk magunkénak. Talán minden Olvasó felismerte már eddigi élete során, hogy nap mint nap bizonyos korlátokat figyelembe kell venni, s

hogy mindig hasznos, ha legalább egy cél megvalósítását tűzzük ki magunk elé. Az optimum számítás (más néven operációkutatás vagy matematikai programozás) éppen ennek a célkitűzésnek az általános megfogalmazásából született. Bizonyára valamennyiüknek volt már életük során egy-egy megvalósítható, s talán meg is valósított célja. Pl egy tartalmas nyári utazás, egy továbblépést jelentő vizsga (érettségi, jogosítvány megszerzése.), s ennek eléréséhez bizonyos feltételeket kellett teljesíteni. Nos, ehhez hasonló tervszerű feladatmegoldással ismertetjük meg az Olvasót. Az itt leírt elvek általánosan is alkalmazhatók, de mi – mivel nem célunk, hogy az Olvasóból a XXI. század Bolyaiját képezzük – megmaradunk a viszonylag egyszerű ún. lineáris összefüggéseket alkalmazó eljárások ismertetésénél Lineáris annyit tesz, hogy az egyik mennyiség a következőképpen függ a másiktól, ha egy felnőtt embernek

naponta 2,5 liter folyadékra van szüksége, akkor két felnőtt embernek 5 literre,, 10 felnőtt embertársunknak pedig 25 literre. Az ilyen jellegű összefüggéseket lineáris (=egyenes) összefüggéseknek nevezzük. Ezek fogják alkotni a korlátjainkat, vagy feltételeinket, illetve a céljainkat is. A középiskolában szöveges feladatokban találkozhattak olyan feladatokkal, amelyeket többismeretlenes egyenlettel oldottak meg, s ezt fogjuk általánosítani. egy, vagy http://www.doksihu Pl. ha van 37 liter vizünk, akkor ez hány embernek elég egy napra A matematikai egyenlet a következő: 2,5 x = 37 Ha a 37-et osztjuk 2,5-lel, akkor 14,8 embert kapunk, ami lehetetlen, mert csak egész ember van. Ilyenkor 14 a megoldás és még marad 2 liter víz Ha feltételként fogalmazzuk meg, akkor helyesebb az = helyett <=-t használva 2,5 x <= 37 -et írni, s figyelembe venni, hogy az ismeretlen változó értéke csak egész szám lehet. Modern korunk másik

követelménye, hogy napjainkban már általában egyszerre egynél több döntést kell hoznunk, azaz csak az egyenes, a lineáris kapcsolat a fix, de a megoldandó feladat már több változó értékének megválasztását igényli. Tegyük fel, hogy a felnőtt férfi ember mellett hölgyek (3 liter) és gyerekek (4 liter) is szóba jöhetnek. Használjunk teljes neveket az ismeretlen változókra (férfi, hölgy, gyerek), ekkor előbbi feltételünk a következő lesz: 2,5 férfi + 3 hölgy + 4 gyerek <= 37 Ennek a feladatnak már nagyon sok lehetséges megoldása van (14 férfi 0 hölgy 0 gyerek, 0 férfi 0 hölgy 9 gyerek,) Egy egészséges társadalomban, családban mindháromból legalább egyre szükség van. Ha ezt is figyelembe vesszük, akkor szűkül a lehetséges megoldások száma, de még mindig sok. Nos, ennek a feladatsornak a megoldására már a múlt század 40-es éveiben kidolgozta Dantzig a lineáris programozás algoritmusát (igaz, nem a népegészségügy,

hanem az amerikai hadsereg számára). Ha ezt a módszert alkalmazzuk, akkor a következő feladatot könnyedén meg tudjuk oldani. Ellátható személyek száma legyen maximális (férfi + hölgy + gyerek), miközben legfeljebb 37 liter vizünk van és minden csoportban legalább egy személy legyen. Az algebra eszközeivel leírva: férfi + hölgy + gyerek -- max 2,5 férfi + 3 hölgy + 4 gyerek <= 37 http://www.doksihu férfi >= 1, hölgy >= 1 és gyerek >= 1. Ha feltételezzük, hogy csak teljes családban gondolkodunk, akkor férfi = hölgy Mivel az optimum számítás egyik alapszabálya, hogy mind a cél, mind a feltételek esetén kötelező a baloldalon a konstans szorozva döntési változó szerepeljen és a jobboldalon csak konstans szerepelhet, ezért az előző feltétel a következő lesz: férfi – hölgy = 0 Ha ezt csatoljuk az előző feladathoz, akkor a következő feladatot kapjuk. feladat célfüggvénye: férfi + hölgy + gyerek -- max

gazdálkodás a napi vízmennyiséggel: 2,5 férfi + 3 hölgy + 4 gyerek <= 37 teljes család feltétele: férfi – hölgy = 0 minimum feltétel a személy csoportokra: férfi >= 1, hölgy >= 1 és gyerek >= 1. Ha ezt a kicsit már teljes feladatot megoldatjuk a WINQSB megfelelő rutinjával, akkor a következő megoldás hármast kapjuk: 6 férfi, 6 hölgy és 1 gyerek. Kedves Olvasó! Higgye el, hogy család és gyerek centrikus vagyok s véletlen, hogy a létszám maximalizálása miatt kerül ennyire háttérbe a gyerekek választása. Persze reálisan a gyerekeknek kell a több víz pl. a mindennapi fürdetéshez Talán ezek után hozzáfoghatunk a rendszeres áttekintéshez. A következőkben előforduló modellekben az általános gazdálkodás egyes részfeladatait tárjuk az Olvasó elé. A feladatok szóbeli és algebrai megfogalmazása után megmutatjuk, hogy hogyan lehet a WinQSB fantázianevű programcsomag Linear and Integer Programing nevű programjával

megértetni (beolvasni), majd megoldatni a feladatot, majd értelmezni a megoldást. (A könnyebb megvalósítás érdekében csak a lineáris folytonos és egészértékű programkomponenst használjuk.) http://www.doksihu 2. A lineáris programozás alapvető fogalmai (Mivel csak egy rövid betekintésre lesz időnk, ezért csak lineáris feladatokat ismertetünk.) Ezek előrebocsátása után a következő fogalmakat vezetjük be: LINEÁRIS KIFEJEZÉS: azokat a kifejezéseket, amelyekben konkrétan megadott számérték és egy ismeretlen - később meghatározásra kerülő - mennyiség szorzataiból álló összeadás sorozat szerepel, lineárisnak nevezzük. Néhány példa: 2x 5x+6y 7 alma + 1 körte -3 szilva Mivel ismételten csak a saját céljainkat tekintjük fontosnak, ezért az általános lineáris fogalmat mellőzzük. Itt a konstansok (rendre 2, 5, 6, 7, 1 és -3), amelyekkel majd az ismeretlenek mennyiségét meg kell szorozni. Ezek egyfajta fajlagos értékek,

amelyeket a megoldandó feladatok szövege (meséje) határoz meg. Nagyon fontos, hogy figyeljünk a helyes mértékegység választásra és azok összhangjára. A MEGOLDANDÓ FELADAT CÉLJA: Amikor a célt választjuk, akkor a célfüggvény optimális (maximális, illetve minimális) értékét keressük. A bevezetés példájában: férfi + hölgy + gyerek - max RHS ÉRTÉKEK (JOBBOLDAL): Az angol nyelvű optimalizáló program rendszerint az RHS (right hand side) jelölést, vagy rövidítést használják s itt mindig csak konstans értékek szerepelhetnek, amelyek háromféle relációval kapcsolódhatnak a lineáris kifejezéshez. KORLÁTOZÓ FELTÉTELEK: Általában a legtöbb esetben azok a feltételek, amelyek valamely felhasználható mennyiséget jelenítenek meg pl. a bevezetésben a naponta felhasználható 37 liter vizet. 2,5 férfi + 3 hölgy + 4 gyerek <= 37 http://www.doksihu IGÉNY FELTÉTELEK: Általában olyan feltételeket jelentenek, amelyeket legalább

teljesíteni kell (lásd a bevezetésben a minden csoportból legalább egy személy meglétét). férfi >= 1, hölgy >= 1 és gyerek >= 1. EGYENLŐSÉG FELÉTELEK: Általában a fix értékkel vagy azonossággal megadott feltételek, mint a bevezetésbeli példánkban szereplő ún. család feltételt férfi – hölgy = 0 DÖNTÉSI VÁLTOZÓK TÍPUSA: a feladat szövegéből következik, hogy az egyes eldöntendő változók milyen értékeket vehetnek fel. Talán egyértelmű, hogy előző példánkban a lehetséges személy számok csak egész számok lehetnek, melyet az angol nyelvű programok Integer szóval jelölnek. A bármely valós számokat az angol programok a Continous szóval jelölnek s talán egyértelmű, hogy szinte valamennyi döntési változónk csak nem negatív lehet. Nagyon extrém esetben valamely ún segédváltozó lehet negatív is, de rövid betekintésünk során ilyennel nem fogunk találkozni. http://www.doksihu 3. A feladatok megoldási

stratégiája Bármely megoldandó feladatnál a következő lépéseket javasoljuk:  A feladat szabatos megfogalmazása szövegesen.  A feladat algebrai megfogalmazása (ahogy ezt a bevezetésben leírt feladatnál is tettük).  A feladat betáplálása a WinQSB program Linear and Integer Programing c. rutinjába. (=lp ilpexe!)  A feladat megoldása és a feladat megoldásának értelmezése. A javasolt sorrendet az első néhány feladatnál teljes egészében közöljük, majd ismertetjük néhány komolyabb élelmiszergazdasági feladat szabatos szövegét annak reményében, hogy a kedves Olvasó a fejlődés és a minden eljövendő értelmiségi számára javasolt agytornát elvégezhesse. http://www.doksihu 4. A WINQSB program használata Bemutatásként a bevezetésben szereplő feladat megoldását követjük lépésről lépésre. Az lp ilp.exe program indítása után a következő képernyőt kapjuk: (Itt a bal felső sarok a lényeg, ahol a File menü

elemet kell választanunk, ahol új feladat esetén a New Problem, előkészített feladat esetén a Load Problem menüpontot kell választanunk.) Amikor a bevezetés feladatát betápláltuk, akkor a New Problem-nél a következőképpen töltöttük ki a táblázatot. A következő információkat hagytuk jóvá illetve írtuk be: http://www.doksihu A feladat neve (Problem Title): családi vízfogyasztás. A változók száma (Number of Variables): 3. A feltételek száma (Number of Constraints): 2. A feladat célja (Objective Criterion): maximum keresése. A feladatot (Data Entry Format): táblázatos (Spreadsheet) formában adjuk meg. A döntési változók (Default Variable Type): többsége nem negatív egész típusú változó. Talán ezután egyértelmű, hogy az OK gombot kell megnyomni. Ekkor a következő lapot kapjuk: Mivel szeretnénk, hogy összhang legyen a feladat algebrai képe és a WINQSB megjelenítése között, ezért megadjuk a változók és a feltételek

feladatbeli nevét. A szükséges almenü pontokat a lassan már megszokott (Windows, Word, Excel, Pover Point) Edit menüpontjában találjuk. Az előbbi esetben válasszuk az Edit menü Variable Names menüpontját: http://www.doksihu Itt egy közbülső állapotot mutatunk, mely utal arra, hogy hogyan kell az új neveket beírni. A feltételek elnevezéséhez a változónevek bevitele után válasszuk a Constainst Names menüelemet válasszuk az előzőhöz hasonlóan. http://www.doksihu Miután ezt megtettük sor kerülhet az adatok begépelésére, amelyben talán csak a tizedespont beírására és a relációjel változtatására kell felhívnunk a figyelmet. (Emlékeztetünk ismét a Word és Excel adatbeviteli lehetőségeire.) Nos, a relációjelet úgy állítottuk át, hogy a család sor <= jelére duplát kattintottunk és az = jellé válik. Az értékeket begépelve, vagy az Enter, vagy az elmozgató nyilak segítségével olvastatjuk el a programmal. Ha a

feladatot csalviz.lpp néven elmentjük (lásd a File menü megfelelő alpontját!(Load Problem)), akkor a következő ASCII típusú állományt kapjuk: LP Variable --> Maximize vízfogyasztás család LowerBound UpperBound VariableType MatrixFormat férfi 1 2.5 1 1 M Integer családi vízfogyasztás 3 2 hölgy gyerek Direction R. H S 1 1 3 4 <= 37 -1 = 0 1 1 M M Integer Integer Talán könnyen átlátható a képernyőn látható feladatforma és az ASCI állomány tartalmának kapcsolata. Talán nem kell sokat magyarázni, hogy hogyan kell az egyes sorokat összeolvasni az algebrai alakban szereplő formával. http://www.doksihu Ezek után következhet a feladat megoldása. A Solve and Analyze menü első pontját (Solve the problem) választva a következő jelzést kapjuk. Amikor az Ok-t jóváhagyjuk a következő táblázat jelenik meg.: http://www.doksihu Különösebb angol tudás nélkül a megadott változó- és feltételnevek segítenek abban, hogy

kiolvassuk, hogy 6 férfi, 6 hölgy és 1 gyerek adják a 13-as maximális létszámot, Szabatos olvasásnál a szereposztás a következő: 1. oszlop tartalmazza a változó, a célfüggvény és a feltétel neveket 2. oszlop tartalmazza a megoldás változó és feltétel értékeit 3. oszlop tartalmazza a fajlagos célfüggvény együtthatókat, az optimalizálás irányát, a feltételek relációjeleit. 4. oszlop tartalmazza a célfüggvény döntési változónkénti, illetve összegzett értékét, továbbá a feltételek RHS értékeit. 5-6. oszlop szövegesen, illetve numerikusan jellemzi az illető változó, illetve feltétel helyzetét a megoldásban. http://www.doksihu 5. Feladatok lépésről lépésre 5.1 Optimális termékszerkezet egy segédüzemben (ZEMPFA01) Egy segédüzem háromféle erőforrást (E1, E2, E3) használ fel két termék (T1, T2) gyártásához. Az erőforrások korlátozottan állnak rendelkezésre, kapacitásuk az alábbi: E1 50 E2 80 E3 90

A termékek átlagos erőforrás igénye: E1 E2 E3 T1 1 2 1 T2 0 1 3 A T1 és T2 termék aránya legfeljebb 2:3 legyen! Milyen gyártási tervet készítsen a segédüzem, ha a maximális nyereség elérése a cél, s az egyes termékek nyeresége 3, illetve 1 pénzegység? A megoldás gondolatmenete: A cél a 3 T1 + 1 T2 lineáris függvény maximalizálása. Az első erőforrás felhasználását az 1 T1 + 0 T2 kifejezés -, a második erőforrásét a 2T1 + 1 T2 kifejezés – és a harmadik erőforrás felhasználását az 1 T1 + 3 T2 kifejezés adja. A teljes megoldás ismertetése előtt az arány átalakítását lépésenként mutatjuk be. Egyszerűen T1:T2<=2:3, ami egyenértékű a 3 T1 <= 2 T2-vel, de az LP modellben csak a baloldalon szerepelhet ismeretlen, ezért 3 T1 – 2 T2 <= 0 lesz. Ebben a feladatban az talán egyértelmű, hogy termelni csak pozitív mennyiséget lehet. Az viszont a feladatból nem derül ki, hogy darabos vagy mérlegen mérhető

ún. folytonos mennyiség termelhető. Az algebrai modellt ez nem befolyásolja A WinQSB-ben lehetőség van mindkét változat optimalizálására. Az előző esetben nonnegativ integer-t, az utóbbi esetben nonnegativ continous változó csoportot kell választani. http://www.doksihu Az algebrai modell a maga teljességében az alábbi: 3 T1 + 1 T2 -- max 1 T1 + 0 T2 <= 50 2 T1 + 1 T2 <= 80 1 T1 + 3 T2 <= 90 3 T1 – 2 T2 <= 0 T1 >=0 és T2>=0 Ha megnézzük a zempfa01.lpp állomány tartalmát, akkor a következőt láthatjuk: ZEMPFA LP MatrixFormat feladatsor 1. 2 4 feladata Variable --> T1 T2 Direction R. H S Maximize 3 1 E1 1 0 <= 50 E2 2 1 <= 80 E3 1 3 <= 90 arány 3 -2 < = 0 LowerBound 0 0 UpperBound M M VariableType Continuous Continuous A szemléltetés érdekében az első sort egy picit átszerkesztettük. Az előző szakasz alapján indítsuk el a WINQSB programcsomag lp ilp.exe elemét s ott a New Problem menü-elemet. Ekkor

a következőket kell válaszolnunk: A feladat neve: ZEMPFA feladatsor 1. feladata A célfüggvény maximumát keressük. Az adatokat táblázatos formában adjuk meg. A változók száma 2, a feltételek száma pedig 4. A döntési változók a nem-negatív folytonos kategóriába tartoznak. http://www.doksihu Ezután két választásunk van: - vagy az első példához hasonlóan bevisszük az adatokat, - vagy a Load Problem menüpont segítségével beolvassuk a zempfa01.lpp állományt. Mindkét esetben a következőhöz hasonló táblázatot kell kapnunk. Ha ezt az előző feladathoz hasonlóan a Solve and Analyse menüpont Solve the problem elemével megoldjuk, és egyet továbblépünk, akkor eredményül a következőt kapjuk: http://www.doksihu Amint látjuk, van a feladatnak optimális megoldása, de mind a T1, mind a T2, mind a célfüggvény értéke végtelen szakaszos tizedes tört, amely a megvalósításnál nem előnyös, ezért talán érdemes választani az

egész értékű megoldást biztosító Integer változatot. (Ezt a későbbiekben egyfajta ismétlésként az Olvasóra bízzuk) 5.2 Szállítási feladat LP modellje (SZK01) (A feladatot később - a feladat specialitásait is kihasználó formában - is megfogalmazzuk és megoldjuk az Excel solver eljárásával.) Adva van egy borszállítással foglalkozó vállalkozó, aki 4 raktárból 3 áruházba szállíthat bort, s ezt minden nap megtervezi a minimális összköltség érdekében. A raktárhelyek s azok induló kapacitása a következő: Raktár helye Cegléd Dabas Pomáz Albertirsa palack Edb 5 000 4 000 1 000 3 000 A felvevő áruházak és azok igénye az adott napon: Áruház helye Szob Budaörs Szolnok Rendelés Edb 2 500 2 000 5 500 http://www.doksihu A raktárhelyek és az áruházak távolságtáblázata a következő: Távolság km Szob Budaörs Szolnok Cegléd 120 90 30 Dabas 90 55 45 Pomáz 40 35 120 Albertirsa 90 65 50

Tételezzük fel, hogy 1 ezer palack (Edb) szállítási költsége 100 Ft, akkor a szállítási költség fajlagos táblázata a következő: Ft/(Edb*km) Szob Budaörs Szolnok Cegléd 12000 9000 3000 Dabas 9000 5500 4500 Pomáz 4000 3500 12000 Albertirsa 9000 6500 5000 Nyilvánvaló, hogy a szállítási vállalkozó minimális összköltségre törekszik. Vezessük be a következő jelölés rendszert! változó honnan hová X11 Cegléd Szob X21 Dabas Szob X31 Pomáz Szob X41 Albertirsa Szob X12 Cegléd Budaörs X22 Dabas Budaörs X32 Pomáz Budaörs X42 Albertirsa Budaörs X13 Cegléd Szolnok X23 Dabas Szolnok X33 Pomáz Szolnok X43 Albertirsa Szolnok Algebrai modell: 12000 X11+ 9000 X12 + 3000 X13 + 9000 X21 + 5500 X22 + 4500X23 + 4000 X31 + 3500X32 + 12000 X33 + 9000 X41 + 6500 X42 + 5000 X43 - min X11+ X21 + X31 + X41 >= 2500 X12+ X22 + X32 + X42 >= 2000 X13+ X23 + X33 + X43 >= 5500 X11 + X12 + X13 <= 5000

http://www.doksihu X21 + X22 + X23 <= 4000 X31 + X32 + X33 <= 1000 X41 + X42 + X43 <= 3000 X11 >= 0, X12 >= 0,X43 >= 0 Bár ezer palackban gondolkodunk, de talán nem felesleges kikötnünk, hogy igazán ezerpalackos konténerekben tudják elképzelni a szállítást. (Mondjuk az egy teherautó teherbírása.) A feladat WinQSB paraméterei: A feladat neve: borszállítás A célfüggvény iránya: minimum. A változók száma: 12. A feltételek száma: 7 A modell megadási módja táblázatos. A változók típusa: nem-negatív egész. Az elmentett szk01.lpp állomány szerkezeti képe a következő: Variable --> X11 X12 X13 X21 X22 X23 X31 X32 X33 X41 X42 X43 Direction R. H S Minimize 12000 9000 3000 9000 5500 4500 4000 3500 12000 9000 6500 5000 Szob 1 1 1 1 >= 2500 Budaörs 1 1 1 1 >= 2000 Szolnok 1 1 1 1 >= 5500 Cegléd 1 1 1 <= 5000 Dabas 1 1 1 <= 4000 Pomáz 1 1 1 <= 1000 Albertirsa 1 1 1 <= 3000 LowerBound 0 0 0 0 0 0 0 0 0 0 0 0

UpperBound M M M M M M M M M M M M VariableType Integer Integer Integer Integer Integer Integer Integer Integer Integer Integer Integer Integer http://www.doksihu A feladat WinQSB grafikus modellje: A feladat megoldása madártávlatból a következő: http://www.doksihu A feladat megoldását ugyanúgy olvashatjuk el, mint a bevezető - s az előző szakasz esetében. 5.3 Szállítási feladat megfogalmazása táblázatos formában (A mini-max algoritmus és a solver technika alkalmazása, SZK01). BORSZÁLLÍTÁS SZERVEZÉSE Nyissa meg a szallitas.xls Excel állományt! Feltételezzük, hogy 1 ezer palack (Edb) 1 km-en történő szállítása 100 Ft-ba kerül. A Költség Ft/Edb táblázatba képlettel írja be a szállítási költség számítási módját! (relatív hivatkozás esetén elég egyszer beírni, majd a többi cellába átmásolni) A Döntés Edb táblázatban egyelőre csak összegezze a sorokat és oszlopokat az összegző függvény felhasználásával! A

feladat megoldása során majd ebbe a táblázatba írjuk be, hogy hány ezer palackot fogunk szállítani az egyes lerakatokból az áruházakba a rendelés szerint. Az Összktg Ft táblázatba cellahivatkozásokkal írja be az egyes városok közt feltételezett szállítás összes költségét, ami már a szállított mennyiséget is figyelembe veszi! (Költség Ft/Edb * Döntés Edb, a fenti táblázatok megfelelő celláira hivatkozva). Írja be itt is a sorok és oszlopok összegzését biztosító függvényeket! Különösen fontos a sárga színnel is kiemelt E29-es cella, mert ez mutatja majd az összes költséget. Szállítási költségek minimalizálása: Térjen vissza a Döntés táblához, és oldja meg a feladatot a szállítandó mennyiségek mini-max módszer szerinti beírásával! (A mini-max módszer lényege az, hogy a legrövidebb úton elszállítjuk a lehető legnagyobb mennyiséget - az igények és a rendelkezésre álló mennyiség korlátait figyelembe

véve.) Az elkészített táblázatot másolja át egy második munkalapra, nevezze át ktg minmax -ra, majd térjen vissza az első munkalapra (Alap-ra)! Az Excel Solver optimalizáló programja segítségével optimalizáljuk a fenti feladatot a következők szerint. Set target cell: (célcella) az összköltséget tartalmazó cella http://www.doksihu Equal to: (az optimalizálás módja): Min By changing cells: (döntési változók) a döntési tábla 12 celláját kell egérrel kijelölni Subject to the Constraints: (korlátozó feltételek hozzáadása) a. Döntési változók tartománya >= 0 (nem Add szállíthatunk negatív mennyiségeket) b. Szobra szállítandó mennyiség = a Szobon rendelt mennyiség c. Budaörsre szállítandó mennyiség = Budaörsön rendelt mennyiség d. Szolnokra szállítandó mennyiség = Szolnokon rendelt mennyiség e. Ceglédről elszállítandó mennyiség <= ceglédi raktárkészlet f. Dabasról elszállítandó mennyiség <=

dabasi raktárkészlet g. Pomázról elszállítandó mennyiség <= pomázi raktárkészlet h. Albertirsáról elszállítandó mennyiség <= albertirsai raktárkészlet A feltételeket azért kell ilyen relációkkal megadni, mert a rendelt mennyiség kisebb volt, mint a raktári készlet, tehát az igényeket ki tudjuk elégíteni, de biztosan marad még raktári készlet. Természetesen ezeket is cellahivatkozásokkal kell megadni! A Solve (megoldás) parancsra való kattintás és újabb jóváhagyás után a számítógép megadja az általa javasolt szállítási tervet. Ellenőrizze, hogy melyik raktárakban marad még a készletből. Számítsa ki, mennyivel kerül így kevesebbe a szállítás megszervezése, mint a minimax módszerrel kapott eredménynél. A feladat eredeti szövege megtalálható a szallitas.txt állományban A feladat kiinduló adatai megtalálhatók a szallitas.xls állományban A fentiekben leírt feladat solveres megoldása az alap, a minimax

módszerrel készített optimum a minimax lapon olvasható a szallitas2.xls állományban http://www.doksihu 6. Ajánlott feladatok 6.1 Egy feldolgozó üzem termelésének optimalizálása (ZEMPFA05) Egy húsüzem kenőmájas, virsli, főzőkolbász és szalámi előállítására alkalmas gépsorokkal rendelkezik, melyek napi kapacitása sorrendben: 5000 kg, 2000 kg, 8000 kg és 1500 kg. Az egyes termékek 1 kg-jának nyersanyag igénye a következő: sertéshús máj marhahús szalonna kenőmájas 0,3 0,5 0,0 0,4 virsli 0,5 0,0 0,4 0,2 főzőkolbász 0,4 0,0 0,5 0,3 szalámi 0,7 0,0 0,0 0,6 A vágóhídról naponta maximum 12 t sertéshúst, 2,5 t májat, 14 t marhahúst és 10 t szalonnát rendelhetünk. Szerződés miatt viszont sertés- és marhahúsból összesen legalább 10 t-t naponként át kell venni. A kereskedelem igénye a késztermékekből bizonyos határok között adott: kenőmájasból 2-5 t, virsliből 1,5-2 t, főzőkolbászból 4-6 t

és szalámiból 10-20 t. Az üzem keresi azt a gyártási programot, amely a feltételek figyelembevétele mellett a késztermékek össztömegét maximalizálja. 6.2 Növénytermesztés optimalizálása (ZEMPFA07) Egy gazdaság négyféle növény (A, B, C, D) termesztésével maximális nyereséget biztosító termelési tervet kíván készíteni. Az egyes növények nyeresége hektáronként: 20, 10, 6 és 9 ezer Ft. Az A növény termésátlaga 3,4 t/ha, a B növényé 2,8 t/ha. A növények termesztéséhez három erőforrást (E1, E2, E3) veszünk figyelembe, melyek kapacitása: 3600, 3400 és 3800 munkanap. http://www.doksihu Az egyes növények fajlagos erőforrásigényét a következő táblázat tartalmazza, munkanap/ha-ban: E1 E2 E3 A 2 0 5 B 3 2 4 c 0 3 3 D 4 2 2 A gazdaság rendelkezésére álló terület, amelyet teljesen ki kell használnia 1000 ha. További kikötések: - a B növény maximum 400 ha-on termeszthető, - a C növény számára

nem használható fel több terület, mint a B növény területének fele, - az A növény termésmennyisége legalább 400 t legyen, - a B növény termésmennyisége nem lehet több mint 700 t. 6.3 Üvegház hasznosítása egy tsz-ben (ZEMPFA11) Egy termelőszövetkezet folyamatosan üzemeltetett üvegházában háromféle (A, B, C) növényt termeszt. Olyan tervet keres, amely megadja, hogy az egyes időszakokban, mely növényeket, mekkora területen érdemes termeszteni a maximális nyereség szempontjából. Az egyszerűség kedvéért az ütemezést negyedéves bontásban végezzük, vagyis minden negyedév elején ültethetjük el a növényeket. Az egyes növények tenyészideje: 3, 2 és 2 negyedév. Értékesítésük a tenyészidő utolsó negyedévében történik. A termesztés sajátosságai miatt az A növényt a IV, a C-t pedig az I. és IV negyedév elején nem ültethetjük Az egyes növények eladási árai az év folyamán változnak. A hektáronkénti

árbevételek eFt/ha-ban az alábbiak: I. II. III. IV. A 15 0 19 25 B 6 3 5 10 C 0 0 18 24 Az egyes negyedévekben különböző nagyságú területek állnak rendelkezésre, éspedig http://www.doksihu I. negyedév 100 ha II. negyedév 150 ha III. negyedév 115 ha IV. negyedév 80 ha Az egyes növények tenyészidejük folyamán az alábbi munkaóra ráfordítást igénylik. A növény termesztésének első negyedévében középső negyedévben utolsó negyedévban B növény termesztésének első negyedévében utolsó negyedévében C növény termesztésének első negyedévében utolsó megyedévében 100 ó/ha 50 ó/ha 100 ó/ha 60 ó/ha 60 ó/ha 120 ó/ha 140 ó/ha A munkaerő gazdálkodás által adott korlátok: a II. negyedévben maximum 15000 munkaóra áll rendelkezésre, a IV. negyedévben viszont minimum 10000 munkaórát kell felhasználni 6.4 Szántóföldi vetésterv egy gazdaságban (ZEMPFA13) Egy gazdaság olyan vetéstervet

kíván készíteni, mely az egyes termékek mennyiségére vonatkozó előírások (szerződés, takarmányigény, stb) betartása és az erőforrások kapacitáskorlátainak figyelembevétele mellett a maximális termelési értéket biztosítja. A gazdaságnak két, egymástól eltérő természeti adottságú szántóterületen működő növénytermesztő üzemegysége van 1155 ha, illetve 600 ha termőterülettel, melyeket teljesen ki kell használni. A termelt növények: búza, árpa, kukorica, hüvelyesek és lucerna. A hüvelyesek csak a második (600 ha-os) területen -, a többi növény mindkét területen termeszthető. A termés mennyiségre vonatkozó korlátok: http://www.doksihu növény alsó korlát t felső korlát búza 0 3600 árpa 330 500 kukorica 2900 4100 hüvelyesek 85 170 lucerna 1800 1800 Az erőforrások és kapacitásaik: Munkaóra 21500 óra Traktor 42100 nba Teherautó 37000 tkm A fajlagos termelési adatok: a. az 1155 ha-os

területen: óra/ha nba/ha tkm/ha t/ha búza 8,5 21,2 29,3 3,8 árpa 5,6 20,5 10,2 3,3 kukorica 16,5 24,0 27,5 5,2 lucerna 10,8 22,5 3,8 7,9 munkaóra traktor teherautó átlagtermés óra/ha nba/ha tkm/ha t/ha búza 8,0 18,3 25,1 4,9 árpa 5,6 19,1 8,4 3,3 kukorica 16,2 21,0 23,4 5,8 hüvelyesek 11,3 16,2 14,8 1,7 lucerna 10,2 20,4 3,2 9,9 b. a 600 ha-os területen: A termelési érték hektáronként 1000 Ft-ban: http://www.doksihu I. terület 1155 ha II. terület 600 ha búza 13703 17466 árpa 13272 13351 kukorica 16891 17870 hüvelyes 9486 lucerna 7110 8910 6.5 Borházasítás (SZK02) (A feladat eredetiben olvasható a borhazasitas m.txt állományban) Rizlingszilváni kész borokhoz az alábbi alapborokat és összetevőket használjuk: alsó korlát felső korlát önköltség alsó korlát felső korlát % El Ft/l Rizlingszilváni 50 194 50 Kunleány 208 Chasselas 180 18 Chardonnay 15 166 15

.Sűrítmény 3 836 alapbor fajta Készítendő olyan piacképes Rizlingszilváni bor, ami a fenti szakmai szabályokat és előírásokat betartja, ugyanakkor a 676 Ft/l-es értékesítési ár mellett a legnagyobb hasznot hozza a borászatnak. I. A feltételrendszer megfogalmazása és leírása: Nevezzük el az összeházasítandó alapborok mennyiségét x1,,x5 névvel és segítségükkel fogalmazzuk meg a feltételeket! a. Cél a maximális nyereség elérése (676-194)*x1+(676-208)x2+(676-180)x3+(676-166)x4+(676-836)x5 -> max b. A Rizlingszilváni alapbor a kész bornak legalább 50 %-át tegye ki x1 >= 0,5 * (x1 + x2 + x3 + x4 + x5) c. A Chardonnay a kész bornak legfeljebb 15 %-át tegye ki http://www.doksihu x4 <= 0,15 * (x1 + x2 + x3 + x4 + x5 ) d. A sűrítmény a kész bornak legalább 3 %-át tegye ki x5 >= 0,03 * (x1 + x2 + x3 + x4 + x5 ) e. Rizlingszilvániból maximum 50 El, használható fel x1 <= 50 f. A Chasselasból legalább 18 El-t fel kell

használni x3 >= 18 g. A Chardonnayből legalább 15 El-t fel kell használni x4 >= 15 Mielőtt a következő ponthoz hozzáfognánk, a feltételeinket fogalmazzuk át a WinQSB szabályainak megfelelően (lineáris kifejezés a baloldalon, konstans a jobboldalon!) Oldjuk meg a feladatot a WinQSB programrendszer Linear and Integer Programming programjával: a. A File/New problem menüponttal kezdeményezzük az új feladat bevitelét! b. A feladat neve (Problem Title) legyen Borházasítás c. A változók száma (Number of Variables) legyen 5 d. A feltételsorok száma (Number of Constraints) legyen 6 e. A célfüggvény kritériuma (Objective Criterion): maximalizálás f. A változók alaptípusa (Default Variable Type): nem-negatív folytonos (ez később egyesével megváltoztatható, ha kell) majd OK A megjelenő táblázatba soronként vigyük be az együtthatókat: g. Először a célfüggvény együtthatóinak kiszámított értékeit visszük be h. Bevisszük egymás

után a 6 feltételsor együtthatóit a következő 6 sorba http://www.doksihu Vigyázat, a változókat az eredeti feltételekben mind át kell rendezni a baloldalra, s csak utána vihetjük be azokat a megfelelő változó oszlopba! A relációjelek irányának a szükség szerinti megváltoztatását a relációra való dupla kattintással tudjuk elérni. Az első három relációjel jobb oldalára 0-át kell írni. Az utolsó három feltételnél a változók együtthatója mindig 1 - ezt kell beírni a megfelelő oszlopba. i. A feladatot a síelő ikonra való kattintással oldjuk meg! Ellenőrizzük az optimális megoldást, hogy kielégíti-e a kezdeti feltételeket. http://www.doksihu 7. Ajánlott irodalom Harnos Zsolt: Operációkutatási módszerek és alkalmazásaik, Kertészeti és Élelmiszeripari Egyetem, Budapest, 1996 Prékopa András: Lineáris programozás. BJMT Budapest, 1968 Felhasznált forrásanyagok: ZEMPFA feladatsorozat: Zala Endre és Emberné dr.

Majzik Piroska gyűjtése SZK feladat sorozat: dr. Szenteleki Károly gyűjtése