---

Tartalom

1. Modellépítési alapelvek
1.1. A valószínűség maximalizálása
1.2. A hasznossági függvény
1.3. Az újságárusfiú problémája
1.4. Hatékony megoldások
1.5. Determinisztikusból sztochasztikus feladat
1.6. Várhatóérték programozás
1.7. Általános modellépítési elvek
1.8. Jelölések

2. Valószínűséggel korlátozott modellek
2.1. Általános elvek
2.2. Logkonkávitási eredmények
2.3. Valószínűségek kiszámítása normális eloszlás esetén
2.4. Korlátok a valószínűségekre
2.5. A STABIL modell
2.6. Megoldó algoritmusok

3. Kétlépcsős modellek
3.1. A kétlépcsős modelltípus alapjai
3.2. A pótló függvény kiszámítása
3.3. Korlátok a pótló függvényre
3.4. Megoldó algoritmusok

4. Szukcesszív regressziós approximáció
4.1. Egyenlet megoldása
4.2. Valószínűséggel korlátozott modellek
4.3. Kétlépcsős modellek
4.4. Kombinált modell
4.5. Sztochasztikus kvadratikus programozás

5. Irodalom

---

Bevezetés

A sztochasztikus programozás a véletlen jelenlétében való döntéshozatallal foglalkozik. Másképpen fogalmazva ez az a matematikai tudományág, amely optimális döntések vizsgálatával és meghatározásával foglalkozik olyan esetekben, amikor véletlen mennyiségeket is figyelembe kell venni a modellek felépítésében, az optimális döntés meghozásában és a döntés következményeinek kiértékelésében.

A jegyzetben a sztochasztikus programozás alapvető modelljeit és megoldási módszereit ismertetjük. Anyagunk négy nagyobb részből áll. Először az általános elvekkel foglalkozó részben különböző, a sztochasztikus programozásban használt modellépítési és döntéshozási elvekkel foglalkozunk. A 2. és a 3. Fejezetben a valószínűséggel korlátozott modellek és a kétlépcsős modellek tulajdonságait tárgyaljuk. Azért választottuk ezt a két modelltípust részletesebb tárgyalásra, mert ezeknek van alaposan kidolgozott matematikai elméletük és a gyakorlatban jól használható megoldó algoritmusuk, továbbá ennek a két modelltípusnak a vizsgálata és alkalmazása alkotja a sztochasztikus programozási kutatások nagy részét. A második és harmadik részben tárgyalt anyag lényegében a sztochasztikus lineáris programozás modelljeit és megoldó algoritmusait ismerteti. A negyedik részben a szukcesszív regressziós approximációk megoldási módszerét tárgyaljuk. Ez használható mindkét nagy modellcsalád esetében, azonkívül ennek használatával meg lehet oldani egy olyan kombinált feladatot is, amelyben valószínűséggel korlátozott feltétel is és a kétlépcsős feladatra jellemző pótló függvény is jelen van. Ennek az egységes megoldó algoritmusnak a kapcsán megmutatjuk, hogy olyan általános kvadratikus sztochasztikus programozási feladat is optimalizálható, amelyben mind kvadratikus feltételek, mind kvadratikus célfüggvény is szerepel.

Terjedelmi korlátok miatt nem tudunk minden, a sztochasztikus programozás témakörébe tartozó feladattal foglalkozni, a legfontosabb speciális eseteket azonban megemlítjük. Az érintett témákról és egyéb, itt nem tárgyalt lehetőségekről az irodalomban talál az olvasó részletesebb leírást - a jegyzet végén egy rövid ismertetésben és az utána következő irodalomjegyzékben a legfontosabb könyvekre és cikkekre felhívjuk a figyelmet. Bár a jegyzet az időkorlát miatt nem lett teljes, de véleményünk szerint így is jól használható - a közeljövőben egy bővített változat megírását tervezzük.

A jegyzetet a Budapesti Műszaki és Gazdaságtudományi Egyetemen ötödéves informatikus és matematikus hallgatóinak, 1993 és 2002 között tartott előadásaim alapján állítottam össze és elsősorban a számukra írtam. Az itt összefoglalt anyag egy féléves oktatásra alkalmas, esetleg további irodalom felhasználásával bővíthető. A jegyzet olvasása az alapvető matematikai és valószínűségszámítási eredményeken kívül feltételezi a lineáris és a nemlineáris optimalizálás elméletének és gyakorlatának ismeretét is. Az utóbbi két témakör nem közismert részeire röviden utalunk, az irodalomról szóló részben az ezekre vonatkozó utalásokat is lehet találni.

Ma már tucatnyinál is több összefoglaló jellegű könyvet írtak a sztochasztikus programozásról, de ezek kevéssé használhatók negyed vagy ötödéves hallgatók oktatására, magyar nyelven pedig tudtunkkal semmilyen sztochasztikus programozási jegyzet vagy könyv nem jelent meg. A jegyzettel ezt a hiányt szeretnénk pótolni. A jegyzet használatát azoknak is ajánljuk, akik a determinisztikus optimalizálás módszerein kívül szeretnék megismerni és munkájukban felhasználni a sztochasztikus programozás alapvető modelljeit.

Egy sztochasztikus programozási modellt három szempontból értékelhetünk: matematikai, számítástechnikai és alkalmazási szempontból. Tárgyalásmódunkban mindhárom szempont, lehetőleg kiegyensúlyozottan szerepel. A közölt modellek vizsgálatában nagy súlyt fektettünk arra, hogy precíz matematikai eszközökkel mutassuk meg a megengedett megoldások létezésének, illetőleg az optimalitási kritériumoknak a teljesülését. A számítástechnikai szempont figyelembevétele azt jelenti, hogy számítástechnikailag hatékony, gyakorlatilag alkalmazható algoritmusokkal foglalkozunk. Tárgyalásmódunk gyakorlatias - kisméretű numerikus példákkal szemléltetjük az elveket, továbbá az algoritmusokat olyan részletességgel írjuk le, hogy a matematikai levezetések teljes megértése nélkül is fel lehessen használni a leirt módszereket. Ezek a példák azt is lehetővé teszik, hogy a sztochasztikus programozás témakörébe elemi szinten betekintést nyerjenek más szakterületek kutatói, alkalmazói. Végül az alkalmazási szempontot is figyelembe vettük, - ahol lehet, már megtörtént gyakorlati alkalmazásokat mutatunk be, illetőleg ilyenekre hívjuk fel a figyelmet. Ezek az alkalmazási példák arra is rávilágítanak, hogy mennyire szerteágazóak a sztochasztikus programozás felhasználásának lehetőségei.

Ezt a jegyzetet Prékopa Andrásnak ajánlom, akitől az első lineáris programozási előadást hallgattam 1965-ben, majd évtizedeken át szerencsém volt az általa vezetett kutatócsoportokban dolgozni.

Budapest, 2003.
Deák István

---