Konvex halmazok és tulajdonságaik. Az LPP tulajdonságainak tanulmányozásához szigorúan meg kell határozni a konvex halmazt. Korábban konvex halmazként olyan halmazt definiáltak, amely bármely két pontjával együtt tartalmazza az őket összekötő szakaszt.
A szakasz fogalmának általánosítása több pontra a konvex lineáris kombinációjuk.
Az X pontot hívják konvex lineáris kombináció pontokat, ha a feltételek teljesülnek
A pontkészlet az konvex, ha két pontjával együtt tartalmazza azok tetszőleges konvex, lineáris kombinációját.
A konvex poliéder ábrázolására vonatkozó következő tétel bizonyítható.
Tétel 1.1. A konvex n-politóp a sarokpontjainak konvex lineáris kombinációja.
Az 1.1. Tételből az következik, hogy egy konvex poliédert a sarokpontjai vagy csúcsai generálnak: egy szakaszt két pont, egy háromszög három, egy tetraéder négy pontot stb. Ugyanakkor egy konvex poliéder tartományt, mivel korlátlan halmaz, nem határozzák meg egyértelműen a sarokpontjai: egyetlen pontja sem ábrázolható sarokpontok konvex lineáris kombinációjaként.
A lineáris programozási probléma tulajdonságai. Korábban a lineáris programozási probléma különféle formáit vizsgálták, és megmutatták, hogy bármely lineáris programozási probléma ábrázolható általános vagy kanonikus problémaként.
A lineáris programozási probléma tulajdonságainak és megoldási módszereinek alátámasztására a kanonikus probléma további két írástípusát célszerű figyelembe venni.
Mátrix jelölés:
Itt VAL VEL- sormátrix, A- rendszermátrix, NS- mátrix-változóoszlop, V- ingyenes tagok mátrixoszlopa:
Vektoros jelölés:
ahol a vektorok az ismeretlenek együtthatók oszlopainak felelnek meg.
A következő tételt fentebb megfogalmaztuk, de általános formában nem igazoltuk.
Tétel 1.2. A lineáris programozási probléma kényszerrendszerének minden lehetséges megoldásának halmaza konvex.
Bizonyíték: Legyen - az LPP két megengedett megoldása mátrix formában megadva. Aztán és . Tekintsünk megoldások konvex lineáris kombinációját, pl.
és mutassuk meg, hogy az (1.3) rendszerben is elfogadható megoldás. Valóban
azaz megoldás x kielégíti az (1.3) rendszert. De azóta NS> 0, azaz a megoldás kielégíti a nem negativitás feltételét.
Tehát bebizonyosodott, hogy a lineáris programozási probléma összes megengedett megoldásának halmaza konvex, pontosabban egy konvex poliédert vagy egy konvex poliéder tartományt képvisel, amelyet a továbbiakban egy taggal fogunk nevezni. megoldások poliédere.
Arra a kérdésre, hogy a megoldások politópjának melyik pontján lehetséges egy lineáris programozási probléma optimális megoldása, a következő alaptétel adja meg a választ.
Tétel 1.3. Ha a lineáris programozási feladatnak van optimális megoldása, akkor a lineáris függvény a megoldási politóp egyik sarokpontjában veszi fel a maximális értékét. Ha egy lineáris függvény egynél több sarokpontban veszi fel a maximális értékét, akkor bármely olyan pontban veszi fel, amely e pontok konvex lineáris kombinációja.
Bizonyíték: Feltételezzük, hogy a megoldási politóp korlátos. Jelöljük a sarokpontjait , és az optimális megoldás megvan X *... Azután F (X *)³ F (X) minden pontra NS megoldások poliédere. Ha X * Ha egy sarokpont, akkor a tétel első része bizonyítva van.
Tegyünk úgy, mintha X * nem sarokpont, akkor az 1.1. Tétel szerint X * a megoldási poliéder sarokpontjainak konvex lineáris kombinációjaként ábrázolható, azaz.
Mivel F (X) Ha egy lineáris függvény, azt kapjuk
Ebben a bővítésben az értékek közül a maximális értéket választjuk. Hagyja, hogy megfeleljen a sarokpontnak X k(1 font k£ R); jelöljük azzal M, azok. . Cserélje le az (1.5) kifejezés minden értékét ezzel a maximális értékkel M. Azután
Feltételezéssel NS* Az optimális megoldás tehát egyrészt, de másrészt bebizonyosodott, hogy
F (X *)£ M, tehát hol X k- sarokpont. Tehát van egy sarokpont X k amelyben a lineáris függvény felveszi a maximális értékét.
A tétel második részének bizonyításához tegyük fel, hogy a célfüggvény a maximális értékét egynél több sarokpontban veszi fel, például a pontokban , ahol , azután
Legyen NS- ezen sarokpontok konvex lineáris kombinációja, azaz.
Ebben az esetben, tekintettel arra, hogy a függvény F (X)- lineáris, kapjuk
azok. lineáris függvény F tetszőleges pontban veszi fel a maximális értéket NS amely sarokpontok konvex lineáris kombinációja.
Megjegyzés. Az a követelmény, hogy a megoldások politópja korlátos legyen a tételben, elengedhetetlen, mivel egy korlátlan poliéder tartomány esetén, amint azt az 1.1. Tétel is megjegyeztük, egy ilyen tartomány nem minden pontja ábrázolható a sarokpontjainak konvex lineáris kombinációjával. .
A bizonyított tétel alapvető, mivel a lineáris programozási problémák alapvető megoldását jelzi. Valójában e tétel szerint ahelyett, hogy a megvalósítható megoldások végtelen halmazát tanulmányoznánk, hogy megtaláljuk közöttük a kívánt optimális megoldást, csak a megoldások poliéderének véges számú sarokpontját kell megvizsgálni.
A következő tétel a sarokpontok megtalálásának analitikai módszerére vonatkozik.
Tétel 1.4. Egy lineáris programozási feladat minden megengedett alapmegoldása megfelel a megoldási politóp egy sarokpontjának, és fordítva, a megoldási poliéder minden sarokpontja egy megengedett alapmegoldásnak felel meg.
Bizonyíték: Legyen egy elfogadható alapmegoldás az LPP-kényszerrendszerhez (1.4), amelyben az első T a komponens a fő változók és a többi n - t komponens - az alapmegoldásban nullával egyenlő kisebb változók (ha ez nem így van, akkor a megfelelő változók átszámozhatók). Mutassuk meg NS
Tegyük fel az ellenkezőjét, pl. mit NS nem sarokpont. Aztán a lényeg NSábrázolható egy olyan szegmens belső pontjával, amely két különböző szakaszt köt össze, amelyek nem esnek egybe X, pontokat
más szóval pontok konvex lineáris kombinációja megoldások poliédere, i.e.
ahol (ezt feltételezzük, ellenkező esetben a lényeg NS ponttal egybeesik NS 1 ill NS 2).
Az (1.6) vektoregyenlőséget koordináta alakban írjuk fel:
Mivel minden változó és együttható nem negatív, akkor az utóbbiból p-t egyenlőségekből következik, hogy i.e. a döntésekben NS 1 , NS 2 és NS egyenletrendszer (1.4) az értékeket n - t komponensei ebben az esetben nullával egyenlőek. Ezeket a komponenseket kisebb változók értékeinek tekinthetjük. De a mellékváltozók értékei egyértelműen meghatározzák a főváltozók értékeit, ezért
Szóval minden NS komponens az oldatokban NS 1 , NS 2 és NS egybeesnek, és ezért a pontok NS 1 és NS 2 összevonása, ami ellentmond a feltételezésnek. Ennélfogva, x A megoldási poliéder sarokpontja.
Bizonyítsuk be a fordított állítást. Legyen a megoldások politópjának sarokpontja és az első T a koordináták pozitívak. Mutassuk meg NS- elfogadható alapmegoldás. nem sarokpont, ami ellentmond a feltételnek. Ezért a feltevésünk hibás, i.e. vektorok lineárisan függetlenek és NS Az (1.4) probléma elfogadható alapmegoldása.
Egy fontos következmény közvetlenül következik az 1.3. és 1.4. tételből: ha egy lineáris programozási feladatnak van optimális megoldása, akkor az legalább az egyik megengedett alapmegoldással egybeesik.
Így, egy lineáris programozási probléma lineáris függvényének optimumát véges számú megengedhető alapmegoldása között kell keresni.
A lineáris modellek optimalizálása MS Excelben történik szimplex módszer- a lineáris programozási probléma támogató megoldásainak céltudatos felsorolása. A szimplex módszer algoritmusa leredukálódik egy konvex poliéder felépítésére többdimenziós térben, majd a csúcsokon való iterációra, hogy megtaláljuk a szélsőértéket. objektív funkció.Hatékony gyógymódok lineáris programozás egész és nemlineáris programozás alapját képezik a bonyolultabb optimalizálási problémákhoz. Ezek a módszerek azonban hosszabb számítási időt vesznek igénybe.
A következő előadásokon a tipikus optimalizálási problémák megoldására és a vezetői döntések meghozatalára az MS Excel "Megoldás keresése" bővítménye segítségével részletesen elemzik a példákat. Az eszköz által legjobban végrehajtható feladatok három fő tulajdonsággal rendelkeznek:
- egyetlen, a rendszer egyéb paramétereivel funkcionálisan összefüggő cél van, amelyet optimalizálni kell (meg kell találni a maximumát, minimumát vagy egy bizonyos számértékét);
- vannak korlátozások, amelyek általában egyenlőtlenségek formájában fejeződnek ki (például a felhasznált nyersanyagok mennyisége nem haladhatja meg a raktárban lévő alapanyag készletet, vagy a gép napi üzemideje nem haladhatja meg a 24 órát mínusz a szolgáltatás);
- van egy sor bemeneti változó érték, amely befolyásolja az optimalizált értékeket és megszorításokat.
A feladat paramétereit a következő határértékek korlátozzák:
- ismeretlenek száma - 200;
- az ismeretlenekre vonatkozó képletmegkötések száma - 100;
- az ismeretlenekre vonatkozó korlátozó feltételek száma 400.
Az optimális megoldások megtalálásának algoritmusa több szakaszból áll:
- előkészítő munka;
- a megoldás hibakeresése;
- a megoldás elemzése.
A közgazdasági és matematikai modellezés MS Excel segítségével történő megoldásához szükséges előkészítő munkák sorrendjét az 1.6. ábra blokkdiagramja mutatja.
Rizs. 1.6.
Az előkészítő munkaterv öt pontja közül csak az ötödik pont formalizált. A többi munka kreativitást igényel – és azt különböző emberek különböző módon végezhetik. Röviden fejtsük ki a terv pontjainak megfogalmazásának lényegét.
A probléma felállításakor ismertek a célegyütthatók és a normalizált együtthatók. Az előző példában a célfüggvényt alkotó együtthatók a típus normalizált, polconkénti nyereségének értékei voltak ( 
) és egy polc ( típusú 
). A normalizált együtthatók az egyes típusok polconkénti anyagfelhasználásának és gépi időjének arányai voltak. A mátrix így nézett ki:
Ezenkívül az erőforrások értékei mindig ismertek. Az előző példában heti deszkakészletről és a gépidő használatának lehetőségéről volt szó: 
, 
... A feladatokban gyakran korlátozni kell a változók értékeit. Ezért meg kell határozni a változási terület alsó és felső határát.
Így a "Megoldás keresése" optimalizáló program párbeszédpanelében a következő célalgoritmust kell megadnunk:
A célfüggvény egyenlő a változók kívánt értékeinek vektorának az objektív együtthatók vektorával való szorzatával
A változók keresett értékeinek vektorának normalizált együtthatói nem haladhatják meg az erőforrások adott vektorának értékét
A változó értékeinek a rendszer kezdeti elemeinek számának meghatározott határain belül kell lenniük
A rendszer kezdeti elemeinek száma
A megadott típusú erőforrások száma
A megoldás hibakeresése akkor szükséges, ha a program negatív eredményről ad ki üzenetet (1.7. ábra):
Rizs. 1.7.
- ha nem születik megvalósítható megoldás, akkor javítsa ki a kiindulási adatok modelljét;
- ha nem kapta meg optimális megoldás, majd további korlátozásokat vezet be.
A program problémái optimális megoldás csak egy valós probléma modellezésére szolgál, nem magának a probléma megoldásának. A modell felépítése során a valós helyzetre vonatkozóan különféle egyszerűsítő feltételezéseket fogalmaztak meg. Ez lehetővé tette a folyamat formalizálását, megközelítőleg a rendszer paraméterei és a cél közötti valós mennyiségi összefüggéseket tükrözve. És ha a valós paraméterek eltérnek a modellben szereplőktől, hogyan változik a döntés? Ennek kiderítésére a vezetői döntés meghozatala előtt modelldöntést elemeznek.
Elemzés optimális megoldás, a programba épített, a gazdasági folyamatok matematikai modellezésének utolsó szakasza. Lehetővé teszi a modell folyamatra való alkalmasságának alaposabb ellenőrzését, valamint az optimális megoldás megbízhatóságát. Adatvezérelt optimális megoldásés a „Megoldás keresése” részben kiadott jelentések. De nem zárja ki vagy helyettesíti a terv hagyományos, gazdasági szempontból történő elemzését a vezetői döntés meghozatala előtt.
A gazdasági elemzésnek a következő céljai vannak:
- a lehetséges következmények meghatározása a rendszer egészében és elemeiben a modellparaméter megváltoztatásakor;
- az optimális terv stabilitásának értékelése a probléma egyes paramétereinek változásaival szemben: ha nem ellenáll a legtöbb paraméter változásának, akkor a megvalósítás és a számított optimum elérésének garanciája csökken;
- változatszámítások elvégzése és új tervváltozatok beszerzése anélkül, hogy a probléma kiigazításokkal az eredeti alapról visszakerülne.
A lehetséges elemzési módszereket az 1.8. ábra diagramja mutatja.
Az optimális megoldás kézhezvétele után a kapott jelentések alapján elemzik. Stabilitáselemzés- a modell egyes paramétereiben bekövetkezett változások hatásának vizsgálata az optimális megoldás mutatóira. Limit elemzés- az optimális terv elfogadható változásainak elemzése, amelyben a terv optimális marad.
Tekintettel a gazdaságosság felelősségére vezetői döntést, a vezetőnek meg kell győződnie arról, hogy a kapott optimális terv az egyetlen helyes. Ehhez a következő kérdésekre kell választ kapni a modell alapján:
- "mi van ha…"
- "mi kell ahhoz, hogy..."
Az első kérdés megválaszolására szolgáló elemzést hívják változatelemzés; elemzést a második kérdés megválaszolásához hívják testreszabott megoldások.
A változatelemzés a következő típusú:
- Paraméteres- elemzés, amely egy probléma megoldásából áll egy bizonyos paraméter különböző értékeire.
- Szerkezeti elemzés- amikor az optimalizálási probléma megoldását a kényszerek eltérő szerkezetével keresik.
- Több szempontú elemzés- Ez egy megoldás a problémára a különböző célfüggvényeknél.
- Elemzés feltételes bemeneti adatokkal- amikor a probléma megoldásához felhasznált kiindulási adatok további feltételek betartásától függenek.
Az elemzést követően az eredményeket grafikus formában kell bemutatni, és a konkrét gazdasági helyzet figyelembevételével döntési javaslatokat tartalmazó jelentést kell készíteni.
Meghatározás... A kényszerrendszer bármely megoldását az LPP elfogadható megoldásának nevezzük.
Meghatározás... Optimális megoldásnak nevezzük azt a megvalósítható megoldást, amelyben a célfüggvény eléri maximális vagy minimális értékét.
E definíciók alapján az LP probléma a következőképpen fogalmazható meg: a kényszerrendszer megoldását jelentő konvex tartomány összes pontja közül válasszunk olyat, amelynek koordinátái minimalizálják (maximalizálják) a lineáris függvényt. F = val vel 1 x + val vel 2 y.
Vegye figyelembe, hogy a változók x, y az LPP-ben általában nem negatív értékeket kell venni ( x≥ 0, y≥ 0), tehát a régió a koordinátasík I. negyedében található.
Tekintsünk egy lineáris függvényt F = val vel 1 x + val vel 2 yés rögzítse néhány értékét F... Legyen pl. F= 0, azaz val vel 1 x + val vel 2 y= 0. Ennek az egyenletnek a grafikonja a (0; 0) koordináták origóján áthaladó egyenes lesz (ábra).
Rajz
Ennek a fix értéknek a megváltoztatásakor F = d, egyenes val vel 1 x+ val vel 2 y = d párhuzamosan fog mozogni, és „nyomja” a teljes síkot. Legyen D- sokszög - a kényszerrendszer megoldására szolgáló terület. Amikor megváltozik d egyenes val vel 1 x + val vel 2 y = d, bizonyos értéken d = d 1 eléri a sokszöget D, nevezzük ezt a pontot A"Belépési pont", majd a sokszöget elhaladva valamilyen értéknél d = d 2 lesz vele az utolsó közös pont V, hívjuk V"Kilépési pont".
Nyilvánvalóan a legkisebb és legnagyobb értékének célfüggvénye F=val vel 1 x + val vel 2 y eléri a belépési pontokat Aés "kilépés" V.
Figyelembe véve, hogy a célfüggvény optimális értéket vesz fel a megvalósítható megoldások halmazán a régió csúcsaiban D, az alábbi terv javasolható az LPP megoldására:
- a korlátozási rendszer megoldási területének kiépítése;
- építsünk egy egyenest a célfüggvénynek megfelelően, és ennek az egyenesnek a párhuzamos átvitelével keressük meg a „belépési” vagy „kilépési” pontot (a célfüggvény minimalizálásának vagy maximalizálásának követelményétől függően);
- határozza meg ennek a pontnak a koordinátáit, számítsa ki bennük a célfüggvény értékét.
Az LPP grafikus megoldása során két olyan eset lehetséges, amelyek külön tárgyalást igényelnek.
1. eset
6. ábra
Ha egyenesen mozog val vel 1 x + val vel 2 y= d A "belépés" vagy a "kilépés" (mint a képen) a sokszög oldalán történik. Ez akkor történik meg, ha a sokszög oldalai párhuzamosak egy egyenessel. val vel 1 NS+ val vel 2 nál nél = d .
Ebben az esetben a "kilépés" ("belépés") pontja számtalan, nevezetesen a szakasz bármely pontja AB... Ez azt jelenti, hogy a célfüggvény nem egy pontban veszi fel a maximális (minimális) értéket, hanem a sokszög megfelelő oldalán lévő összes pontban. D.
2. eset
Tekintsük azt az esetet, amikor a megengedett értékek tartománya korlátlan.
Korlátlan terület esetén a célfüggvény megadható úgy, hogy a hozzá tartozó egyenesnek ne legyen „kilépési” (vagy „belépési”) pontja. Ekkor a függvény maximális értékét (minimumot) soha nem érjük el – azt mondják, hogy a függvény nincs korlátozva. 
Rajz
Meg kell találni a célfüggvény maximális értékét F = 4x + 6y→ max, korlátozási rendszerrel
Szerkesszük meg a megvalósítható megoldások tartományát, pl. grafikusan megoldjuk az egyenlőtlenségek rendszerét. Ehhez megszerkesztjük az egyes egyeneseket, és meghatározzuk az egyenlőtlenségek által adott félsíkokat.
x + y = 18
|
x |
12 |
9 |
|
y |
6 |
9 |
0,5x + y = 12
|
x |
12 |
18 |
|
y |
6 |
3 |
x= 12 - párhuzamos a tengellyel OY ;
y= 9 - párhuzamos a tengellyel ÖKÖR ;
x= 0 - tengely OY ;
y = 0 - tengely ÖKÖR;
x OY;
y≥ 0 - félsík a tengely felett ÖKÖR;
y≤ 9 - félsík alatt y = 9;
x ≤ 12 - félsík balra x = 12;
0,5x + yx + y = 12;
x + y x + y = 18.
Rajz
Mindezen félsíkok metszéspontja nyilvánvalóan az ötszög OAVSD, pontokban lévő csúcsokkal O(0; 0), A(0; 9), V(6; 9), VAL VEL(12; 6), D(12; 0). Ez az ötszög alkotja a probléma megvalósítható megoldásainak tartományát.
F = 4x + 6y→ max.
|
x |
3 |
0 |
|
y |
–2 |
0 |
F = 0: 4x + 6y x+ 6y VAL VEL(12; 6). Benne van F = 4x + 6y
Ezért azért x = 12, y= 6 funkció F F= 4 ∙ 12 + 6 ∙ 6 = 84, egyenlő: 84. A (12; 6) koordinátájú pont kielégíti a kényszerrendszer minden egyenlőtlenségét, és a benne lévő célfüggvény értéke optimális F* = 84 (az optimális értéket "*" jelöli).
A probléma megoldódott. Tehát 12 I-es típusú és 6 II-es típusú terméket kell előállítani, miközben a nyereség 84 ezer rubel lesz.
A grafikus módszerrel olyan problémákat oldanak meg, amelyeknek csak két változója volt a korlátozási rendszerben. Ez a módszer háromváltozós egyenlőtlenségi rendszerekre is alkalmazható. Geometriailag más lesz a helyzet, az egyenesek szerepét a síkok játsszák a háromdimenziós térben, a három változós egyenlőtlenség megoldása pedig a sík egyik oldalán elhelyezkedő féltér lesz. A régiók szerepét a poliéderek töltik be, amelyek a félterek metszéspontjai.
2. példa. A bányában két varrás alakul ki. A vágás eredménye az első rétegben a1%; a másodikon - a2%. A hosszfal maximális termelése az első réteg esetében B1 ezer tonna évente, a második réteg esetében - B2 ezer tonna évente. A munkatechnológia szerint a második rétegből származó termelés nem haladhatja meg az első rétegből származó termelést. A bánya termelése a bányában nem haladhatja meg az évi 1 ezer tonnát. A két réteg éves összterhelése legalább évi C2 ezer tonna legyen. Hozzon létre egy matematikai modellt, és állítsa össze a megengedett terhelési értékeket az első és a második réteghez évente.
3. példa. Az üzletben 2 féle üdítőital kapható: kóla és limonádé. Egy doboz kólás bevétele 5 cent, míg egy doboz limonádéból 7 cent. Egy bolt átlagosan legfeljebb 500 dobozt ad el mindkét italból naponta. Annak ellenére, hogy a kólát egy ismert márka gyártja, a vásárlók a limonádét részesítik előnyben, mert sokkal olcsóbb. Becslések szerint a kóla és a limonádé eladása legalább 2:1 legyen, és az üzletben köztudottan naponta legalább 100 doboz kólát adnak el. Hány doboz minden italból legyen a boltban a nap elején a bevétel maximalizálása érdekében?
4. számú példa. Oldja meg a lineáris programozási feladatot megközelítőleg grafikusan a célfüggvény érték pontos értékének és max (min) utólagos kiszámításával.
5. számú példa. Egy utazási irodának legfeljebb háromtonnás és legfeljebb öttonnás buszra van szüksége. Az első márkájú buszok eladási ára 20 000 USD, a második márka 40 000 USD. Az utazási iroda legfeljebb 1 dollárt fordíthat buszok vásárlására. Az egyes márkákból hány autóbuszt érdemes külön-külön megvásárolni, hogy a teljes (összes) teherbírásuk maximális legyen. Oldja meg a problémát grafikusan.
6. számú példa. Grafikus módszerrel keresse meg a táblázatban megadott feladathoz az optimális gyártási tervet.
7. számú példa. Oldja meg a lineáris programozási feladatot grafikus módszerrel, a feladat kényszerrendszerét a Jordan-Gauss transzformációknak alávetve. A problémamegszorítások rendszere a következő:
a 11 x 1 + a 12 x 2 + a 13 x 3 + a 14 x 4 + a 15 x 5 = b 1
a 21 x 1 + a 22 x 2 + a 23 x 3 + a 24 x 4 + a 25 x 5 = b 2
a 31 x 1 + a 32 x 2 + a 33 x 3 + a 34 x 4 + a 35 x 5 = b 3
Irányelvek... A Jordan-Gauss transzformációk végrehajthatók ezzel a szolgáltatással vagy az SLAE-k tanulmányozásával.
8. számú példa. A vállalkozás kétféle, A és B terméket gyárt, amelyek előállításához háromféle alapanyagot használnak fel. Az A termék egységének előállításához az a1, a2, a3 kg-ot, a B termékegységhez pedig a b1, b2, b3 kg-ot kell elkölteni. A termelést minden típusú alapanyaggal Р1, Р2, Р3 kg mennyiségben biztosítjuk. Az A termék egységének költsége C1 rubel, a B termék egysége pedig C2 rubel. Az A és B termékek gyártására tervet kell készíteni, amely biztosítja a késztermék maximális költségét.
2. példa. Meg kell találni a célfüggvény maximális értékét F = 4x + 6y→ max, korlátozási rendszerrel:
Szerkesszük meg a megvalósítható megoldások tartományát, pl. grafikusan megoldjuk az egyenlőtlenségek rendszerét. Ehhez válassza ki a korlátozások számát 4-gyel (1. ábra). 
1. kép
Ezután kitöltjük a változók és maguknak a megszorításoknak az együtthatóit (2. ábra). 
2. kép 
3. ábra
x= 12 - párhuzamos a tengellyel OY;
y= 9 - párhuzamos a tengellyel ÖKÖR;
x> = 0 - tengely OY
y= 0 - tengely ÖKÖR;
x≥ 0 - félsík a tengelytől jobbra OY;
y≥0 - félsík a tengely felett ÖKÖR;
y≤ 9 - félsík alatt y = 9;
x≤ 12 - félsík balra x = 12;
0,5x + y≤ 12 - egyenes alatti félsík 0,5 x + y = 12;
x + y≤ 18 - félsík az egyenes alatt x + y = 18.
Mindezen félsíkok metszéspontja az ötszög ABCDE, pontokban lévő csúcsokkal A(0; 0), B(0;9), C(6; 9), D(12;6), E(12; 0). Ez az ötszög alkotja a probléma megvalósítható megoldásainak tartományát. 
Tekintsük a probléma célfüggvényét F = 4x + 6y→ max.
|
x |
3 |
0 |
|
y |
–2 |
0 |
A függvény értékének megfelelő egyenest szerkesztünk F = 0: 4x + 6y= 0. Ezt az egyenest párhuzamosan mozgatjuk. Az egész vonalcsaládból 4 x + 6y= const az utolsó csúcs, amelyen az egyenes áthalad, amikor túllépünk a sokszög határán, lesz a csúcs VAL VEL(12; 6). Benne van F = 4x + 6y eléri maximális értékét. 
Ezért azért x = 12, y= 6 funkció F eléri maximális értékét F= 4 ∙ 12 + 6 ∙ 6 = 84, egyenlő: 84. A (12; 6) koordinátájú pont kielégíti a kényszerrendszer minden egyenlőtlenségét, és a benne lévő célfüggvény értéke optimális F* = 84.
Teszt az "Operations Research" tudományágban
(a helyes válaszok az elsők)
1. Megjelent az "operation research" kifejezés...
második világháború idején
a XX. század 50-es éveiben
a XX. század 60-as éveiben
a XX. század 70-es éveiben
század 90-es éveiben
század elején a XXI
2. Operációkutatási eszközök (a legmegfelelőbb opció kiválasztása) ...
tudományos módszerek összessége a szervezeti rendszerek hatékony irányításának problémáinak megoldására
bizonyos műveletek végrehajtása érdekében hozott intézkedések összessége
az elgondolt terv megvalósításának módszerei
az erőforrások elosztásának tudományos módszerei a termelés megszervezésében
3. Rendezze meg azokat a lépéseket, amelyeken minden operatív kutatás jellemzően keresztül megy:
a probléma megfogalmazása
a vizsgált objektum (folyamat) értelmes (verbális) modelljének felépítése
matematikai modell felépítése
a felépített matematikai modell alapján megfogalmazott feladatok megoldása
a kapott eredmények ellenőrzése a vizsgált rendszer jellegének megfelelőségéhez
a kapott megoldás gyakorlati megvalósítása
4. Az operációkutatásban egy műveletet értünk ...
bármely esemény (cselekvési rendszer), amelyet egyetlen fogalom egyesít és egy cél elérésére irányul
bármilyen ellenőrizhetetlen esemény
a fogyasztási cikkek előállítását biztosító technikai intézkedések összessége
5. A megoldást optimálisnak nevezzük, ...
ha ilyen vagy olyan okból előnyösebb
ha racionális
ha a hatóságokkal megállapodnak
ha a közgyűlés jóváhagyja
6. Matematikai programozás ...
extrém problémák tanulmányozásával és megoldási módszerek kidolgozásával foglalkozik
a számítógépes programok létrehozásának folyamata matematikusok irányításával
matematikai feladatokat old meg számítógépen
7. A lineáris programozás feladata ...
egy lineáris függvény legnagyobb (legkisebb) értékének megtalálása lineáris kényszerek jelenlétében
lineáris program készítése kiválasztott programozási nyelven a probléma megoldására
egy adott probléma megoldására szolgáló lineáris algoritmus leírása
8. Másodfokú programozási feladatban ...
a célfüggvény másodfokú
az elfogadható megoldások területe egy négyzet
a kényszerek másodfokú függvényeket tartalmaznak
9. Egészszámú programozási feladatokban...
az ismeretlenek csak egész számokat vehetnek fel
a célfüggvénynek szükségszerűen egész számot kell felvennie, az ismeretlenek pedig tetszőlegesek lehetnek
a célfüggvény egy numerikus állandó
10. Paraméteres programozási feladatokban ...
A célfüggvény és/vagy a kényszerrendszer paraméter(eke)t tartalmaz
a megengedhető megoldások területe paralelogramma vagy paralelepipedon
a változók száma csak páros lehet
11. Dinamikus programozási problémákban ...
a megoldás keresésének folyamata többlépcsős
racionalizálni kell a dinamittermelést
optimalizálni szeretné a hangszórók használatát
12. A következő lineáris programozási probléma merül fel:
F(NS 1, NS 2) = 5NS 1 + 6NS 2→ max
0.2NS 1 + 0.3NS 2 ≤ 1.8,
0.2NS 1 + 0.1NS 2 ≤ 1.2,
0.3NS 1 + 0.3NS 2 ≤ 2.4,
NS 1 ≥ 0, NS 2 ≥ 0.
Válasszon egy feladatot, amely egyenértékű ezzel a feladattal.
F(NS 1, NS 2)= 5NS 1 + 6NS 2 → max,
2NS 1 + 3NS 2 ≤ 18,
2NS 1 + NS 2 ≤ 12,
NS 1 + NS 2 ≤ 8,
NS 1 ≥ 0,
NS 2 ≥ 0.
F(NS 1, NS 2)= 6NS 1 + 5NS 2 → perc,
2NS 1 + 3NS 2 ≤ 18,
2NS 1 + NS 2 ≤ 12,
NS 1 + NS 2 ≤ 8,
NS 1 ≥ 0,
NS 2 ≥ 0.
F(NS 1, NS 2)= 50NS 1 + 60NS 2 → max,
2NS 1 + 3NS 2 ≤ 18,
2NS 1 + NS 2 ≤ 12,
NS 1 + NS 2 ≤ 8,
NS 1 ≥ 0,
NS 2 ≥ 0.
F(NS 1, NS 2)= 5NS 12 + 6NS 22 → max,
2NS 1 + 3NS 2 ≤ 18,
2NS 1 + NS 2 ≤ 12,
3NS 1 + NS 2 ≤ 2.4,
NS 1 ≥ 0,
NS 2 ≥ 0.
13. Egy lineáris programozási probléma célfüggvénye a következő függvény lehet:
F=12x1+20x2-3 0x3→min
F= →min
F=
→max
F=→max.
14. A lineáris programozási probléma kényszerrendszere a következő rendszer lehet:
15. A szimplex módszer a következő:
elemző módszer a lineáris programozás fő problémájának megoldására
módszer egy lineáris programozási probléma megvalósítható megoldási tartományának megtalálására;
grafikus módszer a lineáris programozás fő problémájának megoldására;
módszer egy általános lineáris programozási probléma kanonikus formára redukálására.
16. A lineáris programozás feladata:
egy lineáris függvény legnagyobb vagy legkisebb értékének megtalálása lineáris kényszerek jelenlétében
lineáris algoritmus kidolgozása és megvalósítása számítógépen
lineáris egyenletrendszer felállítása és megoldása
adott korlátozásrendszerrel leírt folyamat fejlődésének lineáris pályájának keresése.
17. A lineáris programozási probléma megvalósítható megoldásainak tartománya nem tudígy néz ki:
18. Egy lineáris programozási probléma célfüggvénye a következő függvény lehet:
F=12x1+20x2-3 0x3→min
F= →min
F=→max
F=→max.
19. A lineáris programozási probléma kényszerrendszere a következő rendszer lehet:
20. A lineáris programozási probléma megvalósítható megoldásainak tartománya a következő:
F(NS 1, NS 2)= 3NS 1 + 5NS 2 egyenlő...
21. A lineáris programozási probléma megvalósítható megoldásainak tartománya a következő alakú:
Ezután a függvény maximális értéke F(NS 1, NS 2)= 5NS 1 + 3NS 2 egyenlő...
22. A lineáris programozási probléma megvalósítható megoldásainak tartománya a következő alakú:
Ezután a függvény maximális értéke F(NS 1, NS 2)= 2NS 1 - 2NS 2 egyenlő...
23. A lineáris programozási probléma megvalósítható megoldásainak tartománya a következő alakú:
F(NS 1, NS 2)= 2NS 1 - 2NS 2 egyenlő...
24. A nemlineáris programozás problémájának megvalósítható megoldási köre a következőképpen alakul:
Ezután a függvény maximális értéke F(NS 1, NS 2)= NS 2 – NS 12 egyenlő...
25. A célfüggvény maximális értéke F(NS 1, NS 2)= 5NS 1 + 2NS 2 korlátozásokkal
NS 1 + NS 2 ≤ 6,
NS 1 ≤ 4,
NS 1 ≥ 0, NS 2 ≥ 0, egyenlő...
26. Egy kisvállalkozás kétféle terméket gyárt. Egy A típusú termék gyártásához 2 kg nyersanyagot, egy B típusú termék gyártásához 1 kg nyersanyagot fogyasztanak el. Összesen 60 kg alapanyag van. A legnagyobb bevételt biztosító gyártási tervet kell készíteni, ha egy A típusú termék eladási költsége 3 c. E., B típusú 1 év. Vagyis az A típusú termékekből legfeljebb 25, a B típusú termékekből legfeljebb 30 darabot kell készíteni.
Ez a feladat...
lineáris programozási probléma
a dinamikus programozási módszerrel megoldott probléma
hálózattervezés feladata.
27. Egy kisvállalkozás kétféle terméket gyárt. Egy A típusú termék gyártásához 2 kg nyersanyagot, egy B típusú termék gyártásához 1 kg nyersanyagot fogyasztanak el. Összesen 60 kg alapanyag van. A legnagyobb bevételt biztosító gyártási tervet kell készíteni, ha egy A típusú termék eladási költsége 3 c. E., B típusú 1 év. Vagyis az A típusú termékekből legfeljebb 25, a B típusú termékekből legfeljebb 30 darabot kell készíteni.
Ennek a feladatnak a célfüggvénye a függvény...
F(x1, x2)=3x1+x2→max
F(x1, x2)=25x1+30x2→max
F(x1, x2)=2x1+x2→max
F(x1, x2)=60 -2x1 - x2→min
28. Egy kisvállalkozás kétféle terméket gyárt. Egy A típusú termék gyártásához 2 kg nyersanyagot, egy B típusú termék gyártásához 1 kg nyersanyagot fogyasztanak el. Összesen 60 kg alapanyag van. A legnagyobb bevételt biztosító gyártási tervet kell készíteni, ha egy A típusú termék eladási költsége 3 c. E., B típusú 1 év. Vagyis az A típusú termékekből legfeljebb 25, a B típusú termékekből legfeljebb 30 darabot kell készíteni.
A feladat érvényes terve a következő:
X =(20, 20)
X =(25, 15)
X =(20, 25)
X =(30, 10)
29. Két A1 és A2 pontban 60, illetve 160 áruegység található. Minden árut a B1, B2, B3 pontokra kell szállítani 80, 70, illetve 70 egységnyi mennyiségben. A tarifamátrix a következő: Tervezze meg a szállítást úgy, hogy a költségek minimálisak legyenek.
Ez a feladat...
szállítási feladat
nemlineáris programozási probléma
utazó eladó probléma
kiosztási feladat
30. Két A1 és A2 pontban 60, illetve 160 áruegység található. Minden árut a B1, B2, B3 pontokra kell szállítani 80, 70, illetve 70 egységnyi mennyiségben. A tarifamátrix a következő: Tervezze meg a szállítást úgy, hogy a költségek minimálisak legyenek
Ennek a feladatnak az alapterve a következő:
;
31. Két A1 és A2 pontban 60, illetve 160 áruegység található. Minden árut a B1, B2, B3 pontokra kell szállítani 80, 70, illetve 70 egységnyi mennyiségben. A tarifamátrix a következő: Tervezze meg a szállítást úgy, hogy a költségek minimálisak legyenek.
Ennek a feladatnak a célfüggvénye a következő függvény:
F=4x11+6x12+ 8x13+5x21+8x22+7x23→min
F= →min
F=60x1+160x2 + 80x3+70x4+705 →max
F=60x1+160x2- 80x3- 70x4- 705 →min
32. Két A1 és A2 pontban 60, illetve 160 áruegység található. Minden árut a B1, B2, B3 pontokra kell szállítani 80, 70, illetve 70 egységnyi mennyiségben. A tarifamátrix a következő: Tervezze meg a szállítást úgy, hogy a költségek minimálisak legyenek.
A feladat optimális terve a következő:
;
.
;
;
33. Közlekedési probléma
zárva lesz, ha...
34. Közlekedési probléma
egy…
nyisd ki
zárva
oldhatatlan
35. Közlekedési probléma
egy…
zárva
nyisd ki
oldhatatlan
36. Az alábbi szállítási feladat megoldása
be kell lépned...
fiktív fogyasztó
fiktív szállító;
érvényes tarifa
37. Az alábbi szállítási feladat megoldása
be kell lépned...
fiktív szállító;
fiktív fogyasztó
érvényes tarifa
effektív kamatláb.
38. Ezen szállítási feladatok közül
zárva vannak...
39. A közlekedési probléma kezdeti alapterve elkészíthető ...
a fenti módszerek mindegyikével
Északnyugati sarok módszer
minimális tarifa módszerrel
kettős preferencia módszer
Vogel-közelítési módszerrel
40. Ha a lineáris programozási feladat célfüggvényét maximumra állítjuk, akkor ... a duális feladat célfüggvényét minimumra állítjuk
a duális problémában nincs objektív függvény
a kettős problémának nincs megoldása
a kettős problémának végtelen sok megoldása van
41. Adott egy lineáris programozási feladat:
F(NS 1, NS 2)= 2NS 1 + 7NS 2 → max,
2NS 1 + 3NS 2 ≤ 14,
NS 1 + NS 2 ≤ 8,
NS 1 ≥ 0, NS 2 ≥ 0.
A következő kettős lesz ehhez a feladathoz...
F*(y1, y2) = 14y1 + 8y2 → min,
3 év 1 + y2 ³ 7,
y 1 ≥ 0, y2 ≥ 0.
F*(y1, y2) = 2y1 + 7y2 → min,
2y1 + 3y2 ³ 14,
y 1 + y2 ³ 8,
y 1 0 GBP, y2 0 GBP.
F*(y1, y2) = 2y1 + 7y2 → min,
3 y 1 + y2 ³ 7,
y 1 0 GBP, y2 0 GBP.
F*(y1, y2) = 14y1 + 8y2 → min,
y 1 + y2 ³ 7,
y 1 ≥ 0, y2 ≥ 0.
42. Ha a kettős probléma egyikének van egy optimális terve, akkor...
a másiknak pedig van egy optimális terve
a másiknak nincs optimális terve
a másiknak nincs megvalósítható megoldása
43. Ha a kettős problémapár egyikének van optimális terve, akkor...
a másiknak pedig van egy optimális terve és az optimális tervükhöz tartozó célfüggvények értékei megegyeznek egymással
a másiknak pedig van egy optimális terve, de az optimális tervükhöz tartozó célfüggvények értékei nem egyenlőek egymással
egy másik problémának lehet, hogy nincs optimális terve, de vannak megvalósítható megoldásai
44. Ha a kettős feladatpárok egyikének célfüggvénye nem korlátos (a maximális feladatnál - felülről, a minimális feladatnál - alulról), akkor
egy másik feladatnak nincsenek érvényes tervei
egy másik feladatnak vannak megvalósítható tervei, de nincs optimális terve
egy másik feladat célfüggvénye sem korlátozott
45. A nemlineáris programozás egyes problémáinak megoldásánál a ...
Lagrange-szorzó módszer
Gauss módszer
Vogel-közelítési módszer
Gomori módszer
46. A nemlineáris programozás problémája be van állítva
F(NS 1, NS 2)= NS 12 + NS 22 → max,
NS 1 + NS 2 =6,
NS 1 ≥ 0, NS 2 ≥ 0.
F(NS 1, NS 2) …
nem elérhető (+ ¥)
47. A nemlineáris programozás problémája be van állítva
F(NS 1, NS 2)= NS 12 + NS 22 → mban ben,
NS 1 + NS 2 =6,
NS 1 ≥ 0, NS 2 ≥ 0.
F(NS 1, NS 2) …
48. A nemlineáris programozás problémája be van állítva
F(NS 1, NS 2)= NS 12 + NS 22 → max,
NS 1 + NS 2 =6,
NS 1, NS 2 - bármilyen.
A célfüggvény legmagasabb értéke F(NS 1, NS 2) …
nem elérhető (+ ¥)
49. A nemlineáris programozás problémája be van állítva
F(NS 1, NS 2)= NS 12 + NS 22 → mban ben,
NS 1 + NS 2 =6,
NS 1, NS 2 - bármilyen.
A célfüggvény legkisebb értéke F(NS 1, NS 2) …
nem elérhető (- ¥)
50. A nemlineáris programozás problémájának megvalósítható megoldási köre a következőképpen alakul:
Ezután a függvény maximális értéke F(NS 1, NS 2)= NS 12 +NS 22 egyenlő...
51. A nemlineáris programozás problémájának megvalósítható megoldási köre a következőképpen alakul:
Ezután a függvény minimális értéke F(NS 1, NS 2)= NS 12 +NS 22 egyenlő...
52. A közlekedési probléma megoldására alkalmazható ...
potenciális módszer
Lagrange-szorzó módszer
Gauss módszer
dezorientációs módszer
53. Az általános lineáris programozási probléma kényszerrendszerében ...
54. A standard (szimmetrikus) lineáris programozási feladat kényszerrendszerében ...
csak egyenlőtlenségek lehetnek jelen
egyenletek és egyenlőtlenségek egyaránt jelen lehetnek
csak egyenletek lehetnek jelen
55. A kanonikus (alap) lineáris programozási probléma kényszerrendszerében ...
csak egyenletek lehetnek jelen (feltéve, hogy a változók nemnegatívak)
csak egyenlőtlenségek lehetnek jelen (feltéve, hogy a változók nemnegatívak)
egyenletek és egyenlőtlenségek egyaránt jelen lehetnek (feltéve, hogy a változók nemnegatívak)
56. A lineáris programozás problémája
F(NS 1, NS 2)= 2NS 1 + 7NS 2 → max,
2NS 1 + 3NS 2 ≤ 14,
NS 1 + NS 2 ≤ 8,
NS 1 ≥ 0, NS 2 ≥ 0.
rögzítve...
szabványos (szimmetrikus) forma
kanonikus (alap)forma
verbális forma
57. Feladat rögzítése
F(NS 1, NS 2)= 2NS 1 + 7NS 2 → max,
2NS 1 + 3NS 2 ≤ 14,
NS 1 + NS 2 ≤ 8,
NS 1 ≥ 0, NS 2 ≥ 0.
kanonikus formában...
58. Feladat rögzítésére
F(NS 1, NS 2)= 2NS 1 + 7NS 2 → max,
2NS 1 + 3NS 2 ≤ 14,
NS 1 + NS 2 ≤ 8,
NS 1 + 4NS 2 ≥ 10,
NS 1 ≥ 0, NS 2 ≥ 0.
kanonikus formában...
három további nem negatív változót kell bevezetni
két további nem negatív változót kell bevezetni
négy további nemnegatív változót kell bevezetni
59. Feladat rögzítése
F(NS 1, NS 2)= 2NS 1 + 7NS 2 → max,
2NS 1 + 3NS 2 = 14,
NS 1 + NS 2 ≤ 8,
NS 1 + 4NS 2 ≥ 10,
NS 1 ≥ 0, NS 2 ≥ 0.
kanonikus formában...
két további nem negatív változót kell bevezetni
három további nem negatív változót kell bevezetni
négy további nemnegatív változót kell bevezetni
további öt nem negatív változót kell bevezetni
60. Egészszámú programozási feladatok megoldásánál használható...
Gomori módszer
Lagrange-szorzó módszer
Gauss módszer
Vogel-közelítési módszer
61. A dinamikus programozás módszerével történő problémák megoldásának középpontjában a ...
Occam borotvája
a "fogat fogért, szemet szemért" elv.
Heisenberg-elv
62. Azt a helyzetet, amelyben olyan felek érintettek, akiknek az érdekei részben vagy teljesen ellentétesek, úgy hívják...
(konfliktus, konfliktus, konfliktus, konfliktus)
63. Az a tényleges vagy formális konfliktus, amelyben legalább két résztvevő (játékos) van, akik mindegyike saját céljainak elérésére törekszik, ...
(játék, játék)
64. Az egyes játékosok megengedett akcióit, amelyek egy bizonyos cél elérésére irányulnak, úgy hívják, hogy ...
(játékszabályok, játékszabályok)
65. A játék eredményeinek mennyiségi értékelését ...
(fizetéssel, fizetéssel, fizetéssel)
66. Ha csak két fél (két személy) vesz részt a játékban, akkor a játék neve ...
(páros, páros, páros, páros)
67. Ha egy páros játékban a kifizetések összege nullával egyenlő, vagyis az egyik játékos vesztesége egyenlő a másik nyereségével, akkor a játékot játéknak nevezzük...
(nulla összeg)
68. A játékos választásának egyértelmű leírása minden olyan lehetséges szituációban, amelyben személyes lépést kell tennie, ..
(játékos stratégia, játékos stratégia, stratégia, stratégia)
69. Ha a játék többszöri megismétlésével a stratégia a lehető legnagyobb átlagos nyereséget (a lehető legkisebb átlagos veszteséget) biztosítja a játékos számára, akkor az ilyen stratégiát ...
(optimális, optimális, optimális stratégia, optimális stratégia)
70. Legyen a egy nulla összegű páros játék alacsony ára, b pedig magas ára. Akkor igaz az állítás...
71. Legyen a egy nulla összegű páros játék alacsony ára, b pedig magas ára. Ha a = b = v, akkor a v számot ...
a játék árán
egyensúlyi pont
optimális stratégia
vegyes stratégia
72. Legyen a egy nulla összegű páros játék alacsony ára, b pedig magas ára. Ha a = b, akkor a játék neve ...
nyeregpontos játék
feloldhatatlan konfliktus
szabályok nélküli játék
73. Egy vektort, amelynek minden komponense a megfelelő tiszta stratégia játékos általi használatának relatív gyakoriságát mutatja, ...
vegyes stratégia
irányvektor
normál vektor
gradiens
74. A mátrixjáték fizetési mátrix által adott alacsonyabb ára egyenlő ...
Több alsó ár
megegyezik az alsó árral
nem létezik
81. Kifizető mátrix által adott mátrixjáték, ...
nyereghegye van
nincs nyereghegy
nincs párosítva
82. A játék ára, amelyet a kifizetési mátrix ad meg, ...
83. Kifizető mátrix által adott mátrixjáték ...
párosítva van
nyereghegye van
nincs párosítva
84. A nulla összegű páros játék, amelyet a kifizetési mátrixa ad meg, lecsökkenthető ...
lineáris programozási probléma
nemlineáris programozási probléma
integer lineáris programozási probléma
klasszikus optimalizálási probléma
85. A fizetési mátrix által megadott mátrixjáték alacsonyabb ára...
Több alsó ár
megegyezik az alsó árral
nem létezik
92. Kifizető mátrix által adott mátrixjáték ...
nincs nyereghegy
nyereghegye van
nincs párosítva
93. A játék fizetési mátrix által megadott ára ...
94. Ha az eseményfolyamban az események előre meghatározott és szigorúan meghatározott időközönként követik egymást, akkor az ilyen folyamot ...
szabályos
szervezett
95. Ha annak a valószínűsége, hogy egy időintervallumra tetszőleges számú esemény esik, csak ennek az intervallumnak a hosszától függ, és nem attól függ, milyen messze van ez az intervallum az idő kezdetétől, akkor a megfelelő eseményfolyamot nevezzük:
helyhez kötött
áramlás következmények nélkül
a legegyszerűbb
Poisson
96. Ha az egyik tetszőlegesen választott időintervallumra eső események száma nem függ egy másik, szintén tetszőlegesen választott időintervallumra eső események számától, feltéve, hogy ezek az intervallumok nem metszik egymást, akkor a megfelelő eseményfolyamot ún. ...
áramlás következmények nélkül
szabályos
jelzésértékű
Normál
97. Ha annak a valószínűsége, hogy két vagy több esemény egyszerre ér egy nagyon rövid időintervallumot, elhanyagolható ahhoz képest, hogy csak egy eseményt, akkor a megfelelő eseményfolyamot ...
rendes
rendkívüli
Normál
Poisson
98. Ha az események áramlása egyszerre rendelkezik a stacionaritás, a hétköznapiság és a következmények hiánya tulajdonságaival, akkor azt nevezzük:
legegyszerűbb (Poisson)
Normál
99. Az egycsatornás rendszer meghibásodásokkal az autómosó napi szervize. Jelentkezés - egy autó, amely abban a pillanatban érkezett, amikor az állás foglalt - szolgáltatásmegtagadást kap. Autó áramlási sebesség λ = 1,0 (kocsi óránként). Az átlagos szervizidő 1,8 óra. Az autóáramlás és a szervizáramlás a legegyszerűbb. Ezután állandósult állapotban a relatív áteresztőképesség q egyenlő...
100. Az egycsatornás rendszer meghibásodásokkal napi autómosó szerviz. Jelentkezés - egy autó, amely abban a pillanatban érkezett, amikor az állás foglalt - szolgáltatásmegtagadást kap. Autó áramlási sebesség λ = 1,0 (kocsi óránként). Az átlagos szervizidő 1,8 óra. Az autóáramlás és a szervizáramlás a legegyszerűbb. Ekkor állandósult állapotban azoknak az autóknak a százalékos aránya, amelyek szolgáltatásmegtagadást kapnak...
A lineáris programozási probléma (LPP) általános megfogalmazása. Példák az LPP-re
A lineáris programozás a matematikának egy olyan ága, amely olyan szélsőséges problémák megoldásának módszereit vizsgálja, amelyeket a változók közötti lineáris kapcsolat és az optimalitás lineáris kritériuma jellemez. Néhány szó a lineáris programozás kifejezésről. Megfelelő megértést igényel. Ebben az esetben a programozás természetesen nem számítógépes programok írása. A programozást itt tervezésként, tervek kialakításaként, cselekvési program kidolgozásaként kell értelmezni. A lineáris programozás matematikai problémái közé tartozik a sajátos termelési és gazdasági helyzetek vizsgálata, amelyeket ilyen vagy olyan formában a korlátozott erőforrások optimális felhasználásának problémájaként értelmeznek. A lineáris programozási módszerekkel megoldható feladatok köre meglehetősen széles. Ez például:
- - az erőforrások optimális felhasználásának problémája a termeléstervezésben;
- - a keverékek problémája (a termékek összetételének tervezése);
- - a különféle típusú termékek optimális kombinációjának megtalálásának problémája a raktárban való tároláshoz (készletkezelés vagy "hátizsák probléma");
- - szállítási feladatok (a vállalkozás helyének elemzése, árumozgás). A lineáris programozás a matematikai programozás legfejlettebb és legszélesebb körben használt ága (ráadásul ide tartozik: egészszámú, dinamikus, nemlineáris, parametrikus programozás). Ennek oka a következők:
- - számos gazdasági probléma matematikai modelljei lineárisak a keresett változókhoz képest;
- - ez a fajta probléma jelenleg a legtöbbet tanulmányozott. Számára speciális módszereket dolgoztak ki, amelyek segítségével ezeket a feladatokat megoldják, és a megfelelő számítógépes programokat;
- - a lineáris programozás számos problémája megoldása után széleskörű alkalmazásra talált;
- - egyes problémák, amelyek az eredeti megfogalmazásban nem lineárisak, számos további megszorítás és feltevés után lineárissá válhatnak, vagy olyan formára redukálhatók, hogy lineáris programozási módszerekkel megoldhatók. Bármely lineáris programozási probléma közgazdasági és matematikai modellje tartalmazza: egy célfüggvényt, melynek optimális értékét (maximumát vagy minimumát) meg kell találni; korlátozások lineáris egyenletrendszer vagy egyenlőtlenség formájában; a változók nem-negativitásának követelménye. Általánosságban a modell a következőképpen van felírva:
- - objektív funkció:
C1x1 + c2x2 + ... + cnxn> max (min); - korlátozások:
a11x1 + a12x2 + ... + a1nxn (? =?) b1,
a21x1 + a22x2 + ... + a2nxn (? =?) b2
am1x1 + am2x2 + ... + amnxn (? =?) bm;
Nem negativitás követelmény:
Ebben az esetben az aij, bi, cj () konstansokat kapunk. A probléma a (2.1) függvény optimális értékének megtalálása a (2.2) és (2.3) megszorítások függvényében. A kényszerrendszert (2.2) a probléma funkcionális megszorításainak, a (2.3) megszorításokat közvetlennek nevezzük. A (2.2) és (2.3) feltételnek eleget tevő vektort a lineáris programozási probléma megvalósítható megoldásának (tervének) nevezzük. Optimálisnak nevezzük azt a kialakítást, amelyben a (2.1) függvény eléri a maximális (minimális) értékét.
Az alábbiakban néhány tipikus, lineáris programozási módszerekkel megoldott problémára mutatunk be példákat. Az ilyen feladatoknak valódi gazdasági tartalma van. Most csak az LPP szempontjából fogalmazzuk meg őket, és az alábbiakban megvizsgáljuk az ilyen problémák megoldásának módszereit.
1. Az erőforrások optimális felhasználásának problémája a termeléstervezésben. Az osztály feladatainak általános jelentése a következő. A vállalkozás n különböző terméket gyárt. Előállításukhoz m különböző típusú erőforrás szükséges (nyersanyag, anyag, munkaidő stb.). A források korlátozottak, tartalékaik a tervezési időszakban rendre b1, b2, ..., bm konvencionális egységek. Ismeretesek az aij technológiai együtthatók is, amelyek megmutatják, hogy az i-edik erőforrásból hány egységre van szükség a j-edik típusú termék egységnyi előállításához (). A vállalkozás által a j-edik típusú termék értékesítéséből származó nyereség cj. A tervezési időszakban az aij, bi és cj értéke állandó marad. Olyan termelési tervet kell készíteni, amelynek megvalósítása során a vállalkozás nyeresége a legnagyobb lenne. Az alábbiakban egy egyszerű példa látható ennek az osztálynak a feladatára.
A cég jégkorongütők és sakkkészletek gyártására specializálódott. Minden egyesület 2 dollár nyereséget termel a cégnek, és 4 dollárt minden sakkkészletért. Négy órát vesz igénybe egy klub elkészítése az A telephelyen és két óra a B helyszínen. Egy sakkkészletet az A helyszínen hat órából, a B telephelyen hat órából és a C telephelyen egy órát készítenek. Az A telephelyen rendelkezésre álló gyártási kapacitás 120 Nm. - napi óra, B szakasz - 72 n-óra és C szakasz - 10 n-óra. Hány klubot és sakkkészletet kell naponta gyártania egy vállalatnak a profit maximalizálása érdekében?
Ennek az osztálynak a problémáinak feltételeit gyakran táblázatos formában mutatják be (lásd a 2.1. táblázatot).
Ezzel a feltétellel egy lineáris programozási problémát fogalmazunk meg. Jelöljük: x1 - naponta gyártott jégkorongütők darabszáma, x2 - naponta gyártott sakkkészletek száma. ZLP megfogalmazás:
4x1 + 6x2? 120,
Hangsúlyozzuk, hogy a funkcionális kényszerek rendszerében minden egyenlőtlenség ebben az esetben egy vagy másik termelőhelynek felel meg, nevezetesen: az első az A telephelynek, a második a B telephelynek, a harmadik pedig a C telephelynek.
A változók rendszere a vetésterületek szerkezetének optimalizálásának problémájában a vetésforgó figyelembevételével
