opt-zkouška

Pomocná proměnná – používáme při tvoření rozšířeného modelu, kdy je připojíme k původnímu modelu do těch rovnic, kde chybí základní proměnné pro výchozí základní řešení

Pomocná účelová funkce – minimalizuje součet pomocných proměnných.

Vlastnosti tzv. rozšířeného lineárního modelu:

a) matice soustavy rovnic obsahuje jednotkovou submatici potřebného typu

b) je možno bezprostředně získat řešení původního modelu

c) řešíme-li rozšířený model podle pomocné účelové funkce, po konečném kroku dospějeme k řešení, v němž se všechny proměnné rovnají nule

DOPRAVNÍ PROBLÉM

Dopravní problém: Problém, kde základním úkolem je rozvést mezi několik odběratelů výrobky z různých míst tak, aby byli uspokojení odběratelé v rámci daných zdrojů a přepravní náklady byly minimální.

Metody pro řešení dopravního problému:

a) simplexová metoda

b) speciální algoritmy např. aproximační metody:

- metoda severozápadního rohu (MSZR)

- metoda indexová vzestupná, sestupná a kombinovaná

- metoda Vogelova aproximační (VAM)

Základní principy všech metod pro řešení dopravního problému:

Simplexová metoda – postup od jednoho základního řešení k druhému

MSZR – začíná se obsazovat pole tabulky od severozápadního rohu, nemusíme se zabývat dopravními náklady, které neovlivní, zda je řešení základní nebo ne

Ostatní aproximační metody – jsou založeny na vyváženosti dopravního problému, např. VAM – postup:

1) stanovíme pro každý řádek a sloupec diferenci mezi nejmenší a druhou nejmenší sazbou

2) vybereme řadu (tj. sloupec nebo řádek) s největší diferencí

3) v této řadě obsadíme největší možnou přepravou pole s nejmenší sazbou

4) řadu s vyčerpanou kapacitou nebo požadavkem vyškrtneme a v dalším postupu s ní nepočítáme

=> opakujeme pořád dokola, dokud nedostaneme výsledek

Rozvrhování výroby – používají se analytické metody (pro malý počet) a logistické (simulace, menší přesnost)

Nevýhoda metody severozápadního rohu – pole se obsazuje bez ohledu na dopravní sazby (nepřesný výsledek – není optimální).

Sedlový bod a jeho použití:

- pole s nejmenší sazbou z hlediska řádku i sloupce

- používáme, jsou-li největší diference stejné u více řad

- mezi několika sedlovými body se rozhodneme pro ten, u něhož je součet řádkové a sloupcové

diferenci největší

- neexistuje-li ani jeden sedlový bod, stanovíme druhé diference

Druhá diference - rozdíl mezi druhou nejmenší sazbou v řadě a mezi nejmenší sazbou v řadě kolmé

Vyrovnaný dopravní problém – souhrn kapacit dodavatelů = souhrn požadavků dodavatelů

Nevyrovnaný dopravní problém - souhrn kapacit se liší od souhrnu požadavků

Řešení nevyrovnaného dopravního problému - přidáme fiktivního dodavatele nebo odběratele, dle aktuální potřeby

Fiktivní odběratel, fiktivní dodavatel: Používáme je, pokud máme nevyrovnaný dopravní problém.