Problema del 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

Problema de Asignación de Personal

Ejemplo:

 

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
Candidato1	10	6	6	5
Candidato2	8	7	6	6
Candidato3	8	6	5	6
Candidato4	9	7	7	6
Candidato5	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 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

Problema de los Árboles Frutales

Un agricultor tiene una parcela de 640m² para dedicarla al cultivo de árboles frutales: naranjos, perales, manzanos y limoneros. Se pregunta de qué forma debería repartir la superficie de la parcela entre las variedades para conseguir el máximo beneficio sabiendo que:

• cada naranjo necesita un mínimo de 16m², cada peral 4m², cada manzano 8m² y cada limonero 12m².
• dispone de 900 horas de trabajo al año, necesitando cada naranjo 30 horas al año, cada peral 5 horas, cada manzano 10 horas, y cada limonero 20 horas.
• a causa de la sequía, el agricultor tiene restricciones para el riego: le han asignado 200m³ de agua anuales. Las necesidades anuales son de 2m³ por cada naranjo, 1m³ por cada peral, 1m³ por cada manzano, y 2m³ por cada limonero.
• los beneficios unitarios son de 50, 25, 20, y 30 € por cada naranjo, peral, manzano y limonero respectivamente.

Se determinan las variables de decisión y se representan algebraicamente. En este caso:

• X1: número de naranjos
• X2: número de perales
• X3: número de manzanos
• X4: número de limoneros

Se determinan las restricciones y se expresan como ecuaciones o inecuaciones de las variables de decisión. Dichas restricciones se deducen de las necesidades de cada árbol de terreno, horas de trabajo anuales, y necesidades de riego:

• Necesidades de terreno: 16·X1 + 4·X2 + 8·X3 + 12·X4 ≤ 640
• Necesidades de horas anuales: 30·X1 + 5·X2 + 10·X3 + 20·X4 ≤ 900
• Necesidades de riego: 2·X1 + X2 + X3 + 2·X4 ≤ 200

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 el número de árboles no puede ser negativo y además debe ser un número entero:

• Xi ≥ 0
• Xi son enteros

Se determina la función objetivo:

• Maximizar Z = 50·X1 + 25·X2 + 20·X3 + 30·X4

Problema de Transporte de Mercancías

Para este tipo de problemas, aunque pueden ser resueltos por el método del Simplex, existe un método específico de más fácil resolución: el método del transporte o método simplificado del Simplex para problemas de transporte. Este método ahorra bastante tiempo y cálculos frente al método del Simplex tradicional.

Sin embargo el problema se modela de la misma forma.

 

Ejemplo

Un fabricante desea despachar varias unidades de un artículo a tres tiendas T1, T2, y T3. Dispone de dos almacenes desde donde realizar el envío, A y B. En el primero dispone de 5 unidades de este artículo y en el segundo 10. La demanda de cada tienda es de 8, 5, y 2 unidades respectivamente. Los gastos de transporte de un artículo desde cada almacén a cada tienda están expresados en la tabla:

	T1	T2	T3
A	1	2	4
B	3	2	1

¿Cómo ha de realizar el transporte para que sea lo más económico posible?

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

• Xi: número de unidades transportadas desde cada almacén a cada tienda
• X1: número de unidades transportadas desde el almacén A hasta la tienda T1
• X2: número de unidades transportadas desde el almacén A hasta la tienda T2
• X3: número de unidades transportadas desde el almacén A hasta la tienda T3
• X4: número de unidades transportadas desde el almacén B hasta la tienda T1
• X5: número de unidades transportadas desde el almacén B hasta la tienda T2
• X6: número de unidades transportadas desde el almacén B hasta la tienda T3

Se determinan las restricciones y se expresan como ecuaciones o inecuaciones de las variables de decisión. Dichas restricciones se deducen de la disponibilidad de unidades que hay en cada almacén así como de la demanda de cada tienda:

• Disponibilidad en el almacén A: X1 + X2 + X3 = 5
• Disponibilidad en el almacén B: X4 + X5 + X6 = 10
• Demanda de la tienda T1: X1 + X4 = 8
• Demanda de la tienda T2: X2 + X5 = 5
• Demanda de la tienda T3: X3 + X6 = 2

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 la cantidad de unidades no puede ser negativa y debe ser además un número entero:

• Xi ≥ 0
• Xi son enteros

Se determina la función objetivo:

• Minimizar Z = X1 + 2·X2 + 4·X3 + 3·X4 + 2·X5 + X6

Problema de Trasporte de Tropas

Un destacamento militar formado por 50 soldados ingenieros, 36 zapadores, 22 de las fuerzas especiales, y 120 soldados de infantería como tropa de apoyo, ha de transportarse hasta una posición estratégica importante. En el parque de la base se dispone de 4 tipos de vehículos A, B, C, y D, acondicionados para transporte de tropas. El número de personas que cada vehículo puede transportar es 10, 7, 6, y 9, de la forma en que se detalla en la siguiente tabla:

	Ingenieros	Zapadores	Fuerzas especiales	Infantería
