Az operációkutatás fogalmának helyes meghatározása: Az operációkutatás tárgya és feladatai

1. Az AI alapfogalmai

ÉS RÓLA – tudományos szakvélemény, a különböző szervezeti rendszerek leghatékonyabb irányítását szolgáló módszerek kidolgozásával és gyakorlati alkalmazásával foglalkozik.

Az IO a következő szakaszokat tartalmazza:

1) matematikai program. (tervek, gazdasági tevékenységi programok indoklása); szakaszokat tartalmaz: lineáris program, nemlineáris program, dinamikus program

2) a véletlenszerű folyamatok elméletén alapuló sorelmélet;

3) játékelmélet, amely lehetővé teszi a hiányos információk körülményei között hozott döntések igazolását.

Egy adott vezérlési probléma megoldása során az AI módszerek használata magában foglalja:

Gazdasági és matematikai modellek felépítése döntéshozatali problémákhoz összetett helyzetekben vagy bizonytalanság körülményei között;

A döntéshozatalt utólag meghatározó összefüggések tanulmányozása és teljesítménykritériumok felállítása, amelyek lehetővé teszik egy adott cselekvési mód előnyeinek felmérését.

Az IO alapfogalmai és definíciói.

Művelet – minden olyan irányított tevékenység, amely egy cél elérésére irányul. A művelet eredménye a végrehajtás módjától, szervezésétől, egyébként - bizonyos paraméterek megválasztásától függ. Egy művelet mindig irányított esemény, vagyis rajtunk múlik, hogyan válasszunk ki néhány paramétert, amelyek a szervezetét jellemzik. A „szervezet” itt a szó tág értelmében értendő, beleértve a művelet során használt technikai eszközök összességét is.

A paraméterek bármilyen konkrét megválasztását hívjuk döntés . A döntések lehetnek sikeresek és sikertelenek, ésszerűek és ésszerűtlenek. Optimális fontolja meg azokat a megoldásokat, amelyek ilyen vagy olyan okból előnyösebbek, mint mások. Az operációkutatás fő feladata az optimális megoldások előzetes kvantitatív igazolása.

Működési modell – ez a művelet meglehetősen pontos leírása matematikai apparátussal (különféle függvények, egyenletek, egyenletrendszerek és egyenlőtlenségek stb.). Egy művelet modelljének elkészítéséhez a leírt jelenség lényegének megértése és a matematikai apparátus ismerete szükséges.

Működési hatékonyság – a feladathoz való alkalmazkodóképességének mértékét mennyiségileg egy hatékonysági kritérium - a célfüggvény - formájában fejezzük ki. A hatékonysági kritérium megválasztása határozza meg a vizsgálat gyakorlati értékét. (A rosszul megválasztott kritérium káros lehet, hiszen az ilyen hatékonysági kritérium szerint szervezett működés esetenként indokolatlan költségekkel jár.)

Hálózattervezési és -menedzsment feladatok vegyük figyelembe egy nagy műveleti komplexum (munkálatok) befejezési dátumai és a komplexum összes műveletének kezdési időpontja közötti kapcsolatot. Ezek a feladatok a műveletek minimális időtartamának, a költségértékek optimális arányának és végrehajtásuk időzítésének megtalálásából állnak.

Sorbaállási problémák Az alkalmazások vagy követelmények sorát tartalmazó szolgáltatási rendszerek tanulmányozására és elemzésére szolgálnak, és a rendszerek teljesítménymutatóinak, optimális jellemzőinek meghatározásából állnak, például a szolgáltatási csatornák számának, a szolgáltatási időnek stb.

Készletgazdálkodási feladatok a készletszint (rendelési pont) és a rendelési méret optimális értékeinek megtalálásából áll. Az ilyen feladatok sajátossága, hogy a készletek szintjének növekedésével egyrészt a tárolás költségei nőnek, másrészt csökkennek a tárolt termék esetleges hiánya miatti veszteségek.

Erőforrás-allokációs problémák bizonyos műveletek (munkák) során merülnek fel, amelyeket korlátozottan rendelkezésre álló erőforrásokkal kell elvégezni, és meg kell találni az erőforrások optimális elosztását a műveletek között vagy a műveletek összetételét.

Berendezés javítási és csere feladatok fontosak a berendezések elhasználódása és idővel történő cseréjének szükségessége miatt. A feladatok az optimális időzítés, a megelőző javítások és ellenőrzések számának meghatározásában, valamint a berendezések korszerűsített berendezésre való cseréjének időpontjában merülnek fel.

Feladatok ütemezése (ütemezése). a műveletek optimális sorrendjének meghatározása (például alkatrészek feldolgozása) különféle típusú berendezéseken.

Tervezési és elhelyezési feladatok nia az új objektumok optimális számának és helyének meghatározásából áll, figyelembe véve a meglévő objektumokkal és egymással való kölcsönhatásukat.

Útvonalválasztási problémák vagy hálózat a leggyakrabban felmerülő problémák a közlekedési és kommunikációs rendszerek különböző problémáinak tanulmányozása során, és a leggazdaságosabb útvonalak meghatározásából állnak.

2. Általános lineáris program probléma. A megoldás optimalizálása

Gazdasági-matematikai modell

Az LP a matematikának egy olyan ága, amely elméletet és numerikus módszereket fejleszt számos változó lineáris függvényének szélsőértékének (maximumának vagy minimumának) megtalálásához lineáris megszorítások, azaz ezeket a változókat összekötő egyenlőségek vagy egyenlőtlenségek jelenlétében.

Az LP módszereket olyan gyakorlati problémákra alkalmazzák, amelyekben: 1) ki kell választani a legjobb megoldást (optimális tervet) a sokféle lehetséges megoldás közül; 2) a megoldás néhány változó értékkészleteként fejezhető ki; a) a probléma konkrét feltételei által a megvalósítható megoldásokra szabott korlátozásokat lineáris egyenletek vagy egyenlőtlenségek formájában fogalmazzák meg; 4) a célt a fő változók lineáris függvényében fejezzük ki. A különböző megoldások összehasonlítását lehetővé tevő célfüggvény értékei a megoldás minőségének kritériumaként szolgálnak.

Egy közgazdasági probléma matematikai módszerekkel történő gyakorlati megoldásához mindenekelőtt közgazdasági-matematikai modellel kell felírni. A gazdasági-matematikai modell a vizsgált gazdasági folyamat vagy tárgy matematikai leírása. Ez a modell a gazdasági folyamat törvényszerűségeit absztrakt formában fejezi ki matematikai összefüggések segítségével.

A modellalkotás általános sémája: I

1) bizonyos számú változó mennyiség kiválasztása, amelyek számértékeinek hozzárendelése egyértelműen meghatározza a vizsgált jelenség egyik lehetséges állapotát;

2) a vizsgált jelenségben rejlő összefüggések kifejezése matematikai összefüggések (egyenletek, egyenlőtlenségek) formájában. Ezek a kapcsolatok a probléma korlátainak rendszerét alkotják;

3) a kiválasztott optimalitási kritérium mennyiségi kifejezése célfüggvény formájában; én

4) a probléma matematikai megfogalmazása a célfüggvény szélsőértékének megtalálásának problémájaként, a változókra szabott korlátozások teljesülése mellett.

Általános lineáris programozási probléma a következő formában van:

Adott egy m lineáris egyenletből és egyenlőtlenségből álló rendszer, n változóval

és lineáris függvény

Megoldást kell találni az X=(x1,x2,…,xj,…,xn) rendszerre, ahol az F lineáris függvény az optimális (azaz maximum vagy minimum) értéket veszi fel.

Az (1) rendszert kényszerrendszernek, az F függvényt pedig lineáris függvénynek, lineáris alaknak, célfüggvénynek vagy célfüggvénynek nevezzük.

Röviden, az általános lineáris programozási probléma a következőképpen ábrázolható:

korlátozásokkal:

Optimális megoldás (vagy optimális terv) egy LP probléma megoldása az X=(x1,x2,…,xj,…,xn), egy kényszerrendszer (1), amely kielégíti a (3) feltételt, amely mellett a (2) lineáris függvény felveszi az optimálisat. (maximum vagy minimum) érték.

Feltéve, hogy minden változó nem negatív, a megszorítások rendszere (1) csak egyenlőtlenségekből áll – egy ilyen lineáris programozási problémát standardnak (szimmetrikusnak) nevezünk; ha a kényszerrendszer csak egyenletekből áll, akkor a problémát kanonikusnak nevezzük.

A kanonikus probléma speciális esete egy olyan alapvető formájú probléma, amelyre jellemző, hogy a kényszervektor összes együtthatója b nem negatívak, és mindegyik egyenletben van egy 1-es együtthatójú változó, amely nem szerepel egyetlen más egyenletben sem. Az ezzel a tulajdonsággal rendelkező változót alapnak nevezzük.

A standard és a kanonikus problémák speciális esetei az általánosnak. Mindegyiket az adott területen használják. Sőt, mindhárom megfogalmazás ekvivalens egymással: bármely lineáris programozási probléma egyszerű matematikai transzformációk segítségével kanonikus, szabványos vagy általános problémává redukálható.

4 . A lineáris algebra elemei

Egy m lineáris egyenletrendszernek n változója van

vagy rövid formában

Egy m lineáris egyenletrendszer tetszőleges m változója n változóval (m< n) называются основными (или базисными), если определитель матрицы коэффициентов при них отличен от нуля. Такой определитель часто называют базисным минором матрицы А. Тогда остальные m–n переменных называются неосновными (или свободными).

A (2.1) rendszer megoldása m feltétel mellett< n сформулируем утверждение.

Nyilatkozat 2.1. Ha a rendszernekmlineáris egyenletek -valnváltozók (m < n) a változók együtthatói mátrixának rangja egyenlő m-rel, azaz. Ha van legalább egy alapváltozócsoport, akkor ez a rendszer határozatlan, és a nem alapváltozók tetszőleges értékkészlete a rendszer egy megoldásának felel meg.

Megoldás A (2.1) rendszer X=(x1,x2,…,xn)-ét akkor nevezzük megengedhetőnek, ha csak nem negatív komponenseket tartalmaz, pl. xj>=0 bármely j=1,n esetén. Ellenkező esetben a megoldást érvénytelennek nevezzük.

A rendszer végtelen számú megoldása között megkülönböztetik az ún. alapmegoldásokat.

Alap megoldás Az m lineáris egyenletrendszer n változós megoldása olyan megoldás, amelyben minden n–m kisebb változó nulla.

A lineáris programozási feladatokban különösen érdekesek az elfogadható alapmegoldások, vagy ahogy más néven referenciatervek. Degeneráltnak nevezzük azt az alapmegoldást, amelyben legalább az egyik főváltozó nullával egyenlő.

Konvex ponthalmazok

A konvex sokszöget a nem-konvextől megkülönböztető közös jellemző az, hogy ha bármelyik két pontját kivesszük és összekötjük egy szegmenssel, akkor a teljes szakasz ehhez a sokszöghez fog tartozni. Ez a tulajdonság felhasználható egy konvex ponthalmaz meghatározására.

A pontok halmazát konvexnek nevezzük, ha bármelyik két pontjával együtt tartalmazza az ezeket a pontokat összekötő teljes szakaszt.

A konvex halmazoknak fontos ingatlan: Tetszőleges számú konvex halmaz metszéspontja (közös része) konvex halmaz.

A konvex halmaz pontjai között megkülönböztethetünk belső, határ- és sarokpontokat.

Egy halmaz egy pontját belsőnek nevezzük, ha a szomszédságában csak ennek a halmaznak a pontjai vannak.

Egy halmaz egy pontját határpontnak nevezzük, ha valamelyik környéke az adott halmazhoz tartozó és nem hozzá tartozó pontokat is tartalmaz.

A lineáris programozási problémákban különösen érdekesek a sarokpontok. A halmaz pontját ún szögletes(vagy extrém), ha nem belső az adott halmazhoz teljes egészében tartozó szegmensben.

ábrán. A 2.4 példákat mutat be a sokszög különböző pontjaira: belső (M pont), határ (N pont) és sarok (A, B, C, D, E pontok). Az A pont egy sarokpont, mivel a teljes egészében egy sokszöghez tartozó szakasz, például az AP szakasz nem belső; Az A pont a KL szakaszon belül van, de ez a szakasz nem tartozik teljesen a sokszöghez.

Konvex halmaznál a sarokpontok mindig egybeesnek a sokszög (poliéder) csúcsaival, míg nem konvex halmaznál ez nem szükséges. Egy ponthalmazt zártnak nevezünk, ha az összes határpontját tartalmazza. A ponthalmazt ún korlátozott, ha a halmaz bármely pontjában van egy véges sugarú, középpontú golyó (kör), amely teljes egészében tartalmazza az adott halmazt; egyébként a halmaz korlátlannak mondható.

Egy véges sok sarokponttal rendelkező síkban lévő konvex zárt ponthalmazt konvex sokszögnek nevezzük, ha korlátos, és konvex sokszögtartománynak, ha nem korlátos.

Egyenlőtlenségek, egyenletek és rendszereik megoldásainak geometriai jelentése

Nézzük az egyenlőtlenségek megoldásait.

1. állítás Az a11x1+a12x2 kétváltozós egyenlőtlenség megoldási halmaza<=b1 является одной из двух полуплоскостей, на которые вся плоскость делится прямой a11x1+a12x2=b1 , включая и эту прямую, а другая полуплоскость с той же прямой есть множество решений неравен­ства a11x1+a12x2>=b1.

A kívánt félsík (felső vagy alsó) meghatározásához ajánlatos egy tetszőleges vezérlőpontot beállítani, amely nem a határán fekszik - a megépített egyenest. Ha egy egyenlőtlenség érvényes egy vezérlőpontban, akkor a vezérlőpontot tartalmazó félsík minden pontjában fennáll, és nem érvényes a másik félsík összes pontjában. Ezzel szemben, ha egy egyenlőtlenség nem teljesül egy vezérlőpontban, akkor nem teljesül a vezérlőpontot tartalmazó félsík minden pontjában, és teljesül a másik félsík összes pontjában. Célszerű az O (0;0) koordináták origóját venni, amely nem a megszerkesztett egyenesen fekszik, vezérlőpontnak.

Tekintsünk egy sor megoldást az egyenlőtlenségi rendszerekre.

2. állítás. A két változós lineáris egyenlőtlenségek együttes rendszerének megoldási halmaza egy konvex sokszög (vagy egy konvex sokszögtartomány).

Mindegyik egyenlőtlenség az 1. állításnak megfelelően meghatározza az egyik félsíkot, amely egy konvex ponthalmaz. A lineáris egyenlőtlenségek közös rendszerének megoldási halmaza olyan pontok, amelyek az összes egyenlőtlenség megoldási félsíkjaihoz tartoznak, azaz. kereszteződésükhöz tartoznak. A konvex halmazok metszéspontjára vonatkozó állítás szerint ez a halmaz konvex, és véges sok sarokpontot tartalmaz, pl. egy konvex sokszög (konvex sokszög terület).

A sarokpontok koordinátáit - a sokszög csúcsait - a megfelelő egyenesek metszéspontjainak koordinátáiként találjuk meg.

Az egyenlőtlenségi rendszerek megoldási területeinek megalkotásakor más esetek is előfordulhatnak: a megoldások halmaza egy konvex sokszögű terület (2.9. ábra, a); egy pont (2.9. ábra, b); üres halmaz, amikor az egyenlőtlenségek rendszere inkonzisztens (2.9. ábra, c).

5 . Geometriai módszer LP feladatok megoldására

optimális megoldás az LP problémára

1. tétel. Ha az LP feladatnak van optimális megoldása, akkor a lineáris függvény a megoldási poliéder egyik sarokpontjában veszi fel a maximális értékét. Ha egy lineáris függvény egynél több sarokpontban vesz fel egy maximális értéket, akkor bármely olyan pontban veszi fel, amely e pontok konvex lineáris kombinációja.

A tétel az LP problémák megoldásának alapvető módját jelzi. Valójában e tétel szerint ahelyett, hogy a megvalósítható megoldások végtelen halmazát tanulmányoznánk, hogy megtaláljuk közöttük a kívánt optimális megoldást, a megoldási poliédernek csak véges számú sarokpontját kell megvizsgálni.

A következő tétel a sarokpontok megtalálásának analitikai módszerével foglalkozik.

2. tétel. Az LP feladat minden megengedett alapmegoldása megfelel a megoldási poliéder egy sarokpontjának, és fordítva, a megoldási poliéder minden sarokpontjának egy-egy megengedett alapmegoldás.

Egy fontos következmény közvetlenül következik az 1. és 2. tételből: Ha egy LP-problémának van optimális megoldása, akkor az legalább az egyik elfogadható alapmegoldással egybeesik.

Így, az LP probléma lineáris függvényének optimumát a véges számú megengedhető alapmegoldása között kell keresni.

Tehát az LP probléma megvalósítható megoldásainak halmaza (megoldási poliéder) egy konvex poliéder (vagy konvex poliéder), és a probléma optimális megoldása a megoldási poliéder legalább egyik sarokpontjában található.

Tekintsük a problémát standard formában két változóval (P = 2).

Legyen a kényszerrendszer geometriai képe egy sokszög ABCDE(4.1. ábra). Ennek a sokszögnek a pontjai között meg kell találni egy pontot, ahol az F=c1x1+c2x2 lineáris függvény a maximális (vagy minimum) értéket veszi fel.

Tekintsük az ún szintvonal lineáris függvény F, azaz vonal, amely mentén ez a függvény ugyanazt a rögzített értéket veszi fel A, azaz F = A, vagy c1x1+c2x2=a.

Keresse meg a megoldási sokszögön azt a pontot, amelyen a függvényszint egyenes áthalad F a legmagasabb (ha a lineáris függvény maximalizálása) vagy a legalacsonyabb (ha minimalizálják) szinttel.

A c1x1+c2x2=a függvény szintegyenlete az egyenes egyenlet. Különböző szinteken A a szintvonalak párhuzamosak, mivel szögegyütthatóikat csak a c1 és c2 együtthatók közötti kapcsolat határozza meg, ezért egyenlők. Így a függvényszintű vonalak F – Ezek sajátos „párhuzamok”, amelyek általában szöget zárnak be a koordinátatengelyekkel.

A lineáris függvény szintvonalának fontos tulajdonsága, hogy a vonal párhuzamos eltolásakor az egyik irányba a szint csak nő, másik irányba tolva pedig csak csökken. Az origóból kilépő c=(c1,c2) ​​vektor az F függvény leggyorsabb növekedésének irányát jelzi. A lineáris függvény szintvonala merőleges a c=(c1,c2) ​​vektorra.

Az LP probléma grafikus megoldásának eljárása:

1. Szerkesszünk megoldások sokszögét!

2. Szerkesszünk meg egy c=(c1,c2) ​​vektort, és először rajzoljunk neki egy lineáris függvényszintvonalat F például F=0.

3. Az F=0 egyenes párhuzamos mozgatásával a c(-c) vektor irányában keressük meg azt az Amax(Bmin) pontot, ahol F eléri maximumát (minimumát).

1. Az optimális pontban metsző egyenesek egyenleteinek közös megoldásával keresse meg annak koordinátáit!

2. Számítsa ki az Fmax(Fmin) értéket.

Megjegyzés. A minimum pont a megoldási sokszög „belépési” pontja, a maximum pedig a „kilépési” pont a sokszögből.

6. A szimplex módszer általános ötlete. Geometriai értelmezés

A grafikus módszer a lineáris programozási feladatok igen szűk osztályára alkalmazható: hatékonyan képes megoldani legfeljebb két változót tartalmazó feladatokat. Figyelembe vették a lineáris programozás alaptételeit, amelyekből az következik, hogy ha egy lineáris programozási feladatnak van optimális megoldása, akkor az megfelel a megoldási poliéder legalább egy sarokpontjának, és egybeesik a megoldási poliéder legalább egyik megengedett alapmegoldásával. korlátok rendszere. Bármely lineáris programozási probléma megoldásának módját jelölték meg: felsorolni a kényszerrendszer véges számú megvalósítható alapmegoldását, és ezek közül kiválasztani azt, amelyiken a célfüggvény az optimális megoldást adja. Geometriailag ez megfelel a megoldási poliéder összes sarokpontjának számbavételének. Egy ilyen kimerítő keresés végső soron optimális megoldáshoz vezet (ha létezik), de gyakorlati megvalósítása óriási nehézségekkel jár, hiszen a valós problémák esetében a megvalósítható alapmegoldások száma, bár véges, rendkívül nagy lehet.

A keresendő megengedhető alapmegoldások száma csökkenthető, ha a keresést nem véletlenszerűen, hanem a lineáris függvény változásait figyelembe véve, pl. annak biztosítása, hogy minden következő megoldás „jobb” (vagy legalábbis „nem rosszabb”) legyen, mint az előző, a lineáris függvény értékei szerint (maximum megtalálásakor növelve, minimum megtalálásakor csökkentve) . Ez a keresés lehetővé teszi, hogy csökkentse a lépések számát, amikor megtalálja az optimálisat. Magyarázzuk meg ezt egy grafikus példával.

Legyen a megvalósítható megoldások tartománya sokszöggel ábrázolva ABCDE. Tegyük fel, hogy a sarokpontja A megfelel az eredeti megvalósítható alapmegoldásnak. A véletlenszerű kereséshez a sokszög öt sarokpontjának megfelelő öt megvalósítható alapmegoldást kell tesztelni. A rajzból azonban jól látszik, hogy a felső után A előnyös egy szomszédos csúcsba költözni BAN BEN, majd az optimális pontig VAL VEL.Öt helyett csak három csúcson mentünk keresztül, következetesen javítva a lineáris függvényt.

A megoldás egymás utáni javításának ötlete egy univerzális módszer alapját képezte a lineáris programozási problémák megoldására - szimplex módszer vagy a terv szekvenciális javításának módszere.

