Investigación de Operaciones

2010-11-24T15:23:00.000-08:00

La Investigación de Operaciones o Investigación Operativa, es una rama de las Matemáticas consistente en el uso de modelos matemáticos, estadística y algoritmos con objeto de realizar un proceso de toma de decisiones. Frecuentemente, trata del estudio de complejos sistemas reales, con la finalidad de mejorar (u optimizar) su funcionamiento. La investigación de operaciones permite el análisis de la toma de decisiones teniendo en cuenta la escasez de recursos, para determinar cómo se puede optimizar un objetivo definido, como la maximización de los beneficios o la minimización de costes.

Wikimedia Commons alberga contenido multimedia sobre Investigación de operaciones.

¿Qué es la Programación Lineal?

Un modelo de Programación Lineal (PL) considera que las variables de decisión tienen un comportamiento lineal, tanto en la función objetivo como restricciones del problema. En este sentido, la Programación Lineal es una de las herramientas más utilizadas en la Investigación Operativa debido a que por su naturaleza se facilitan los cálculos y en general permite una buena aproximación de la realidad.

Los Modelos Matemáticos se dividen básicamente en Modelos Determistas (MD) oModelos Estocásticos (ME). En el primer caso (MD) se considera que los parámetros asociados al modelo son conocidos con certeza absoluta, a diferencia de los Modelos Estocásticos, donde la totalidad o un subconjunto de los parámetros tienen una distribución de probabilidad asociada. Los cursos introductorios a la Investigación Operativa generalmente se enfocan sólo en Modelos Determistas.

Ejemplo prototipo.

Chícharos enlatados es uno de los productos más importantes de la compañía P & T. Los chícharos se preparan en tres enlatadoras (cercanas a Bellingham, Washington; a Eugene, Oregón y a Albert Lea, Minnesota) y después se mandan por camión a cuatro almacenes de distribución (en Sacramento, California; Salt Lake City, Utah; Rapid City, South Dakota y Alburquerque, New Mexico) en el oeste de Estados Unidos. Puesto que los costos de embarque constituyen un gasto importante, la gerencia ha iniciado un estudio para reducirlos lo más posible que se pueda. Se ha hecho una estimación de la producción de cada enlatadora para la próxima temporada y se ha asignado a cada almacén una cierta cantidad de la producción total de chícharos. En la siguiente tabla se proporciona esta información (en unidades de carga de camión), junto con el costo de transporte por camión cargado para cada combinación de enlatadora-almacén. Como se ve hay un total de 300 cargas de camión que se deben transportar. El problema es determinar el plan de asignación de estos embarques a las distintas combinaciones de enlatadora-almacén que minimice el costo total de transporte.

Costo de embarque ($) por carga

	Almacén
	1	2	3	4	Producción
1	464	513	654	867	75
Enlatadora 2	352	416	690	791	125
3	995	682	388	685	100
Asignación	80	65	70	85

Este, de hecho, es un problema de programación lineal del tipo de los problemas de transporte. Para formularlo, sea Z el costo total de transporte y sea x_ij (i = 1, 2, 3; j = 1, 2, 3, 4) el número de cargas de camión que se mandan de la enlatadora i al almacén j. Entonces el objetivo es seleccionar los valores de estas 12 variables de decisión (las x_ij) para:

Minimizar Z= 464x₁₁ + 513x₁₂ + 654x₁₃ + 867x₁₄ + 352x₂₁ + 416x₂₂ + 690x₂₃ + 791x₂₄

995x₃₁ + 682x₃₂ + 388x₃₃ + 685x₃₄

sujeta a las restricciones:

x₁₁

x₁₂

x₁₃

x₁₄

x₂₁

x₂₂

x₂₃

x₂₄

125

x₃₁

x₃₂

x₃₃

x₃₄

100

x₁₁

x₂₁

x₃₁

x₁₂

x₂₂

x₃₂

x₁₃

x₂₃

x₃₃

x₁₄

x₂₄

x₃₄

x_ij ³ 0 (i = 1, 2, 3; j = 1, 2, 3, 4)

La siguiente tabla muestra los coeficientes de las restricciones. Como se verá enseguida, lo que distingue a este problema como un problema de transporte es la estructura especial en el patrón de estos coeficientes, no su contexto.

Coeficiente de:
	x₁₁	x₁₂	x₁₃	x₁₄	x₂₁	x₂₂	x₂₃	x₂₄	x₃₁	x₃₂	x₃₃	x₃₄

	1	1	1	1
					1	1	1	1					Restricciones
									1	1	1	1	de enlatadora
A =	1				1				1
		1				1				1			Restricciones
			1				1				1		de almacén
				1				1				1

Entre paréntesis, la solución óptima para este problema es x₁₁ = 0, x₁₂ = 20, x₁₃ = 0, x₁₄ = 55,
x₂₁ = 80, x₂₂ = 45, x₂₃ = 0, x₂₄ = 0, x₃₁ = 0, x₃₂ = 0, x₃₃ = 70, x₃₄ = 30. Cuando se conozca la prueba de optimalidad se podrá verificar este resultado.

METODO DE LA ESQUINA NOROESTE.

Este método comienza asignando la cantidad máxima permisible para la oferta y la demanda a la variable X₁₁ (la que está en la esquina noroeste de la tabla).

