Meg kell tanulnia az operációkutatás alapfogalmait és definícióit.

A művelet minden olyan ellenőrzött tevékenység, 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 minden határozott megválasztását megoldásnak nevezzük. Optimális megoldásnak azokat tekintjük, amelyek valamilyen okból előnyösebbek másoknál. Ezért az operációkutatás fő feladata az optimális megoldások előzetes kvantitatív igazolása.

Megjegyzés 1

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

2. megjegyzés

Ha a műveletkutatás egyes feladatainál az az optimális megoldás, amelyben a választott hatékonysági kritérium maximumot vagy minimális értéket vesz fel, akkor más feladatokban erre egyáltalán nincs szükség. Tehát a problémában optimálisnak tarthatunk például olyan számú üzletet és bennük lévő személyzetet, amelyekben az átlagos ügyfélszolgálati idő nem haladja meg például az 5 percet, és az átlagos sorban állás bármikor legfeljebb 3 fő lehet (1, .10-11. oldal).

A termelés és a kereskedelmi tevékenység hatékonyságát nagymértékben meghatározza a különböző szintű vezetők által napi szinten meghozott döntések minősége. Ebben a tekintetben nagy jelentőséggel bírnak a döntéshozatali folyamatok fejlesztésének feladatai, amelyek megoldását az operációkutatás lehetővé teszi. Az "operációs kutatás" kifejezést először 1939-1940-ben használták. katonai területen. Ekkorra a tudományos és technológiai forradalom következtében a haditechnika és annak kezelése alapvetően bonyolulttá vált. Ezért a második világháború elejére sürgősen szükség volt tudományos kutatásra az új katonai felszerelések hatékony felhasználása, a parancsnokság által hozott döntések mennyiségi értékelése és optimalizálása terén. A háború utáni időszakban az új tudományág sikereire a békés területeken volt igény: az iparban, a vállalkozói és kereskedelmi tevékenységben, a kormányzati intézményekben és az oktatási intézményekben.

Az operációkutatás a matematikai kvantitatív módszerek alkalmazásának módszertana a céltudatos emberi tevékenység minden területén felmerülő problémák megoldásának igazolására. Az operációkutatás módszerei és modelljei lehetővé teszik, hogy olyan megoldásokat kapjunk, amelyek a legjobban megfelelnek a szervezet céljainak.

Az operációkutatás a szervezeti rendszerek leghatékonyabb (vagy optimális) irányítását szolgáló módszerek kidolgozásával és gyakorlati alkalmazásával foglalkozó tudomány.

Az operációkutatás fő posztulátuma a következő: az optimális megoldás (kontroll) a változók olyan értékkészlete, amely eléri a művelet hatékonysági kritériumának (objektív függvényének) optimális (maximum vagy minimum) értékét, és betartja a meghatározott korlátozások.

Az operációkutatás tárgya az optimális döntések meghozatalának problémája egy olyan rendszerben, amelynek működése eredményességének értékelése alapján vezérelhető. A műveletkutatás jellemző fogalmai: modell, változó változók, megszorítások, célfüggvény.

Az operációkutatás tárgya a valóságban a szervezetirányítási rendszerek (szervezetek), amelyek nagyszámú, egymással kölcsönhatásban álló részlegből állnak, és az osztályok érdekei nem mindig állnak összhangban egymással, és ellentétesek is lehetnek.

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

Optimálisnak azt a megoldást nevezzük, 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ás pedig szuboptimális lesz.

Példaként a szervezeti menedzsment tipikus problémájára, ahol az osztályok ellentétes érdekei ütköznek, vegyük figyelembe a vállalkozás készletgazdálkodásának problémáját.

A gyártó részleg arra törekszik, hogy minél több terméket a lehető legalacsonyabb költséggel állítson elő. Ezért érdekli a lehető leghosszabb és folyamatos gyártás, vagyis a termékek nagy tételben történő előállítása, mivel az ilyen gyártás csökkenti a berendezések átkonfigurálásának költségeit, és ezáltal a teljes gyártási költségeket. A termékek nagy mennyiségben történő előállításához azonban nagy mennyiségű anyag-, alkatrész- stb. készlet létrehozása szükséges.

Az értékesítési részleg a késztermékek nagy készleteiben is érdekelt, hogy bármikor kielégítse a vevői igényeket. Az egyes szerződések megkötésekor az értékesítési osztálynak, igyekezve minél több terméket értékesíteni, a lehető legszélesebb termékpalettát kell kínálnia a fogyasztónak. Emiatt a gyártási részleg és az értékesítési részleg között gyakran konfliktus van a termékpaletta kapcsán. Ugyanakkor az értékesítési részleg ragaszkodik ahhoz, hogy sok kis mennyiségben gyártott termék szerepeljen a tervben, még akkor is, ha azok nem hoznak nagy nyereséget, és a termelési osztály követeli az ilyen termékek kizárását a termékkínálatból.

A pénzügyi osztály a vállalkozás működéséhez szükséges tőkemennyiség minimalizálására törekszik, a „kapcsolódó” forgótőke mennyiségének csökkentésére törekszik. Ezért érdekelt abban, hogy a készleteket minimálisra csökkentsék. Mint látható, a szervezet különböző részlegeinek készleteinek méretére vonatkozó követelmények eltérőek. Felmerül a kérdés, hogy melyik készletezési stratégia lesz a leghasznosabb az egész szervezet számára. Ez a szervezetirányítás tipikus feladata. Összefügg a rendszer egésze működésének optimalizálásának problémájával, és kihat a részlegeinek ütköző érdekeire.

Az operatív kutatás főbb jellemzői:

1. A felvetett probléma elemzésének szisztematikus megközelítése. A rendszerszemlélet vagy rendszerelemzés a műveletkutatás fő módszertani elve, amely a következő. Bármilyen feladatot első pillantásra magánjellegűnek is tűnik, abból a szempontból veszünk figyelembe, hogy milyen hatással van az egész rendszer működésének kritériumára. Fentebb a szisztematikus megközelítést a készletgazdálkodási probléma példájával illusztráltuk.

2. Az operációkutatásra jellemző, hogy az egyes problémák megoldása során egyre több új feladat merül fel. Ezért ha eleinte szűk, korlátozott célokat tűznek ki, az operatív módszerek alkalmazása nem hatékony. A legnagyobb hatás csak folyamatos kutatással érhető el, biztosítva az egyik feladatról a másikra való átmenet folytonosságát.

3. Az operációkutatás egyik lényeges jellemzője a probléma optimális megoldásának megtalálása. Egy ilyen megoldás azonban gyakran elérhetetlennek bizonyul a rendelkezésre álló erőforrások (pénz, számítógépes idő) vagy a modern tudomány színvonala miatti korlátok miatt. Például számos kombinatorikus feladatra, különösen az n > 4 gépszámmal kapcsolatos ütemezési problémákra, a matematika modern fejlődésével az optimális megoldást csak az opciók egyszerű felsorolásával lehet megtalálni. Ekkor az embernek egy „elég jó” vagy szuboptimális megoldás keresésére kell szorítkoznia. Ezért egyik megalkotója, T. Saaty úgy határozta meg az operációkutatást, mint "... azokra a gyakorlati kérdésekre rossz válaszok művészete, amelyekre más módszerekkel még rosszabb válaszokat adnak".

4. Az operatív kutatás jellemzője, hogy komplexen, sok területen folyik. Egy ilyen vizsgálat elvégzésére operatív csoportot hoznak létre. Különböző tudásterületek szakembereiből áll: mérnökök, matematikusok, közgazdászok, szociológusok, pszichológusok. Az ilyen operatív csoportok létrehozásának feladata a probléma megoldását befolyásoló tényezők teljes halmazának átfogó vizsgálata, a különböző tudományok ötleteinek, módszereinek felhasználása.

Minden operatív kutatás a következő fő szakaszokon megy keresztül egymás után:

1) a tervezési feladat leírása,

2) matematikai modell felépítése,

3) megoldást találni,

4) a modell ellenőrzése és javítása,

5) a megtalált megoldás gyakorlati megvalósítása.

A tervezési feladat leírása:

A hálózattervezés és -menedzsment feladatai

mérlegelje a nagy műveleti komplexum (munkálatok) befejezésének határideje és a komplexum összes műveletének kezdetének pillanatai közötti kapcsolatot. Ezek a feladatok a műveletek minimális időtartamának, a költségek optimális arányának és végrehajtásának időzítésének megtalálásából állnak.

A sorba állítási feladatok az alkalmazások vagy követelmények sorát tartalmazó sorbanállá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.

A készletkezelési feladatok a készletszintek (rendelési pontok) és a rendelési méretek optimális értékeinek megtalálása. Az ilyen feladatok sajátossága abban rejlik, hogy a készletek szintjének növekedésével egyrészt nőnek a tárolás költségei, másrészt csökkennek a raktározott termék esetleges hiánya miatti veszteségek.

Erőforrás allokációs problémák merülnek fel egy bizonyos műveletsornál (munkálatoknál), amelyeket korlátozottan rendelkezésre álló erőforrásokkal kell végrehajtani, é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.

A berendezések javításának, cseréjének feladatai a berendezések elhasználódása és időbeli cseréjének szükségessége miatt relevánsak. A feladatok az optimális időzítés meghatározására, a megelőző javítások és ellenőrzések számának, valamint a berendezés korszerűsítettre cseréjének pillanataira korlátozódnak.

Az ütemezés (ütemezés) feladata a különböző típusú berendezéseken végzett műveletek (például alkatrészek feldolgozása) optimális sorrendjének meghatározása.

A tervezés és elhelyezés feladatai az új objektumok számának és elhelyezkedésének meghatározása, figyelembe véve a meglévő objektumokkal és egymás közötti interakcióikat.

Útvonalválasztási problémák vagy hálózati problémák leggyakrabban a közlekedés és a kommunikációs rendszer különböző problémáinak tanulmányozása során merülnek fel, és a leggazdaságosabb útvonalak meghatározásából állnak (1, 15. o.).

művelet nevezünk minden olyan eseményt (cselekvési rendszert), amelyet egyetlen terv egyesít és egy meghatározott cél elérésére irányul. A művelet mindig sikerült esemény, azaz. rendelkezni lehet néhány, a szervezetét jellemző paraméter kiválasztásának módszerével. Ezeket az opciókat hívják vezérlő változók.

Az ilyen változók bármilyen határozott 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.

Az operációkutatás bármely feladatának vannak kezdeti "diszciplináris" feltételei, pl. olyan kezdeti adatok, amelyek a kezdetektől rögzítettek és nem sérthetők meg. Ezek együttesen alkotják a lehetséges megoldások úgynevezett halmazát.

A különböző megoldások hatékonyságának összehasonlításához 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 nem magát az optimalizálni kívánt értéket vesszük a hatékonyság mutatójának, 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. DE, amely vagy teljesen elérhető, vagy egyáltalán nem érhető el (például "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 egy p(A) = 0 vagy 1, akkor elérkezünk a kibernetikában jól ismert „fekete doboz” problémához.)

A teljesítménymutató helytelen megvá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ás feladatának általános megfogalmazása

Az operációkutatási feladatok két kategóriába sorolhatók: a) közvetlen és b) inverz.

