Generaliseret opgaveproblem

I anvendt matematik forstås et generaliseret opgaveproblem som et kombinatorisk optimeringsproblem , som er en generalisering af opgaveproblemet , hvor sættet af udførende har en størrelse, der ikke nødvendigvis er lig med størrelsen af opgavesættet. I dette tilfælde kan udøveren få tildelt at udføre et hvilket som helst arbejde (ikke nødvendigvis ét værk, som i opgaveproblemet). Når du tildeler en eksekutør til at udføre arbejde, er to værdier angivet - omkostninger og indtægter. Hver kunstner har et bestemt budget, så summen af alle omkostninger bør ikke overstige dette budget. Det er påkrævet at finde en sådan tildeling af kunstnere til at udføre arbejde for at maksimere indkomsten.

Særlige lejligheder

I det tilfælde, hvor budgetterne for kunstnere og alle omkostninger ved arbejde er lig med 1, bliver problemet til det maksimale matchningsproblem .

Hvis priser og indkomster for alle jobopgaver er lige store, reduceres problemet til en multiplikativ rygsæk .

Hvis der kun er et middel, reduceres problemet til rygproblemet .

Definition

Der er n job og m kunstnere . Hver kunstner har et budget . For hvert par kunstnere og arbejde angives indkomst og vægt . Løsningen er en delmængde af jobs U og en fordeling af jobs fra U blandt udførende. Beslutningen er acceptabel, hvis omkostningerne til udøverens tildelte arbejde ikke overstiger budgettet . Indkomsten fra beslutningen er summen af alle indkomster af alle fordelinger af arbejdsudøver. ${\displaystyle x_{1},\dots ,x_{n))$ ${\displaystyle b_{1},\dots ,b_{m))$ $b_{i}$ $w_{i}$ $b_{i}$ $x_{j}$ $p_{i,j}$ $w_{i,j}$ $b_{i}$ $w_{i}$

Matematisk kan det generaliserede opgaveproblem formuleres som følger:

maksimere

\sum _{i=1}^{m}\sum _{j=1}^{n}p_{ij}x_{ij}.

underlagt ;

\sum _{j=1}^{n}w_{ij}x_{ij}\leq w_{i}\qquad i=1,\ldots ,m

\sum _{i=1}^{m}x_{ij}\leq 1\qquad j=1,\ldots ,n

;

x_{ij}\in \{0,1\}\qquad i=1,\ldots ,m,\quad j=1,\ldots ,n

;

Det generaliserede tildelingsproblem er NP-hårdt og endda APX-hårdt .

Fleischer, Gomans, Mirokni og Sviridenko foreslog en kombinatorisk lokal søgealgoritme med tilnærmelse og en algoritme baseret på lineær programmering med tilnærmelse [1] . $(2+\varepsilon )$ $({\frac {e}{e-1}}+\varepsilon )$

Approksimationen er den bedst kendte tilnærmelse af det generaliserede opgaveproblem. $({\frac {e}{e-1}}+\epsilon )$

Greedy Approximation Algorithm

Ved hjælp af tildelingsproblemet -approksimationsalgoritmen kan man skabe en ( ) -tilnærmelse for det generaliserede tildelingsproblem på samme måde som en grådig algoritme ved hjælp af begrebet restindkomst. Algoritmen opretter iterativt en foreløbig sekvens, hvori det er meningen, at den skal tildele arbejde til udføreren ved iterationen . Valget for udøveren kan senere ændres ved tildeling af arbejde til andre udøvende. Den resterende indkomst af værket for den udøvende er , hvis værket ikke er givet til en anden udøvende kunstner, og - hvis værket er givet til den udøvende . $\alfa$ $\alpha +1$ $j$ $b_{j}$ $b_{j}$ $x_{i}$ $b_{j}$ $p_{{ij}}$ $x_{i}$ ${\displaystyle p_{ij))$ ${\displaystyle p_{ik))$ $b_{k}$

Formelt:

Brug vektor til forvalg og i denne vektor $T$

T[i]=j

betyder, at det er meningen, at det skal anvise en bobestyrer til arbejdet ,

x_{i}

b_{j}

T[i]=-1

betyder, at ingen er blevet tildelt jobbet.

x_{i}

Den resterende indkomst pr. iteration er angivet med , hvor $j$ $P_{j}$

{\displaystyle P_{j}[i]=p_{ij))

hvis intet job er valgt (dvs. )

x_{i}

T[i]=-1

{\displaystyle P_{j}[i]=p_{ij}-p_{ik))

, hvis værket formodes at blive givet til udøveren (dvs. ).

x_{i}

b_{k}

T[i]=k

Så algoritmen ser sådan ud:

Tildelte begyndelsesværdier for alle

T[i]=-1

i=1\ldots n

For alle , gør:

j=1...m

En tilnærmelsesalgoritme bruges til at opnå fordelingen af arbejdet for entreprenøren ved hjælp af restindkomstfunktionen . Udvalgte værker er angivet .

b_{j}

P_{j}

S_j

Rettet vha . , dvs. for alle .

T

S_j

T[i]=j

i\in S_{j}

slutningen af cyklussen

Se også

Opgave problem

Noter

↑ L. Fleischer, MX Goemans, VS Mirrokni og M. Sviridenko. Strenge tilnærmelsesalgoritmer til maksimale generelle tildelingsproblemer. I SODA'06: Proc