Matematické Fórum

A každý člověk má předem určeno na které(á) pracoviště může být přidělen?

Tak, jak to píšeš stačí každého na každé pracoviště přidělit minimum a potom zbylými lidmi doplňovat pracoviště na maximum.

Nevím, jestli pomůžu, ale šlo by na to koukat, jako že hledáme nějaký vektor řešení X (pro pohodlnost asi bude lepší považovat za matici ř. m x n), kde X[i,j] je 1, pokud itého člověka zaměstnám na j-tém místě, jinak 0. Další podmínky snadno zapíšeme soustavou rovnic a nerovnic a máme normální (celočíselnou) úlohu lineárního programování, kterou půjde nakrmit počítač, maximalizujeme fci (suma přes i,j)X[i,j]

Uznávám, že to je dost ošklivé a asi děsně neefektivní (nechce se mi teď přemýšlet o složitosti, ale moc bych tomu nefandil ani proti klasickému bactrackingu), ale jde to nabouchat do počítače a třeba to nějak pomůže (možná někoho při této formulaci snáz napadne, jak to zjednodušit).

Na první  pohled lze úlohu malinko zjednodušit, ale to je ti asi jasné
- na 'neomezena' (tj vice nabidek nez uchazecu) pracoviste nacpu, koho muzu
- zaměstnám zoufalce s jedinou možností
- po opakovani zbyde to zajímavé - lidi a místa z více možnostmi. Tak nějak intuitivně bych asi koukal u každého místa na poměry potřebuji nacpat/dostupných a můžu nacpat/dostupných a vybíral lidi, kteří se mi někam hodí a jinde je oželím. S trochou přemýšlení se možná najde něco, co zas úlohu zjednoduší.