Konvexní množiny a jejich vlastnosti. Abychom mohli studovat vlastnosti konvexní množiny, je nutné konvexní množinu přesně definovat. Dříve byla konvexní množina definována jako množina, která spolu s libovolnými dvěma svými body obsahuje segment spojující je.
Zobecněním pojmu úsečka pro více bodů je jejich konvexní lineární kombinace.
Bod X se nazývá konvexní lineární kombinace body, pokud jsou splněny podmínky
Sada bodů je konvexní, jestliže spolu s libovolnými dvěma svými body obsahuje jejich libovolnou konvexní, lineární kombinaci.
Můžeme dokázat následující větu o zobrazení konvexního mnohostěnu.
Věta 1.1. Konvexní n-rozměrný mnohostěn je konvexní lineární kombinace jeho rohových bodů.
Z věty 1.1 vyplývá, že konvexní mnohostěn je generován svými rohovými body nebo vrcholy: úsečka dvěma body, trojúhelník třemi, čtyřstěn čtyřmi body atd. Zároveň konvexní polyedrická oblast, která je neomezenou množinou, není jednoznačně definována svými rohovými body: žádný z jejích bodů nelze reprezentovat jako konvexní lineární kombinaci rohových bodů.
Vlastnosti úlohy lineárního programování. Dříve byly zvažovány různé formy problému lineárního programování a ukázalo se, že jakýkoli problém lineárního programování může být reprezentován jako obecný nebo kanonický problém.
Pro doložení vlastností problému lineárního programování a metod jeho řešení je vhodné zvážit další dva typy zápisu kanonické úlohy.
Maticový záznamový formulář:
Tady S- řádková matice, A- matice systému, X– maticový sloupec proměnných, V– maticový sloupec volných členů:
Vektorová forma záznamu:
kde vektory odpovídají sloupcům koeficientů pro neznámé.
Následující věta byla formulována výše, ale nebyla prokázána v obecné formě.
Věta 1.2. Množina všech možných řešení systému omezení úlohy lineárního programování je konvexní.
Důkaz: Nechat - dvě proveditelná řešení PLP, uvedená v maticové formě. Pak . Uvažujme konvexní lineární kombinaci řešení, tzn.
a ukázat, že je to také přípustné řešení soustavy (1.3). Vskutku
tj. řešení X vyhovuje systému (1.3). Ale od té doby X>0, tzn. řešení splňuje podmínku nezápornosti.
Bylo tedy prokázáno, že množina všech proveditelných řešení problému lineárního programování je konvexní, přesněji řečeno představuje konvexní mnohostěn nebo konvexní mnohostěn, který budeme dále nazývat jedním pojmem - mnohostěn řešení.
Odpověď na otázku, v jakém bodě řešení je mnohostěn optimálním možným řešením problému lineárního programování, dává následující základní věta.
Věta 1.3. Pokud má problém lineárního programování optimální řešení, pak lineární funkce nabývá maximální hodnoty v jednom z rohových bodů mnohostěnu řešení. Pokud lineární funkce nabývá maximální hodnoty ve více než jednom rohovém bodě, pak ji nabývá v libovolném bodě, který je konvexní lineární kombinací těchto bodů.
Důkaz: Budeme předpokládat, že mnohostěn řešení je ohraničený. Označme jeho rohové body pomocí , a optimální řešení je přes X*. Pak F(X*)³ F(X) za všechny body X mnohostěn řešení. Li X* je rohový bod, pak je dokázána první část věty.
Pojďme to předstírat X* není tedy rohový bod na základě věty 1.1 X* lze znázornit jako konvexní lineární kombinaci rohových bodů mnohostěnu řešení, tzn.
Protože F(X) je lineární funkce, dostáváme
Při tomto rozkladu volíme mezi hodnotami maximum. Nechte to odpovídat rohovému bodu Xk(1 £ k£ R); označme to tím M, těch. . Nahraďte každou hodnotu ve výrazu (1.5) touto maximální hodnotou M. Pak
Podle předpokladu X* je tedy na jednu stranu optimální řešení, ale na druhou stranu se to prokázalo
F(X*)£ M, tedy, , kde Xk– rohový bod. Existuje tedy rohový bod Xk, ve kterém lineární funkce nabývá své maximální hodnoty.
Abychom dokázali druhou část věty, předpokládejme, že účelová funkce nabývá maximální hodnoty ve více než jednom rohovém bodě, například v bodech , Kde , Pak
Nechat X– konvexní lineární kombinace těchto rohových bodů, tzn.
V tomto případě s ohledem na funkci F(X)– lineární, dostáváme
těch. lineární funkce F nabývá maximální hodnoty v libovolném bodě X, což je konvexní lineární kombinace rohových bodů.
Komentář. Požadavek, aby mnohostěn řešení byl ve větě ohraničen, je zásadní, protože v případě neomezené mnohostěnné oblasti, jak je uvedeno ve větě 1.1, nelze každý bod takové oblasti znázornit konvexní lineární kombinací jejích rohových bodů.
Osvědčený teorém je základní, protože ukazuje základní způsob řešení problémů lineárního programování. Podle této věty je totiž místo studia nekonečné množiny proveditelných řešení k nalezení požadovaného optimálního řešení mezi nimi nutné studovat pouze konečný počet rohových bodů mnohostěnu řešení.
Další věta je věnována analytické metodě hledání rohových bodů.
Věta 1.4. Každému přípustnému základnímu řešení úlohy lineárního programování odpovídá rohový bod mnohostěnu řešení a naopak každému rohovému bodu mnohostěnu řešení odpovídá přípustné základní řešení.
Důkaz: Nechť je přípustné základní řešení systému omezení LLP (1.4), ve kterém první T složka jsou hlavní proměnné a zbytek p - t komponenta – nehlavní proměnné rovné nule v základním řešení (pokud tomu tak není, pak lze odpovídající proměnné přečíslovat). Pojďme si to ukázat X
Předpokládejme opak, tj. Co X není rohový bod. Pak bod X může být reprezentován vnitřním bodem segmentu spojujícího dva různé, které se neshodují X, body
jinými slovy, konvexní lineární kombinace bodů mnohostěn řešení, tzn.
kde (předpokládáme, že , protože jinak bod X se shoduje s pointou X 1 nebo X 2).
Zapišme vektorovou rovnost (1.6) v souřadnicovém tvaru:
Protože všechny proměnné a koeficienty jsou nezáporné, pak od posledního p-t rovnosti z toho vyplývá, že , tzn. v rozhodnutích X 1 , X 2 a X soustava rovnic (1.4) hodnot p - t složky jsou v tomto případě rovné nule. Tyto složky lze považovat za hodnoty neprimárních proměnných. Ale hodnoty nezákladních proměnných jednoznačně určují hodnoty hlavních, proto
Takže všechno P součást řešení X 1 , X 2 a X shodují, a tedy i body X 1 a X 2 sloučit, což je v rozporu s předpokladem. Proto, X– rohový bod mnohostěnu řešení.
Dokažme opačné tvrzení. Dovolit být rohový bod řešení mnohostěnu a jeho první T souřadnice jsou kladné. Pojďme si to ukázat X– přípustné základní řešení. není rohový bod, což je v rozporu s podmínkou. Proto je náš předpoklad nesprávný, tzn. vektory jsou lineárně nezávislé a X je přípustné základní řešení problému (1.4).
Důležitý důsledek vyplývá přímo z vět 1.3 a 1.4: Pokud má problém lineárního programování optimální řešení, pak se shoduje s alespoň jedním z jeho proveditelných základních řešení.
Tak, optimum lineární funkce problému lineárního programování by se mělo hledat mezi konečným počtem jeho proveditelných základních řešení.
Komponenty matematického modelu
Základem řešení ekonomických problémů jsou matematické modely.
Sestavení matematického modelu zahrnuje:Matematický model problém je soubor matematických vztahů, které popisují podstatu problému.
- výběr problémových proměnných
- sestavení systému omezení
- volba objektivní funkce
Úkolové proměnné se nazývají veličiny X1, X2, Xn, které zcela charakterizují ekonomický proces. Obvykle se zapisují jako vektor: X=(X1, X2,...,Xn).
Systém omezení problémy jsou souborem rovnic a nerovností, které popisují omezené zdroje v uvažovaném problému.
Objektivní funkceúkoly se nazývají funkce proměnných úkolu, které charakterizují kvalitu úkolu a jejichž extrém je třeba najít.
Obecně lze problém lineárního programování napsat takto:
Tento záznam znamená následující: najděte extrém účelové funkce (1) a odpovídající proměnné X=(X1, X2,...,Xn) za předpokladu, že tyto proměnné splňují systém omezení (2) a nezápornost podmínky (3).
Platné řešení(plán) úlohy lineárního programování je libovolný n-rozměrný vektor X=(X1, X2,...,Xn), který vyhovuje systému omezení a podmínek nezápornosti.
Soubor možných řešení (plánů) problému tvoří region proveditelných řešení(ODR).
Příklad sestavení matematického modelu Problém využití zdrojů (surovin)Optimální řešení(plán) úlohy lineárního programování je takové přípustné řešení (plán) úlohy, ve kterém účelová funkce dosahuje extrému.
Stav: K výrobě n druhů výrobků se používá m druhů zdrojů. Vytvořte matematický model.
Známý:
- bi (i = 1,2,3,...,m) - rezervy každého i-tého typu zdroje;
- aij (i = 1,2,3,...,m; j=1,2,3,...,n) - náklady každého i-tého druhu zdroje na výrobu jednotky objemu j-tý typ produktu;
- cj (j = 1,2,3,...,n) - zisk z prodeje jednotky objemu j-tého druhu produktu.
Je třeba sestavit plán výroby, který zajistí maximální zisk při daných omezeních zdrojů (surovin).
Řešení:
Zaveďme vektor proměnných X=(X1, X2,...,Xn), kde xj (j = 1,2,...,n) je objem výroby j-tého typu produktu.
Náklady i-tého druhu zdroje na výrobu daného objemu xj výrobků se rovnají aijxj, proto omezení využití zdrojů na výrobu všech druhů výrobků má podobu:
Zisk z prodeje j-tého typu produktu se rovná cjxj, takže účelová funkce je rovna:
Odpovědět- Matematický model vypadá takto:
Kanonická forma úlohy lineárního programování
V obecném případě je problém lineárního programování napsán tak, že omezeními jsou jak rovnice, tak nerovnosti a proměnné mohou být buď nezáporné, nebo libovolně se měnící.
V případě, kdy jsou všechna omezení rovnicemi a všechny proměnné splňují podmínku nezápornosti, nazývá se problém lineárního programování kanonický.
Může být reprezentován v souřadnicovém, vektorovém a maticovém zápisu.
Kanonický problém lineárního programování v souřadnicovém zápisu má tvar:
Kanonický problém lineárního programování v maticovém zápisu má tvar:
- A - matice koeficientů soustavy rovnic
- X - matice-sloupec úkolových proměnných
- Ао - maticový sloupec správných částí systému omezení
Často se používají problémy lineárního programování, nazývané symetrické, které v maticovém zápisu mají tvar:
Redukce obecného problému lineárního programování na kanonickou formu
Ve většině metod řešení problémů lineárního programování se předpokládá, že systém omezení se skládá z rovnic a přirozených podmínek pro nezápornost proměnných. Při sestavování modelů ekonomických problémů se však omezení tvoří především v podobě soustavy nerovnic, proto je nutné umět přejít od soustavy nerovnic k soustavě rovnic.
To lze provést takto:Vezměme lineární nerovnost a1x1+a2x2+...+anxn≤b a na její levou stranu připočtěme určitou hodnotu xn+1 tak, aby se z nerovnosti stala rovnost a1x1+a2x2+...+anxn+xn+1=b . Navíc tato hodnota xn+1 je nezáporná.
Podívejme se na vše na příkladu.
Příklad 26.1Převeďte problém lineárního programování do kanonické podoby:
Řešení:
Přejděme k problému hledání maxima účelové funkce.
K tomu měníme znaménka koeficientů účelové funkce.
Pro transformaci druhé a třetí nerovnosti systému omezení do rovnic zavádíme nezáporné doplňkové proměnné x4 x5 (v matematickém modelu je tato operace označena písmenem D).
Proměnná x4 je zavedena do levé strany druhé nerovnosti se znaménkem „+“, protože nerovnost má tvar „≤“.
Proměnná x5 je zavedena do levé strany třetí nerovnosti se znaménkem „-“, protože nerovnost má tvar „≥“.
Proměnné x4 x5 se zadávají do účelové funkce s koeficientem. rovna nule.
Problém zapíšeme v kanonické podobě:
Lineární programování je obor matematiky, který studuje metody pro nalezení minima nebo maxima lineární funkce konečného počtu proměnných za předpokladu, že proměnné splňují konečný počet omezení ve formě lineárních rovnic nebo lineárních nerovností.
Obecný problém lineárního programování (GLP) lze tedy formulovat následovně.
Najděte hodnoty skutečných proměnných, pro které Objektivní funkce
má minimální hodnotu na množině bodů, jejichž souřadnice vyhovují systém omezení
Jak známo, uspořádaná sbírka hodnot n proměnné , , … jsou reprezentovány bodem v n-rozměrném prostoru. V následujícím budeme tento bod označovat X=( , , … ).
V maticové formě lze problém lineárního programování formulovat následovně:
, A- velikostní matice,
Tečka X Zavolá se =( , , … ), splňující všechny podmínky platný bod . Volá se množina všech přípustných bodů platná oblast .
Optimální řešení (optimální plán) problém lineárního programování se nazývá řešení X=( , , … ), patřící do přípustné oblasti a pro kterou je lineární funkce Q nabývá optimální (maximální nebo minimální) hodnoty.
Teorém. Množina všech možných řešení systému omezení úlohy lineárního programování je konvexní.
Množina bodů se nazývá konvexní , pokud spolu s libovolnými dvěma svými body obsahuje jejich libovolnou konvexní lineární kombinaci.
Tečka X volal konvexní lineární kombinace bodů, pokud jsou splněny podmínky
Množina všech proveditelných řešení problému lineárního programování je konvexní polyedrická oblast, kterou budeme dále nazývat mnohostěn řešení .
Teorém. Pokud má ZLP optimální řešení, pak účelová funkce nabývá maximální (minimální) hodnoty v jednom z vrcholů mnohostěnu řešení. Pokud účelová funkce nabývá maximální (minimální) hodnoty ve více než jednom bodě, pak tuto hodnotu nabývá v libovolném bodě, který je konvexní lineární kombinací těchto bodů.
Mezi mnoha řešeními systému m lineární rovnice popisující mnohostěn řešení, rozlišují se tzv. základní řešení.
Základní řešení systému m lineární rovnice s n proměnnými je řešení, ve kterém vše n-m vedlejší proměnné jsou nulové. V úlohách lineárního programování se taková řešení nazývají přípustná základní řešení (referenční plány).
Teorém. Každé přípustné základní řešení úlohy lineárního programování odpovídá vrcholu mnohostěnu řešení a naopak každému vrcholu mnohostěnu řešení odpovídá přípustné základní řešení.
Z výše uvedených teorémů vyplývá důležitý důsledek:
Pokud má problém lineárního programování optimální řešení, pak se shoduje s alespoň jedním z jeho proveditelných základních řešení.
Optimum lineární funkce cíle problému lineárního programování je tedy třeba hledat mezi konečným počtem jeho proveditelných základních řešení.
Definice. Jakékoli řešení systému omezení se nazývá přípustné řešení pro PLP.
Definice. Možné řešení, ve kterém účelová funkce dosáhne maximální nebo minimální hodnoty, se nazývá optimální řešení.
Vzhledem k těmto definicím lze úlohu LP formulovat následovně: ze všech bodů konvexní oblasti, která je řešením systému omezení, vyberte ten, jehož souřadnice minimalizují (maximalizují) lineární funkci. F = S 1 X + S 2 y.
Všimněte si, že proměnné X, y v ZLP zpravidla nabývají nezáporné hodnoty ( X≥ 0, y≥ 0), proto se oblast nachází v první čtvrtině souřadnicové roviny.
Uvažujme lineární funkci F = S 1 X + S 2 y a opravit část jeho hodnoty F. Ať např. F= 0, tj. S 1 X + S 2 y= 0. Grafem této rovnice bude přímka procházející počátkem souřadnic (0;0) (obr.).
Výkres
Při změně této pevné hodnoty F = d, rovný S 1 X+ S 2 y = d posune rovnoběžně a „obkreslí“ celou rovinu. Nechat D– polygon – doména řešení soustavy omezení. Když se to změní d rovný S 1 X + S 2 y = d, v nějaké hodnotě d = d 1 dosáhne polygonu D, nazvěme tento bod A"vstupní bod" a poté, co prošel polygonem, na nějaké hodnotě d = d 2 s ním budeme mít poslední společný bod V, zavolejme V„výstupní bod“.
Je zřejmé, že účelová funkce má své nejmenší a největší hodnoty F=S 1 X + S 2 y dosáhne na vstupní body A a "exit" V.
Vzhledem k tomu, že optimální hodnota na množině možných řešení nabývá účelová funkce na vrcholech oblasti D, můžeme navrhnout následující plán řešení problému:
- sestrojí doménu řešení systému omezení;
- sestrojte přímku odpovídající účelové funkci a paralelním posunem této přímky najděte „vstupní“ nebo „výstupní“ bod (v závislosti na požadavku minimalizovat nebo maximalizovat účelovou funkci);
- určit souřadnice tohoto bodu a vypočítat v nich hodnotu účelové funkce.
Při grafickém řešení ZLP jsou možné dva případy, které vyžadují zvláštní diskusi.
Případ 1
Obrázek 6
Při pohybu po přímce S 1 X + S 2 y= d„vstup“ nebo „výstup“ (jako na obrázku) se objeví podél strany polygonu. K tomu dojde, pokud má mnohoúhelník strany rovnoběžné s čárou S 1 X+ S 2 na = d .
V tomto případě existuje nekonečný počet „výstupních“ („vstupních“) bodů, konkrétně jakéhokoli bodu na segmentu AB. To znamená, že účelová funkce nabývá maximální (minimální) hodnoty nikoli v jednom bodě, ale ve všech bodech ležících na odpovídající straně polygonu. D.
Případ 2
Uvažujme případ, kdy je rozsah přípustných hodnot neomezený.
V případě neomezené oblasti lze účelovou funkci specifikovat tak, že odpovídající přímka nemá „výstupní“ (nebo „vstupní“) bod. Pak se nikdy nedosáhne maximální hodnoty funkce (minimum) - říkají, že funkce je neomezená. 
Výkres
Je nutné najít maximální hodnotu účelové funkce F = 4X + 6y→ max , se systémem omezení
Vytvořme oblast proveditelných řešení, tzn. Vyřešme soustavu nerovnic graficky. K tomu sestrojíme každou přímku a určíme poloroviny definované nerovnostmi.
X + y = 18
|
X |
12 |
9 |
|
y |
6 |
9 |
0,5X + y = 12
|
X |
12 |
18 |
|
y |
6 |
3 |
X= 12 – rovnoběžně s osou OY ;
y= 9 – rovnoběžně s osou VŮL ;
X= 0 – osa OY ;
y = 0 – osa VŮL;
X OY;
y≥ 0 – polorovina nad osou VŮL;
y≤ 9 – polorovina níže y = 9;
X ≤ 12 – polorovina vlevo X = 12;
0,5X + yX + y = 12;
X + y X + y = 18.
Výkres
Průsečík všech těchto polorovin je zjevně pětiúhelník OAVSD, s vrcholy v bodech O(0; 0), A(0; 9), V(6; 9), S(12; 6), D(12; 0). Tento pětiúhelník tvoří oblast proveditelných řešení problému.
F = 4X + 6y→ max.
|
X |
3 |
0 |
|
y |
–2 |
0 |
F = 0: 4X + 6y X+ 6y S(12; 6). Je v něm F = 4X + 6y
Takže když X = 12, y= 6 funkcí F F= 4 ∙ 12 + 6 ∙ 6 = 84, rovná se 84. Bod se souřadnicemi (12; 6) splňuje všechny nerovnosti systému omezení a v něm je hodnota účelové funkce optimální. F* = 84 (optimální hodnotu označíme jako „*“).
Problém je vyřešen. Je tedy nutné vyrobit 12 výrobků typu I a 6 výrobků typu II se ziskem 84 tisíc rublů.
Grafická metoda se používá k řešení problémů, které měly v systému omezení pouze dvě proměnné. Tuto metodu lze použít i pro soustavy nerovnic se třemi proměnnými. Geometricky bude situace jiná, roli přímek budou hrát roviny v trojrozměrném prostoru a řešením nerovnice ve třech proměnných bude poloprostor umístěný na jedné straně roviny. Roli ploch budou hrát mnohostěny, které jsou průnikem poloprostorů.
Příklad č. 2. Důl vyvíjí dvě sloje. Výtěžek shluku pro první vrstvu je a1 %; za druhé - a2%. Maximální produktivita pracovní plochy pro první vrstvu je B1 tisíc tun za rok, pro druhou vrstvu - B2 tisíc tun za rok. Podle technologie práce nemůže výroba z druhé vrstvy převýšit výrobu z první vrstvy. Těžba lomu přes důl by neměla překročit 1 tis. tun ročně. Celkové zatížení dvou vrstev za rok by nemělo být nižší než C2 tisíce tun za rok. Vytvořte matematický model a sestavte sadu hodnot přípustného zatížení pro první a druhou vrstvu za rok.
Příklad č. 3. Prodejna prodává 2 druhy nealko nápojů: Colu a limonádu. Příjem z jedné plechovky coly je 5 centů, zatímco příjem z jedné plechovky limonády je 7 centů. V průměru prodejna neprodá více než 500 plechovek obou nápojů denně. Navzdory tomu, že kolu vyrábí známá značka, zákazníci preferují limonádu, protože je mnohem levnější. Odhaduje se, že objem prodeje koly a limonády by měl mít poměr minimálně 2:1, navíc je známo, že obchod prodá minimálně 100 plechovek coly denně. Kolik plechovek každého nápoje by měl mít obchod na začátku dne, aby maximalizoval výnos?
Příklad č. 4. Úlohu lineárního programování vyřešte přibližně graficky, následovanou výpočtem přesné hodnoty a max(min) hodnoty účelové funkce.
Příklad č. 5. Cestovní společnost nepožaduje více než třítunové autobusy a ne více než pětitunové autobusy. Prodejní cena autobusů první značky je 20 000 USD, druhé značky 40 000 USD. Cestovní společnost může na nákup autobusů vyčlenit maximálně 1 $. Kolik autobusů každé značky je třeba zakoupit samostatně, aby jejich celková (celková) přepravní kapacita byla maximální. Vyřešte problém graficky.
Příklad č. 6. Grafickou metodou najděte optimální plán výroby v úloze dané tabulkou.
Příklad č. 7. Řešte problém lineárního programování graficky a podrobte systém omezení problému Jordan-Gaussovým transformacím. Systém omezení problému má tvar:
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
Směrnice. Jordano-Gaussovy transformace lze provádět pomocí této služby nebo prostřednictvím studie SLAE.
Příklad č. 8. Společnost vyrábí dva druhy výrobků A a B, k jejichž výrobě se používají tři druhy surovin. K výrobě jednotky produktu A je nutné utratit suroviny každého typu a1, a2, a3 kg, v tomto pořadí a na jednotku produktu B - b1, b2, b3 kg. Výroba je zajišťována surovinami každého druhu v množství P1, P2, P3 kg, resp. Náklady na jednotku produktu A jsou C1 rub. a náklady na jednotku produktu B jsou C2 rub. Pro výrobky A a B je nutné vypracovat plán výroby, který zajistí maximální cenu hotového výrobku.
Příklad č. 2. Je nutné najít maximální hodnotu účelové funkce F = 4X + 6y→ max, se systémem omezení:
Vytvořme oblast proveditelných řešení, tzn. Vyřešme soustavu nerovnic graficky. K tomu vybereme počet omezení rovný 4 (obrázek 1). 
Obrázek 1
Poté vyplníme koeficienty pro proměnné a samotná omezení (obrázek 2). 
Obrázek 2 
Obrázek 3
X= 12 – rovnoběžně s osou OY;
y= 9 – rovnoběžně s osou VŮL;
X> = 0 – osa OY
y= 0 – osa VŮL;
X≥ 0 – polorovina vpravo od osy OY;
y≥0 – polorovina nad osou VŮL;
y≤ 9 – polorovina níže y = 9;
X≤ 12 – polorovina vlevo X = 12;
0,5X + y≤ 12 – polorovina pod přímkou 0,5 X + y = 12;
X + y≤ 18 – polorovina pod přímkou X + y = 18.
Průsečíkem všech těchto polorovin je pětiúhelník ABCDE, s vrcholy v bodech A(0; 0), B(0;9), C(6; 9), D(12;6), E(12;0). Tento pětiúhelník tvoří oblast proveditelných řešení problému. 
Zvažte objektivní funkci problému F = 4X + 6y→ max.
|
X |
3 |
0 |
|
y |
–2 |
0 |
Sestrojme přímku odpovídající hodnotě funkce F = 0: 4X + 6y= 0. Tuto přímku posuneme paralelně. Z celé rodiny řad 4 X + 6y= const poslední vrchol, kterým čára projde při opuštění hranice polygonu, bude vrcholem S(12; 6). Je v něm F = 4X + 6y dosáhne své maximální hodnoty. 
Takže když X = 12, y= 6 funkcí F dosáhne své maximální hodnoty F= 4 ∙ 12 + 6 ∙ 6 = 84, rovná se 84. Bod se souřadnicemi (12;6) splňuje všechny nerovnosti systému omezení a v něm je hodnota účelové funkce optimální. F* = 84.
Test v oboru "Operační výzkum"
(správné odpovědi jsou první)
1. Objevil se termín „operační výzkum“...
za druhé světové války
v 50. letech XX století
v 60. letech XX století
v 70. letech XX století
v 90. letech XX století
na počátku 21. století
2. Operační výzkum se týká (vyberte nejvhodnější možnost) ...
soubor vědeckých metod pro řešení problémů efektivního řízení organizačních systémů
soubor opatření přijatých k provedení určitých operací
soubor metod pro realizaci plánu
vědecké metody alokace zdrojů při organizaci výroby
3. Uspořádejte fáze, kterými obvykle prochází jakýkoli operační výzkum:
formulace problému
konstrukce smysluplného (verbálního) modelu uvažovaného objektu (procesu).
sestavení matematického modelu
řešení problémů formulovaných na základě sestrojeného matematického modelu
kontrola, zda získané výsledky odpovídají povaze studovaného systému
implementace získaného řešení do praxe
4. Operace znamená v operačním výzkumu...
jakákoli událost (systém akcí) spojená jediným plánem a zaměřená na dosažení cíle
jakákoli neovlivnitelná událost
soubor technických opatření k zajištění výroby spotřebního zboží
5. Řešení se nazývá optimální...
pokud je z toho či onoho důvodu výhodnější než ostatní
pokud je to racionální
pokud je to dohodnuto s úřady
pokud to schválí valná hromada
6. Matematické programování...
se zabývá studiem extremálních problémů a vývojem metod jejich řešení
je proces tvorby počítačových programů pod vedením matematiků
řeší matematické úlohy na počítači
7. Problém lineárního programování je...
nalezení největší (nejmenší) hodnoty lineární funkce za přítomnosti lineárních omezení
vytvoření lineárního programu ve zvoleném programovacím jazyce určeného k řešení daného problému
popis lineárního algoritmu pro řešení daného problému
8. V problému kvadratického programování...
účelová funkce je kvadratická
plocha možného řešení je čtverec
omezení obsahují kvadratické funkce
9. V problémech celočíselného programování...
neznámé mohou nabývat pouze celočíselné hodnoty
cílová funkce musí nutně mít celočíselnou hodnotu a neznámé mohou být libovolné
účelová funkce je číselná konstanta
10. V úlohách parametrického programování...
cílová funkce a/nebo systém omezení obsahuje parametr(y)
oblastí možných řešení je rovnoběžník nebo rovnoběžnostěn
počet proměnných může být pouze sudý
11. V problémech dynamického programování...
proces hledání řešení je vícestupňový
výrobu dynamitu je třeba racionalizovat
potřeba optimalizovat použití reproduktorů
12. Vznikl následující problém lineárního programování:
F(X 1, X 2) = 5X 1 + 6X 2→ max
0.2X 1 + 0.3X 2 ≤ 1.8,
0.2X 1 + 0.1X 2 ≤ 1.2,
0.3X 1 + 0.3X 2 ≤ 2.4,
X 1 ≥ 0, X 2 ≥ 0.
Vyberte úkol, který je ekvivalentní tomuto úkolu.
F(X 1, X 2)= 5X 1 + 6X 2 → max,
2X 1 + 3X 2 ≤ 18,
2X 1 + X 2 ≤ 12,
X 1 + X 2 ≤ 8,
X 1 ≥ 0,
X 2 ≥ 0.
F(X 1, X 2)= 6X 1 + 5X 2 → min,
2X 1 + 3X 2 ≤ 18,
2X 1 + X 2 ≤ 12,
X 1 + X 2 ≤ 8,
X 1 ≥ 0,
X 2 ≥ 0.
F(X 1, X 2)= 50X 1 + 60X 2 → max,
2X 1 + 3X 2 ≤ 18,
2X 1 + X 2 ≤ 12,
X 1 + X 2 ≤ 8,
X 1 ≥ 0,
X 2 ≥ 0.
F(X 1, X 2)= 5X 12 + 6X 22 → max,
2X 1 + 3X 2 ≤ 18,
2X 1 + X 2 ≤ 12,
3X 1 + X 2 ≤ 2.4,
X 1 ≥ 0,
X 2 ≥ 0.
13. Cílovou funkcí úlohy lineárního programování může být funkce:
F=12x1+20x2–3 0x3→min
F= →min
F=
→max
F=→max.
14. Systém omezení pro problém lineárního programování může být následující systém:
15. Simplexová metoda je:
analytická metoda pro řešení základní úlohy lineárního programování
způsob hledání oblasti proveditelných řešení problému lineárního programování;
grafická metoda řešení hlavního problému lineárního programování;
metoda pro redukci obecného problému lineárního programování na kanonickou formu.
16. Problém lineárního programování je:
nalezení největší nebo nejmenší hodnoty lineární funkce za přítomnosti lineárních omezení
vývoj lineárního algoritmu a jeho implementace na počítači
sestavování a řešení soustavy lineárních rovnic
hledání lineární trajektorie vývoje procesu popsaného daným systémem omezení.
17. Oblast možných řešení úlohy lineárního programování nemůže vypadat takto:
18. Cílovou funkcí úlohy lineárního programování může být funkce:
F=12x1+20x2–3 0x3→min
F= →min
F=→max
F=→max.
19. Systém omezení pro problém lineárního programování může být systém:
20. Oblast proveditelných řešení problému lineárního programování má tvar:
F(X 1, X 2)= 3X 1 + 5X 2 se rovná...
21. Oblast proveditelných řešení problému lineárního programování má tvar:
Potom maximální hodnota funkce F(X 1, X 2)= 5X 1 + 3X 2 se rovná...
22. Oblast proveditelných řešení problému lineárního programování má tvar:
Potom maximální hodnota funkce F(X 1, X 2)= 2X 1 - 2X 2 se rovná...
23. Oblast proveditelných řešení problému lineárního programování má tvar:
F(X 1, X 2)= 2X 1 - 2X 2 se rovná...
24. Oblast možných řešení problému nelineárního programování má tvar:
Potom maximální hodnota funkce F(X 1, X 2)= X 2 – X 12 se rovná...
25. Maximální hodnota účelové funkce F(X 1, X 2)= 5X 1 + 2X 2 s omezeními
X 1 + X 2 ≤ 6,
X 1 ≤ 4,
X 1 ≥ 0, X 2 ≥ 0, rovná se...
26. Malý podnik vyrábí dva druhy výrobků. Výroba jednoho výrobku typu A vyžaduje 2 kg surovin a výroba jednoho výrobku typu B 1 kg. Celkem jde o 60 kg surovin. Je třeba sestavit plán výroby, který zajistí příjem největšího výnosu, pokud prodejní cena jednoho výrobku typu A je 3 kč, typ B - 1 kč. To znamená, že není požadováno více než 25 výrobků typu A a ne více než 30 výrobků typu B.
Tento úkol je...
problém lineárního programování
problém řešený metodou dynamického programování
problém s plánováním sítě.
27. Malý podnik vyrábí dva druhy výrobků. Výroba jednoho výrobku typu A vyžaduje 2 kg surovin a výroba jednoho výrobku typu B 1 kg. Celkem jde o 60 kg surovin. Je třeba sestavit plán výroby, který zajistí příjem největšího výnosu, pokud prodejní cena jednoho výrobku typu A je 3 kč, typ B - 1 kč. To znamená, že není požadováno více než 25 výrobků typu A a ne více než 30 výrobků typu B.
Objektivní funkcí tohoto problému je funkce...
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ábí dva druhy výrobků. Výroba jednoho výrobku typu A vyžaduje 2 kg surovin a výroba jednoho výrobku typu B 1 kg. Celkem jde o 60 kg surovin. Je třeba sestavit plán výroby, který zajistí příjem největšího výnosu, pokud prodejní cena jednoho výrobku typu A je 3 kč, typ B - 1 kč. e. a výrobků typu A musí být vyrobeno ne více než 25 a typu B - ne více než 30
Platný plán pro tento úkol je plán:
X=(20, 20)
X=(25, 15)
X=(20, 25)
X=(30, 10)
29. Ve dvou bodech A1 a A2 je 60 a 160 jednotek zboží. Veškeré zboží musí být přepraveno do bodů B1, B2, B3 v množství 80, 70 a 70 kusů. Tarifní matice je následující: . Naplánujte si dopravu tak, aby její náklady byly minimální.
Tento úkol je...
dopravní úkol
problém nelineárního programování
problém cestujícího prodejce
problém zadání
30. Ve dvou bodech A1 a A2 je 60 a 160 jednotek zboží. Veškeré zboží musí být přepraveno do bodů B1, B2, B3 v množství 80, 70 a 70 kusů. Tarifní matice je následující: . Naplánujte si dopravu tak, aby její náklady byly minimální
Základním plánem pro tento úkol je plán:
;
31. Ve dvou bodech A1 a A2 je 60 a 160 jednotek zboží. Veškeré zboží musí být přepraveno do bodů B1, B2, B3 v množství 80, 70 a 70 kusů. Tarifní matice je následující: . Naplánujte si dopravu tak, aby její náklady byly minimální.
Cílovou funkcí tohoto problému je funkce:
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. Ve dvou bodech A1 a A2 je 60 a 160 jednotek zboží. Veškeré zboží musí být přepraveno do bodů B1, B2, B3 v množství 80, 70 a 70 kusů. Tarifní matice je následující: . Naplánujte si dopravu tak, aby její náklady byly minimální.
Optimální plán pro tento problém je plán:
;
.
;
;
33. Dopravní problém
bude zavřeno, pokud...
34. Dopravní problém
je…
OTEVŘENO
ZAVŘENO
neřešitelný
35. Dopravní problém
je…
ZAVŘENO
OTEVŘENO
neřešitelný
36. K vyřešení následujícího dopravního problému
potřeba vstoupit...
fiktivního spotřebitele
fiktivní dodavatel;
efektivní tarif
37. Řešení následujícího dopravního problému
potřeba vstoupit...
fiktivní dodavatel;
fiktivního spotřebitele
efektivní tarif
efektivní úroková sazba.
38. Mezi tyto dopravní úkoly
jsou zavřené...
39. Počáteční referenční plán pro dopravní problém lze vypracovat...
všechny výše uvedené metody
metoda severozápadního rohu
metoda minimálního tarifu
metoda dvojité preference
Vogelova aproximační metoda
40. Je-li účelová funkce problému lineárního programování nastavena na maximum, pak... je cílová funkce duálního problému nastavena na minimum
V duálním problému není žádná cílová funkce
duální problém nemá řešení
duální problém má nekonečně mnoho řešení
41. Daný problém lineárního programování:
F(X 1, X 2)= 2X 1 + 7X 2 → max,
2X 1 + 3X 2 ≤ 14,
X 1 + X 2 ≤ 8,
X 1 ≥ 0, X 2 ≥ 0.
Duální pro tento problém je následující...
F*(y1, y2)= 14y1 + 8y2 → min,
3r 1 + y2 ³ 7,
y 1 ≥ 0, y2 ≥ 0.
F*(y1, y2)= 2y1 + 7y2 → min,
2y1 + 3y2 ³ 14,
y 1 + y2 ³ 8,
y 1 £ 0, y2 £ 0.
F*(y1, y2)= 2y1 + 7y2 → min,
3 y 1 + y2 ³ 7,
y 1 £ 0, y2 £ 0.
F*(y1, y2)= 14y1 + 8y2 → min,
y 1 + y2 ³ 7,
y 1 ≥ 0, y2 ≥ 0.
42. Pokud má jeden z dvojice duálních problémů optimální plán, pak...
a druhý má optimální plán
ten druhý nemá optimální plán
ten druhý nemá žádné proveditelné řešení
43. Pokud má jeden z dvojice duálních problémů optimální plán, pak...
a druhý má optimální plán a hodnoty cílových funkcí s jejich optimálními plány jsou si navzájem rovné
a druhý má optimální plán, ale hodnoty cílových funkcí pro jejich optimální plány se navzájem nerovnají
jiný problém nemusí mít optimální plán, ale má proveditelná řešení
44. Není-li účelová funkce jednoho z dvojice duálních problémů omezená (pro maximální problém – shora, pro minimální problém – zdola), pak
druhý úkol nemá žádné platné plány
jiný problém má proveditelné plány, ale nemá optimální plán
objektivní funkce druhého úkolu je rovněž neomezená
45. Při řešení některých problémů nelineárního programování,...
Lagrangeova multiplikační metoda
Gaussova metoda
Metoda Vogelovy aproximace
Gomoriho metoda
46. Je dán problém nelineárního programování
F(X 1, X 2)= X 12 + X 22 → max,
X 1 + X 2 =6,
X 1 ≥ 0, X 2 ≥ 0.
F(X 1, X 2) …
nedostupný (+ ¥)
47. Je uveden problém nelineárního programování
F(X 1, X 2)= X 12 + X 22 → mv,
X 1 + X 2 =6,
X 1 ≥ 0, X 2 ≥ 0.
F(X 1, X 2) …
48. Je uveden problém nelineárního programování
F(X 1, X 2)= X 12 + X 22 → max,
X 1 + X 2 =6,
X 1, X 2 - libovolný.
Největší hodnota účelové funkce F(X 1, X 2) …
nedostupný (+ ¥)
49. Je uveden problém nelineárního programování
F(X 1, X 2)= X 12 + X 22 → mv,
X 1 + X 2 =6,
X 1, X 2 - libovolný.
Minimální hodnota účelové funkce F(X 1, X 2) …
nedostupný (- ¥)
50. Oblast proveditelných řešení problému nelineárního programování má tvar:
Potom maximální hodnota funkce F(X 1, X 2)= X 12 +X 22 se rovná...
51. Oblast proveditelných řešení problému nelineárního programování má tvar:
Potom minimální hodnota funkce F(X 1, X 2)= X 12 +X 22 se rovná...
52. K vyřešení dopravního problému lze použít...
potenciální metoda
Lagrangeova multiplikační metoda
Gaussova metoda
dezorientační metoda
53. V systému omezení obecného problému lineárního programování...
54. V systému omezení standardního (symetrického) problému lineárního programování...
mohou být přítomny pouze nerovnosti
mohou být přítomny jak rovnice, tak nerovnice
mohou být přítomny pouze rovnice
55. V systému omezení kanonického (hlavního) problému lineárního programování...
mohou být přítomny pouze rovnice (za předpokladu, že proměnné nejsou záporné)
mohou být přítomny pouze nerovnosti (za předpokladu, že proměnné nejsou záporné)
mohou být přítomny rovnice i nerovnosti (za předpokladu, že proměnné jsou nezáporné)
56. Problém lineárního programování
F(X 1, X 2)= 2X 1 + 7X 2 → max,
2X 1 + 3X 2 ≤ 14,
X 1 + X 2 ≤ 8,
X 1 ≥ 0, X 2 ≥ 0.
zaznamenáno v...
standardní (symetrická) forma
kanonická (základní) forma
slovesný tvar
57. Chcete-li zaznamenat úkol
F(X 1, X 2)= 2X 1 + 7X 2 → max,
2X 1 + 3X 2 ≤ 14,
X 1 + X 2 ≤ 8,
X 1 ≥ 0, X 2 ≥ 0.
v kanonické podobě...
58. Chcete-li zaznamenat úkol
F(X 1, X 2)= 2X 1 + 7X 2 → max,
2X 1 + 3X 2 ≤ 14,
X 1 + X 2 ≤ 8,
X 1 + 4X 2 ≥ 10,
X 1 ≥ 0, X 2 ≥ 0.
v kanonické podobě...
musí být zavedeny tři další nezáporné proměnné
je nutné zavést dvě další nezáporné proměnné
musí být zavedeny čtyři další nezáporné proměnné
59. Chcete-li zaznamenat úkol
F(X 1, X 2)= 2X 1 + 7X 2 → max,
2X 1 + 3X 2 = 14,
X 1 + X 2 ≤ 8,
X 1 + 4X 2 ≥ 10,
X 1 ≥ 0, X 2 ≥ 0.
v kanonické podobě...
je nutné zavést dvě další nezáporné proměnné
musí být zavedeny tři další nezáporné proměnné
musí být zavedeny čtyři další nezáporné proměnné
musí být zavedeno pět dalších nezáporných proměnných
60. Při řešení úloh celočíselného programování lze použít...
Gomoriho metoda
Lagrangeova multiplikační metoda
Gaussova metoda
Metoda Vogelovy aproximace
61. Základem řešení úloh metodou dynamického programování je...
Princip Occamovy břitvy
princip „zub za zub, oko za oko“
Heisenbergův princip
62. Situace, kdy strany, jejichž zájmy jsou zcela nebo částečně protichůdné, se nazývá...
(konflikt, konflikt, konflikt, konflikt)
63. Skutečný nebo formální konflikt, ve kterém jsou alespoň dva účastníci (hráči), z nichž každý usiluje o dosažení svých vlastních cílů, se nazývá ...
(hra, hra)
64. Přípustné akce každého hráče směřující k dosažení určitého cíle se nazývají...
(pravidla hry, pravidla hry)
65. Kvantitativní hodnocení výsledků hry se nazývá...
(platba, platba, platba)
66. Pokud se hry účastní pouze dvě strany (dvě osoby), pak se hra nazývá...
(čtyřhra, čtyřhra, čtyřhra, čtyřhra)
67. Pokud je ve hře dvojic součet plateb nula, to znamená, že ztráta jednoho hráče se rovná zisku druhého, pak se hra nazývá hra...
(nulový součet)
68. Jednoznačný popis volby hráče v každé z možných situací, ve kterých musí provést osobní tah, se nazývá.
(strategie hráče, strategie hráče, strategie, strategie)
69. Pokud, když se hra mnohokrát opakuje, strategie poskytuje hráči maximální možnou průměrnou výhru (minimální možnou průměrnou prohru), pak se taková strategie nazývá ...
(optimální, optimální, optimální strategie, optimální strategie)
70. Nechť a je nižší cena ab horní cena párové hry s nulovým součtem. Pak je tvrzení pravdivé...
71. Nechť a je nižší cena ab horní cena párové hry s nulovým součtem. Pokud a = b = v, pak se číslo v nazývá...
za cenu hry
rovnovážný bod
optimální strategii
smíšená strategie
72. Nechť a je nižší cena ab horní cena párové hry s nulovým součtem. Pokud a = b, pak se hra nazývá...
sedlo bodová hra
neřešitelný konflikt
hra bez pravidel
73. Vektor, jehož každá složka ukazuje relativní frekvenci hráčského použití odpovídající čisté strategie, se nazývá ...
smíšená strategie
vodicí vektor
normální vektor
spád
74. Nižší cena maticové hry daná výplatní maticí je...
Více nižší cena
rovnající se nižší ceně
neexistuje
81. Maticová hra daná výplatní maticí, ...
má sedlový hrot
nemá sedlový hrot
ne pár
82. Cena hry daná platební maticí je…
83. Maticová hra daná výplatní maticí, ...
je parní lázeň
má sedlový hrot
ne pár
84. Hru párů s nulovým součtem, danou její výplatní maticí, lze zredukovat na...
problém lineárního programování
problém nelineárního programování
celočíselný problém lineárního programování
klasický optimalizační problém
85. Nižší cena maticové hry daná výplatní maticí je...
Více nižší cena
rovnající se nižší ceně
neexistuje
92. Maticová hra daná výplatní maticí, ...
nemá sedlový hrot
má sedlový hrot
ne pár
93. Cena hry, daná platební maticí, je v mezích...
94. Pokud v proudu událostí události následují po sobě v předem určených a přesně definovaných časových intervalech, pak se takový proud nazývá ...
pravidelný
organizovaný
95. Jestliže pravděpodobnost libovolného počtu událostí spadajících do časového intervalu závisí pouze na délce tohoto intervalu a nezávisí na tom, jak daleko se tento interval nachází od počátku času, pak se odpovídající tok událostí nazývá:
stacionární
tok bez následků
nejjednodušší
jed
96. Pokud počet událostí připadajících na jeden z libovolně zvolených časových intervalů nezávisí na počtu událostí připadajících na jiný, rovněž libovolně zvolený časový interval, za předpokladu, že se tyto intervaly neprotínají, pak se odpovídající tok událostí nazývá ...
tok bez následků
pravidelný
orientační
normální
97. Pokud je pravděpodobnost výskytu dvou nebo více událostí najednou ve velmi krátkém časovém úseku zanedbatelná ve srovnání s pravděpodobností výskytu pouze jedné události, pak se odpovídající tok událostí nazývá...
obyčejný
mimořádný
normální
jed
98. Má-li tok událostí současně vlastnosti stacionarity, obyčejnosti a absence důsledků, pak se nazývá:
nejjednodušší (Poisson)
normální
99. Jednokanálová QS s poruchami je stanice denní údržby pro mytí automobilů. Žádost – auto, které přijede v době, kdy je místo obsazeno – je odmítnuto doručit. Intenzita proudění automobilů λ=1,0 (vůz za hodinu). Průměrná doba trvání služby je 1,8 hodiny. Tok automobilů a tok služeb jsou nejjednodušší. Pak v ustáleném stavu relativní propustnost q rovnat se...
100. Jednokanálová QS s poruchami je stanice denní údržby pro mytí automobilů. Žádost – auto, které přijede v době, kdy je místo obsazeno – je odmítnuto doručit. Intenzita proudění automobilů λ=1,0 (vůz za hodinu). Průměrná doba trvání služby je 1,8 hodiny. Tok automobilů a tok služeb jsou nejjednodušší. V ustáleném stavu se pak procento aut, kterým byla služba odmítnuta, rovná...