Lineární programování

Lineární programování – disciplína operačního výzkumu, která se zabývá řešením rozhodovacích problémů. Musí se zde respektovat určité podmínky a najít řešení, při kterém je cíl splněn co nejlépe. Programování je synonymem pro plánování programů, lineární vyjadřuje, že všechny vazby v modelech jsou vazbami lineárními tzn. že matematické fce jsou fce lineární.

V úlohách lineárního programování se vyskytují 2 základní modely:

• Ekonomický model – vyjádření rozhodovacího problému formou jeho slovního, případně číselného popisu.

• Matematický model – matematická formalizace ekonomického modelu rozhodovacího problému. Obsahuje n - počet strukturních proměnných v modelu, m - počet vlastních omezení, c_j, j=1,2,..n – cenové koeficienty, b_i, i=1,2,..m – hodnoty pravých stran, a_ij, j=1,2,..n, i=1,2,..m tzv. strukturní koeficienty, podmínky

Stupně řešení úloh lineárního programování:

• Základní řešení (základní přípustné) – každé základní řešení ekvivalentní soustavy rovnic, které vyhovuje podmínkám nezápornosti; má maximálně tolik nenulových proměnných, kolik je lineárně nezávislých řádků této soustavy.

• Přípustné řešení – řešení, které splňuje všechny omezující podmínky modelu, tj. soustavu vlastních omezení i podmínky nezápornosti

• Optimální řešení – nejlepší ze všech přípustných řešení

Fáze řešení rozhodovacího procesu

1) rozpoznání problému v rámci systému a jeho definice

2) formulace ekonomického modelu – cíl analýzy (max. zisk), popis procesů (výroba),

popis činitelů (spotřeba omezujících zdrojů), popis mezi procesy a činiteli a cílem analýzy

3) matematický model – obsahuje stejné prvky jako ekonomický model

4) řešení matematického modelu

5) interpretace a verifikace výsledků

6) implementace

Ekvivalentní soustava rovnic – soustava linearnich rovnic ziskana prevodem soustavy vlastnich omezeni na soustavu rovnic pomoci pridatnych promenych

Kanonicky tvar soustavy lineárních rovnic – takovy tvar soustavy m rovnic, ve kterem obsahuje matice strukturnich koeficientu jednotkovou submatice m x m

Zakladni promenny m – to jsou promenne, kterym odpovidaji jednotkove vektory a jejichz hodnoty jsou v prislusnem zakladnim reseni rovny hodnotam prave strany.

Nezakladni promenny n – to jsou vsechny ostatni promenne, jejich hodnoty jsou v zakladnim reseni rovny 0.

Základní věta lineárního programování – má-li úloha LP optimální řešení, má také základní optimální řešen; podle této věty stačí hledat optimální řešeni pouze mezi základními řešeními úlohy LP (kterých je konečný počet)

Simplexová metoda – postup pro nalezení optimálního řešení úloh lineárního programování. Pokud je optimální řešení již k dispozici, tak simplexová metoda vypočte nové základní řešení s lepší hodnotou účelové funkce.

Fáze:

1. Nalezení výchozího základního řešení

2. Postup vedoucí k optimalizaci účelové fce

Schéma:

Nalezení výchozího základního řešení – Je to řešení optimální? Jestli ne, tak výpočet nového základního řešení s lepší hodnotou účelové fce – Je řešení optimální? Pokud ano, tak se ptáme, jestli je to jediné optimální řešení? Pokud ano, tak končím, pokud ne, tak ještě popíšu množinu optimálních řešení.

Typy:

• Jednofázová simplexová metoda – pouze v případě, že všechna omezení jsou ≤, pak to převedeme na ekvivalentní soustavu rovnic pomocí přídatných proměnných, dostaneme soustavu rovnic v kanonickém tvaru, v kanonickém tvaru máme m základních proměnných a n nezákladních proměnných, následuje test optimality – pokud nelze nalézt v daném kroku výpočtu vstupující proměnnou, která by vedla ke zvýšení (u maximalizace) nebo ke snížení (u minimalizace) hodnoty účelové fce, potom základní řešení obsažené v tomto kroku výpočtu je řešením optimálním.

Optimální řešení:

Variable Value Reduced Cost

X1 0.0000000 2.500000

X2 1.000000 0.0000000

X3 27.00000 0.0000000

Row Slack or Surplus Dual Price

1 285.0000 1.000000

2 0.0000000 2.500000

3 0.0000000 5.000000

Pridatne promenne (slack or surplus (2,3)) - množství nespotřebovaného materiálu

Při úlohách lineárního programování se interpretují především následující hodnoty:

• Redukované ceny udávají, o kolik by se zvýšil zisk, kdybychom vyráběli o jednu jednotku příslušné proměnné více. Redukované ceny u základních proměnných jsou vždy nulové

• Stínové ceny (dual price) udávají, o kolik se zvýší nebo klesne hodnota účelové funkce, když se pravá strana (většinou množstevní omezení surovin) zvýší o jednotku.

Mezi hlavní analýzy v rámci úloh lineárního programování patří:

• Analýza citlivosti pravých stran určuje meze, o kolik může stoupnout, příp. klesnout hodnota pravé strany, aby se nezměnila báze (aby řešení zůstalo optimální).

• Analýza citlivosti cenových koeficientů určuje meze, o kolik může stoupnout, případně klesnout cena produktu, aby se nezměnila báze.