Konvexné množiny a ich vlastnosti. Aby bolo možné študovať vlastnosti LPP, je potrebné presne definovať konvexnú množinu. Predtým bola konvexná množina definovaná ako množina, ktorá spolu s ľubovoľnými dvoma bodmi obsahuje segment, ktorý ich spája.

Zovšeobecnením pojmu úsečka pre niekoľko bodov je ich konvexná lineárna kombinácia.

Bod X sa nazýva konvexná lineárna kombinácia bodov, ak sú splnené podmienky

Súbor bodov je konvexný, ak spolu s ktorýmkoľvek z jeho dvoch bodov obsahuje ich ľubovoľnú konvexnú, lineárnu kombináciu.

Dá sa dokázať nasledujúca veta o zobrazení konvexného mnohostenu.

Veta 1.1. Konvexný n-polytop je konvexná lineárna kombinácia jeho rohových bodov.

Z vety 1.1 vyplýva, že konvexný mnohosten je generovaný svojimi rohovými bodmi alebo vrcholmi: úsečka dvoma bodmi, trojuholník tromi, štvorsten štyrmi bodmi atď. Zároveň konvexná polyedrická oblasť, ktorá je neohraničenou množinou, nie je jednoznačne určená svojimi rohovými bodmi: žiadny jej bod nemôže byť reprezentovaný ako konvexná lineárna kombinácia rohových bodov.

Vlastnosti úlohy lineárneho programovania. Predtým sa uvažovalo o rôznych formách problému lineárneho programovania a ukázalo sa, že každý problém lineárneho programovania môže byť reprezentovaný ako všeobecný alebo kanonický problém.

Na zdôvodnenie vlastností úlohy lineárneho programovania a metód na jej riešenie je vhodné zvážiť ďalšie dva typy zápisu kanonickej úlohy.

Maticový zápis:

Tu S- riadková matica, A- systémová matica, NS- maticový stĺpec premenných, V- maticový stĺpec voľných členov:

Vektorový zápis:

kde vektory zodpovedajú stĺpcom koeficientov pre neznáme.

Nasledujúca veta bola uvedená vyššie, ale nebola dokázaná vo všeobecnej forme.

Veta 1.2. Množina všetkých realizovateľných riešení systému obmedzení úlohy lineárneho programovania je konvexná.

dôkaz: Nechať byť - dve prípustné riešenia LPP uvedené v matricovej forme. Potom a . Uvažujme konvexnú lineárnu kombináciu riešení, t.j.

a ukázať, že je to tiež prípustné riešenie systému (1.3). Naozaj

t.j. Riešenie X vyhovuje systému (1.3). Ale odvtedy NS> 0, t.j. riešenie spĺňa podmienku nezápornosti.

Dokázalo sa teda, že množina všetkých prípustných riešení úlohy lineárneho programovania je konvexná, presnejšie povedané, predstavuje konvexný mnohosten alebo konvexný mnohosten, ktorý budeme ďalej nazývať jedným pojmom - mnohosten riešení.

Odpoveď na otázku, v ktorom bode polytopu riešení je možné optimálne riešenie úlohy lineárneho programovania, dáva nasledujúca základná veta.

Veta 1.3. Ak má problém lineárneho programovania optimálne riešenie, potom lineárna funkcia nadobudne svoju maximálnu hodnotu v jednom z rohových bodov polytopu riešenia. Ak lineárna funkcia nadobudne svoju maximálnu hodnotu vo viac ako jednom rohovom bode, potom ju získa v akomkoľvek bode, ktorý je konvexnou lineárnou kombináciou týchto bodov.

dôkaz: Budeme predpokladať, že polytop riešenia je ohraničený. Označme jej rohové body pomocou , a optimálne riešenie je cez X *... Potom F (X *)³ F (X) za všetky body NS mnohosten riešení. Ak X * Ak je rohový bod, potom je prvá časť vety dokázaná.

Predstierajme to X * nie je rohový bod, potom podľa vety 1.1 X * možno znázorniť ako konvexnú lineárnu kombináciu rohových bodov mnohostenu riešenia, t.j.

Pretože F (X) Je to lineárna funkcia, získame

V tomto rozšírení si spomedzi hodnôt vyberáme maximálnu hodnotu. Nech zodpovedá rohovému bodu X k(1 £ k£ R); označme to tým M, tie. . Nahraďte každú hodnotu vo výraze (1.5) touto maximálnou hodnotou M. Potom

Podľa predpokladu NS* Je teda na jednej strane optimálnym riešením, no na druhej strane je to dokázané
F (X *)£ M, teda, kde X k- rohový bod. Existuje teda rohový bod X k v ktorom lineárna funkcia nadobúda svoju maximálnu hodnotu.

Na dôkaz druhej časti vety predpokladajme, že účelová funkcia nadobúda svoju maximálnu hodnotu vo viac ako jednom rohovom bode, napríklad v bodoch , kde , potom

Nechať byť NS- konvexná lineárna kombinácia týchto rohových bodov, t.j.

V tomto prípade vzhľadom na funkciu F (X)- lineárny, dostaneme

tie. lineárna funkcia F nadobúda maximálnu hodnotu v ľubovoľnom bode NSčo je konvexná lineárna kombinácia rohových bodov.

Komentujte. Požiadavka, aby bol polytop riešení vo vete ohraničený, je podstatná, pretože v prípade neohraničenej polyedrickej oblasti, ako je uvedené vo vete 1.1, nie každý bod takejto oblasti môže byť reprezentovaný konvexnou lineárnou kombináciou jej rohových bodov. .

Dokázaná veta je základná, pretože naznačuje základný spôsob riešenia problémov lineárneho programovania. V skutočnosti je podľa tejto vety namiesto štúdia nekonečnej množiny realizovateľných riešení na nájdenie požadovaného optimálneho riešenia medzi nimi potrebné skúmať iba konečný počet rohových bodov mnohostenu riešení.

Ďalšia veta je venovaná analytickej metóde hľadania rohových bodov.

Veta 1.4. Každému prípustnému základnému riešeniu úlohy lineárneho programovania zodpovedá rohový bod mnohostena riešenia a naopak každý rohový bod mnohostenu riešenia zodpovedá prípustnému základnému riešeniu.

dôkaz: Nech je prípustné základné riešenie systému obmedzení LPP (1.4), v ktorom je prvý T komponent sú hlavné premenné a zvyšok n - t zložka - vedľajšie premenné rovné nule v základnom riešení (ak tomu tak nie je, potom je možné príslušné premenné prečíslovať). Ukážme to NS

Predpokladajme opak, t.j. čo NS nie je rohový bod. Potom pointa NS môže byť reprezentovaný vnútorným bodom segmentu spájajúceho dva rôzne, ktoré sa nezhodujú s X, bodov

inými slovami, konvexná lineárna kombinácia bodov mnohosten riešení, t.j.