A szimplex módszer geometriai jelentése a kényszerpoliéder egyik csúcsából (amelyet kezdeti csúcsnak nevezünk) szekvenciális átmenetből áll a szomszédosba, amelyben a lineáris függvény a legjobb (legalábbis nem a legrosszabb) értéket veszi fel a korláthoz képest. a probléma célja; az optimális megoldás megtalálásáig - az a csúcs, ahol a célfüggvény optimális értékét elérjük (ha a feladatnak van végső optimuma).

A szimplex módszert először J. Danzig amerikai tudós javasolta 1949-ben, de még 1939-ben a módszer ötleteit L. V. orosz tudós dolgozta ki. Kantorovics.

A szimplex módszer, amely lehetővé teszi bármely lineáris programozási probléma megoldását, univerzális. Jelenleg számítógépes számításokhoz használják, de a szimplex módszerrel egyszerű példák kézzel is megoldhatók.

A szimplex módszer - a megoldás szekvenciális javítása - megvalósításához elsajátításra van szükség három fő elem:

módszer egy probléma kezdeti megvalósítható alapvető megoldásának meghatározására;

a legjobb (pontosabban, nem rosszabb) megoldásra való áttérés szabálya;

kritérium a talált megoldás optimálisságának ellenőrzésére.

A szimplex módszer használatához a lineáris programozási feladatot le kell redukálni kanonikus formára, azaz. a kényszerrendszert egyenletek formájában kell bemutatni.

A szakirodalom kellően részletesen leírja: a kezdeti támogatási terv (kezdetben elfogadható alapmegoldás) megtalálása, mesterséges bázis módszer alkalmazása is, az optimális támogatási terv megtalálása, feladatok megoldása szimplex táblák segítségével.

7 . A szimplex módszer algoritmusa.

Tekintsük a ZLP szimplex módszerrel történő megoldását, és mutassuk be a maximalizálási probléma kapcsán.

1. A feladat feltételei alapján összeállítjuk annak matematikai modelljét.

2. Az elkészült modellt a rendszer kanonikus formára konvertálja. Ebben az esetben egy kezdeti referenciatervvel rendelkező alap azonosítható.

3. A probléma kanonikus modellje szimplex tábla formájában van megírva, így minden szabad tag nem negatív. Ha a kezdeti referenciaterv van kiválasztva, folytassa az 5. lépéssel.

Szimplex tábla: egy kényszeregyenletrendszert és egy célfüggvényt a kezdeti alaphoz képest feloldott kifejezések formájában kell megadni. Azt a sort, amelybe az F célfüggvény együtthatóit írjuk, F-egyenesnek vagy célfüggvény egyenesnek nevezzük.

4. A kiindulási referenciatervet úgy találjuk meg, hogy szimplex transzformációkat hajtunk végre a minimális szimplex relációknak megfelelő pozitív feloldó elemekkel, az F-soros elemek előjeleinek figyelembevétele nélkül. Ha a transzformációk során egy 0 sorral találkozunk, amelynek a szabad tag kivételével minden eleme nulla, akkor a probléma kényszeregyenletrendszere inkonzisztens. Ha olyan 0 sorral találkozunk, amelyben a szabad tagon kívül nincs más pozitív elem, akkor a restriktív egyenletrendszernek nincsenek nemnegatív megoldásai.

A (2.55), (2.56) rendszer redukcióját új alapra hívjuk szimplex transzformáció . Ha a szimplex transzformációt formális algebrai műveletnek tekintjük, akkor észrevehető, hogy e művelet eredményeként a szerepek egy bizonyos lineáris függvényrendszerben szereplő két változó között újra eloszlanak: az egyik változó függőből függetlenné válik, a másik pedig , ellenkezőleg, függetlenről függővé. Ez a művelet az algebrában ún Jordan kieső lépés.

5. A talált kezdeti támogatási tervet megvizsgáljuk az optimálisság szempontjából:

a) ha az F-sorban nincsenek negatív elemek (nem számítva a szabad tagot), akkor a terv optimális. Ha nincsenek nullák, akkor csak egy optimális terv van; ha van legalább egy nulla, akkor végtelen sok optimális terv van;

b) ha az F-sorban van legalább egy negatív elem, amely megfelel a nem pozitív elemek oszlopának, akkor;

c) ha az F-sorban van legalább egy negatív elem, és az oszlopában van legalább egy pozitív elem, akkor áttérhet egy új, az optimálishoz közelebbi referenciatervre. Ehhez a megadott oszlopot feloldó oszlopnak kell kijelölni, a minimális szimplex arány segítségével meg kell keresni a feloldó sort és végrehajtani egy szimplex transzformációt. Az így kapott referenciatervet ismét megvizsgáljuk az optimálisság szempontjából. A leírt folyamatot addig ismételjük, amíg el nem születik egy optimális terv, vagy amíg a probléma megoldhatatlansága meg nem állapítható.

A bázisban szereplő változó együtthatók oszlopát feloldásnak nevezzük. Így az F-sor negatív eleme alapján a bázisba bevitt változó kiválasztásával (vagy feloldó oszlop kiválasztásával) biztosítjuk, hogy az F függvény növekedjen. .

Kicsit nehezebb meghatározni a bázisból kizárandó változót. Ehhez összeállítják a szabad tagok arányát a feloldó oszlop pozitív elemeihez (az ilyen relációkat szimplexnek nevezik), és megkeresik közülük a legkisebbet, amely meghatározza a kizárt változót tartalmazó sort (feloldást). A bázisból kizárt változó (illetve a feloldósor választása) a minimális szimplex reláció szerint garantálja a már megállapított báziskomponensek pozitivitását az új referenciatervben.

Az algoritmus 3. pontjában feltételezzük, hogy a szabad kifejezések oszlop összes eleme nem negatív. Ez a követelmény nem szükséges, de ha teljesül, akkor minden további szimplex transzformáció csak pozitív feloldóelemekkel történik, ami kényelmes a számításokhoz. Ha a szabad kifejezések oszlopban negatív számok vannak, akkor a feloldó elemet a következőképpen kell kiválasztani:

1) nézzük végig a valamilyen negatív szabad tagnak megfelelő sort, például egy t-sort, és válasszunk ki benne valamilyen negatív elemet, és a megfelelő oszlopot tekintjük megoldónak (feltételezzük, hogy a probléma korlátai konzisztensek);

2) hozza létre a szabad kifejezések oszlopának elemeinek viszonyait a feloldó oszlop megfelelő, azonos előjelű elemeihez (simplex relációk);

3) válassza ki a legkisebb szimplex relációt. Ez határozza meg az engedélyezési karakterláncot. Legyen ez pl. R-vonal;

4) a feloldó oszlop és sor metszéspontjában egy felbontó elem található. Ha az y-sor eleme feloldónak bizonyul, akkor a szimplex transzformáció után ennek a sornak a szabad tagja pozitív lesz. Ellenkező esetben a következő lépésben ismét a t-sor érhető el. Ha a probléma megoldható, akkor bizonyos számú lépés után nem marad negatív elem a szabad kifejezések oszlopában.

8. Inverz mátrix módszer

Tekintsünk egy LP-t a következő formában:

A – kényszermátrix;

C=(c1,c2,…,cn)–sorvektor;

X=(x1,x2,…,xn) – változók;

a jobb oldal vektora.

Feltételezzük, hogy minden egyenlet lineárisan független, azaz. rang(a)=m. Ebben az esetben az alap az A mátrix rendjének minora. Azaz, van legalább egy m rendű B almátrix, amelyre |B|<>0. Minden B-nek megfelelő ismeretlent alapnak nevezünk. Az összes többi ingyenes.

Legyen B valamilyen alap. Ekkor az A mátrix oszlopait átrendezve mindig redukálhatjuk A-t A=(B|N) alakra,

ahol N egy almátrix, amely az A mátrix oszlopaiból áll, amelyek nem tartoznak a bázishoz. Ugyanígy lehetséges az x vektor felosztása az és az alapváltozók vektorává.

Az (1) probléma bármely megoldása kielégíti az A*x=b feltételt, és ezért a rendszer a következő formát ölti:

Mert |B|<>0, akkor van egy inverz mátrix. Ha balról megszorozzuk az inverzt, a következőt kapjuk:

- közös döntés.

Az alapmegoldás (a B bázishoz viszonyítva) a (2) feladat speciális megoldása, amelyet a feltétel alapján kapunk. Ezután egyedileg határozzák meg.

Az alapmegoldást ún megvalósítható, Ha.

A megvalósított alapmegoldásnak megfelelő alap. Hívott megvalósítható alapon. Az alapmegoldást degeneráltnak nevezzük, ha a vektornak nulla komponense van.

Az általános megoldás tartalmazza az összes létező megoldást. Térjünk vissza a célfüggvényhez. Bevezetjük a Cb – együtthatókat az alapváltozók elé, Cn – a többit.

Így kapjuk. Helyettesítjük az általános megoldásból:

Nyilatkozat. Az alapmegoldás optimálissági kritériuma.

Mondjuk. Ekkor az alapmegoldás az optimális. Ha, akkor az alapmegoldás nem optimális.

Dokumentum: Legyen. Tekintsük az alapmegoldást, .

Ezért az alapmegoldás célfüggvényének értéke.

Legyen más megoldás is: (Xb,Xn).

Akkor nézzük

Így az alapmegoldás a leginkább min. Ellenkezőleg, ne teljesüljön, i.e. létezik.

Ekkor van olyan megoldás, amelynél a célfüggvény értéke kisebb lesz, mint az alapmegoldás célfüggvényének értéke.

Legyen ez egy szabad Xi:Xj változónak felel meg, adunk egy értéket és beírjuk a bázisba, majd származtatunk egy másik változót és szabadnak nevezzük.

Hogyan határozzuk meg? Az összes szabad változó, kivéve, továbbra is egyenlő 0-val.

Aztán az általános megoldásban hol.

Vegyük ki: – szükséges feltétel.

Az alapmegoldást szabályosnak nevezzük, ha. A változót a bázisból származtatjuk. Új megoldással a célfüggvény csökken, mert

Algoritmus:

1.LP probléma szabványos formában.

2. Lineárisan független egyenleteket hagyunk.

3. Keressen egy olyan B mátrixot, amelyre |B|<>0 és az alapmegoldás.

Kiszámoljuk:

ha, akkor van optimális megoldás – ez az alapmegoldás;

ha, akkor megtaláljuk a komponenst, hozzáadjuk, és így találunk egy másik megoldást; – amelyben az egyik alapváltozó =0. Ezt a változót eltávolítjuk az alapból, és bevezetjük az xi-t. Kaptunk egy új B2 bázist, amely konjugált a B1 bázishoz. Ezután újra számolunk.

1. Ha van optimális megoldás, akkor véges számú lépés után azt kapjuk.

Geometriailag az eljárást úgy értelmezik, mint egy sarokpontból egy konjugált sarokpontba való átmenetet az X halmaz határa mentén - a probléma megoldásainak halmaza. Mert véges sok sarokpont van és az F(x) függvény szigorú csökkenése megtiltja, hogy ugyanazon a szélső ponton kétszer áthaladjunk, majd ha van optimális megoldás, akkor véges számú lépés után azt kapjuk.

9. A probléma közgazdasági értelmezése az erőforrás-felhasználási problémával párhuzamosan

Feladat. Kétféle P1 és P2 termék előállításához négyféle S1, S2, S3, S4 erőforrást használnak. Az erőforrás tartalékok, egy termelési egység előállítására fordított erőforrás egységek száma adott. A P1 és P2 termelési egységből származó nyereség ismert. Olyan termelési tervet kell készíteni, amelyben az értékesítésből származó nyereség maximális lesz.

Feladatén(eredeti):

F=c1x1+c2x2+…+CnXn->max korlátozásokkal:

és a nem-negativitás feltétele x1>=0, x2>=0,…,Xn>=0

Készítsen X=(x1,x2,…,Xn) termelési tervet, amelyben a termékértékesítésből származó nyereség (bevétel) maximális lesz, feltéve, hogy az egyes terméktípusok erőforrás-felhasználása nem haladja meg a rendelkezésre álló tartalékokat

FeladatII(dupla)

Z=b1y1+b2y2+…+BmYm->min

korlátozásokkal:

és a nem-negativitás feltétele

y1>=0, y2>=0,…,yn>=0.

Keressen egy olyan Y=(y1,y2,…,yn) erőforrásárak (becslések) halmazát, amelynél az erőforrások összköltsége minimális lesz, feltéve, hogy az egyes terméktípusok előállítása során az erőforrások költsége nem kevesebb, mint a termék értékesítéséből származó nyereség (bevétel).

A fenti modellben bi(i=1,2,…,m) az Si erőforrás tartalékot jelöli; aij – egy termelési egység előállításához felhasznált Si erőforrás egységeinek száma Pj(j=1,2,…,n); cj– Pj termelési egység értékesítéséből származó nyereség (bevétel) (vagy Pj termékár) .

Tegyük fel, hogy egy szervezet úgy döntött, hogy megvásárolja a vállalkozás S1, S2,..., Sm erőforrásait, és ezekre az y1, y2,..., ym erőforrásokra optimális árat kell beállítani. Nyilvánvalóan a beszerző szervezet érdekelt abban, hogy minden Z erőforrást b1,b2,…,bm mennyiségben költsön. y1,y2,…,ym árakon rendre minimálisak voltak, pl. Z=b1,y1+b2y2+…+bmym->min.

Másrészt az erőforrásokat értékesítő vállalkozás abban érdekelt, hogy a kapott bevétel ne legyen kevesebb, mint amennyit a vállalkozás az erőforrások késztermékké történő feldolgozásakor kaphat.

Egy egység P1 termék előállításához a11 egységnyi S1 erőforrást, a21 egységnyi S2 erőforrást,...., aj1 egységnyi erőforrást Si1,......, am1 egységnyi Sm erőforrást fogyasztanak el y1 áron ,y1,...,yi,...,ym, ill. Ezért az eladó igényeinek kielégítése érdekében a P1 termékegység előállításához felhasznált erőforrások költsége nem lehet kevesebb, mint annak c1 ára, azaz. a11y1+a21y2+…+am1ym>=c1.

Hasonlóképpen korlátozásokat hozhat létre egyenlőtlenségek formájában minden egyes P1, P2,…Pn terméktípushoz. Az így kapott II. kettős probléma közgazdasági-matematikai modellje és értelmes értelmezése a táblázat jobb oldalán található.

Az y1,y1,…,yi,…,ym erőforrásárak különböző elnevezéseket kaptak a közgazdasági szakirodalomban: számvitel, implicit, árnyék . Ezeknek a neveknek az a jelentése, hogy az feltételes , "hamis" árak. Ellentétben a termékek „külső” áraival c1,c2,…,cn, amelyek általában a gyártás megkezdése előtt ismertek, az erőforrásárak y1,y2,…,ym vannak belső , mert nem kívülről adják, hanem közvetlenül a probléma megoldása eredményeként határozzák meg, ezért gyakrabban ún. becslések erőforrások.

10. Kölcsönösen kettős LP problémák és tulajdonságaik

Tekintsük formálisan a lineáris programozás két, a táblázatban bemutatott I. és II. problémáját, elvonatkoztatva a gazdasági és matematikai modelljeikben szereplő paraméterek értelmes értelmezésétől.

Mindkét feladatnak a következő jellemzői vannak tulajdonságok:

1. Az egyik feladatban egy lineáris függvény maximumát, a másikban a minimumát keressük.

2. Az egyik probléma lineáris függvényében szereplő változók együtthatói egy másik probléma korlátozásrendszerének szabad tagjai.

3. A feladatok mindegyike szabványos formában van megadva, a maximalizálási feladatban pedig a " forma összes egyenlőtlensége"<=", а в задаче минимизации – все неравенства вида ">=".

4. A változók együtthatói mátrixai mindkét probléma kényszerrendszerében transzponálva vannak egymásra.

5. Egy probléma kényszerrendszerében az egyenlőtlenségek száma egybeesik egy másik probléma változóinak számával.

6. A változók nem-negativitásának feltételei mindkét feladatban megmaradnak.

Megjegyzés. Ha az eredeti feladat j-edik változójára nem-negativitási feltételt szabunk, akkor a duális probléma j-edik megszorítása egyenlőtlenség lesz, de ha a j-edik változó pozitív és negatív értéket is felvehet, akkor a duális probléma j-edik kényszere egyenlet lesz; az eredeti probléma megszorításai és a duál változói hasonló módon kapcsolódnak egymáshoz.

Két I. és II. lineáris programozási feladatot, amelyek a jelzett tulajdonságokkal rendelkeznek, szimmetrikus kettős feladatnak nevezzük. A következőkben az egyszerűség kedvéért egyszerűen nevezzük őket kettős feladat.

Minden LP probléma kettős feladatához társítható.

11. Algoritmus kettős feladat összeállításához:

1. Csökkentsük az eredeti probléma kényszerrendszerének minden egyenlőtlenségét egyetlen jelentésre: ha az eredeti feladatban egy lineáris függvény maximumát keresik, akkor a megszorítási rendszer összes egyenlőtlenségét redukáljuk a következő alakra:<=", а если минимум – к виду ">=". Azokra az egyenlőtlenségekre, amelyekben ez a követelmény nem teljesül, szorozza meg –1-gyel.

2. Állítsa össze az A rendszer kiterjesztett mátrixát, amely a változók együtthatóinak mátrixát, a korlátozási rendszer szabad tagjainak oszlopát és a változók együtthatóinak sorát tartalmazza egy lineáris függvényben.

3. Keresse meg az A mátrixra transzponált mátrixot .

4. Fogalmazzon meg egy kettős feladatot a kapott mátrix alapján és a változók nem-negativitásának feltételei: a duális probléma célfüggvényét alkotják, az eredeti probléma megszorítási rendszerének szabad tagjait véve együtthatónak a változókhoz; alkosson megszorító rendszert a kettős feladatra, a változókhoz mátrixelemeket, az eredeti probléma célfüggvényében szereplő változókra pedig szabad tagként vegyen együtthatókat, és írja le az ellenkező értelmű egyenlőtlenségeket; írja le a duális feladat változóinak nem-negativitásának feltételét!

12. Első dualitástétel

A duális problémák optimális megoldásai közötti kapcsolat dualitástételek segítségével jön létre.

Az optimálisság elégséges jele.

Ha X*=(x1*,x2*,…,xn*) És Y*=(y1*,y2*,…,ym*) – elfogadható megoldások a kölcsönösen kettős problémákra, amelyekre az egyenlőség vonatkozik,

akkor az eredeti I. feladat és a II. kettős feladat optimális megoldása.

A kölcsönösen kettős problémák optimálisságának kellő jele mellett megoldásaik között más fontos összefüggések is vannak. Mindenekelőtt felmerülnek a kérdések: mindig vannak-e egyidejűleg optimális megoldások minden kettős problémapárra? Lehetséges, hogy a kettős problémák közül az egyiknek van megoldása, a másiknak pedig nincs? Ezekre a kérdésekre a következő tétel adja meg a választ.

Az első (fő) dualitástétel. Ha a kölcsönösen duális problémák egyikének van optimális megoldása, akkor a másiknak is van, és a lineáris függvényeik optimális értékei megegyeznek:

Fmax = Zmin vagy F(X*)=Z(Y*) .

Ha az egyik feladat lineáris függvénye nem korlátozott, akkor a másik probléma feltételei ellentmondásosak (a feladatnak nincs megoldása).

Megjegyzés. A fő dualitástétel második részére fordított állítás általános esetben nem igaz, azaz. abból, hogy az eredeti probléma feltételei ellentmondásosak, nem következik, hogy a duális probléma lineáris függvénye korlátlan.

Az első dualitástétel közgazdasági jelentése.

Gyártási terv X*=(x1*,x2*,…,xn*) és az erőforrások árkészlete (becslése) Y*=(y1*,y2*,…,ym*) akkor és csak akkor válik optimálisnak, ha a termékekből származó haszon (bevétel) „külső” (előre ismert) árakon c1, c2,…, cn megegyezik a „belső” (csak meghatározott) erőforrások költségeivel. a feladat megoldásából) árak y1 ,y2,…,ym. Minden más tervhez xÉs Y Mindkét probléma esetén a termékekből származó profit (bevétel) mindig kisebb (vagy egyenlő), mint az erőforrásköltség.

Az első kettősségi tétel közgazdasági jelentése a következőképpen értelmezhető: a vállalkozásnak közömbös, hogy az optimális X*=(x1*,x2*,…,xn*) terv szerint gyártson-e termékeket és maximális profitot (bevételt) kap-e Fmax. vagy értékesítse az erőforrásokat optimális áron Y* =(y1*,y2*,…,ym*) és az értékesítésből megtéríteni a minimális erőforrásköltséget Zmin.

13. Második dualitástétel

Adjunk meg két, kölcsönösen kettős feladatot. Ha ezeket a problémákat szimplex módszerrel oldjuk meg, akkor kanonikus formába kell hozni őket, amihez be kell vezetni az I. feladat (röviden jelölés) kényszerrendszerébe. T nem negatív változók, és a II. feladat kényszerrendszerébe () – n nem negatív változók, ahol i(j) annak az egyenlőtlenségnek a száma, amelybe a további változót bevezetjük.

A kölcsönösen kettős problémák mindegyikének korlátozási rendszere a következőképpen alakul:

Állítsunk fel egyezést az egyik kettős feladat kezdőváltozói és a másik probléma (tábla) további változói között.

Tétel. Az egyik kölcsönösen duális probléma optimális megoldásának pozitív (nem nulla) komponensei a másik probléma optimális megoldásának nulla összetevőinek felelnek meg, azaz. bármely i=1,2,…,m u j=1,2,…,n esetén: ha X*j>0, akkor; Ha , akkor és hasonlóképpen,

ha akkor ; ha akkor.

Ebből a tételből az a fontos következtetés következik, hogy a kölcsönösen duális problémák változói között bevezetett megfeleltetés az optimum elérésekor (azaz az egyes problémák szimplex módszerrel történő megoldásának utolsó lépésében) a kölcsönösen kettős feladatok változói közötti megfelelést jelenti. fő-(szabály szerint nem egyenlő nullával) az egyik kettős probléma változói és nem mag(nullával egyenlő) egy másik probléma változói, ha megvalósítható alapmegoldásokat alkotnak.

