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

Método de Plano de Corte de Gomory

Programación Entera Pura
by

Juan David Lara

on 17 November 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Método de Plano de Corte de Gomory

Método de Plano de Corte de Gomory
1° Paso
En primer lugar, hemos de resolver el problema de manera “
tradicional
”, es decir sin tener en cuenta que algunas o todas las variables del problema deben ser enteras. Para ello en cada restricción debemos agregar nuestras variables de Holgura

2° Paso
Después de agregar las variables necesarias y cambiar el
signo de nuestra función objetivo
, para trabajar nuestro modelo independiente de cada restricción y de acuerdo a las diferentes formas, cuando ya este listo el modelo lo llevaremos a nuestro Tablero Simplex, y procederemos a realizar su solución, de manera similar a los Problemas de Programación Lineal.

3° Paso
Resolvemos el Problema Primal, si la solución es entera, corresponde a la óptima para el problema de Programación Lineal Entera y entonces Terminaremos, de existir variables con valores reales realizaremos el siguiente Paso 4.

4° Paso
Seleccionamos variables con valores decimales y escogemos aquel que tenga la mayor parte fraccionaria tomando las ecuaciones completas.

Programación Entera Pura (PEP)
Investigación de Operaciones II
Universidad Distrital Francisco José de Caldas

4° Paso
Fin del Algoritmo si la Solución Relajada nos entrega resultados Enteros.
Solución Relajada Entera
Solución Relajada Real
Teniendo el Tablero Final Simplex de la Forma:
Si observamos que una Variable toma un Valor de la Forma (d/e) tendremos un resultado fraccional, ya escogida nuestra variable, seleccionamos todos los elementos de la fila.
5° Paso
Ahora que seleccionamos la Variable formamos una Ecuación con la Fila que deseamos trabajar, tendremos


6° Paso
7° Paso
8° Paso
Ahora dependiendo de los Valores que acompañan nuestras variables Separaremos Nuestra Ecuación entre las Variables con Coeficiente Entero y las Variables con Coeficiente Real. Suponiendo que A, C , D son Coeficientes Fraccionales y B es Entero además con el supuesto de que los demás coeficientes son Cero, tendríamos:



Luego de Obtener nuestra Nueva Restricción la Agregamos a Nuestro Tablero Simplex, adicionándole la Variable de Holgura necesaria y Solucionamos el Problema con esta Nueva Restricción.




Si Obtenemos Variables con Valores Enteros entonces terminamos nuestro Método de Gomory, de obtener nuevamente valores Fraccionales repetimos nuestro Método de Gomory desde el
Paso 4
, y generamos una Nueva Restricción, que cortara nuevamente nuestra región factible reduciendo la cantidad de posibles soluciones factibles.





Programación Entera Pura (PEP)
Investigación de Operaciones II
Grupo 81 – 2013-3
Grupo Interno 1


Juan David Lara Rodríguez - 20102020050
Andrés Velandia Rodríguez - 20102020102
William Alfredo Linares G. - 20102020052
Full transcript