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.

Método Grafico

Método Grafico

I. Definición del Método.

 

El método grafico para la resolución de problemas de programación lineal (PL) consiste en representar gráficamente las restricciones, condiciones técnicas y función objetivo de dicho problema  para tratar de identificar el área de soluciones factibles, para lograr así una tabla con valores que las variables de decisión pueden adoptar, con lo cual se busca el valor máximo que la función objetivo puede obtener en base a estos valores.

Es importante mencionar que este método solo es práctico para problemas PL con únicamente 2 variables de decisión, pues cada variable representa un plano adicional en la grafica, lo que se traduce en graficas en dimensiones mayores a 2.

                

II. Pasos del Método.

 

1.    Se plantea el problema como un problema PL, en el caso de que no se tenga ya en esta forma.

2.    se grafican las soluciones factibles, o el espacio de soluciones (factible), que satisfagan todas las restricciones en forma simultánea, es decir, graficar cada restricción como si fuera una función lineal, con lo cual se encontrará un área que contiene todas las soluciones factibles del problema.

3.    trazar cada línea recta en el plano y la región en cual se encuentra cada restricción cuando se considera la desigualdad lo indica la dirección de la flecha situada sobre la línea recta asociada es decir, se indica con una línea hacia donde se cumple la desigualdad, hacia valores positivos, o hacia valores negativos.

4.     Cada punto contenido o situado en la frontera del espacio de soluciones satisfacen todas las restricciones y por consiguiente, representa un punto factible.

5.    luego de obtener el conjunto de soluciones factibles, se identifican los vértices de la figura generada por el área factible, y se genera una tabla con los puntos de los vértices.

6.    se evalúa cada punto encontrado en la función objetivo, y el punto con el que se obtenga el mayor o menor valor, según sea el caso(Minimización o Maximización), será la solución factible del problema.

III. Ejemplo Practico.

Cierto fabricante produce dos artículos, A y B, para lo que requiere la utilización de dos secciones de producción: sección de montaje y sección de pintura. El artículo A requiere una hora de trabajo en la sección de montaje y dos en la de pintura; y el artículo B, tres horas en la sección de montaje y una hora en la de pintura. La sección de montaje solo puede estar en funcionamiento nueve horas diarias, mientras que la de pintura solo ocho horas cada día. El beneficio que se obtiene produciendo el artículo B es de 40 dólares y el de A es de 20 dólares.

Calcula la producción diaria de los artículos A y B que maximiza el beneficio.

 

1.  Se plantea el problema:

max   20A  +   40B

SA         2A  +      B<=8

               A  +     3B<=9

                        A, B>=0

2.  Se grafican las restricciones para encontrar el área factible:

 

3.  Se encuentran los valores de los vértices(Extremos del polígono formado por la solución factible)

 

Punto (B, A)	Función objetivo (Z=20A + 40 B)	Valor de Z
(0,0)	Z=20(0) + 40(0)	Z=0
(0,4)	Z=20(4) + 40(0)	Z=80
(2,3)	Z=20(3) + 40(3)	Z=140
(0,3)	Z=20(0) + 40(3)	Z=120

 

4.   Solución del problema

Se deben producir 2 productos diarios de tipo b y 3 de tipo A para una ganancia de 140.

Contribución de: Juan Maldonado, Frederick Jiménez, Johansen Pineda, Marlon Lizardo, Luis Mejía.