Második dualitástétel. A kettős probléma optimális megoldásának összetevői megegyeznek az eredeti probléma lineáris függvényének megfelelő változóinak együtthatóinak abszolút értékeivel, az optimális megoldás nem alapváltozóival kifejezve.

Megjegyzés. Ha a kölcsönösen duális problémák egyikében az optimális megoldás egyedisége sérül, akkor a duális probléma optimális megoldása degenerált. Ennek az az oka, hogy ha az eredeti probléma optimális megoldásának egyedisége sérül, akkor a nem alapváltozókra vonatkozó optimális megoldása lineáris függvényének kifejezésében legalább egy fő változó hiányzik.

14. Objektíven meghatározott értékelések és jelentésük

A kettős probléma optimális megoldásának összetevőit az eredeti probléma optimális (duális) becslésének nevezzük. L. V. Kantorovich akadémikus hívta őket objektíven meghatározott" becslések ( a szakirodalomban rejtett jövedelemnek is nevezik) .

Az eredeti I. feladat további változói, amelyek az S1, S2, S3, S4 erőforrások bi tartalékai közötti különbséget jelentik és fogyasztásukat, expressz fennmaradó források , és a II. kettős probléma további változói, amelyek az egységnyi kibocsátás előállításához szükséges erőforrások költségei és a P1, P2 termékek cj ára közötti különbséget jelentik. , Expressz többletköltség az ár felett.

Az erőforrások objektíven meghatározott felmérései tehát meghatározzák az erőforrások szűkösségének mértékét: az optimális termelési terv szerint a szűkös (azaz teljesen felhasznált) erőforrások nem nulla, a nem szűkös erőforrások pedig nulla értékelést kapnak. Az y*i érték az i-edik erőforrás értékelése. Minél nagyobb az y*i becslés értéke, annál nagyobb az erőforrás szűkössége. Nem szűkös erőforrás esetén y*i=0.

Tehát az optimális gyártási tervbe csak a jövedelmező, nem jövedelmező terméktípusok kerülhetnek be (a jövedelmezőségi kritérium azonban itt egyedülálló: a termék ára nem haladja meg a gyártás során felhasznált erőforrások költségeit, hanem pontosan egyenlő velük).

Harmadik dualitástétel . A duális probléma optimális megoldásának összetevői megegyeznek a lineáris függvény parciális deriváltjainak értékeivel Fmax(b1, b2,…, bm)a megfelelő érvek szerint, i.e.

Az objektíven meghatározott erőforrásbecslések azt mutatják meg, hogy a termékértékesítésből származó maximális nyereség (bevétel) hány pénzegységben változik, ha a megfelelő erőforrás állománya egy egységgel változik.

A kettős értékelés eszközül szolgálhat az elemzéshez és a megfelelő döntések meghozatalához a folyamatosan változó termelés körülményei között. Például objektíven meghatározott erőforrásbecslések segítségével össze lehet hasonlítani az optimális feltételes költségeket és a termelési eredményeket.

Az erőforrások objektíven meghatározott becslései lehetővé teszik, hogy nem bármilyen, hanem csak viszonylag kis erőforrás-változás hatását ítéljük meg. Hirtelen változások esetén maguk a becslések is eltérőek lehetnek, ami lehetetlenné teszi a termelés hatékonyságának elemzését. Az objektíven meghatározott értékelések arányai alapján meghatározhatók az erőforrások helyettesíthetőségének számított normái, amelyek mellett a kettős értékelések stabilitásának határain belül végrehajtott pótlások nem befolyásolják az optimális terv eredményességét. Következtetés. A kettős becslések a következők:

1. Az erőforrások és termékek szűkösségének mutatója.

2. A korlátozások célfüggvény értékére gyakorolt ​​hatásának mutatója.

3. Egyes termékek gyártási hatékonyságának mutatója az optimalitási kritérium szempontjából.

4. Eszköz az összes feltételes költség és eredmény összehasonlítására.

15. A szállítási probléma megfogalmazása a költségkritérium alapján.

A TK - a homogén vagy felcserélhető termék előállítási helyétől (indulóállomástól) a fogyasztási helyig (célállomásig) történő szállításának leggazdaságosabb tervének problémája - az LP legfontosabb speciális problémája, amely kiterjedt gyakorlati alkalmazásokkal rendelkezik. nem csak a közlekedési problémákra.

A műszaki specifikációt az LP-ben a gazdasági jellemzőinek bizonyossága, a matematikai modell jellemzői és a specifikus megoldási módszerek jelenléte különbözteti meg.

A műszaki leírás legegyszerűbb megfogalmazása a költségkritérium szerint a következő: in T az A1,…,Am kiindulási pontokon a1,…,am homogén rakomány (erőforrások) egységeit kell szállítani. n fogyasztók B1,…,Bn mennyiségben b1,…,bn egység (szükséglet). Egy rakományegység i-edik kiindulási ponttól a j-edik fogyasztási pontig történő szállításának Cij szállítási költsége ismert.

Szállítási tervet kell készíteni, azaz meg kell találni, hogy az i-edik kiindulási ponttól a j-edik fogyasztási pontig hány egységnyi rakományt kell elküldeni, hogy az igényeket maradéktalanul kielégítsük és a teljes szállítást költségek minimálisak.

Az érthetőség kedvéért táblázat formájában mutatjuk be a műszaki specifikáció feltételeit ún terjesztés .

Szolgáltató	Fogyasztó			Rakománykészlet
Szükség

Itt az i-edik indulási ponttól a j-edik célállomásig szállított rakomány mennyisége egyenlő xij-vel, az i-edik indulási pont rakományállományát az ai>=0 érték határozza meg, és a rakományszükséglet a j-edik célállomáson bj>=0 . Feltételezzük, hogy minden xij>=0.

A mátrix az ún tarifamátrix (költségek vagy szállítási költségek).

Közlekedési feladatterv mátrixnak nevezzük, ahol minden xij szám az i-edik kiindulási ponttól a j-edik célállomásig szállítandó rakományegységek számát jelöli. Az xij mátrixot ún szállítási mátrix.

A szállítási terv megvalósításához kapcsolódó összes költség a célfüggvénnyel ábrázolható

Az xij változóknak meg kell felelniük a készletekre, a fogyasztókra és a nem-negatívitási feltételekre vonatkozó korlátozásoknak:

– a tartalékokra vonatkozó korlátozások (2);

– fogyasztókra vonatkozó korlátozások (2);

– nem-negatív feltételek (3).

Így matematikailag a közlekedési probléma a következőképpen fogalmazódik meg. Adott a (3) feltétel szerinti korlátozásrendszer (2) és a célfüggvény (1). A (2) rendszer megoldási halmazai között olyan nemnegatív megoldást kell találni, amely minimalizálja az (1) függvényt.

Az (1) – (3) feladat kényszerrendszere m+n egyenletet tartalmaz Tn változók. Feltételezzük, hogy az összes tartalék egyenlő a teljes szükséglettel, azaz.

16. A közlekedési probléma megoldhatóságának jele

Ahhoz, hogy egy közlekedési probléma elfogadható tervei legyenek, szükséges és elégséges az egyenlőség kielégítése.

Kétféle közlekedési probléma létezik: zárva , amelyben a szállítók teljes rakománymennyisége megegyezik a fogyasztók összkeresletével, és nyisd ki , amelyben a beszállítók összes termelési kapacitása meghaladja a fogyasztói keresletet vagy a fogyasztói kereslet nagyobb, mint a szállítók tényleges összkapacitása, azaz.

A nyitott modell zárttá alakítható. Tehát, ha, akkor egy fiktív (n+1)-edik úti célt bevezetünk a közlekedési probléma matematikai modelljébe. Ebből a célból a feladatmátrix egy további oszlopot tartalmaz, amelyre a kereslet megegyezik a szállítók teljes kapacitása és a fogyasztók tényleges kereslete közötti különbséggel:

Az eddig a pontig tartó rakományszállítási díjakat nullával egyenlőnek kell tekinteni. Ez a probléma nyitott modelljét zárttá alakítja át. Új probléma esetén a célfüggvény mindig ugyanaz, mivel a járulékos szállítás ára nulla. Vagyis a fiktív fogyasztó nem sérti meg a kényszerrendszer összeegyeztethetőségét.

Ha tehát bevezetünk egy fiktív (m+1)-edik kiindulási pontot, amelyhez a rakománytartalékot hozzá kell rendelni.

Ettől a fiktív szállítótól származó áruk szállításának tarifáit ismét nullára állítják. Egy sor kerül a mátrixba, ez nem befolyásolja a célfüggvényt, és a probléma kényszerrendszere együttessé válik, azaz lehetővé válik az optimális terv megtalálása.

A szállítási probléma szempontjából fontos a következő tétel.

Tétel. A szállítási probléma mátrix rangja eggyel kevesebb, mint az egyenletek száma, pl. r ( a )= m + n -1.

A tételből következik, hogy minden referenciatervnek rendelkeznie kell (m-1)(n-1) nullával egyenlő szabad változókkal és m+n-1 bázisváltozóval.

Közvetlenül az elosztási táblázatban keressük meg a szállítási feladat szállítási tervét. Tegyük fel, hogy ha az xij változó értéket vesz fel, akkor ezt az értéket írjuk a megfelelő cellába (I,j), de ha xij=0, akkor az (I,j) cellát szabadon hagyjuk. Figyelembe véve a mátrix rangjára vonatkozó tételt az eloszlási táblázatban a referenciatervnek tartalmaznia kell m+n-1 elfoglalt cellák, a többi pedig ingyenes lesz.

A referenciatervre vonatkozó meghatározott követelmények nem az egyedüliek. A referenciaterveknek egy másik, a ciklusokkal kapcsolatos követelménynek is meg kell felelniük.

Egy szállítási mátrix celláinak halmazát, amelyben két és csak két szomszédos cella található egy sorban vagy egy oszlopban, és a halmaz utolsó cellája ugyanabban a sorban vagy oszlopban van, mint az első, zártnak nevezzük. ciklus .

Grafikusan a ciklus egy zárt szaggatott vonal, amelynek csúcsai a táblázat foglalt celláiban, a hivatkozások pedig csak sorokban vagy oszlopokban találhatók. Ráadásul a ciklus minden csúcsánál pontosan két link található, amelyek közül az egyik egy sorban, a másik pedig egy oszlopban található. Ha egy ciklust alkotó szaggatott vonal önmagát metszi, akkor az önmetszéspontok nem csúcsok.

A szállítási problématervek következő fontos tulajdonságai a cikluscellák halmazához kapcsolódnak:

1) egy szállítási probléma elfogadható terve akkor és csak akkor referencia, ha a terv által elfoglalt cellákból nem lehet ciklust kialakítani;

2) ha van referenciatervünk, akkor minden szabad cellához csak egy ciklus képezhető, amely ezt a cellát és a foglalt cellák egy részét tartalmazza.

17. Az eredeti referenciaterv elkészítése

Az "északnyugati sarok" szabály.

A kezdeti szállítási terv elkészítéséhez célszerű az „északnyugati sarok” szabályt használni, amely a következő.

A bal felső, hagyományosan „északnyugati saroknak” nevezett résztől kezdve töltjük ki, haladva tovább a vonal mentén jobbra vagy lefelé az oszlopban. Tegyük az (1; 1) cellába az a1 és b1 számok közül a kisebbet, azaz . Ha, akkor az első oszlop „zárt”, azaz az első fogyasztó kereslete teljesen kielégített. Ez azt jelenti, hogy az első oszlop összes többi cellájánál a rakomány mennyisége .

Ha, akkor az első sor hasonlóan „zárt”, azaz for . Folytatjuk a szomszédos cella (2; 1) kitöltésével, amelybe belépünk.

A második cella (1; 2) vagy (2; 1) kitöltése után folytatjuk a következő harmadik cella kitöltését a második sor mentén vagy a második oszlopban. Ezt a folyamatot addig folytatjuk, amíg egy bizonyos szakaszban a források és a szükségletek kimerülnek. Az utolsó kitöltött cella az utolsó n-edik oszlopban és az utolsó m-edik sorban lesz.

A "minimális elem" szabály.

Az „északnyugati sarok” szabály szerint megépített kezdeti referenciaterv általában nagyon távol áll az optimálistól, mivel meghatározásakor nem veszik figyelembe a cij költségértékeket. Ezért a további számításokhoz sok iterációra lesz szükség az optimális terv eléréséhez. Az iterációk száma csökkenthető, ha a kezdeti terv a „minimális elem” szabály szerint épül fel. Lényege abban rejlik, hogy minden lépésnél a rakomány ketrecbe történő maximális lehetséges „mozgatása” minimális tarifa mellett történik. A táblázat kitöltését abból a cellából kezdjük, amelyik a tarifamátrix legkisebb cij elemének felel meg. Az ai vagy bj számok közül a kisebbik a legalacsonyabb tarifával rendelkező cellába kerül . Ekkor az a beszállítónak megfelelő sor, akinek a készlete teljesen elfogyott, vagy az a vevőnek az oszlopa, akinek az igénye teljesen kielégített, nem kerül figyelembevételre. Egy sor és egy oszlop egyidejű kiiktatására is szükség lehet, ha a szállító készletei teljesen elfogytak, és a vevői igény teljes mértékben kielégítésre kerül. Ezután a táblázat fennmaradó cellái közül ismét kiválasztásra kerül a legalacsonyabb tarifával rendelkező cella, és a készletek felosztása addig folytatódik, amíg az összeset ki nem osztják és a keresletet kielégítik.

18. A potenciálok módszere

A szállítási probléma optimális tervének potenciálmódszerrel történő meghatározásának általános elve hasonló az LP-probléma szimplex módszerrel történő megoldásának elvéhez, nevezetesen: először meg kell találni egy szállítási probléma referenciatervét, majd ezt követően. mindaddig javítani kell, amíg meg nem születik az optimális terv.

A potenciális módszer lényege a következő. A kezdeti referencia szállítási terv megtalálása után minden szállítóhoz (minden sorhoz) hozzárendelnek egy Ai szállítói potenciálnak nevezett számot, és minden fogyasztóhoz (minden oszlophoz) hozzárendelnek egy bizonyos számot, amelyet fogyasztói potenciálnak neveznek.

Egy tonna rakomány költsége egy ponton megegyezik egy tonna rakomány szállítási költségével + szállításának költségével: .

Egy szállítási probléma megoldásához a lehetséges módszerrel a következőket kell tennie:

1. Készítsen egy alapvető szállítási tervet a megadott szabályok valamelyikének megfelelően. A kitöltött cellák száma m+n-1 legyen.

2. Számítsa ki a potenciálokat és ennek megfelelően a szállítókat és a fogyasztókat (elfoglalt cellák esetén): . A kitöltött cellák száma m+n-1, az egyenletek száma m+n. Mert az egyenletek száma eggyel kevesebb, mint az ismeretlenek száma, akkor az egyik ismeretlen szabadnak bizonyul, és tetszőleges számértéket vehet fel. Például, . Egy adott referenciaoldat fennmaradó potenciálja egyedileg kerül meghatározásra.

3. Ellenőrizze az optimalitást, pl. szabad cellák esetén számítson ki becsléseket. Ha, akkor a szállítás célszerű és az X terv optimális - az optimalitás jele. Ha van legalább egy eltérés, akkor lépjen át egy új referenciatervre. Gazdasági értelemben az érték a teljes szállítási költség változását jellemzi, amely az i-edik szállító által a j-edik fogyasztóhoz történő egyszeri kiszállítás miatt következik be. Ha, akkor egyetlen szállítás megtakarítást eredményez a szállítási költségekben, de ha - ezek növekedését. Ebből következően, ha az ingyenes szállítási irányok között nincs olyan irány, amely megtakarítja a szállítási költségeket, akkor az így kapott terv optimális.

4. A pozitív számok közül a maximumot választja ki, és egy újraszámítási ciklust szerkeszt a szabad cellához, amelyhez tartozik. A ciklus létrehozása után a kiválasztott szabad cellához lépjen át egy új referenciatervre. Ehhez egy újraszámítási ciklussal át kell mozgatni a terheléseket az adott szabad cellához kapcsolódó cellákon belül.

a) Az adott szabad cellával ciklussal összekapcsolt cellák mindegyikéhez egy bizonyos előjel tartozik, és ez a szabad cella a „+”, az összes többi cella (a ciklus csúcsa) pedig felváltva a „–” és a „ +”. Ezeket a cellákat mínusznak és plusznak nevezzük.

b) A ciklus negatív celláiban megtaláljuk a minimális utánpótlást, amit jelölünk. A mínusz cellákban található xij számok közül a kisebbik átkerül ebbe a szabad cellába. Ugyanakkor ezt a számot hozzáadjuk a megfelelő számokhoz a cellákban egy „+” jellel, és kivonjuk a mínusz cellákban lévő számokból. A korábban szabad cella foglalt lesz, és belép a támaszsíkra; és a mínusz cella, amely az xij számok minimumát tartalmazza, szabadnak minősül, és elhagyja a támogatási tervet.

Így új referenciatervet határoztak meg. A fent leírt átmenetet egyik referenciatervről a másikra az újraszámítási ciklus eltolásának nevezzük. Az újraszámítási ciklus mentén eltolva a foglalt cellák száma változatlan marad, azaz m+n-1 marad. Sőt, ha két vagy több azonos xij szám van a negatív cellákban, akkor ezek közül csak az egyik cella szabadul fel, a többi pedig nulla készlettel marad el.

5. Az eredményül kapott referenciaterv optimalitása ellenőrzésre kerül, pl. ismételje meg az összes lépést a 2. lépéstől.

19. A dinamikus programozás fogalma.

A DP (tervezés) egy matematikai módszer többlépcsős (többlépcsős) problémák optimális megoldásainak megtalálására. E problémák egy része természetesen külön lépésekre (szakaszokra) bomlik, de vannak olyan problémák, amelyeknél a partíciót mesterségesen kell bevezetni ahhoz, hogy a DP módszerrel megoldódjanak.

A DP-módszerek jellemzően egyes vezérelt rendszerek működését optimalizálják, amelyek hatását értékelik adalékanyag, vagy multiplikatív, a célfüggvény. Adalékanyag több f(x1,x2,…,xn) változóból álló függvényt hívunk meg, amelynek értékét néhány, csak egy xj változótól függő fj függvény összegeként számítjuk ki: . Az additív célfüggvény feltételei a szabályozott folyamat egyes szakaszaiban hozott döntések hatásának felelnek meg.

R. Bellman optimalitási elve.

A dinamikus programozásban megvalósított megközelítés lényege, hogy az eredeti többdimenziós probléma megoldását egy alacsonyabb dimenziójú feladatsorral helyettesítsük. A feladatok alapvető követelményei:

1. a kutatás tárgya legyen ellenőrzött rendszer (objektum) adott érvényességgel Államok és elfogadható osztályok;

2. a feladatnak lehetővé kell tennie az értelmezést többlépcsős folyamatként, melynek minden lépése az elfogadásból áll megoldásokat O kiválasztva az egyik elfogadható ellenőrzést, ami ahhoz vezet állapotváltozás rendszerek;

3. a feladat nem függhet a lépések számától, és mindegyiknél meg kell határozni;

4. a rendszer állapotát minden lépésben ugyanazon (összetételében) paraméterkészlettel kell leírni;

5. a következő állapot, amelyben a rendszer a megoldás kiválasztása után találja magát k-m lépés, csak az adott döntéstől és a kezdet kezdeti állapotától függ k- lépés. Ez a tulajdonság a dinamikus programozás ideológiája szempontjából alapvető és ún nincs következménye .

Tekintsük a dinamikus programozási modell alkalmazásának kérdéseit általánosított formában. Legyen a feladat valamilyen absztrakt objektum vezérlése, amely különböző állapotú lehet. Az objektum aktuális állapotát a rendszer egy bizonyos paraméterkészlettel azonosítja, amelyet a továbbiakban S-vel jelölünk és ún. állapotvektor. Feltételezzük, hogy adott az összes lehetséges állapotból egy S halmaz. Az objektumhoz egy halmaz is definiálva van megengedett ellenőrzések(ellenőrző műveletek) X, amely az általánosság elvesztése nélkül numerikus halmaznak tekinthető. Az ellenőrzési műveletek az idő és a menedzsment diszkrét pillanataiban hajthatók végre megoldás az egyik vezérlő kiválasztásából áll. Terv feladatok ill menedzsment stratégia x=(x1,x2,…,xn-1) vektornak nevezzük, melynek összetevői a folyamat egyes lépéseiben kiválasztott vezérlők. Tekintettel a várható nincs utóhatás az objektum Sk és Sk+1 két egymást követő állapota között ismert funkcionális kapcsolat van, amely magában foglalja a kiválasztott vezérlőt is: . Így az objektum kezdeti állapotának beállítása és a terv kiválasztása x egyértelműen meghatározni viselkedési pálya tárgy.

A hatékonyság ellenőrzése minden lépésben k függ az aktuális Sk állapottól, a kiválasztott xk vezérlőtől, és számszerűsítése az fk(xk,Sk) függvényekkel történik, amelyek kifejezések additív célfüggvény , jellemzi a létesítménygazdálkodás általános hatékonyságát. ( jegyzet , hogy az fk(xk,Sk) függvény definíciója tartalmazza a megengedett értékek tartományát xk , és ez a terület általában a Sk) aktuális állapotától függ. Optimális vezérlés , adott S1 kezdeti állapothoz egy ilyen optimális terv kiválasztása x* , amelynél ez megvalósul maximális összeget fk értékei a megfelelő pályán.

A dinamikus programozás alapelve, hogy minden lépésben ne törekedjünk az fk(xk,Sk) függvény izolált optimalizálására, hanem az optimális x*k vezérlést válasszuk, feltéve, hogy minden további lépés optimális. Formálisan ezt az elvet úgy valósítják meg, hogy minden lépésnél megtalálják k feltételes optimális vezérlések , amely ettől a lépéstől kezdve a legnagyobb összhatékonyságot biztosítja, feltételezve, hogy a jelenlegi állapot S.