kde (predpokladáme, že inak bod NS sa zhoduje s bodom NS 1 alebo NS 2).

Vektorovú rovnosť (1.6) zapíšeme v súradnicovom tvare:

Pretože všetky premenné a koeficienty sú nezáporné, potom z tých druhých p-t rovnosti vyplýva, že t.j. v rozhodnutiach NS 1 , NS 2 a NS sústavy rovníc (1.4) hodnoty n - t zložky sú v tomto prípade rovné nule. Tieto komponenty možno považovať za hodnoty vedľajších premenných. Ale hodnoty vedľajších premenných jednoznačne určujú hodnoty hlavných, preto

Takže všetky NS komponent v riešeniach NS 1 , NS 2 a NS zhodujú, a teda aj body NS 1 a NS 2 zlúčiť, čo je v rozpore s predpokladom. teda X Je rohový bod mnohostenu riešenia.

Dokážme opačné tvrdenie. Dovoliť byť rohový bod polytopu riešení a jeho prvý T súradnice sú kladné. Ukážme to NS- prípustné základné riešenie. nie je rohový bod, čo je v rozpore s podmienkou. Preto je náš predpoklad nesprávny, t.j. vektory sú lineárne nezávislé a NS Je prípustné základné riešenie problému (1.4).

Dôležitý dôsledok vyplýva priamo z viet 1.3 a 1.4: ak má problém lineárneho programovania optimálne riešenie, potom sa zhoduje aspoň s jedným z jeho prípustných základných riešení.

takze optimum lineárnej funkcie problému lineárneho programovania treba hľadať medzi konečným počtom jeho prípustných základných riešení.

Prebieha optimalizácia lineárnych modelov v MS Excel simplexná metóda- účelné vymenovanie podporných riešení úlohy lineárneho programovania. Algoritmus simplexovej metódy je redukovaný na konštrukciu konvexného mnohostenu vo viacrozmernom priestore a potom na iteráciu cez jeho vrcholy s cieľom nájsť extrémnu hodnotu. objektívna funkcia.

Účinné prostriedky lineárne programovanie sú základom celočíselného aj nelineárneho programovania pre komplexnejšie optimalizačné problémy. Tieto metódy však vyžadujú dlhší čas výpočtu.

V ďalších prednáškach budú podrobne rozobraté príklady riešenia typických optimalizačných problémov a rozhodovania manažmentu pomocou doplnku MS Excel „Hľadať riešenie“. Úlohy, ktoré tento nástroj najlepšie vykonáva, majú tri hlavné vlastnosti:

• existuje jediný cieľ, funkčne súvisiaci s ostatnými parametrami systému, ktorý je potrebné optimalizovať (nájsť jeho maximum, minimum, prípadne určitú číselnú hodnotu);
• existujú obmedzenia, ktoré sú zvyčajne vyjadrené vo forme nerovností (napríklad množstvo použitých surovín nesmie prekročiť zásoby surovín na sklade, alebo prevádzková doba stroja za deň by nemala byť dlhšia ako 24 hodín mínus čas na službu);
• existuje množina hodnôt vstupných premenných, ktoré ovplyvňujú optimalizované hodnoty a obmedzenia.

Parametre úlohy sú obmedzené nasledujúcimi limitnými hodnotami:

• počet neznámych - 200;
• počet obmedzení vzorca na neznámych - 100;
• počet obmedzujúcich podmienok pre neznáme je 400.

Algoritmus na nájdenie optimálnych riešení zahŕňa niekoľko fáz:

• prípravné práce;
• ladenie riešenia;
• analýza riešenia.

Postupnosť nevyhnutných prípravných prác vykonaných pri riešení úloh ekonomického a matematického modelovania pomocou MS Excel je znázornená na blokovej schéme na obrázku 1.6.

Ryža. 1.6.

Z piatich bodov plánu prípravných prác je formalizovaný iba piaty bod. Zvyšok práce si vyžaduje kreativitu – a môžu ju vykonávať rôzni ľudia rôznymi spôsobmi. Poďme si v krátkosti vysvetliť podstatu znenia bodov plánu.

Pri nastavovaní problému sú známe cieľové koeficienty a normalizované koeficienty. V predchádzajúcom príklade boli koeficienty tvoriace cieľovú funkciu hodnoty normalizovaného zisku na policu typu ( ) a jedna polica typu ( ). Normalizované koeficienty boli miery spotreby materiálu a strojového času na policu každého typu. Matrica vyzerala takto:

Okrem toho sú hodnoty zdrojov vždy známe. V predchádzajúcom príklade to bola týždenná dodávka dosiek a možnosť využitia strojového času: , ... V úlohách je často potrebné obmedziť hodnoty premenných. Preto je potrebné určiť spodnú a hornú hranicu oblasti ich zmien.

V dialógovom okne optimalizačného programu „Hľadať riešenie“ teda musíme zadať nasledujúci cieľový algoritmus:

Cieľová funkcia sa rovná súčinu vektora požadovaných hodnôt premenných vektorom cieľových koeficientov

Normalizované koeficienty pre vektor hľadaných hodnôt premenných by nemali presiahnuť hodnotu daného vektora zdrojov

Hodnoty premennej musia byť v rámci stanovených limitov počtu počiatočných prvkov systému

Počet počiatočných prvkov systému

Počet špecifikovaných typov zdrojov

Ladenie riešenia je potrebné v prípade, keď program vydá hlásenie o negatívnych výsledkoch (obrázok 1.7):

Ryža. 1.7.

• ak sa nezíska realizovateľné riešenie, opravte model počiatočných údajov;
• ak nebol prijatý optimálne riešenie, potom zaviesť ďalšie obmedzenia.

Problémy s programom optimálne riešenie len na modelovanie skutočného problému, nie na riešenie problému samotného. Pri konštrukcii modelu sa vychádzalo z rôznych zjednodušujúcich predpokladov reálnej situácie. To umožnilo formalizovať proces, približne odrážajúci skutočné kvantitatívne vzťahy medzi parametrami systému a cieľom. A ak sa skutočné parametre líšia od tých, ktoré sú zahrnuté v modeli, ako sa zmení rozhodnutie? Aby sa to zistilo, pred prijatím manažérskeho rozhodnutia sa analyzuje modelové rozhodnutie.

Analýza optimálne riešenie, zabudovaný do programu, je záverečnou fázou matematického modelovania ekonomických procesov. Umožňuje hlbšiu kontrolu vhodnosti modelu pre daný proces, ako aj spoľahlivosť optimálneho riešenia. Je riadený dátami optimálne riešenie a správy, ktoré sa vydávajú v časti „Hľadanie riešenia“. Nevylučuje ani nenahrádza tradičnú analýzu plánu z ekonomického hľadiska pred prijatím manažérskeho rozhodnutia.

Ekonomická analýza má tieto ciele:

