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

Modelo de Programación Entera

No description
by

Ramón Flores

on 5 November 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Modelo de Programación Entera

Modelos de Programación Entera
Introducción
Solución
En muchos modelos prácticos, las variables de decisión alcanzan un sentido sólo si tienen valores enteros.
Muchas veces la solución del programa lineal truncado esta lejos de ser el óptimo entero, por lo que se hace necesario usar algún algoritmo para hallar esta solución de forma exacta.
Los modelos enteros
se dividen en:

- Enteros Puros
- Enteros Mixtos
- Binarios
Algunos de los modelos más importantes:

- Tipo Mochila
- Asignación de capital
- Cobertura de conjuntos
- Asignación de horarios
- Agente Viajero
- Cargo fijo
- Sí, entonces
- Restricciones 'o bien'
Ventajas
- Como la mayoría de los problemas son de tipo entero, tiene grandes ventajas el saber cómo plantear y resolver problemas de éste tipo.

- Se puede obtener una solución entera más óptima que truncando soluciones usando Programación Lineal
Planteamiento
Me voy cambiar de casa y deseo llevar las cosas más valiosas, éstos son los detalles:
¿Qué objetos debo elegir para maximizar el valor?
Las variables son los objetos a llevar, los cuales están limitados por la capacidad del camión de carga.
xi : 1 se lleva el objeto i
0 no se lleva el objeto i

Max z = 800x1 + 300x2 + 700x3 + 500x4 + 1000x5 + 600x6

s.a.

400x1 + 200x2 + 500x3 + 350x4 + 300x5 + 400x6 <= 1100

xi >= 0, xi E {0,1}
Usaremos le método de ramificación y acotamiento para modelos binarios.
Primero obtenemos el beneficio por artículo dividiendo el valor entre el peso:
Ahora, los ordenamos del mayor al menor:
Creamos la raíz del árbol, asignando el valor de 1 al objeto más valioso, restamos su peso al límite (b = 1100) y sumamos su valor a z
.
Continuamos con las ramificaciones:
Solución:
x6 = 1
x5 = 1
x1 = 1
x2, x3, x4 = 0

Z = 2400
Interpretación
x1 = Cama
x2 = Radio
x3 = Sofá
x4 = Librero
x5 = Televisor
x6 = Escritorio
Referencias
Hillier, F. & Lieberman, G. (2010). Introducción a la investigación de Operaciones (9na Edición). McGraw Hill Educación: México.
Imagen R. Gomory (2013). Recuperada el 04 de Noviembre de 2013 de http://www.nndb.com/people/449/000159969/
Imagen E. Dijsktra(2002). Recuperada el 04 de Noviembre de 2013 de http://en.wikipedia.org/wiki/Edsger_W._Dijkstra
Imagen E. Balas (2013). Recuperada el 04 de Noviembre de 2013 de http://public.tepper.cmu.edu/facultydirectory/FacultyDirectoryProfile.aspx?id=39
Programación Lineal (2013). http://es.wikipedia.org/wiki/Programaci%C3%B3n_lineal#Programaci.C3.B3n_entera
Imagen Televisor (2013). Recuperada el 03 de Noviembre de 2013 de http://www.xataka.com/hogar-digital/haier-lanza-un-televisor-totalmente-inalambrico
Imagen estéreo (2013). Recuperada el 03 de Noviembre de 2013 de http://www.mxonda.es/dvd/18-conjunto-estereo-de-cine-en-casa-mx-dhs8545-8413366454790.html
Imagen cama (2013). Recuperada el 03 de Noviembre de 2013 de http://www.estiloambientacion.com.ar/tienda/cama-brandon-2-plazas.html
Imagen sofá (2010). Recuperada el 03 de Noviembre de 2013 de http://www.massada-bneianusim.org/v2/2010/10/06/quien-paga/
Imagen camión (2013). Recuperada el 03 de Noviembre de 2013 de http://fletes-mudanzas.vivanuncios.com.mx/traslados+alvaro-obregon/transporte-flete-mudanza-camion-3-5-tons-loca)
Imagen Librero (2013). Recuperada el 03 de Noviembre de 2013 de http://www.gebesa.com/portfolio_ibusiness/librero-alto-abierto-millenium-2/
Imagen escritorio (2013). Recuperada el 04 de Noviembre de 2013 de http://www.portobellostreet.es/mueble/19467/Mesa-de-Escritorio-Vintage-7-Cajones-Bromo
Imagen idea (2012). Recuperada el 04 de Noviembre de 2013 de http://www.problemasdematematica.com/blog/2010/07/soluciones-problemas-con-fracciones-1/
Elaborado por:
Flores Rodríguez Ramón
Olea Vallejo José Franco

Historia
1958 - Gomory publica su método de cortes.
1959 - Dijkstra da a conocer su algoritmo de ruta más corta.
1960 - Land y Doig proponen el primer algoritmo de Ramificación y Acotamiento para modelos enteros.
1965 - Balas desarrolla el algoritmo que lleva su nombre, para modelos binarios.
Ralph E. Gomory
Edsger W. Dijkstra
Egon Balas
Full transcript