Jelölje Zk(s) az fk függvények összegének maximális értékét a lépések során k előtt P(optimális szabályozással a folyamat adott szegmensében nyert), feltéve, hogy az objektum a lépés elején k S állapotban van. Ekkor a Zk(s) függvényeknek ki kell elégíteniük az ismétlődési relációt:

Ezt az arányt ún alapvető kiújulási reláció (alapvető funkcionális egyenlet) dinamikus programozás. A dinamikus programozás alapelvét valósítja meg, más néven Bellman optimalitás elve :

Az optimális szabályozási stratégiának a következő feltételnek kell megfelelnie: bármilyen legyen is a kezdeti állapot sk a k. lépésben és az ebben a lépésben kiválasztott vezérlőelem xk, a későbbi menedzsmentnek (vezetői döntéseknek) optimálisnak kell lennie ahhoz képest cocomo Ianiya ,lépésben hozott döntés eredményeként .

A fő reláció lehetővé teszi, hogy megtaláljuk a Zk(s) függvényeket csak V kombinálva kezdeti állapot, ami esetünkben egyenlőség.

A fent megfogalmazott optimalitás elve csak olyan objektumok vezérlésére alkalmazható, amelyeknél az optimális szabályozás megválasztása nem függ a vezérelt folyamat hátterétől, vagyis attól, hogy a rendszer hogyan került jelenlegi állapotába. Ez az a körülmény, amely lehetővé teszi számunkra, hogy felbontsuk a problémát, és lehetővé tegyük gyakorlati megoldását.

Minden egyes feladathoz a funkcionális egyenletnek megvan a maga sajátos formája, de mindenképpen meg kell őriznie a (*) kifejezésben rejlő visszatérő jelleget, amely megtestesíti az optimalitás elvének alapgondolatát.

20. A játékmodellek fogalma.

A konfliktushelyzet matematikai modelljét ún játszma, meccs , a konfliktusban érintett felek - játékosok, és a konfliktus kimenetele az győzelem.

Minden formalizált játéknál szabályokat , azok. feltételrendszer, amely meghatározza: 1) a játékosok cselekvési lehetőségeit; 2) az egyes játékosok birtokában lévő információk mennyisége partnereik viselkedéséről; 3) a nyereség, amelyhez az egyes műveletek halmazai vezetnek. Jellemzően a győzelem (vagy a veszteség) számszerűsíthető; például a veszteséget nullára, a győzelmet egyre, a döntetlent pedig 1/2-re értékelheti. A játék eredményeinek számszerűsítését ún fizetés .

A játék ún gőzszoba , ha két játékosról van szó, és többszörös , ha a játékosok száma kettőnél több. Csak a páros meccseket vesszük figyelembe. Két játékost érintenek AÉs BAN BEN, akiknek az érdekei ellentétesek, játék alatt pedig cselekvések sorozatát értjük AÉs BAN BEN.

A játék ún zéró-összegű játék vagy ellentétes ég , ha az egyik játékos nyeresége egyenlő a másik veszteségével, azaz. mindkét fél nyereményének összege nulla. A játékfeladat teljesítéséhez elég az egyik értékét feltüntetni . Ha kijelöljük A- az egyik játékos nyereménye, b – a másik nyereményét, majd nulla összegű játékra b = –A, ezért elég figyelembe venni pl A.

A szabályok által előírt műveletek valamelyikének kiválasztását és végrehajtását hívják előrehalad játékos. A mozdulatok lehetnek személyes És véletlen . Személyes lépés – ez a játékos tudatos választása a lehetséges cselekvések közül (például egy lépés egy sakkjátszmában). Az egyes személyes lépések lehetséges opcióit a játékszabályok szabályozzák, és mindkét oldal korábbi lépéseinek összességétől függ.

Véletlenszerű mozgás – ez egy véletlenszerűen kiválasztott akció (például kártya kiválasztása egy megkevert pakliból). Ahhoz, hogy egy játék matematikailag definiálható legyen, a játékszabályoknak minden véletlenszerű lépésnél jelezniük kell Valószínűségi eloszlás lehetséges eredményeket.

Egyes játékok csak véletlenszerű lépésekből állhatnak (úgynevezett tiszta szerencsejáték) vagy csak személyes lépésekből (sakk, dáma). A legtöbb kártyajáték a vegyes típusú játékokhoz tartozik, azaz véletlenszerű és személyes mozdulatokat is tartalmaz. A jövőben csak a játékosok személyes megmozdulásait vesszük figyelembe.

A játékokat nem csak a lépések jellege (személyes, véletlenszerű), hanem az is, hogy az egyes játékosok milyen jellegűek és milyen információk állnak rendelkezésre a másik cselekedeteivel kapcsolatban, osztályozzák. A játékok egy speciális osztálya az úgynevezett „teljes információs játékok”. Egy játék teljes információval egy olyan játék, amelyben minden játékos minden személyes lépésével ismeri az összes korábbi lépés eredményét, mind személyes, mind véletlenszerűen. A teljes információt tartalmazó játékok például a sakk, a dáma és a jól ismert „tic-tac-toe” játék. A gyakorlati jelentőségű játékok többsége nem tartozik a teljes információs játékok osztályába, mivel az ellenség cselekedeteivel kapcsolatos bizonytalanság általában a konfliktushelyzetek lényeges eleme.

A játékelmélet egyik fő fogalma a koncepció stratégiákat .

Stratégia A játékos egy olyan szabályrendszer, amely az aktuális helyzettől függően minden egyes személyes lépésnél meghatározza az akcióját. Általában a játék során minden személyes lépésnél a játékos választ a konkrét helyzettől függően. Elvileg azonban lehetséges, hogy minden döntést a játékos hoz meg előre (bármely adott helyzetre reagálva). Ez azt jelenti, hogy a játékos egy konkrét stratégiát választott, amelyet szabálylistaként vagy programként is megadhatunk. (Ily módon számítógéppel is játszhat a játékkal.) A játék ún végső , ha minden játékosnak véges számú stratégiája van, és végtelen .– másképp.

Azért, hogy döntsd el játszma, meccs , vagy megtalálni játék megoldás , minden játékos számára olyan stratégiát kell választanunk, amely megfelel a feltételnek optimalitás , azok. az egyik játékosnak meg kell kapnia maximális nyeremény, amikor a második ragaszkodik a stratégiájához, ugyanakkor a második játékosnak rendelkeznie kell minimális veszteség , ha az első kitart a stratégiája mellett. Az ilyen stratégiákat ún optimális . Az optimális stratégiáknak is meg kell felelniük a feltételnek fenntarthatóság , azok. Bármelyik játékos számára hátrányosnak kell lennie, ha felhagy a stratégiájával ebben a játékban.

Ha a játékot jó néhányszor megismétlik, akkor előfordulhat, hogy a játékosokat nem érdekli az egyes játékok nyerése és vesztesége, de A átlagos győzelem (vereség) minden tételben.

A játékelmélet célja az optimális stratégia meghatározása minden játékos számára.

21. Fizetési mátrix. A játék alsó és felső ára

A végső játék, amelyben a játékos A Megvan T stratégiákat és a játékost V – p A stratégiákat m×n játéknak nevezzük.

Tekintsünk egy m×n játékot két játékosból AÉs BAN BEN(„mi” és „ellenség”).

Engedd a játékost A van T személyes stratégiák, amelyeket A1,A2,…,Am-ként jelölünk. Engedd a játékost BAN BEN elérhető n személyes stratégiák, jelöljük őket B1,B2,…,Bn.

Hagyja, hogy mindegyik fél válasszon egy konkrét stratégiát; nekünk Ai lesz, az ellenségnek Bj. Annak eredményeként, hogy a játékosok bármelyik Ai és Bj (Bj) stratégiapárt választják, a játék kimenetele egyedileg meghatározható, pl. játékos nyereménye aij A(pozitív vagy negatív) és a játékos elvesztése (-aij). BAN BEN.

Tegyük fel, hogy az aij értékei bármely stratégiapárra ismertek (Ai, Bj) . Mátrix P=aij , melynek elemei az Ai és Bj stratégiáknak megfelelő kifizetések, hívott fizetési mátrix vagy a játék mátrixa. Ennek a mátrixnak a sorai megfelelnek a játékos stratégiáinak A,és az oszlopok – a játékos stratégiái B. Ezeket a stratégiákat tisztanak nevezzük.

Az m×n játék mátrixának alakja:

Tekintsünk egy m×n játékot mátrixszal, és határozzuk meg a legjobbat az A1,A2,…,Am stratégiák közül. . Stratégia kiválasztása Ai játékos A számítania kell a játékosnak BAN BEN válaszol rá az egyik Bj stratégiával, amellyel a játékos nyer A minimális (lejátszó BAN BEN igyekszik "károsítani" a játékost A).

Jelöljük a játékos legkisebb nyereményével A amikor az összes lehetséges játékos stratégiához az Ai stratégiát választja BAN BEN(legkisebb szám én a fizetési mátrix sora), azaz.

Az összes szám közül () kiválasztjuk a legnagyobbat: .

Hívjuk fel a játék legalacsonyabb ára, vagy maximális nyeremény (maxmin). Ez garantált nyeremény az A játékos számára a B játékos bármely stratégiája esetén. Ennélfogva,

A maximinnak megfelelő stratégiát ún maximal stratégia . Játékos BAN BENérdekelt a játékos nyereményének csökkentésében A, a Bj stratégia kiválasztásakor figyelembe veszi a maximálisan lehetséges nyereséget A. Jelöljük

Az összes szám közül válassza ki a legkisebbet

és hívjuk a játék felső ára vagy minimax győzelem(minimax). Ego garantált B játékos elvesztése. Ebből adódóan,

A minimaxnak megfelelő stratégiát ún minimax stratégia.

Azt az elvet, amely megköveteli a játékosoktól, hogy a legóvatosabb minimax és maximin stratégiákat válasszák, az ún. minimax elv . Ez az elv abból az ésszerű feltevésből következik, hogy minden játékos az ellenfele céljával ellentétes cél elérésére törekszik.

Tétel. A játék alsó ára mindig nem haladja meg a játék felső árát .

Ha a játék felső és alsó ára megegyezik, akkor a játék felső és alsó árának összértéke ún. a játék tiszta ára, vagy a játék árán. A játék árának megfelelő minimax stratégiák optimális stratégiák , és azok összessége - optimális megoldás vagy a játék megoldása. Ebben az esetben a játékos A a garantált maximumot kapja (a játékos viselkedésétől függetlenül) BAN BEN) nyeremények vés a játékos BAN BEN eléri a garantált minimumot (a játékos viselkedésétől függetlenül A) vesztes v. Azt mondják, hogy a játék megoldása megvan fenntarthatóság , azok. Ha az egyik játékos ragaszkodik az optimális stratégiájához, akkor a másik számára nem lehet nyereséges, ha eltér az optimális stratégiájától.

Ha az egyik játékos (pl A) ragaszkodik az optimális stratégiájához, és a másik játékoshoz (BAN BEN) akkor bármilyen módon el fog térni optimális stratégiájától az eltérést elkövető játékos számára az soha nem lehet nyereséges; olyan játékos eltérés BAN BEN legjobb esetben is változatlanul hagyhatja a nyereményt. és legrosszabb esetben növelje meg.

Ellenkezőleg, ha BAN BEN betartja optimális stratégiáját, és A eltér a sajátjától, akkor ez semmiképpen sem lehet előnyös a számára A.

Egy pár tiszta stratégia, és akkor és csak akkor ad optimális megoldást a játékra, ha a megfelelő elem oszlopában a legnagyobb és sorában a legkisebb is. Ezt a helyzetet, ha létezik, ún teljesítménypont. A geometriában a felület azon pontját, amelynek az a tulajdonsága, hogy az egyik koordinátán egyidejűleg van egy minimum, a másikban a maximum, ún. erő pont, analógia útján ezt a kifejezést használják a játékelméletben.

A játék, amihez , hívott power pointtal játszik. Az ilyen tulajdonságú elem a mátrix erőpontja.

Tehát minden power pointos játékhoz létezik egy olyan megoldás, amely mindkét fél számára meghatároz egy pár optimális stratégiát, amelyek a következő tulajdonságokban különböznek egymástól.

1) Ha mindkét fél ragaszkodik az optimális stratégiájához, akkor az átlagos nyeremény megegyezik a játék nettó költségével v, ami egyben alsó és felső ára is.

2) Ha az egyik fél ragaszkodik az optimális stratégiájához, a másik pedig eltér a sajátjától, akkor az eltérõ fél csak veszíthet, és semmi esetre sem növelheti nyereményét.

A játékelméletben bebizonyosodott, hogy különösen minden teljes információval rendelkező játéknak van erőpontja, és ezért minden ilyen játéknak van megoldása, azaz mindkét félnek van egy-egy optimális stratégiája, ami átlagos nyereményt ad. megegyezik a játék költségével. Ha egy teljes információval rendelkező játék csak személyes mozdulatokból áll, akkor amikor mindkét fél alkalmazza a maga optimális stratégiáját, mindig jól meghatározott eredménnyel kell végződnie, nevezetesen a játék költségével pontosan megegyező győzelemmel.

22. A játék megoldása vegyes stratégiákban.

A gyakorlati jelentőségű véges játékok között viszonylag ritkák az erőpontos játékok; tipikusabb eset, amikor a játék alsó és felső ára eltérő. Az ilyen játékok mátrixait elemezve arra a következtetésre jutunk, hogy ha minden játékos egyetlen stratégiát választ, akkor egy ésszerűen cselekvő ellenféllel számolva ezt a választást a minimax elv alapján kell meghatározni. Maximális stratégiánkat betartva az ellenség bármilyen viselkedése esetén nyilvánvalóan a játék α alacsonyabb árával megegyező győzelmet garantálunk magunknak. Az ilyen kombinált stratégiák, amelyek több tiszta stratégia alkalmazásából állnak, véletlenszerű törvény szerint váltakozva egy bizonyos frekvenciaarányt a játékelméletben hívják vegyes stratégiák

Vegyes stratégia Sa A játékos az A1,A1,…,Ai,…,Am tiszta stratégiák alkalmazása p1,p2,…pi,…pm valószínűségekkel, és a valószínűségek összege egyenlő 1: . Az A játékos vegyes stratégiái mátrixként vannak felírva

vagy karakterláncként Sa=(p1,p2,…,pi,…,pm).

Hasonlóképpen a B játékos vegyes stratégiáit a következőképpen jelöljük:

Vagy Sb=(q1,q2,…,qi,…,qn),

ahol a stratégiák megjelenési valószínűségeinek összege egyenlő 1: .

Nyilvánvaló, hogy minden tiszta stratégia egy speciális esete egy vegyesnek, amelyben egy kivételével minden stratégiát nulla gyakorisággal (valószínűséggel), ezt pedig 1-es gyakorisággal (valószínűséggel) alkalmazzuk.

Kiderült, hogy nemcsak tiszta, hanem vegyes stratégiák alkalmazásával is lehetséges, hogy minden véges játék olyan megoldást kapjon, azaz olyan (általános esetben vegyes) stratégiák párját, hogy amikor mindkét játékos használja ezeket, a a kifizetés megegyezik a játék árával, és amikor Bármilyen egyoldalú eltérés az optimális stratégiától, csak a deviáns számára kedvezőtlen irányba változtathatja meg a kifizetést. Tehát a minimax elv alapján határozzák meg optimális megoldás (vagy megoldás) játékok: ez egy pár optimális stratégia általános esetben vegyes, amelynek a következő tulajdonsága van: ha az egyik játékos ragaszkodik az optimális stratégiájához, akkor a másiknak nem lehet kifizetődő, ha eltér a sajátjától. Az optimális megoldásnak megfelelő kifizetést ún a játék árán v . A játék ára kielégíti az egyenlőtlenséget:

Ahol α és β a játék alsó és felső ára.

Az elhangzott nyilatkozat a tartalmát képezi az ún játékelmélet alaptétele. Ezt a tételt először Neumann János bizonyította 1928-ban. A tétel ismert bizonyításai viszonylag összetettek; Ezért csak a megfogalmazását adjuk meg.

Minden véges játéknak van legalább egy optimális megoldása, esetleg vegyes stratégiák között.

A főtételből az következik, hogy minden véges játéknak ára van.

Hadd legyen – egy pár optimális stratégia. Ha egy tiszta stratégia nullától eltérő valószínűséggel szerepel egy optimális vegyes stratégiában, akkor azt ún aktív (hasznos) .

Becsületes aktív stratégiák tétele: ha az egyik játékos ragaszkodik az optimális vegyes stratégiájához, akkor a nyeremény változatlan marad és megegyezik a játék költségével v, ha a második játékos nem lépi túl aktív stratégiáinak határait.

A játékos bármelyik aktív stratégiáját tiszta formájában használhatja, és tetszőleges arányban keverheti is.

Ez a tétel nagy gyakorlati jelentőséggel bír - konkrét modelleket ad az optimális stratégiák megtalálásához nyeregpont hiányában.

Mérlegeljük 2x2 méretű játék, ami egy véges játék legegyszerűbb esete. Ha egy ilyen játéknak van nyeregpontja, akkor az optimális megoldás ennek a pontnak megfelelő tiszta stratégiapár.

Olyan játék, amelyben a játékelmélet alaptételének megfelelően nincs nyereghegy az optimális megoldás létezik, és azt egy pár vegyes stratégia határozza megÉs.

Ezek megtalálásához az aktív stratégiákra vonatkozó tételt használjuk. Ha a játékos A ragaszkodik optimális stratégiájához , akkor átlagos nyereménye megegyezik a játék árával v, függetlenül attól, hogy milyen aktív stratégiát használ a játékos BAN BEN. Egy 2x2-es játéknál bármely tiszta ellenfél stratégia aktív, ha nincs középpont. A játékos nyereményei A(játékos elvesztése BAN BEN)– egy valószínűségi változó, amelynek matematikai elvárása (átlagértéke) a játék ára. Ezért az átlagos játékos nyereménye A(optimális stratégia) egyenlő lesz v mind az 1., mind a 2. ellenséges stratégiához.

Adja meg a játékot egy kifizetési mátrix.

A játékosok átlagos nyereményei A, ha optimális vegyes stratégiát alkalmaz és a játékos BAN BEN - tiszta B1 stratégia (ez a kifizetési mátrix 1. oszlopának felel meg R), megegyezik a játék árával v: .

A játékos ugyanazt az átlagos nyereményt kapja A, ha a 2. játékos a B2 stratégiát használja, azaz. . Ezt figyelembe véve egy egyenletrendszert kapunk az optimális stratégia meghatározásához és a játékárak v:

Ezt a rendszert megoldva megkapjuk az optimális stratégiát

és a játék ára.

Az aktív stratégiákra vonatkozó tétel alkalmazása kereséskor – a játékos optimális stratégiája BAN BEN, ezt minden tiszta játékos stratégia esetében tapasztaljuk A (A1 vagy A2) átlagos játékosvesztés BAN BEN megegyezik a játék árával v, azaz

Ekkor az optimális stratégiát a képletek határozzák meg: .

Egy játék megoldásának problémája, ha a mátrixa nem tartalmaz nyeregpontot, annál nehezebb, minél nagyobbak az értékek m És n. Ezért a mátrixjátékok elméletében olyan módszereket vesznek figyelembe, amelyek segítségével egyes játékok megoldását más, egyszerűbbek megoldására redukálják, különösen a mátrix dimenziójának csökkentésével. A mátrix dimenziója kizárással csökkenthető sokszorosítása és nyilván nem jövedelmező stratégiákat.

Másolat olyan stratégiáknak nevezzük, amelyek a fizetési mátrix elemeinek azonos értékeinek felelnek meg, pl. a mátrix azonos sorokat (oszlopokat) tartalmaz.

Ha a mátrix i-edik sorának minden eleme kisebb, mint a k-adik sor megfelelő eleme, akkor a játékos i-edik stratégiája A veszteséges (kevesebb nyereség).

Ha a mátrix r-edik oszlopának minden eleme nagyobb, mint a j-edik oszlop megfelelő eleme, akkor a játékos számára BAN BEN Az r-edik stratégia veszteséges (a veszteség nagyobb).

A duplikált és nyilvánvalóan veszteséges stratégiák kiküszöbölésére irányuló eljárásnak mindig meg kell előznie a játék megoldását.

23. A játék geometriai értelmezése 2x2

Játék megoldás 2x2 világos geometriai értelmezést tesz lehetővé.

A játékot a P=(aij), i, j=1,2 fizetési mátrix adja meg.

Az abszcissza tengelyen (ábra) ábrázoljuk Mértékegység A1A2 szegmens; pont A1 ( x=0) az A1 stratégiát ábrázolja, az A2 pont ( x=1) az A2 stratégiát ábrázolja, és ennek a szegmensnek minden közbenső pontja az első játékos Sa vegyes stratégiája, és az Sa-tól a szegmens jobb vége közötti távolság az A1 stratégia p1 valószínűsége. , távolság a bal végtől – az A2 stratégia p2 valószínűsége .

Az A1 és A2 pontokon keresztül rajzoljunk két merőlegest az abszcissza tengelyére: I-I tengely és II-II tengely. Az I-I tengelyen ábrázoljuk az A1 stratégia nyereményeit; a II-II tengelyen – az A2 stratégia kifizetései.

Ha A játékos A1 stratégiát használ, akkor B játékos B1 stratégiájával a nyereménye a11, B2 stratégiával pedig a12. Az I. tengelyen lévő a11 és a12 számok a B1 és B2 pontoknak felelnek meg.

Ha A játékos A2 stratégiát használ, akkor B játékos B1 stratégiájával a nyereménye a21, B2 stratégiával pedig a22. Az a21 és a22 számok a II. tengely B1 és B2 pontjainak felelnek meg.

