1. Előadás Lineáris programozás Salamon Júlia Előadás II. éves gazdaság informatikus hallgatók számára
Operációkutatás Az operációkutatás az alkalmazott matematika az az ága, ami bizonyos folyamatok és eljárások optimalizálásával foglalkozik. Az operációkutatás szóban az operáció hadműveletre utal. Elsőként 1938-ban alkalmazta a brit légierő egy radarfigyelő rendszer kiépítésére. A második világháborúban a Nagy-Britannia, az USA és a Szovjetunió által alapított Operational Research Sectionsben többek között a hajók optimális száma, a hajókonvojok védőkíséretének mérete vagy a szőnyegbombázás sűrűsége és kiterjedése. A háború után az operációkutatás a csatamezőkről bevonult a gazdaságba, ahol is arra alkalmazták, hogy minimalizálja az adott cél elérésének költségét, vagy duálisan, maximalizálja az adott eszközökkel elérhető célt. Ma a mérnöki tudományokban, a gazdasági informatikában is hasznosítják, továbbá összekapcsolódott a játékelmélettel. 2016.09.26.
I. előadás
2
Előadások tematikája 1) LINEÁRIS PROGRAMOZÁS. 1) Lineáris programozás modellje 2) Dualitás. A dualitás közgazdasági jelentése. 3) Érzékenység vizsgálat 4) Szimplex algoritmus 5) Degenerált lineáris programozási feladatok 6) Keverési feladatok 7) Belsőpontos algoritmus 2) SZÁLLÍTÁSI ÉS HOZZÁRENDELÉSI FELADATOK 1) Szállítási feladatok 2) Hozzárendelési feladatok
2016.09.26.
I. előadás
3
3) JÁTÉKELMÉLET 1) Kétszemélyes nullaösszegű játékok 2) Neumann egyensúlyi pont 3) Nash egyensúlyi pontok 4) A játék magja és a Shapley érték n személyes játékokban 5) Játékelméleten alapuló közgazdasági modellek 4) HÁLÓZATOK ELEMZÉSE 1) Minimális feszítőfa problémája 2) Legrövidebb út keresése 3) Maximális folyam meghatározása 4) Utazó ügynök problémája 5) PROJEKTEK ÜTEMEZÉSE 1) Kritikus út módszere – CPM 2) Idő-költség diagramon alapuló CMP módszer 3) PERT módszer
2016.09.26.
I. előadás
4
Könyvészet www.emte.siculorum.ro/~salamonjulia Makó Z., Salamon J.: Operációkutatási példatár közgazdászoknak, Ed. Scientia, Cluj Napoca, 2011. (30 db. a könyvtárban) Winston W.: Operációkutatás I. II., Ed. AULA, Budapest, 2003. (5 db. a könyvtárban) Darnyi P., Varró Z.: Operációkutatás, Ed. Carbocomp, Pécs, 2001. (19 db. a könyvtárban) Hiller F. S., Lieberman G. J.: Bevezetés az Operációkutatásba LSI Okt.központ, Budapest, 1999. (1 db. a könyvtárban)
2016.09.26.
I. előadás
5
Lineáris programozás A lineáris programozási feladat (LP) egy olyan optimalizálási feladat, amelyben: maximalizáljuk vagy minimalizáljuk a döntési változók egy lineáris függvényét. Ezt a maximalizálandó vagy minimalizálandó függvényt célfüggvénynek nevezzük; a döntési változók értékeinek ki kell elégíteniük a korlátozó feltételeket. Ezen a feltételek vagy lineáris egyenlőtlenségek vagy lineáris egyenletek kell legyenek; a döntési változókhoz tartozhat előjel-korlátozás is. Ha a döntési változókra pluszban kikötjük, hogy értékei egész számok, akkor egész értékű lineáris programozási feladatról beszélünk. 2016.09.26.
I. előadás
6
Általános alakja
2016.09.26.
I. előadás
7
Lineáris programozás Matematikai modell felírásának lépései: 1. lépés: A döntési változók és a mértékegységek meghatározása. x1, x2, ….. 2. lépés: A célfüggvény felírása. 3. lépés: A korlátozó feltételek és a döntési változókra vonatkozó előjel-korlátozó feltételek megadása.
2016.09.26.
I. előadás
8
Lineáris programozás Feladat Egy cég kéttípusú robot összeszerelésével foglalkozik. Az első típusú robot R1-nek nevezik és darabja 50 euró profitot, a második típust R2-nek nevezik és darabja 40 euró profitot jövedelmez. A következő héten a két robot összeszerelésére 150 munkaóra áll rendelkezésre. Egy darab R1 összeszereléséhez 3 munkaóra és egy darab R2 összeszereléséhez pedig 5 munkaóra szükséges. A R2 olyan speciális processzort tartalmaz, amiből csak 20 darab van raktáron. A cég raktározási helysége 300 négyzetméter, amiből egy R1 8 négyzetmétert és egy R2 pedig 5 négyzetméter területet foglal el. A cég vezetősége maximalizálni szeretné a profitját. Milyen termelési tervet kövessen?
2016.09.26.
I. előadás
9
Matematikai modell 1. A döntési változók és a mértékegységek meghatározása: x1 az összeszerelendő R1 robotok darabszáma; x2 az összeszerelendő R2 robotok darabszáma.
2. A célfüggvény felírása. Mivel a cél a profit maximalizálása, ezért meghatározzuk, hogy ha a cég az (x1, x2) termelési tervet választja, azaz x1 darabot szerel össze a R1-ből és x2-őt a R2-ből, mennyi lesz a profitja. Tudjuk, hogy 1 darab R1 50 euró profitot eredményez. Tehát x1 darabnak 50x1 a profitja. Teljesen hasonlóan x2 darab R2 40x2 profitot eredményez. Tehát, a teljes profit: 50x1 + 40x2. Következésképpen a célfüggvény: z = 50x1 + 40x2. 2016.09.26.
I. előadás
10
3. A korlátozó feltételek megadása. Az összeszerelés időigényével kapcsolatos feltétel: mivel egy darab R1 összeszereléséhez 3 munkaóra és egy darab R2 összeszereléséhez 5 munkaóra szükséges, ezért x1 darab R1-et és x2 darab R2-t 3x1 + 5x2 munkaóra alatt szerelnek össze, ami nem lehet nagyobb, mint a rendelkezésre álló 150 munkaóra, vagyis 3x1 + 5x2 ≤150. A R2 processzorigényével kapcsolatos feltétel: mivel csak 20 darab processzor van raktáron, ezért: x2 ≤ 20. A raktározási feltétel: mivel egy R1 8 m2-t és egy R2 5 m2-t foglal el, ezért x1 darab R1 és x2 darab R2 összesen 8x1 + 5x2 m2 területet igényel, ami nem lehet nagyobb, mint a rendelkezésre álló 300 m2 raktározási felület. Következésképpen: 8x1 + 5x2 ≤ 300. A döntési változókra vonatkozó előjelkorlátozó feltételek: mivel az x1 és x2 darabszámokat jelölnek, ezért x1 ≤ 0, x2 ≤ 0, és x1, x2 egész számok. 2016.09.26.
I. előadás
11
Ha összegezzük az 1. 2. és 3. pontokban kapott összefüggéseket, az alábbi matematikai modellhez jutunk:
2016.09.26.
I. előadás
12
A lehetséges megoldások halmazának megszerkesztése Tekintünk egy olyan koordinátarendszert, amelynek a vízszintes tengelyen x1 döntési változót, a függőleges tengelyén pedig az x2 döntési változót vesszük fel. Az egyenlőtlenségekkel megadott korlátozó feltételek egy félsíkot, az egyenlőséggel megadott feltételek pedig egy egyenest határoznak meg. Ábrázoljuk a határegyeneseket: 3x1 + 5x2 = 150 x2 = 20 8x1 + 5x2 = 300 Ahhoz, hogy meghatározzuk a lehetséges megoldások halmazt ki kell számítsuk a három határegyenes páronkénti metszéspontjainak koordinátáit, azaz meg kell oldani a
2016.09.26.
I. előadás
13
Metszéspontok: F( 50/3 , 20), G(25, 20) és H(30, 12). Az M (lehetséges megoldások halmaza) egy olyan poliéder, amelynek csúcspontjai: O,E, F, H, D.
2016.09.26.
I. előadás
14
Sajátos esetek Alternatív vagy többszörös megoldások. Ha két egymásmelletti csúcspontban optimális megoldásokat kapunk, akkor a két csúcspontot összekötő szakasz minden pontja optimális pont. Ebben az esetben a szintvonal párhuzamos az optimális szakaszt tartalmazó egyenessel. Nincs lehetséges megoldás. Előfordulhat, hogy a korlátozó feltételek és az előjelkorlátozások által meghatározott tartományok metszete üres. Ekkor a LP-nek nincs megoldása. Az LP feladat nem nemkorlátos. Egy maximalizálási problémában a nemkorlátos eset akkor fordul elő, ha a lehetséges megoldások halmazában találhatók olyan pontok, amelyekhez tetszőlegesen nagy z értékek tartoznak. Ez csak akkor fordulhat elő, ha a profit szintvonalat a növekvő z irányába saját magával párhuzamosan mozgatjuk, és soha nem hagyjuk el a lehetséges megoldások halmazát. Hasonlóan a minimalizálási feladatoknál, ha a költség szintvonalat a csökkenő z irányába saját magával párhuzamosan mozgatjuk, és soha nem hagyjuk el a lehetséges megoldások halmazát. 2016.09.26.
I. előadás
15