A	3	2	1	4
B	1	1	2	3
C	2	1	2	1
D	3	2	3	1

El combustible necesario para que cada vehículo llegue hasta el punto de destino se estima en 160, 80, 40, y 120 litros respectivamente. Si queremos ahorrar combustible, ¿cuántos vehículos de cada tipo habrá que utilizar para que el consumo sea el mínimo posible?

Se determinan las variables de decisión y se representan algebraicamente. En este caso:

• Xi: número de vehículos de cada tipo que se usen
• X1: número de vehículos de tipo A
• X2: número de vehículos de tipo B
• X3: número de vehículos de tipo C
• X4: número de vehículos de tipo D

Se determinan las restricciones y se expresan como ecuaciones o inecuaciones de las variables de decisión. Dichas restricciones se deducen de los soldados que deben ser transportados:

• Ingenieros: 3·X1 + X2 + 2·X3 + 3·X4 ≥ 50
• Zapadores: 2·X1 + X2 + X3 + 2·X4 ≥ 36
• Fuerzas especiales: X1 + 2·X2 + 2·X3 + 3·X4 ≥ 22
• Infantería: 4·X1 + 3·X2 + X3 + X4 ≥ 120

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 la cantidad de vehículos no puede ser negativa y debe ser además un número entero:

• Xi ≥ 0
• Xi son enteros

Se determina la función objetivo:

• Minimizar Z = 160·X1 + 80·X2 + 40·X3 + 120·X4

Problema de la Dieta

El problema de la dieta fue uno de los primeros sobre optimización. Se trataba hallar la manera más económica de alimentar al ejercito pero asegurando al mismo tiempo unos determinados niveles nutricionales.

Este tipo de problema se puede plantear en distintas formas tales como minimizar los gastos de la compra, dieta para el ganado, una dieta adelgazante que cumpla unos determinados niveles de calorías, proteínas, hidratos de carbono, ....

 

Ejemplo

Nos proponemos alimentar el ganado de una granja con una dieta que sea la más económica posible. Dicha dieta debe contener cuatro tipos de nutrientes que llamamos A, B, C, y D. Estos componentes se encuentran en dos tipos de piensos M y N. La cantidad, en gramos, de cada componente por kilo de estos piensos viene dada en la tabla siguiente:

	A	B	C	D
M	100	-	100	200
N	-	100	200	100

La dieta diaria de un animal debe estar compuesta por al menos 0.4Kg del componente A, 0.6Kg del componente B, 2Kg del componente C, y 1.7Kg del componente D. El compuesto M cuesta 0.2€/Kg y el compuesto N 0.08€/Kg. ¿Qué cantidades de piensos M y N deben adquirirse para que el gasto de comida sea el menor posible?

Se determinan las variables de decisión y se representan algebraicamente. En este caso:

• X1: cantidad de pienso M en Kg
• X2: cantidad de pienso N en Kg

Se determinan las restricciones y se expresan como ecuaciones o inecuaciones de las variables de decisión. Dichas restricciones se deducen de la composición requerida para la dieta diaria (en Kg):

• En el componente A: 0.1·X1 + 0·X2 ≥ 0.4
• En el componente B: 0·X1 + 0.1·X2 ≥ 0.6
• En el componente C: 0.1·X1 + 0.2·X2 ≥ 2
• En el componente D: 0.2·X1 + 0.1·X2 ≥ 1.7

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 cantidades de pienso que forman la dieta no pueden ser negativas:

• X1 ≥ 0
• X2 ≥ 0

Se determina la función objetivo:

• Minimizar Z = 0.2·X1 + 0.08·X2

Teoría sobre el modelado de problemas

Para poder solucionar un problema mediante un algoritmo primero se debe extraer toda la información que nos aporta el enunciado y preparar el problema para dicho algoritmo.

 

Los pasos para modelar un problema son los siguientes:

 

• Paso 1: Se determinan las variables de decisión y se expresan algebraicamente.
•  
• X1,..., Xn
•  
•  Paso 2: Se determinan las restricciones y se expresan como ecuaciones o inecuaciones de las variables de decisión:

                   A11·X1 + A12·X2 + ... + A1n·Xn ≥, ≤, ó = b1
                   A21·X1 + A22·X2 + ... + A 2n·Xn ≥, ≤, ó = b2...
                   Am1·X1 + Am2·X2 + ... + Amn·Xn ≥, ≤, ó = bm

•  Paso 3: 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, ...
•  
• X1,..., Xn ≥ 0
• X1,..., Xn son números enteros, o son booleanos,...
 
• Paso 4: Se determina la función objetivo.
  • Maximizar o minimizar Z = C1·X1 + C2·X2 + ... + Cn·Xn
  •  
• Paso 5: Se encuentra la solución.