Teorie-emm ke zkoušce

DEGENERACE

• pokud má řešení m + n -1 méně > jedná se o degeneraci

• formálně odstraníme dodáním obsazení pole Epsilonem

• epsilon má malou hodnotu

  • vzniká při hledání výchozího řešení, nebo při přechodu na nové řešení

téma 8 – 9: JEDNOSTUPŇOVÁ DOPRAVNÍ ÚLOHA II, DVOUSTUPŇOVÁ ÚLOHA

1) Uveďte princip metody MODI při řešení modelu jednostupňové dopravní úlohy.

MODI

• vychází z vlastností duálně sdružených úloh

• říká, zda je řešení optimální

• určí, zde je řešení OPT, nebo zda existují lepší řešení

• Zij – Cij pro minimalizaci

• Zij – Cij <= 0 pokud není splněno, dá se zlepšit a jdeme k dalšímu kroku

2) Co je to Danzigův uzavřený obvod? K čemu slouží při řešení modelu jednostupňové dopravní úlohy?

• pokud test optimality ukáže, že může být jiné lepší řešení s lepší účelovou funkcí

• musíme změnit bázi > dle Danzigových obvodů

• vychází z prázdné buňky, lomí se v obsazené buňce a končí v té, kde začala

• buňky, kde se lomí označím střídavě + - + -

• nově obsazená buňka

3) Co je to perspektivita dopravních tras? Jak se analýza perspektivity provádí?

= jak je trasa výhodná v absolutní hodnotě

• dle testu optima

4) Co je to propustnost dopravních tras? Jak se analýza propustnosti provádí?

= kolik můžu maximálně převést

• z OPT řešení se spočítá přes Danzigův obvod

5) Uveďte podstatu a komponenty jednostupňové dopravní úlohy. (stejné jako téma 7/1)

• nejvýhodnější přeprava

• minimalizace nákladů

• od více dodavatelů k více spotřebitelům

• homogenita přepravovaného materiálu > stejnorodost

6) Jaký je rozdíl mezi počtem rozměrů a počtem stupňů dopravní úlohy? Navrhněte a stručně popište možnou praktickou aplikaci alespoň dvou dopravních úloh, které se liší počtem stupňů i rozměrů.

Dva stupne

Jednostupňová…dodavatele > spotrebitele

Dvoustupňová – navíc mezisklady

Rozmery – pocty dodavatelu a odberatelu

7) Uveďte princip řešení dvoustupňové dopravní úlohy jako úlohy jednostupňové. Co je to úloha o optimálním dimenzování meziskladů?

• algoritmus

• převod na jednostupňovou

• kvadranty