Összekapcsoljuk a B1 (I) és B1 (II) pontokat; B2 (I) és B2 (II). Van két egyenes vonalunk. Közvetlen B1B1– ha a lejátszó A vegyes stratégiát alkalmaz (az A1 és A2 stratégiák tetszőleges kombinációja p1 és p2 valószínűséggel), a B játékos pedig a B1 stratégiát. A játékos nyer A megfelel egy pontnak, amely ezen a vonalon fekszik. A vegyes stratégiának megfelelő átlagos kifizetést az a11p1+a21p2 képlet határozza meg, és az M1 pont képviseli. a B1B1 egyenesen.

Hasonlóképpen megszerkesztjük a B2B2 szegmenst, amely megfelel a B2 stratégia második játékos általi használatának. Ebben az esetben az átlagos nyereményt az a12p1+a22p2 képlet határozza meg, és az M2 pont képviseli. közvetlen B2B2-n.

Meg kell találnunk az optimális S*a stratégiát, vagyis azt, amelyiknél a minimális megtérülés (bármilyen viselkedés esetén BAN BEN) maximumra fordulna. Erre fogunk építeni nyeremény alsó határa B1B2 stratégiákhoz , ábrán jelölt B1NB2 szaggatott vonal. félkövér vonal. Ez az alsó korlát a játékos minimális nyereményét fejezi ki A bármely vegyes stratégiájával; pontN , amelyben ez a minimális nyereség eléri a maximumot, és meghatározza a megoldást (optimális stratégiát) és a játék árát. Ordináta pont Nára van a játéknak v. Pont koordinátái N a B1B1 és B2B2 egyenesek metszéspontjainak koordinátáit találjuk. Esetünkben a játék megoldását a stratégiák metszéspontja határozta meg. Ez azonban nem mindig lesz így.

Geometriailag meg lehet határozni az optimális stratégiát játékosként A,így a játékos is BAN BEN; mindkét esetben a minimax elvet alkalmazzák, de a második esetben nem a nyeremény alsó, hanem felső határát konstruálják meg és nem a maximumot, hanem a minimumot határozzák meg rajta.

Ha a fizetési mátrix negatív számokat tartalmaz, akkor a probléma grafikus megoldásához jobb áttérni egy új, nem negatív elemekkel rendelkező mátrixra; Ehhez elegendő a megfelelő pozitív számot hozzáadni az eredeti mátrix elemeihez. A játék megoldása nem változik, de a játék ára ennyivel emelkedik. A grafikus módszerrel megoldható a 2×n, m×2 játék.

24. Mátrix játék redukálása lineáris programozási problémává

Általános esetben az m×n játéknak nincs egyértelmű geometriai értelmezése. Megoldása nagyok számára meglehetősen munkaigényes TÉs n, ennek azonban nincsenek alapvető nehézségei, hiszen egy lineáris programozási probléma megoldására redukálható. Mutassuk meg.

Adja meg az m×n játékot a kifizetési mátrix . Játékos A A1,A2,..Ai,..Am stratégiákkal rendelkezik , játékos BAN BEN - stratégiákat B 1,B 2,..Bén,.. B n. Meg kell határozni az optimális stratégiákat és hol a megfelelő Ai,Bj tiszta stratégiák használatának valószínűsége,

Az optimális stratégia a következő követelményt elégíti ki. Ez biztosítja a játékost Aátlagos nyeremény, nem kevesebb, mint a játék ára v, bármilyen játékos stratégiához BAN BENés a játék árával megegyező nyeremény v, a játékos optimális stratégiájával BAN BEN. Az általánosság elvesztése nélkül feltételezzük v> 0; ez az összes elem elkészítésével érhető el . Ha a játékos A vegyes stratégiát alkalmaz minden tiszta Bj-játékos stratégiával szemben BAN BEN, akkor megkapja átlagos nyeremény , vagy a győzelem matematikai elvárása (azaz elemek j-Go a fizetési mátrix oszlopait tagonként megszorozzuk az A1, A2,..Ai,..Am stratégiák megfelelő valószínűségével, és az eredményeket összeadjuk).

Az optimális stratégia érdekében az összes átlagos nyeremény nem kevesebb, mint a játék ára v, ezért egy egyenlőtlenségi rendszert kapunk:

Az egyenlőtlenségek mindegyike osztható egy számmal. Vezessünk be új változókat: . Ekkor a rendszer formát ölt

Játékos gól A - maximalizálja garantált nyereményeit, pl. játék ára v.

Az egyenlőséggel elosztva azt kapjuk, hogy a változók teljesítik a következő feltételt: . A játék árának maximalizálása v egyenértékű a mennyiség minimalizálásával , Ezért a probléma a következőképpen fogalmazható meg: határozza meg a változók értékét , mahogy kielégítsék a lineáris korlátokat(*) És míg a lineáris függvény (2*) minimumra alkalmazva.

Ez egy lineáris programozási probléma. Az (1*)–(2*) feladat megoldásával megkapjuk az optimális megoldást és optimális stratégia .

Az optimális stratégia meghatározásához figyelembe kell venni, hogy a játékos BAN BEN a garantált nyereség minimalizálására törekszik, i.e. megtalálni max. A változók kielégítik az egyenlőtlenségeket

amelyek abból a tényből következnek, hogy egy játékos átlagos vesztesége BAN BEN nem haladja meg a játék árát, függetlenül attól, hogy milyen tiszta stratégiát használ a játékos A.

Ha jelöljük (4*), akkor egyenlőtlenség-rendszert kapunk:

A változók kielégítik a feltételt.

A játék a következő problémáig jutott.

Változóértékek meghatározása , amelyek kielégítik az egyenlőtlenségek rendszerét (5*)És maximalizálja a lineáris függvényt

A lineáris programozási probléma (5*), (6*) megoldása határozza meg az optimális stratégiát. Ugyanakkor a játék ára. (7*)

Miután az (1*), (2*) és (5*), (6*) feladatokhoz kiterjesztett mátrixokat állítottunk össze, megbizonyosodtunk arról, hogy az egyik mátrixot a másikból kaptuk transzponálással:

Így a lineáris programozási feladatok (1*), (2*) és (5*), (6*) kölcsönösen kettősek. Nyilvánvaló, hogy konkrét problémák optimális stratégiáinak meghatározásakor a kölcsönösen duális problémák közül egyet kell választani, amelynek megoldása kevésbé fáradságos, a másikra pedig dualitástételek segítségével kell megoldást találni.

Egy m×n méretű tetszőleges véges játék megoldásánál a következő séma betartása javasolt:

1. Zárja ki a fizetési mátrixból azokat a stratégiákat, amelyek nyilvánvalóan veszteségesek más stratégiákhoz képest. Ilyen stratégiák a játékos számára A

1. A közgazdasági operációkutatás tárgya és céljai. Műveletkutatáselméleti alapfogalmak.

Az operációkutatás tárgya a szervezetirányítási rendszerek vagy szervezetek, amelyek nagyszámú, egymással nem mindig konzisztens, egymással kölcsönhatásban álló egységből állnak, és ellentétesek is lehetnek.

Az operációkutatás célja a szervezetek irányítására hozott döntések mennyiségi alátámasztása.

Azt a megoldást nevezzük optimálisnak, amelyik az egész szervezet számára a legelőnyösebb, az egy vagy több részleg számára legelőnyösebb megoldást pedig szuboptimálisnak nevezzük.

Az operációkutatás olyan tudomány, amely a szervezeti rendszerek legoptimálisabb irányítását szolgáló módszerek kidolgozásával és gyakorlati alkalmazásával foglalkozik.

Művelet minden olyan esemény (cselekvési rendszer), amelyet egyetlen terv egyesít, és valamilyen cél elérésére irányul.

Az operációkutatás célja az optimális megoldások előzetes kvantitatív igazolása.

A paraméterek minden tőlünk függő konkrét megválasztását megoldásnak nevezzük. Az optimális megoldások azok, amelyek bizonyos jellemzők alapján előnyösebbek másoknál.

Azokat a paramétereket, amelyek kombinációja megoldást alkot, megoldáselemeknek nevezzük.

A megvalósítható megoldások halmaza olyan feltételeket kap, amelyek rögzítettek és nem sérthetők meg.

A hatékonysági mutató egy olyan mennyiségi mérőszám, amely lehetővé teszi a különböző megoldások összehasonlítását a hatékonyság szempontjából.

2. A hálózattervezés és -menedzsment fogalma. A folyamat és elemeinek hálózati modellje.

A hálózati gráfokkal való munkamódszer - hálózattervezés - gráfelméletre épül. Görögről lefordítva a gráf (grafpho - írom) egy pontrendszert jelent, amelyek egy részét vonalak - ívek (vagy élek) kötik össze. Ez a kölcsönható rendszerek topológiai (matematikai) modellje. Grafikonok segítségével nem csak hálózattervezési problémákat, hanem egyéb problémákat is megoldhat. A hálózattervezési módszert az egymással összefüggő munkák halmazának tervezésekor alkalmazzák. Lehetővé teszi a munka szervezeti és technológiai sorrendjének megjelenítését és a köztük lévő kapcsolat kialakítását. Ezenkívül lehetővé teszi a különböző bonyolultságú műveletek összehangolását és azon műveletek azonosítását, amelyektől a teljes munka (azaz a szervezeti esemény) időtartama függ, valamint az egyes műveletek időben történő befejezésére összpontosít.

A hálózattervezés és -menedzsment alapja a hálózati modell (NM), amely egy bizonyos cél elérésének folyamatát tükröző, egymással összefüggő művek és események halmazát modellezi. Megjeleníthető grafikon vagy táblázat formájában.

A hálózati modell alapfogalmai:

Esemény, munka, út.

Az események egy vagy több munka eredménye. Nincs időhosszabbításuk.

Az útvonal az egymást követő feladatok láncolata, amely összeköti a kezdő és a vég csúcsot.

Az utazás időtartamát az azt alkotó munkálatok időtartamának összege határozza meg.

3. Hálózati diagram felépítése és szervezése.

A hálózattervezési és irányítási rendszerekben (NPS) az építési és szerelési munkafolyamat technológiai és szervezeti összefüggéseit tükröző hálózati modellt használnak.

A hálózati modell a folyamatok grafikus ábrázolása, amelynek megvalósítása egy vagy több kitűzött cél eléréséhez vezet, jelezve e folyamatok között kialakult kapcsolatokat. A hálózati diagram egy hálózati modell számított időparaméterekkel.

A hálózati diagram szerkezetét, amely meghatározza a tevékenységek és események kölcsönös függőségét, topológiájának nevezzük.

A munka idő-, munkaerő- és anyagi erőforrásokat igénylő termelési folyamat, amely befejezve bizonyos eredmények eléréséhez vezet.

Az időt nem igénylő függőséget (fiktív alkotást) pontozott nyíllal ábrázoljuk. A fiktív munkákat hálózati diagramban használják az események és tevékenységek közötti kapcsolatok bemutatására.

A hálózati diagram az időt, a költségeket és a munka egyéb jellemzőit használja.

Folyamatos munkavégzés – a munka befejezéséhez szükséges idő munkanapokban vagy más időegységekben, amelyek megegyeznek a hálózati ütemezésben szereplő összes munkával. A munka időtartama lehet egy bizonyos (determinisztikus) vagy egy valószínűségi változó, amelyet az eloszlásának törvénye határoz meg.

A munka költsége az elvégzéséhez szükséges közvetlen költségek, a munka időtartamától és feltételeitől függően.

Az erőforrásokat egy adott munka elvégzéséhez szükséges fizikai egységek iránti igény jellemzi.

A munka minősége, megbízhatósága és egyéb mutatói a munka további jellemzőiként szolgálnak.

Esemény egy vagy több munka befejezésének ténye, amely szükséges és elegendő egy vagy több következő munka megkezdéséhez. Minden eseményhez kódnak nevezett szám tartozik. Minden feladatot két esemény határoz meg: egy kezdő eseménykód, amelyet i jelöl, és egy befejező eseménykód, amelyet j jelöl.

Azokat az eseményeket, amelyeknek nincs korábbi munkájuk, kezdetinek nevezzük; az események, amelyeknek nincs későbbi, végesek.

1 A hálózatépítés iránya eltérő jellegű lehet. A hálózati diagram felépíthető a kezdeti eseménytől a végső eseményig és a végső eseménytől a kezdőig, valamint bármelyik eseménytől a kezdő vagy a végső eseményig.

2 Hálózat kiépítésekor a következő problémák oldódnak meg:

Milyen munkát kell elvégezni a munka megkezdéséhez;

Milyen munkát célszerű ezzel a munkával párhuzamosan elvégezni;

3 A kezdeti hálózati ütemterv a hálózatot alkotó munka időtartamának figyelembevétele nélkül készül.

4 A grafikon formájának egyszerűnek és vizuálisan könnyen észlelhetőnek kell lennie.

5 Két esemény között csak egy feladat fordulhat elő. Épületek, építmények építése során egymást követően, párhuzamosan vagy egyidejűleg, hol szekvenciálisan, hol pedig párhuzamosan végezhetők munkák, aminek következtében az egyes munkák között különféle függőségek alakulnak ki.

Az események számozása (kódolása) a hálózatépítés befejezése után történik, a kezdeti eseménytől a végső eseményig.

4. A hálózati diagram kritikus útvonala. Időtartalékok. Az események és a munka korai és késői időpontjai a hálózati ütemezésben.

Egy hálózati diagramban több útvonal is lehet a kezdő és a befejező események között. A leghosszabb időtartamú utat kritikusnak nevezzük. A kritikus út határozza meg a tevékenység teljes időtartamát. Minden más út rövidebb időtartamú, ezért a rajtuk végzett munkának van időtartaléka.

A hálózati diagramon vastag vagy dupla vonalak (nyilak) jelzik a kritikus utat.

A hálózati diagram elkészítésekor két fogalom különösen fontos:

A munka korai megkezdése olyan időszak, amely előtt a munka az elfogadott technológiai sorrend megsértése nélkül nem kezdhető meg. A kezdeti eseménytől a munka kezdetéig tartó leghosszabb út határozza meg

A késedelmes munkavégzés a munkavégzés legkésőbbi határideje, amelynél a munkavégzés teljes időtartama nem növekszik. Az adott eseménytől az összes munka befejezéséig vezető legrövidebb út határozza meg.

A korai befejezés egy olyan határidő, amely előtt a munkát nem lehet befejezni. Ez egyenlő a korai kezdéssel és a munka időtartamával

Késői kezdés - az az időszak, amely után a munka nem kezdhető el az építkezés teljes időtartamának növelése nélkül. Ez egyenlő a kései befejezéssel mínusz a munka időtartama.

Ha egy esemény csak egy feladat vége (vagyis csak egy nyíl irányul rá), akkor ennek a jobnak a korai vége egybeesik a következő feladat korai kezdetével.

Az általános (teljes) tartalék az a maximális időtartam, ameddig egy adott munka befejezése késleltethető a munka teljes időtartamának növelése nélkül. Ezt a késői és korai kezdés (vagy késői és korai befejezés) közötti különbség határozza meg, ami ugyanaz.

Privát (ingyenes) tartalék az a maximális időtartam, ameddig egy adott feladat végrehajtása késleltethető anélkül, hogy a következő korai kezdését megváltoztatnánk. Ez a tartalék csak akkor lehetséges, ha az esemény két vagy több munkakört (függőséget) foglal magában, pl. két vagy több nyíl (tömör vagy pontozott) irányul feléje. Ekkor ezek közül csak az egyiknek lesz olyan korai befejezése, amely egybeesik a következő munka korai kezdésével, de a többinél ezek más értékek. Ez a különbség az egyes munkáknál a saját tartaléka lesz.

5. Dinamikus programozás. Bellman optimalitás és kontroll elve.

A dinamikus programozás az egyik leghatékonyabb optimalizálási technika. Különböző profilú szakemberek foglalkoznak a racionális döntések meghozatalával, a legjobb lehetőségek kiválasztásával és az optimális gazdálkodással. Az optimalizálási módszerek között a dinamikus programozás különleges helyet foglal el. Ez a módszer rendkívül vonzó alapelvének - az optimalitás elvének - egyszerűsége és egyértelműsége miatt. Az optimalitás elvének alkalmazási köre rendkívül széles, az alkalmazható problémák köre még nem körvonalazódott teljes mértékben. A dinamikus programozás kezdettől fogva az optimalizálási problémák gyakorlati megoldásának eszköze.

Az optimalitás elve, a kutatás fő módszere mellett nagy szerepet játszik a dinamikus programozási apparátusban az a gondolat, hogy egy adott optimalizálási problémát hasonló problémák családjába merítsünk. Harmadik jellemzője, ami megkülönbözteti a többi optimalizálási módszertől, a végeredmény formája. Az optimalitás és a többlépcsős, diszkrét folyamatokba való belemerülés elvének alkalmazása a minőségi kritérium optimális értékére vonatkozóan ismétlődő funkcionális egyenletekhez vezet. A kapott egyenletek lehetővé teszik az eredeti probléma optimális vezérlőelemeinek következetes kiírását. Ennek az az előnye, hogy a teljes folyamatra vonatkozó vezérlés kiszámításának problémája a folyamat egyes szakaszaira vonatkozó, számos egyszerűbb vezérlésszámítási problémára oszlik.

A módszer fő hátránya Bellman szavaival élve a „dimenzionalitás átka” – összetettsége katasztrofálisan növekszik a probléma dimenziójának növekedésével.

6. A vállalkozások közötti pénzelosztás problémája.

Elmondhatjuk, hogy a dinamikus programozási módszerrel az optimális vezérlés felépítésének eljárása két szakaszra oszlik: előzetes és végleges. Az előzetes szakaszban minden lépésnél a rendszer állapotától függően (az előző lépések eredményeként elért) meghatározzák a SOE-t, és az összes hátralévő lépésben a feltételesen optimális nyereséget, ettől kezdve, szintén állapottól függően. . Az utolsó szakaszban minden lépéshez meghatározzák a (feltétel nélküli) optimális szabályozást. Az előzetes (feltételes) optimalizálás lépésről lépésre, fordított sorrendben történik: az utolsó lépéstől az elsőig; végső (feltétel nélküli) optimalizálás - lépésenként is, de természetes sorrendben: az első lépéstől az utolsóig. A két optimalizálási szakasz közül az első összehasonlíthatatlanul fontosabb és időigényesebb. Az első szakasz befejezése után a második befejezése nem jelent nehézséget: nincs más hátra, mint „elolvasni” az első szakaszban már elkészített ajánlásokat.

7. A lineáris programozási probléma megfogalmazása.

A lineáris programozás népszerű eszköz olyan gazdasági problémák megoldására, amelyeket egy kritérium jelenléte jellemez (például a termelésből származó bevétel maximalizálása egy gyártási program optimális megválasztásával, vagy például a szállítási költségek minimalizálása stb.). A gazdasági problémákat az erőforrások (anyagi és/vagy pénzügyi) korlátozottsága jellemzi. Egyenlőtlenségi rendszer formájában íródnak, néha egyenlőségek formájában.

Az általánosított nemparaméteres módszer keretében elfogadható árintervallumok (vagy értékesítési mennyiségek) előrejelzése szempontjából a lineáris programozás alkalmazása azt jelenti:

A kritérium az érdeklődési körből következő termék MAX ára f.

A szabályozott változók az f csoport összes termékének árai.

Az általánosított nemparaméteres módszerrel végzett előrejelzési problémánk korlátai a következők:

a) egyenlőtlenségek rendszere (a fogyasztói magatartás racionalitásának korlátai) (lásd 4.2. Előrejelzés az általánosított nemparaméteres módszer keretében);

b) a szabályozott változók negativitásának követelménye (előrejelzési feladatunkban megköveteljük, hogy az f csoportba tartozó termékek ára ne essen az utolsó időpontban érvényes árértékek 80%-a alá);

c) költségvetési megszorítás egyenlőség formájában - az a követelmény, hogy az f csoportba tartozó termékek beszerzésének költségei állandóak legyenek (például 15%-os infláció figyelembevételével).

8. Grafikus módszer lineáris programozási feladatok megoldására.

A grafikus módszer a lineáris programozási feladat geometriai értelmezésén alapul, és főleg kétdimenziós térben, háromdimenziós térben pedig csak néhány feladat megoldásánál használatos, mivel meglehetősen nehéz olyan megoldási poliédert konstruálni, amely így alakul ki. félterek metszéspontjának eredménye. Általában lehetetlen egy problémát háromnál nagyobb méretű térben grafikusan ábrázolni.

Adjuk meg a lineáris programozási feladatot egy kétdimenziós térben, azaz a megszorítások két változót tartalmaznak.

Keresse meg egy függvény minimális értékét

(2.1) Z = С1х1+С2х2

a11x1 + a22x2 b1

(2.2)a21x1 + a22x2 b2

aM1x1 + aM2x2 bM

(2.3) x1 0, x2 0

Tegyük fel, hogy a (2.2) rendszer a (2.3) feltétel mellett konzisztens és megoldási sokszöge korlátos. A (2.2) és (2.3) egyenlőtlenségek mindegyike, ahogy fentebb megjegyeztük, egy félsíkot határoz meg határvonalakkal: ai1x1 + ai2x2 + ai3x3 = bi,(i = 1, 2, ..., n), x1=0 , x2=0 . A lineáris függvény (2.1) Z rögzített értékeire egy egyenes egyenlete: C1x1 + C2x2 = állandó. Szerkesszük meg a (2.2) kényszerrendszer megoldási sokszögét és a lineáris függvény (2.1) grafikonját Z = 0-nál (2.1. ábra). Ekkor a feltett lineáris programozási probléma a következő értelmezést kaphatja. Keresse meg a megoldási sokszögnek azt a pontját, ahol a C1x1 + C2x2 támaszvonal = const és a Z függvény eléri a minimumot.

A Z = C1x1 + C2x2 értékei az N = (C1, C2) vektor irányában nőnek, így a Z = 0 egyenest önmagával párhuzamosan mozgatjuk az X vektor irányába. 2.1 ebből az következik, hogy az egyenes kétszer referenciaegyenes lesz a megoldási sokszöghez képest (az A és C pontokban), és az A pontban veszi fel a minimális értéket. Az A pont koordinátáit (x1, x2) úgy találjuk meg, hogy megoldjuk AB és AE egyenesek egyenletrendszere.

