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:

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 asignado y 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 ser negativas, 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 a otro. 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 de carreteras. 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 del balance 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 pueblo 4: 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 valores, … En este caso las restricciones son que las variables deben ser booleanas (0 no se toma el camino, 1 se toma), y por lo tanto no pueden ser negativas:

• Xij  0
• Xij es booleano

Se determina la función objetivo:

• Minimizar Z = 12·X12 + 4·X13 + 5·X24 + 3·X25 + 2·X34 + 10·X36 + 5·X42 + 2·X43 + 10·X45 + 3·X52 + 10·X54 + 2·X57 + 10·X63 + 4·X67

Localización

Una empresa tiene la exclusiva para la distribución de un producto en 4 poblaciones. En un estudio de mercado se ha determinado la demanda potencial, según se muestra en la siguiente tabla:

Se sabe que los costes de transporte son de 0.02‚¬ por Km y unidad transportada. La distancia entre los pueblos es la que figura en la tabla siguiente:

Para abaratar los costes de transporte se decide instalar un almacén con capacidad para 6000 unidades en dos de estas cuatro poblaciones. Determinar en que poblaciones deben instalarse los almacenes.

Se determinan las variables de decisión, en este caso:

• Xij: cantidad enviada del almacén i a la población j
• Yi: almacén situado en la población i (0 indica que no hay ningún almacén y 1 que sí­ lo hay)

Se determinan las restricciones y se expresan como ecuaciones o inecuaciones de las variables de decisión. Dichas restricciones se deducen de la siguiente manera:

• Las unidades que se enví­an a cada población desde los almacenes deben cumplir con la demanda de dicha población:
  • X11 + X21 + X31 + X41 = 3000
  • X12 + X22 + X32 + X42 = 2000
  • X13 + X23 + X33 + X43 = 2500
  • X14 + X24 + X34 + X44 = 2700
  Solo se crearán dos almacenes:
• • Y1 + Y2 + Y3 + Y4 = 2
• La cantidad de unidades que puede enviar cada almacén debe ser menor o igual que la capacidad de éste:
  • X11 + X12 + X13 + X14 = 6000·Y1
  • X21 + X22 + X23 + X24 = 6000·Y2
  • X31 + X32 + X33 + X34 = 6000·Y3
  • X41 + X42 + X43 + X44 = 6000·Y4

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 valores, … En este caso las restricciones son que las unidades enviadas desde cada almacén no pueden ser negativas y además la variable que determina si se creará o no un almacén debe ser booleana (0 no se crea, 1 se crea):

• Xij = 0
• Yi es booleano

Se determina la función objetivo:

• Minimizar Z = 0.5·X12 + 0.7·X13 + 0.6·X14 + 0.5·X21 + 0.4·X23 + 0.8·X24 + 0.7·X31 + 0.4·X32 + 0.6·X34 + 0.6·X41 + 0.8·X42 + 0.6·X43

Inversión en bolsa

Una inversora dispone de 50.000‚¬ para invertir entre las cuatro siguientes posibilidades: bolsa X, bolsa Y, bonos X, y bonos Y, por el periodo de un año. Un máximo de 10.500€ puede ser invertido en bonos X, y un máximo de 10.000€ en bonos Y. La inversión en la bolsa X conlleva un riesgo considerable por lo que se determina no invertir más de un cuarto de la inversión total. La cantidad invertida en la bolsa Y debe ser al menos tres veces la cantidad invertida en la bolsa X. Además, la inversora requiere que la inversión en bonos sea al menos tan grande como la mitad de la inversión en las bolsas. Los retornos netos anuales se estiman según se muestra en la siguiente tabla:

¿Cual es la forma optima de realizar la inversión para conseguir las máximas ganancias?

Se determinan las variables de decisión, en este caso:

• X1: inversión en bolsa X
• X2: inversión en bolsa Y
• X3: inversión en bonos X
• X4: inversión en bonos Y

Se determinan las restricciones y se expresan como ecuaciones o inecuaciones de las variables de decisión. Dichas restricciones se deducen de las decisiones tomadas por la inversora sobre la forma de invertir y de la inversión máxima que se puede realizar:

• X1 + X2 + X3 + X4 = 50000
• X1 = 12500
• X3 =10500
• X4 = 10000
• 3·X1 – X2 = 0
• 0.5·X1 + 0.5·X2 – X3 – X4 = 0

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 valores, … En este caso la única restricción es que las inversiones no pueden ser negativas:

• Xi = 0

Se determina la función objetivo:

• Maximizar Z = 0.2·X1 + 0.1·X2 + 0.09·X3 + 0.11·X4