30 de abril de 2015 resoluciÓn de modelos de programaciÓn entera entera/clases... ·...

Programación Entera José Luis Quintero 1

RESOLUCIÓN DE MODELOS DE PROGRAMACIÓN

ENTERAMÉTODOS HEURÍSTICOS

Y RELAJACIONESPostgrado de Investigación de Operaciones

Facultad de Ingeniería

Universidad Central de Venezuela

30 de Abril de 2015


1. Técnica del redondeo

2. Método heurístico sencillo

3. Relajaciones en PLE

Puntos a tratar


Redondear la solución delproblema de PL a la soluciónentera más cercana puedeproducir soluciones óptimas, noóptimas o no factibles

Técnica de redondeo


Ejemplo 1. Técnica de redondeo





Puntos a tratar


• Resolver el problema lineal para hallar (si existe)una solución óptima lineal x.

CASO 1. Si la solución es entera, FIN.

CASO 2. Si el problema lineal es infactible, FIN.

• Para cada componente no entera, generarsoluciones al azar como sigue:

• Seleccionar como solución aproximada la mejor delas soluciones factibles generadas.

ix

ii

i

1 con probabilidad xx =

0 con probabilidad 1-x

Una heurística para Programación Lineal Entera 0-1





Puntos a tratar


Notación a usar:

F(Q) Conjunto de soluciones factibles

del problema Q

Función objetivo de Q

Valor que toma en x

J Conjunto de variables enteras

QZ

QZ (x)QZ

Relajaciones en Programación Lineal Entera


DEFINICIÓN. Sea P un problema demaximización de PLE, se dice que PR es unarelajación de P si:

a.

b. PR P

F(P) F(PR)

Z (x) Z (x) x F(P)

⊆≥ ∀ ∈

Ejemplos:Relajación LinealRelajación LagrangeanaRelajación por reemplazoDescomposición Lagrangeana



Relajación Lagrangeana

tjP: max c x s.a. Ax b, Bx d, x 0, x entero si j J≤ ≤ ≥ ∈

0λ ≥λ: vector de la dimensión de b. real fijo

t tjPR: max c x (b Ax) s.a. Bx d, x 0, x entero si j J+ λ − ≤ ≥ ∈


{ }

PR

1 2 3

1 1 2 3

2 1 2 3

1 2 3

1 2 3 1 2

max 2x 3x 5x

(8 2x x 5x )

(9 3x x 6x ) s.a.

x 2x 3x 4

x , x , x 0,1 , , 0 fijos

+ + +λ − − − +λ − − −

+ + ≤

∈ λ λ ≥

Ejemplo 5. Relajación Lagrangeana

{ }

P

1 2 3

1 2 3

1 2 3

1 2 3

1 2 3

max 2x 3x 5x s.a.

x 2x 3x 4

2x x 5x 8

3x x 6x 9

x ,x ,x 0,1

+ ++ + ≤

+ + ≤+ + ≤

∈

PR es un problema tipo mochila (knapsack problem)


Relajación Lagrangeana

TEOREMA. Sean P un problema de PLE,

un problema de relajación lagrangeana ytal que:

a. es óptimo deb.c.

Entonces es óptimo de P.

, x∗ ∗λ

x∗ P ∗λx F(P)∗ ∈

t(b Ax ) 0∗ ∗λ − =

x∗

Pλ


{ }

P

1 2

1 2

1 2

max 2x x s.a.

x x 1

x ,x 0,1

++ ≤

∈

{ }PR1

1 2 1 2

1 2

max 2x x 2(1 x x ) s.a.

x ,x 0,1

+ + − −

∈


{ }PR2

1 2 1 2

1 2

max 2x x 3(1 x x ) s.a.

x ,x 0,1

+ + − −

∈factibles:

(0,0)

(0,1)

(1,0) óptimo

óptimos: (0,0) , (1,0)

óptimo: (0,0)


{ }

P

1 2

1 2

1 2

max 2x x s.a.

x x 3 /2

x ,x 0,1

++ ≤

∈{ }

PR

1 2 1 2

1 2

max 2x x 2(3 /2 x x ) s.a.

x ,x 0,1

+ + − −

∈


factibles:

(0,0)

(0,1)

(1,0)

(1,1) óptimo

óptimos: (0,0) , (1,0)


Relajación por reemplazo (Surrogate relaxation)


0µ ≥μ: vector de la dimensión de b. real fijo

t tjPR : max c x s.a. (Ax b) 0, Bx d, x 0, x entero si j Jµ − ≤ ≤ ≥ ∈


{ }

PR

1 2

1 2

t

1 21 2

1 2

1 2

max 2x 3x s.a.

x 2x 4

2x x 31 06x x 8

4x 2x 51 0

x ,x 0,1

++ ≤

+ − ≤ ⇒ − ≤ − −

∈

Ejemplo 8. Relajación por reemplazo

{ }

P

1 2

1 2

1 2

1 2

1 2

max 2x 3x s.a.

x 2x 4

2x x 3

4x 2x 5

x ,x 0,1

++ ≤

+ ≤− ≤

∈


Descomposición Lagrangeana


t t

j k

P̂ : max c x c y s.a. Ax b, By d, x y, 1

x 0, x entero si j J, y entero si k J , reales fijos

α + β ≤ ≤ = α + β =≥ ∈ ∈ α β

P y son problemas equivalentes P̂


Descomposición Lagrangeana

t t t

j k

PR: max c x c y (y x) s.a. Ax b, By d, 1

x 0, x entero si j J, y entero si k J , reales fijos

α + β + λ − ≤ ≤ α + β =≥ ∈ ∈ α β

t t t t

j k

PR : max c x x max (1 )c y y s.a.

Ax b, By d,

x 0, x entero si j J, y entero si k J

real fijo

α − λ + − α + λ≤ ≤

≥ ∈ ∈

α



TEOREMA. Sean P un problema de PLE (casomax) y PR una relajación:

a. Si entonces .b. Si y acotado, entonces existe

una solución óptima para PR y.

c. Suponga . Si es óptimoen PR y entonces es óptimoen P.

F(PR) = ∅ F(P) = ∅F(PR) ≠ ∅

v(PR) v(P)≥

Z(PR) Z(P)≡ x∗

x F(P)∗ ∈ x∗


Pensamiento de hoy

“Todo el mundo desea saber, peropocos están dispuestos a pagar elprecio”.

Juvenal

30 de abril de 2015 resoluciÓn de modelos de programaciÓn entera entera/clases... ·...

Documents