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

Ricardo Mayen

on 5 November 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Programación Entera

Características de la programación entera
Ventajas de uso
En algunos casos requerimos soluciones que se compongan de valores enteros para alguna de las variables. La solución por medio de la programación lineal no causa un gran conflicto, pues los resultados tienen que ser truncados y esto genera una solución no factible. Por esto se hace necesario el desarrollo de métodos para hallar soluciones exactas a este tipo de problemas. Los métodos de enteros hayan la solución de una manera más rapida y eficientemente.
Planteamiento de modelo
Cinco artículos deben ser cargados en un navío. El peso Wi, y el volumen vi, junto con el valor ri para el articulo i que se tabulan a continuación.




El peso y el volumen máximo permitidos para
la carga son 112 toneladas y 109 yardas
respectivamente.

Referencias
Programación entera
¿Qué es la programación lineal?
La Programación Lineal es un procedimiento o algoritmo matemático mediante el cual se resuelve un problema indeterminado, formulado a través de ecuaciones lineales, optimizando la función objetivo, también lineal.
Historia
1826-Joseph Fourier anticipa la programación lineal. Carl Friedrich Gauss
resuelve ecuaciones lineales por eliminación "gaussiana".

1902- Gyula Farkas concibe un método para resolver sistemas de desigualdades.

1947-George Dantzig pública el algoritmo simplex y
John von Neumann desarrolló la teoría de la dualidad.
Se sabe que Leonid Kantoróvich también formuló la teoría en forma independiente.

1984-Narendra Karmarkar introduce el método del punto interior para resolver
problemas de programación lineal.
Programación entera
Historia
1958- Gomory expone su Método de planos de Cortantes, en ese mimos año Bellman hace uso de la Programación Dinámica.
1960- Land Doig proponen el primer Algoritmo de Ramificación y Acotamiento.
1965- Balas desarrolla un algoritmo de enumeriacion implícito para problemas lineales de Kendall.
Métodos más importantes
Método Gráfico


Método de planos de corte
-Fracción de Gomory
-Mixto de Gomory
-Puro de Gomory


Método de Ramificación y acotamiento

Método enumeración implício


Características de modelos
Modelo entero puro





Modelo entero mixto






Modelo binario
- Los coeficientes de las restricciones son enteros.
-Las todas las variables son enteras (holgura y exceso).
-La función objetivo pueden no tener coeficientes enteros
-Este modelo tiene variables binarias y continuas.
-Las variables binarias aparecen en la función objetivo con un cargo.
-Tienen un conjunto de restricciones que limitan las variables continuas y un conjunto de restricciones que combinan variables continuas y binarias.

La única característica de este modelo es que sus variables de decisión son binarias (1 éxito , 0 fracaso ).
Modelo de programación lineal
El palneamiento es un modelo binario y se resolvera por el modelo de ramificación.
xi =
{
1 se lleva articulo i
0 no se lleva
Max z= 400x1+700x2+600x3+500x4+40x5
s.a
5x1+8x2+3x3+2x4+7x5 <= 12
x1+8x2+6x3+5x4+4x5 <= 10
xi >= 0 xi={1,0}
Solución
Iteración 5
Iteración 2
Iteración 3
Iteración 1
Iteración 4
Interpretación
Solo se tranportara el articulo x1 y x3.
Estos artículos suman 8 toneladas, ocupan 7 yardas de espacio y la ganancia es de 1000 dolraes.
19-rrhh [Imagen]. (2009). Recuperado de http://www.csigsac.com/ joomla16/index.php/12-novedades/19-rrhh-iso-9001

resoluciongrafica[imagen].(2001). Recuperado de http:// www.investigaciondeo peraciones.net/ resolucion_grafica.html

capitulo1[imagen].(2005). Recuperado de http://www.virtual.unal.edu.co/cursos/sedes/manizales/4060014/html/Capitulo%20VI/ramificacion.htm

unidad2ioi[imagen].(2009). Recuperado de http://www.geocities.ws/mdmoli/archivos/ioi2/unidad2ioi.html

tranport[imagen].(2010). Recuperado de http://ru.123rf.com/photo_11895901_types-of-transport-of-transporting-are-loads.html

cc30[imagen].(2007). Recuperado de http://www.postgradoeinvestigacion.uadec.mx/CienciaCierta/CC30/3.html




Full transcript