Оцените презентацию от 1 до 5 баллов!
Тип файла:
ppt / pptx (powerpoint)
Всего слайдов:
17 слайдов
Для класса:
1,2,3,4,5,6,7,8,9,10,11
Размер файла:
155.54 kB
Просмотров:
66
Скачиваний:
0
Автор:
неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Ekonomicko-matematické metody I
3/12
Modely lineárního programování. Simplexový algoritmus.
№2 слайд
Содержание слайда: Vzdělávací cíle
Připravit model LP pro výpočet simplexovým algoritmem
Sestavit výchozí simplexovou tabulku
Nalézt optimální řešení pomocí simplexové metody
№3 слайд
Содержание слайда: Model lineárního programování
Cíl: nalézt vázaný extrém lineární funkce více proměnných, který vyhovuje daným lineárním omezujícím podmínkám
Komponenty modelu
proměnné;
omezující podmínky;
účelová (kriteriální) funkce;
podmínky nezápornosti.
№4 слайд
Содержание слайда: Použité symboly a značení
Proměnné
x … strukturní proměnné;
d … doplňkové proměnné;
p … pomocné proměnné.
Omezující podmínky … Ax ≤ b
A = (aij) … matice soustavy;
b … vektor pravých stran.
Účelová funkce … z = c.x
c … cenové koeficienty proměnných (jednotkové ceny)
№5 слайд
Содержание слайда: Příklad
Farma se rozhoduje o vyhrazení části své půdy pro pěstování pšenice, ječmene a žita.
tyto plodiny mají obsadit celkem právě 140 hektarů;
potřeba chlévského hnoje je 40; 15 a 20 t/ha, k dispozici je maximálně 3000 t hnoje;
odhadované zisky v tis. Kč/ha jsou pro jednotlivé plodiny 1; 1 a 2 (bráno po řadě), je požadováno dosáhnout alespoň 200 tis. Kč zisku.
Farma chce minimalizovat dopady na životní prostředí, které vyjadřuje v „jednotkách zátěže“ (JZ/ha) a které jsou pro jednotlivé plodiny 7; 2 a 4. Na jaké ploše by měly být vysety jednotlivé plodiny?
№6 слайд
Содержание слайда: Simplexový algoritmus
Splnění podmínek simplexového algoritmu
Výchozí bázické řešení
Test optima (vstupu)
Test přípustnosti báze (výstupu)
Přechod na nové řešení Jordanovou eliminační metodou
№7 слайд
Содержание слайда: Podmínky simplexového algoritmu
Nezápornost složek vektoru pravých stran
stačí zkontrolovat;
pokud není splněna, lze příslušné omezující podmínky vynásobit hodnotou (-1).
Matice soustavy v kanonickém tvaru
krok 1: rovnicový tvar modelu;
krok 2: kanonický tvar modelu.
№8 слайд
Содержание слайда: Rovnicový tvar
Nerovnice vyrovnáme na rovnice
Doplňkové proměnné
značíme d, indexujeme číslem omezující podmínky;
přebírají jednotky omezující podmínky;
v účelové funkci ohodnocujeme nulovou sazbou;
požadujeme jejich nezápornost.
Přidáváme do omezujících podmínek
kapacitních s kladným znaménkem (rezerva);
požadavkových se záporným znaménkem (překročení požadavku).
№9 слайд
Содержание слайда: Kanonický tvar
Nerovnice vyrovnáme na rovnice (doplňkové proměnné)
Zajistíme úplnou jednotkovou submatici
Pomocné proměnné
značíme p, indexujeme číslem omezující podmínky;
přebírají jednotky omezující podmínky;
v účelové funkci ohodnocujeme nevýhodnou (prohibitivní) sazbou;
požadujeme jejich nezápornost.
№10 слайд
Содержание слайда: Pomocné proměnné
Přidáváme do omezujících podmínek
požadavkových;
typu určení;
vždy s kladným znaménkem.
Interpretace
kolik jednotek zbývá do splnění omezení;
řešení s kladnou hodnotou pomocné proměnné je proto automaticky nepřípustné.
№11 слайд
Содержание слайда: Výchozí bázické řešení
Sestavení výchozí simplexové tabulky
Identifikace bázických a nebázických proměnných
Určení hodnot proměnných ve výchozím bázickém řešení
Určení hodnoty účelové funkce
№12 слайд
Содержание слайда: Test optimality
Existuje bázické řešení s lepší hodnotou ÚF?
Záměna proměnných v bázi
Koeficient zj – cj
záporný: hodnota ÚF se zvyšuje;
kladný: hodnota ÚF se snižuje;
nulový: proměnná nemá vliv na hodnotu ÚF.
Řešení je optimální
minimalizace: zj – cj ≤ 0 pro všechna j;
maximalizace: zj – cj ≥ 0 pro všechna j.
Klíčový sloupec: maximální hodnota |zj – cj| z těch, které porušují podmínku optimality
№13 слайд
Содержание слайда: Test přípustnosti
I nové řešení musí splňovat podmínky SA
Nezáporné složky vektoru b
Známe klíčový sloupec (z testu optima)
Určíme klíčový řádek podle podílů
Pouze pro aij > 0
Minimum z těchto podílů určuje klíčový řádek
№14 слайд
Содержание слайда: Nové řešení
Jeden krok Jordanovy eliminační metody
Přesun jednotkového vektoru pod proměnnou, která vstupuje do báze
Průsečík klíčového řádku a klíčového sloupce = klíčový prvek
Klíčový řádek vydělíme klíčovým prvkem
Od ostatních řádků odečteme vhodný násobek NOVÉHO klíčového řádku
№15 слайд
Содержание слайда: Interpretace výsledku
Rozdělení proměnných na bázické a nebázické
Hodnoty všech proměnných
Hodnota účelové funkce
Relativní nevýhodnost nebázických proměnných – duální (stínové) ceny
№16 слайд
Содержание слайда: Shrnutí
Pojem lineární optimalizační model
Konstrukce simplexové tabulky
Čtení v simplexové tabulce
Optimalizace v simplexové tabulce
Základní interpretace výsledků
№17 слайд
Содержание слайда: Literatura
Šubrt a kol.: Ekonomicko-matematické metody, vydavatel Aleš Čeněk, Plzeň, 2011
Houška, M., Beránková, M.: Lineární programování - cvičebnice, ČZU Praha, 2008
Získal, J., Beránková, M., Houška, M.: Lineární programování I., ČZU Praha, 2005