Közvetlen feladatok válaszoljon a kérdésre: mi lesz 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 építenek, amely lehetővé teszi a hatékonysági mutató adott feltételekkel történő kifejezését és egy megoldást, nevezetesen:

ahol
adott tényezők (kiindulási adatok),

vezérlő változók (megoldás),

Z– teljesítménymutató (objektív funkció),

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ő módon fejeződik ki. közötti kapcsolat és általában korlátokként 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 ehhez a funkcióhoz.

Inverz problémák válaszoljon a kérdésre: hogyan, adott feltételek mellett megoldást választani
hogy a teljesítménymutató Z maximumra (minimumra) fordult. Az ilyen problémát megoldásoptimalizálási feladatnak nevezzük.

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

Meg akarta 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ó extrémumának keresésének 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 rótt korlátok típusa. (Például egy klasszikus lineáris programozási probléma.)

1. Az IO alapfogalmai

ÉS RÓLA – tudományos tudományág, amely 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. (gazdasági tevékenységi tervek, programok megalapozása); szakaszokat tartalmaz: lineáris program, nemlineáris program, dinamikus program

2) a véletlenszerű folyamatok elméletén alapuló sorban állás elmélete;

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

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

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

A későbbi döntéshozatalt meghatározó összefüggések tanulmányozása, teljesítménykritériumok felállítása, amelyek lehetővé teszik egy vagy másik cselekvési mód előnyeinek értékelé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álasszuk ki a szervezetét jellemző paraméterek egy részét. 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ármely adott választása meghívásra kerül 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 a matematikai apparátus segítségével (különféle függvények, egyenletek, egyenletrendszerek és egyenlőtlenségek stb.). A működési modell 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 feladat teljesítéséhez 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 meghatározza a vizsgálat gyakorlati értékét. (A rosszul megválasztott kritérium káros lehet, mert az ilyen hatékonysági kritérium alapján szervezett működés esetenként indokolatlan költségekkel jár.)

A hálózattervezés és -menedzsment feladatai mérlegelje a nagy műveleti komplexum (munkálatok) befejezésének határideje és a komplexum összes műveletének kezdetének pillanatai közötti kapcsolatot. Ezek a feladatok a műveletek komplexumának minimális időtartamának, a költségek optimális arányának és végrehajtásának időzítésének megtalálásából állnak.

Sorba állítási feladatok Az alkalmazás- vagy követelménysorokkal rendelkező sorbanállási rendszerek tanulmányozására és elemzésére szolgál, és a rendszerek teljesítménymutatóinak, optimális jellemzőik meghatározásából áll, 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 (utánrendelé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 nőnek a tárolás költségei, másrészt csökkennek a raktározott termék esetleges hiánya miatti veszteségek.

Erőforrás-allokációs feladatok Egy bizonyos műveletsorral (munkákkal) merül 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 a berendezések elhasználódása és idővel történő cseréjének szükségessége miatt releváns. A feladatok az optimális időzítés meghatározására, a megelőző javítások és ellenőrzések számának, valamint a berendezés korszerűsítettre cseréjének pillanataira korlátozódnak.

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 azok interakcióját a meglévő tárgyakkal és egymás között.

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

2. A lineáris program általános feladata. Optimális megoldás

Gazdasági és matematikai modell

Az LP a matematika egy olyan területe, 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ának problémáinak megoldására lineáris kényszerek, 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) a lehetséges megoldások közül ki kell választani a legjobb megoldást (optimális tervet); 2) a megoldás bizonyos nagyságrendű változók é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ényeként fejezzük ki. A célfüggvény értékei, amelyek lehetővé teszik a különböző megoldások összehasonlítását, 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 megírni. Gazdasági-matematikai modell - a vizsgált gazdasági folyamat vagy tárgy matematikai leírása. Ez a modell a gazdasági folyamat mintázatait 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ó kiválasztása, amelyek hozzárendelése - számértékei egyértelműen meghatározzák 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 problémakényszer-rendszert alkotnak;

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 támasztott korlátok függvényében.

A lineáris programozás általános problémájaúgy néz ki, mint a:

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

és lineáris függvény

Ilyen 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) Az LP probléma az (1) kényszerrendszer X=(x1,x2,…,xj,…,xn) megoldása, amely teljesíti a (3) feltételt, amely mellett a (2) lineáris függvény az optimálisat (maximális ill. 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 az alapformájú probléma, amely abban különbözik, 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 egyik másik egyenletben sem szerepel. Az ezzel a tulajdonsággal rendelkező változót alapváltozónak 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

Az m lineáris egyenletrendszernek n változóval van alakja

vagy gyorsírással

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. 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 megoldási halmaza között megkülönböztetjük az ún. alapmegoldásokat.

Alap megoldás egy m lineáris egyenletrendszert n változóval olyan megoldásnak nevezzük, amelyben minden n–m nem alapváltozó nullával egyenlő.

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

Konvex ponthalmazok

A konvex poligont a nem konvex poligontól az az általános definiáló tulajdonság, 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 felfogható egy konvex ponthalmaz definíciójaként.

A ponthalmazt konvexnek nevezzük, ha bármely 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ül kiemelhetünk belső, határ- és sarokpontokat.

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

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

A sarokpontok különösen érdekesek a lineáris programozási problémáknál. A halmaz pontját ún szögletes(vagy extrém), ha nem belső egyetlen olyan szegmensre sem, amely teljes egészében az adott halmazhoz tartozik.

á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 szögletes, mivel minden olyan szakasz esetében, amely teljesen a sokszöghez tartozik, például az AP szakaszhoz, 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, ugyanakkor ez nem szükséges egy nem konvex halmaznál. 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ú golyó (kör), amely az adott halmazt teljesen tartalmazza; egyébként a halmazt korlátlannak nevezzük.

Konvex zárt ponthalmazt egy síkban, amelynek véges sok sarokpontja van, konvex sokszögnek nevezzük, ha korlátos, és konvex sokszögtartománynak, ha nem korlátos.

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

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 fekszik a határán - a megépített vonalon. Ha az egyenlőtlenség egy vezérlőpontban teljesül, akkor a vezérlőpontot tartalmazó félsík minden pontjában is teljesül, és nem teljesül a másik félsík összes pontjában. És fordítva, ha az egyenlőtlenség nem teljesül a 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. Ellenőrzési pontként célszerű az O (0; 0) koordináták origóját venni, amely nem a megszerkesztett egyenesen fekszik.

Tekintsük az egyenlőtlenségek rendszereinek megoldásait.

2. állítás. Két változós m lineáris egyenlőtlenségek konzisztens 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ároz egy félsíkot, amely pontok konvex halmaza. A lineáris egyenlőtlenségek együttes rendszerének megoldásainak 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ái - a sokszög csúcsai a megfelelő vonalak metszéspontjainak koordinátáiként találhatók.

Egyenlőtlenségi rendszerek megoldási területeinek megalkotásakor más esetek is előfordulhatnak: a megoldások halmaza egy konvex sokszögtartomány (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

az LP probléma optimális megoldása

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 ezen pontok konvex lineáris kombinációja.

A tétel az LP feladatok megoldásának fő módját jelzi. Valójában e tétel szerint a megengedett megoldások végtelen halmazának tanulmányozása helyett a kívánt optimális megoldás megtalálásához a megoldási poliédernek csak véges számú sarokpontját kell megvizsgálni.

A következő tételt a sarokpontok megtalálásának analitikai módszerének szenteljük.

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.

Az 1. és 2. tételből rögtön egy fontos következmény következik: ha egy LP-feladatnak van optimális megoldása, akkor az legalább egy megvalósítható alapmegoldással egybeesik.

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

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

Tekintsünk egy problémát szabványos formában két változóval (P = 2).

Legyen a kényszerrendszer geometriai ábrázolása egy sokszög ABCDE(4.1. ábra). Ennek a sokszögnek a pontjai között meg kell találni egy olyan 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ény szintvonala áthalad F a legnagyobb (ha a lineáris függvény maximalizált) vagy a legkisebb (ha minimalizálva van) szinttel.

A c1x1+c2x2=a függvény szintvonalának egyenlete egy egyenes egyenlete. Különféle szinteken a a szintvonalak párhuzamosak, mivel meredekségeit csak a c1 és c2 együtthatók aránya határozza meg, és ezért egyenlők. Tehát a jellemzőszintű vonalak F – ezek sajátos "párhuzamok", amelyek általában a koordinátatengelyekkel szöget zárnak be.

A lineáris függvény szintvonalának fontos tulajdonsága, hogy az egyenes párhuzamos eltolásával az egyik irányban a szint csak nő, a másik irányú eltolással pedig csak csökken. Az origóból induló c=(c1,c2) ​​vektor jelzi az F függvény leggyorsabb növekedésének irányát. 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ási sokszöget!

2. Szerkesszen meg egy c = (c1, c2) vektort, és húzza meg neki a lineáris függvény szintjének vonalát. F például F=0.

3. Az F=0 egyenes párhuzamos eltolása a c(-c) vektor irányába, hogy megtaláljuk azt az Amax(Bmin) pontot, ahol F eléri a maximumát (minimumát).

1. Az optimális pontban metsző egyenesek egyenleteinek együttes megoldásával, határozzuk meg annak koordinátáit!

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

Megjegyzés. A minimális pont a döntési sokszögbe való „belépés” pont, 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 fő té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. kényszerrendszer. Bármely lineáris programozási probléma megoldásának módját jelölték meg: fel kell sorolni a kényszerrendszer véges számú megvalósítható alapmegoldását, és ezek közül kiválasztani azt, amelyen a célfüggvény az optimális döntést hozza. Geometriailag ez megfelel a megoldási poliéder összes sarokpontjának számbavételének. Egy ilyen felsorolás végül elvezet egy optimális megoldáshoz (ha létezik), de gyakorlati megvalósítása óriási nehézségekkel jár, hiszen valós problémák esetén a megvalósítható alapmegoldások száma, bár véges, rendkívül nagy lehet.

A felsorolandó megengedhető alapmegoldások száma csökkenthető, ha a felsorolást nem véletlenszerűen, hanem a lineáris függvény változásait figyelembe véve, pl. arra törekedni, hogy a lineáris függvény értékeit tekintve minden következő megoldás "jobb" (vagy legalábbis "nem rosszabb") legyen, mint az előző (a maximum megtalálásakor növelve, minimum megtalálásakor csökkentve) . Egy ilyen felsorolás lehetővé teszi az optimum megtalálásának lépéseinek csökkentését. Magyarázzuk meg ezt egy grafikus példával.

A megvalósítható megoldások területét egy sokszög ábrázolja ABCDE. Tegyük fel, hogy a sarokpontja DE megfelel az eredeti megengedhető alapmegoldásnak. Véletlenszerű felsorolásnál a sokszög öt sarokpontjának megfelelő öt megvalósítható alapmegoldást kellene kipróbálni. A rajz azonban azt mutatja, hogy a felső után DE előnyös a következő csúcsra menni NÁL NÉL, majd az optimális pontig TÓL TŐL.Öt helyett csak három csúcsot jártunk be, következetesen javítva a lineáris függvényt.

A megoldás szekvenciális 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 egymást követő 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; amíg meg nem találjuk az optimális megoldást - azt a csúcsot, ahol a célfüggvény optimális értékét elérjük (ha a feladatnak véges optimuma van).

A szimplex módszert először J. Danzig amerikai tudós javasolta 1949-ben, de már 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 megvalósításához - a megoldás egymás utáni javításához - elsajátításra van szükség három fő elem:

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

a legjobb (pontosabban nem a legrosszabb) 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 a kanonikus formára, azaz. a kényszerrendszert egyenletek formájában kell bemutatni.

A szakirodalom kellő részletességgel ismerteti: a kezdeti referenciaterv (kezdeti megvalósítható alapmegoldás) megtalálása, mesterséges bázis módszerrel is, az optimális referenciaterv megtalálása, feladatok megoldása szimplex táblák segítségével.

7 . A szimplex módszer algoritmusa.

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

1. A feladat feltételének megfelelően összeállítjuk annak matematikai modelljét.

2. A megszerkesztett modellt kanonikus formára konvertáljuk. Ebben az esetben egy kezdeti referenciatervvel rendelkező alap kiemelkedik.

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 korlátozó egyenletrendszert és egy célfüggvényt a kezdeti bázishoz képest feloldott kifejezések formájában adunk meg. Azt a sort, amelybe az F célfüggvény együtthatóit beírjuk, F-vonalnak vagy a célfüggvény egyenesének nevezzük.

4. A kezdeti referenciatervet úgy találjuk meg, hogy szimplex transzformációkat hajtunk végre a minimális szimplex arányoknak megfelelő pozitív felbontású elemekkel, és figyelmen kívül hagyjuk az F-sor elemeinek előjeleit. Ha az átalakítások során van egy 0 sor, amelynek a szabad tag kivételével minden eleme nulla, akkor a feladat restrikciós egyenletrendszere inkonzisztens. Ha viszont van olyan 0 sor, 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 új bázisra redukálása kerül meghívásra szimplex transzformáció . Ha egy szimplex transzformációt formális algebrai műveletnek tekintünk, akkor látható, hogy a 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, ill. a másik fordítva - függetlenről függőre. Ez a művelet az algebrában ún Jordan kieső lépés.

5. A talált kezdeti alaptervet 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 az optimális terv egyedi; ha van legalább egy nulla, akkor végtelen számú optimális terv létezik;

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

c) ha az F-sorban legalább egy negatív elem, az oszlopában pedig legalább egy pozitív elem van, akkor átválthatunk egy új, az optimálishoz közelebbi referenciatervre. Ehhez a megadott oszlopot feloldóként kell hozzárendelni, a minimális szimplex aránnyal, meg kell keresni a feloldó sort és végrehajtani egy szimplex transzformációt. A kapott alaptervet újra megvizsgáljuk az optimálisság szempontjából. A leírt folyamatot addig ismételjük, amíg egy optimális tervet nem kapunk, vagy amíg a probléma megoldhatatlanná válik.

A bázisban szereplő változó együtthatók oszlopát feloldásnak nevezzük. Így az F sor negatív elemével a bázisba bevitt változót választva (vagy feloldó oszlopot választva) biztosítjuk, hogy az F függvény növekedjen. .

Kicsit nehezebb meghatározni az alapból kizárandó változót. Ehhez elkészítik a szabad tagok arányát a feloldó oszlop pozitív elemeihez (az ilyen relációkat szimplexnek nevezzük), é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árandó változó (illetve a feloldó sztring) minimális szimplex arány szerinti megválasztása garantálja a már megállapított alapkomponensek pozitivitását az új referenciatervben.

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

1) nézzük meg egy negatív szabad tagnak megfelelő sort, például egy t-sort, és válasszunk ki benne tetszőleges negatív elemet, és a hozzá tartozó oszlopot tekintjük megengedőnek (feltételezzük, hogy a probléma korlátai kompatibilisek );