Ha a megoldási sokszög egy határtalan sokszög terület, akkor két eset lehetséges.

1. eset. A C1x1 + C2x2 = const egyenes az N vektor irányába vagy vele szemben haladva folyamatosan metszi a megoldási sokszöget, és egyetlen pontban sem támasztéka annak. Ebben az esetben a lineáris függvény nincs korlátos a megoldási sokszögre sem felül, sem alul (2.2. ábra).

2. eset. A mozgó egyenes ennek ellenére a megoldások sokszögéhez képest támasztékává válik (2.2. ábra, a - 2.2, c). Ekkor a terület típusától függően a lineáris függvény felülről korlátos, alulról korlátlan (2.2. ábra, a), alulról korlátos és felülről korlátlan (2.2. ábra, b), vagy alulról és alulról egyaránt korlátos. felülről (2.2. ábra, c).

9. Simplex módszer.

A szimplex módszer a fő a lineáris programozásban. A probléma megoldása a feltételek poliéderének egyik csúcsának figyelembevételével kezdődik. Ha a vizsgált csúcs nem felel meg a maximumnak (minimumnak), akkor a szomszédba költöznek, a feladat megoldásánál maximumra növelve, a minimumra csökkentve a célfüggvény értékét. Így az egyik csúcsból a másikba való mozgás javítja a célfüggvény értékét. Mivel a poliéder csúcsainak száma korlátozott, így véges számú lépésben garantáltan megtaláljuk az optimális értéket, vagy megállapíthatjuk, hogy a probléma megoldhatatlan.

Ez a módszer univerzális, minden lineáris programozási problémára alkalmazható kanonikus formában. A kényszerrendszer itt lineáris egyenletrendszer, amelyben az ismeretlenek száma nagyobb, mint az egyenletek száma. Ha a rendszer rangja r, akkor választhatunk r ismeretlent, amit a fennmaradó ismeretlenekkel fejezünk ki. A határozottság kedvéért feltételezzük, hogy az első egymást követő ismeretlenek X1, X2, ..., Xr vannak kiválasztva. Ekkor egyenletrendszerünk így írható fel

A szimplex módszer a szimplex módszer alaptételének nevezett tételen alapul. A kanonikus formájú lineáris programozási probléma optimális tervei között szükségszerűen van referenciamegoldás a kényszerrendszerére. Ha a feladat optimális terve egyedi, akkor az egybeesik valamilyen referenciamegoldással. A kényszerrendszernek véges számú különböző támogató megoldása létezik. Ezért a probléma kanonikus formában történő megoldását úgy lehetne keresni, hogy átkutatjuk a referenciamegoldásokat, és kiválasztjuk közülük azt, amelyiknél a legnagyobb az F érték. De egyrészt minden referenciamegoldás ismeretlen, és meg kell találni, másrészt a valós problémákban sok ilyen megoldás létezik, és a közvetlen keresés aligha lehetséges. A szimplex módszer egy bizonyos eljárás a támogató megoldások irányított felsorolására. A szimplex módszer egy bizonyos algoritmusával előre talált referenciamegoldás alapján egy új referenciamegoldást számítunk ki, amelyen az F célfüggvény értéke nem kisebb, mint a régié. Lépések sorozata után eljutunk egy referenciamegoldáshoz, ami az optimális terv.

10. A közlekedési probléma megfogalmazása. A referenciatervek meghatározásának módszerei.

Egyazon terméknek m kiindulási pontja („szállítók”) és n fogyasztási pontja („fogyasztója”) van. Minden egyes tételnél a következők vannak meghatározva:

ai - az i-edik szállító termelési volumene, i = 1, …, m;

вj - a j-edik fogyasztó kereslete, j= 1,…,n;

сij egy egységnyi termék elszállításának költsége Ai pontból, az i-edik szállítóból Bj pontba, a j-edik fogyasztóba.

Az érthetőség kedvéért célszerű az adatokat táblázat formájában bemutatni, amelyet szállítási költségek táblázatának nevezünk.

Olyan szállítási tervet kell találni, melyben minden fogyasztó igénye maradéktalanul kielégíthető, a beszállítóktól elegendő készlet állna rendelkezésre és a teljes szállítási költség minimális lenne.

A szállítási terv a szállítás mennyiségére vonatkozik, i.e. az az árumennyiség, amelyet az i-edik szállítótól a j-edik fogyasztóhoz kell szállítani. A probléma matematikai modelljének felépítéséhez m·n xij, i= 1,..., n, j= 1,..., m változót kell megadni, mindegyik xij változó a pontból történő szállítás mennyiségét jelöli. Ai pont Bj. Az X = (xij) változók halmaza lesz az a terv, amelyet a probléma megfogalmazása alapján meg kell találni.

Ez a feltétele a zárt és nyitott szállítási problémák (CTZ) megoldásának.

Nyilvánvaló, hogy az 1. feladat megoldásához szükséges, hogy a teljes kereslet ne haladja meg a beszállítói termelés mennyiségét:

Ha ez az egyenlőtlenség szigorúan teljesül, akkor a problémát „nyitottnak” vagy „kiegyensúlyozatlannak” nevezzük, de ha , akkor a problémát „zárt” szállítási problémának nevezzük, és a következő formában lesz: (2):

Egyensúlyi állapot.

Ez a zárt szállítási problémák (CTP) megoldásának feltétele.

11. Algoritmus a szállítási probléma megoldására.

Az algoritmus alkalmazásához számos előfeltételnek kell megfelelni:

1. Ismerni kell egy termékegységnek az egyes előállítási helyekről az egyes rendeltetési helyekre történő szállításának költségét.

2. Ismerni kell az egyes termelési pontok termékkészletét.

3. Minden fogyasztási helyen ismerni kell a termékigényeket.

4. A teljes kínálatnak egyenlőnek kell lennie a teljes kereslettel.

A szállítási probléma megoldására szolgáló algoritmus négy szakaszból áll:

I. szakasz: Mutassa be az adatokat egy szabványos táblázat formájában, és keresse meg a lehetséges erőforrás-allokációt. Elfogadható az erőforrások olyan elosztása, amely lehetővé teszi, hogy kielégítse az összes keresletet a rendeltetési helyeken, és eltávolítsa a teljes termékkészletet a termelési pontokról.

2. szakasz. Az eredményül kapott erőforrás-allokáció optimálisságának ellenőrzése

3. szakasz: Ha az erőforrások ebből eredő allokációja nem optimális, akkor az erőforrások újraelosztásra kerülnek, csökkentve a szállítási költségeket.

4. szakasz. Az eredményül kapott erőforrás-allokáció optimálisságának újraellenőrzése.

Ezt az iteratív folyamatot addig ismételjük, amíg az optimális megoldást meg nem kapjuk.

12. Készletgazdálkodási modellek.

Annak ellenére, hogy bármely készletgazdálkodási modell két fő kérdés (mikor és mennyi) megválaszolására készült, jelentős számú modell létezik, amelyek felépítéséhez sokféle matematikai eszközt használnak.

Ezt a helyzetet a kezdeti feltételek különbsége magyarázza. A készletgazdálkodási modellek osztályozásának fő alapja a raktározott termékek iránti kereslet jellege (emlékezzünk arra, hogy az általánosabb fokozatosság szempontjából ma már csak az önálló keresletű esetekkel foglalkozunk).

Tehát a kereslet jellegétől függően a készletgazdálkodási modellek lehetnek

meghatározó;

valószínűségi.

A determinisztikus kereslet viszont lehet statikus, amikor a fogyasztás intenzitása nem változik az időben, vagy dinamikus, amikor a megbízható kereslet idővel változhat.

A valószínűségi igény lehet stacionárius, amikor a kereslet valószínűségi sűrűségfüggvénye időben nem változik, és nem stacionárius, ahol a valószínűségi sűrűségfüggvény idő függvényében változik. A fenti besorolást az ábra szemlélteti.

A legegyszerűbb eset a termékek iránti determinisztikus statikus kereslet esete. Ez a fajta fogyasztás azonban meglehetősen ritka a gyakorlatban. A legösszetettebb modellek a nem stacionárius típusú modellek.

A készletgazdálkodási modellek felépítésénél a termékek iránti kereslet jellegén túl sok egyéb tényezőt is figyelembe kell venni, pl.

a megrendelés teljesítésének határideje. A beszerzési időszak időtartama lehet állandó vagy véletlenszerű változó;

készletfeltöltési folyamat. Lehet azonnali vagy időben elosztva;

a forgótőkére, raktárterületre stb. vonatkozó korlátozások megléte.

13. Sorozati rendszerek (QS) és hatékonyságuk mutatói.

A sorban állási rendszerek (QS) olyan speciális típusú rendszerek, amelyek hasonló feladatok ismételt végrehajtását valósítják meg. Az ilyen rendszerek a gazdaság, a pénzügy, a termelés és a mindennapi élet számos területén fontos szerepet játszanak. Példák a minőségbiztosításra a pénzügyi és gazdasági területen; a szférában említhetünk különféle típusú bankokat (kereskedelmi, befektetési, jelzálog-, innovatív, megtakarítási bankokat), biztosítókat, állami részvénytársaságokat, társaságokat, társaságokat, egyesületeket, szövetkezeteket, adófelügyelőségeket, könyvvizsgálói szolgáltatásokat, különféle kommunikációs rendszereket (pl. telefonközpontok), be- és kirakodó komplexumok (kikötők, teherállomások), benzinkutak, különféle vállalkozások és szolgáltató szervezetek (üzletek, információs pultok, fodrászok, jegyirodák, pénzváltók, javítóműhelyek, kórházak). Egyfajta QS-nek tekinthetők az olyan rendszerek is, mint a számítógépes hálózatok, az információgyűjtő, -tároló és -feldolgozási rendszerek, a szállítórendszerek, az automatizált termelési területek, a gyártósorok, a különféle katonai rendszerek, különösen a légi- vagy rakétavédelmi rendszerek.

Minden QS a struktúrájában tartalmaz bizonyos számú kiszolgáló eszközt, amelyeket szolgáltatási csatornáknak (eszközök, vonalak) nevezünk. A csatornák szerepét különböző eszközök, bizonyos műveleteket végző személyek (pénztárosok, operátorok, fodrászok, eladók), kommunikációs vonalak, autók, daruk, szerelők, vasúti sínek, benzinkutak stb.

A sorban állási rendszerek lehetnek egycsatornásak vagy többcsatornásak.

Mindegyik QS a rendszer bemenetére érkező alkalmazások (követelmények) bizonyos folyamának kiszolgálására (teljesítésére) van kialakítva, többnyire nem rendszeresen, hanem véletlenszerűen. Az alkalmazások kiszolgálása ebben az esetben szintén nem állandó, előre ismert ideig tart, hanem véletlenszerű ideig, ami sok véletlenszerű, esetenként számunkra ismeretlen okból függ. A kérés kiszolgálása után a csatorna felszabadul, és készen áll a következő kérés fogadására. A kérések áramlásának és kiszolgálási idejének véletlenszerű jellege a QS egyenetlen terheléséhez vezet: máskor a nem kiszolgált alkalmazások halmozódhatnak fel a QS bemenetén, ami a QS túlterheléséhez vezet, és néha akkor, amikor szabad csatornák vannak a QS bemenetén, nem lesznek alkalmazások, ami a QS alulterheléséhez vezet, azaz pl. csatornáinak tétlenségére. Azok az alkalmazások, amelyek a QS bejáratánál gyűlnek össze, vagy „csatlakoznak” a sorhoz, vagy a további sorban állás lehetetlensége miatt kiszolgálatlanul hagyják a QS-t.

A „CMO - fogyasztó” pár működésének hatékonyságának mutatói, ahol a fogyasztó alatt az alkalmazások teljes halmazát vagy azok egyes forrásait értjük (például a KGSZ által időegységre vetített átlagos bevétel stb. ). Ez a mutatócsoport hasznosnak bizonyul azokban az esetekben, amikor az alkalmazások kiszolgálásából származó bevételek és a szolgáltatási költségek egy része azonos mértékegységben mérhető. Ezek a mutatók általában nagyon specifikusak, és a QS sajátosságai, a kiszolgált kérések és a szolgáltatási fegyelem határozzák meg őket.

14. Dinamikai egyenletek valószínűségi állapotokhoz (Kolmogorov-egyenletek). Állapotok valószínűségének korlátozása.

Formálisan megkülönböztetve a Kolmogorov–Chapman egyenletet s-hez képest s = 0-nál, megkapjuk a közvetlen Kolmogorov-egyenletet:

Formálisan megkülönböztetve a Kolmogorov-Chapman egyenletet t-hez képest t = 0 esetén, megkapjuk az inverz Kolmogorov egyenletet

Hangsúlyozni kell, hogy a végtelen dimenziós terek esetében az operátor már nem feltétlenül folytonos, és nem feltétlenül definiálható mindenhol, például differenciális operátorként az eloszlások terén.

Ha az S rendszer állapotainak száma véges, és lehetségesnek tűnik az egyes állapotokból (bizonyos számú lépésben) egymáshoz való átlépés, akkor az állapotok korlátozó valószínűségei léteznek, és szintén nem függnek a kezdeti állapottól a rendszerről.

ábrán. állapotok és átmenetek grafikonját mutatjuk be, amelyek kielégítik a felállított feltételt: bármely állapotból a rendszer előbb-utóbb bármely más állapotba át tud lépni. A feltétel nem teljesül, ha a 4-3 nyíl iránya az ábra grafikonján megváltozik, hanem az ellenkezőjére.

Tegyük fel, hogy a megadott feltétel teljesül, és ezért fennállnak a korlátozó valószínűségek:

A korlátozó valószínűségeket ugyanazokkal a betűkkel jelöljük, mint az állapotok valószínűségét, miközben számokat jelentenek, nem változókat (időfüggvényeket).

Nyilvánvaló, hogy az állapotok korlátozó valószínűségeinek egységet kell adniuk: Következésképpen a rendszerben egy bizonyos korlátozó stacionárius rezsim jön létre: még ha a rendszer véletlenszerűen változtatja is saját állapotait, ezeknek az állapotoknak a valószínűsége nem időtől függenek, és mindegyik állandó valószínűséggel fordul elő, ami az átlagos relatív idő, amíg a rendszer ebben az állapotban marad.

15. A halál és a szaporodás folyamata.

Nevezzük Markov-féle halálozási és szaporodási folyamatnak folytonos idővel azt a folyamatot, amely csak nem negatív egész értékeket tud felvenni; változás ebben a folyamatban a t időpontban bármikor bekövetkezhet, míg bármely időpontban vagy eggyel nőhet, vagy változatlan maradhat.

A λi(t) reprodukciós áramlásokat Poisson-folyamoknak nevezzük, ami az X(t) függvény növekedéséhez vezet. Ennek megfelelően μi(t) az X(t) függvény csökkenéséhez vezető haláláramlás.

Állítsuk össze a Kolmogorov-egyenletet a gráfból:

Ha az áramlás véges állapotú:

A halál és szaporodás folyamatának Kolmogorov egyenletrendszere korlátozott számú állapottal a következő:

A tiszta szaporodás folyamata a halál és szaporodás folyamata, amelyben az összes haláláramlás intenzitása nullával egyenlő.

A tiszta halál folyamata a halál és a szaporodás folyamata, amelyben az összes szaporodási folyamat intenzitása nullával egyenlő.

16. Sorbaállási rendszerek meghibásodásokkal.

A sorelmélet keretében vizsgált problémák közül a legegyszerűbb a meghibásodásokkal vagy veszteségekkel járó egycsatornás QS modellje.

Meg kell jegyezni, hogy ebben az esetben a csatornák száma 1 (). Ez a csatorna Poisson kéréseket kap, amelyek intenzitása egyenlő. Az idő befolyásolja az intenzitást:

Ha egy alkalmazás olyan csatornába érkezik, amely jelenleg nem ingyenes, akkor a rendszer elutasítja, és már nem szerepel a rendszerben. Az alkalmazások kiszolgálása véletlenszerű idő alatt történik, amelynek elosztása az exponenciális törvénynek megfelelően a következő paraméterrel valósul meg:

17. Sorozati rendszerek várakozással.

A csatorna foglalt állapotában kapott kérés sorban áll, és szolgáltatásra vár.

Korlátozott sorhosszú rendszer. Először tegyük fel, hogy a sorban lévő helyek számát m korlátozza, azaz ha egy alkalmazás akkor érkezik, amikor már m alkalmazás van a sorban, akkor a rendszert kiszolgálatlanul hagyja. A jövőben m-t a végtelenbe irányítva megkapjuk az egycsatornás QS jellemzőit a sorhossz korlátozása nélkül.

A QS állapotait számozni fogjuk a rendszerben lévő alkalmazások száma szerint (mind szervizelve, mind szolgáltatásra várva):

— a csatorna ingyenes;

— a csatorna foglalt, nincs sor;

— a csatorna foglalt, egy kérés van a sorban;

— a csatorna foglalt, k - 1 kérés van sorban;

— a csatorna foglalt, rengeteg alkalmazás van sorban.

18. Döntéshozatali módszerek konfliktushelyzetekben. Mátrix játékok. Tiszta és vegyes stratégiai játékok.

A mátrixjáték két játékos véges nulla összegű játéka, amelyben az 1. játékos nyereményét mátrix formájában adjuk meg (a mátrix sora a 2. játékos alkalmazott stratégiájának számának felel meg, oszlopa a 2. játékos alkalmazott stratégiájának számához; a mátrix sorának és oszlopának metszéspontjában az 1. játékos kifizetése található, az alkalmazott stratégiáknak megfelelően).

A mátrixos játékoknál bebizonyosodott, hogy bármelyiknek van megoldása, és ez könnyen megtalálható, ha a játékot lineáris programozási problémává redukálják.

Egy kétjátékos nulla összegű mátrixjáték a következő absztrakt kétjátékos játékként fogható fel.

Az első játékosnak m stratégiája van i = 1,2,...,m, a második játékosnak n stratégiája van j = 1,2,...,n. Minden stratégiapárhoz (i,j) tartozik egy aij szám, amely az 1. játékos nyereségét fejezi ki a 2. játékos rovására, ha az első játékos elfogadja az i-edik stratégiáját, a 2. játékos pedig a j-edik stratégiáját.

