Autor Zpráva
Pato
Profil *
Zdravim,
potrebujem pomoct s jedným projektom. Ide o to:

V databáze mám nejakých ľudí, ktorí ovládajú pozíciu A, B, A+B.
Z tejto databazy potrebujem ludi do pozicie A1, A2, A3, A4, B1, B2, B3, B4,
pricom ludia, ktori ovladaju A mozu ist do pozicii A1-A4, B do pozicii B1-B4 a A+B do vsetkych pozicii. U tychto ludi mam este bodove hodnotenie, takze, najlepsi bude bud v A1, alebo v B1.

Názorny priklad:
Mam, napr. tychto 10 ludi, vedla mien su pozicie ktore ovladaju:

Peter - A
Julo - A
Adam - A+B
Pavol - B
Tomas - A+B
Lucia - A+B
Veronika - B
Natalia - A
Dagmar - A
Filip - B
-------------------------
Z nich potrebujem vybrat 8 ludi, ktori im prideli program takuto poziciu:
Peter: A1
Julo: A2
Adam:B1
Pavol:B2
Tomas:A3
Lucia:B3
Veronika:B4
Natalia:A4


Ak mam napr. v prvej osmicke 5ludi, co ovladaju iba poziciu A, tak vyberie iba prvych 4, a napr. B4 bude nejaky bud 9. clovek alebo horsi...


Mohli by ste ma prosim vas nejako nakopnut. Popripade poradit, ake php funkcie by sa dali vyuzit? Jedine, co ma napada, su vela vela podmienok urobit, ale myslim si, ze to bude velmi neefektivne to takto urobit. Dakujem za rady .
juriad
Profil
tyto a podobné úlohy lze řešit lineárním programováním

na každé místo chceš přesně jednoho člověka
každého člověka chceš použít maximálně jednou
chceš maximální součet pozice krát hodnocení všech obsazených osob

proměnné jsou buď 0, nebo 1; značení: proměnná a2,1 je pozice A2 pro první osobu

váha pozice (čím vyšší má pozice váhu, tím lépe; toto závisí na tvé volbě); značení: konstanta va1 je váha pozice a1
hodnocení osoby (to bys měl dopředu znát); značení: konstanta h1 je hodnocení první osoby

toto značení je čistě lokální kvůli nemožnosti používat indexy

na tomto příkladu by to vypadalo:

nerovnice pro osoby:
a1,1 + a2,1 + a3,1 + a4,1 <= 1 // petr může být jen na pozicích A
a1,2 + a2,2 + a3,2 + a4,2 <= 1 // julo to samé
a1,3 + a2,3 + a3,3 + a4,3 + b1,3 + b2,3 + b3,3 + b4,3 <= 1 // adam na A i B
b1,4 + b2,4 + b3,4 + b4,4 <= 1 // pavol jen na B
a1,5 + a2,5 + a3,5 + a4,5 + b1,5 + b2,5 + b3,5 + b4,5 <= 1 // tomas
a1,6 + a2,6 + a3,6 + a4,6 + b1,6 + b2,6 + b3,6 + b4,6 <= 1 // lucia
b1,7 + b2,7 + b3,7 + b4,7 <= 1 // veronika
a1,8 + a2,8 + a3,8 + a4,8 <= 1 // natalia
a1,9 + a2,9 + a3,9 + a4,9 <= 1 // dagmar
b1,10 + b2,10 + b3,10 + b4,10 <= 1 // filip

rovnice pro pozice:
a1,1 + a1,2 + a1,3 + a1,5 + a1,6 + a1,8 + a1,9 = 1 // pozice a1
a2,1 + a2,2 + a2,3 + a2,5 + a2,6 + a2,8 + a2,9 = 1 // pozice a2
a3,1 + a3,2 + a3,3 + a3,5 + a3,6 + a3,8 + a3,9 = 1 // pozice a3
a4,1 + a4,2 + a4,3 + a4,5 + a4,6 + a4,8 + a4,9 = 1 // pozice a4
b1,3 + b1,4 + b1,5 + b1,6 + b1,7 + b1,10 = 1 // pozice b1
b2,3 + b2,4 + b2,5 + b2,6 + b2,7 + b2,10 = 1 // pozice b2
b3,3 + b3,4 + b3,5 + b3,6 + b3,7 + b3,10 = 1 // pozice b3
b4,3 + b4,4 + b4,5 + b4,6 + b4,7 + b4,10 = 1 // pozice b4

