Modely lineárního programování. Simplexový algoritmus

Сентябрь 7, 2022

Главная
Алгебра
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í
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
4. Použité symboly a značení Proměnné x … strukturní proměnné; d … doplňkové proměnné; p … pomocné
5. Příklad Farma se rozhoduje o vyhrazení části své půdy pro pěstování pšenice, ječmene a žita. tyto
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)
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í
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
9. Kanonický tvar Nerovnice vyrovnáme na rovnice (doplňkové proměnné) Zajistíme úplnou jednotkovou submatici Pomocné proměnné značíme p,
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
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
12. Test optimality Existuje bázické řešení s lepší hodnotou ÚF? Záměna proměnných v bázi Koeficient zj –
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
14. Nové řešení Jeden krok Jordanovy eliminační metody Přesun jednotkového vektoru pod proměnnou, která vstupuje do báze
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
16. Shrnutí Pojem lineární optimalizační model Konstrukce simplexové tabulky Čtení v simplexové tabulce Optimalizace v simplexové tabulce
18. Скачать презентацию

Слайд 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?

Sestavit model

Слайд 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

Ukázat obecněji na malé tabulce

Слайд 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 αij > 0
Minimum z těchto podílů určuje klíčový řádek

, kde k je index klíčového sloupce

Ukázat obecněji na malé tabulce

Слайд 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ů

Modely lineárního programování. Simplexový algoritmus

Содержание

Vzdělávací cílePřipravit model LP pro výpočet simplexovým algoritmemSestavit výchozí simplexovou tabulkuNalézt

Model lineárního programováníCíl: nalézt vázaný extrém lineární funkce více proměnných, který

Použité symboly a značeníProměnnéx … strukturní proměnné;d … doplňkové proměnné;p …

PříkladFarma se rozhoduje o vyhrazení části své půdy pro pěstování pšenice,

Simplexový algoritmusSplnění podmínek simplexového algoritmuVýchozí bázické řešeníTest optima (vstupu)Test přípustnosti báze

Podmínky simplexového algoritmuNezápornost složek vektoru pravých stranstačí zkontrolovat;pokud není splněna, lze

Rovnicový tvarNerovnice vyrovnáme na rovniceDoplňkové proměnnéznačíme d, indexujeme číslem omezující podmínky;přebírají

Kanonický tvarNerovnice vyrovnáme na rovnice (doplňkové proměnné)Zajistíme úplnou jednotkovou submaticiPomocné proměnnéznačíme

Pomocné proměnnéPřidáváme do omezujících podmínekpožadavkových; typu určení;vždy s kladným znaménkem.Interpretacekolik jednotek

Výchozí bázické řešeníSestavení výchozí simplexové tabulkyIdentifikace bázických a nebázických proměnnýchUrčení hodnot

Test optimalityExistuje bázické řešení s lepší hodnotou ÚF?Záměna proměnných v báziKoeficient

Test přípustnostiI nové řešení musí splňovat podmínky SANezáporné složky vektoru bZnáme

Nové řešeníJeden krok Jordanovy eliminační metodyPřesun jednotkového vektoru pod proměnnou, která

Interpretace výsledkuRozdělení proměnných na bázické a nebázickéHodnoty všech proměnnýchHodnota účelové funkceRelativní

ShrnutíPojem lineární optimalizační modelKonstrukce simplexové tabulkyČtení v simplexové tabulceOptimalizace v simplexové

Похожие презентации