• určenie možných dôsledkov v systéme ako celku a jeho prvkoch pri zmene parametra modelu;
• posúdenie stability optimálneho plánu voči zmenám jednotlivých parametrov problému: ak nie je odolný voči zmenám väčšiny parametrov, klesá záruka jeho realizácie a dosiahnutia vypočítaného optima;
• realizácia variantných výpočtov a získavanie nových variantov plánu bez opätovného riešenia problému z pôvodného podkladu pomocou úprav.

Možné metódy analýzy sú znázornené v diagrame na obrázku 1.8.

Po získaní optimálneho riešenia sa analyzuje podľa prijatých správ. Analýza stability- štúdium vplyvu zmien jednotlivých parametrov modelu na ukazovatele optimálneho riešenia. Limitná analýza- analýza prijateľných zmien v optimálnom pláne, v ktorom plán zostáva optimálny.

Vzhľadom na zodpovednosť robiť ekonomické manažérske rozhodnutie, vedúci sa musí uistiť, že prijatý optimálny plán je jediný správny. Na to je potrebné získať odpovede na nasledujúce otázky na základe modelu:

• "čo ak…"
• "čo je potrebné..."

Analýza na zodpovedanie prvej otázky sa nazýva variantná analýza; analýza na zodpovedanie druhej otázky riešenia na mieru.

Analýza variantov je nasledujúcich typov:

• Parametrický- analýza, ktorá spočíva v riešení problému pre rôzne hodnoty určitého parametra.
• Štrukturálna analýza- keď sa riešenie optimalizačného problému hľadá s inou štruktúrou obmedzení.
• Multikriteriálna analýza- Toto je riešenie problému pre rôzne cieľové funkcie.
• Analýza s podmienenými vstupnými údajmi- keď počiatočné údaje použité pri riešení problému závisia od dodržania dodatočných podmienok.

Po vykonaní analýzy by mali byť výsledky prezentované v grafickej forme a mala by byť vypracovaná správa s odporúčaniami pre rozhodnutie s prihliadnutím na konkrétnu ekonomickú situáciu.

Definícia... Akékoľvek riešenie systému obmedzení sa nazýva prípustné riešenie LPP.
Definícia... Uskutočniteľné riešenie, v ktorom účelová funkcia dosiahne svoju maximálnu alebo minimálnu hodnotu, sa nazýva optimálne riešenie.

Na základe týchto definícií môže byť problém LP formulovaný nasledovne: spomedzi všetkých bodov konvexnej oblasti, ktorá je riešením systému obmedzení, vyberte taký, ktorého súradnice minimalizujú (maximalizujú) lineárnu funkciu. F = s 1 X + s 2 r.
Všimnite si, že premenné X, r v LPP majú spravidla nezáporné hodnoty ( X≥ 0, r≥ 0), takže oblasť sa nachádza v I štvrtine súradnicovej roviny.

Zvážte lineárnu funkciu F = s 1 X + s 2 r a opraviť niektoré jeho hodnoty F... Nech napr. F= 0, t.j. s 1 X + s 2 r= 0. Grafom tejto rovnice bude priamka prechádzajúca počiatkom súradníc (0; 0) (obr.).
Kreslenie
Pri zmene tejto pevnej hodnoty F = d, rovný s 1 X+ s 2 y = d sa bude pohybovať paralelne a "stopovať" celú rovinu. Nechať byť D- polygón - plocha pre riešenie systému obmedzení. Keď sa to zmení d rovno s 1 X + s 2 r = d, v určitej hodnote d = d 1 dosiahne polygón D, nazvime tento bod A"Vstupný bod" a potom prejdením polygónu na určitej hodnote d = d 2 s ním budeme mať posledný spoločný bod V, zavoláme V"Výstupný bod".
Je zrejmé, že objektívna funkcia je jeho najmenšia a najväčšia hodnota F=s 1 X + s 2 r dosiahne na vstupné body A a "exit" V.
Berúc do úvahy, že účelová funkcia má optimálnu hodnotu na množine realizovateľných riešení vo vrcholoch regiónu D možno navrhnúť nasledovný plán riešenia LPP:

1. vybudovať oblasť riešení systému obmedzení;
2. postaviť priamku zodpovedajúcu cieľovej funkcii a paralelným prenosom tejto priamky nájsť „vstupný“ alebo „výstupný“ bod (v závislosti od požiadavky minimalizovať alebo maximalizovať účelovú funkciu);
3. určiť súradnice tohto bodu, vypočítať v nich hodnotu účelovej funkcie.

Všimnite si, že vektor ( s 1 , s 2), kolmo na priamku, ukazuje smer rastu cieľovej funkcie.

Pri grafickom riešení LPP existujú dva možné prípady, ktoré si vyžadujú osobitnú diskusiu.

Prípad 1
Obrázok 6
Pri priamom pohybe s 1 X + s 2 r= d"Vstup" alebo "výstup" (ako na obrázku) nastane na strane polygónu. To sa stane, ak má mnohouholník strany rovnobežné s priamkou. s 1 NS+ s 2 pri = d .
V tomto prípade je bezpočet bodov „výstupu“ („vstupu“), a to akéhokoľvek bodu segmentu AB... To znamená, že účelová funkcia nadobúda maximálnu (minimálnu) hodnotu nie v jednom bode, ale vo všetkých bodoch ležiacich na zodpovedajúcej strane mnohouholníka. D.

Prípad 2
Zvážte prípad, keď je rozsah prípustných hodnôt neobmedzený.
V prípade neohraničenej oblasti môže byť účelová funkcia špecifikovaná tak, že zodpovedajúca priamka nemá „výstupný“ (alebo „vstupný“) bod. Vtedy sa nikdy nedosiahne maximálna hodnota funkcie (minimum) - hovoria, že funkcia nie je obmedzená.
Kreslenie
Je potrebné nájsť maximálnu hodnotu účelovej funkcie F = 4X + 6r→ max, so systémom obmedzení
Zostrojme oblasť realizovateľných riešení, t.j. graficky vyriešime systém nerovností. Aby sme to urobili, zostrojíme každú čiaru a definujeme polroviny dané nerovnicami.
X + r = 18

X	12	9
r	6	9

0,5X + r = 12

X	12	18
r	6	3

X= 12 - rovnobežne s osou OY ;
r= 9 - rovnobežne s osou VÔL ;
X= 0 - os OY ;
r = 0 - os VÔL;
X OY;
r≥ 0 - polrovina nad osou VÔL;
r≤ 9 - nižšie v polovičnej rovine r = 9;
X ≤ 12 - polrovina vľavo X = 12;
0,5X + rX + r = 12;
X + r X + r = 18.
Kreslenie
Priesečníkom všetkých týchto polrovín je zrejme päťuholník OAVSD, s vrcholmi v bodoch O(0; 0), A(0; 9), V(6; 9), S(12; 6), D(12; 0). Tento päťuholník tvorí oblasť realizovateľných riešení problému.

