ANOTACIÓN 2012 Serie 1 No 9 29 de febrero, 2012

ANOTACIÓN 2012 Serie 1 No 9: 29 de febrero, 2012

VIPERS: Especificaciones para la primera generación de prototipos, cont.

Nota: En esta anotación se suman tres nuevos ejemplos de la aplicación del modelo de investigación de operaciones denominada “programación lineal”:

El “Problema de la Asignación de Personal”

Fuente:  “An Illustrated Guide to Linear Programming” de Saul I. Gass

La programación lineal ha sido una herramienta importante para el campo de la clasificación de personal. El problema de la asignación de personal es central a esta investigación, y se puede describir y resolver con el modelo de programación lineal.

En nuestro problema modelo tenemos un centro de reclutamiento y asignación de reclutas para vacantes en tres escuelas de entrenamiento profesional. Llamemos a los tres reclutas Ángel, Ben, y Carlos. Cada uno ha tomado una serie de exámenes para determinar su aptitud para carreras profesionales como la de operador de radio, programador de ordenadores, y recepcionista. Sus puntuaciones aparecen en la siguiente tabla:

	Radio	Ordenador	Recepción
Ángel	5	4	7
Ben	6	7	3
Carlos	8	11	2

Cuanta más alta la puntuación, más alta la aptitud del recluta para el trabajo correspondiente. Carlos probablemente sería muy bueno como programador de ordenadores, pero un petardo como secretario. El centro de reclutamiento será otorgado una cuota de tres hombres – nuestro Ángel, Ben, y Carlos – y el centro debe asignarles las tres escuelas de entrenamiento disponibles: la de operador de radio, la de programador de computadoras, y la recepcionista. El problema con el cual se enfrenta el centro es como deberá hacerse las asignaciones de forma que se maximicen la utilidad de los nuevos reclutas al servicio del ejército.

Aquí nos ayudaría considerar el presente problema a la luz de nuestro conocimiento del problema del transporte. En esencia tenemos un número de orígenes denominados Ángel, Ben, y Carlos; cada uno de estos orígenes tiene 1 U de material – el recluta mismo – para ser enviado a algún destino: los destinos son la escuela de operadores de radio, de programadores de computación, y recepcionistas.  Al contrario del problema del transporte, deseamos maximizar el costo total del envío – en realidad, maximizar la suma de las calificaciones de los reclutas para las asignaciones. Organizando la data en una tabla parecida al problema del transporte tenemos:

	Radio		Ordenador		Recepción
Ángel	5	x11	4	x12	7	x13
Ben	6	x21	7	x22	3	x23
Carlos	8	x31	11	x32	2	x33

Las variables son interpretadas como la asignación del recluta a la escuela correspondiente; o sea, x₂₃ representa la asignación de Ben a la escuela de recepcionistas. Cada variable debe ser positiva o cero, y de hecho, cada variable está restringida a ser o un 1 o un 0. La solución óptima provista arriba indica que x₂₁ = 1, x₃₂ = 1 y x₁₃ = 1 y los demás x son ceros. Tomando nuestra delantera del problema del transporte, el modelo de la programación lineal del problema de la asignación de personal consiste en encontrar valores no negativos para las variables x_ij >= 0, que maximicen:

5x₁₁ +  4x₁₂ + 7x₁₃ + 6x₂₁ + 7x₂₂ + 3x₂₃ + 8x₃₁ + 11x₃₂ + 2x₃₃, sujeto a las siguientes restricciones:

x11	+ x12	+ x13							=	1
			x21	+ x22	+ x23				=	1
						x31	+ x32	+ x33	=	1
x11			+ x21			+ x31			=	1
	x12			+ x22			+ x32		=	1
		x13			+ x23			+ x33	=	1

La solución a este problema tiene el requisito explícito de que las variables tomen valores integrales – o 0 o 1. Oportunamente la estructura matemática del problema es la misma como la del problema del transporte y estamos garantizados una solución óptima en números enteros.

El “Problema de la Dieta”

Fuente:  “An Illustrated Guide to Linear Programming” de Saul I. Gass

El problema:

Consideremos un problema común y típico según el cual tenemos un número de alternativas de cereales para el desayuno, cada uno con un costo asociado y ciertos ingredientes nutricionales. Queremos formular un plan de desayuno que minimice el costo por una parte y por otra parte que garantice una mínima cantidad de ciertos nutrientes y calorías que se consideren esenciales. Expresemos los requisitos de acuerdo a la siguiente tabla de valores ficticios:

Nutrientes	Cantidad de cada nutriente en un gramo del Kokolocos (K)	Cantidad de cada nutriente en un gramo de Chocopicos (C)	Requisitos para cada nutriente
Nutriente 1	0.1 miligramos	0.25	1
Nutriente 2	1.00	0.25	5
Calorías	110.00	120.00	400
Costo	3.8 centavos de $	4.2 centavos de $

