Scribd
Cargar
31 vistas13 páginas

Métodos de Programación Entera en P.E.

Este documento describe métodos para resolver problemas de programación entera. Explica que las variables pueden ser binarias u otras variables enteras. Luego describe dos métodos principales: el método de ramificación y acotamiento (Branch and Bound), que divide el problema en subproblemas hasta encontrar la solución óptima; y el método de los planos de corte (Cutting plane), que itera entre obtener soluciones no enteras y agregar restricciones. Finalmente, presenta un ejemplo del algoritmo de Land-Doig aplicando el método de ramificación y acotamiento.

Cargado por

PEDRO ANTONIO NAVARRETE SOSA
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PPT, PDF, TXT o lee en línea desde Scribd
31 vistas13 páginas

Métodos de Programación Entera en P.E.

Este documento describe métodos para resolver problemas de programación entera. Explica que las variables pueden ser binarias u otras variables enteras. Luego describe dos métodos principales: el método de ramificación y acotamiento (Branch and Bound), que divide el problema en subproblemas hasta encontrar la solución óptima; y el método de los planos de corte (Cutting plane), que itera entre obtener soluciones no enteras y agregar restricciones. Finalmente, presenta un ejemplo del algoritmo de Land-Doig aplicando el método de ramificación y acotamiento.

Cargado por

PEDRO ANTONIO NAVARRETE SOSA
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PPT, PDF, TXT o lee en línea desde Scribd

Introducción

Un problema de Programación Entera (P.E.) es un


programa lineal con la característica adicional de
que algunas o todas las variables deben ser números
enteros.
A estas variables se les denomina variables enteras.
Se llama variable binaria a un tipo de variable que
sólo puede tomar los valores 0 ó 1.
Una variable binaria es muy útil para el
planteamiento de problemas complejos.
Resolución
Para resolver problemas con variables enteras no
basta redondear la solución obtenida con el método
Simplex. Posibles consecuencias:
Soluciones no factibles.
Proceso muy complejo al tratar de evitar caer en este
error.
Existen dos grandes métodos:
El método de ramificación y acotamiento (Branch and
Bound).
El método de los planos de corte (Cutting plane).
Método de ramificación y
acotamiento
Se va redondeando poco a poco las soluciones no
enteras obtenidas para las variables enteras, acotando
de manera sistemática las posibilidades que se van
presentando.
Existen varios algoritmos que se basan en este
método, que difieren únicamente en el procedimiento
de ramificación.
Algoritmo de Land-Doig: ejemplo
Max Z 8x1 + 5x2 Subproblema 1
s.a : x1 + x2  6 Z = 41,25
x1 = 3,75
9x1 + 5x2  45 x2 = 2,25
x1, x2  0 ; x1, x2 enteros
x1³ 4 x1£ 3

Subproblema 2 Subproblema 3
Z = 41 ¿Vale la pena seguir Z = 39 = L.I.1
x1 = 4,0 ramificando? x1 = 3
x2 = 1,8 x2 = 3

x2 ³ 2 x2£ 1

Subproblema 4 Subproblema 5
Z = 40,555 ¿Vale la pena seguir
No factible x1 = 4,444 ramificando?
x2 = 1,000

x1³ 5 x1£ 4

Subproblema 6 Subproblema 7
Z = 40 = L.I.2 Z = 37 < L.I.2
X1 = 5 X1 = 4
X2 = 0 X2 = 1
 Min Z= 0.3x+0.52y Z=1.06
 s.a x =0.5 ; y = 1.75
 1. 2.5x+y ≥ 3 x≥0 x≥1
 2. X+2y ≥ 4 x= 0 x=1 NF
 F y=3 y= 1.5
 Z=1.56 z= 1.08

 y≥1 y≥ 2
 F y= 1 y=2 NF
 x=2 x = 0.4
 Z= 1.12 Z = 1.16


 Área factible
Min Z= 0.3x+0.52y
S.a
2.5x+y ≥ 3
X+2y ≥ 4
X>0,y>0
Método de enumeración completa
El método consisten en obtener todos los puntos
posibles de las combinaciones de valores enteros para
las variables de decisión y evaluar Z para cada uno
ellos, siendo la solución optima aquel punto que
optimice la Z y sea factible.
Este método esta limitado solo a dos variables, es
impráctico para mas de tres variables por la cantidad
de puntos a evaluar.

También podría gustarte