F = 4X + 6r→ max.

X	3	0
r	–2	0

F = 0: 4X + 6r X+ 6r S(12; 6). Je to v nej F = 4X + 6r
Preto pre X = 12, r= 6 funkcií F F= 4 ∙ 12 + 6 ∙ 6 = 84, rovná sa 84. Bod so súradnicami (12; 6) spĺňa všetky nerovnosti systému obmedzení a hodnota účelovej funkcie v ňom je optimálna. F* = 84 (optimálna hodnota bude označená „*“).
Problém bol vyriešený. Je teda potrebné vyrobiť 12 produktov typu I a 6 produktov typu II, pričom zisk bude 84 tisíc rubľov.

Grafická metóda sa používa na riešenie problémov, ktoré mali v systéme obmedzení iba dve premenné. Túto metódu je možné aplikovať aj na systémy nerovností s tromi premennými. Geometricky bude situácia iná, úlohu priamok budú hrať roviny v trojrozmernom priestore a riešením nerovnosti v troch premenných bude polopriestor umiestnený na jednej strane roviny. Úlohu regiónov budú zohrávať mnohosteny, ktoré sú priesečníkom polpriestorov.

Príklad č.2. Baňa rozvíja dva švy. Výstup rezu v prvej vrstve je a1%; na druhom - a2%. Maximálna produkcia porubu pre prvú vrstvu je B1 tisíc ton ročne, pre druhú vrstvu - B2 tisíc ton ročne. Podľa technológie práce nemôže výroba z druhej vrstvy prevýšiť výrobu z prvej vrstvy. Výkon bane v bani by nemal presiahnuť 1 tisíc ton ročne. Celkové zaťaženie dvoch vrstiev za rok by malo byť minimálne C2 tisíc ton ročne. Vytvorte matematický model a zostavte súbor hodnôt prípustného zaťaženia pre prvú a druhú vrstvu za rok.

Príklad č.3. Predajňa predáva 2 druhy nealkoholických nápojov: Cola a limonáda. Príjem z jednej plechovky koly je 5 centov, pričom príjem z jednej plechovky limonády je 7 centov. V priemere predajňa nepredá viac ako 500 plechoviek oboch nápojov denne. Napriek tomu, že kolu vyrába známa značka, kupujúci uprednostňujú limonádu, pretože je oveľa lacnejšia. Odhaduje sa, že predaj koly a limonády by mal byť minimálne 2:1 a v obchode je známe, že denne predá minimálne 100 plechoviek koly. Koľko plechoviek každého nápoja by mal mať obchod na začiatku dňa, aby sa maximalizoval príjem?

Príklad č.4. Úlohu lineárneho programovania vyriešte približne graficky s následným výpočtom presnej hodnoty a max (min) hodnoty cieľovej funkcie.

Príklad č.5. Cestovná kancelária vyžaduje maximálne trojtonové autobusy a maximálne päťtonové autobusy. Predajná cena autobusov prvej značky je 20 000 USD, druhej značky 40 000 USD. Cestovná kancelária môže prideliť na nákup autobusov najviac 1 $. Koľko autobusov každej značky je potrebné zakúpiť samostatne, aby ich celková (celková) nosnosť bola maximálna. Vyriešte problém graficky.

Príklad č.6. Pomocou grafickej metódy nájdite optimálny plán výroby pre úlohu uvedenú v tabuľke.

Príklad č.7. Vyriešte problém lineárneho programovania grafickou metódou, pričom systém obmedzení problému podrobte Jordan-Gaussovým transformáciám. Systém problémových obmedzení je nasledujúci:
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
Smernice... Jordan-Gaussove transformácie je možné vykonávať pomocou tejto služby alebo prostredníctvom štúdia SLAE.

Príklad č. 8. Podnik vyrába dva druhy výrobkov A a B, na výrobu ktorých sa používajú tri druhy surovín. Na výrobu jednotky produktu A je potrebné minúť suroviny každého typu a1, a2, a3 kg a na jednotku produktu B - b1, b2, b3 kg. Výroba je zabezpečovaná surovinami každého druhu v množstve Р1, Р2, Р3 kg, resp. Náklady na jednotku produktu A sú C1 rubľov a jednotka produktu B je C2 rubľov. Je potrebné vypracovať plán výroby výrobkov A a B, ktorý zabezpečuje maximálne náklady na hotový výrobok.

Príklad č.2. Je potrebné nájsť maximálnu hodnotu účelovej funkcie F = 4X + 6r→ max, so systémom obmedzení:

Zostrojme oblasť realizovateľných riešení, t.j. graficky vyriešime systém nerovností. Ak to chcete urobiť, vyberte počet obmedzení rovný 4 (obrázok 1).
Obrázok 1

Potom vyplníme koeficienty pre premenné a samotné obmedzenia (obrázok 2).
Obrázok 2

Obrázok 3
X= 12 - rovnobežne s osou OY;
r= 9 - rovnobežne s osou VÔL;
X> = 0 - os OY
r= 0 - os VÔL;
X≥ 0 - polrovina napravo od osi OY;
r≥0 - polrovina nad osou VÔL;
r≤ 9 - nižšie v polovičnej rovine r = 9;
X≤ 12 - polrovina vľavo X = 12;
0,5X + r≤ 12 - polrovina pod priamkou 0,5 X + r = 12;
X + r≤ 18 - polrovina pod priamkou X + r = 18.

Priesečníkom všetkých týchto polrovín je päťuholník A B C D E, s vrcholmi v bodoch A(0; 0), B(0;9), C(6; 9), D(12;6), E(12; 0). Tento päťuholník tvorí oblasť realizovateľných riešení problému.

Zvážte objektívnu funkciu problému F = 4X + 6r→ max.

X	3	0
r	–2	0

Zostrojíme priamku zodpovedajúcu hodnote funkcie F = 0: 4X + 6r= 0. Túto čiaru budeme posúvať paralelne. Z celej rodiny línií 4 X + 6r= const posledný vrchol, cez ktorý prechádza priamka, keď ide za hranicu mnohouholníka, bude vrcholom S(12; 6). Je to v nej F = 4X + 6r dosiahne svoju maximálnu hodnotu.

Preto pre X = 12, r= 6 funkcií F dosiahne svoju maximálnu hodnotu F= 4 ∙ 12 + 6 ∙ 6 = 84, rovná sa 84. Bod so súradnicami (12; 6) spĺňa všetky nerovnosti systému obmedzení a hodnota účelovej funkcie v ňom je optimálna. F* = 84.

Test v disciplíne "Operačný výskum"

(správne odpovede sú prvé)

1. Pojem "operačný výskum" sa objavil ...

počas druhej svetovej vojny

v 50-tych rokoch XX storočia

v 60-tych rokoch XX storočia