Para construir las restricciones del problema la cantidad total de cada nutriente en las columnas izquierdas tienen que >= a las cantidades mostradas en la columna derecha. Por lo tanto por cada nutriente tenemos una restricción. Para el Nutriente 1, K gramos Kokolocos contiene 0.10 mg; cada gramo de Chocopicos  contiene 0.25 de miligramos del Nutriente 2.  Para el Nutriente 1, una solución al problema debería tener:

0.10K + 0.25C >= 1

De igual forma, para el Nutriente 2:

1.00K + 0.25C >= 5

Y para las calorías:

110.00K +120.00C > = 400.

La cantidad de cada comida consumida debería ser cero o una cantidad positiva; por lo tanto K tiene que >= 0,  y C >= 0. Finalmente el costo total del menú del desayuno será:

3.8K + 4.2C

Juntando todo lo anterior, el problema del menú del desayuno consiste en encontrar los valores de K y C que minimicen el costo total de:

3.8K + 4.2C

Sujeto a:

0.10K	+ 0.25C	>=	1
1.00K	+ 0.25C	>=	5
110.00K	+120.00C	>=	400
K		>=	0
	C	>=	0

La solución mínima es cuando K = 4 4/9 g y C = 2 2/9 g., con un costo total de 26 2/9 centavos de dólar. Esta solución dará 1 mg del Nutriente 1 y 5 mg del Nutriente 2, las cuales son  exactamente los requisitos mínimos del problema, y dará 755 5/9 calorías, con un exceso de 355 5/9 y cinco calorías.

Este modelo simple puede fácilmente extenderse al problema de determinar una dieta de múltiples comidas a la vez que numerosos nutrientes (vitaminas, amino ácidos, etc.).

El “Problema del Análisis de Actividades”

Fuente:  “An Illustrated Guide to Linear Programming” de Saul I. Gass

El Problema:

Una forma moderna de ver las operaciones industriales en una organización es describir cada ítem producido en términos de los recursos requeridos para fabricar una unidad del mismo. La manufactura de una unidad – una unidad de actividad productiva – a representa el uso de algunos de los recursos disponibles de la empresa. El problema para el gerente de la producción consiste en determinar cuántos ítems de cada unidad debería producir – los niveles de actividad – que le permitan maximizar las ganancias de la empresa sujeto a las restricciones impuestas por los recursos a su disposición. Este planteamiento algo simplista – considerar las operaciones complejas en términos de actividades interrelacionadas básicas – es un método poderoso para resolver y para comprender una amplia gama de procesos industriales. Inherente a este enfoque es el modelo de análisis de actividades de programación lineal.

Vamos a suponer una fábrica de muebles que produce: mesas (m), sillas (s), libreros (l), y escritorios (e). Cada uno de esos muebles requiere una cantidad de material – madera de nogal (n), cuero (c), pegamento (p) y vidrio (v) – y de mano de obra (m), según la siguiente tabla:

	Madera de nogal (n) pies de tablero	Cuero (c) – pies cuadrados	Pegamento (p) - onzas	Vidrio (v) – pies cuadrados	Mano de obra (m) – horas
Mesa (m)	20	0	8	0	15
Silla (s)	5	4	3	0	10
Librero (l)	22	0	10	20	20
Escritorio (e)	15	20	15	0	25

El promedio de recursos disponibles semanales para nuestra fábrica ficticia se resume en la siguiente tabla:

20,000 pies-tablero	Madera de nogal
4,000 horas	Trabajo manual
2,000 onzas	Pegamento
3,000 pies cuadrados	Cuero
500 pies cuadrados	Vidrio

                La siguiente es una tabla de ganancias por cada uno de los productos manufacturados:

Producto	Ganancia
Mesa (m)	$80m
Silla (s)	$45s
Librero (l)	$55l
Escritorio (e)	$110e

                La pregunta es: ¿Dados los recursos disponibles cuantas unidades de cada producto debería fabricarse para maximizar las ganancias?

Matemáticamente la deseada máxima ganancia queda representada por la siguiente ecuación:

$45s + $80m + $110e + $55l

 Ahora solamente tenemos que encontrar los valores de s, m. e, y l que maximicen las ganancias, sujetos a las siguientes restricciones:

 5s  + 20m + 15e + 22l <= 20,000

10s + 15m +25e + 20l <= 4,000

   3s + 8m + 15e + 10l  <= 2,000

   4s            + 20e          <= 3,000

                               20l  <= 500

Si queremos otras especificaciones, como por ejemplo, un mínimo 50 sillas se tendría que añadir la siguiente ecuación:

 3s   >= 50

O no más de 30 escritorios se especificarían de la siguiente manera:

50e   <= 30

                Con las anteriores ecuaciones determinaríamos los parámetros necesarios para la aplicación de nuestro modelo de programación lineal.