2) állítsa be a szabad tagok oszlopának elemeinek arányát a felbontóoszlop megfelelő elemeihez, amelyek azonos előjelűek (szimplex arányok);

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

4) a feloldó oszlopok és sorok metszéspontjában egy feloldó elem található. Ha az y-karakterlánc eleme feloldónak bizonyult, akkor a szimplex transzformáció után ennek a karakterláncnak a szabad tagja lesz pozitív. Ellenkező esetben a következő lépésben a t-sort újra megcímzi. Ha a probléma megoldható, akkor bizonyos számú lépés után nem lesz 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 a kényszermátrix;

C=(c1,c2,…,cn)–vektor–sor;

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 mollja. Azaz, van legalább egy m rendű B részmá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 módosítva A mátrixot mindig A=(B|N) alakba hozhatjuk,

ahol N egy almátrix, amely az A mátrix olyan oszlopaiból áll, amelyek nem tartoznak a bázishoz. Ugyanígy fel lehet bontani az x vektort – az alapváltozók vektorára és.

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

Mert |B|<>0, akkor van egy inverz mátrix. A bal oldali inverzével megszorozva a következőket kapjuk:

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

Az alapmegoldás (a B bázishoz képest) a (2) feladat speciális megoldása, amelyet a feltétel alapján kapunk. Akkor egyedileg meghatározott.

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

A megvalósított alapmegoldásnak megfelelő alap. hívott megvalósítható alap. 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. Az alapváltozók elé bevezetjük a Cb-együtthatókat, a többit a Cn.

Így kapunk. 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.

Doc-in: Hadd. 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).

Aztán nézzük

Így az alapmegoldás min. Ellenkezőleg, ne legyünk elégedettek, 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 egy Xi:Xj szabad változónak felel meg, adjunk hozzá egy értéket és vigyük be a bázisba, és származtassunk egy másik változót és nevezzük szabadnak.

Hogyan határozzuk meg? Az összes szabad változó a változó kivételével továbbra is 0.

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

Kivesszük: - szükséges feltételt.

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 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 az alkatrészt, rögzítjük, akkor más megoldást találunk; – amelynél az egyik alapváltozó =0. Ezt a változót kihagyjuk az alapból, írjuk be az xi-t. Új bázis B2 konjugátumot kaptunk 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 értelmezzük, mint egy sarokpontból egy konjugált sarokpontba való átmenetet az X halmaz, a probléma megoldásainak halmaza mentén. 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, akkor 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ások felhasználásának kettős problémája

Egy feladat. Kétféle P1 és P2 termék gyártásához négyféle S1, S2, S3, S4 erőforrást használnak. Adott erőforráskészletek, egy egységnyi kibocsátás előállítására fordított erőforrás-egységek száma. Ismert a P1 és P2 termelési egységből származó nyereség. Tervet kell készíteni olyan termékek előállítására, amelyekben az értékesítésből származó nyereség maximális lesz.

Egy 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 egy olyan X=(x1,x2,…,Xn) termelési tervet, amelyben a termékek értékesítésébő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ó mennyiséget. készletek

Egy 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 készletét jelöli; aij- egy termelési egység előállításához felhasznált Si erőforrás-egységek 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 termelési ár) .

Tegyük fel, hogy egy szervezet S1,S2,…,Sm vállalati erőforrások vásárlása mellett döntött, és ezekre az y1,y2,…,ym erőforrásokra optimális árat kell beállítani. Nyilvánvaló, hogy a beszerző szervezet érdekelt abban, hogy az összes Z erőforrás költsége b1,b2,…,bm mennyiségben 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 az az összeg, amelyet a vállalkozás az erőforrások késztermékké történő feldolgozásakor kaphat.

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 költenek egy egységnyi P1 termék előállítására y1,y1,…,yi áron. ,…,ym, ill. Ezért az eladó követelményeinek teljesítéséhez a P1 termelési egység gyártása során felhasznált erőforrások költségének legalább a c1 árának kell lennie, azaz. a11y1+a21y2+…+am1ym>=c1.

Hasonlóképpen lehetséges megszorításokat összeállítani egyenlőtlenségek formájában minden P1,P2,…Pn szorzattí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 feltételes , "hamis" árak. Ellentétben a termékek „külső” c1,c2,…,cn áraival, amelyek általában a gyártás megkezdése előtt ismertek, az y1,y2,…,ym erőforrások árai vannak belső , mert nem kívülről vannak beállítva, hanem közvetlenül a probléma megoldása eredményeként határozzák meg, ezért gyakran hívják őket 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 a lineáris függvény maximumát, a másikban a minimumot keresik.

2. Egy probléma lineáris függvényében szereplő változók együtthatói egy másik probléma kényszerrendszerének szabad tagjai.

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

4. Mindkét probléma kényszerrendszerében szereplő változók együtthatói mátrixait transzponáljuk egymásra.

5. Egy probléma kényszerrendszerében az egyenlőtlenségek száma megegyezik 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ója alá van vetve a nem-negativitási feltételnek, akkor a duális feladat 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 korlátai és a duális probléma változói hasonló összefüggésben állnak egymással.

A lineáris programozás két I. és II. feladatát a jelzett tulajdonságokkal szimmetrikus kölcsönösen duális 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 társítható a kettős problémájával.

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

1. Hozd az eredeti probléma kényszerrendszerének minden egyenlőtlenségét egy jelentésbe: ha egy lineáris függvény maximumát keressük az eredeti feladatban, akkor a kényszerrendszer összes egyenlőtlensége a következő alakra redukálódik<=", а если минимум – к виду ">=". Azoknál az egyenlőtlenségeknél, amelyeknél ez a követelmény nem teljesül, szorozd 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: alkossuk meg a duális probléma célfüggvényét úgy, hogy az eredeti probléma kényszerrendszerének szabad tagjait vegyük a változók együtthatóinak; állítson össze a kettős probléma kényszerrendszerét, a mátrix elemeit a változók együtthatójaként, az eredeti probléma célfüggvényében szereplő változók együtthatóit pedig szabad tagként veszi fel, és írja le az ellenkező értelmű egyenlőtlenségeket; írja le a duális probléma változóinak nem-negativitásának feltételét!

12. Első dualitástétel

A duális feladatok optimális megoldásai közötti kapcsolatot dualitástételek segítségével állapítjuk meg.

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

Ha egy 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 optimális megoldása, és a II. duális feladat optimális megoldása.

A kölcsönösen kettős problémák optimálisságának elégséges kritériuma mellett megoldásaik között más fontos összefüggések is vannak. Mindenekelőtt felmerülnek a kérdések: mindig van-e egyidejűleg optimális megoldás minden kettős feladatpárra; lehetséges-e, hogy a kettős problémák egyikének van megoldása, a másiknak pedig nincs. Ezekre a kérdésekre a következő tétel ad 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, és a lineáris függvényeik optimális értékei:

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ő kettősségi tétel második részével ellentétes állítás általános esetben nem igaz, i.e. 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 ne lenne korlátos.

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

Gyártási terv X*=(x1*,x2*,…,xn*) és az erőforrások árai (becslései) 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) c1,c2,…,cn árakon megegyezik a "belső" (csak meghatározott) erőforrások költségével. feladat megoldásából) árak y1 ,y2,…,ym. Az összes többi tervhez xés Y Mindkét feladat esetén a termékből származó nyereség (bevétel) mindig kisebb (vagy egyenlő), mint az erőforrások költsége.