v 70-tych rokoch XX storočia

v 90-tych rokoch XX storočia

na začiatku XXI storočia

2. Prostriedky operačného výskumu (vyberte najvhodnejšiu možnosť) ...

súbor vedeckých metód na riešenie problémov efektívneho riadenia organizačných systémov

súbor opatrení prijatých na realizáciu určitých operácií

súbor metód na realizáciu koncipovaného plánu

vedecké metódy alokácie zdrojov v organizácii výroby

3. Usporiadajte kroky, ktorými zvyčajne prechádza každý operačný výskum:

formulácia problému

konštrukcia zmysluplného (verbálneho) modelu uvažovaného objektu (procesu)

zostavenie matematického modelu

riešenie problémov formulovaných na základe zostrojeného matematického modelu

overenie získaných výsledkov pre primeranosť charakteru skúmaného systému

implementáciu získaného riešenia do praxe

4. V operačnom výskume sa operáciou rozumie ...

akákoľvek udalosť (systém akcií), spojená jednotným pojmom a zameraná na dosiahnutie cieľa

akúkoľvek nekontrolovateľnú udalosť

súbor technických opatrení na zabezpečenie výroby spotrebného tovaru

5. Riešenie sa nazýva optimálne, ...

ak je to z jedného alebo druhého dôvodu vhodnejšie

ak je to racionálne

ak je to dohodnuté s úradmi

ak to schváli valné zhromaždenie

6. Matematické programovanie ...

sa zaoberá štúdiom extrémnych problémov a vývojom metód ich riešenia

je proces tvorby počítačových programov pod vedením matematikov

rieši matematické úlohy na počítači

7. Úlohou lineárneho programovania je ...

nájdenie najväčšej (najmenšej) hodnoty lineárnej funkcie za prítomnosti lineárnych obmedzení

vytvorenie lineárneho programu vo vybranom programovacom jazyku určeného na riešenie úlohy

popis lineárneho algoritmu na riešenie daného problému

8. V úlohe kvadratického programovania ...

účelová funkcia je kvadratická

plocha prípustných riešení je štvorec

obmedzenia obsahujú kvadratické funkcie

9. V problémoch celočíselného programovania ...

neznáme môžu nadobúdať iba celočíselné hodnoty

účelová funkcia musí nevyhnutne nadobúdať celočíselné hodnoty a neznáme môžu byť ľubovoľné

cieľová funkcia je číselná konštanta

10. V úlohách parametrického programovania ...

cieľová funkcia a/alebo systém obmedzení obsahuje parameter (parametre)

oblasť prípustných riešení je rovnobežník alebo rovnobežnosten

počet premenných môže byť len párny

11. V problémoch dynamického programovania ...

proces hľadania riešenia je viacstupňový

potreba racionalizovať výrobu dynamitu

chcete optimalizovať používanie reproduktorov

12. Vznikol nasledujúci problém lineárneho programovania:

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.

Vyberte úlohu, ktorá je ekvivalentná tejto úlohe.

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 → min,

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. Cieľovou funkciou úlohy lineárneho programovania môže byť funkcia:

F=12x1+20x2-3 0x3→min

F= →min

F=→max

F=→max.

14. Systém obmedzení problému lineárneho programovania môže byť systém:

15. Simplexová metóda je:

analytická metóda na riešenie hlavného problému lineárneho programovania

metóda na nájdenie oblasti realizovateľných riešení problému lineárneho programovania;

grafická metóda na riešenie hlavného problému lineárneho programovania;

metóda na redukciu všeobecného problému lineárneho programovania na kanonickú formu.

16. Úlohou lineárneho programovania je:

nájdenie najväčšej alebo najmenšej hodnoty lineárnej funkcie v prítomnosti lineárnych obmedzení

vývoj lineárneho algoritmu a jeho implementácia na počítači

zostavenie a riešenie sústavy lineárnych rovníc

hľadanie lineárnej trajektórie vývoja procesu opísaného daným systémom obmedzení.

17. Oblasť realizovateľných riešení úlohy lineárneho programovania nemôže vyzerať takto:

18. Cieľovou funkciou úlohy lineárneho programovania môže byť funkcia:

F=12x1+20x2-3 0x3→min

F= →min

F=→max

F=→max.

19. Systém obmedzení problému lineárneho programovania môže byť systém:

20. Oblasť realizovateľných riešení problému lineárneho programovania je nasledovná:

F(NS 1, NS 2)= 3NS 1 + 5NS 2 sa rovná...

21. Oblasť realizovateľných riešení úlohy lineárneho programovania má tvar:

Potom maximálna hodnota funkcie F(NS 1, NS 2)= 5NS 1 + 3NS 2 sa rovná...

22. Oblasť realizovateľných riešení úlohy lineárneho programovania má tvar:

Potom maximálna hodnota funkcie F(NS 1, NS 2)= 2NS 1 - 2NS 2 sa rovná...

23. Oblasť realizovateľných riešení úlohy lineárneho programovania má tvar:

F(NS 1, NS 2)= 2NS 1 - 2NS 2 sa rovná...

24. Oblasť realizovateľných riešení problému nelineárneho programovania má tvar:

Potom maximálna hodnota funkcie F(NS 1, NS 2)= NS 2 – NS 12 sa rovná...

25. Maximálna hodnota účelovej funkcie F(NS 1, NS 2)= 5NS 1 + 2NS 2 s obmedzeniami
NS 1 + NS 2 ≤ 6,

NS 1 ≤ 4,

NS 1 ≥ 0, NS 2 ≥ 0, rovná sa...

26. Malý podnik vyrába produkty dvoch druhov. Na výrobu jedného výrobku typu A sa spotrebujú 2 kg surovín, na výrobu jedného výrobku typu B - 1 kg. Spolu je to 60 kg surovín. Je potrebné vypracovať plán výroby, ktorý zabezpečí príjem najväčších výnosov, ak predajná cena jedného výrobku typu A je 3 jednotky, typu B je 1 jednotka. To znamená, že výrobky typu A nie je potrebné vyrobiť viac ako 25 a typ B - nie viac ako 30.

Táto úloha je...

problém lineárneho programovania

problém riešený metódou dynamického programovania

úlohou plánovania siete.

27. Malý podnik vyrába produkty dvoch druhov. Na výrobu jedného výrobku typu A sa spotrebujú 2 kg surovín, na výrobu jedného výrobku typu B - 1 kg. Spolu je to 60 kg surovín. Je potrebné vypracovať plán výroby, ktorý zabezpečí príjem najväčších výnosov, ak predajná cena jedného výrobku typu A je 3 jednotky, typu B je 1 jednotka. To znamená, že výrobky typu A nie je potrebné vyrobiť viac ako 25 a typ B - nie viac ako 30.

