Ingenieria

Una empresa ha preseleccionado 5 candidatos para ocupar 4 puestos de trabajo en dicha empresa. Los puestos de trabajo consisten en manejar 4 máquinas diferentes (un trabajador para cada máquina). La empresa puso a prueba a los 5 trabajadores en las 4 máquinas, realizando el mismo trabajo todos ellos en cada una de las máquinas, obteniendo los siguientes tiempos:
| Máquina1 | Máquina2 |Máquina3 | Máquina4 |
Cand1 | 10 | 6 | 6 | 5 |
Cand2 | 8 | 7 | 6 | 6 |
Cand3 | 8 | 6 | 5 | 6 |
Cand4 | 9 | 7 | 7 | 6 |
Cand5 | 8 | 7 | 6 | 5 |
Determinar qué candidatos debe seleccionar la empresa y a qué máquinas debe asignarlos.
Se determinan las variables de decisión, en este caso:
Xij: acción de que el trabajador i es asignado a la máquina j (0 indica que el trabajador no ha sido asignadoy 1 que sí ha sido asignado)
Se determinan las restricciones y se expresan como ecuaciones o inecuaciones de las variables de decisión. Dichas restricciones son que cada trabajador debe ser asignado a una sola máquina y no debe quedar ninguna máquina sin un trabajador asignado a ella:
Cada trabajador debe estar asignado a una sola máquina o a ninguna si no se selecciona:
X11 + X12 + X13 +X14=1
X21 + X22 + X23 + X24 =1
X31 + X32 + X33 + X34 = 1
X41 + X42 + X43 + X44 = 1
X51 + X52 + X53 + X54 = 1
En cada máquina debe haber un trabajador:
X11 + X21 + X31 + X41 + X51 = 1
X12 + X22 + X32 + X42 + X52 = 1
X13 + X23 + X33 + X43 + X53 = 1
X14 + X24 + X34 + X44 + X54 = 1
Se expresan todas las condiciones implícitamente establecidas por la naturaleza de las variables: que no puedan sernegativas, que sean enteras, que solo puedan tomar determinados valores, … En este caso las restricciones son que las asignaciones de trabajadores a máquinas no puede ser negativa y debe ser además una variable booleana (0 no se asigna, 1 se asigna):
Xij = 0
Xij es booleano
Se determina la función objetivo:
* Minimizar Z = 10·X11 + 8·X21 + 8·X31 + 9·X41 + 8·X51 + 6·X12 + 7·X22 + 6·X32 +7·X42 + 7·X52 + 6·X13 + 6·X23 + 5·X33 + 7·X43 + 6·X53 + 5·X14 + 6·X24 + 6·X34 + 6·X44 + 5·X54
Camino mínimo
Los problemas conocidos como problemas del camino mínimo o camino más corto, tratan como su nombre indica de hallar la ruta mínima o más corta entre dos puntos. Este mínimo puede ser la distancia entre los puntos origen y destino o bien el tiempo transcurrido para trasladarse desde un punto aotro. Se aplica mucho para problemas de redes de comunicaciones.
Este tipo de problemas pueden ser resueltos por el método del Simplex, sin embargo existen otros métodos más eficientes como por ejemplo el algoritmo de Dijkstra o el de Bellman-Ford.
Ejemplo
Una persona tiene que desplazarse a diario de un pueblo 1 a otro 7. Está estudiando cual es el trayecto más corto usando un mapa decarreteras. Las carreteras y sus distancias están representadas en la figura siguiente:

Se determinan las variables de decisión, en este caso:
Xij: acción de desplazarse del pueblo i al j (0 indica que no hay desplazamiento y 1 que sí hay desplazamiento)
Se determinan las restricciones y se expresan como ecuaciones o inecuaciones de las variables de decisión. Dichas restricciones se deducen delbalance entre los posibles caminos que parten desde cada pueblo y los que llegan hasta él (obviando los caminos que nos devuelvan al punto de partida y los que provengan del punto de destino):
Balance de caminos del pueblo 1: X12 + X13 = 1
Balance de caminos del pueblo 2: X24 + X25 – X12 – X42 – X52 = 0
Balance de caminos del pueblo 3: X34 + X36 – X13 – X43 – X63 = 0
Balance de caminos del pueblo4: X42 + X43 + X45 – X24 – X34 – X54 = 0
Balance de caminos del pueblo 5: X52 + X54 + X57 – X25 – X45 = 0
Balance de caminos del pueblo 6: X63 + X67 – X36 = 0
Balance de caminos del pueblo 7: – X57 – X67 = -1
Se expresan todas las condiciones implícitamente establecidas por la naturaleza de las variables: que no puedan ser negativas, que sean enteras, que solo puedan tomar determinados...