Úlohy lineárního programování
• kapacitní problém (maximalizace zisku nebo minimalizace nákladů)
• problém optimálního rozmístění finančních prostředků (maximalizace výnosu nebo minimalizace
• výživový (nutriční, směšovací) problém (minimalizace nákladů)
• řezný (krájecí) problém (maximalizace vytvořených kusů nebo minimalizace odpadu)
• distribuční problém
• Přípustné řešení – je takový vektor řešení, který vyhovuje všem omezujícím podmínkám, v typické
• Bázické řešení – má-li úloha přípustné řešení pak má i řešení bázické (podmnožinou přípustných
• Nedegerované bázické řešení – počet kladných složek v BŘ = m (počet omezujících podmínek)
• Degenefované bázické řešení – počet kladných složek v BŘ < m (počet omezujících podmínek)
• Optimální řešení – přípustné řešení úlohy, ve kterém hodnota účelové funkce vykazuje extrémní
rizika)
příkladě existuje nekonečně velké množství takových řešení
řešení), takové přípustné řešení úlohy které obsahuje maximální m (počet omezujících podmínek)
kladných složek
velikost, má- li úloha optimální řešení musí mít i bázické
o Množina K – konvexní polyedr (ohraničená konvexní množina), neohraničená konvexní
mnohohranná množina, prázdná množina (jednotlivé omezení si odporují)
DUALITA V LINEÁRNÍM PROGRAMOVÁNÍ:
• Ke každé úloze LP lze sestavit duální úlohu, původní je označována za primární, mezi oběma
• Vztah mezi souměrně sdruženými úlohami
• Vztah mezi nesouměrně sdruženými úlohami
úlohami existuje symetrický vztah
o účelová funkce v PÚ maximalizační v DÚ je minimalizační (a naopak)
o počet vlastních omezujících podmínek v PÚ je počet strukturních proměnných y v DÚ
o počet strukturních proměnných x v PÚ je počet vlastních omezujících podmínek v DÚ
o koeficienty účelové funkce z v PÚ se v DÚ objevují jako hodnoty pravých stran vlastních
omezujících podmínek a naopak
o je-li účelová funkce g minimalizační musí DÚ mít všechny relace větší nebo rovno
o je-li účelová funkce z maximalizační musí PÚ mít všechny relace menší nebo rovno
(obsahuje-li opačné musíme příslušné podmínky vynásobit –1)
o K takovým PÚ, jejichž omezující podmínky mají podobu nerovnic stejného typu
(maximalizační ÚF – nerovnost <=, minimalizační ÚF – nerovnost >=)
o Jestliže se vyskytuje v omezujících podmínkách rovnice lze ji převést na 2 nerovnice, poté se
ale některé dvě duální proměnné vztahují k jedné podmínce a tudíž musí být stejně označeny
jen s odlišením + a –, pro tuto duální proměnnou neplatí podmínky nezápornosti
o primární úloha musí být ve standardním tvaru: všechny vlastní omezující podmínky jsou
rovnice
o pro duální proměnné neplatí podmínky nezápornosti
účelových funkcí jsou stejné
nemá přípustné řešení
řešení
VĚTY O DUALITĚ
• má-li jedna ze sdružených úloh optimální řešení má optimální řešení i druhá z dvojice, hodnoty
• jestliže jedna z dvojice má přípustné řešení, ale optimální je v nekonečnu, pak druhá z dvojice úloh
• jestliže jedna z dvojice nemá přípustné řešení, pak druhá z dvojice úloh nemá konečné optimální
PRINCIP SIMPLEXOVÉ METODY:
• nalezení výchozího bazického řešení
• testování výchozího bazického řešení a dalších bazických řešení
• podle výsledku testu
• přecházíme k jinému bazickému řešení
• znovu otestujeme
• návrat k bodu 3
KANONICKÝ TVAR:
o řešení končí, pokud je test optimality splněn
o řešení pokračuje, pokud test splněn nebyl
• využívá se při výpočtu pomocí simplexové metody
• lze získat ze standardního tvaru elementárními úpravami vlastních omezujících podmínek (vytvoření
• přidáváme umělé proměnné
• koeficienty umělých proměnných jsou v ÚF +M (minimalizační ÚF), -M (maximalizační ÚF)
OPTIMÁLNÍ ŘEŠENÍ:
• maximalizační úloha – platí-li pro všechny nebazické proměnné (v indexním řádku) ∆j>=0 a pro
• minimalizační úloha – platí-li pro všechny nebázické proměnné ∆j<=0 a pro všechny bázické
• jestliže v optimálním bázickém řešení úlohy pro některou z nebázických proměnných platí ∆j=0 tzn.
ZAŘAZENÍ DO BÁZE, VYŘAZENÍ Z BÁZE
• Existuje-li nějaká proměnná, pro kterou se test optimality nesplňuje – existuje jiné bázické řešení
• maximalizační úloha – zařadíme do báze takovou proměnou, která splňuje min∆j pro ∆j<0 a
• minimalizační úloha – zařadíme do báze takovou proměnou, která splňuje max∆j pro ∆j>0 a
ŘEŠENÍ ÚLOH:
• jedno bázické optimální řešení – test optimality je splněn, hodnoty ∆j=0 v indexním řádku výsledné
• více bazických a nekonečně mnoho nebázických řešení – test optimality splněn, hodnoty ∆j=0
• jedno bázické optimální řešení a nekonečně mnoho nebázických řešení – test optimality je splněn
• nemá konečné optimální řešení – test není splněn a nelze určit klíčový řádek
• nemá žádné přípustné řešení – test optimality je splněn ale v bázi zůstala umělá proměnná pro kterou
čtvercové jednotkové submatice)
o = … + umělá proměnná
o >= … + umělá proměnná
všechny bázické proměnné ∆j=0
proměnné ∆j=0
úloha má více bazických a nekonečně mnoho nebázických optimální řešení
s lepší hodnotou účelové funkce
vyřadíme z báze min β/α pro α>0, kde β jsou hodnoty pravých stran a α koeficienty strukturních
proměnných v určitém řádku
vyřadíme z báze min β/α pro α>0
ST jsou pouze pod bázickými proměnnými
v indexním řádku ST jsou i pod nebázickými proměnnými
hodnoty ∆j=0 v indexním řádku výsledné ST jsou i pod některou nebázickou proměnou, chceme- li
však tuto nebázickou proměnou zařadit do báze, nelze určit, kterou z báze vyřadit
platí x větší jak nula
VZTAHY UVNITŘ ST:
• Stínové ceny
• Redukované ceny
o indexní čísla pod doplňkovými nebo umělými proměnnými
o poskytují informace o tom, kolik jednotek hodnoty ÚF připadá na 1 jednotku pravé strany i-
té vlastní omezující podmínky
o umožňují uvažovat o dopadech změn pravých stran jednotlivých VOP
o koeficient příslušející strukturním proměnným – indexní čísla pod strukturními proměnnými
o vyjadřují míru výhodnosti jednotlivých procesů
DUÁLNÍ SIMPLEXOVÁ METODA
• Je splněna nezápornost – ve vektoru pravých stran se nemůže vyskytnout záporná hodnota
• Primárně přípustná báze – vektor pravých stran je nezáporný
• Báze duálně nepřípustná – nesplňuje test optimality
• Báze duálně přípustná – splňuje test optimality
• Primární simplexová metoda – báze primárně přípustná a duálně nepřípustná
• Duální simplexová metoda
o báze primárně nepřípustná a duálně přípustná
o maximalizační úloha – všechny koeficienty ÚF záporná hodnota
o minimalizační úloha – všechny koeficienty ÚF kladná hodnota
o při zlepšování báze nejdříve určujeme klíčový řádek (nejmenší hodnota z vektoru pravých
stran) a poté teprve klíčový sloupec (min |∆j/αj, pro α<0|)
VÍCEKRITERIÁLNÍ LINEÁRNÍ OPTIMALIZACE
• Při řešení úlohy je přihlíželo k více kritériím
• Řešení by mělo vyhovovat co nejlépe několika hodnotícím hlediskům – kompromisní řešení
• Metody
o metoda agregace dílčích účelových funkcí
o metoda změny dílčí účelové funkce na vlastní omezující podmínky
o metoda minimalizace „odchylkové funkce“
METODA AGREGACE DÍLČÍCH ÚČELOVÝCH FUNKCÍ
• Vytvoření ze všech dílčích účelových funkcí jednu funkci agregovanou
o Pro zachování poměru se používá geometrický průměr stejnolehlých koeficientů všech
dílčích funkcí – např. √c1*c2,
o Zdůraznění váhy některé funkce – 3√c1*c2 *c2
3√c1*c2 *c3 …
• Po odmocnění řešíme simplexovou metodou
• Použití poze pro případy, kdy všechny koeficienty jsou kladná čísla
METODA ZMĚNY DÍLČÍ ÚČELOVÉ FUNKCE NA VLASTNÍ OMEZUJÍCÍ PODMÍNKY
• Vypočteme monokriterální optimální řešení pro všechny dílčí ÚF
• Jednu z dílčích ÚF označíme za superfunkci
• Výpočet optimálního řešení superfunkce dosadíme do všech ostatních ÚF
• Nová omezující podmínka – LS = dílčí ÚF, PS = hodnota z <výsledek po dasazení superfunkce,
METODA MINIMALIZACE „ODCHYLKOVÉ FUNKCE“
• Hledání kompromisního řešení při kterém by se dílčí ÚF co nejméně odchylovali od svých
• Vypočteme monokriterální optimální řešení pro všechny dílčí ÚF
• Zformulujeme přidruženou úlohu rozšířenou o jednu proměnnou a nové omezující podmínky
monokriterální výsledek>
monokriterálních optimálních řešení
o Minimalizujeme novou proměnnou
o Omezující podmínky vytvoříme z ÚF a novou proměnnou buď přičítáme (ÚF byla
maximalizační a platí relace >=) nebo odečítáme (ÚF minimalizační a relace <=)
• Přidruženou úlohu řešíme simplexovou metodou
CÍLOVÉ PROGRAMOVÁNÍ
• Problémy, ve kterých je třeba hledat řešení, které by co nejlépe vyhovovalo několika současně
• Pro tyto cíle jsou stanovené žádoucí cílové hodnoty
• V těchto úlohách do jisté míry mizí rozdíl mezi účelovou funkcí a vlastní omezující podmínkou
• Dva druhy omezení:
uplatňovaných požadavkům, cílům
o vlastní omezující podmínky (tvrdé omezení) – dodržování je bezpodmínečně nutné
o cílové omezující podmínky (měkké omezení) – hodnoty k nimž je žádoucí se přiblížit,
hledáme takové řešení, které se maximálně přiblíží těmto hodnotám, obykle přidávány
odchylkové proměnné o+ (kladná odchylka) a o- (záporná odchylka), pro tyto odchylky platí
podmínky nezápornosti a vždy alespoň jedna musí být rovna nule
velikost minimalilzujeme
• V ÚF se objevují ty odchylkové proměnné, které můžeme chápat jako nežádoucí a proto jejich
• V ÚF výskyt jen kladných odchylkových proměnných – snaha o přiblížení shora – náklady atd.
• V ÚF výskyt jen záporných odchylkových proměnných – snaha o přiblížení směrem dolů – výnosy
• Řešíme postupně podle stupně priority pomocí simplexové metody
o V modelu jsou všechny VOP a cílová omezující podmínka s nejvyšší prioritou
o V ÚF jsou všechny strukturní proměnné a odchylkové proměnné s nejvyšší prioritou
o Odchylková proměnná, která má být minimalizována má koeficient 1, ostatní 0
o V dalším kroku vypustíme proměnnou, kterou jsme se snažili minimalizovat a zařadíme
další cílovou podmínku…
CELOČÍSELNÉ PROGRAMOVÁNÍ
• Uplatňováno navíc ještě další omezení a to požadavek celočíselnosti
• Ten se vztahuje buď na všechny nebo jen na některé proměnné v daném modelu
• Tři typy úloh:
• Můžeme získat řešení – optimální celočíselné, celočíselné přípustné neoptimální, nepřípustné řešení
• Metody
o ryze celočíselné – všechny strukturní proměnné měly celočíselnou hodnotu
o smíšené celočíselné – u části proměnných je požadovaná celočíselnost u části není
o Bivalentní – proměnné mohou mít pouze dvě hodnoty 0 nebo 1
o Kombinatorické
o Řezných nadrovin
o Speciální
KOMBINATORICKÉ METODY
• výpočet optimálního řešení úlohy pomocí simplexové metody (primární nebo duální), aniž bychom
• je-li řešení celočíselné výpočet ukončíme, v opačném případě přejdeme k následujícímu bodu
• přidáme k úloze novu vlastní omezující podmínku, která omezí množinu přípustných řešení
• opakujeme postup od bodu dva tak dlouho dokud nezískáme požadované celočíselné řešení nebo
• Řešení, ve kterém budou proměnné celá čísla – rozdělení množiny přípustných hodnost na dvě
brali v úvahu požadavky celočíselnosti
dojdeme k poznatku, že takové řešení nemá
podmnožiny, aby libovolně vybranná proměnná získala celočíselnou hodnotu (rovna nejbližšímu
vyššímu a nižššímu celému číslu)
METODY ŘEZNÝCH (SEČNÝCH) NADROVIN
• výpočet optimálního řešení úlohy pomocí simplexové metody (primární nebo duální), aniž bychom
• je-li řešení celočíselné výpočet ukončíme, v opačném případě přejdeme k následujícímu bodu
• formulace vhodné omezující podmínky, která by po přidání zajistila, že z původní množiny
• Gomoryho metoda použitelná pro řešení ryze celočíselných úloh
brali v úvahu požadavky celočíselnosti
přípustných řešení bude odříznuta část přípustnách řešení a to tak, aby nebylo odděleno ani jedno
celočíselné řešení
o Optimální řešení pomocí siplexové metody
o Přidání nové VOP a řešení pomocí duální simplexové metody
Síťová analýza
Využívá graficko-analytické metody pro plánování, řízení a kontrolu složitých návazných procesů. Tyto procesy
se dají rozložit na dílčí a organizačně spolu související činnosti. Tyto procesy se nazývají v síťové analýze
projekty (výstavba budov, silnic; výzkumné úkoly; plánování zavádění informačního systému do podniku).
Matematický základ síťové analýzy je teorie grafů.
TEORIE GRAFŮ A SÍTÍ
• Grafem je neprázdná množina uzlů a neprázdná množina hran, které jsou jistým způsobem
• O shodnosti a rozdílnosti vypovídá počet uzlů a hran a způsob jejich vzájemného propojení
• Konečný počet uzlů – konečný graf, nekonečný počet uzlů – nekonečný graf
• Nulový graf – neprázdná množina uzlů, ale prázdná množina hran
• Orientované a neorientované grafy
• Stupeň uzlu – podle počtu neorientovaných hran, kterými je uzel spojen s ostatními, izovolovaný
• Souvislý graf – všechny uzly jsou vzájemně propojeny
• Komponenta grafu – ta část nesouvislého grafu, která je sama o sobě souvislá
• Polostupeň uzlu – podle počtu orientovaných hran, které do uzlu vstupují (vystupují)
• Hranově ohodnocený graf – reálná hodnota přiřazená hranám, uzlově orientovaný graf – reálná
• Symetrický graf – existuje-li ke každé hraně hij
• Neuvažujeme-li smyčky, pak maximální počet neorientovaných hran je (n × (n-1)) / 2, n…počet uzlů
• Graf s maximálním počtem hran – úplný, méně hran – neúplný
• Cesta v grafu – posloupnost navazujících orientovaných hran, jestliže cesta končí tam, kde začala,
• Multigraf – v orientovaném grafu 2 uzly s více stejně orientovanými hranami
• Rovinný graf – možno zobrazit tak, aby se jeho hrany vzájemně neprotínaly
uspořádány ve dvoj či trojrozměrném prostoru
uzel – stupeň 0, není hranou spojen s žádným jiným uzlem, vyskytuje se v nesouvislém grafu
hodnota přiřazená uzlům
nesymetrický graf
jedná se o cykluls, posloupnost navazujících neorientovaných hran – řetěz, stejný začátek a konec –
kružnice
• Strom – konečný, souvislý neorientovaný graf, který neobsahuje kružnici
• Kostra grafu – vznikne cílevědomým vypouštěním některých hran původního grafu
• Síťový graf – souvislý, konečný, orientovaný, acyklický, nezáporně ohodnocený graf s jedním
• Incidenční (vazební) matice – zachycuje existenci (1) či neexistenci (0) hran v grafu
• Počet komponent v grafu
• Uspořádaný graf – pro každou hranu hij
• Řád uzlu
• Metoda přeškrtávání hran
• Uspořádání grafu pommocí incidenční matice
• Fordův algoritmus
počátečním a jedním konečným uzlem
o Sloupec obsahující pouze nuly – počáteční uzel
o Počet 1 v řádku – počet vystupujících hran z uzlu
o Počet 1 ve sloupci – počet vstupujících hran do uzlu
o 1 na hlavní diagonále informuje o smyčce
o 1 nad hlavní diagonálou – vychází z uzlu s nižším číslem a končí v uzlu s vyšším číslem
o 1 pod hlavní diagonálou – vychází z uzlu s vyšším číslem a končí v uzlu s nižším číslem
o V případě neorientovaného grafu bez smyček jsou veškeré 1 symetricky rozmístěny kolem
hlavní diagonály
o Sestrojíme tabulku uzlů a hran
o Procházíme graf (jednotlivé hrany) a číslujeme komponenty (Ki
Kj
…Ki
o Graf budeme procházet do té doby, dokud se čísla komponent nebudou měnit
o Mezi uzly stejného řádu neexistuje hrana
o Hrany vstupující do uzlů r-tého řádu mají počátek v uzlech r-1-tého řádu
o Hrany vystupující z uzlů r-tého řádu končí v uzlech r+1-tého řádu
o Vstupní uzel má řád 0, výstupní má nejvyšší řád
o Uspořádání lze dosáhnout – proškrtáváním hran nebo fordovým algoritmem
o Vyhledáme vstupní uzel a přidělíme mu číslo 1, přeškrtáváme všechny hrany vystupující
z tohoto uzlu
o Pokud se po této úpravě objeví jeden nebo více uzlů, do kterých nevstupuje žádná
nepřeškrtnutá hrana, jedná se o uzly prvního řádu, tyto uzly očíslujeme (vzestupně) a
přeškrtáváme hrany vedoucí z těchto uzlů
o Uzlům s nepřeškrtnutou hranou opět přidělujeme čísla a pokračujeme v přeškrtávání
o Řád informuje o maximálním počtu hran, přes které se dá k uzlu dostat z nultého uzlu
o Určíme vstupní uzel – uzel nultého řádu
o Vyškrtneme řádek, který odpoídá vstupnímu uzlu a opět vyhledáváme sloupce, kde není ani
jedna 1 – uzly dalších řádů
o Přiřadíme všem uzlům grafu λ = 0, horní index je číslo kroku a dolní index označení uzlu
o Všem hranám přiřadíme neměnnou hodnotu 1
o Procházíme graf v určitém pořadí v souladu s orientací hran a přepočítáme hodnotu λ podle
vztahu λ = max (λ + 1) – řád následujícího uzlu na prvním kroku je roven maximálnímu řádu
ze všech přímopředcházejících uzlů zvýšeným o jedničku
o Končíme, když nedojde ke změně hodnot λ u žádného uzlu
o Po určení řádu je možno všechny uzly vzestupně očíslovat
o V případě, že hodnota λ je vyšší než počet uzlů – v grafu se nachází cyklus
:=Kj)
platí i < j
NEJKRATŠÍ CESTA V GRAFU
• Hledání cesty s minimální hodnotou účelové funkce
• Metoda spojená se značkováním uzlů grafu
o Značku tvoří dvě čísla – první je vzdálenost a druhé předcházející uzel
o Značky mohou být dočasné nebo definitivní
o V prvním kroku stanovýme počáteční uzel 0;P
o Označíme dočasnými značkami všechny uzly, které jsou přímo dostupně z počátečního uzlu
a vybereme ten, který má nejmenší vzdálenost od počátečního a jeho značku změníme na
definitivní
o V dalším kroku dáme dočasné značky těm uzlům, které jsou přímu spojeny s uzlem, kterému
jsme naposled udělili značku definitivní; značky dáváme tam, kde ještě žádné nejsou, nebo
když dojde ke změně (minimalizaci) vzdálenosti
o Zjistíme tak minimální cestu a seznam uzlů, přes které cesta vede
MINIMÁLNÍ KOSTRA GRAFU
• Nalezení faktoru, který je stromem s minimálním součtem hodnot hran
• Vybereme počáteční uzel a vyhledáme nejkratší hranu z něho vycházející a nový uzel označíme
• Hledáme nejkratší z hran spojující již označené uzly s neoznačenými až do propojení posledního
• Sečteme hodnoty všech n-1 označených hran, které tvoří minimální kostru
MAXIMÁLNÍ TOK V SÍTI
• V neúplném grafu s n+1 uzly platí, že jestli jeho součástí je hrana hij
• Každá nezáporná hodnota hrany určuje její možnou kapacitu
• Jestliže se skutečný průtok s kapacitou hrany rovnají, jedná se o nasycenou hranu, jestliže je průtok
• Pro vstupní a výstupní uzel grafuplatí, že součet všech toků na výstupu se rovná součtu toků na
• Největší množství přepravitelné po určité cestě je určeno tou částí cesty, která má nejmenší kapacitu
• Vybereme některou z cest v grafu s kladným tokem a stanovíme maximální možný tok realizovatelný
• Opakujeme a pokud již v grafu neexistuje žádná další cesta je úloha vyřešena
ŘÍZENÍ PROJEKTŮ
• Mezi dílčími činnostmi existují závislosti, které je nutno respektovat
• Potřebujeme zhotovit seznam dílčích činností a stanovení doby trvání, stanovení návazností a
• Projekt můžeme řešit deterministickky (bez náhodných vlivů) nebo stochasticky (s náhodnými vlivy)
• CPM (Critical Path Method, deterministická metoda), 1957, Du Pont
• PERT (Program Evaluation and Review Technique, stochastická metoda), 1958, vojenská raketa
• Síťový graf
symetrický graf
menší než kapacita – jedná se o nenasycenou hranu
vstupu
v rámci vybrané cesty a upravíme údaje o kapacitě v jednotlivých úsecích
činností, které mohou probíhat současně
METODA CPM
• Umožňuje stanovit nejkratší možnou dobu trvání, kritické činnosti i kritickou cestu a rozmítění a
• Procházíme grafem od začátku a pro všechny dílčí činnosti je nutno určit
• Stanovíme kritické činnosti (NMK = NPZ) a kritickou cestu (cesta od začátku do konce přes kritické
• Stanovení časových rezerv
o Hrany jsou dílčí činnosti a uzly časové okamžiky počátku nebo konce
o Každá dílčí činnost musí mít právě jeden počáteční a koncový uzel, jestliže tomu tak není,
třeba doplnit o fiktivní uzel nebo agregací hran
o Graf musí zobrazovat závislost dílčích činností, možno doplnit o fiktivní činnost
o Musí mít jeden počáteční a jeden koncový uzel
o Možnost zkrácení doby projektu paralelním vykonáváním prací
velikost časových rezerv
o Nejdříve možný začátek NMZ – žádná činnost nemůže začít dříve, než budou ukončeny
činnosti končící v tomto uzlu
o Nejdříve možný konec NMK – NMK = NMZ + délka trvání
o Nejpozději přípustný konec NPK – informace o tom, kdy nejpozději musí být ukončena
činnost
o Nejpozději přípustný začátek NPZ – NPZ = NPK – délka trvání
o V uzlech z nichž vystupuje pouze jedna hrana platí NPZ = PKK
o Pro rozvodný uzel vypočteme NPK jako minNPZ
činnosti)
o Jestliže je doba trvání činnosti delší než interval mezi NPK a NMZ
o Činnosti s časouvou rezervou nejsou kritické
o Časovou rezervu počítáme jako NPZ – NMZ nebo NPK – NMK