Az első kettősségi tétel közgazdasági jelentése a következőképpen is értelmezhető: a vállalkozásnak nem mindegy, hogy az X*=(x1*,x2*,…,xn*) optimális terv szerint gyártja-e a termékeket és a maximális profitot ( bevétel) Fmax vagy értékesítsen erőforrásokat optimális áron Y* =(y1*,y2*,…,ym*) és az eladásból azzal megegyezően térítse meg a minimális erőforrásköltséget Zmin.

13. A második kettősségi tétel

Adjunk meg két kölcsönösen kettős problémát. Ha ezeket a feladatokat szimplex módszerrel oldjuk meg, akkor azokat kanonikus formára kell redukálni, amihez az I. feladat (röviden jelöléssel) kényszerrendszerében be kell vezetni. t nem negatív változók, hanem a II. feladat kényszerrendszerébe () – n nem negatív változók, ahol i(j) annak az egyenlőtlenségnek a száma, amelyben a további változót bevezetjük.

Az egyes kölcsönösen kettős problémák kényszerrendszerei a következőképpen alakulnak:

Á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 egy 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 feladatok szimplex módszerrel történő megoldásának utolsó lépésében) megfeleltetést jelent fő-(általában 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 elfogadható alapmegoldásokat alkotnak.

A 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óinál az együtthatók abszolút értékeivel, optimális megoldásának kisebb változóiban 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ók szempontjából optimális megoldásának 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 duális 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 kondicionált 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 készletei közötti különbséget jelentik és fogyasztásukat, expressz maradék erőforrásokat , é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ége és a P1,P2 termékek cj ára közötti különbséget jelentik. , Expressz többletköltség az ár felett.

Így az erőforrások objektíven meghatározott becslései határozzák meg 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ösek pedig nulla becsléseket kapnak. Az y*i érték az i-edik erőforrás becslé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 költséghatékony, veszteséges terméktípusok kerülhetnek be (bár itt a jövedelmezőség kritériuma sajátos: egy termék ára nem haladja meg a gyártás során felhasznált erőforrások költségeit, hanem pontosan megegyezik nekik).

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éggel változik, ha a megfelelő erőforrás készlete egy egységgel változik.

A kettős becslés eszközül szolgálhat az elemzéshez és a megfelelő döntések meghozatalához egy folyamatosan változó iparágban. Így 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 nem bármilyen, hanem csak viszonylag kis erőforrás-változás hatásának megítélését teszik lehetővé. Hirtelen változtatások esetén maguk a becslések is eltérőek lehetnek, ami azt eredményezi, hogy a termelés hatékonyságának elemzésére nem használhatók fel. Az objektíven meghatározott becslések arányai szerint meghatározhatók azok a számított erőforrás-helyettesítési normák, amelyek mellett a kettős becslések stabilitásán belül a folyamatban lévő pótlások nem befolyásolják az optimális terv hatékonyságát. Következtetés. A kettős pontszámok 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 függő költség és eredmény összehasonlítására.

15. A szállítási feladat kimutatása a költség szempontja szerint.

A TK - a leggazdaságosabb terv feladata egy homogén vagy cserélhető terméknek a gyártási helyről (induló állomásról) a fogyasztási helyekre (célállomások) történő szállítására - az LP legfontosabb magánfeladata, amely kiterjedt gyakorlati alkalmazásokkal nem rendelkezik. csak közlekedési problémákra.

A TK-t az LP-ben a gazdasági jellemzők bizonyossága, a matematikai modell jellemzői, a konkrét megoldási módszerek jelenléte különbözteti meg.

A TOR legegyszerűbb megfogalmazása a költségek szempontjából a következő: in t Az A1,…,Am kiindulási pontok a1,…,am a szállítandó homogén rakomány (erőforrások) egységei 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 úgy, hogy az igényeket maradéktalanul kielégítsük, és a teljes szállítási költség minimális.

Az érthetőség kedvéért a TK feltételeit táblázat formájában mutatjuk be, amelyet ún terjesztés .

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

Itt az i-edik kiindulá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 a j-edik rendeltetési hely igénye a rakományban 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 jelöli azon rakományegységek számát, amelyeket az i-edik kiindulási pontról a j-edik célállomásra kell szállítani. Az xij mátrixot ún forgalmi 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 vonatkozó korlátozásoknak és a negativitás feltételeinek:

– a készletekre vonatkozó korlátozások (2);

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

a nem-negativitás feltételei (3).

Így matematikailag a közlekedési probléma a következőképpen fogalmazódik meg. Adott a (3) feltétel szerinti kényszerrendszer (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 a közlekedési probléma elfogadható tervei legyenek, szükséges és elegendő az egyenlőség

Kétféle szállítási feladat 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ók keresletét, vagy a fogyasztók kereslete nagyobb, mint a szállítók tényleges összkapacitása, azaz.

A nyitott modell zárttá alakítható. Tehát, ha, akkor a közlekedési probléma matematikai modelljébe egy fiktív (n + 1)-edik cél kerül be. Ehhez a feladatmátrixban egy további oszlop szerepel, amelyre a szükséglet megegyezik a szállítók teljes kapacitása és a fogyasztók tényleges kereslete közötti különbséggel:

Az áruk e pontig történő szállítására vonatkozó összes tarifát nullával egyenlőnek kell tekinteni. Ily módon a probléma nyitott modellje zárttá alakul. Új probléma esetén a célfüggvény mindig ugyanaz, mivel a járulékos szállítás költsége nulla. Vagyis a fiktív fogyasztó nem sérti meg a kényszerrendszer következetességét.

Ha, akkor egy fiktív (m + 1)-edik kiindulási pontot vezetnek be, amelyhez a rakományállományt hozzá kell rendelni.

Az ettől a fiktív szállítótól származó áruk szállításának tarifáit ismét nullának kell tekinteni. Egy sor kerül a mátrixba, ez nem befolyásolja a célfüggvényt, és a problémakényszerrendszer kompatibilissé válik, azaz lehetővé válik az optimális terv megtalálása.

A következő tétel nagy jelentőséggel bír a közlekedési probléma szempontjából.

Tétel. A transzportfeladat mátrixának rangja eggyel kevesebb, mint az egyenletek száma, azaz. 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 alapvá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. Feltételezzük, 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 főtervnek tartalmaznia kell m+n-1 elfoglalt cellákés a többi ingyen lesz.

Ezek az alaptervre vonatkozó követelmények nem az egyedüliek. Az alapterveknek egy másik, a ciklusokkal kapcsolatos követelménynek is meg kell felelniük.

A forgalmi mátrix cellák azon 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. Ezenkívül a ciklus minden csúcsán pontosan két link található, amelyek közül az egyik egy sorban, a másik pedig egy oszlopban található. Ha a ciklust alkotó vonallánc önmagát metszi, akkor az önmetszéspontok nem csúcsok.

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

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

2) ha van alaptervünk, akkor minden szabad cellára csak egy ciklust lehet kialakítani, amely ezt a cellát és a foglalt cellák egy részét tartalmazza.

17. A kezdeti alapvonal felépítése

Északnyugati sarokszabály.

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

A bal felső saroktól kezdve, hagyományosan "északnyugati sarokként" fogjuk kitölteni, tovább haladva a vonal mentén jobbra vagy lefelé az oszlopban. Az (1; 1) cellába az a1 és b1 számok közül a kisebbet tesszük, azaz. Ha, akkor az első oszlop „zárt”, azaz az első fogyasztó kereslete teljes mértékben kielégül. 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 továbblépünk a második sor vagy a második oszlop következő harmadik cellájának kitöltésére. Ezt a folyamatot addig folytatjuk, amíg egy bizonyos szakaszban a források és a szükségletek el nem merü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.

A kezdeti, „északnyugati sarok” szabály szerint megépített referenciaterv általában nagyon távol áll az optimálistól, mivel a cij költséget nem veszik figyelembe annak meghatározásakor. Ezért a további számításoknál 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 maximális lehetséges „mozgatása” a cellába a 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 legkisebb a legalacsonyabb tarifával rendelkező cellába kerül . Ekkor a beszállítónak megfelelő sor, akinek a készletei teljesen elfogytak, vagy a fogyasztónak megfelelő oszlop, akinek az igénye teljes mértékben ki van elégítve, nem kerül figyelembevételre. Előfordulhat, hogy egy sort és egy oszlopot egyidejűleg ki kell zárni, ha a szállító készlete teljesen elfogy, és a fogyasztó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 feladat szimplex módszerrel történő megoldásának elvéhez, nevezetesen: először meg kell találni a szállítási probléma alaptervét, majd ezt követően sor kerül. az optimális terv elérése érdekében.

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 bizonyos számot, amelyet a szállító potenciáljának Ai-nek neveznek, é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: .

A szállítási probléma lehetséges módszerrel történő megoldásához szükséges:

1. Készítsen egy alapvető szállítási tervet a vázolt 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, illetve 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 szabad és tetszőleges számértéket vehet fel. Például, . Az adott referenciaoldat fennmaradó potenciáljait egyedileg határozzuk meg.

3. Ellenőrizze az optimalitást, pl. a szabad cellákhoz pontszámok kiszámítása. 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 egy új referenciatervre. Gazdasági értelemben az érték azt a változást jellemzi a szállítási összköltségben, amely az i-edik szállító által a j-edik fogyasztónak történő egyszeri szállítása miatt bekövetkezik. Ha, akkor egyetlen szállítás a szállítási költségek megtakarítását eredményezi, ha - azok növekedését. Ezért, 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álasztjuk, szabad cellára építve, amelyhez az újraszámítási ciklusnak felel meg. Miután a ciklus elkészült a kiválasztott szabad cellához, lépjen tovább egy új referenciatervre. Ehhez át kell mozgatnia a terheléseket az ehhez a szabad cellához tartozó cellákon belül az újraszámítási ciklussal.

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

b) A ciklus mínusz celláiban megtaláljuk a minimális készletet, amit jelölünk. A negatív cellákban lévő 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 „+” jelű cellákban, és kivonjuk a mínusz cellákban lévő számokból. A korábban szabad cella foglalt lesz, és belép a referenciatervbe; és a mínusz cella, amelyben az xij számok minimuma szerepelt, szabadnak tekinthető, és elhagyja a referenciatervet.

Így új alapvonal került meghatározásra. Az egyik alapvonalról a másikra fent leírt átmenetet az újraszámítási ciklus eltolódásának nevezzük. Az újraszámítási ciklus mentén történő eltoláskor a foglalt cellák száma változatlan marad, azaz m+n-1 marad. Sőt, ha két vagy több egyforma xij szám van a negatív cellákban, akkor ezek közül csak az egyik cellát ürítjük ki, a többit pedig nulla készlettel töltjük el.

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

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. Ezen problémák egy része természetesen külön lépésekre (szakaszokra) bomlik, de vannak olyan problémák, amelyekben a particionálást mesterségesen kell bevezetni ahhoz, hogy a DP módszerrel megoldható legyen.

