Investigacion Operacionales

INVESTIGACIÓN DE OPERACIONES II Angélica Gutiérrez Limón

OBJETIVO:Aplicará a situaciones reales los principales modelos y técnicas determinanticas y probabilísticas de la Investigación de Operaciones para la toma de decisiones óptima. angelicagtz@gmail.com

SESION

TEMA

1 UNIDAD UNO

Programación dinámica

2 1.1 Características de los problemas de programación dinámica: etapas, estados, fórmula recursiva, programación en avance y en retroceso

3 1.2 Algunos ejemplos de modelos de P.D. Al estudiar cada aplicación ponga especial atención a los tres elementos básicos de un modelo de programación dinámica.

1. Definición de las etapas

2. Definición de las alternativas en cada etapa

3. Definición de los estados para cada etapa

En general, de los tres elementos, la definición de estado suele ser la más sutil. Al investigar cada aplicación (diferentes ejemplos de modelos de P.D.), encontrará útil tener en cuenta las preguntas siguientes:

1. ¿Qué relaciones vinculan entre sí a las etapas?

2. ¿Qué información se necesita para tomar decisiones factibles en la etapa actual sin volver a examinar las decisiones tomadas en las etapas anteriores?

Algunos ejemplos de modelos de P.D. son:

• Problema de la mochila/ equipo de vuelo/ carga del contenedor

• Modelo del tamaño de la fuerza de trabajo

• Modelo de reposición de equipo

FUENTE: http://www.itescam.edu.mx/principal/sylabus/rptSylabus.php?tipo=PDF&id_asignatura=447&clave_asignatura=INB-0412&carrera=IIND0405001

4 1.2 Algunos ejemplos de modelos de P.D.

Al estudiar cada aplicación ponga especial atención a los tres elementos básicos de un modelo de programación dinámica.

4. Definición de las etapas

5. Definición de las alternativas en cada etapa

6. Definición de los estados para cada etapa

En general, de los tres elementos, la definición de estado suele ser la más sutil. Al investigar cada aplicación (diferentes ejemplos de modelos de P.D.), encontrará útil tener en cuenta las preguntas siguientes:

3. ¿Qué relaciones vinculan entre sí a las etapas?

4. ¿Qué información se necesita para tomar decisiones factibles en la etapa actual sin volver a examinar las decisiones tomadas en las etapas anteriores?

Algunos ejemplos de modelos de P.D. son:

• Problema de la mochila/ equipo de vuelo/ carga del contenedor

• Modelo del tamaño de la fuerza de trabajo

• Modelo de reposición de equipo

FUENTE: www.itescam.edu.mx/principal/sylabus/fpdb/recursos/r26320.DOC

5 1.3 Programación dinámica determinística.

6 1.4 Programación dinámica probabilística.

7 1.4 Programación dinámica probabilística.

PROGRAMACION DINAMICA PROBABILISTICA

La programación dinámica probabilística difiere de la programación dinámica determinística en que el estado de la etapa siguiente no queda completamente determinado por el estado y la decisión de la política en el estado actual. En lugar de ello existe una distribución de probabilidad para lo que será el estado siguiente. Sin embargo, esta distribución de probabilidad todavía esta completamente determinada por el estado y la decisión de la política del estado actual. En la siguiente figura se describe diagramáticamente la estructura básica que resulta para la programación dinámica probabilística, en donde N denota el número de estados posibles en la etapa n+1. Para ver el gráfico seleccione la opción "Descargar" del menú superior

Cuando se desarrolla de esta forma para incluir todos los estados y decisiones posibles en todas las etapas, a veces recibe el nombre de árbol de decisión. Si el árbol de decisión no es demasiado grande, proporciona una manera útil de resumir las diversas posibilidades que pueden ocurrir.

FUENTE: http://www.monografias.com/trabajos23/planeacion-requerimientos/planeacion-requerimientos.shtml#programac

8 1.5 Problema de dimensionalidad en P. D.

Fuente: Taha, Investigacion de Operaciones, Mexico 2006

9 1.6 Uso de programas de computación

PROGRAMAS DE COMPUTACIÓN PARA RESOLVER

PROBLEMAS DE PROGRAMACION LINEAL

En esta pagina, se presenta la documentación relativa a los programas de computación que serán utilizados en el curso para resolver problemas de programación Lineal, adicionalmente, el alumno puede bajar los programas de computación con fines académicos, con miras a resolver los problemas propuestos del curso y no deben ser utilizados con fines comerciales ya que los mismos están protegidos por las leyes de derechos de autor.

A.-) PROGRAMAS DE COMPUTACIÓN

