Vypracované okruhy

1. Co je to podmínka primární přípustnosti řešení?
podmínka primární přípustnosti řešení = nezápornosti proměnných (proměnná může nabývat buď 0 a nebo je větší než 0
Úlohu lineárního programování lze matematicky formulovat jako úlohu nalezení extrému (maxima nebo minima) lineární funkce více proměnných při vedlejších podmínkách vyjádřených lineárními rovnicemi nebo nerovnostmi. Protože nerovnosti lze převést na rovnice o větším počtu neznámých a řešení úloh minimalizačních na maximalizační, formulujeme obecnou úlohu lineárního programování takto:
Funkci (1.1), jejíž maximum hledáme, nazýváme účelovou funkcí.
Rovnice (1.2) jsou vlastní omezení úlohy.
Nerovnosti (1.3) se nazývají podmínkami nezápornosti .
Proměnné xi , kde i = 1,2,....,n, charakterizují objemy procesů, které se mají realizovat, má-li být daný úkol splněn.
2. Jakých hodnot může proměnná nabývat v rámci podmínky primární přípustnosti nabývat?
Proměnná může nabývat pouze kladných hodnot (nacházíme se v I. Kvadrantu). Neplatí to pro ekonomické ukazatele – ekonomické kategorie mohou nabývat i hodnot záporných.
3. Co je to antagonistická strategická hra?
Znamená když jeden vyhraje druhý prohraje. Jinak řečeno výhra jednoho se rovná prohře druhého.
V případě antagonistického konfliktu dosažení cíle jedním z účastníků zamezí pozitivnímu výsledku ostatních, úspěch každého z hráčů je možný pouze na úkor úspěšnosti ostatních hráčů.
4. Definujte jednotlivé kroky při řešení úloh lineárního programovaní
Zadání
Text zadání vede k formulaci 1) kapacitních omezujících podmínek, 2) technologických omezujících podmínek, 3)marketingových podmínek, 4) ekonomických podmínek a 5) účelové funkce.
Schéma rozhodovací situace
složí k formulaci omezujících podmínek a k ujasnění rozhodovací situace
je to účelné zhotovení grafického nákresu
Přehled proměnných
dělíme na doplňkové a umělé proměnné
Doplňkové proměnné: - značíme R+ název omezení
- mají každá svoji ekonomickou interpretaci a rozměr
- POZOR! Nejedná se vždy o rezervy
- jejich definice jsou uvedeny u formulace příslušné omez. podmínky
- Umělé proměnné: -nezobrazují se
Formulace omezujících podmínek
jedná se o bilanční podmínky – obecně bilance mezi zdrojem a spotřebou
formulace ekonomických omezujících podmínek a účelové funkce, které se tvoří podobně jako bilanční podmínky ( nerovnice, rovnice), ale ve skoutčnosti nejde o bilanci, ale pouze o sečení nákladů dílčích procesů do jedné proměnné
Zápis vytvořeného modelu do Excelu
pomocí programu Linkosa v Excelu
Optimální řešení
výsledek výpočtu programem Linkosa
nahoře na stránce nalezneme optimální hodnotu účelové funkce
v tabulce strukturních proměnných jsou označeny bazické proměnné
Matice transformovaných vektorů
matici transformace lze využít k sestavení vektoruobecného řešení a postoptimalizačním úvahám o změně optimálního při zařazení nebázické proměnné
ve sloupci báze je seznam bázických proměnných, dolpňkové proměnné mají příslušných omezujícich podmínek tj. řádků tabulky zadání názvy
5.3 Anylýza citlivosti vzhledem ke změnám vektoru pravých stran
- interval stablity řešení
- o změnách pravých stran nejčastěji uvažujeme pouze utěch omezujících podmínek, které mají nějakou reálnou pravou stranu – požadavek na omezení
- pokud dolní nehorní mez chybí rozumí se tím, že leží v nekonečnu
Analýza citlivosti vzhledem ke změnám koeficientů účelové funkce
intervaly stability řešení
při rozboru tabulky citlivosti vzhledem k cenám je třeba rozlišovat bázické (orámovavé) a nebázické proměnné
u nebázických proměnných sde vždz jen o jednu hranici intervalu stability (maximalizace – horní mez)
u bázických proměnných mohou být obě hranice intervalu stability (jedna chybí = leží v nekonečnu)
6. Charakterizujte pojem základní (bazické) řešení modelu LP
Základním (bazickým) řešením modelu LP, který obsahuje n proměnných a m omezujících podmínek (m < n), rozumíme takové řešení, ve kterém nejvýše m proměnných nabývá kladné hodnoty. Tyto proměnné označujeme jako bazické. V matici soustavy jim přísluší jednotkové vektory a nabývají hodnot odpovídající složky vektoru pravých stran. Ostatní proměnné označujeme jako nebazické a jejich hodnotu pokládáme rovnu nule.
Je dána soustava rovnic Ax = b a k ní soustava ekvivalentní v kanonickém tvaru s bazickými proměnnými x1, x2, …, xm. Soustava rovnic má v této bázi bazické řešení x0 = (β1, β2, …, βm, 0, 0, …, 0)T
Základní věta lineárního programování (LP)
Pokud má úloha LP alespoň jediné optimální řešení, potom je to řešení základní, tj. takové, které se nachází v některém z vrcholů konvexního polyedru. Základní (bazické) řešení představuje bázi.
Bazické řešení je přípustné, jestliže všechny jeho složky splňují podmínky nezápornosti. Bazické řešení je nedegenerované, jestliže obsahuje právě m kladných složek xj, to znamená, že všechny bazické proměnné jsou kladné.
7. Jaké jsou kroky Simplexové metody?
Simplexová metoda
Je to univerzální metoda typu „step by step“, tj. krokový algoritmus, kdy se k hledanému řešení přibližujeme postupně. Všechny algoritmy tohoto typu vyžadují znalost nějakého počátečního řešení (které může být i značně vzdálené od optimálního řešené); v případě simplexové metody musí být výchozí řešení bazické a nezáporné.
Přecházíme podle určitých pravidel od výchozího základního přípustného řešení dané úlohy k jiným základním přípustným řešením, která dávají lepší hodnotu účelové funkce, až do dosažení optima.
Pokud se hned v prvním kroku neukáže, že daná úloha nemá vůbec přípustné řešení, vede simplexová metoda u nedegenerovaných úloh po konečném počtu kroků buď k optimálnímu řešení nebo k výsledku, že úloha nemá optimální řešení.
Věta o změně báze a Dantzigův test optimality spolu s dantzigovou větou jsou základem simplexového algoritmu pro řešení úloh lineárního programování.
Simplexová metoda je založena na následujícím postupu:
V úloze lineárního programování se určí nějaké nezáporné bazické řešení- zpravidla to bývá nějaké výchozí řešení SOP, které vznikne při transformaci nerovnic na rovnice.
Výchozí řešení se testuje tzv. testem optimality (zj-cj- Jestliže jsou všechny rozdíly nezáporné, řešení x0 se nedá zlepšit a je optimální) a když není optimální, zlepšuje se zařazením některé nebazické proměnné. Změna báze se provádí pomocí věty o změně báze tak, aby nová byla opět nezáporná a nové řešení tedy vyhovovalo podmínkám nezápornosti úlohy.
Nově nalezené řešení považujeme za nové výchozí řešení (lepší než původní) a opakujeme krok b)
Algoritmus končí, jestliže pro všechna j platí zj-cj ≥ 0, když se tedy řešení již nedá zlepšit. Pokud má úloha lineárního programování extrém, simplexová metoda vždy vede k cíli (protože má konečný počet kroků díky existenci extrému v bazických řešeních); je to metoda velmi rychlá a úsporná i při řešení značně velkých úloh.
8) Kdy je model LP v kanonickém (bazickém) tvaru?
Když upravujeme model LP do výchozí simplexové tabulky, tak jeden z posledních kroků je převedení na kanonický tvar. Kanonický tvar musí obsahovat jednotkovou submatici a dosáhneme toho pomocí pomocné proměnné p.
Př.
Rovnicový tvar:
1/10a + 1/5b + = 1
1/5a + = 1
1/4b + = 1
2000a + 1000b - = 4000
Převedení na kanonický tvar:
1/10a + 1/5b + = 1
1/5a + = 1
1/4b + = 1
2000a + 1000b - + = 4000
Po převedení do simplexové tabulky:
 
