Problém s přiřazením

Úloha zadání je jedním ze základních kombinatorických optimalizačních problémů v oblasti matematické optimalizace nebo operačního výzkumu . Problém je najít minimální součet oblouků ve váženém bipartitním grafu .

Ve své nejobecnější podobě je problém formulován takto:

Existuje určitý počet děl a určitý počet účinkujících . Kterýkoli dodavatel může být pověřen prováděním jakékoli (ale pouze jedné) práce, ale za různé náklady. Dílo je nutné rozložit tak, aby bylo dílo dokončeno s minimálními náklady.

Pokud je počet pracovních míst a výkonných pracovníků stejný, pak se problém nazývá lineární problém přiřazení . Obvykle, když mluvíme o přiřazovacím problému bez dalších podmínek, mají na mysli lineární přiřazovací problém .

Algoritmy a zobecnění

Maďarský algoritmus je jedním z mnoha algoritmů navržených k řešení problému lineárního přiřazení v polynomiálním čase v počtu úloh.

Problém přiřazení je speciální případ problému dopravy , což je speciální případ problému toku minimálních nákladů , což je zase speciální případ problému lineárního programování . Kterýkoli z těchto problémů lze vyřešit simplexovou metodou , ale každá specializace má svůj vlastní efektivnější algoritmus založený na vlastnostech struktury problému.

Je-li účelová funkce vyjádřena ve čtvercích, mluvíme o kvadratickém přiřazovacím problému .

Příklad

Předpokládejme, že taxislužba má tři volná auta (exekutoři) a tři zákazníky (práce), kteří chtějí co nejdříve získat taxi. Firmě záleží na době přistavení taxi k zákazníkovi, takže u každého vozu je cena určena dobou, za kterou vůz dojede na čekací místo určené zákazníkem. Řešením problému zadání je distribuce strojů mezi zákazníky tak, aby celkové náklady (celková čekací doba) byly minimální.

Úkol zadání může být flexibilnější. Ve výše uvedeném příkladu nemusí být tři, ale čtyři taxíky zdarma, ale stále jsou zde tři zákazníci. Čtvrtého fiktivního zákazníka můžete přiřadit s nulovými náklady, zatímco přidělení vozu fiktivnímu zákazníkovi znamená „nedělat nic“.

Podobnou techniku lze použít, když počet objednávek může překročit počet dostupných vozů a vůz lze přiřadit k provedení několika zakázek, a také když lze zakázku přidělit několika pracovníkům (např. skupina, která se nevejde do jednoho taxíku). Můžete si také nastavit cíl zvýšit tržby spíše než minimalizovat cenu.

Formální matematická definice

Formální vyjádření problému zadání :

Jsou dány dvě množiny A a T stejné velikosti a je dána nákladová funkce C : A × T → R . Je potřeba najít bijekci f : A → T takovou, aby účelová funkce :

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

minimální.

Obvykle je nákladová funkce dána jako čtvercová matice C sestávající z reálných čísel, takže účelovou funkci lze zapsat jako:

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

Problém se nazývá „lineární“, protože jak účelová funkce, tak omezení obsahují pouze lineární výrazy.

Problém může být reprezentován jako problém lineárního programování s účelovou funkcí

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

a omezení

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

pro ,

i\in A

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

pro ,

j\in T

x_{ij}\geq 0

pro .

i,j\in A,T

Proměnná představuje přiřazení vykonavatele k zakázce , přičemž má hodnotu 1, pokud je vykonavatel přiřazen k dané zakázce, a 0 jinak. V této formulaci nemusí být řešení celé číslo, ale vždy existuje optimální řešení s celočíselnými hodnotami. Tato skutečnost vyplývá z absolutní unimodularity matice . První omezení vyžaduje, aby každému pracovníkovi byl přidělen přesně jeden úkol, druhé vyžaduje, aby byl každému úkolu přidělen jeden pracovník. $x_{ij}$ $i$ $j$

Viz také

Literatura

Hemdy A. Taha. Kapitola 5.4 Problém zadání. // Úvod do operačního výzkumu. 7. vydání. Za. z angličtiny. - M. : Nakladatelství "Williams", 2005.
Wagner G. Příloha 1.2 Řešení zadání // Základy operačního výzkumu. Za. z angličtiny. - M . : Nakladatelství "Mir", 1972 .. - T. 1.
Akof R., Sasieni M.,. Kapitola 5 Distribuční úkoly: Přidělování a alokace zdrojů // Základy operačního výzkumu. - M .: Nakladatelství "Mir", 1971.
Richard A. Brualdi. Třídy kombinatorických matic . - Cambridge: Cambridge University Press , 2006. - (Encyklopedie matematiky a jejích aplikací). — ISBN 0-521-86565-4 .
Rainer Burkard, M. Dell'Amico, S. Martello. Problémy s přiřazením (revidovaný dotisk). - SIAM, 2012. - ISBN 978-1-61197-222-1 .