Opgave problem

Opgaveproblemet er et af de grundlæggende kombinatoriske optimeringsproblemer inden for matematisk optimering eller operationsforskning . Problemet er at finde minimumsummen af buer i en vægtet todelt graf .

I sin mest generelle form er problemet formuleret som følger:

Der er et vist antal værker og et vist antal udøvende kunstnere . Enhver entreprenør kan udpeges til at udføre et hvilket som helst (men kun ét) job, men til forskellige omkostninger. Det er nødvendigt at fordele arbejdet for at fuldføre arbejdet med minimale omkostninger.

Hvis antallet af job og udførende er det samme, kaldes problemet et lineært tildelingsproblem . Normalt, når man taler om et tildelingsproblem uden yderligere betingelser, mener de normalt et lineært tildelingsproblem .

Algoritmer og generaliseringer

Den ungarske algoritme er en af mange algoritmer designet til at løse det lineære tildelingsproblem i polynomisk tid i antallet af job.

Tildelingsproblemet er et specialtilfælde af transportproblemet , som er et særligt tilfælde af minimumsomkostningsflowproblemet , som igen er et specialtilfælde af det lineære programmeringsproblem . Ethvert af disse problemer kan løses ved simplex-metoden , men hver specialisering har sin egen mere effektive algoritme baseret på funktionerne i problemstrukturen.

Hvis den objektive funktion er udtrykt i kvadrater, taler man om en andengradsopgave .

Eksempel

Antag, at et taxaselskab har tre frie biler (eksekutorer) og tre kunder (job), som ønsker at få en taxa hurtigst muligt. Firmaet bekymrer sig om tidspunktet for levering af taxaen til kunden, så for hver bil bestemmes prisen af det tidspunkt, hvormed bilen når det ventested, som kunden har angivet. Løsningen på opgaveproblemet er at fordele maskiner blandt kunderne på en sådan måde, at den samlede omkostning (samlet ventetid) er minimal.

Opgaveopgaven kan gøres mere fleksibel. I ovenstående eksempel er der måske ikke tre, men fire gratis taxaer, men der er stadig tre kunder. Du kan tildele en fjerde fiktiv kunde uden omkostninger, mens at allokere en bil til en fiktiv kunde betyder "gør ingenting".

En lignende teknik kan bruges, når antallet af ordrer kan overstige antallet af tilgængelige biler, og bilen kan tildeles til at udføre flere opgaver, og også når jobbet kan tildeles flere udførende (f.eks. hvis kunden er en gruppe, der ikke passer i én taxa). Du kan også sætte målet om at øge omsætningen frem for at minimere prisen.

Formel matematisk definition

Formel redegørelse for opgaveproblemet :

Givet to sæt A og T af samme størrelse og givet en omkostningsfunktion C : A × T → R. Det er nødvendigt at finde en bijektion f : A → T således at den objektive funktion :

\sum _{a\in A}C(a,f(a))

minimal.

Normalt er omkostningsfunktionen givet som en kvadratisk matrix C bestående af reelle tal, således at den objektive funktion kan skrives som:

{\displaystyle \sum _{a\in A}C_{a,f(a)))

Problemet kaldes "lineær", fordi både den objektive funktion og begrænsningerne kun indeholder lineære udtryk.

Problemet kan repræsenteres som et lineært programmeringsproblem med en objektiv funktion

{\displaystyle \sum _{i\in A}\sum _{j\in T}C(i,j)x_{ij))

og restriktioner

\sum _{j\in T}x_{ij}=1

for ,

i\in A

\sum _{i\in A}x_{ij}=1

for ,

j\in T

x_{ij}\geq 0

for .

i,j\in A,T

Variablen repræsenterer tildelingen af en udførende til et job , idet den tager værdien 1, hvis udføreren er tildelt det pågældende job og 0 ellers. I denne formulering er løsningen muligvis ikke heltal, men der findes altid en optimal løsning med heltalsværdier. Dette faktum følger af matrixens absolutte unimodularitet . Den første begrænsning kræver, at der tildeles præcis én opgave til hver medarbejder, den anden kræver, at én arbejder tildeles hver opgave. $x_{ij}$ $jeg$ $j$

Se også

Litteratur

Hemdy A. Taha. Kapitel 5.4 Opgaveproblemet. // Introduktion til operationsforskning. 7. udgave. Om. fra engelsk. - M . : Forlaget "Williams", 2005.
Wagner G. Bilag 1.2 Løsning af opgaveproblemet // Fundamentals of Operations Research. Om. fra engelsk. - M . : Forlaget "Mir", 1972 .. - T. 1.
Akof R., Sasieni M.,. Kapitel 5 Fordelingsopgaver: Tildeling og allokering af ressourcer // Fundamentals of Operations Research. - M . : Forlaget "Mir", 1971.
Richard A. Brualdi. Kombinatoriske matrixklasser . - Cambridge: Cambridge University Press , 2006. - (Encyclopedia of Mathematics and Its Applications). — ISBN 0-521-86565-4 .
Rainer Burkard, M. Dell'Amico, S. Martello. Opgaveproblemer (Revideret genoptryk). - SIAM, 2012. - ISBN 978-1-61197-222-1 .