Problém s přiřazením kvadratického úzkého místa - Quadratic bottleneck assignment problem

V matematice je problém s přiřazením kvadratického úzkého místa (QBAP) je jedním ze základních kombinatorická optimalizace problémy v oboru optimalizace nebo operační výzkum, z kategorie umístění zařízení problémy.[1]

Souvisí to s problém kvadratického přiřazení stejným způsobem jako lineární problém s přiřazením úzkého místa souvisí s problém lineárního přiřazení, "součet" je nahrazen "max" v Objektivní funkce.

Problém modeluje následující problém z reálného života:

Existuje sada n zařízení a soubor n umístění. Pro každou dvojici míst a vzdálenost je uvedeno a pro každou dvojici zařízení a hmotnost nebo tok je uvedeno (např. množství dodávek přepravovaných mezi dvěma zařízeními). Problémem je přiřadit všechna zařízení na různá místa s cílem minimalizovat maximální vzdálenosti vynásobené odpovídajícími toky.

Výpočetní složitost

Problém je NP-tvrdé, protože jej lze použít k formulaci Hamiltonovský cyklus problém pomocí toků ve vzoru cyklu a vzdáleností, které jsou krátké pro hrany grafu a dlouhé pro jiné než hrany.[2]

Speciální případy

Reference

  1. ^ Problémy s přiřazením tím, že Rainer Burkard, Mauro Dell'Amico, Silvano Martello, 2009
  2. ^ Burkard, R.E .; Fincke, U. (1982), „K problémům s náhodným přiřazením kvadratického úzkého místa“, Matematické programování, 23 (2): 227–232, doi:10.1007 / BF01583791, PAN  0657082.