1 2 3 4 5 6 7 8 9 10 11 12

 
El problema de las asignaciones

Podemos representar problema de las asignaciones mediante una red de transporte. Utilizamos entonces un grafo $ G=(V, E) $ bipartido, que se define como un grafo en donde el conjunto de vértices $ V $ se puede dividir en dos subconjuntos disjuntos $ V_1 $ y $ V_2 $, de manera que cada lado $ e\in E $, es incidente en un vértice de $ V_1 $ y en otro de $ V_2 $. Para convertir un grafo bipartido en una red de transporte es necesario agregar una superfuente $\displaystyle s $ y un superdepósito $\displaystyle t $. En la Fig.1.4 el grafo bipartido original incluía solo los nodos $\displaystyle p_i $ y $\displaystyle t_i $. El peso asignado a los nuevos lados que salen de $ s $ a los $ p_i $ es de 1, y de igual forma el peso que llega de los $ t_i $ a $ t $ es también de 1.

 

\begin{figure}\begin{center} \unitlength=1.50mm \linethickness{0.4pt} \begin{... ...kebox(0,0)[cc]{$ t $}} \end{picture} \end{center}\vspace{-12em} \end{figure}

Figura 1.4: Red de transporte asignada al problema de las asignaciones.

 

Se debe observar que el peso asignado a cada lado en la red de la Fig.1.4, es de 1. Estamos suponiendo aquí que cada persona $ p_i $ puede atender un único trabajo $ t_j $, de los que manifiesta en la Fig.1.4, sin embargo puede darse el caso en que una persona, por ejemplo, pueda atender dos trabajos de los tres que apetece.Para representar esta situación es suficiente asignar un peso de dos a la arista que sale de la superfuente $ s $ a la persona con esta característica. Las siguientes definiciones nos permiten formalizar aún más los conceptos que hemos venido estudiando:

Definición
Supóngase que $ R = \left\{\,p_1, p_2, \cdots, p_m\, \right\} $ es un conjunto de $ m $ recursos y que $ N=\left\{\,t_1, t_2,\cdots, t_n\, \right\} $ es un conjunto de $ n $ necesidades, entonces:

  1. Una manifestación preferencial de $ R $ a $ N $ es un conjunto $ M \subseteq R\times N $.

  2. La matriz $ A $ que satisface $ A[i, j]=1 $ si $ (i, j) \in M $ y $ A[i, j]=0 $ si no, se llama matriz de preferencias de la manifestación preferencial $ M $.

  3. La red de transporte $ G=(V, E) $, dada por:

    1. $ V= R\cup N\cup \left\{\,s\, \right\} \cup \left\{\,t\, \right\} $, en donde $ s $ y $ t $ son respectivamente la superfuente y el superdepósito,

    2. $ E = M \cup \left\{\,(s, p_i): 1\leq i\leq m\, \right\} \cup\left\{\,(t_i, t): 1\leq i\leq n\, \right\} $,

    3. y con un peso de 1 asociado a cada arista existente,se llama red de preferencias asociada a la manifestación preferencial $ M $.

  4. La matriz $ C $ de tamaño $ (m+n+2)\times (m+n+2) $ que satisface $ C[u, v] =1 $ si $ (u, v) \in E $ y $ C[u, v] =0 $ si no, se llama la matriz de capacidades de la red de preferencias.

 1 2 3 4 5 6 7 8 9 10 11 12

Revista Virtual, Matemática Educación e Internet.
Derechos Reservados.