Konvexní množiny a jejich vlastnosti. Aby bylo možné studovat vlastnosti LPP, je nutné podat přesnou definici konvexní množiny. 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 kterýmkoli ze svých dvou bodů obsahuje jejich libovolnou konvexní, lineární kombinaci.
Lze dokázat následující větu o zobrazení konvexního mnohostěnu.
Věta 1.1. Konvexní n-polytop 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ě určena svými rohovými body: žádný její 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ápis:
Tady S- řádková matice, A- matice systému, X- maticový sloupec proměnných, PROTI- maticový sloupec volných členů:
Vektorový zápis:
kde vektory odpovídají sloupcům koeficientů pro neznámé.
Následující věta byla uvedena 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ě přípustná řešení LPP uvedená v maticové formě. Potom a . Uvažujme konvexní lineární kombinaci řešení, tzn.
a ukázat, že je to také přípustné řešení systému (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 přípustných řešení úlohy lineárního programování je konvexní, přesněji řečeno představuje konvexní mnohostěn nebo konvexní mnohostěnnou oblast, kterou budeme dále nazývat jedním výrazem - mnohostěn řešení.
Odpověď na otázku, v jakém bodě polytopu řešení je možné optimální řešení úlohy 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ů polytopu řešení. Pokud lineární funkce nabývá své 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 polytop ř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-li rohový bod, pak je první část věty dokázána.
Pojďme to předstírat X * není rohový bod, pak podle 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
V tomto rozšíření volíme mezi hodnotami maximální hodnotu. Nechte to odpovídat rohovému bodu X k(1 £ k£ R); označme to tím M, ty. . 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 je to dokázáno
F (X *)£ M, tedy kde X k- rohový bod. Existuje tedy rohový bod X k 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
ty. 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 byl polytop řešení omezen ve větě, je zásadní, protože v případě neomezené polyedrické oblasti, jak je uvedeno ve větě 1.1, ne každý bod takové oblasti může být reprezentován konvexní lineární kombinací jejích rohových bodů. .
Dokázaná věta 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é zkoumat 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é přípustné základní řešení úlohy lineárního programování odpovídá rohovému bodu 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í LPP (1.4), ve kterém první T komponenta jsou hlavní proměnné a zbytek n - t složka - vedlejší 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 pointa 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 jinak bod X shoduje se s bodem X 1 nebo X 2).
Vektorovou rovnost (1.6) zapíšeme v souřadnicovém tvaru:
Protože všechny proměnné a koeficienty jsou nezáporné, pak z posledně jmenovaných p-t rovnosti z toho vyplývá, že tzn. v rozhodnutích X 1 , X 2 a X soustavy rovnic (1.4) hodnoty n - t složky jsou v tomto případě rovné nule. Tyto komponenty lze považovat za hodnoty vedlejších proměnných. Ale hodnoty vedlejších proměnných jednoznačně určují hodnoty hlavních, proto
Takže všechny 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 Je rohový bod mnohostěnu řešení.
Dokažme opačné tvrzení. Dovolit být rohový bod polytopu řešení 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 přípustných základních řešení.
Tak, optimum lineární funkce problému lineárního programování je třeba hledat mezi konečným počtem jeho přípustných základních řešení.
Je provedena optimalizace lineárních modelů v MS Excel simplexní metoda- účelný výčet podpůrných řešení úlohy lineárního programování. Algoritmus simplexové metody je redukován na konstrukci konvexního mnohostěnu ve vícerozměrném prostoru a poté na iteraci přes jeho vrcholy za účelem nalezení extrémní hodnoty. Objektivní funkce.Účinné prostředky lineární programování jsou základem celočíselného i nelineárního programování pro složitější optimalizační problémy. Tyto metody však zaberou delší dobu výpočtu.
V navazujících přednáškách budou podrobně rozebrány příklady řešení typických optimalizačních problémů a rozhodování managementu pomocí doplňku MS Excel "Hledat řešení". Úkoly, které tento nástroj nejlépe zvládne, mají tři hlavní vlastnosti:
- existuje jediný cíl, funkčně související s ostatními parametry systému, který je potřeba optimalizovat (zjistit jeho maximum, minimum, případně určitou číselnou hodnotu);
- existují omezení, obvykle vyjádřená ve formě nerovností (např. objem použitých surovin nesmí překročit zásoby surovin ve skladu nebo provozní doba stroje za den by neměla být delší než 24 hodin minus čas na službu);
- existuje sada hodnot vstupních proměnných, které ovlivňují optimalizované hodnoty a omezení.
Parametry úlohy jsou omezeny následujícími limitními hodnotami:
- počet neznámých - 200;
- počet omezení vzorce na neznámých - 100;
- počet omezujících podmínek pro neznámé je 400.
Algoritmus pro nalezení optimálních řešení zahrnuje několik fází:
- přípravné práce;
- ladění řešení;
- analýza řešení.
Posloupnost nezbytných přípravných prací prováděných při řešení úloh ekonomického a matematického modelování pomocí MS Excel ukazuje blokové schéma na obrázku 1.6.
Rýže. 1.6.
Z pěti bodů plánu přípravných prací je formalizován pouze pátý bod. Zbytek práce vyžaduje kreativitu – a různí lidé je mohou dělat různými způsoby. Pojďme si stručně vysvětlit podstatu znění bodů plánu.
Při zadávání problému jsou známy cílové koeficienty a normalizované koeficienty. V předchozím příkladu byly koeficienty tvořící účelovou funkci hodnoty normalizovaného zisku na polici typu ( 
) a jedna police typu ( 
). Normalizované koeficienty byly míry spotřeby materiálu a strojního času na polici každého typu. Matrix vypadal takto:
Kromě toho jsou hodnoty zdrojů vždy známé. V předchozím příkladu se jednalo o týdenní zásobu desek a možnost využívat strojový čas: 
, 
... V úkolech je často třeba omezit hodnoty proměnných. Proto je nutné určit spodní a horní hranici oblasti jejich změn.
V dialogovém okně optimalizačního programu "Hledat řešení" tedy musíme zadat následující cílový algoritmus:
Cílová funkce je rovna součinu vektoru požadovaných hodnot proměnných vektorem cílových koeficientů
Normalizované koeficienty pro vektor hledaných hodnot proměnných by neměly překročit hodnotu daného vektoru zdrojů
Hodnoty proměnné musí být v rámci zadaných limitů počtu počátečních prvků systému
Počet počátečních prvků systému
Počet specifikovaných typů zdrojů
Odladění řešení je nutné v případě, kdy program vydá zprávu o negativních výsledcích (obrázek 1.7):
Rýže. 1.7.
- pokud se nepodaří získat schůdné řešení, opravte model původních dat;
- pokud nebyl přijat optimální řešení poté zaveďte další omezení.
Problémy s programem optimální řešení pouze modelovat skutečný problém, nikoli řešení problému samotného. Při konstrukci modelu byly učiněny různé zjednodušující předpoklady reálné situace. To umožnilo formalizovat proces, přibližně odrážející skutečné kvantitativní vztahy mezi parametry systému a cílem. A pokud se skutečné parametry liší od těch zahrnutých v modelu, jak se změní rozhodnutí? Abychom to zjistili, před přijetím manažerského rozhodnutí je analyzováno modelové rozhodnutí.
Analýza optimální řešení, zabudovaný do programu, je konečnou fází matematického modelování ekonomických procesů. Umožňuje hloubkovou kontrolu vhodnosti modelu pro daný proces a také spolehlivost optimálního řešení. Je řízen daty optimální řešení a zprávy, které jsou vydávány v "Hledání řešení". Nevylučuje ani nenahrazuje tradiční analýzu plánu z ekonomického hlediska před přijetím rozhodnutí managementu.
Ekonomická analýza má následující cíle:
- stanovení možných důsledků v systému jako celku a jeho prvcích při změně parametru modelu;
- posouzení stability optimálního plánu vůči změnám jednotlivých parametrů problému: pokud není odolný vůči změnám většiny parametrů, klesá záruka jeho realizace a dosažení vypočítaného optima;
- provedení variantních výpočtů a získání nových variant záměru bez přeřešení problému z původního podkladu pomocí úprav.
Možné metody analýzy jsou znázorněny v diagramu na obrázku 1.8.
Po obdržení optimálního řešení je analyzováno podle obdržených zpráv. Analýza stability- studium vlivu změn jednotlivých parametrů modelu na ukazatele optimálního řešení. Limitní analýza- analýza přijatelných změn v optimálním plánu, kdy plán zůstává optimální.
Vzhledem k odpovědnosti dělat ekonomické manažerské rozhodnutí, vedoucí se musí ujistit, že přijatý optimální plán je jediný správný. K tomu je nutné na základě modelu získat odpovědi na následující otázky:
- "co když…"
- "co je potřeba k..."
Analýza k zodpovězení první otázky se nazývá variantní analýza; se nazývá analýza k zodpovězení druhé otázky řešení na míru.
Analýza variant je následujících typů:
- Parametrické- analýza, která spočívá v řešení problému pro různé hodnoty určitého parametru.
- Strukturální analýza- když se hledá řešení optimalizačního problému s jinou strukturou omezení.
- Vícekriteriální analýza- Toto je řešení problému pro různé cílové funkce.
- Analýza s podmíněnými vstupními daty- kdy výchozí data použitá při řešení problému závisí na dodržení dalších podmínek.
Po provedení analýzy by měly být výsledky prezentovány v grafické podobě a měla by být vypracována zpráva s doporučeními pro rozhodnutí s přihlédnutím ke konkrétní ekonomické situaci.
Definice... Jakékoli řešení systému omezení se nazývá přípustné řešení LPP.
Definice... Možné řešení, ve kterém účelová funkce dosáhne své maximální nebo minimální hodnoty, se nazývá optimální řešení.
Na základě těchto definic lze problém 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 LPP mají zpravidla nezáporné hodnoty ( X≥ 0, y≥ 0), takže oblast se nachází v I čtvrtině souřadnicové roviny.
Uvažujme lineární funkci F = S 1 X + S 2 y a opravit některé 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 se bude pohybovat paralelně a "stopovat" celou rovinu. Nechat D- polygon - plocha pro řešení systému 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é při průchodu polygonem na nějaké hodnotě d = d 2 s ním budeme mít poslední společný bod PROTI, zavolejme PROTI"Výstupní bod".
Je zřejmé, že objektivní funkce jeho nejmenší a největší hodnoty F=S 1 X + S 2 y dosáhne na vstupní body A a "exit" PROTI.
Vezmeme-li v úvahu, že účelová funkce nabývá optimální hodnoty na množině proveditelných řešení ve vrcholech oblasti D, lze navrhnout následující plán řešení LPP:
- vybudovat oblast řešení systému omezení;
- sestrojte přímku odpovídající účelové funkci a paralelním přenosem 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, vypočítat v nich hodnotu účelové funkce.
Při grafickém řešení LPP existují dva možné případy, které vyžadují zvláštní diskusi.
Případ 1
Obrázek 6
Při přímém pohybu S 1 X + S 2 y= d"Vstup" nebo "výstup" (jako na obrázku) se objeví na straně polygonu. K tomu dojde, pokud má mnohoúhelník strany rovnoběžné s přímkou. S 1 X+ S 2 na = d .
V tomto případě je bodů "výstupu" ("vstupu") nespočet, jmenovitě jakýkoli bod 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
Zvažte případ, kdy je rozsah přípustných hodnot neomezený.
V případě neohraničené 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 není omezena. 
Výkres
Je nutné najít maximální hodnotu účelové funkce F = 4X + 6y→ max, se systémem omezení
Sestrojme oblast proveditelných řešení, tzn. vyřešíme graficky soustavu nerovnic. K tomu sestrojíme každou úsečku a definujeme poloroviny dané 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číkem všech těchto polorovin je zjevně pětiúhelník OAVSD, s vrcholy v bodech Ó(0; 0), A(0; 9), PROTI(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 to v ní F = 4X + 6y
Proto pro X = 12, y= 6 funkcí F F= 4 ∙ 12 + 6 ∙ 6 = 84, rovno 84. Bod se souřadnicemi (12; 6) splňuje všechny nerovnosti systému omezení a hodnota účelové funkce v něm je optimální. F* = 84 (optimální hodnota bude označena "*").
Problém byl vyřešen. Je tedy nutné vyrobit 12 produktů typu I a 6 produktů typu II, přičemž zisk bude 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 také aplikovat na systémy 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 regionů budou hrát mnohostěny, které jsou průsečíkem poloprostorů.
Příklad č. 2. Důl vyvíjí dvě sloje. Výstup řezu v první vrstvě je a1%; na druhém - a2%. Maximální produkce porubu pro první vrstvu je B1 tisíc tun za rok, pro druhou vrstvu - B2 tisíce tun za rok. Podle technologie práce nemůže výroba z druhé vrstvy převýšit výrobu z první vrstvy. Výkon dolu v dole by neměl přesáhnout 1 tisíc tun ročně. Celkové zatížení dvou vrstev za rok by mělo být minimálně C2 tisíc 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, kupující preferují limonádu, protože je mnohem levnější. Odhaduje se, že prodej koly a limonády by měl být minimálně 2:1 a v obchodě je známo, že 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 s následným výpočtem přesné hodnoty a max (min) hodnoty cílové funkce.
Příklad č. 5. Cestovní kancelář požaduje maximálně třítunové autobusy a maximálně pětitunové autobusy. Prodejní cena autobusů první značky je 20 000 USD, druhé značky 40 000 USD. Cestovní kancelář nemůže na nákup autobusů přidělit více než 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. Pomocí grafické metody najděte optimální plán výroby pro úkol uvedený v tabulce.
Příklad č. 7. Řešte problém lineárního programování grafickou metodou, přičemž systém omezení problému podrobte Jordan-Gaussovým transformacím. Systém omezení problému je následující:
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... Jordan-Gaussovy transformace lze provádět pomocí této služby nebo prostřednictvím studia SLAE.
Příklad č. 8. Podnik vyrábí dva druhy výrobků A a B, k jejichž výrobě se používají tři druhy surovin. Pro výrobu jednotky produktu A je nutné utratit suroviny každého typu a1, a2, a3 kg, v tomto pořadí a pro jednotku produktu B - b1, b2, b3 kg. Výroba je zajišťována surovinami každého druhu v množství Р1, Р2, Р3 kg, resp. Cena jednotky produktu A je C1 rublů a jednotka produktu B je C2 rublů. Je nutné vypracovat plán výroby výrobků A a B, který zajistí maximální náklady na hotový výrobek.
Příklad č. 2. Je nutné najít maximální hodnotu účelové funkce F = 4X + 6y→ max, se systémem omezení:
Sestrojme oblast proveditelných řešení, tzn. vyřešíme graficky soustavu nerovnic. Chcete-li to provést, vyberte 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 |
Sestrojíme přímku odpovídající hodnotě funkce F = 0: 4X + 6y= 0. Tuto přímku posuneme paralelně. Z celé rodiny linií 4 X + 6y= const vrcholem bude poslední vrchol, kterým prochází přímka při přechodu za hranici polygonu S(12; 6). Je to v ní F = 4X + 6y dosáhne své maximální hodnoty. 
Proto pro X = 12, y= 6 funkcí F dosáhne své maximální hodnoty F= 4 ∙ 12 + 6 ∙ 6 = 84, rovno 84. Bod se souřadnicemi (12; 6) splňuje všechny nerovnosti systému omezení a hodnota účelové funkce v něm je optimální. F* = 84.
Test v oboru "Provozní výzkum"
(správné odpovědi jsou první)
1. Pojem "operační výzkum" se objevil ...
během 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 XXI století
2. Prostředky operačního výzkumu (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 koncipovaného plánu
vědecké metody alokace zdrojů v organizaci výroby
3. Uspořádejte kroky, 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
ověření získaných výsledků pro přiměřenost charakteru zkoumaného systému
implementace získaného řešení do praxe
4. Operací se v operačním výzkumu rozumí ...
jakákoli událost (systém akcí), sjednocená jediným konceptem 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 to z toho či onoho důvodu výhodnější
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 extrémní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. Úkolem 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 vybraném programovacím jazyce určeného k řešení 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 přípustných ř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
účelová funkce musí nutně nabývat celočíselné hodnoty a neznámé mohou být libovolné
cílová funkce je číselná konstanta
10. V úlohách parametrického programování ...
cílová funkce a/nebo omezující systém obsahuje parametr(y)
oblast přípustný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ý
potřeba racionalizovat výrobu dynamitu
chcete optimalizovat využ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í úlohy lineárního programování může být systém:
15. Simplexová metoda je:
analytická metoda pro řešení hlavního problému lineárního programování
způsob pro nalezení 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. Úkolem 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í úlohy lineárního programování může být systém:
20. Oblast možných řešení úlohy lineárního programování je následující:
F(X 1, X 2)= 3X 1 + 5X 2 se rovná...
21. Oblast možných řešení úlohy 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 možných řešení úlohy 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í úlohy lineárního programování má tvar:
F(X 1, X 2)= 2X 1 - 2X 2 se rovná...
24. 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 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í produkty dvou typů. Na výrobu jednoho výrobku typu A se spotřebují 2 kg surovin, na výrobu jednoho výrobku typu B - 1 kg. Celkem je 60 kg surovin. Je třeba sestavit plán výroby, který zajistí příjem nejvyšších výnosů, pokud prodejní cena jednoho výrobku typu A je 3 ks, typu B je 1 ks. To znamená, že výrobky typu A musí být vyrobeny ne více než 25 a typ B - ne více než 30.
Tento úkol je...
problém lineárního programování
problém řešený metodou dynamického programování
úkol plánování sítě.
27. Malý podnik vyrábí produkty dvou typů. Na výrobu jednoho výrobku typu A se spotřebují 2 kg surovin, na výrobu jednoho výrobku typu B - 1 kg. Celkem je 60 kg surovin. Je třeba sestavit plán výroby, který zajistí příjem nejvyšších výnosů, pokud prodejní cena jednoho výrobku typu A je 3 ks, typu B je 1 ks. To znamená, že výrobky typu A musí být vyrobeny ne více než 25 a typ B - ne více než 30.
Objektivní funkcí tohoto úkolu 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í produkty dvou typů. Na výrobu jednoho výrobku typu A se spotřebují 2 kg surovin, na výrobu jednoho výrobku typu B - 1 kg. Celkem je 60 kg surovin. Je třeba sestavit plán výroby, který zajistí příjem nejvyšších výnosů, pokud prodejní cena jednoho výrobku typu A je 3 ks, typu B je 1 ks. To znamená, že výrobky typu A musí být vyrobeny ne více než 25 a typ 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ží je potřeba dopravit do bodů B1, B2, B3 v množství 80, 70 a 70 jednotek. Tarifní matice je následující:. Naplánujte si dopravu tak, aby náklady byly minimální.
Tento úkol je...
dopravní úkol
problém nelineárního programování
problém cestujícího prodejce
úkol zadání
30. Ve dvou bodech A1 a A2 je 60 a 160 jednotek zboží. Veškeré zboží je potřeba dopravit do bodů B1, B2, B3 v množství 80, 70 a 70 jednotek. Tarifní matice je následující:. Naplánujte si dopravu tak, aby 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ží je potřeba dopravit do bodů B1, B2, B3 v množství 80, 70 a 70 jednotek. Tarifní matice je následující:. Naplánujte si dopravu tak, aby náklady byly minimální.
Cílovou funkcí tohoto úkolu 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ží je potřeba dopravit do bodů B1, B2, B3 v množství 80, 70 a 70 jednotek. Tarifní matice je následující:. Naplánujte si dopravu tak, aby náklady byly minimální.
Optimální plán pro tento úkol je plán:
;
.
;
;
33. Dopravní problém
bude zavřeno, pokud...
34. Dopravní problém
je…
otevřeno
Zavřeno
nerozpustný
35. Dopravní problém
je…
Zavřeno
otevřeno
nerozpustný
36. K vyřešení následujícího dopravního problému
musíte zadat...
fiktivního spotřebitele
fiktivní dodavatel;
efektivní tarif
37. K vyřešení následujícího dopravního problému
musíte zadat...
fiktivní dodavatel;
fiktivního spotřebitele
efektivní tarif
efektivní úroková sazba.
38. Mezi tyto dopravní úkoly
zavřené jsou...
39. Počáteční základní plán dopravního problému lze vypracovat ...
všemi výše uvedenými metodami
Metoda severozápadního rohu
metodou minimálního tarifu
metoda dvojité preference
metodou Vogelovy aproximace
40. Pokud je cílová funkce úlohy lineárního programování nastavena na maximum, pak ... je cílová funkce úlohy duální úlohy nastavena na minimum
v duálním problému není žádná objektivní funkce
duální problém nemá řešení
duální problém má nekonečně mnoho řešení
41. Je dán 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.
Následující bude pro tento úkol dvojí...
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á žádný 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í pro jejich optimální 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 jedné z dvojice duálních úloh omezena (pro maximální problém - shora, pro minimální problém - zdola), pak
jiný úkol nemá žádné platné plány
jiný úkol má proveditelné plány, ale nemá optimální plán
objektivní funkce jiného úkolu také není omezena
45. Při řešení některých problémů nelineárního programování se používá ...
Lagrangeova multiplikační metoda
Gaussova metoda
Vogelova aproximační metoda
Gomoriho metoda
46. Problém nelineárního programování je nastaven
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. Problém nelineárního programování je nastaven
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. Problém nelineárního programování je nastaven
F(X 1, X 2)= X 12 + X 22 → max,
X 1 + X 2 =6,
X 1, X 2 - libovolný.
Nejvyšší hodnota účelové funkce F(X 1, X 2) …
nedostupný (+ ¥)
49. Problém nelineárního programování je nastaven
F(X 1, X 2)= X 12 + X 22 → mv,
X 1 + X 2 =6,
X 1, X 2 - libovolný.
Nejmenší hodnota účelové funkce F(X 1, X 2) …
nedostupný (- ¥)
50. 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 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í (symetrické) úlohy 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 (základního) problému lineárního programování ...
mohou být přítomny pouze rovnice (za předpokladu, že proměnné jsou nezáporné)
mohou být přítomny pouze nerovnosti (za předpokladu, že proměnné jsou nezáporné)
mohou být přítomny rovnice i nerovnice (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ě...
je nutné zavést tři další nezáporné proměnné
je nutné zavést dvě další nezáporné proměnné
je nutné zavést č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é
je nutné zavést tři další nezáporné proměnné
je nutné zavést čtyři další nezáporné proměnné
je nutné zavést 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
Vogelova aproximační metoda
61. Jádrem řešení problémů metodou dynamického programování je ...
Occamova břitva
princip "zub za zub, oko za oko"
Heisenbergův princip
62. Situace, ve které jsou zapojeny strany, jejichž zájmy jsou zcela nebo částečně opačné, 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 z hráčů, zaměřené na dosažení určitého cíle, se nazývají ...
(pravidla hry, pravidla hry)
65. Kvantitativní hodnocení výsledků hry se nazývá ...
(platbou, platbou, platbou)
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 roven nule, 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 při vícenásobném opakování hry strategie poskytuje hráči maximální možný průměrný zisk (minimální možná průměrná ztráta), pak se taková strategie nazývá ...
(optimální, optimální, optimální strategie, optimální strategie)
70. Nechť a je nízká cena a b vysoká cena hry s nulovým součtem dvojic. Pak je tvrzení pravdivé...
71. Nechť a je nízká cena a b vysoká cena hry s nulovým součtem dvojic. 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 nízká cena a b vysoká cena hry s nulovým součtem dvojic. 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
směrový vektor
normální vektor
spád
74. Nižší cena maticové hry daná platební maticí se rovná ...
Více spodní cena
rovnající se spodní ceně
neexistuje
81. Maticová hra daná výplatní maticí, ...
má sedlový hrot
nemá sedlový hrot
nespárováno
82. Cena hry, daná výplatní maticí, je ...
83. Maticová hra daná výplatní maticí ...
je spárovaný
má sedlový hrot
nespárováno
84. Hru dvojic s nulovým součtem, danou její výplatní maticí, lze snížit 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á platební maticí je...
Více spodní cena
rovnající se spodní ceně
neexistuje
92. Maticová hra daná výplatní maticí ...
nemá sedlový hrot
má sedlový hrot
nespárováno
93. Cena hry, daná platební maticí, se pohybuje v ...
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í proud 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í proud událostí nazývá ...
tok bez následků
pravidelný
orientační
normální
97. Pokud je pravděpodobnost, že dvě nebo více událostí zasáhnou velmi krátký časový interval najednou, zanedbatelná ve srovnání s pravděpodobností pouze jedné události, pak se odpovídající proud událostí nazývá ...
obyčejný
mimořádný
normální
jed
98. Má-li tok událostí současně vlastnosti stacionarity, všednosti a absence důsledků, pak se nazývá:
nejjednodušší (Poisson)
normální
99. Jednokanálový systém s poruchami je denní čerpací stanicí pro mytí aut. Aplikace - auto, které dorazilo v okamžiku, kdy je místo obsazeno - obdrží odmítnutí služby. Průtok auta λ = 1,0 (auto za hodinu). Průměrná doba servisu je 1,8 hodiny. Tok automobilů a tok služeb jsou nejjednodušší. Pak v ustáleném stavu relativní propustnost q se rovná ...
100. Jednokanálový systém s poruchami je denní čerpací stanicí pro mytí aut. Aplikace - auto, které dorazilo v okamžiku, kdy je místo obsazeno - obdrží odmítnutí služby. Průtok auta λ = 1,0 (auto za hodinu). Průměrná doba servisu je 1,8 hodiny. Tok automobilů a tok služeb jsou nejjednodušší. Pak v ustáleném stavu je procento vozů, kterým bylo odmítnuto poskytnutí služby, ...
Obecná formulace problému lineárního programování (LPP). Příklady LPP
Lineární programování je odvětví matematiky, které studuje metody řešení extrémních problémů, které se vyznačují lineárním vztahem mezi proměnnými a lineárním kritériem optimality. Pár slov k samotnému pojmu lineární programování. Vyžaduje to správné pochopení. Programování v tomto případě samozřejmě není psaní počítačových programů. Programování by zde mělo být interpretováno jako plánování, tvorba plánů, vývoj akčního programu. Matematické problémy lineárního programování zahrnují studium specifických výrobních a ekonomických situací, které jsou v té či oné podobě interpretovány jako problémy optimálního využití omezených zdrojů. Spektrum úloh, které lze řešit metodami lineárního programování, je poměrně široké. Toto je například:
- - problém optimálního využití zdrojů při plánování výroby;
- - problém směsí (plánování složení výrobků);
- - problém hledání optimální kombinace různých typů produktů pro skladování ve skladech (řízení zásob nebo "zádahový problém");
- - dopravní úkoly (analýza umístění podniku, pohyb zboží). Lineární programování je nejrozvinutější a nejrozšířenější odvětví matematického programování (kromě toho sem patří: celočíselné, dynamické, nelineární, parametrické programování). Důvodem je následující:
- - matematické modely velkého počtu ekonomických problémů jsou lineární s ohledem na hledané proměnné;
- - tento typ problémů je v současnosti nejvíce studován. Pro něj byly vyvinuty speciální metody, s jejichž pomocí se tyto úkoly řeší, a odpovídající počítačové programy;
- - mnoho problémů lineárního programování po vyřešení našlo široké uplatnění;
- - některé problémy, které v původní formulaci nejsou lineární, se po řadě dodatečných omezení a předpokladů mohou stát lineárními nebo mohou být redukovány do takové podoby, že je lze řešit metodami lineárního programování. Ekonomický a matematický model jakéhokoli problému lineárního programování zahrnuje: objektivní funkci, jejíž optimální hodnotu (maximum nebo minimum) je třeba najít; omezení ve formě soustavy lineárních rovnic nebo nerovnic; požadavek nezápornosti proměnných. Obecně je model napsán takto:
- - Objektivní funkce:
C1x1 + c2x2 + ... + cnxn> max (min); - omezení:
a11x1 + a12x2 + ... + a1nxn (? =?) b1,
a21x1 + a22x2 + ... + a2nxn (? =?) b2
am1x1 + am2x2 + ... + amnxn (? =?) bm;
Požadavek na nezápornost:
V tomto případě jsou aij, bi, cj () dané konstanty. Problém je najít optimální hodnotu funkce (2.1) s omezením (2.2) a (2.3). Systém omezení (2.2) se nazývá funkční omezení problému a omezení (2.3) se nazývají přímé. Vektor splňující podmínky (2.2) a (2.3) se nazývá proveditelné řešení (plán) úlohy lineárního programování. Návrh, ve kterém funkce (2.1) dosáhne své maximální (minimální) hodnoty, se nazývá optimální.
Níže jsou uvedeny příklady některých typických problémů řešených pomocí metod lineárního programování. Takové úkoly mají skutečný ekonomický obsah. Nyní je pouze formulujeme z hlediska LPP a níže zvážíme způsoby řešení takových problémů.
1. Problém optimálního využití zdrojů při plánování výroby. Obecný význam úkolů této třídy je následující. Podnik vyrábí n různých produktů. Jejich výroba vyžaduje m různých druhů zdrojů (suroviny, materiály, pracovní doba atd.). Zdroje jsou omezené, jejich rezervy v plánovacím období jsou b1, b2, ..., bm konvenčních jednotek. Známé jsou také technologické koeficienty aij, které ukazují, kolik jednotek i-tého zdroje je potřeba k výrobě jednotky j-tého typu produktu (). Zisk podniku z prodeje výrobku j-tého typu se rovná cj. V období plánování zůstávají hodnoty aij, bi a cj konstantní. Je třeba vypracovat takový plán výroby, při jehož realizaci by byl zisk podniku největší. Níže je uveden jednoduchý příklad úlohy této třídy.
Firma se specializuje na výrobu hokejek a šachových setů. Každý klub generuje společnosti zisk 2 dolary a 4 dolary za každou šachovou sadu. Výroba jednoho klubu v lokalitě A trvá čtyři hodiny a v lokalitě B dvě hodiny. Šachová souprava se vyrábí se šesti hodinami v lokalitě A, šesti hodinami v lokalitě B a jednou hodinou v lokalitě C. Dostupná výrobní kapacita v lokalitě A je 120 Nm - hodin denně, sekce B - 72 n-hod a sekce C - 10 n-hod. Kolik klubů a šachových sad by měla společnost vyrábět denně, aby maximalizovala zisk?
Podmínky pro problémy této třídy jsou často prezentovány v tabulkové formě (viz tabulka 2.1).
Za této podmínky formulujeme problém lineárního programování. Označme: x1 - počet denně vyrobených hokejek, x2 - počet denně vyrobených šachových sad. znění ZLP:
4x1 + 6x2? 120,
Zdůrazněme, že každá nerovnost v systému funkčních omezení odpovídá v tomto případě jednomu či druhému místu výroby, a to: první místu A, druhé místu B a třetí místu C.
Systém proměnných v problematice optimalizace struktury osevních ploch s přihlédnutím k osevním postupům