Adicional al programa SOLVER, incluido en EXCEL-2000 de MIcrosoft (cuya explicación didáctica del funcionamiento del programa Solver (445 kb), se incluye en este documento que puede ser bajado por Usted), se incorporan otros programas que operan bajo sistema WIndows 98/ME/2000/XP, debiendo disponer de una computadora actualizada con procesador Pentium II y superiores, memoria mínima de 256 kb y capacidad de disco de 50 MB y los cuales pueden ser bajados a continuación:.

A.1) El programa WinQSB (3.9 Mb), cuya propiedad intelectual es del Dr. Yih-Long Chang y es aplicable a todos los problemas de Investigación de Operaciones. Para conocer sus usos y aplicaciones, se incorpora el MANUAL DE USO del WINQSB.

A.2) El programa PrgLin, cuya propiedad es de la Universidad de Lisboa (Portugal), el cual se aplica para soluciones gráficas de problemas de dos dimensiones.

A.3) El programa InvOp (361 kb), desarrollado por la Universidad del Cuyo en Argentina, se aplica para la solución de problemas relacionados con transporte y redes.

A.3) El programa Lingo, propiedad de Lindo Systems Inc (USA), que dado su gran tamaño (18.9 Mb), se recomienda que Usted lo recupere directamente de la pagina Web del propietario de dicha tecnologia http:// www.lindo.com

Posteriormente se irán incorporando otros programas de computación específicos para cada caso y cuyo uso será descrito mediante ejemplos en la Clase.

B.-) USO DEL PROGRAMA SOLVER DE EXCEL (Microsoft)

Para conocer la aplicación del método SOLVER de EXCEL (Microsoft), se utilizará un ejemplo práctico:

Max Z= 10 X1 + 8 X2

Sujeto a:

30X1 +20X2 <= 120

2X1 + 2X2 <= 9

4X1 + 6X2 <= 24

X1,X2 >=0

La única dificultad que tenemos es el de modelar el programa dentro del Excel, y eso, es muy fácil. Por supuesto, hay infinidad de maneras de hacerlo, aquí propongo una.

Se activa Excel y en una hoja...

• Se ubican las celdas que se corresponderán con el valor de las variables de decisión; en éste caso, las celdas B6 y C6, se les da un formato para diferenciarlas de las demás, aquí azul oscuro (ver captura abajo). Se ubica también, las celdas que contendrán los coeficientes de las variables de decisión, B4 y C4, y se llenan con sus respectivos valores, 10 y 8. Aunque éste último paso, se podría omitir y dejar los coeficientes definidos en la celda de la función objetivo, así es mejor para los análisis de sensibilidad y para que la hoja quede portable para otro programa.

• Se ubica la celda que se corresponderá con la función objetivo (celda objetivo), la B3. En ella se escribe la función que sea, en éste caso, será el coeficiente de X1 (en B4) por el valor actual de X1 (en B6) mas el coeficiente de X2 (en C4) por el valor actual de X2 (en C6) O sea: =$B$4*$B$6+$C$6*$C$4

• Coeficientes para la primera restricción: los podemos escribir en la misma columna de las variables de decisión; en las celdas B7 y C7, con los valores 30 y 20, seguido del sentido de la desigualdad (<=) y de su correspondiente RHS: 120. A la derecha ubicaremos el valor actual de consumo de la restricción, ella se escribirá en función de las variables de decisión y de los coeficientes de la restricción. Esta celda, la utilizará Solver como la real restricción, cuando le digamos que el valor de ésta celda no pueda sobrepasar la de su correspondiente RHS. De nuevo será el valor del coeficiente por el de la variable:=B7*$B$6+C7*$C$6. Notese que ahora B7 y C7 no tienen el signo $. Pues es que luego que se haya escrito ésta celda, se podrá arrastrar hacia abajo para que Excel escriba la fórmula por nosotros (la pereza!), pero tome los valores relativos a los coeficientes que le corresponda a los mismos valores de las variables de decisión. Se repite los pasos anteriores para las otras restricciones, pero ahora la fórmula será: =B8*$B$6+C8*$C$6 y =B9*$B$6+C9*$C$6.

El resto del formato es para darle una presentación más bonita a la hoja. Ahora a resoverlo! Al hacer click en Herramientas , Solver se tendrá una pantalla como la siguiente. Lo primero que hay que hacer es especificar la celda objetivo y el propósito: maximizar. Se escribe B3 (o $B3 ó B$3 ó $B$3 como sea, da igual), en el recuadro "cambiando las celdas", se hace un click en la flechita roja, para poder barrer las celdas B6 y C6; lo mismo da si se escriben directamente los nombres.

Y ahora para las restricciones: se hace click en

...