Általában a DP módszerek optimalizálják egyes vezérelt rendszerek működését, amelyek hatását becsülik adalékanyag, vagy multiplikatív, objektív funkció. Adalékanyag több f(x1,x2,…,xn) változó függvénye, amelyek értéke néhány olyan fj függvény összegeként kerül kiszámításra, amelyek csak egy xj változótól függenek: . 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 értelme abban rejlik, hogy az eredeti többdimenziós probléma megoldását egy alacsonyabb dimenziójú feladatsorral helyettesítjü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 egy elfogadásból áll megoldásokat ról ről 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 az egyes lépések alapján határozható meg;

4. a rendszer állapotát minden lépésben ugyanazzal a (összetételileg) 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-th lépés, csak az adott megoldástól és a kezdeti állapottól függ k- lépés. Ez a tulajdonság a legfontosabb a dinamikus programozás ideológiája szempontjából, és ún következmények hiánya .

Tekintsük a dinamikus programozási modell általánosított formában történő alkalmazásának kérdéseit. Legyen feladat valamilyen absztrakt objektum kezelése, amely különböző állapotú lehet. Az objektum aktuális állapotát egy bizonyos paraméterkészlettel azonosítjuk, amit a következőkben S-vel jelölünk és ún. állapotvektor. Feltételezzük, hogy az összes lehetséges állapot S halmaza adott. A halmaz az objektumhoz 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 irányítási műveletek diszkrét időpontokban hajthatók végre, és a vezérlés megoldás az egyik vezérlő kiválasztásából áll. terv feladatok ill menedzsment stratégia az x=(x1,x2,…,xn-1) vektort hívjuk meg, melynek összetevői a folyamat egyes lépéseiben kiválasztott vezérlők. Tekintettel a várható utóhatás hiánya az objektum Sk és Sk+1 két egymást követő állapota között ismert funkcionális függés van, amely magában foglalja a kiválasztott vezérlést 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ályát tárgy.

Vezetési hatékonyság minden lépésben k függ az aktuális Sk állapottól, a kiválasztott xk vezérlőtől, és mennyiségileg az fk(xk,Sk) függvényekkel történik, amelyek összegzé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ására redukál x* , ahol maximális összeget fk értékei a megfelelő pályán.

A dinamikus programozás fő elve, hogy minden lépésnél nem az fk(xk,Sk) függvény izolált optimalizálására kell törekedni, hanem az optimális x*k vezérlést kell kiválasztani, feltéve, hogy minden további lépés optimális. Formálisan ez az elv úgy valósul meg, hogy minden lépésnél megtaláljuk k feltételes optimális vezérlések , amely ettől a lépéstől kezdve a legmagasabb összhatékonyságot biztosítja, feltételezve, hogy az aktuális á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ás mellett a folyamat adott szegmensén 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 a rekurzív 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 teljesítenie kell a következő feltételt: bármilyen legyen is a kezdeti állapot sk a k-ik lépésben és az ebben a lépésben választott vezérlés xk, a későbbi ellenőrzéseknek (vezetési döntéseknek) optimálisnak kell lenniük ahhoz képest cocomo yanyu ,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 ban ben társítva valamivel kezdeti állapot ami esetünkben egyenlőség.

A fent megfogalmazott optimalitás elve csak olyan vezérlési objektumokra alkalmazható, amelyeknél az optimális vezérlés megválasztása nem függ a vezérelt folyamat előtörténetétől, vagyis attól, hogy a rendszer hogyan került a jelenlegi állapotba. Ez a körülmény teszi lehetővé a probléma lebontását és gyakorlati megoldását.

Minden egyes feladat esetében a funkcionális egyenletnek megvan a maga sajátos formája, de minden bizonnyal meg kell őriznie a (*) kifejezésben rejlő visszatérő jelleget, amely megtestesíti az optimalitás elvének fő gondolatá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 nyerő.

Minden formalizált játéknál bemutatjuk előírások , 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 a partnerek viselkedéséről; 3) a kifizetés, amelyhez az egyes akciókészletek vezetnek. Általában a nyereség (vagy veszteség) számszerűsíthető; például a veszteséget nullával, a győzelmet eggyel, a döntetlent pedig 1/2-tel é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ékos vesz részt, és többszörös , ha a játékosok száma kettőnél több. Csak a páros játékokat vesszük figyelembe. Két játékos játssza őket DEés NÁL NÉL, akiknek az érdekei ellentétesek, és a játék alatt cselekvések sorozatát értjük DEés NÁL NÉL.

A játék ún zéró-összegű játék vagy ellentétes skoy , ha az egyik játékos nyeresége egyenlő a másik veszteségével, azaz. mindkét fél kifizetésének összege nulla. A játék feladatának teljesítéséhez elegendő az egyik értékének feltüntetése . Ha kijelöljük a- megnyerni az egyik játékost, b – a másik fizetése, majd nulla összegű játékra b= –a, ezért elég figyelembe venni például a.

A szabályok által előírt cselekvések valamelyikének kiválasztását és végrehajtását hívják mozog játékos. Mozgás lehet 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 a játék matematikailag definiálható legyen, a játékszabályoknak meg kell határozniuk minden véletlenszerű lépést 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ékok) 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 következőkben 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 egyes játékosok számára elérhető információk jellege és mennyisége alapján is osztályozzák a másik cselekedeteivel kapcsolatban. 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 Olyan játékot hívnak, amelyben minden játékos minden személyes lépésnél 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 körű információs játékok osztályába, hiszen az ellenfél cselekedeteinek ismeretlensége általában a konfliktushelyzetek lényeges eleme.

A játékelmélet egyik alapfogalma a fogalom stratégiákat .

stratégia A játékost szabályrendszernek nevezzük, amely a helyzettől függően minden egyes személyes lépéshez meghatározza a cselekvésének megválasztását. Általában a játék során minden személyes mozdulatnál a játékos az adott helyzettől függően választ. 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 bizonyos stratégiát választott, amit szabálylista vagy program formájában is megadhatunk. (Tehát 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.

Nak nek döntsd el játszma, meccs , vagy megtalálni játék döntése , minden játékosnak olyan stratégiát kell választania, 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ő ragaszkodik a stratégiájához. 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ármely játékos számára veszteségesnek kell lennie, ha felhagy a stratégiájával ebben a játékban.

Ha a játékot elégszer megismétlik, akkor előfordulhat, hogy a játékosok nem érdekeltek abban, hogy minden egyes játékban nyerjenek vagy veszítsenek, a átlagos győzelem (vereség) minden pártban.

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

Vége a játéknak, amelyben a játékos DE Megvan t stratégiákat és a játékost B - p A stratégiákat m×n játéknak nevezzük.

Vegyünk egy m×n játékot két játékosból DEés NÁL NÉL("mi" és "ellenfél").

Hagyja a játékost DE van t személyes stratégiák, amelyeket A1,A2,…,Am. Hagyja a játékost NÁL NÉL elérhető n személyes stratégiák, jelöljük őket B1,B2,…,Bn.

Hagyja, hogy mindegyik fél válasszon egy adott stratégiát; nekünk Ai lesz, az ellenfélnek Bj. Annak eredményeként, hogy a játékosok bármelyik Ai és Bj () stratégiapárt választják, a játék kimenetele egyedileg meghatározott, azaz. nyerj aij játékost DE(pozitív vagy negatív) és a játékos elvesztése (-aij). NÁL NÉL.

Tegyük fel, hogy az aij értékek 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 játékmátrix. Ennek a mátrixnak a sorai megfelelnek a játékos stratégiáinak DE, az oszlopok pedig a játékos stratégiái B. Ezeket a stratégiákat tisztanak nevezzük.

Az m×n játékmátrix 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 DE számítania kell a játékosnak NÁL NÉL válaszolni fog rá az egyik Bj stratégiával, amelyért a játékos nyereménye DE minimális (lejátszó NÁL NÉL igyekszik "károsítani" a játékost A).

Jelölje a játékos legkisebb nyereményével DE amikor az Ai stratégiát választja a játékos összes lehetséges stratégiájához NÁL NÉL(legkisebb szám én-a kifizetési mátrix sora), azaz.

Az összes szám közül () válassza ki a legnagyobbat: .

Hívjuk fel a játék alacsonyabb ára, vagy maximális nyeremény (maxmin). Ez az A játékos garantált nyereménye a B játékos bármely stratégiája esetén. Következésképpen,

A maximinnak megfelelő stratégiát hívjuk maximal stratégia . Játékos NÁL NÉLérdekelt a játékos fizetésének csökkentésében DE, A Bj stratégiát választva figyelembe veszi a maximálisan lehetséges kifizetést DE. Jelöli

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

és hívja legjobb játék ára vagy minimax kifizetés(minimax). Ego garantált B játékos elvesztése. Ezért,

A minimax stratégiát ún minimax stratégia.

Az az elv, amely a játékosok számára a legóvatosabb minimax és maximin stratégia kiválasztását diktálja, az ún. minimax elv . Ez az elv abból az ésszerű feltevésből következik, hogy minden játékos az ellenfél ellenkező célját akarja elérni.

Tétel. A játék alsó ára soha 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 nettó ára, vagy a játék ára. A játék árának megfelelő minimax stratégiák az optimális stratégiák , és azok összessége optimális megoldás vagy játék döntése. Ebben az esetben a játékos DE a garantált maximumot kapja (a játékos viselkedésétől függetlenül) NÁL NÉL) győzelem v, és a játékos NÁL NÉL eléri a garantált minimumot (a játékos viselkedésétől függetlenül) DE) vesztes v. A játék megoldása állítólag megvan fenntarthatóság , azok. ha az egyik játékos ragaszkodik az optimális stratégiájához, akkor nem lehet előnyös, ha a másik eltér az optimális stratégiájától.

Ha az egyik játékos (pl DE) ragaszkodik az optimális stratégiájához, és a másik játékoshoz (NÁL NÉL) akkor bármilyen módon eltér az optimális stratégiájától az eltérést elkövető játékos számára ez soha nem lehet előnyös; a játékos ilyen eltérése NÁL NÉL legfeljebb változatlanul hagyhatja a nyereséget. és legrosszabb esetben növelje meg.

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

Egy pár tiszta stratégia 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. Az ilyen helyzetet, ha létezik, ún teljesítménypont. A geometriában a felület azon pontját, amelynek a tulajdonsága: egyidejűleg minimum az egyik koordinátán, maximum pedig a másikon, ún. erő pont, analógia alapján ezt a kifejezést használják a játékelméletben.

A játék, amihez , hívott power point játék. Az elem, amely rendelkezik ezzel a tulajdonsággal, a mátrix hatványpontja.

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, amely a következő tulajdonságokban különbözik.

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 alsó és felső ára is.

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

A játékelméletben bebizonyosodott, hogy különösen minden teljes információval rendelkező játéknak van erőpontja, következésképpen minden ilyen játéknak van megoldása, azaz van egy-két optimális stratégia az egyik és a másik oldal számára, ami ad a játék árával megegyező átlagos nyeremény. Ha egy tökéletes információval rendelkező játék csak személyes mozdulatokból áll, akkor, amikor mindkét fél a saját optimális stratégiáját alkalmazza, mindig egy egészen határozott eredménnyel kell végződnie, nevezetesen a játék árával pontosan megegyező nyereménnyel.

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; jellemzőbb az az 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él alapján ezt a választást a minimax elv alapján kell meghatározni. Maximális stratégiánkhoz ragaszkodva az ellenfél bármilyen viselkedése esetén garantáljuk magunknak a játék α alacsonyabb árának megfelelő nyereményt. vegyes stratégiák