Objektívnou funkciou tejto úlohy je funkcia ...

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. Malý podnik vyrába produkty dvoch druhov. Na výrobu jedného výrobku typu A sa spotrebujú 2 kg surovín, na výrobu jedného výrobku typu B - 1 kg. Spolu je to 60 kg surovín. Je potrebné vypracovať plán výroby, ktorý zabezpečí príjem najväčších výnosov, ak predajná cena jedného výrobku typu A je 3 jednotky, typu B je 1 jednotka. To znamená, že výrobky typu A je potrebné vyrobiť nie viac ako 25 a typ B - nie viac ako 30

Platný plán pre túto úlohu je plán:

X =(20, 20)

X =(25, 15)

X =(20, 25)

X =(30, 10)

29. V dvoch bodoch A1 a A2 je 60 a 160 jednotiek tovaru. Všetok tovar je potrebné prepraviť do bodov B1, B2, B3 v množstve 80, 70 a 70 jednotiek. Tarifná matica je nasledovná:. Naplánujte si dopravu tak, aby boli náklady minimálne.

Táto úloha je...

dopravná úloha

problém nelineárneho programovania

problém cestujúceho predajcu

priraďovacia úloha

30. V dvoch bodoch A1 a A2 je 60 a 160 jednotiek tovaru. Všetok tovar je potrebné prepraviť do bodov B1, B2, B3 v množstve 80, 70 a 70 jednotiek. Tarifná matica je nasledovná:. Naplánujte si dopravu tak, aby boli náklady minimálne

Základným plánom pre túto úlohu je plán:

;

31. V dvoch bodoch A1 a A2 je 60 a 160 jednotiek tovaru. Všetok tovar je potrebné prepraviť do bodov B1, B2, B3 v množstve 80, 70 a 70 jednotiek. Tarifná matica je nasledovná:. Naplánujte si dopravu tak, aby boli náklady minimálne.

Cieľovou funkciou tejto úlohy je funkcia:

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. V dvoch bodoch A1 a A2 je 60 a 160 jednotiek tovaru. Všetok tovar je potrebné prepraviť do bodov B1, B2, B3 v množstve 80, 70 a 70 jednotiek. Tarifná matica je nasledovná:. Naplánujte si dopravu tak, aby boli náklady minimálne.

Optimálny plán pre túto úlohu je plán:

;

.

;

;

33. Dopravný problém

bude zatvorené, ak...

34. Dopravný problém

je…

otvorené

zatvorené

nerozpustný

35. Dopravný problém

je…

zatvorené

otvorené

nerozpustný

36. Na vyriešenie nasledujúceho dopravného problému

musíte zadať...

fiktívny spotrebiteľ

fiktívny dodávateľ;

účinná tarifa

37. Na vyriešenie nasledujúceho dopravného problému

musíte zadať...

fiktívny dodávateľ;

fiktívny spotrebiteľ

účinná tarifa

efektívna úroková sadzba.

38. Medzi tieto dopravné úlohy

zatvorené sú...

39. Počiatočný základný plán dopravného problému možno vypracovať ...

všetkými vyššie uvedenými metódami

Metóda severozápadného rohu

metódou minimálnej tarify

metóda dvojitej preferencie

Vogelovou aproximáciou

40. Ak je cieľová funkcia úlohy lineárneho programovania nastavená na maximum, potom ... cieľová funkcia úlohy duálnej úlohy je nastavená na minimum

v duálnom probléme neexistuje objektívna funkcia

duálny problém nemá riešenia

duálny problém má nekonečne veľa riešení

41. Je daný problém lineárneho programovania:

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.

Nasledujúce bude dvojaké pre túto úlohu ...

F *(y1, y2) = 14y1 + 8y2 → min,

3r 1 + y2 ³ 7,

r 1 ≥ 0, y2 ≥ 0.

F *(y1, y2) = 2y1 + 7y2 → min,

2y1 + 3y2 ³ 14,

r 1 + y2 ³ 8,

r 1 £ 0, y2 £ 0.

F *(y1, y2) = 2y1 + 7y2 → min,

3 r 1 + y2 ³ 7,

r 1 £ 0, y2 £ 0.

F *(y1, y2) = 14y1 + 8y2 → min,

r 1 + y2 ³ 7,

r 1 ≥ 0, y2 ≥ 0.

42. Ak má jeden z dvojice duálnych problémov optimálny plán, potom ...

a druhý má optimálny plán

ten druhý nemá optimálny plán

druhý nemá žiadne realizovateľné riešenie

43. Ak má jeden z dvojice duálnych problémov optimálny plán, potom ...

a druhý má optimálny plán a hodnoty cieľových funkcií pre ich optimálne plány sú si navzájom rovné

a druhý má optimálny plán, ale hodnoty cieľových funkcií pre ich optimálne plány sa navzájom nerovnajú

iný problém nemusí mať optimálny plán, ale má realizovateľné riešenia

44. Ak objektívna funkcia jednej z dvojice duálnych úloh nie je ohraničená (pre maximálny problém - zhora, pre minimálny problém - zdola), potom

iná úloha nemá žiadne platné plány

iná úloha má realizovateľné plány, ale nemá optimálny plán

objektívna funkcia inej úlohy tiež nie je obmedzená

45. Pri riešení niektorých problémov nelineárneho programovania sa používa ...

Lagrangeova multiplikačná metóda

Gaussova metóda

Vogelova aproximačná metóda

Gomoriho metóda

46. ​​Problém nelineárneho programovania je nastavený

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) …

nedostupné (+ ¥)

47. Problém nelineárneho programovania je nastavený

F(NS 1, NS 2)= NS 12 + NS 22 → mv,

NS 1 + NS 2 =6,

NS 1 ≥ 0, NS 2 ≥ 0.

F(NS 1, NS 2) …

48. Problém nelineárneho programovania je nastavený

F(NS 1, NS 2)= NS 12 + NS 22 → max,

NS 1 + NS 2 =6,

NS 1, NS 2 - ľubovoľný.

Najvyššia hodnota účelovej funkcie F(NS 1, NS 2) …

nedostupné (+ ¥)

49. Problém nelineárneho programovania je nastavený

F(NS 1, NS 2)= NS 12 + NS 22 → mv,

NS 1 + NS 2 =6,

NS 1, NS 2 - ľubovoľný.

Najmenšia hodnota účelovej funkcie F(NS 1, NS 2) …

nedostupné (- ¥)

50. Oblasť realizovateľných riešení problému nelineárneho programovania má tvar:

Potom maximálna hodnota funkcie F(NS 1, NS 2)= NS 12 +NS 22 sa rovná...

51. Oblasť realizovateľných riešení problému nelineárneho programovania má tvar:

Potom minimálna hodnota funkcie F(NS 1, NS 2)= NS 12 +NS 22 sa rovná...

52. Na vyriešenie dopravného problému možno použiť ...

potenciálna metóda

Lagrangeova multiplikačná metóda