a chceš maximalizovat hodnotu výrazu:
va1*h1*a1,1 + va1*h2*a1,2 + va1*h3*a1,3 + va1*h5*a1,5 + va1*h6*a1,6 + va1*h8*a1,8 + va1*h9*a1,9  + 
va2*h1*a2,1 + va2*h2*a2,2 + va2*h3*a2,3 + va2*h5*a2,5 + va2*h6*a2,6 + va2*h8*a2,8 + va2*h9*a2,9  + 
va3*h1*a3,1 + va3*h2*a3,2 + va3*h3*a3,3 + va3*h5*a3,5 + va3*h6*a3,6 + va3*h8*a3,8 + va3*h9*a3,9  + 
va4*h1*a4,1 + va4*h2*a4,2 + va4*h3*a4,3 + va4*h5*a4,5 + va4*h6*a4,6 + va4*h8*a4,8 + va4*h9*a4,9  + 
vb1*h3*b1,3 + vb1*h4*b1,4 + vb1*h5*b1,5 + vb1*h6*b1,6 + vb1*h7*b1,7 + vb1*h10*b1,10  + 
vb2*h3*b2,3 + vb2*h4*b2,4 + vb2*h5*b2,5 + vb2*h6*b2,6 + vb2*h7*b2,7 + vb2*h10*b2,10  + 
vb3*h3*b3,3 + vb3*h4*b3,4 + vb3*h5*b3,5 + vb3*h6*b3,6 + vb3*h7*b3,7 + vb3*h10*b3,10  + 
vb4*h3*b4,3 + vb3*h4*b4,4 + vb4*h5*b4,5 + vb4*h6*b4,6 + vb4*h7*b4,7 + vb4*h10*b4,10

vypadá to šíleně, ale přesně toto jsou podmínky, kterými je omezené řešení

jako aproximace by mohl sloužit podobný program:
měl bys jen pozice A a B, přičemž jejich velikost by byla 4 místa

nerovnice pro osoby:
a,1 <= 1
a,2 <= 1
a,3 + b,3 <= 1
b,4 <= 1
a,5 + b,5 <= 1
a,6 + b,6 <= 1
b,7 <= 1
a,8 <= 1
a,9 <= 1
b,10 <= 1

rovnice pro pozice:
a,1 + a,2 + a,3 + a,5 + a,6 + a,8 + a,9 = 4
b,3 + b,4 + b,5 + b,6 + b,7 + b,10 = 4

a chceš maximalizovat hodnotu výrazu:
h1*a,1 + h2*a,2 + h3*a,3 + h5*a,5 + h6*a,6 + h8*a,8 + h9*a,9  + 
h3*b,3 + h4*b,4 + h5*b,5 + h6*b,6 + h7*b,7 + h10*b,10

tento menší program bude dávat podobné řešení ale bohužel pro hodnocení a tvůj příklad výsledku:
1, 1, 10, 10, 5, 10, 10, 1, 0, 0
tak máš na pozici A osoby s hodnocením (5, 1, 1, 1) a B (10, 10, 10, 10), přestože by bylo lepší Tomáše a Adama prohodit: A=(10, 1, 1, 1) a B=(10, 10, 10, 5)
to ti ale tento menší program neumožní rozlišit (pro obě řešení vyjde maximalizační funkce stejně)

takto formulované úlohy lze řešit docela efektivně (klidně soustavy deseti-tisíců (ne)rovnic), ale neznám žádný řešič napsaný v php
ale můžeš využít třeba c-čkovou knihovnu glpk, nebo program sage

Vaše odpověď

Mohlo by se hodit


Prosím používejte diakritiku a interpunkci.

Ochrana proti spamu. Napište prosím číslo dvě-sta čtyřicet-sedm:

0