miércoles, 24 de noviembre de 2010

Investigación de Operaciones


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.




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 xij (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 xij) para:

            Minimizar Z= 464x11 + 513x12 + 654x13 + 867x14 + 352x21 + 416x22 + 690x23 + 791x24
995x31 + 682x32 + 388x33 + 685x34

sujeta a las restricciones:

x11
+
x12
+
x13
+
x14
















=
75








x21
+
x22
+
x23
+
x24








=
125
















x31
+
x32
+
x33
+
x34
=
100
x11






+
x21






+
x31






=
80


x12






+
x22






+
x32




=
65




x13






+
x23






+
x33


=
70






x14






+
x24






+
x34
=
85

xij ³ 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:

x11
x12
x13
x14
x21
x22
x23
x24
x31
x32
x33
x34















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 x11 = 0, x12 = 20, x13 = 0, x14 = 55,
x21 = 80, x22 = 45, x23 = 0, x24 = 0, x31 = 0, x32 = 0, x33 = 70, x34 = 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 X11 (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 (cij) 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 (cij) menor y en esa celda realizamos la primera asignación:






Recursos
DIF.

3


6


4


7





5
1

2          


4


3


2


3




            2

2  0
0

5


4


8





3
1

Demanda

3

4

2  0

1
        10
  10

DIF.
1
1
        3  1
2





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.

3


6


4


7





5
1


2          


4


3


2


3




            2

2  0
0


5


4


8



            3


3  0
1


Demanda

3

4  1

2  0

1
        10
  10

DIF.
1
1
        3  1
2


1
        4   2
        2
1



            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  1
2


1
        4   2
        2
1




            La solución inicial básica factible es x11=3, x12=1, x13=0 (variable básica degenerada), x14=1, x23=2 y x32=3 y el costo total de transporte asociado a esta primera “Política de Transporte” factible es de:


x11
c11

x12
c12

x13
c13

x14
c14

x23
c23

x32
c32

Costo =
3
(3)
+
1
(7)
+
0
(6)
+
1
(4)
+
2
(3)
+
3
(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.