Buscar
Estás en modo de exploración. debe iniciar sesión para usar MEMORY

   Inicia sesión para empezar

level: Speciální úlohy LP a ILP

Questions and Answers List

level questions: Speciální úlohy LP a ILP

QuestionAnswer
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