vegyes stratégia Sa Az A játékost az A1,A1,…,Ai,…,Am tiszta stratégiák alkalmazásának nevezzük 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óan 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 minden véges játékra olyan megoldást lehet kapni, azaz olyan (általában vegyes) stratégiák párját, hogy ha mindkét játékos használja őket, akkor a nyeremény egyenlő lesz. a játék árához, és az optimális stratégiától való bármilyen egyoldalú eltérés esetén a kifizetés csak a deviáns számára kedvezőtlen irányba változhat. 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 az övétől. Az optimális megoldásnak megfelelő kifizetést ún 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.

Ez az állítás a tartalma az ún a 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 mutatjuk be.

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.

Hagyjuk és – optimális stratégia pár. 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égia tétel: 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áit.

A játékos bármelyik aktív stratégiáját tiszta formá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ára nyeregpont hiányában.

Fontolgat 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.

Nyereghegy nélküli játék, a játékelmélet alaptétele szerint 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 DE ragaszkodik az optimális stratégiájához , akkor az átlagos kifizetése 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 NÁL NÉL. 2v2 játék esetén bármely ellenfél tiszta stratégiája aktív, ha nincs ssdl pont. Játékos nyer DE(játékos elvesztése NÁL NÉL)– egy valószínűségi változó, melynek matematikai elvárása (átlagértéke) a játék ára. Ezért egy játékos átlagos kifizetése DE(optimális stratégia) egyenlő lesz v mind az 1., mind a 2. ellenséges stratégiához.

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

Átlagos játékos nyeremény DE, ha optimális vegyes stratégiát alkalmaz és a játékos NÁL NÉL - 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 DE, ha a 2. játékos a B2 stratégiát használja, azaz. . Ennek alapján 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égia tétel alkalmazása a kereséshez – a játékos optimális stratégiája NÁL NÉL, ezt megkapjuk a játékos bármely tiszta stratégiájára DE (A1 vagy A2) átlagos játékosvesztés NÁL NÉL megegyezik a játék árával v, azaz

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

A játék megoldásának feladata, ha a mátrixa nem tartalmaz nyeregpontot, annál nehezebb, annál nagyobb az érték 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. Lehetőség van a mátrix dimenziójának csökkentésére kizárással másolat és nyilván hátrányos stratégiákat.

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

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 DE veszteséges (kevesebbet nyer).

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 NÁL NÉL 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 2×2 játék geometriai értelmezése

Játék döntés 2×2 világos geometriai értelmezést tesz lehetővé.

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

Az abszcisszán (ábra) Tedd félre 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. , a bal végtől való távolság az A2 stratégia p2 valószínűsége .

Rajzoljunk két merőlegest az x tengelyre az A1 és A2 pontokon keresztül: I-I tengely és II-II tengely. Az I-I tengelyen elhalasztjuk az A1 stratégia szerinti nyereséget; a II-II tengelyen - az A2 stratégia szerinti kifizetések.

Ha A játékos A1 stratégiát használ, akkor B játékos B1 stratégiája szerint a nyereménye a11, a B2 stratégia szerint 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ája szerint a nyereménye a21, a B2 stratégia esetén 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). Két egyenes vonal van. Egyenes B1B1 – ha a játékos DE 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), és B játékos a B1 stratégiát alkalmazza. Nyertes játékos DE egy pontnak felel meg ezen a vonalon. 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 vonalon.

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 nyereséget az a12p1+a22p2 képlet határozza meg, és az M2 pont képviseli. a B2B2 egyenesen.

Meg kell találnunk egy optimális S*a stratégiát, azaz olyat, amelyik esetén (bármilyen viselkedés esetén) minimális a megtérülés NÁL NÉL) maximumra fordulna. Ennek érdekében építkezünk az erősítés alsó határa B1B2 stratégiákkal , ábrán jelölt B1NB2 szaggatott vonal. vastag vonal. Ez az alsó korlát a játékos minimális kifizetését fejezi ki DE bármely vegyes stratégiájához; pontN , amelyben ez a minimális nyeremény eléri a maximumot, és meghatározza a megoldást (optimális stratégiát) és a játék árát. Pont ordináta N van-e ára a játéknak v. Pont koordinátái N a B1B1 és B2B2 egyenesek metszéspontjainak koordinátáit találjuk. Nálunk 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 DE, valamint a játékos NÁL NÉL; mindkét esetben a minimax elvet alkalmazzák, de a második esetben nem a kifizetés alsó, hanem felső határát építik, és nem a maximumot, hanem a minimumot határozzák meg rajta.

Ha a kifizetési mátrix negatív számokat tartalmaz, akkor a probléma grafikus megoldásához jobb, ha egy új, nem negatív elemeket tartalmazó mátrixra váltunk; ehhez elegendő a megfelelő pozitív számot hozzáadni az eredeti mátrix elemeihez. A játék döntése 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á

Az m×n játéknak általában nincs vizuális 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 DE A1,A2,..Ai,..Am stratégiákkal rendelkezik , játékos NÁL NÉL - 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 alkalmazásának valószínűségei,

