Kvadratisk tildelingsproblem

Quadratic assignment problem (KZN, eng. Quadratic assignment problem , QAP ) er et af de grundlæggende problemer ved kombinatorisk optimering inden for optimerings- eller operationsforskning , der hører til kategorien objektplaceringsproblemer .

Opgaven modellerer følgende virkelige opgave:

Der er et sæt af n virksomheder, der kan være placeret n steder. For hvert par lokationer er der angivet en afstand , og for hvert par af produktioner angives en vægt eller flow (dvs. mængden af materiale (råmateriale eller produkt), der transporteres mellem to produktioner). Det er påkrævet at placere produktioner på steder (to produktioner kan ikke placeres ét sted) på en sådan måde, at summen af afstande ganget med de tilsvarende flow bliver minimal.

Det er intuitivt klart, at virksomheder med et stort flow bør placeres tættere på hinanden.

Formuleringen af opgaven ligner formuleringen af opgaveproblemet , de adskiller sig i den objektive funktion - i en kvadratisk opgave er den kvadratisk, hvilket afspejler navnet.

Formel matematisk definition

Den formelle definition af det kvadratiske opgaveproblem er som følger:

Givet to sæt, P ("produktioner") og L ("lokationspunkter") af lige store størrelser, sammen med en vægtfunktion w : P × P → R og en afstandsfunktion d : L × L → R . Det er nødvendigt at finde en bijektion f : P → L ("tildeling"), således at værdien af den objektive funktion:

\sum _{a,b\in P}w(a,b)\cdot d(f(a),f(b))

vil være minimal.

Normalt betragtes vægte og afstande som kvadratiske reelle matricer , så den objektive funktion kan skrives som følger:

{\displaystyle \sum _{a,b\in P}w_{a,b}d_{f(a),f(b)))

I matrixform:

\min _{X\in \Pi _{n}}\operatørnavn {trace} (WXDX^{T})

, hvor er permutationsmatricer, W er vægtmatricen, og D er afstandsmatrixen.

\Pin}

Beregningsmæssig kompleksitet

Problemet er NP-hårdt , så der er ingen algoritme, der løser problemet i polynomisk tid, og selv små problemer kan tage lang tid at beregne. Det er også blevet bevist, at problemet ikke har en tilnærmelsesalgoritme, der kører i polynomiel tid for nogen (konstant) faktor, medmindre P = NP [1] . Problemet med den rejsende sælger kan betragtes som et særligt tilfælde af QZN, hvis det kræves, at flows forbinder alle produktioner i én cyklus med den samme flowværdi, der ikke er nul. Mange andre standard kombinatoriske optimeringsproblemer kan skrives i denne form.

Ansøgninger

Ud over den originale formulering af produktionsplacering er QZN en matematisk model for problemerne med at placere relaterede elektroniske komponenter på printplader eller integrerede kredsløb . Modellen tjener som en del af processen med at placere og forbinde computerstøttede designsystemer i elektronikindustrien.

Se også

Minimax Quadratic Assignment Problem

Noter

↑ Sahni & Gonzalez, 1976 .

Litteratur

Sartaj Sahni, Teofilo Gonzalez. . P-komplet tilnærmelsesproblemer . — Journal of the ACM , 1976, 23 (3). - S. 555-565. - doi : 10.1145/321958.321975 . .
Michael R. Garey, David S. Johnson. . Computere og intraktabilitet: En guide til teorien om NP-fuldstændighed . - W. H. Freeman, 1979. - ISBN 0-7167-1045-5 . — S. 218.