- Stahuj zápisky z přednášek a ostatní studijní materiály
- Zapisuj si jen kvalitní vyučující (obsáhlá databáze referencí)
- Nastav si své předměty a buď stále v obraze
- Zapoj se svojí aktivitou do soutěže o ceny
- Založ si svůj profil, aby tě tví spolužáci mohli najít
- Najdi své přátele podle místa kde bydlíš nebo školy kterou studuješ
- Diskutuj ve skupinách o tématech, které tě zajímají
Studijní materiály
Hromadně přidat materiály
Otazky_k_casti_II_p2007
PMEMMI - Ekonomicko-matematické metody I
Hodnocení materiálu:
Zjednodušená ukázka:
Stáhnout celý tento materiálOtázky ke II. části písemné zkoušky
Úvod do operačního výzkumu
1. Popište proces operačního výzkumu a uveďte typy rozhodovacích situací.
Rozhodovací situace můžeme klasifikovat podle následujících hledisek (ta se promítají také do
klasifikace modelů):
a) Hledisko určitosti veličin a vztahů:
• rozhodování za určitosti (deterministické modely obsahující pouze pevně dané veličiny a
vztahy)
• rozhodování za rizika (stochastické modely obsahující alespoň jednu náhodnou veličinu,
přičemž rozdělení pravděpodobnosti všech náhodných veličin v modelu je známé)
• rozhodování za neurčitosti (např. fuzzy modely, v nichž je neurčitost modelována pomocí
teorie fuzzy množin)
b) Hledisko počtu kritérií:
• rozhodování s jedním kritériem (jednokriteriální modely)
• rozhodování s více kritérii (vícekriteriální modely): např. při nákupu nějakého zařízení
můžeme chtít takové, které má co nejmenší cenu a současně co největší spolehlivost nebo
výkon
c) Hledisko počtu rozhodovatelů
• rozhodování s jedním rozhodovatelem: to ovšem nemusí být pouze jedna osoba, ale může to
být i skupina osob, majících stejné cíle (např. vedení podniku)
• rozhodování s více rozhodovateli: používají se pro modelování konfliktních situací (např. na
trhu se v konkurenčním boji střetávají zájmy různých rozhodovatelů) a zabývá se jimi
teorie her
2. Na zvoleném příkladě popište strukturu optimalizačního modelu.
Při výběru veličin je nutné zvážit otázku úrovně podrobnosti modelu, která by měla odpovídat jednak
účelu modelování, jednak kvalitě dostupných informací o zkoumaném objektu.
Veličiny modelu vstupují do následujících matematických vztahů:
• kriteriální (účelová) funkce, vyjadřující závislost zvoleného kritéria na neřiditelných
veličinách a rozhodovacích proměnných; tato funkce může být maximalizačního (např.
zisk, hodnota produkce, spolehlivost) nebo minimalizačního typu (např. náklady);
• omezující podmínky které vymezují množinu přípustných řešení modelu; jsou to rovnice nebo
nerovnice, v nichž vystupují rozhodovací proměnné a neřiditelné veličiny; tyto podmínky
dělíme na
• vlastní omezení (zachycují vztahy, které musejí platit mezi rozhodovacími
proměnnými),
• podmínky pro jednotlivé rozhodovací proměnné (např. dolní a horní meze hodnot
těchto proměnných nebo podmínky jejich celočíselnosti).
Formulace a vlastnosti úloh lineárního programování
3. Napište definici báze. Ilustrujte na příkladě. Jaký je maximální počet různých bází?
Nechť A je typu (m, n) o hodnosti m a nechť B je matice tvořená m lineárně nezávislými sloupci
matice A. Pak matice B se nazývá bází uvedené úlohy LP. Každá báze určuje právě jedno bázické
řešení.
Proměnné odpovídající sloupcům matice B se nazývají bázické. Ostatní proměnné se nazývají
nebázické. Počet různých bází a tedy i počet různých bázických řešení je shora ohraničen
kombinačním číslem
m
n
a je tedy konečný.
4. Napište definici bázického řešení. Ilustrujte na příkladě. Jaký je geometrický význam bázického
řešení?
Řešení soustavy Ax = b se nazývá bázické, jestliže sloupce matice A, které odpovídají nenulovým
složkám tohoto řešení, tvoří lineárně nezávislou soustavu vektorů.
Přípustné bázické řešení je takové bázické řešení, které navíc vyhovuje podmínkám nezápornosti
x ≥ 0.
Přípustné řešení úlohy LP je bázické právě tehdy, je-li krajním bodem množiny přípustných
řešení.
5. Jak se zjistí bázické řešení odpovídající dané bázi B? Ilustrujte na příkladě.
Bázické řešení pro danou bázi můžeme získat následovně. Nechť B je báze úlohy (2.11). Označme
xB … vektor bázických proměnných
xN … vektor nebázických proměnných
Položme nebázické proměnné rovny nule, tj. xN = 0. Pak vektor xB je řešením rovnice BxB = b a tedy
xB = B–1b
6. Jak zní základní věta LP a co je jejím důsledkem?
Pro úlohu LP
max{cTx| Ax=b, x>=0}
může nastat právě jedna z těchto tří možností:
a) množina přípustných řešení M = ∅ (úloha LP nemá žádné přípustné řešení),
b) M ≠ ∅ a množina optimálních řešení M* = ∅ (úloha LP má přípustné řešení, ale nemá žádné
optimální řešení),
c) M* ≠ ∅ (úloha LP má optimální řešení).
Dále platí:
Je-li M ≠ ∅, pak existuje přípustné bázické řešení.
Je-li M* ≠ ∅, pak existuje bázické optimální řešení.
Tedy jestliže má úloha LP přípustné řešení, má také přípustné bázické řešení a jestliže má
optimální řešení, má také bázické optimální řešení.
Význam základní věty LP spočívá v tom, že v jejím důsledku se při hledání optimálního řešení úlohy
LP se můžeme omezit pouze na řešení bázická, jejichž počet je konečný. Základní věta LP je
teoretickým základem simplexové metody řešení úloh LP.
Simplexová metoda
7. Popište dvoufázovou simplexovou metodu.
Do původní úlohy zavedeme nezáporné pomocné (umělé) proměnné tak, abychom získali
kanonický tvar, a původní účelovou funkci nahradíme pomocnou účelovou funkcí, která je
součtem pomocných proměnných. V prvé fázi simplexové metody pak simplexovým algoritmem
hledáme bázické řešení, které minimalizuje pomocnou účelovou funkci. Pokud jsou v tomto
řešení všechny pomocné proměnné nulové, použijeme hodnoty ostatních proměnných jako
výchozí pro druhou fázi simplexové metody, v níž pomocí simplexového algoritmu hledáme
bázické řešení, které optimalizuje původní účelovou funkci. Jestliže se při minimalizaci pomocné
účelové funkce nepodařilo anulovat všechny pomocné proměnné, pak to znamená, že původní
úloha nemá žádné přípustné řešení.
a) Je-li g(xPo) = 0 (tj. jestliže jsou všechny pomocné proměnné rovny nule), pak vektor xo je výchozí
přípustné bázické řešení původní úlohy.
b) Je-li g(xPo) ≠ 0, pak původní úloha nemá žádné přípustné řešení. Poznamenejme, že v takovém
případě musí být hodnota pomocné účelové funkce kladná, protože tato funkce je součtem
nezáporných pomocných proměnných. Pokud by tedy tato hodnota vyšla záporná, znamenalo by
to, že při výpočtu došlo k nějaké chybě.
Obecně má simplexová metoda dvě fáze (proto se používá název dvoufázová simplexová metoda):
1. Nalezení výchozího přípustného bázického řešení.
Jestliže úloha nemá žádné přípustné řešení, pak postup končí. V opačném případě se přechází na
druhou fázi.
2. Hledání optimálního bázického řešení.
Tato fáze končí nalezením optimálního bázického řešení nebo zjištěním, že optimální řešení
neexistuje.
V obou fázích se využívá simplexový algoritmus, který bude popsán v následujícím odstavci.
Simplexový algoritmus
Mějme výchozí přípustné bázické řešení x1. Položme k = 1, A(k) = A, b(k) = b. Simplexový algoritmus
sestává z následujících tří kroků, které později rozvedeme podrobněji:
1. Test kritéria optimality pro xk. Je-li splněno, pak konec (bázické řešení xk je optimálním řešením).
2. Určení klíčového prvku a matice A)(krs(k). Není-li možné určit klíčový prvek, pak konec (úloha
nemá konečné optimální řešení).
3. Simplexová transformace matice (A(k) | b(k)). Získáme matici (A(k+1) | b(k+1)) a nové bázické řešení
xk+1. Položíme k = k + 1 a postup opakujeme od bodu 1.
8. Jaké jsou možné případy zakončení simplexové metody? Ilustrujte graficky. Jak se tyto případy
poznají v simplexové tabulce?
Podle základní věty LP (viz § 2.3) mohou pro každou úlohu LP nastat pouze tři možnosti: má
optimální řešení, má přípustné ale nemá optimální řešení, nemá přípustné řešení. V následujícím
přehledu prvý případ rozdělíme na dva podpřípady a uvedeme, jak se tyto situace poznají v
simplexové tabulce:
1. Úloha má jediné optimální řešení:
Je splněno kritérium optimality a pro všechny nebázické proměnné jsou redukované ceny Δj ≠ 0.
2. Úloha má nekonečně mnoho optimálních řešení:
Je splněno kritérium optimality a alespoň pro jednu nebázickou proměnnou je redukovaná cena Δj =
0.
3. Úloha nemá konečné optimální řešení:
Není splněno kritérium optimality a není možno určit klíčový řádek.
4. Úloha nemá žádné přípustné řešení:
Optimální hodnota pomocné účelové funkce není nulová.
Tyto možnosti zakončení simplexové metody se vztahují k případu, kdy úloha není degenerovaná.
Degenerovaná je taková úloha, která má alespoň jedno degenerované bázické řešení.
U degenerované úlohy mohou nastat tyto situace:
• výskyt Δj = 0 u nebázické proměnné nemusí být příznakem existence nekonečně mnoha
optimálních řešení (viz příklad 3.11),
• může dojít k zacyklení (toto nebezpečí se dá odstranit úpravou simplexového algoritmu).
Dualita a analýza citlivosti
9. Napište definici dvojice symetricky duálně sdružených úloh a uveďte konkrétní příklad takové
dvojice.
Přitom maximalizační úloze odpovídá úloha minimalizační a naopak. Úlohy lineárního
programování se tedy vlastně vyskytují ve dvojicích (hovoříme o dvojicích duálně sdružených
úloh). Původní úlohu v této dvojici nazýváme primární, kdežto úlohu s ní sdruženou označujeme
jako duální.
10. Napište slabou a silnou větu o dualitě. Jaké jsou důsledky těchto vět?
Slabá věta o dualitě
Nechť primární úloha je maximalizační s účelovou funkcí f(x), duální úloha je minimalizační s
účelovou funkcí g(u), a nechť x0 je libovolné přípustné řešení primární úlohy a u0 je libovolné
přípustné řešení duální úlohy. Pak platí
f(x0) ≤ g(u0)
Tedy hodnota účelové funkce minimalizační úlohy v kterémkoli přípustném řešení je horní mezí
hodnot účelové funkce duálně sdružené maximalizační úlohy na množině všech jejích přípustných
řešení a obdobně hodnota účelové funkce maximalizační úlohy v kterémkoli přípustném řešení je
dolní mezí hodnot účelové funkce duálně sdružené minimalizační úlohy na množině všech jejích
přípustných řešení.
Silná věta o dualitě
Má-li jedna z duálně sdružených úloh optimální řešení, má optimální řešení i úloha druhá, přičemž
optimální hodnoty účelových funkcí jsou si rovny.
Důsledky silné a slabé věty o dualitě
• Platí-li pro přípustné řešení x0 primární úlohy a pro přípustné řešení u0 duální úlohy rovnost f(x0)
= g(u0), pak x0 a u0 jsou optimální řešení.
• Je-li množina přípustných řešení maximalizační úlohy neprázdná a je-li účelová funkce této úlohy
shora neomezená, pak duálně sdružená úloha nemá žádné přípustné řešení.
• Je-li množina přípustných řešení minimalizační úlohy neprázdná a je-li účelová funkce této úlohy
zdola neomezená, pak duálně sdružená úloha nemá žádné přípustné řešení.
• Nemá-li jedna z dvojice duálně sdružených úloh přípustné řešení, pak druhá úloha nemá
optimální řešení.
Prvá tři tvrzení jsou důsledkem slabé věty o dualitě, zatímco poslední tvrzení lze chápat jako
důsledek silné věty o dualitě.
11. Napište větu o komplementaritě. Na jejím základě odpovězte na otázku, jaká bude v úloze
optimalizace výrobního programu optimální hodnota duální proměnné, když odpovídající zdroj
nebude plně využit?
Přípustná řešení symetricky duálně sdružených úloh jsou optimální právě tehdy, když platí
Toto tvrzení je sice pro jednoduchost zformulováno pro případ symetricky duálně sdružených úloh,
ale platí i v nesymetrických případech. Výše uvedené vztahy znamenají, že nabývá-li nějaká
proměnná kladnou hodnotu, pak odpovídající duálně sdružené omezení musí být splněno jako rovnice
(tj. příslušná doplňková proměnná musí být nulová) a naopak je-li nějaké omezení splněno jako ostrá
nerovnost (tj. příslušná doplňková proměnná je nenulová), pak odpovídající duálně sdružená
proměnná musí být nulová. Jak uvidíme dále, tato věta má zajímavou ekonomickou interpretaci.
- nulová.
12. Co je cílem analýzy citlivosti a jaké úlohy se zde řeší? Jaký je význam duálních proměnných z
hlediska analýzy citlivosti?
Dodatečně pak chceme zjistit, zda to, co jsme vynechali, skutečně nemá na optimální řešení vliv.
Rovněž koeficienty v zadání úlohy se často mohou měnit nebo mohou být pouhými odhady a
potřebujeme zjistit, jak případné změny těchto koeficientů ovlivňují optimální řešení úlohy.
Těmito otázkami se zabývá analýza citlivosti, která také bývá nazývána postoptimalizační
analýzou. Někdy lze popsat změnu zadání úlohy jako závislost koeficientů úlohy na parametrech,
které nabývají hodnot z dané množiny. Sledujeme pak závislost optimálního řešení na těchto
parametrech a hovoříme o úloze parametrického programování.
K analýze citlivosti optimálního řešení na změny zadání úlohy existují dva základní přístupy.
Optimální hodnoty duálních proměnných vyjadřují citlivost optimální hodnoty primární účelové
funkce na změny pravých stran primárních omezení. Duální proměnné tudíž hrají důležitou roli v
anal
Vloženo: 24.04.2009
Velikost: 965,88 kB
Komentáře
Tento materiál neobsahuje žádné komentáře.
Copyright 2024 unium.cz