Bevezetés az operációkutatásba A lineáris programozás alapjai

Bevezetés az operációkutatásba A lineáris programozás alapjai Alkalmazott operációkutatás 1. elıadás 2008/2009. tanév 2008. szeptember 12. Smahó Melinda

Smahó Smahó Melinda

Mi az operációkutatás (operations research)? • Kialakulása: II. világháború alatt • Operációkutatás: a döntéshozatalt olyan tudományos eszközökkel közelítjük meg, amelyek segítségével meghatározható egy rendszer legjobb felépítése és mőködtetése olyan körülmények között, amikor a források szőkösen állnak rendelkezésre (Winston, 2003). – döntések elıkészítése, gazdasági optimum meghatározása matematikai szélsıérték feladat alkalmazásával – lineáris és nemlineáris programozási modellek, készletezési modellek, hálótervezés, sorbanállási elmélet, szimuláció, elırejelzési modellek

• Modell: az objektív valóságnak az ember által alkotott leegyszerősített képe


1

Az operációkutatás módszertana

Forrás: Winston, 2003. 2. o.


Bevezetés a lineáris programozásba

• • • •

optimalizálási problémák megoldásának egyik eszköze Walras (1870), Neumann (1939) G.B. Dantzig (1947) szimplex algoritmus kifejlesztése L.V. Kantorovics, T.C Koopmans, közgazdasági Nobel-díj (1975) • Kornai János: A gazdasági szerkezet matematikai tervezése


2

A lineáris programozás nagy alakjai

Leonid Vitaliyevich Kantorovich Academy of Sciences Moscow, USSR (1912-1986)

Tjalling C. Koopmans

G.B. Dantzig

Yale University New Haven, CT, USA

(1914-2005)

(1910-1985)

"The tremendous power of the simplex method is a constant surprise to me." Smahó Smahó Melinda

A lineáris programozás alapjai

Lineáris programozás: 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, minél nagyobb gazdasági haszon elérése érdekében (Ferenczi, 2006).


3

A lineáris programozási feladat Egy Fafaragó Cég kétfajta játékot gyárt: katonákat és vonatokat. Egy katonát 27$-ért lehet eladni, elıállításához 10$ értékő nyersanyag szükséges, és minden legyártott katona 14$-ral növeli a vállalat bérben jelentkezı változó költségeit. Egy vonat 21$-ért adható el, elıállításához 9$ értékő nyersanyag szükséges, és minden legyártott vonat 10$-ral növeli a cég változó- és általános költségeit. A katonák és vonatok gyártása kétféle szakképzett munkát igényel: fafaragó és felületkezelı munkát. Egy katona elıállításához 2 óra felületkezelı munka és 1 óra fafaragó munka szükséges. Egy vonathoz 1 óra felületkezelı és 1 óra fafaragó munka kell. A vállalatnak minden héten korlátlan mennyiségő nyersanyag áll rendelkezésére, de hetente csak 100 felületkezelı munkaóra és 80 fafaragó munkaóra használható fel. A vonatok iránti kereslet korlátlan, katonákból azonban legfeljebb csak 40 darabot vesznek meg hetente. A vállalat maximalizálni szeretné a heti profitot (bevételek – költségek). Keressünk a vállalat helyzetének leírására egy olyan matematikai modellt, amely a heti profitot maximalizálja! (Winston, 2003. 51. o. alapján) Smahó Smahó Melinda

A lineáris programozás alapfogalmai I. • Döntési változók: a jövıben meghozandó döntések leírására szolgálnak x1 = a hetente gyártott katonák száma x2 = a hetente gyártott vonatok száma • Célfüggvény: a maximalizálandó vagy minimalizálandó függvény (heti bevételek) – (nyersanyag költségek) – (egyéb változó költségek) → max heti bevételek (vonat + katona) = 27x1 + 21x2 heti nyersanyagköltség = 10x1 + 9x2 egyéb heti változó költségek = 14x1 + 10x2 célfüggvény: (27x1 + 21x2 ) – (10x1 + 9x2) – (14x1 + 10x2)→max célfüggvény (átrendezve): z = 3 x1 + 2 x2 →max a változó | célfüggvény együtthatója


4

A lineáris programozás alapfogalmai II. • Korlátozó feltételek: a változók értékeit korlátozó megszorítások felületkezelı feltétel: 2x1 + x2 ≤ 100 fafaragó feltétel: x1 + x2 ≤ 80 katonák iránti kereslet: x1 ≤ 40 – döntési változók korlátozó feltételekben szereplı együtthatói = technológiai együtthatók – feltételek jobb oldalán szereplı számok = jobb oldal

• Elıjelkorlátozások: a döntési változó pozitív és negatív értéket is felvehet-e? – döntési változó csak nemnegatív lehet: elıjelkorlátozó feltétel xi ≥ 0 – döntési változó pozitív és negatív értéket is felvehet: elıjelkorlátozatlan változó Smahó Smahó Melinda

Lineáris programozási feladat

felületkezelı feltétel: fafaragó feltétel: katonák iránti kereslet: nemnegativitási feltétel: nemnegativitási feltétel:

2x1 + x2 ≤ 100 x1 + x2 ≤ 80 x1 ≤ 40 ≥0 x1 x2 ≥ 0

z = 3x1 + 2x2 → max

KORLÁTOZÓ FELTÉTELEK NEMNEGATIVITÁSI FELTÉTELEK CÉLFÜGGVÉNY


5

Definíciók I. • Lineáris függvény: az f (x1, x2, ....., xn) akkor és csak akkor lineáris függvénye az x1, x2, ....., xn változóknak, ha valamely c1, c2, ......, cn konstansokra f (x1, x2, ....., xn) = c1x1 + c2x2 + ... + cnxn • Lineáris egyenlıtlenség: bármely f (x1, x2, ....., xn) lineáris függvény és tetszıleges b szám esetén f (x1, x2, ....., xn) ≤ b és f (x1, x2, ....., xn) ≥ b lineáris egyenlıtlenségek. c1x1 + c2x2 + ... + cnxn ≤ b c1x1 + c2x2 + ... + cnxn ≥ b

Forrás: Winston, 2003. 55. o. alapján


Definíciók II. A lineáris programozási feladat egy olyan optimalizálási feladat, amelyben a következık történnek: 1. Maximalizáljuk vagy minimalizáljuk a döntési változók egy lineáris függvényét. A maximalizálandó vagy minimalizálandó függvényt célfüggvénynek nevezzük. 2.A döntési változók értékeinek ki kell elégíteniük a korlátozó feltételeket. Minden feltételnek vagy lineáris egyenletnek vagy lineáris egyenlıtlenségnek kell lennie. 3.Minden változó esetében meg kell vizsgálni, hogy szükség van-e elıjelkorlátozásra (megengedett-e, hogy a változók negatív értéket is felvegyenek). Smahó Smahó Melinda

6

Köszönöm a figyelmet!


7

Bevezetés az operációkutatásba A lineáris programozás alapjai

Recommend Documents