Az optimális stratégia a következő követelményt elégíti ki. Ez biztosítja a játékost DEátlagos nyeremény nem kevesebb, mint a játék ára v, a játékos bármely stratégiájához NÁL NÉLés a játék árával megegyező nyeremény v, a játékos optimális stratégiájával NÁL NÉL. Az általánosság elvesztése nélkül beállítottuk v> 0; ez az összes elem elkészítésével érhető el . Ha a játékos DE vegyes stratégiát alkalmaz bármely tiszta stratégiai Bj-játékossal szemben NÁL NÉL, akkor megkapja átlagos fizetés , vagy a győzelem matematikai elvárása (azaz elemek j-Go A kifizeté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, így egy egyenlőtlenségrendszert 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 DE - maximalizálja garantált megtérülését, 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 , tehát a probléma a következőképpen fogalmazható meg: változó értékek meghatározása , mahogy kielégítse a lineáris korlátokat(*) és míg a lineáris függvény (2*) a minimumra fordult.

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 NÁL NÉL a garantált megtérülés 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 NÁL NÉL nem haladja meg a játék értékét, függetlenül attól, hogy milyen tiszta stratégiát használ a játékos DE.

Ha jelöljük (4*) , akkor egy egyenlőtlenségrendszert kapunk:

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

A játék a következő feladatra redukálódott.

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 feladat (5*), (6*) megoldása határozza meg az optimális stratégiát. Ugyanakkor a játék ára. (7*)

Miután kiterjesztett mátrixokat állítottunk össze az (1*), (2*) és (5*), (6*) feladatokhoz, megbizonyosodunk 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óan az egyes problémák optimális stratégiáinak meghatározásakor a kölcsönösen duális problémák közül az egyiket kell választani, amelynek megoldása kevésbé fáradságos, a másik probléma megoldását pedig dualitástételek segítségével kell megtalá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. A nyilvánvalóan veszteséges stratégiákat zárja ki a kifizetési mátrixból más stratégiákhoz képest. Ilyen stratégiák a játékos számára DE

Alatt művelet minden olyan eseményt értünk, amelyet egyetlen ötlet és irány egyesít egy meghatározott cél elérése érdekében.

Egy művelet mindig menedzselt esemény, pl. rajtunk múlik, hogy kiválasszuk azokat a paramétereket, amelyek a szervezés módját jellemzik.

Bármilyen, tőlünk függő paraméter-választás meg lesz hívva döntés.

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

Az operációkutatás fő célja az optimális megoldások előzetes mennyiségi indoklása. Az operatív kutatásnak nem célja a döntéshozatal teljes automatizálása. A döntést mindig az ember hozza meg. Az operációkutatás célja olyan kvantitatív adatok és ajánlások előállítása, amelyek megkönnyítik az ember döntéseit.

A fő feladattal együtt - optimális megoldások megalapozása, Az operációkutatás köre további feladatokat is magában foglal:

A műveletszervezés különböző lehetőségeinek összehasonlító értékelése,

A különböző paraméterek működésére gyakorolt ​​hatás értékelése,

A "szűk keresztmetszetek" vizsgálata, pl. elemek, amelyek megzavarása különösen erősen befolyásolja a művelet sikerességét stb.

Ezek a segédfeladatok különösen akkor fontosak, ha egy adott műveletet nem elszigetelten, hanem az egész szerves elemeként tekintünk. rendszerek tevékenységek. Az operációkutatás feladatainak „rendszerszemléletű” megközelítése megköveteli, hogy figyelembe vegyék egy sor tevékenység kölcsönös függőségét és feltételrendszerét, pl. a végső döntést ennek a műveletnek a rendszerben betöltött szerepének és helyének figyelembevételével hozza meg.

Alatt hatékonyság a működés alatt az előtte álló feladat végrehajtásához való alkalmazkodásának mértékét értjük.

Egy művelet hatékonyságának megítéléséhez és a különbözőképpen szervezett műveletek hatékonyságának összehasonlításához rendelkezni kell néhány numerikus értékelési kritérium vagy teljesítménymutató.

A műveletek sorrendje az operációkutatásban.

1. A vizsgálat céljának megfogalmazása és a problémafelvetés kidolgozása.

2. A kvantitatív módszerek bármely területen történő alkalmazásához mindig szükség van a jelenség matematikai modelljének felépítésére. Ez a modell az eredeti tulajdonságainak elemzése alapján épül fel.

3. A modell felépítése után eredményeket kapunk rajta

4. Az eredetire nézve értelmezik, és átviszik az eredetire.

5. Összehasonlítás segítségével a szimulációs eredményeket összevetjük az eredeti közvetlen vizsgálata során kapott eredményekkel.

Ha a modell segítségével kapott eredmények közel állnak az eredeti vizsgálata során kapott eredményekhez, akkor ezen tulajdonságok tekintetében a modell megfelelőnek tekinthető az eredetivel.

Az automatizált vezérlőrendszerek tervezése és üzemeltetése során gyakran felmerülnek a működésük mennyiségi és minőségi mintáinak elemzésével, optimális szerkezetének meghatározásával, stb. kapcsolatos feladatok.

A tárgyakon végzett közvetlen kísérletezés ezen problémák megoldása érdekében számos jelentős hátránnyal jár:

1. Az objektum megállapított működési módja sérül.

2. Egy teljes körű kísérletben lehetetlen elemezni az összes alternatív lehetőséget a rendszer felépítésére stb.

Ezeket a problémákat célszerű az objektumtól elkülönített, számítógépen megvalósított modellen megoldani.

Az információs rendszerek modellezésekor széles körben alkalmazzák a matematikai modelleket.

A matematikai modellezés módszere különböző objektumok tanulmányozásának módszere megfelelő matematikai leírás összeállításával és ennek alapján a vizsgált objektum jellemzőinek kiszámításával.

Szükséges egy matematikai modell felépítése. Formálisan tükrözi az eredeti működését, és leírja viselkedésének főbb mintáit. Ebben az esetben minden másodlagos, jelentéktelen tényezőt kizárunk a számításból.

A matematikai modellezés tárgya összetett rendszerek. A komplex rendszer nagyszámú információhoz kapcsolódó és kölcsönhatásban lévő elem meghatározott módon szervezett és célirányosan működő összessége, külső tényezők hatására.

A számítógépes rendszerek modellezésének 4 fő szakasza van:

A rendszer fogalmi modelljének felépítése és formalizálása;

A rendszermodell algoritmizálása és modellező program kidolgozása;

Előzetes szimulációs eredmények megszerzése és értelmezése;

A modell és a rendszer megfelelőségének ellenőrzése; modell beállítás

A rendszer működésének minőségi mutatóinak fő számítása a modellezés eredményei alapján, a modell megvalósítása.

3. előadás A szakértői értékelés módszerének alapfogalmai. Szakértői csoportok kialakítása. szavazási eljárások. Rangsorolás módszerei, páros összehasonlítás, értékelés relatív skálán.

1. A gazdaságban végzett műveletek vizsgálatának tárgya és céljai. A műveletkutatás elméleti alapfogalmai.

Az operációkutatás tárgya olyan 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ával kapcsolatos döntések mennyiségi alátámasztása

Optimálisnak azt a megoldást nevezzük, 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ás pedig szuboptimális lesz.

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

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

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

A paraméterek tőlünk függő határozott megválasztását megoldásnak nevezzük. A megoldásokat akkor nevezzük optimálisnak, ha valamilyen okból előnyben részesítik őket másokkal szemben.

Azokat a paramétereket, amelyek összessége megoldást alkot, a megoldás elemeinek nevezzük.

Az elfogadható megoldások halmaza olyan feltételeket tartalmaz, amelyek rögzítettek és nem sérthetők meg.

Teljesítménymutató - kvantitatív 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 - a hálózattervezés - gráfelméletre épül. Görögről lefordítva a gráf (grafpho - írom) pontrendszert jelöl, amelyek közül néhányat vonalak - ívek (vagy élek) kötnek össze. Ez a kölcsönható rendszerek topológiai (matematikai) modellje. A grafikonok segítségével nem csak hálózattervezési, hanem egyéb problémák megoldására is lehetőség nyílik. A hálózattervezési módszert egymáshoz kapcsolódó munkák komplexumá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 koordinálá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íthat.

A hálózattervezés és -menedzsment alapja a hálózati modell (SM), amely egy adott cél elérésének folyamatát tükröző, egymással összefüggő tevékenységek és események összességé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 tevékenység végrehajtásának eredményei. Nincs időhosszabbításuk.

Az út egy egymást követő munkalánc, amely összeköti a kezdeti és a végső csúcsot.

Egy útvonal időtartamát az azt alkotó munkák időtartamának összege határozza meg.

3. Hálózati diagram felépítése, megrendelése.

A hálózati modellt olyan modellként alkalmazzák, amely tükrözi a hálózattervezési és -menedzsment rendszerekben (SPU) az építési és telepítési folyamatok technológiai és szervezeti összefüggéseit.

A hálózati modell a folyamatok grafikus ábrázolása, amelynek megvalósítása egy vagy több cél eléréséhez vezet, jelezve a 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 munka és az 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, amelynek végrehajtása bizonyos eredmények eléréséhez vezet.

Az időráfordítást nem igénylő függőséget (fiktív munka) pontozott nyíl jelzi. A próbamunkát hálózati diagramon használják az események és tevékenységek közötti kapcsolatok bemutatására.

A hálózati ütemezésben az idő, a költség és a munka egyéb jellemzői kerülnek felhasználásra.

A munka időtartama - a munkavégzés ideje munkanapokban vagy más időegységekben, ugyanaz a hálózatban végzett összes munka esetében. A munka időtartama lehet egy bizonyos (determinisztikus), vagy az eloszlásának törvénye által meghatározott valószínűségi változó.

A munka költsége a végrehajtásához 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 a 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.

Az 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 egy szám tartozik, amelyet kódnak neveznek. 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 tevékenységük, kezdeti eseményeknek nevezzük; események, amelyeknek nincs utólagos - végleges.

1 A hálózat kiépítésének iránya eltérő jellegű lehet. Hálózati gráf építhető a kezdeti eseménytől a végső eseményig és a végső eseménytől a kezdetiig (kezdeti), valamint bármely eseménytől a kezdeti vagy végső eseményig.

2 Hálózatépítéskor a következő kérdéseket kell megoldani:

Milyen munkát (munkát) kell elvégezni e munka megkezdéséhez;

Milyen munkát kell végezni ezzel a munkával párhuzamosan;

3 A kezdeti hálózati ütemterv a hálózatot alkotó tevékenységek 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 mű lehet. Épületek, építmények építése során egymás után, párhuzamosan vagy egyidejűleg, hol sorosan, hol pedig párhuzamosan végezhetők munkák, melynek 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 tevékenységek korai és késői időpontjai a hálózati diagramban.

Egy hálózati diagramban több útvonal is lehet a kezdési és befejezési események között. A leghosszabb időtartamú utat kritikus útnak nevezzük. A kritikus út határozza meg a tevékenységek 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 a kritikus utat vastagított vagy dupla vonalak (nyilak) jelzik.

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

A munka korai megkezdése - az az időszak, amely előtt lehetetlen elkezdeni ezt a munkát az elfogadott technológiai sorrend megsértése nélkül. A kezdeményezéstől a munka megkezdéséig tartó leghosszabb út határozza meg.

A késői befejezés egy olyan munka legkésőbbi befejezési dátuma, amely nem növeli meg a munka teljes időtartamát. Az adott eseménytől az összes munka befejezéséig vezető legrövidebb út határozza meg.

A korai befejezés az a határidő, amely előtt a munka nem fejezhető be. Ez egyenlő a korai kezdéssel és a munka időtartamával.

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

Ha az 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.

A teljes (teljes) tartalék az a maximális idő, ameddig ennek a munkának a végrehajtása elhalasztható 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 – ami ugyanaz) különbsége határozza meg.

Privát (ingyenes) tartalék - ez a maximális idő, ameddig elhalaszthatja ennek a munkának a végrehajtását anélkül, hogy megváltoztatná a következő munka korai kezdését. Ez a tartalék csak akkor lehetséges, ha az esemény két vagy több tevékenységet (függőséget) tartalmaz, pl. két vagy több nyíl (folytonos vagy pontozott) mutat rá. Ekkor ezek közül csak az egyiknek lesz olyan korai befejezése, amely egybeesik a következő munka korai kezdésével, míg a többinél ezek eltérő értékek. Ez a különbözet ​​minden munkáná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. A racionális döntések meghozatalának, a legjobb opciók kiválasztásának, az optimális irányításnak a feladatait különböző profilú szakemberek végzik. A dinamikus programozás különleges helyet foglal el az optimalizálási módszerek között. 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, még nem körvonalazódott teljes mértékben az a problémakör, amelyre alkalmazható. 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 fontos szerepet játszik a dinamikus programozás berendezésében 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, amely megkülönbözteti a többi optimalizálási módszertől, a végeredmény formája. Az optimalitás elvének é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 szekvenciális kiírását. Ennek az az előnye, hogy a teljes folyamatra vonatkozó vezérlés kiszámításának feladata több egyszerűbb feladatra oszlik, amelyek a folyamat egyes szakaszaira vonatkoznak.

A módszer fő hátránya Bellman szavaival élve a "dimenzionalitás átka" – összetettsége katasztrofálisan növekszik a problémadimenziós növekedésével.

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

Elmondható, hogy az optimális vezérlés dinamikus programozási módszerrel történő megalkotásának folyamata két szakaszra oszlik: előzetes és végső szakaszra. Az előzetes szakaszban minden lépésnél a rendszer állapotától függően kerül meghatározásra az SOC (amelyet az előző lépések eredményeként értek el), és a feltételesen optimális nyereség az összes többi lépésben, ettől kezdve, szintén függ a rendszer állapotától. állapot. 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. Az optimalizálás két szakasza közül az első összehasonlíthatatlanul fontosabb és időigényesebb. Az első szakasz befejezése után a második szakasz végrehajtása 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ás problémájának 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 feladatokat az erőforrások (anyagi és/vagy pénzügyi) korlátai jellemzik. Egyenlőtlenségek rendszereként írják őket, néha egyenlőségként.

Az elfogadható árintervallumok (vagy értékesítési mennyiségek) előrejelzése szempontjából egy általánosított, nem paraméteres módszer keretében 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 általánosított, nem paramé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 árak 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 egy lineáris programozási probléma geometriai értelmezésére épül, és főként a kétdimenziós tér és csak néhány háromdimenziós tér problémájának megoldására használatos, mivel meglehetősen nehéz olyan megoldási poliédert konstruálni, amely úgy van kialakítva. félterek metszéspontjának eredménye. A háromnál nagyobb méretű tér feladata grafikusan egyáltalán nem ábrázolható.

Legyen a lineáris programozási probléma adott 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 fix értékeire egy egyenes egyenlete: C1x1 + C2x2 = állandó. Szerkesszük meg a (2.2) kényszerrendszer megoldásainak sokszögét és a lineáris függvény (2.1) grafikonját Z = 0 esetén (2.1. ábra). Ekkor a lineáris programozás adott problémája a következőképpen értelmezhető. Keresse meg a megoldási sokszög azon pontját, ahol a C1x1 + C2x2 = const egyenes a támaszvonal és a Z függvény eléri a minimumot.

A Z = C1x1 + C2x2 értékek az N = (C1, C2) vektor irányában nőnek, ezért 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 lesz referencia a megoldások sokszögéhez képest (az A és C pontban), a minimális érték pedig az A pontban. Az A pont koordinátáit (x1, x2) úgy találjuk meg, hogy megoldjuk a az AB és AE egyenesek egyenletrendszere.

