| Distribuční úlohy LP | ⟶ Úkolem celé velké skupiny distribučních úloh je zajistit distribuci(tj. rozdělení) určité homogenní komodity (např. zboží) z jedné oblasti (např. dodavatelé) do druhé oblasti (např. odběratelé).
⟶ Proměnné:přiřazení jednotky z první skupiny k jednotce z druhé skupiny (např. doprava od daného dodavatele k danému odběrateli), hodnoty určují, zda k přiřazení dojde či ne (0/1) nebo jak intenzivní přiřazení je (množství převáženého zboží)
⟶ Omezení:kapacity a požadavkyu
⟶ Cíl:obvykle minimalizace nákladů |
| Odlišnost od běžných úloh | ⟶ Liší se od běžných úloh LP svým specifickým matematickým modelem
⟶ Řada z nich je charakteristická požadavkem celočíselnosti proměnných
⟶ Řeší se proto specifickými metodami |
| Dopravní problém (DP) | ⟶ Úkol: určit, kolik jednotek dodá každýdodavatel každému odběrateli
⟶ Cíl: uspokojit požadavky odběratelů tak, aby hodnota stanoveného cíle byla minimální |
| Nevyrovnaný dopravní problém | ⟶ Lze převést na vyrovnaný dopravní problému
⟶ Buď přidáním fiktivního dodavatele nebo fiktivního odběratele |
| Kontejnerový dopravní problém (KDP) | ⟶ KDP je modifikací dopravního problému s tím rozdílem, že přeprava zboží se provádí pouze v kontejnerech
⟶ Každý kontejner má kapacitu K jednotek
⟶ Náklady na přepravu jsou uvedeny na jeden kontejner
⟶ Náklady jsou stejné bez ohledu na to, je-li kontejner plný nebo poloprázdný
⟶ Celkové náklady na přepravu se minimalizují |
| Obecný distribuční problém (ObDP) | ⟶ Je velmi podobný DP především svým MM
⟶ Ekonomické modely se liší:
v DP jde o rozdělení (distribuci) zdrojů, které se nijak nemění, pouze se převážejí a v ObDP jde o rozdělení činností, jejichž realizací vznikají nové výrobky
⟶ Cílem je takové rozdělení činností, které minimalizuje náklady |
| Přiřazovací problém (PP) | ⟶ Jedná se o vzájemně jednoznačné přiřazení dvojice jednotek ze dvou skupin (párování)
⟶ Např. může jít o auta a garáže, stavby a rypadla, pracovníci a pracovní místa apod.
⟶ Toto přiřazení má přinést co nejvyšší efekt
⟶ Můžeme minimalizovat ujetou vzdálenost, náklady, maximalizovat pracovní výkon apod. |
| Přiřazovací problém (PP)
Rozdílný počet prvků | ⟶ Předpokládáme, že obě skupiny mají stejný počet prvků
⟶ Pokud nemají, lze jednu ze skupin doplnit fiktivními jednotkami |
| Přiřazovací problém (PP)
Řešení | ⟶ Řeší se speciálními metodami pro bivalentní úlohy nebo heuristickými metodami, které dávají přibližné výsledky (maďarská metoda, metoda větví a mezí) |
| Okružní dopravní problém (OkDP) | ⟶ H istorický název e „problém obchodního cestujícího“
⟶ Obchodní cestující má vyjít z místa M1
⟶ Obejít stanovený počet míst tak, aby do každého jednou vešel a jednou z něj vyšel
⟶ Cestu musí absolvovat najednou
⟶ Celková délka cesty musí být minimální
⟶ Na rozdíl od DP nejde o určení přepravovaných množství, ale o stanovení dopravní cesty |
| Úloha o pokrytí (ÚoP) | ⟶ Jde o jednu z variant přiřazovacího problému
⟶ Je třeba rozhodnout o umístění ?obslužných stanic (hasičská stanice, první pomoc atd.)
⟶ Území působnosti těchto stanic je rozděleno do ? obvodů (?>?)
⟶ Každý obvod je obsluhován jednou stanicí
⟶ Je třeba určit, do kterých obvodů bude umístěna určitá obslužná stanice
⟶ Současně je třeba určit území působnosti této stanice |