Minden játékos egy lépést tesz: az 1. játékos kiválasztja az i-edik stratégiáját (i=), a 2. - a j-edik stratégiáját (j=), majd az 1. játékos megkapja a kifizetési aij-t a 2. játékos rovására (ha aij

Az i= játékos minden stratégiája; j = gyakran nevezik tiszta stratégiának.

Meghatározás. Egy játékos vegyes stratégiája a tiszta stratégiák használatának valószínűségeinek teljes halmaza.

Így ha az 1. játékosnak m tiszta stratégiája van 1,2,...,m, akkor az x vegyes stratégiája x = (x1,..., xm) számok halmaza, amely kielégíti az összefüggéseket.

xi³ 0 (i= 1,m), =1.

Hasonlóképpen a 2. játékos esetében, akinek n tiszta stratégiája van, az y vegyes stratégia a számok halmaza

y = (y1, ..., yn), yj ³ 0, (j = 1, n), = 1.

Mivel minden alkalommal, amikor egy játékos egy tiszta stratégiát használ, kizárja egy másik használatát, a tiszta stratégiák összeegyeztethetetlen események. Ráadásul ezek az egyetlen lehetséges események.

A tiszta stratégia a vegyes stratégia speciális esete. Valójában, ha egy vegyes stratégiában bármelyik i-edik tiszta stratégiát 1-es valószínűséggel alkalmazzuk, akkor az összes többi tiszta stratégiát nem alkalmazzuk. Ez az i-edik tiszta stratégia pedig a vegyes stratégia speciális esete. A titoktartás érdekében minden játékos a saját stratégiáját alkalmazza, függetlenül a másik játékos döntéseitől.

19. Geometriai módszer mátrixjáték megoldására.

A 2xn vagy nx2 méretű játékok megoldása egyértelmű geometriai értelmezést tesz lehetővé. Az ilyen játékok grafikusan is megoldhatók.

Az XY síkon az abszcissza tengely mentén egyetlen A1A2 szakaszt ábrázolunk (5.1. ábra). Rendeljünk a szakasz minden pontjához valamilyen vegyes U = (u1, u2) stratégiát. Ezen túlmenően az U közbülső ponttól a szegmens jobb vége közötti távolság az A1 stratégia választásának u1 valószínűsége, a bal végtől való távolság pedig az A2 stratégia választásának u2 valószínűsége. Az A1 pont a tiszta A1 stratégiának, az A2 pont a tiszta A2 stratégiának felel meg.

Az A1 és A2 pontokon visszaállítjuk a merőlegeseket, és rájuk helyezzük a játékosok nyereményét. Az első merőlegesen (amely egybeesik az OY tengellyel) az A játékos kifizetését mutatjuk az A1 stratégia alkalmazásakor, a másodikon - az A2 stratégia használatakor. Ha A játékos A1 stratégiát használ, akkor B játékos B1 stratégiájával a nyereménye 2, B2 stratégiája esetén pedig 5. Az OY tengelyen lévő 2 és 5 számok a B1 és B2 pontoknak felelnek meg. Hasonlóképpen a második merőlegesen találjuk a B"1 és B"2 pontokat (6 és 4 erősítés).

A B1 és B"1, B2 és B"2 pontok összekapcsolásával két egyenest kapunk, amelyektől az OX tengelytől mért távolság határozza meg a megfelelő stratégiák bármely kombinációja esetén az átlagos kifizetést.

Például a B1B"1 szakasz bármely pontjától az OX tengelyig mért távolság határozza meg az A játékos átlagos kifizetését az A1 és A2 stratégiák (u1 és u2 valószínűséggel) és a B játékos B1 stratégiájának bármely kombinációja esetén.

A B1MB"2 szaggatott vonalhoz tartozó pontok ordinátái határozzák meg az A játékos minimális nyereményét, ha bármilyen vegyes stratégiát alkalmaz. Ez a minimális érték az M pontban a legnagyobb, ezért ez a pont megfelel az optimális U* = ( ,), ordinátája pedig egyenlő a játék költségével v.

Az M pont koordinátáit a B1B"1 és B2B"2 egyenesek metszéspontjának koordinátáiként találjuk meg.

Ehhez ismernie kell az egyenesek egyenleteit. Ilyen egyenleteket a két ponton átmenő egyenes egyenletének képletével hozhat létre:

Hozzunk létre egyenes egyenleteket a problémánkra.

B1B"1 sor: = vagy y = 4x + 2.

Közvetlen B2B"2: = vagy y = -x + 5.

A rendszert kapjuk: y = 4x + 2,

Oldjuk meg: 4x + 2 = -x + 5,

x = 3/5, y = -3/5 + 5 = 22/5.

Így U = (2/5, 3/5), v = 22/5.

20. Bi-mátrix játékok.

A bimátrixos játék két játékos véges játéka nullától eltérő összeggel, amelyben minden játékos nyereményét mátrixok határozzák meg külön a megfelelő játékos számára (minden mátrixban egy sor az 1. játékos stratégiájának felel meg, egy oszlop megfelel a 2. játékos stratégiájának, az első mátrixban a sor és az oszlop metszéspontjában a játékos 1. nyereménye, a második mátrixban a 2. játékos nyereménye.)

A bimátrixos játékokhoz is kidolgozták az optimális játékos viselkedés elméletét, de az ilyen játékok megoldása nehezebb, mint a hagyományos mátrixos játékoknál.

21. Statisztikai játékok. A teljes és részleges bizonytalanság körülményei között történő döntéshozatal alapelvei és kritériumai.

Az operációkutatásban a bizonytalanságok három típusát szokás megkülönböztetni:

a célok bizonytalansága;

a környezetről és az ebben a jelenségben ható tényezőkről szerzett ismereteink bizonytalansága (természetbizonytalansága);

egy aktív vagy passzív partner vagy ellenfél cselekedeteinek bizonytalansága.

A fenti osztályozásban a bizonytalanság típusát a matematikai modell egyik vagy másik eleme szempontjából vizsgáljuk. Például a célok bizonytalansága a feladat kitűzésekor tükröződik akár az egyes kritériumok, akár a jótékony hatás teljes vektorának megválasztásában.

Másrészt a másik két típusú bizonytalanság elsősorban a kényszeregyenletek célfüggvényének megfogalmazását és a döntési módszert érinti. Természetesen a fenti kijelentés meglehetősen feltételes, akárcsak minden osztályozás. Csak azzal a céllal mutatjuk be, hogy rávilágítsunk a bizonytalanságok néhány további jellemzőjére, amelyeket a döntéshozatal során szem előtt kell tartani.

A lényeg az, hogy a bizonytalanságok fentebb tárgyalt osztályozása mellett figyelembe kell venni azok típusát (vagy „nemzetségét”) a véletlenszerűséghez való viszonyuk szempontjából.

Ezen az alapon megkülönböztethető a sztochasztikus (valószínűségi) bizonytalanság, amikor az ismeretlen tényezők statisztikailag stabilak, és ezért a valószínűségszámítás közönséges tárgyait jelentik - valószínűségi változókat (vagy véletlenszerű függvényeket, eseményeket stb.). Ebben az esetben minden szükséges statisztikai jellemzőt (eloszlási törvényeket és azok paramétereit) ismerni kell, illetve a probléma felállításakor meg kell határozni.

Ilyen feladatokra példa lehet különösen bármilyen típusú berendezés karbantartási és javítási rendszere, ritkításszervezési rendszer stb.

Egy másik szélsőséges eset lehet a nem sztochasztikus típusú bizonytalanság (E. S. Ventzel szavaival élve: „rossz bizonytalanság”), amelyben nem léteznek sztochasztikus stabilitásra vonatkozó feltételezések. Végül a bizonytalanság köztes típusáról beszélhetünk, amikor a valószínűségi változók eloszlási törvényeire vonatkozó hipotézisek alapján születik döntés. Ugyanakkor a döntéshozónak szem előtt kell tartania annak veszélyét, hogy eredményei és a valós viszonyok között eltérés mutatkozik. Az eltérés kockázatát kockázati együtthatók segítségével formalizálják.

A kockázati feltételek melletti döntéshozatal a következő kritériumok egyikén alapulhat:

várható érték kritériuma;

várható érték és szórás kombinációi;

ismert határérték;

a legvalószínűbb esemény a jövőben.

Művelet Minden olyan eseményt (cselekvési rendszert), amelyet egyetlen terv egyesít, és egy meghatározott cél elérésére irányul, ún. Mindig van egy műtét ellenőrzött esemény, azaz. El lehet dönteni, hogyan válasszunk ki bizonyos paramétereket, amelyek a szervezetét jellemzik. Ezeket a paramétereket ún vezérlő változók.

Az ilyen változók bármely konkrét megválasztását nevezzük döntés. A döntések lehetnek sikeresek és sikertelenek, ésszerűek és ésszerűtlenek. Optimális Nevezzen meg olyan megoldásokat, amelyek bizonyos kritériumok szerint előnyösebbek másokhoz képest.

Az operációkutatás célja az optimális megoldások előzetes kvantitatív indoklása, amelyekből több is lehet. A döntés végső megválasztása túlmutat az operációkutatás keretein, és az ún. döntéselmélet segítségével történik.

Bármely műveleti kutatási feladatnak vannak kezdeti „fegyelmező” feltételei, pl. olyan kezdeti adatok, amelyek a kezdetektől rögzítve vannak, és nem sérthetők meg. Ezek együttesen alkotják a lehetséges megoldások úgynevezett halmazát.

Ahhoz, hogy a különböző megoldásokat a hatékonyság szempontjából összehasonlíthassuk, rendelkeznie kell egy kvantitatív kritériummal, az úgynevezett teljesítménymutató(vagy célfüggvény). Ezt a mutatót úgy választják ki, hogy tükrözze a művelet célorientáltságát.

A műveletet gyakran véletlenszerű tényezők hatása kíséri. Ekkor a hatékonyság mutatójaként nem magát az optimalizálni kívánt értéket veszik, hanem annak átlagértékét (vagy matematikai elvárását).

Néha egy véletlenszerű tényezőkkel kísért művelet ilyen célt követ A, ami vagy teljesen elérhető, vagy egyáltalán nem (mint például az „igen-nem”). Ezután a cél elérésének valószínűségét választják a hatékonyság mutatójaként p(A). (Ha p(A) = 0 vagy 1, akkor elérkezünk a kibernetikában ismert „fekete doboz” problémához.)

A rossz teljesítménymutató kiválasztása nagyon veszélyes. A sikertelenül választott kritérium szerint szervezett műveletek indokolatlan költségekhez és veszteségekhez vezethetnek. (Például a „tengely” a fő kritérium egy vállalkozás gazdasági tevékenységének értékeléséhez.)

1.3. Az operációkutatási probléma általános megfogalmazása

Az operációkutatási problémák két kategóriába sorolhatók: a) előre és b) hátra.

Közvetlen feladatok válaszoljon a kérdésre: mivel lesz egyenlő a hatékonysági mutató? Z, ha adott feltételek mellett y  Y megszületik valami döntés x  x. Egy ilyen probléma megoldására egy matematikai modellt szerkesztenek, amely lehetővé teszi a hatékonysági mutató kifejezését adott feltételeken és egy megoldáson keresztül, nevezetesen:

Ahol
meghatározott tényezők (kiindulási adatok),

ellenőrzési változók (döntés),

Z– hatékonysági mutató (célfunkció),

F– a változók közötti funkcionális függés.

Ez a függőség a különböző modellekben eltérően fejeződik ki. közötti függőség És rendszerint korlátozásokkal fejezik ki

Ha a függőség típusa F ismert, akkor a mutató Z közvetlen helyettesítéssel találjuk meg És ebbe a funkcióba.

Inverz problémák válaszoljon a kérdésre: hogyan ilyen körülmények között megoldást választani
hogy a teljesítménymutató Z maximumra (minimálisra) fordult. Ezt a problémát megoldásoptimalizálási feladatnak nevezzük.

Legyen megoldva a direkt probléma, pl. a működési modell és a függőség típusa meg van adva F híres. Ekkor az inverz probléma (azaz optimalizálási probléma) a következőképpen fogalmazható meg.

Meg kell találni ilyen döntés
amelynél a hatékonysági mutató Z = dönt:

Ez a képlet így hangzik: Z van egy optimális érték
átvette a lehetséges megoldások sorában szereplő összes megoldást x.

A hatékonysági mutató szélsőértékének megtalálásának módszere Zés a hozzá tartozó optimális megoldás mindig a funkció jellemzői alapján kell kiválasztani Fés a megoldásra vonatkozó korlátozások típusa. (Például egy klasszikus lineáris programozási probléma.)

Operációkutatási probléma

Bevezetés…………………………………………………………………………………3

1. Az operációkutatás alapfogalmai és definíciói……………..5

2. Az operációkutatási probléma általános megfogalmazása…………..…………6

Következtetés……………………………………………………………………………………………………………………..

Irodalom…………………………………………………………………………………….14

Bevezetés

Operatív kutatás - olyan tudományág, amely a különféle szervezeti rendszerek leghatékonyabb irányítását szolgáló módszerek kidolgozásával és gyakorlati alkalmazásával foglalkozik.

Bármely rendszer irányítása bizonyos törvényeknek megfelelő folyamatként valósul meg. Tudásuk segít meghatározni a folyamat megvalósításához szükséges és elégséges feltételeket. Ehhez a folyamatot és a külső körülményeket jellemző összes paramétert számszerűsíteni és mérni kell. Ezért az operációkutatás célja az a meghozott döntések mennyiségi indoklása az irányítási szervezetről.

Egy adott irányítási probléma megoldása során az operációkutatási módszerek alkalmazása magában foglalja:

Gazdasági és matematikai modellek felépítése döntéshozatali problémákhoz összetett helyzetekben vagy bizonytalanság körülményei között;

A döntéshozatalt utólag meghatározó összefüggések tanulmányozása és teljesítménykritériumok felállítása, amelyek lehetővé teszik egy adott cselekvési mód előnyeinek felmérését.

A sajátosságát tükröző műveletkutatási feladatok példái a következő feladatok.

Feladat 1. A gyártott termékek magas minőségének biztosítása érdekében az üzemben mintavétel-ellenőrző rendszert szerveznek. Szükséges a szervezeti formák megválasztása - például az ellenőrző tételek méreteinek kijelölése, az ellenőrzési műveletek sorrendjének megjelölése, az elutasítás szabályainak meghatározása - annak érdekében, hogy minimális költségek mellett biztosítsák a kívánt minőséget.

2. feladat Egy bizonyos köteg szezonális áru értékesítéséhez ideiglenes kiskereskedelmi üzletek hálózatát hozzuk létre. Szükséges a hálózati paraméterek - a pontok száma, elhelyezkedése, létszáma - megválasztása az értékesítés maximális gazdasági hatékonysága érdekében.

3. feladat Adott időpontig a lakosság egy csoportjának tömeges orvosi vizsgálata szükséges bizonyos betegségek azonosítása érdekében. Anyagokat, felszereléseket és személyzetet biztosítottak a vizsgálathoz. Szükséges egy ilyen vizsgálati terv kidolgozása - meg kell határozni az orvosi állások számát, elhelyezkedését, típusát és a vizsgálatok számát, a betegek lehető legnagyobb százalékának azonosítása érdekében.

Meg kell jegyezni az erőforrás-felhasználással, a keverékekkel, a kapacitások felhasználásával, a forgácsolási anyagokkal, szállítási problémával stb. kapcsolatos problémákat is, amelyekben megoldást kell találni, ha néhány teljesítménykritérium(például profit, bevétel, erőforrásköltség stb.) maximum vagy minimum értéket vesz fel.

Az adott feladatok különböző gyakorlati területekre vonatkoznak, de vannak közös vonásaik: minden esetben néhányról beszélünk irányított esemény (művelet), egy bizonyosra törekszik cél. Az 1. feladatban - ez a mintavételi ellenőrzés megszervezése a termékek minőségének biztosítása érdekében; 2. feladatban - időszakos kiskereskedelmi üzletek szervezése szezonális értékesítés lebonyolítása céljából; a 3. feladatban - tömeges orvosi vizsgálat az esetek százalékos arányának meghatározására.

Minden feladat tartalmaz néhányat körülmények ennek a rendezvénynek a lebonyolítása, melynek keretein belül meg kell tenni megoldás -úgy, hogy az esemény valamilyen hasznot hoz. A művelet végrehajtásának feltételei az egyes feladatoknál a rendelkezésünkre álló eszközök, idő, eszközök, technológia, a megoldás az 1. feladatban az ellenőrzési forma megválasztása - ellenőrzési tételek nagysága, elutasítási szabályok; a 2. feladatban - az elhelyezési pontok számának és a létszám kiválasztásában; a 3. feladatban - az orvosi állások számának, a vizsgálatok típusának és számának megválasztásában.

1. Az operációkutatás alapfogalmai és definíciói

Művelet- minden olyan irányított esemény, amelynek célja egy cél elérése. A művelet eredménye a végrehajtás módjától, szervezésétől, egyébként - bizonyos paraméterek megválasztásától függ.

A paraméterek bármilyen konkrét megválasztását hívjuk döntés.

Optimális fontolja meg azokat a megoldásokat, amelyek ilyen vagy olyan okból előnyösebbek, mint mások. Ezért fő feladat műveletek kutatása előzetes kvantitatív optimális megoldások indoklása.

Megjegyzés 1. Figyelmet kell fordítani a probléma megfogalmazására: a döntéshozatal túlmutat az operációkutatás keretein, és a felelős személy vagy embercsoport felelőssége, aki a matematikailag indokolttól eltérő szempontokat is figyelembe vehet.

Jegyzet 2. Ha egyes műveletek kutatási problémáinál az az optimális megoldás, amelyben valamilyen hatékonysági kritérium érvényesül

maximum vagy minimum érték, akkor más feladatoknál ez egyáltalán nem szükséges. Így a 2. feladatban a kiskereskedelmi egységek és a bennük lévő személyzet optimális létszámát úgy tekinthetjük, hogy az átlagos ügyfélszolgálati idő ne haladja meg például az 5 percet, és a sor hossza átlagosan minden időpontban ne legyen hosszabb. mint 3 ember.

A kvantitatív kutatási módszerek alkalmazásához építeni szükséges a művelet matematikai modellje. A modell felépítése során a műveletet általában egyszerűsítik, sematizálják, és a műveleti sémát egy vagy másik matematikai berendezéssel írják le.

Modell tevékenységek - ez a művelet meglehetősen pontos leírása matematikai apparátussal (különféle függvények, egyenletek, egyenletrendszerek és egyenlőtlenségek stb.). Egy művelet modelljének elkészítéséhez a leírt jelenség lényegének megértése és a matematikai apparátus ismerete szükséges.

Működési hatékonyság - a feladathoz való alkalmazkodóképességének mértékét mennyiségileg egy hatékonysági kritérium - a célfüggvény - formájában fejezzük ki. Például az erőforrások felhasználásának problémájában a hatékonysági kritérium az előállított termékek értékesítéséből származó haszon, amelyet maximalizálni kell, a szállítási problémában pedig az áruk szállítótól a fogyasztóig történő szállításának összköltsége, amelyet minimalizálni kell. . A hatékonysági kritérium megválasztása határozza meg a vizsgálat gyakorlati értékét. (A rosszul megválasztott kritérium káros lehet, hiszen az ilyen hatékonysági kritérium szerint szervezett működés esetenként indokolatlan költségekkel jár.)

2. Az operációkutatási probléma általános megfogalmazása

Fontos megérteni az operációkutatási problémák modelljének felépítésének módszertanát. A művelet leírásában szereplő összes tényező két csoportra osztható:

állandó tényezők(működési feltételek), amit nem tudunk befolyásolni. Jelöljük őket α1, α2, ... ;

függő tényezők(a megoldás elemei) x 1, x2, ...; amelyeket bizonyos határok között belátásunk szerint választhatunk.

Például az erőforrások felhasználásának problémájában az állandó tényezők közé kell sorolni az egyes típusok erőforrás-tartalékait, a termelési mátrixot, amelynek elemei meghatározzák az egyes típusok nyersanyag-felhasználását az egyes típusok kibocsátási egységére vetítve. A megoldás elemei - gyártási terv minden terméktípushoz.

Valamilyen ún. függvény által kifejezett teljesítménykritérium cél, mindkét csoport tényezőitől függ, tehát a célfüggvény Z formába írható

Z= f (x1, x2, ..., α1, α2, ...)

Az operációkutatás minden modellje osztályozható a művelet jellege és tulajdonságai, a megoldandó problémák természete, valamint az alkalmazott matematikai módszerek jellemzői alapján.

Meg kell jegyezni mindenekelőtt a nagy optimalizálási modellek osztálya. Ilyen problémák merülnek fel, ha komplex rendszerek, elsősorban gazdasági rendszerek tervezését és irányítását próbálják optimalizálni. Az optimalizálási probléma általános formában megfogalmazható: változók keresése x1, x2, ..., x n , egyenlőtlenségrendszer (egyenlet) kielégítése

g én (x1, x2, x3,..., x n )<= b én , i = 1, 2,..., n (0.1)

És a célfüggvény maximumra (vagy minimumra) fordítása, azaz.

Z= f (x1, x2, ..., x n ) - m ah (m ban ben ) (0.2)

(A változók nem-negativitásának feltételeit, ha vannak, a (0.1) korlátozás tartalmazza.)

Nézzünk egy másik, az operációkutatásra jellemző problémát - a klasszikus fogyasztási probléma, nagy jelentősége van a közgazdasági elemzésben.

Legyen Páruk és szolgáltatások típusai, amelyek mennyisége (természetes egységekben) x1, x2, ..., x n, ennek megfelelő áron p 1, p 2, ..., p n egy egységhez. Ezen áruk és szolgáltatások teljes költsége ∑ p én x én .

Fogyasztási szint Z valamilyen függvénnyel kifejezhető Z= f (x1, x2, ..., x n ) ,hívott hasznossági függvény. Meg kell találni egy ilyen áru- és szolgáltatáskészletet x1, x2, ..., x n adott jövedelem összege I, nak nek maximális fogyasztási szint biztosítása, azok.

Z= f (x1, x2, ..., x n ) - m Ó (0.3)

tekintettel arra

∑ p én x én <= én (0.4)

x én >= 0 ( én = 1, 2,..., n ) (0.5)

Az áraktól függő megoldások erre a problémára p 1, p 2, ..., p nés a bevétel összegét én, hívják keresleti függvények.

Nyilvánvaló, hogy a vizsgált fogyasztási probléma (0,3)-(0,5), valamint sok más, a függvény szélsőértékének meghatározására fentebb megfogalmazott általános probléma (0,1)-(0,2) speciális esete. P változók bizonyos korlátozások mellett, pl. feladat számára feltételes extrémum.

Azokban az esetekben, amikor a funkciók fÉs g én, a (0.1)-(0.2) feladatban legalább kétszer differenciálhatóak, használhatjuk klasszikus optimalizálási módszerek. Ezeknek a módszereknek az operációkutatásban való felhasználása azonban nagyon korlátozott, mivel az i változók függvényének feltételes szélsőértékének meghatározása technikailag nagyon nehéz: a módszer lehetővé teszi a lokális szélsőség meghatározását, illetve a változók többdimenziós jellegéből adódóan. a függvény, annak maximális (vagy minimum) értékének (globális szélsőértékének) meghatározása igen munkaigényesnek bizonyulhat - főleg, hogy ez a szélsőség a megoldási tartomány határán lehetséges. A klasszikus módszerek egyáltalán nem működnek, ha az érvényes argumentumértékek halmaza diszkrét vagy a függvény Z táblázatban van megadva. Ezekben az esetekben a (0.1)-(0.2) feladat megoldására módszereket alkalmazunk matematikai programozás.

Ha a teljesítménykritérium Z= f (x1, x2, ..., x n ) (0.2) egy lineáris függvényt és a függvényeket jelöli g én (x1, x2, x3,..., x n ) a kényszerrendszerben (0.1) is lineárisak, akkor egy ilyen probléma probléma lineáris programozás. Ha a tartalom alapján a megoldásai egész számok kell, hogy legyenek, akkor ez a probléma egészszámú lineáris programozás. Ha a hatékonysági kritériumot és (vagy) a korlátozási rendszert nemlineáris függvények adják meg, akkor megvan a probléma nemlineáris programozás. Különösen, ha a jelzett függvények konvexitási tulajdonságokkal rendelkeznek, akkor az ebből eredő probléma probléma konvex programozás.

Ha egy matematikai programozási feladatban van időváltozó, és a hatékonysági kritérium (0,2) nem kifejezetten változók függvényében, hanem közvetetten - a műveletek időbeni lefolyását leíró egyenletek segítségével fejeződik ki, akkor egy ilyen probléma probléma. dinamikus programozás.

Ha a hatékonysági kritériumot (0,2) és a korlátozási rendszert (0,1) az űrlap függvényei adják meg Val vel*( x 1^α 1 )*( x 2^α 2 )...( x n ^α n ) , akkor megvan a probléma geometriai programozás. Ha a funkciók fés/vagy g én a (0.2) és (0.1) kifejezésekben a paraméterek függvénye, akkor megkapjuk a problémát parametrikus programozás, ha ezek a függvények véletlenszerű jellegűek, a feladat sztochasztikus programozás. Ha a túlzottan sok megoldási lehetőség miatt nem lehet algoritmikusan megtalálni a pontos optimumot, akkor folyamodjunk módszerekhez heurisztikus programozás, lehetővé teszi, hogy jelentősen csökkentse a keresett lehetőségek számát, és találjon, ha nem is optimális, de egy meglehetősen jó megoldást, amely gyakorlati szempontból kielégítő.

A matematikai programozás felsorolt ​​módszerei közül a legelterjedtebb és legfejlettebb a lineáris programozás. Az operációkutatási feladatok széles körét fedi le.