Gaussova metóda

dezorientačná metóda

53. V systéme obmedzení všeobecného problému lineárneho programovania ...

54. V systéme obmedzení úlohy štandardného (symetrického) lineárneho programovania ...

môžu byť prítomné iba nerovnosti

môžu byť prítomné rovnice aj nerovnice

môžu byť prítomné iba rovnice

55. V systéme obmedzení kanonického (základného) problému lineárneho programovania ...

môžu byť prítomné iba rovnice (za predpokladu, že premenné sú nezáporné)

môžu byť prítomné iba nerovnosti (za predpokladu, že premenné sú nezáporné)

môžu byť prítomné rovnice aj nerovnosti (za predpokladu, že premenné sú nezáporné)

56. Problém lineárneho programovania

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.

zaznamenané v...

štandardná (symetrická) forma

kanonická (základná) forma

slovesný tvar

57. Na zaznamenanie úlohy

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.

v kanonickej forme...

58. Na zaznamenanie úlohy

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.

v kanonickej forme...

je potrebné zaviesť tri ďalšie nezáporné premenné

je potrebné zaviesť dve ďalšie nezáporné premenné

je potrebné zaviesť štyri ďalšie nezáporné premenné

59. Na zaznamenanie úlohy

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.

v kanonickej forme...

je potrebné zaviesť dve ďalšie nezáporné premenné

je potrebné zaviesť tri ďalšie nezáporné premenné

je potrebné zaviesť štyri ďalšie nezáporné premenné

je potrebné zaviesť päť ďalších nezáporných premenných

60. Pri riešení úloh celočíselného programovania je možné použiť ...

Gomoriho metóda

Lagrangeova multiplikačná metóda

Gaussova metóda

Vogelova aproximačná metóda

61. Jadrom riešenia problémov metódou dynamického programovania je ...

Occamova žiletka

princíp "zub za zub, oko za oko"

Heisenbergov princíp

62. Situácia, v ktorej sú zapojené strany, ktorých záujmy sú úplne alebo čiastočne opačné, sa nazýva ...

(konflikt, konflikt, konflikt, konflikt)

63. Skutočný alebo formálny konflikt, v ktorom sú najmenej dvaja účastníci (hráči), z ktorých každý sa snaží dosiahnuť svoje vlastné ciele, sa nazýva ...

(hra, hra)

64. Prípustné činnosti každého z hráčov zamerané na dosiahnutie určitého cieľa sa nazývajú ...

(pravidlá hry, pravidlá hry)

65. Kvantitatívne hodnotenie výsledkov hry sa nazýva ...

(platbou, platbou, platbou)

66. Ak sa hry zúčastňujú iba dve strany (dve osoby), potom sa hra nazýva ...

(štvorhra, štvorhra, štvorhra, štvorhra)

67. Ak sa v hre štvorhry súčet platieb rovná nule, to znamená, že strata jedného hráča sa rovná zisku druhého, potom sa hra nazýva hra ...

(nulový súčet)

68. Jednoznačný popis voľby hráča v každej z možných situácií, v ktorých musí urobiť osobný ťah, sa nazýva ..

(stratégia hráča, stratégia hráča, stratégia, stratégia)

69. Ak pri viacnásobnom opakovaní hry stratégia poskytuje hráčovi maximálny možný priemerný zisk (minimálna možná priemerná strata), potom sa takáto stratégia nazýva ...

(optimálna, optimálna, optimálna stratégia, optimálna stratégia)

70. Nech a je nízka cena a b vysoká cena hry s nulovým súčtom. Potom je výrok pravdivý...

71. Nech a je nízka cena a b vysoká cena hry s nulovým súčtom vo dvojiciach. Ak a = b = v, potom číslo v sa nazýva ...

za cenu hry

rovnovážny bod

optimálna stratégia

zmiešaná stratégia

72. Nech a je nízka cena a b vysoká cena hry s nulovým súčtom. Ak a = b, potom sa hra nazýva ...

sedlo bodová hra

neriešiteľný konflikt

hra bez pravidiel

73. Vektor, ktorého každá zložka ukazuje relatívnu frekvenciu hráčovho použitia zodpovedajúcej čistej stratégie, sa nazýva...

zmiešaná stratégia

smerový vektor

normálny vektor

gradient

74. Nižšia cena maticovej hry daná platobnou maticou sa rovná ...

Viac spodná cena

rovná spodnej cene

neexistuje

81. Maticová hra daná výplatnou maticou, ...

má sedlový hrot

nemá sedlový hrot

nespárované

82. Cena hry, daná výplatnou maticou, je ...

83. Maticová hra daná výplatnou maticou ...

je spárovaný

má sedlový hrot

nespárované

84. Hru dvojíc s nulovým súčtom, daná jej výplatnou maticou, možno znížiť na ...

problém lineárneho programovania

problém nelineárneho programovania

problém celočíselného lineárneho programovania

klasický optimalizačný problém

85. Nižšia cena maticovej hry daná platobnou maticou je...

Viac spodná cena

rovná spodnej cene

neexistuje

92. Maticová hra daná výplatnou maticou ...

nemá sedlový hrot

má sedlový hrot

nespárované

93. Cena hry, daná platobnou maticou, sa pohybuje v ...

94. Ak v prúde udalostí udalosti nasledujú za sebou vo vopred určených a presne definovaných časových intervaloch, potom sa takýto prúd nazýva ...

pravidelné

organizovaný

95. Ak pravdepodobnosť ľubovoľného počtu udalostí spadajúcich do časového intervalu závisí iba od dĺžky tohto intervalu a nezávisí od toho, ako ďaleko sa tento interval nachádza od začiatku času, potom sa príslušný prúd udalostí nazýva:

stacionárne

plynúť bez následkov

najjednoduchšie

jed

96. Ak počet udalostí pripadajúcich na jeden z ľubovoľne zvolených časových intervalov nezávisí od počtu udalostí pripadajúcich na iný, tiež ľubovoľne zvolený časový interval, za predpokladu, že sa tieto intervaly nepretínajú, potom sa príslušný prúd udalostí nazýva tzv. ...

plynúť bez následkov

pravidelné

orientačné

normálne

97. Ak je pravdepodobnosť, že dve alebo viacero udalostí naraz zasiahne veľmi krátky časový interval, zanedbateľná v porovnaní s pravdepodobnosťou zasiahnutia iba jednej udalosti, potom sa zodpovedajúci prúd udalostí nazýva ...

obyčajný

mimoriadny

normálne

jed

98. Ak má tok udalostí súčasne vlastnosti stacionárnosti, obyčajnosti a absencie následkov, potom sa nazýva:

najjednoduchšie (Poisson)

normálne