Ha a dönté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 utal rá. Ebben az esetben a lineáris függvény a megoldási sokszögön felül és lent is korlátlan (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 lehet felülről korlátos és alulról határtalan (2.2. ábra, a), alulról korlátos és felülről határtalan (2.2. ábra, b), vagy alulról is korlátos, ill. felülről (2.2. ábra, c).

9. Simplex módszer.

A szimplex módszer a fő a lineáris programozásban. A feladat megoldása a poliéder feltételek 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 célfüggvény értékét a feladat megoldásánál maximumra növelve, a feladat megoldásakor pedig minimálisra csökkentve. Í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 lettek 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. Végtelen sok különböző támogatási megoldás létezik a kényszerrendszerhez. Ezért a probléma kanonikus formában történő megoldását úgy lehetett keresni, hogy felsoroljuk a referenciamegoldásokat, és kiválasztjuk közülük azt, amelyiknél F értéke a legnagyobb. De egyrészt az összes 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 felsorolás aligha lehetséges. A szimplex módszer a referenciamegoldások irányított felsorolásának egy bizonyos eljárása. Valamelyik korábban talált referenciamegoldás alapján a szimplex módszer egy bizonyos algoritmusával olyan ú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. Alaptervek meghatározásának módszerei.

Egyazon terméknek m kiindulási pontja ("beszállító") és n fogyasztási pontja ("fogyasztója") van. Minden elemhez meghatározzák:

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

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

cij - egy termelési egység Ai pontból – az i-edik szállítóból – a Bj pontba – a j-edik fogyasztó – történő szállításának költsége.

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, amely minden fogyasztó igényét maradéktalanul kielégíti, miközben elegendő beszállítói készlet és a teljes szállítási költség minimális lenne.

A szállítási terv alatt a forgalom nagyságát, i.e. az i-edik szállítótól a j-edik fogyasztóig szállítandó áru mennyisége. A probléma matematikai modelljének felépítéséhez m n хij, i= 1,…, n, j= 1, …, m változót kell beírni, mindegyik хij változó az Ai ponttól Bj pontig tartó forgalom nagyságát jelöli. Az X = (xij) változók halmaza lesz az a terv, amelyet a problémafelvetés alapján meg kell találni.

Ez a feltétele a zárt és nyitott szállítási feladatok (ZTZ) megoldásának.

Nyilvánvalóan az 1. probléma megoldhatóságá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 feladatok (ZTZ) 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 az élelmiszerigé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. Az adatok szabványos táblázat formájában történő bemutatása és az erőforrások elfogadható allokációjának keresése. Az erőforrások elfogadható elosztása olyan, hogy a rendeltetési helyeken minden keresletet kielégít, és a teljes termékkínálatot eltávolítja a termelési pontokról.

2. szakasz. A kapott erőforrás-allokáció optimálisságának ellenőrzése

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

4. szakasz. A kapott erőforrás-allokáció optimálisságának újraellenőrzése.

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

12. Készletgazdálkodási modellek.

Annak ellenére, hogy minden készletgazdálkodási modellt úgy terveztek, hogy két alapvető kérdést (mikor és mennyit) válaszoljon meg, jelentős számú modell létezik, amelyek különféle matematikai eszközöket használnak az építéshez.

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 általánosabb gradáció szempontjából ma már csak ö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 kereslet lehet stacionárius, amikor a kereslet valószínűségi sűrűsége nem változik az időben, és nem stacionárius, ahol a valószínűségi sűrűség függvény idővel változik. A fenti besorolást az ábra szemlélteti.

A legegyszerűbb a termék 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 megbízások teljesítésének feltételei. A beszerzési időszak időtartama lehet állandó vagy véletlenszerű változó;

utánpótlási folyamat. Lehet azonnali vagy időben elosztva;

a forgótőkére, a tárhelyre stb. vonatkozó korlátozások jelenléte.

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

A sorban állási rendszerek (QS) olyan speciális típusú rendszerek, amelyek azonos típusú 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 pénzügyi és gazdasági KPSZ-ekre; A szférában különböző típusú bankok (kereskedelmi, befektetési, jelzálog-, innovatív, megtakarítási), biztosító szervezetek, állami részvénytársaságok, társaságok, cégek, egyesületek, szövetkezetek, adófelügyelőségek, könyvvizsgálói szolgáltatások, különféle kommunikációs rendszerek (beleértve a telefonközpontokat is) ), be- és kirakodó komplexumok (kikötők, teherpályaudvarok), benzinkutak, a szolgáltató szektor különböző vállalkozásai és szervezetei (ü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 gyártóhelyek, a gyártósorok, a különféle katonai rendszerek, különösen a légvédelmi vagy rakétavédelmi rendszerek.

Minden QS a struktúrájában tartalmaz bizonyos számú szolgáltatási 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, kezelők, fodrászok, eladók), kommunikációs vonalak, autók, daruk, javítócsapatok, vasutak, benzinkutak stb.

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

Mindegyik QS egy bizonyos alkalmazásfolyamat (követelmény) kiszolgálására (végrehajtására) készült, amelyek többnyire nem rendszeresen, hanem véletlenszerűen érkeznek a rendszer bemenetére. A kiszolgálási kérések ebben az esetben is nem állandó, előre ismert, hanem véletlenszerű ideig tartanak, 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. Az alkalmazások áramlásának és kiszolgálási idejének véletlenszerű jellege a QS egyenetlen munkaterheléséhez vezet: máskor a nem kiszolgált kérések halmozódhatnak fel a QS bemenetén, ami a QS túlterheléséhez vezet. nem lesznek kérések a szabad csatornákkal rendelkező QS bemenetén, ami a QS alulterheléséhez vezet, azaz pl. tétlenül járni a csatornáit. A QS bejáratánál felhalmozódó alkalmazások vagy „bekerülnek” a sorba, vagy a további sorban állás lehetetlensége miatt kiszolgálatlanul hagyják a QS-t.

Teljesítménymutatók a „QS – fogyasztó” páros működéséhez, ahol a fogyasztó alatt az alkalmazások teljes halmazát vagy azok forrásának egy részét (például a QS által időegységre vetített átlagos bevételt stb.) értjük. Ez a mutatócsoport olyan esetekben hasznos, amikor a szolgáltatási igényekből származó bevételek és a szolgáltatási költségek egy része azonos mértékegységben történik. Ezek a mutatók általában meglehetősen specifikusak, és a QS, a szolgáltatási kérések és a szolgáltatási fegyelem sajátosságai 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-nál, 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.

Abban az esetben, ha az S rendszer állapotainak száma véges, és minden állapotból (egy vagy több lépésszámra) át lehet lépni egy másik állapotba, akkor az állapotok határvalószínűségei léteznek, és nem is függenek a rendszer kezdeti állapotáról.

ábrán. állapotok és átmenetek grafikonját mutatja, amelyek kielégítik a feltételt: bármely állapotból a rendszer előbb-utóbb bármely más állapotba kerülhet. A feltétel nem teljesül, ha a grafikonon a 4-3 nyíl iránya megfordul.

Tegyük fel, hogy a megadott feltétel teljesül, és ezért léteznek a határvaló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 adni: Következésképpen egy bizonyos korlátozó stacionárius mód jön létre a rendszerben: hagyja, hogy a rendszer véletlenszerűen változtassa meg saját állapotát, de ezeknek az állapotoknak a valószínűsége nem függ időben, és mindegyiket valamilyen állandó valószínűséggel hajtják végre, ami az átlagos relatív idő, amelyet a rendszer ebben az állapotban tölt.

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

Markov-folyamat alatt a halál és szaporodás folytonos idővel olyan s.p.-t értünk, amely csak nem negatív egész értékeket vehet fel; változás ebben a folyamatban bármikor bekövetkezhet t, miközben bármikor vagy eggyel nőhet, vagy változatlan maradhat.

A λi(t) szorzófolyamok az X(t) függvény növekedéséhez vezető Poisson-folyamatok. Ennek megfelelően a μi(t) haláláramok, amelyek az X(t) függvény csökkenéséhez vezetnek.

Állítsuk össze a Kolmogorov-egyenleteket a grafikon szerint:

Ha egy szál véges számú állapottal:

A Kolmogorov-egyenletrendszer a halál és szaporodás folyamatára korlátozott számú állapottal a következőképpen alakul:

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

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

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

A sorban állás elméletének keretében vizsgált problémák közül a legegyszerűbb egy hibás vagy veszteséges 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őben történik, melynek eloszlása ​​az exponenciális törvény szerint valósul meg a következő paraméterrel:

17. Sorozati rendszerek várakozással.

Egy olyan kérés, amely akkor érkezik, amikor a csatorna foglalt, sorba kerül, és a szolgáltatásra vár.

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

A QS állapotokat a rendszerben lévő kérések (kiszolgált és várakozó szolgáltatás) száma szerint számozzuk:

— 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 a sorban;

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

18. Döntéshozatali módszerek konfliktusos körülmények között. Mátrix játékok. Tiszta és vegyes stratégiai játékok.

A mátrixjáték két játékos nulla összegű végjá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, az oszlop a 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ó, amely az alkalmazott stratégiákra vonatkozik).

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

A két játékos nulla összegű mátrix játék a következő absztrakt kétjátékos játékként tekinthető.

Az első játékosnak m stratégiája van i = 1,2,...,m, a másodiknak n stratégiája j = 1,2,...,n. Minden egyes stratégiapárhoz (i, j) van hozzárendelve egy aij szám, amely kifejezi az 1. játékos kifizetését 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.

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

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

Meghatározás. Egy játékos vegyes stratégiája a tiszta stratégiák alkalmazásá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 az 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 alkalmazzák, akkor az összes többi tiszta stratégiát nem alkalmazzák. 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 választásátó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 mentén egyetlen A1A2 szakaszt félreteszünk (5.1. ábra). A szakasz minden pontja valamilyen vegyes U = (u1, u2) stratégiához kapcsolódik. Ezen túlmenően az U közbülső ponttól a szegmens jobb végéhez mért 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 pontokban visszaállítjuk a merőlegeseket, és elhalasztjuk a rajtuk lévő játékosok kifizetését. Az első merőlegesen (amely egybeesik az OY tengellyel) az A játékos kifizetését mutatjuk az A1 stratégia használatakor, 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, a B2 stratégiával pedig 5. Az OY tengelyen a 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 kifizetés).

A B1 és B"1, B2 és B"2 pontokat összekötve két egyenest kapunk, amelyektől az OX tengelyig mért távolság határozza meg az átlagos kifizetést a megfelelő stratégiák tetszőleges kombinációja esetén.

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 vonallánchoz 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 árával 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. Az ilyen egyenleteket a két ponton áthaladó egyenes egyenletének képletével állíthatja össze:

Állítsuk össze a feladatunkhoz tartozó egyenesek egyenleteit.

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.

Tehát U = (2/5, 3/5), v = 22/5.

20. Bimatrix 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 adják meg külön a megfelelő játékosra (minden mátrixban a sor az 1. játékos stratégiájának felel meg, az oszlop megfelel a 2. játékos stratégiájának, az első mátrixban a sor és az oszlop metszéspontjában az 1. játékos, a második mátrixban a 2. játékos nyereménye van.)

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

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 elvei és kritériumai.

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

a célok bizonytalansága;

a környezetről és 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ágok típusát a matematikai modell egyik vagy másik eleme szempontjából vizsgáljuk. Így például a célok bizonytalansága tükröződik a probléma megfogalmazásában, akár az egyes kritériumok, akár a hasznos 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 állítás meglehetősen feltételes, mint minden osztályozás. Csak azért mutatjuk be, hogy kiemeljük a döntési folyamat során szem előtt tartandó bizonytalanságok néhány további jellemzőjét.

Az tény, hogy a bizonytalanságok fenti osztályozása mellett figyelembe kell venni azok típusát (vagy "fajtá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árgyai - valószínűségi változók (vagy véletlenszerű függvények, események 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 bizonytalanság (E.S. Wentzel szerint - "rossz bizonytalanság"), amelyben nincsenek feltételezések a sztochasztikus stabilitásról. 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 az eredményei és a valós feltételek közötti eltérés veszélyét. Az eltérés kockázatát kockázati együtthatók segítségével formalizálják.

A kockázati 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;

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