La columna o renglón satisfechos se tacha indicando que las variables restantes en la columna o renglón tachado son igual a cero. Si la columna y el renglón se satisfacen simultaneamente, únicamente uno (cualquiera de los dos) debe tacharse. Esta condición garantiza localizar las variables básicas cero si es que existen. Después de ajustar las cantidades de oferta y demanda para todos los renglones y columnas no tachados, la cantidad máxima factible se asigna al primer elemento no tachado en la nueva columna o renglón. El procedimiento termina cuando exactamente un renglón o una columna se dejan sin tachar.

Ejemplo:

Una compañía tiene 3 almacenes con 15, 25 y 5 artículos disponibles respectivamente. Con estos productos disponibles desea satisfacer la demanda de 4 clientes que requieren 5, 15, 15 y 10 unidades respectivamente. Los costos asociados con el envío de mercancía del almacén al cliente por unidad se dan en la siguiente tabla.

	Clientes
Almacén	1	2	3	4
1	10	0	20	11
2	12	7	9	20
3	0	14	16	18

MÉTODO DE APROXIMACIÓN DE VOGEL.

Método de Aproximación de Vogel: para cada renglón y columna que queda bajo consideración, se calcula su diferencia, que se define como la diferencia aritmética entre el costo unitario más pequeño (c_ij) y el que le sigue, de los que quedan en ese renglón o columna. (Si se tiene un empate para el costo más pequeño de los restantes de un renglón o columna, entonces la diferencia es 0). En el renglón o columna que tiene la mayor diferencia se elige la variable que tiene el menor costo unitario que queda. (Los empates para la mayor de estas diferencias se pueden romper de manera arbitraria).

Para hacer más concreta esta descripción, se ilustrará el procedimiento general, utilizando el método de aproximación de Vogel

para resolver el ejemplo presentado anteriormente y que fue resuelto por la regla de la esquina noroeste:

Iniciamos el método calculando las primeras diferencias para cada renglón y columna. De las diferencias que obtuvimos nos fijamos en la mayor (¿Por qué?), que resulta ser para la tercera columna. En esa columna encontramos el costo unitario (c_ij) menor y en esa celda realizamos la primera asignación:

Recursos

DIF.

2 0

Demanda

2 0

DIF.

3 ¹

Nota: Marcaremos a la mayor de las diferencias seleccionada encerrándola en un círculo y escribiéndole como superíndice el número que le corresponda en la secuencia de selección.

Observemos en la figura anterior que únicamente eliminamos el segundo renglón ya que la tercera columna nos servirá después para hacer la asignación de una variable básica degenerada. Continuando con la aplicación del método, tenemos que calcular nuevamente las diferencias de las columnas ya que hemos eliminado un renglón y ésto puede ocasionar que las diferencias aritméticas entre el costo unitario más pequeño y el que le sigue ya no sean las mismas:

Recursos

DIF.

2 0

3 0

Demanda

4 1

2 0

DIF.

3 ¹

4 ²

Como siguiente paso deberíamos calcular las nuevas diferencias de columnas, pero ya que solamente queda un renglón dentro de las posibilidades (ésto no significa que solamente un renglón quede bajo consideración ya que podemos observar que ninguna de las cuatro columnas (destinos) ha sido eliminada y todas quedan todavía bajo consideración), no es posible encontrar la diferencia aritmética entre el costo menor y el que le sigue, por lo tanto vamos tomando una a una las celdas que quedan comenzando con la de menor costo unitario hasta que todas hayan sido asignadas.

					Recursos	DIF.
	3	1	0	1	5 2 1 0	1
			2		2 0	0
		3			3 0	1
Demanda	3 0	4 1 0	2 0	1 0	10 10
DIF.	1	1	3 ¹	2
	1	4 ²	2	1

La solución inicial básica factible es x₁₁=3, x₁₂=1, x₁₃=0 (variable básica degenerada), x₁₄=1, x₂₃=2 y x₃₂=3 y el costo total de transporte asociado a esta primera “Política de Transporte” factible es de:

x₁₁

c₁₁

x₁₂

c₁₂

x₁₃

c₁₃

x₁₄

c₁₄

x₂₃

c₂₃

x₃₂

c₃₂

Costo =

(3)

(7)

(6)

(4)

(3)

= 35 unidades

Es necesario aclarar que ésta puede o no ser la solución final del problema, es necesario aplicar a esta primera solución factible la prueba de optimalidad ya que puede existir una mejor “política de transporte” que minimice todavía más el costo total.

PROGRAMACIÓN DINÁMICA

La programación dinámica es un enfoque general para la solución de problemas en los que es necesario tomar decisiones en etapas sucesivas. Las decisiones tomadas en una etapa condicionan la evolución futura del sistema, afectando a las situaciones en las que el sistema se encontrará en el futuro (denominadas estados), y a las decisiones que se plantearán en el futuro.

Conviene resaltar que a diferencia de la programación lineal, el modelado de problemas de programación dinámica no sigue una forma estándar. Así, para cada problema será necesario especificar cada uno de los componentes que caracterizan un problema de programación dinámica.

El procedimiento general de resolución de estas situaciones se divide en el análisis recursivo de cada una de las etapas del problema, en orden inverso, es decir comenzando por la última y pasando en cada iteración a la etapa antecesora. El análisis de la primera etapa finaliza con la obtención del óptimo del problema.

Investigacion de Operaciones

Investigación de Operaciones

Costo de embarque ($) por carga

Producción

A =