a
b
d1
d2
d3
d4
p1
b
d1
1/10
1/5
1
0
0
0
0
1
d2
1/5
0
0
1
0
0
0
1
d3
0
1/4
0
0
1
0
0
1
p1
2000
1000
0
0
0
-1
1
4000
Červeně vidíme jednotkovou submatici, která vznikla díky převedení na kanonický tvar.
9. Co provedeme v případě, že se úloha LP nenachází v kanonickém tvaru?
Převod na kanonický tvar má dvojí smysl:
Se soustavami rovnic se dobře počítá, zejména lze provádět ekvivalentní řádkové úpravy, aniž by to mělo vliv na množinu přípustných řešení.
Úlohu v kanonickém tvaru lze mnohem jednodušeji sdělit. K zadání úlohy v kanonickém tvaru stačí zadat cenový vektor c, matici A a vektor pravých stran b.
Úloha lineárního programování je v kanonickém tvaru, jestliže:
Účelová funkce se maximalizuje ( provedeme obrácením znamínek u všech koeficientů účelové funkce)
Na všechny proměnné se klade podmínka nezápornosti
Všechny strukturní podmínky jsou typu rovnice ( tzn. „=“ )
Všechny koeficienty pravých stran jsou nezáporné
Příklad převodu úlohy na kanonický tvar:
2x1 + 3x2 → min
x1 - 2x2 ≤ 2
-2x1 + x2 ≤ 2
x1 + x2 ≥ 5
x1, x2 ≥ 0
Kvůli třem strukturním podmínkám musíme zavést tři doplňkové proměnné x3,x4,x5.
- 2x1 - 3x2 → max
x1 - 2x2 + x3 = 2
-2x1 + x2 + x4 = 2
x1 + x2 – x5 = 5
x1,….., xn ≥ 0
x3,x4 jsou s kladným znamínkem, protože v nerovnice je ≤
x5 je se záporným znamínkem, protože v nerovnici je ≥
10. Jaké typy omezení můžu stanovit u proměnných v symplexové metodě a kolik?
-u proměnných můžu stanovit 6 zákl. typů omezení:
1. rovnost (rovnice) ….. xj=bi (jednojednoznačné přiřazení)
2. kapacitní
-podmínky omezují seshora – omezení limitu (nesmím něco překročit)
<
xj = bi
n <
Σ xj = bi
j=1
n <
Σ aijxj = bi
j=1
3. požadavkové
- opakem ad 2)
- musí toho být více (nejméně tak a nebo více)
- stanovují minim. hranice požadavku j-tého procesu
>
xj = bi
n >
Σ xj = bi
j=1
n >
Σ aijxj = bi
j=1
4. bilanční
5. poměrové
6. poměrově/přípustkové ∆/∆
12. Jakou cenu připisujeme v ÚF doplňkovým a pomocným proměnným?
U pomocných proměnných je to tzv. prohibitivní cena – sazba, která algoritmicky znemožní, aby umělá pomocná proměnná vstoupila do optimální báze. Jsou obvykle řádově vyšší 10x, 100x, 1000x než běžná sazba. U minimalizačních úloh je to velmi kladná sazba, u maximalizačních úloh je to záporná sazba.
Doplňková přídatná proměnná může být buď kladná fiktivní nebo záporná fiktivní a ceny fiktivních proměnných jsou vždy 0 bez ohledu na to, zda jde o úlohu minimalizační nebo maximalizační.
13. Kdy zavádíme do modelu LP pomocnou proměnnou?
Pomocné (technické) proměnné slouží k vytvoření jednotkové submatice matice soustavy.
V účelové funkci jsou koeficienty těchto proměnných prohibitivní nebo-li nevýhodné sazby.
Nepřisuzujeme jim reálnou ekonomickou interpretaci, pokud ji přidáme k záporné fiktivní proměnné. Jestliže je výchozí podmínkou rovnice, má pomocná proměnná reálnou ekonomickou interpretaci.
Pomocné proměnné spolu s fiktivním nebo-li doplňkovými proměnnými zavádíme do modelu LP, abychom nerovnostní podmínky vyrovnaly na rovnice a úlohu tak dostaly do kanonického tvaru, který obsahuje úplnou jednotkovou matici.
Výchozí základní přípustné řešení úlohy LP musí obsahovat pouze nezáporná čísla. Toho dosáhneme tím, že k levé straně i-té rovnice soustavy přičteme nezápornou proměnnou vi, (i = 1,…,m), jejíž koeficient se rovná číslu 1. Vektory koeficientů těchto proměnných tedy tvoří kanonickou bázi, do níž patří vektory e1,…,em, takže je vlastně k matici soustavy připojena jednotková submatice. Proměnné vi se nazývají pomocné proměnné.
Ax – Eu + Ev = b, ui ≥ 0,vi ≥ 0
Kde v = (v1,…,vm)T, tj.
a11x1 + …a1nxn – u1 + v1 = b1,
--------------------------------------------------
am1x1 + …amnxn - um + vm = bm,
ui ≥ 0, vi ≥ 0, i = 1, … ,m, xj ≥ 0, j = 1, …, n.
Metoda umělé báze, tj. pomocné proměnné, použijeme také v případě, že omezující podmínky jsou formulovány jako rovnice.
Z těch řešení, pro něž jsou všechny pomocné proměnné rovny nule, je možno bezprostředně získat řešení původního modelu. Proto je nutné během výpočtu všechny pomocné proměnné vyřadit z řešení tak, aby v optimálním řešení byly všechny pomocné proměnné nezákladními, tj. aby jejich hodnoty byly nulové.
Vyřazení pomocných proměnných z výpočtu docílíme tím, že za koeficienty pomocných proměnných v účelové funkci zvolíme velmi nevýhodné číslo, které značíme obecně M a nazýváme prohibitivní sazbou (cenou). Při maximalizaci bude prohibitivní sazba záporné číslo (např. -10 000 atd.) a jsou obvykle řádově vyšší než je běžná sazba.
Při praktickém výpočtu za M dosazujeme konkrétní číslo, které můžeme přibližně určit podle vztahu:
M ≈ 10max|cj| se zaokrouhlením na např. 10 000.
j
14. Definujte strukturní (rozhodovací) proměnnou
Strukturní (rozhodovací) proměnné
vyjadřují hledanou (neznámou) úroveň reálných procesů
v účelové funkci mají reálné ceny (cj)
můžou nabývat kladných i záporných hodnot
ve výchozí simplexové tabulce jsou ve vnitřní části opsány koeficienty u proměnných ze soustavy omezujících podmínek úlohy LP
Definujte doplňkovou proměnnou.
Doplňuje nerovnice v omezujících podmínkách na rovnice. V účelových funkcí jsou koeficienty těchto proměnných vždy nulové. Mají ekonomickou interpretaci, tzn. vyjadřují buď překročení požadavku nebo nevyužití zdroje.
16. Degenerace úlohy u Simplexu = degenerace řešení u Siplexu
degenerace úlohy = degenerované řešení je takové řešení, jestliže v bázi je zařazená 1 nebo více proměnných s nulovou hodnotou
17. Pomocná (technická) proměnná:
- pouze matematický nástroj (proměnná) v úlohách lineárního programování
- v účelové funkci jsou koeficienty těchto proměnných prohibitivní (nevýhodné sazby) sazby
- nemá reálnou ekonomickou interpretaci
- slouží vytvoření jednotkové submatice matice soustavy
18. Test optimality
U simplexové metody nalezneme optimální řešení (pokud existuje) a potom provedeme test optima.
test optima / optimality:
Zj – cj ═ cTXB * αj - cj
- skalární součin vektoru cen bazických proměnných a koeficientů testované proměnné snížený o původní sazbu této proměnné.
Test optima má 3 funkce:
v každém interakčním kroku analyzuje zda nalezené řešení je již optimální, či nikoliv (zda budeme ve výpočtu pokračovat, či jde o finální stav)
určuje nově zařazené proměnné, proměnné, které vstoupí v příštím kroku do báze
př.: Z2 – C2 – jednotná změna účelové funkce v souvislosti se vstupem proměnné do báze (stanovení změny)
Naplnění těchto funkcí:
Jsme v optimu?
Musím rozlišit:
maximalizační úloha – pokud v indexu, klíči, kritériu, komparačním řešení je alespoň 1 záporná hodnota (úloha dosud není v optimu), lze nalézt lepší s vyšší hodnotou účelové funkce (-(Zj-cj))
minimalizační úloha – existuje alespoň 1 Zj kladné a ( než 0, potom lze hodnotu účelové funkce snížit ( řešení není dosud optimální)
- u nebazických proměnných se může stát, že Zj-cj=0, potom vzniká tzv. alternativní optimální řešení – řešení, které má jinou strukturu proměnných, ale má stejnou hodnotu účelové funkce
kterou proměnnou zařadíme do báze?
Max (-(Zj-cj)) – vyberu největší proměn. v absolutní hodnotě
(Z= -Xj (Zj-cj) – říká nám, jaká účelová funkce je násobkem rozsahu nově zařazené proměnné a její sazby (hodnoty) Zj-cj – používá se u maximalizace
Zmax k+1 = Zk – xj (Zj – cj)
1. interační krok
hodnota účelové fce v příštím kroku
hodnota účelové fce předchozího kroku
rozhodli jsme, že proměnná vstoupí do nové báze( test optima nám určuje nově zařazenou proměnnou, my však musíme nějakou proměnnou z báze odstranit
Dantzigův test optima
zj – cj = cxbT . αj – cj
= skalární součin vektoru cen proměnných v bázi a koeficientu zkoumané proměnné snížený o původní sazbu této proměnné
cj
reálná (pro strukturní reálné procesy)
nulová (pro fiktivní procesy)
prohibitivní (vysoká zakazující)
+ nebo – podle typu účelové funkce
19. Jaký je význam duality na jednotlivých úrovních?
Dualita je vztah mezi dvěma vektorovými prostory. V případě úloh LP se dualita projevuje takto: ke každé úloze LP se dá přířadit jiná úloha LP (duální). Obě úlohy mají tytéž parametry, ale s jinou ekonomickou interpretací.
Primární model:
max. ia.org/math/0/f/5/0f54ff7946d0869755ce6eee024304d3.png" \* MERGEFORMATINET
 INCLUDEPICTURE "http://upload.wikimedia.org/math/4/d/0/4d093b31cae4ce416fb090c5e8e6a43e.png" \* MERGEFORMATINET
Duální model:
min.  INCLUDEPICTURE "http://upload.wikimedia.org/math/a/5/4/a5492a04580691df14915d2a6b387d7a.png" \* MERGEFORMATINET
 INCLUDEPICTURE "http://upload.wikimedia.org/math/6/6/a/66a5f44d6abbe6de6a5e34f580286992.png" \* MERGEFORMATINET
Pro dvojice sdružených úloh LP platí tyto základní věty:
Má-li jeden ze sdružených modelů optimální řešení s konečnou hodnotou účelové funkce, má i druhý model optimální řešení s konečnou hodnotou účelové funkce a hodnoty obou účelových funkcí se sobě rovnají, tj. max z = min f.
Může-li hodnota účelové funkce jednoho ze sdružených problémů růst (klesat) neomezeně, pak druhý problém nemá přípustné řešení.
Ekonomické interpretace duální úlohy
Známe-li optimální řešení sdružených problémů x a yT , pak duální hodnoty yi udávají hodnoty primární účelové funkce (z(bi) při jednotkovém přírůstku pravých stran vlastních omezení bi
20. Co nám zobrazují vektory záporné fiktivní proměnné?
Fiktivní proměnné zavádíme, pokud se kapacity dodavatelů a požadavky spotřebitelů liší.
Při převisu poptávky doplníme fiktivního dodavatele, jehož kapacita bude rovna rozdílu mezi celkovými požadavky spotřebitelů a kapacitami dodavatelů.
Při převisu nabídky je rozdíl mezi požadavky a kapacitami záporný, proto použijeme zápornou fiktivní proměnnou ( záporného fiktivního dodavatele ).
21. SIMPLEXOVÁ METODA
Simplexová metoda je iterační výpočetní postup pro nalezení optimálního řešení úloh lineárního programování. Princip této metody vychází ze základní věty lineárního programování, která zní: „má-li úloha lineárního programování optimální řešení, pak se toto řešení nachází ve vrcholu množiny přípustných řešení“. Tato metoda tudíž zkoumá pouze vrcholy této množiny a mezi nimi hledá optimální řešení. Přípustné řešení je jakékoliv řešení, které splňuje všechna omezení, která jsou definována v zadání úlohy a také podmínku nezápornosti pravých stran (zásoby materiálu nemohou být záporné atp.). Optimálním řešením je pak řešení, které splňuje všechna omezení, podmínku nezápornosti pravých stran a také dosahuje maximální (minimální) hodnoty účelové funkce. Předpokladem použití jednofázové simplexové metody je, že matice rovnic je v kanonickém tvaru (matice o m rovnicích obsahuje jednotkovou podmatici m x m ) (např. matice o třech rovnicích obsahuje jednotkovou matici 3x3).
Postup výpočtu je zhruba následující. Ze zadání si vytvoříme tkz. matematický model úlohy. Ten obsahuje všechna omezení (spotřeba materiálu, časový fond pracovníků) ve formě nerovnic a také účelovou fci. (rovnici) (zisk dosažený výrobou, náklady na výrobu atd.). Nerovnice v podmínkách upravíme na rovnice přidáním přídatných proměnných, které vyjadřují nevyčerpané zdroje. Všechny rovnice dosadíme do matice. Před každý řádek matice napíšeme přídatnou proměnou, která byla do rovnice přidána a nad každý sloupec matice napíšeme příslušnou proměnnou, ke které patří koeficienty ve sloupci. Proměnné, které jsou „před maticí“ jsou tkz. základní proměnné. Jejich struktura se s každou iterací mění. Optimální řešení je takové, u kterého jsme v účelové fci. dosáhli pouze nezáporných koeficientů (v případě maximalizace) nebo nekladných koeficientů (v případě minimalizace). Úpravy v matici se provádí ekvivalentními úpravami podle klíčového řádku. Klíčový řádek zjistíme t