Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Programación Entera

No description
by

Gerardo Garcia

on 24 November 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Programación Entera

Investigación de Operaciones
.

Programación Entera
Cuando en nuestro entorno tenemos un problema al que se pretende optimizar ya sea obteniendo el mayor beneficio o generando el menor gaste de recursos y sabemos que se puede solucionar haciendo uso de la investigación de operaciones. Pero además que la solución debe reportarse en números enteros o unidades completas, por ejemplo número de empleados a contratar, número de máquinas a reemplazar, número de unidades a producir, etc.

Podemos hacer uso de la Programación entera y aprovechar los métodos de solución que esta presenta para así obtener la solución óptima deseada.



.
Métodos mas importantes
Historia

Es difícil precisar el inicio de la investigación de operaciones. Muchos de los primeros iniciadores llevaron a cabo trabajos que ahora consideraríamos como investigación de operaciones.
Pero fue en el tiempo de la segunda guerra mundial cuando los gobiernos en conflicto comenzaron a encomendar a científicos tareas de optimización y asignación de de recursos, el primer invento que se derivo fue el radar con el fin de localizar aviones enemigos, después se amplio este problema a la puntería contra aviones y lanzamiento de misiles. Bellman con su Programación Dinámica, Kuhn y Tucker realizaban estudios con la Progamación No-Lineal, Gómory con la Programación Entera, Fulkerson y Ford generan las redes de optimización , y trabajos acdeerca Simulación llevados a cabo por Markowitz.

El Análisis de Decisiones de Raiffa, mientras mientras Howard realiza estudios de procesos Markovianos. La generalización de Investigación de Operaciones, ha sido tratada por Churchman, Ackoff y Arnoff.
Al término de la Guerra el éxito de la Investigación de Operaciones genera gran interés fuera de lo militar y llama la atención de los norteamericanos hasta finales de los 50's.
Los investigadores antes mencionados, hicieron que la investigacion de operaciones fuera usada en la industria, los negocios y el gobierno. Y desde entonces esta disciplina se ha desarrollado con rapidez, pudiendo identificar aspectos importantes que permitieron su expansión a otros campos
Tipos de Modelos
Los tipos de modelos son los tres siguientes:



2.- Modelo Entero Puro.
Son modelos similares a los de programación entera. El valor de sus resultado pertenecen a los números enteros.

Forma General :
Max or Min =A1X1+A2X2+A3X3+A4X4+A5X5+..........+AnXn

Sujeto a las restricciones:
A1X1+A2X2+A3X3+A4X4+A5X5+..........+AnXn >= (<=)(=) Bi

No negatividad : Xi >= 0 y ENTERO, Ai es coeficiente.
1.- Modelo Binario.

En estos modelos lineales , las variables sólo toman valores 0 y 1 , son usadas para uso probabilístico. Donde 0 se rechaza la opción y 1 se acepta la opción

Forma General :

Max or Min = A1Y1+A2Y2+A3Y3+A4Y4+A5Y5+..........+AnYn
Sujeto a las restricciones:
dy1+y2+y3+y4+..........+yn >= (<=)(=) Bi

No negatividad : yi >= 0 v 1, Ai es coeficiente.
3.- Modelo Mixto.

Este modelo es una combinación de los dos modelos anteriores , integra las variables puras y las mixtas
Ejemplo de modelo Binario.

Max or Min = A1X1+A2X2+A3X3+A4X4+A5X5+..........+AnXn+A1Y1+A2Y2+A3Y3+A4Y4+A5Y5+..........+AnYn

Sujeto a la restricción :
A1X1+A2X2+A3X3+A4X4+A5X5+..........+AnXn >= (<=)(=) Bi
y1+y2+y3+y4+..........+yn >= (<=)(=) Bi

No negatividad :
Xi >= 0 y ENTERO yi >= 0 v 1 . 0=se rechaza la decisión. 1= se acepta la decisión. Ai es coeficiente.

Los tipos de restricciones usadas en la programación entera son :

1) Excluyentes : Solo sirve para elegir una alternativa de varias posibles

2) Pre-requisito : Cuando necesitas realizar una acción antes de proceder con la siguiente

3) Incluyente : Dicha restricción se da para cuando realizas una acción "A" entonces debes hacer la acción "B"

4) Costo Fijo : Cuando se nombra un costo fijo , es sinónimo de uso de variable mixta
Tipos de Restricciones.
Ejemplo de modelo binario
.
Planos de Corte
Método Fraccional de Gomory, Método Mixto de Gomory, Método puro de Gomory: Estos métodos fueron los primeros en usarse y resuelven modelos de tamaño medio, ya que cada iteración se agrega una variable y una restricción para excluir solución.
Este método hace cortes de poca magnitud a la región factible inconvexa, obligando a la solución lineal a ser entera.
Estos métodos trabajan con modelos enteros y mixtos.


Método Gráfico
Enumeración Implícita.
Ramificación y acotamiento
Este método gráfica las restricciones de nuestro modelo matemático y la función objetivo en el plano cartesiano, se obtiene la región factible o región inconvexa en donde cada punto de la región es una solución para para el modelo de optimización , este método funciona mejor para modelos de dos variables de decisión.
Los puntos que cumplen con las restricciones del modelo se llaman puntos de celosía, la solución esta conformada de puntos de celosía y este conjunto sera enumerado.
Con este método se puede resolver cualquier tipo de modelo.
Interpretación
Los resultados arrojados fueron:
x1=0
x2=1
x3=1
Lo cual se interpreta como que en el pueblo x2 y x3 se construirá una gasolinera.
A continuación se enumeran los métodos mas importantes para la programación entera:
Planteamiento
ESTACIONES DE BOMBEROS
Hay 3 municipios en Tlaxcala. El gobernador debe determinar en que lugar construir estaciones de bomberos. Se desea construir una mínima cantidad de estaciones de bomberos para asegurar que por lo menos una estación este dentro de 15 minutos (tiempo de viaje) de cada ciudad. En la siguiente tabla se muestran los tiempos requeridos (minutos) para viajar ente las ciudades
.-Investigación de Operaciones, Programación Entera. (WEB 2013) http://www.investigaciondeoperaciones.net/programacion_entera.html
.-Clases de Investigación de Operaciones, La Programación Entera.(WEB,2013) http://invope2arl.blogspot.mx/2012/04/programacion-entera_09.html
.-Historia de la Investigación de Operaciones, IPN. (WEB,2013) http://www.angelfire.com/ak5/invo1_escom/2_Historia.pdf
.-Breve Historia de la Investigación de Operaciones (WEB, 2013) http://html.rincondelvago.com/investigacion-de-operaciones_2.html

Ejemplo:
Ejemplo:
Este método podemos aplicar a los modelos de tipo mixto, binario, tipo mochila y del tipo agente viajero.
Este método usa la lógica de "divide y verás" partiendo de soluciones relajadas donde se ramifica y acota las soluciones y el progreso de la aplicación del método. Al hacer cortes de mayor magnitud a la región factible se llega más rápido a la solución factible.
Aquí usamos el método de BALAS para solucionar solamente modelos binarios, este modelo en algunas ocasiones tendrá a una aproximación muy cercana a la solución óptima. su procedimiento es muy lógico y no se tiene una solución inicial.
Bibliografía
Integrantes:

Jiménez Rosas Jazmín Yaritza
Garcia Moreno Gerardo
Ejemplo:
Full transcript