99. Jednokanálový systém s poruchami je denná servisná stanica pre autoumyvárne. Aplikácia - auto, ktoré prišlo v momente, keď je miesto obsadené - dostane odmietnutie služby. Prietok auta λ = 1,0 (auto za hodinu). Priemerný servisný čas je 1,8 hodiny. Tok áut a tok služieb sú najjednoduchšie. Potom v ustálenom stave relatívna priepustnosť q rovná sa...

100. Jednokanálový systém s poruchami je každodennou servisnou stanicou pre autoumyvárne. Aplikácia - auto, ktoré prišlo v momente, keď je miesto obsadené - dostane odmietnutie služby. Prietok auta λ = 1,0 (auto za hodinu). Priemerný servisný čas je 1,8 hodiny. Tok áut a tok služieb sú najjednoduchšie. Potom, v rovnovážnom stave, percento áut, ktoré dostanú odmietnutie služby, je ...

Všeobecná formulácia problému lineárneho programovania (LPP). Príklady LPP

Lineárne programovanie je odvetvie matematiky, ktoré študuje metódy riešenia extrémnych problémov, ktoré sa vyznačujú lineárnym vzťahom medzi premennými a lineárnym kritériom optimality. Pár slov k samotnému pojmu lineárne programovanie. Vyžaduje si to správne pochopenie. V tomto prípade programovanie samozrejme nie je písanie počítačových programov. Programovanie by sa tu malo chápať ako plánovanie, tvorba plánov, vývoj akčného programu. Matematické problémy lineárneho programovania zahŕňajú štúdium špecifických výrobných a ekonomických situácií, ktoré sa v tej či onej podobe interpretujú ako problémy optimálneho využívania obmedzených zdrojov. Spektrum úloh, ktoré je možné riešiť pomocou metód lineárneho programovania, je pomerne široké. Toto je napríklad:

• - problém optimálneho využitia zdrojov pri plánovaní výroby;
• - problém zmesí (plánovanie zloženia výrobkov);
• - problém hľadania optimálnej kombinácie rôznych druhov produktov na skladovanie v skladoch (riadenie zásob alebo „problém s batohom“);
• - prepravné úlohy (analýza polohy podniku, pohyb tovaru). Lineárne programovanie je najrozvinutejším a najpoužívanejším odvetvím matematického programovania (okrem toho sem patrí: celočíselné, dynamické, nelineárne, parametrické programovanie). Dôvodom sú nasledujúce skutočnosti:
• - matematické modely veľkého množstva ekonomických problémov sú lineárne vzhľadom na hľadané premenné;
• - tento typ problémov je v súčasnosti najviac skúmaný. Pre neho boli vyvinuté špeciálne metódy, pomocou ktorých sa tieto úlohy riešia, a príslušné počítačové programy;
• - mnohé problémy lineárneho programovania po vyriešení našli široké uplatnenie;
• - niektoré problémy, ktoré v pôvodnej formulácii nie sú lineárne, sa po množstve dodatočných obmedzení a predpokladov môžu stať lineárnymi alebo sa dajú zredukovať do takej podoby, že sa dajú riešiť metódami lineárneho programovania. Ekonomický a matematický model akéhokoľvek problému lineárneho programovania zahŕňa: objektívnu funkciu, ktorej optimálnu hodnotu (maximum alebo minimum) je potrebné nájsť; obmedzenia vo forme sústavy lineárnych rovníc alebo nerovníc; požiadavka nezápornosti premenných. Vo všeobecnosti je model napísaný takto:
• - objektívna funkcia:

C1x1 + c2x2 + ... + cnxn> max (min); - obmedzenia:

a11x1 + a12x2 + ... + a1nxn (? =?) b1,

a21x1 + a22x2 + ... + a2nxn (? =?) b2

am1x1 + am2x2 + ... + amnxn (? =?) bm;

Požiadavka na nezápornosť:

V tomto prípade sú aij, bi, cj () dané konštanty. Problémom je nájsť optimálnu hodnotu funkcie (2.1) s obmedzeniami (2.2) a (2.3). Systém obmedzení (2.2) sa nazýva funkčné obmedzenia problému a obmedzenia (2.3) sa nazývajú priame. Vektor spĺňajúci obmedzenia (2.2) a (2.3) sa nazýva realizovateľné riešenie (plán) problému lineárneho programovania. Návrh, v ktorom funkcia (2.1) dosiahne svoju maximálnu (minimálnu) hodnotu, sa nazýva optimálny.

Nižšie sú uvedené príklady niektorých typických problémov vyriešených pomocou metód lineárneho programovania. Takéto úlohy majú skutočný ekonomický obsah. Teraz ich sformulujeme iba z hľadiska LPP a nižšie zvážime metódy riešenia takýchto problémov.

1. Problém optimálneho využitia zdrojov pri plánovaní výroby. Všeobecný význam úloh tejto triedy je nasledujúci. Podnik vyrába n rôznych produktov. Ich výroba si vyžaduje m rôznych druhov zdrojov (suroviny, materiály, pracovný čas atď.). Zdroje sú obmedzené, ich rezervy v plánovacom období sú b1, b2, ..., bm konvenčných jednotiek. Známe sú aj technologické koeficienty aij, ktoré ukazujú, koľko jednotiek i-tého zdroja je potrebných na výrobu jednotky j-tého typu produktu (). Zisk, ktorý podnik získa z predaja výrobku j-tého typu, sa rovná cj. V plánovacom období zostávajú hodnoty aij, bi a cj konštantné. Je potrebné vypracovať taký plán výroby, pri realizácii ktorého by bol zisk podniku najväčší. Nižšie je uvedený jednoduchý príklad úlohy tejto triedy.

Firma sa špecializuje na výrobu hokejok a šachových súprav. Každý klub generuje pre spoločnosť zisk 2 doláre a 4 doláre za každý šachový set. Výroba jednej palice v lokalite A trvá štyri hodiny a v lokalite B dve hodiny. Vytvorí sa šachová súprava so šiestimi hodinami v lokalite A, šiestimi hodinami v lokalite B a jednou hodinou v lokalite C. Dostupná výrobná kapacita v lokalite A je 120 Nm - hodín denne, úsek B - 72 n-hodín a úsek C - 10 n-hodín. Koľko palíc a šachových súprav by mala spoločnosť vyrábať denne, aby maximalizovala zisk?

Podmienky pre problémy tejto triedy sú často prezentované v tabuľkovej forme (pozri tabuľku 2.1).

Za tejto podmienky formulujeme problém lineárneho programovania. Označme: x1 - počet denne vyrobených hokejok, x2 - počet denne vyrobených šachových súprav. ZLP:

4x1 + 6x2? 120,

Zdôraznime, že každá nerovnosť v systéme funkčných obmedzení zodpovedá v tomto prípade jednému alebo druhému miestu výroby, a to: prvému miestu A, druhému miestu B a tretiemu miestu C.

Systém premenných v problematike optimalizácie štruktúry osevných plôch s prihliadnutím na striedanie plodín