Hálózattervezési és -menedzsment feladatok vegyük figyelembe egy nagy műveleti komplexum (munkálatok) befejezési dátumai és a komplexum összes műveletének kezdési időpontja közötti kapcsolatot. Ezek a feladatok a műveletek minimális időtartamának, a költségértékek optimális arányának és végrehajtásuk időzítésének megtalálásából állnak.

Sorbaállási problémák Az alkalmazások vagy követelmények sorát tartalmazó szolgáltatási rendszerek tanulmányozására és elemzésére szolgálnak, és a rendszerek teljesítménymutatóinak, optimális jellemzőinek meghatározásából állnak, például a szolgáltatási csatornák számának, a szolgáltatási időnek stb.

Készletgazdálkodási feladatok a készletszint (rendelési pont) és a rendelési méret optimális értékeinek megtalálásából áll. Az ilyen feladatok sajátossága, hogy a készletek szintjének növekedésével egyrészt a tárolás költségei nőnek, másrészt csökkennek a tárolt termék esetleges hiánya miatti veszteségek.

Erőforrás-allokációs problémák bizonyos műveletek (munkák) során merülnek fel, amelyeket korlátozottan rendelkezésre álló erőforrásokkal kell elvégezni, és meg kell találni az erőforrások optimális elosztását a műveletek között vagy a műveletek összetételét.

Berendezés javítási és csere feladatok fontosak a berendezések elhasználódása és idővel történő cseréjének szükségessége miatt. A feladatok az optimális időzítés, a megelőző javítások és ellenőrzések számának meghatározásában, valamint a berendezések korszerűsített berendezésre való cseréjének időpontjában merülnek fel.

Feladatok ütemezése (ütemezése). a műveletek optimális sorrendjének meghatározása (például alkatrészek feldolgozása) különféle típusú berendezéseken.

Tervezési és elhelyezési feladatok az új objektumok optimális számának és helyének meghatározásából áll, figyelembe véve a meglévő objektumokkal és egymással való kölcsönhatásukat.

Útvonalválasztási problémák vagy hálózat a leggyakrabban felmerülő problémák a közlekedési és kommunikációs rendszerek különböző problémáinak tanulmányozása során, és a leggazdaságosabb útvonalak meghatározásából állnak.

Az operációkutatás modelljei közül a konfliktushelyzetekben az optimális döntéshozatal modelljeit vizsgálta játékelmélet. Azok a konfliktushelyzetek, amelyekben két (vagy több) fél érdekei ütköznek, különböző célokat követve, számos helyzetet foglalnak magukban a közgazdaságtan, a jog, a katonai ügyek stb. területén. A játékelméleti problémáknál ajánlásokat kell kidolgozni a a konfliktusban résztvevők ésszerű viselkedése, optimális stratégiáik meghatározása.

A gyakorlatban a legtöbb esetben egy művelet sikerességét nem egy, hanem egyszerre több kritérium alapján értékelik, amelyek közül az egyiket maximalizálni, a többit minimalizálni. A matematikai apparátus olyan esetekben is hasznos lehet több szempontú műveletek kutatási problémái, legalább segít elvetni a nyilvánvalóan sikertelen megoldásokat.

A célfüggvény kiválasztásához számos kritérium közül, beleértve azokat is, amelyek ellentmondanak egymásnak (például nyereség és ráfordítás), meg kell határozni prioritás kritériumok. Jelöljük f 1 (x), f 2 (x), ..., f n (x)(Itt X - feltételes érv). Rendezzük őket csökkenő fontossági sorrendbe. Bizonyos feltételektől függően alapvetően két lehetőség van:

Célfüggvényként a kritériumot választjuk f 1 (x), a legmagasabb prioritású;

Egy kombinációt fontolgatnak

f ( x ) = ω 1 * f 1 ( x ) + ω 2 * f 2 ( x ) + …+ ω n * f n ( x ) , (0.6)

Ahol ω 1 , ω 2 , … ω n- néhány együttható (súly).

Nagyságrend f (X), amely bizonyos mértékig minden kritériumot figyelembe vesz, célfüggvényként kerül kiválasztásra.

A bizonyosság feltételei között ω én- számok, f én (x)- funkciókat. A bizonytalanság körülményei között f én (x) véletlenszerűnek bizonyulhat, és helyette f én (x) az összeg matematikai elvárását (0,6) kell célfüggvénynek tekinteni.

Az a kísérlet, hogy egy többkritériumú problémát egy hatékonysági feltétellel (objektív függvény) problémává redukáljunk, a legtöbb esetben nem ad kielégítő eredményt. Egy másik megközelítés abban áll, hogy a nyilvánvalóan sikertelen megoldásokat az elfogadható megoldások sorából kiselejtezzük („kiselejtezzük”), amelyek a többieknél rosszabbak. minden kritérium. Ezen eljárás eredményeként az ún hatékony(vagy " Pareto") megoldásokat, amelyek halmaza általában lényegesen kisebb, mint az eredeti. És a „kompromisszumos” megoldás végső választása (nem minden kritérium szerint optimális, ami általában nem létezik, de elfogadható e kritériumok szerint) marad a személynél – a döntéshozónál.

Következtetés

Az orosz tudósok L. V. nagymértékben hozzájárultak egy modern matematikai apparátus létrehozásához és a műveletek kutatásának számos területének fejlesztéséhez. Kantorovich, N.P. Buslenko, E.S. Ventzel, N.N. Vorobjov, N.N. Moiseev, D.B. Yudin és még sokan mások. Különösen figyelemre méltó az akadémikus L.V. Kantorovich, aki 1939-ben, miután elkezdte a rétegelt lemez gyáregységek üzemeltetését, számos problémát megoldott: a berendezések legjobb rakodásáról, az anyagok minimális veszteséggel járó darabolásáról, a rakomány elosztásáról a különféle szállítási módok között stb. L.V. Kantorovich a feltételesen szélsőséges problémák új osztályát fogalmazta meg, és egy univerzális módszert javasolt ezek megoldására, megalapozva az alkalmazott matematika új irányát - a lineáris programozást.

Az operációkutatás kialakításában és fejlesztésében jelentős mértékben járultak hozzá külföldi tudósok, R. Akof, R. Bellman, G. Danzig, G. Kuhn, J. Neumann, T. Saaty, R. Churchman, A. Kofman és mások.

Az operációkutatási módszerek, mint minden matematikai módszer, mindig leegyszerűsítik és valamilyen mértékben elnagyítják a problémát, néha nemlineáris folyamatokat tükröznek lineáris modellekkel, sztochasztikus rendszereket determinisztikusokkal, dinamikus folyamatokat statikus modellekkel stb. Az élet gazdagabb minden programnál. Ezért nem szabad sem eltúlozni a kvantitatív módszerek jelentőségét az operációkutatásban, sem a sikertelen megoldások példáira hivatkozva minimalizálni. Helyénvaló ezzel kapcsolatban megemlíteni az operációkutatás humorosan paradox definícióját, amelyet egyik megalkotója, T. Saaty fogalmazott meg: „azokra a gyakorlati kérdésekre a rossz válaszok művészete, amelyek más módszerekkel még rosszabbul is megválaszolhatók”.

Irodalom

1. Kremer N. Sh., Putko B. A., Trishin I. M., Fridman M. N. Operációk kutatása a közgazdaságtanban: Tankönyv egyetemeknek - M.: UNITI, 2002.

2. Ventzel E.S. Operációkutatás. Célok, alapelvek, módszertan - M.: Nauka, 1980.

3. Gorelik V.A., Ushakov I.A. Operációkutatás. - M.: Gépészmérnök, 1986.

BAN BEN. Slinkin

Tankönyv pedagógiai egyetemek hallgatóinak

számítástechnika szakon

Shadrinsk, 2003

Slinkina I.N.

Operációkutatás. Oktatási és módszertani kézikönyv. – Shadrinsk: a Shadrinsk Állami Pedagógiai Intézet kiadója, 2002. - 106 p.

Slinkina I.N. – a pedagógiai tudományok kandidátusa

A tankönyv az Operations Research tantárgy elméleti részét mutatja be. Az „Informatika” szakot folytató karok nappali és részmunkaidős hallgatói számára készült.

© Shadrinsk Állami Pedagógiai Intézet

© Slinkina I.N., 2002

Kérdések az „Operations Research” kurzus egységeihez 5

1.1. Az operációkutatás tárgya és feladatai 7

1.2. Az operációkutatás alapfogalmai és elvei 8

1.3. A műveletek matematikai modelljei 10

1.4. A lineáris programozás fogalma 12

1.5. Példák gazdasági lineáris programozási problémákra. Az erőforrások legjobb felhasználása, 13. probléma

1.6. Példák gazdasági lineáris programozási problémákra. Az optimális technológiák kiválasztásának problémája 15

1.7. Példák gazdasági lineáris programozási problémákra. Keverési probléma 16

1.8. Példák gazdasági lineáris programozási problémákra. Szállítási probléma 17

1.9. A lineáris programozási problémák rögzítésének alapvető típusai 19

1.10. 21 konverziós módszer

1.11. Áttérés a kanonikus formára 22

1.12. Áttérés a felvétel szimmetrikus formájára 25

2.1. A lineáris programozási feladat geometriai értelmezése 28

2.2. Lineáris programozási feladatok megoldása grafikus módszerrel 29

2.3. Lineáris programozási problémák megoldásainak tulajdonságai 34

2.4. A szimplex módszer általános ötlete 35

2.5. A kezdeti referenciaterv felépítése lineáris programozási feladatok megoldása során szimplex módszerrel 36

2.6. A referenciaterv optimálisságának jele. Simplex táblázatok 40

2.7. Áttérés a legrosszabb eset referenciatervére. 44

2.8. Szimplex transzformációk 46

2.9. Alternatív optimum (a referenciaterv-készlet végtelenségének jele) 51

2.10. A célfüggvény határtalanságának jele 52

2.11. A degeneráció fogalma. A szimplex módszer monotonitása és végessége. Hurkolás 53

2.12. A dualitás fogalma szimmetrikus lineáris programozási problémák esetén 54

3.1. Aszimmetrikus kettős problémák 57

3.2. A közlekedési probléma nyitott és zárt modelljei 61

3.3. A kezdeti referenciaterv elkészítése. Északnyugati sarok 63. szabály

3.4. A kezdeti referenciaterv elkészítése. Minimális elem szabály 64

3.5. A kezdeti referenciaterv elkészítése. Vogel-módszer 64

3.6. 65. lehetséges módszer

3.7. Szállítási problémák megoldása kapacitáskorlátozással 69

3.8. Példák diszkrét programozási problémákra. Konténerszállítási probléma. Hozzárendelési probléma 71

3.9. A diszkrét optimalizálási módszerek lényege 72

3.10. Konvex programozási probléma 74

3.11. Lagrange-szorzó módszer 75

3.12. Gradiens módszerek 77

4.1. Büntetés- és sorompófunkciók módszerei 78

4.2. Dinamikus programozás. Alapfogalmak. A megoldási módszerek lényege 79

4.3. Sztochasztikus programozás. Alapfogalmak 81

4.4. Nulla összegű mátrixjátékok 83

4.5. Tiszta és vegyes stratégiák és tulajdonságaik 85

4.6. A tiszta és vegyes stratégiák tulajdonságai 88

4.7. Egy mátrixjáték redukálása ZLP 92-re

4.8. A sorbanállás elméletének problémái. Sorozati rendszerek osztályozása 94

4.9. Eseményfolyamok 96

4.10. A halál és szaporodás sémája 97

4.11. Little's Formula 99

4.12. A legegyszerűbb sorban állási rendszerek 101

Kérdések a blokkhoz az „Operations Research” kurzusban

1. blokk

1. Az operációkutatás tárgya és céljai.

2. Az operációkutatás alapfogalmai és elvei.

3. Műveletek matematikai modelljei.

4. A lineáris programozás fogalma.

5. Példák gazdasági lineáris programozási problémákra. Feladat

6. Példák gazdasági lineáris programozási problémákra. Az optimális technológiák kiválasztásának problémája.

7. Példák gazdasági lineáris programozási problémákra. Probléma a keverékekkel.

8. Példák gazdasági lineáris programozási problémákra. Közlekedési probléma.

9. A lineáris programozási feladatok írásának alaptípusai.

10. Konverziós módszerek.

11. Áttérés a kanonikus formára.

12. Áttérés a felvétel szimmetrikus formájára.

2. blokk

1. A lineáris programozási probléma geometriai értelmezése.

2. Lineáris programozási feladatok megoldása grafikus módszerrel.

3. A lineáris programozási probléma megoldásainak tulajdonságai.

4. A szimplex módszer általános ötlete.

5. A kiindulási referenciaterv felépítése lineáris programozási feladatok szimplex módszerrel történő megoldása során.

6. A referenciaterv optimálisságának jele. Simplex táblázatok.

7. Áttérés a nem legrosszabb referenciatervre.

8. Szimplex transzformációk.

9. Alternatív optimum (a referenciaterv-halmaz végtelenségének jele).

10. A célfüggvény határtalanságának jele.

11. A degeneráció fogalma. A szimplex módszer monotonitása és végessége. Hurkolás.

12. A dualitás fogalma szimmetrikus lineáris programozási problémákra.

3. blokk

1. Aszimmetrikus kettős problémák.

2. A közlekedési probléma nyitott és zárt modelljei.

3. A kezdeti referenciaterv elkészítése. "Északnyugati sarok" szabály.

4. A kezdeti referenciaterv elkészítése. Minimális elem szabály.

5. A kezdeti referenciaterv elkészítése. Vogel módszer.

6. A potenciálok módszere.

7. Szállítási problémák megoldása kapacitáskorlátozással.

8. Példák diszkrét programozási problémákra. Konténerszállítási probléma. Hozzárendelési probléma.

9. A diszkrét optimalizálási módszerek lényege.

10. Konvex programozási probléma.

11. Lagrange-szorzó módszer.

12. Gradiens módszerek.

4. blokk

1. Büntetés- és sorompófunkciók módszere.

2. Dinamikus programozás. Alapfogalmak. A megoldási módszerek lényege.

3. Sztochasztikus programozás. Alapfogalmak.

4. Nulla összegű mátrixjátékok.

5. Tiszta és vegyes stratégiák.

6. Tiszta és vegyes stratégiák tulajdonságai.

7. Mátrix játék redukálása PLP-vé

8. A sorozás elméletének problémái. Sorozati rendszerek osztályozása.

9. Eseményfolyamok.

10. A halál és szaporodás sémája.

11. Little képlete.

12. A legegyszerűbb sorban állási rendszerek.

1. blokk.

Az operációkutatás tárgya és feladatai

A tudomány és a technika jelenlegi állása, különös tekintettel a számítógépes számítási eszközök fejlődésére és az elméletek matematikai alátámasztására, lehetővé tette számos tudományágak számára felmerülő probléma megoldásának jelentős egyszerűsítését. Sok probléma a termelés optimalizálása és az optimális folyamatszabályozás kérdésének megoldására vezethető vissza.

A gyakorlati igények speciális tudományos módszereket eredményeztek, amelyeket kényelmesen az „operációkutatás” néven kombinálunk.

Meghatározás: Operációkutatás alatt matematikai, kvantitatív módszerek alkalmazását értjük a döntések igazolására a céltudatos emberi tevékenység minden területén.

Tegyenek lépéseket egy bizonyos cél elérése érdekében. A rendezvényt szervező személynek (vagy embercsoportnak) mindig van némi választási szabadsága: megszervezhető így vagy úgy. A döntés egy választás a szervező rendelkezésére álló számos lehetőség közül.

A döntések meghozatalának és a javasolt megoldási hipotézis tesztelésének szükségességét a következő példák matematikailag megerősítik:

1. feladat. Az erőforrások legjobb felhasználásáról.

A cég többféle terméket gyárt. Előállításukhoz bizonyos erőforrásokat használnak fel (beleértve az embert, az energiát stb.). Ki kell számítani, hogyan kell megtervezni a vállalkozás munkáját úgy, hogy az erőforrások költségei minimálisak legyenek, és a nyereség maximalizálódjon.

2. feladat. A keverékekről.

Olyan keveréket kell készíteni, amely bizonyos tulajdonságokkal rendelkezik. Ehhez használhat néhány „terméket” (étrendek kiszámításához - élelmiszerek, takarmánykeverékek - állatok számára készült élelmiszerek, műszaki keverékek - ötvözetek, folyadékok műszaki célokra). a feladat az optimális számú termék kiválasztása (ár szerint), hogy az optimális keverékmennyiséget kapjuk.

3. feladat. Közlekedési probléma.

Létezik a hasonló, azonos minőségű termékeket előállító vállalkozások hálózata, valamint ezen termékek fogyasztóinak hálózata. A fogyasztókat és a beszállítókat kommunikációs útvonalak (utak, vasútvonalak, légitársaságok) kötik össze. A szállítási díjakat meghatározták. Ki kell számítani a termékek szállításának optimális tervét, hogy a szállítási költségek minimálisak legyenek, minden fogyasztó szükségletei kielégítve legyenek, és minden árut eltávolítsanak a szállítóktól.

A megadott példák mindegyikében valamilyen eseményről beszélünk, amely meghatározott célt követ. Meghatároznak bizonyos feltételeket, amelyek a helyzetet jellemzik (különösen a megsemmisíthető eszközöket). Ezen feltételek között kell olyan döntést hozni, hogy a tervezett rendezvény valamilyen értelemben jövedelmezőbb legyen.

Ezen általános jellemzőknek megfelelően a hasonló problémák megoldására általános módszereket dolgoznak ki, amelyek együttesen alkotják az operációkutatás módszertani sémáját és apparátusát.

Jelenleg a számítástechnika alkalmazásán alapuló automatizált vezérlőrendszerek (ACS) terjednek el. Az automatizált vezérlőrendszer létrehozása lehetetlen a vezérelt folyamat előzetes matematikai modellezési módszerekkel történő vizsgálata nélkül. Az események növekvő léptékű és összetettebbé válásával a döntések alátámasztására szolgáló matematikai módszerek egyre fontosabbá válnak.

Az operációkutatás alapfogalmai és elvei

Meghatározás: Művelet minden olyan esemény (cselekvési rendszer), amelyet egyetlen terv egyesít, és valamilyen cél elérésére irányul.

Egy művelet mindig irányított esemény, pl. A számításoktól függ, hogyan kell kiválasztani a szervezetét jellemző paramétereket. A „szervezet” itt a szó tág értelmében értendő, beleértve a művelet során használt technikai eszközök összességét is.

Meghatározás: A döntő paraméterektől függő minden konkrét választást döntésnek nevezünk.

Meghatározás: Az optimális megoldások azok, amelyek ilyen vagy olyan okból előnyösebbek, mint mások.

Az operatív kutatás célja– optimális megoldások előzetes mennyiségi indoklása.

Néha a vizsgálat eredményeként egyetlen, szigorúan definiált megoldást lehet megjelölni, sokkal gyakrabban lehet azonosítani a szinte egyenértékű optimális megoldások területét, amelyen belül meg lehet hozni a végső választást.

Maga a döntéshozatal túlmutat az operációkutatás keretein, és a felelős személy, gyakrabban egy olyan embercsoport hatáskörébe tartozik, akiknek joga van a végső döntés meghozatalára, és akik felelősséggel tartoznak ezért a döntésért.

Meghatározás: Azokat a paramétereket, amelyek kombinációja megoldást alkot, megoldáselemeknek nevezzük.

A megoldás elemei lehetnek különféle számok, vektorok, függvények, fizikai jellemzők stb. Az egyszerűség kedvéért a megoldás teljes elemkészletét x-szel jelöljük.

Bármely műveletkutatási probléma megoldási elemei mellett adottak a probléma állapotában rögzített, nem sérthető feltételek is. Az ilyen feltételek közé tartoznak különösen az ártalmatlanítható eszközök (anyagi, műszaki, emberi), valamint a döntésre vonatkozó egyéb korlátozások. Ezek együttesen alkotják az úgynevezett „lehetséges megoldások halmazát”. Jelöljük ezt a halmazt X, és azt, hogy az x megoldás ehhez a halmazhoz tartozik, a következőképpen lesz írva: xОХ.

A különböző megoldások hatékonysági összehasonlításához szükség van valamilyen mennyiségi kritériumra, az úgynevezett hatékonysági mutatóra (objektív függvény). Ez a mutató úgy van kiválasztva, hogy tükrözze a művelet célirányát. A legjobb megoldásnak azt tekintjük, amely a lehető legnagyobb mértékben hozzájárul a cél eléréséhez. A Z teljesítménymutató kiválasztásához először meg kell határoznia, hogy a probléma megoldásának mihez kell vezetnie. A megoldás kiválasztásakor előnyben részesítjük azt, amelyik a Z hatékonysági mutatót maximumra vagy minimumra fordítja. Például szeretném maximalizálni a műveletből származó bevételt; ha a hatékonyság mutatója a költségek, akkor azokat célszerű minimálisra csökkenteni.

Nagyon gyakran a műveletet véletlenszerű tényezők kísérik: a természet „szeszélyei”, a kereslet-kínálat ingadozása, a műszaki eszközök meghibásodása stb. Ilyenkor általában nem magát az értéket szeretnénk maximalizálni (minimalizálni), hanem az átlagértéket (matematikai elvárást) tekintjük a hatékonyság mutatójának.

A teljesítménymutató kiválasztásának feladatát minden egyes problémára egyedileg oldják meg.

1. feladat. Az erőforrások legjobb felhasználásáról.

A művelet célja a maximális számú áru előállítása. Hatékonysági mutató Z – az áruk értékesítéséből származó nyereség minimális erőforrásköltséggel (max Z).

2. feladat. A keverékekről.

A hatékonyság természetes mutatója, amit a probléma megfogalmazása sugall, a keverékhez szükséges termékek ára, a keverék meghatározott tulajdonságainak megőrzése mellett (min Z).

3. feladat. Közlekedési probléma.

A működés célja a fogyasztók áruellátásának biztosítása minimális szállítási költséggel. A Z hatékonysági mutató az áruszállítás teljes költsége időegységre vetítve (min Z).