PDF de programación - Métodos numéricos en LSIP

Bibliografía El problema Clasificación Condiciones suficientes para los métodos de discretización Discretización mediante planos de corte Método simplex para LSIP

Métodos numéricos en LSIP

Valentín Jornet

Seminario en Homenaje al Prof. Marco A. López

20 de febrero de 2010

Valentín Jornet

Métodos numéricos en LSIP

Bibliografía El problema Clasificación Condiciones suficientes para los métodos de discretización Discretización mediante planos de corte Método simplex para LSIP

Outline

1 Bibliografía

2 El problema

3 Clasificación

4 Condiciones suficientes para los métodos de discretización

5 Discretización mediante planos de corte

Cortes factibles: Método de Kelley
Método de Elzinga-Moore

6 Método simplex para LSIP

Valentín Jornet

Métodos numéricos en LSIP

Bibliografía El problema Clasificación Condiciones suficientes para los métodos de discretización Discretización mediante planos de corte Método simplex para LSIP

Referencias para Métodos en Semi-Infinita

Valentín Jornet

Métodos numéricos en LSIP

Bibliografía El problema Clasificación Condiciones suficientes para los métodos de discretización Discretización mediante planos de corte Método simplex para LSIP

Referencias para Métodos en Semi-Infinita

Toda la información necesaria para esta presentación se ha
obtenido de los capítulos 11 y 12 del texto Semi-Infinite Linear
Programming, publicado por JOHN WILEY & SONS en 1998 y
cuyos autores son Goberna, Miguel A.; L ópez, Marco A.

Valentín Jornet

Métodos numéricos en LSIP

Bibliografía El problema Clasificación Condiciones suficientes para los métodos de discretización Discretización mediante planos de corte Método simplex para LSIP

Referencias para Métodos en Semi-Infinita

Toda la información necesaria para esta presentación se ha
obtenido de los capítulos 11 y 12 del texto Semi-Infinite Linear
Programming, publicado por JOHN WILEY & SONS en 1998 y
cuyos autores son Goberna, Miguel A.; L ópez, Marco A.
Aunque los siguientes trabajos también pueden considerarse
aportaciones a los métodos numéricos en semi-infinita:

Valentín Jornet

Métodos numéricos en LSIP

Bibliografía El problema Clasificación Condiciones suficientes para los métodos de discretización Discretización mediante planos de corte Método simplex para LSIP

Referencias para Métodos en Semi-Infinita

Toda la información necesaria para esta presentación se ha
obtenido de los capítulos 11 y 12 del texto Semi-Infinite Linear
Programming, publicado por JOHN WILEY & SONS en 1998 y
cuyos autores son Goberna, Miguel A.; L ópez, Marco A.
Aunque los siguientes trabajos también pueden considerarse
aportaciones a los métodos numéricos en semi-infinita:

Anderson,Edward J.; Goberna, Miguel A.; L ópez, Marco A.
Simplex-like trajectories on quasi-polyhedral sets. Math. Oper. Res.
26 (2001)

Valentín Jornet

Métodos numéricos en LSIP

Bibliografía El problema Clasificación Condiciones suficientes para los métodos de discretización Discretización mediante planos de corte Método simplex para LSIP

Referencias para Métodos en Semi-Infinita

Toda la información necesaria para esta presentación se ha
obtenido de los capítulos 11 y 12 del texto Semi-Infinite Linear
Programming, publicado por JOHN WILEY & SONS en 1998 y
cuyos autores son Goberna, Miguel A.; L ópez, Marco A.
Aunque los siguientes trabajos también pueden considerarse
aportaciones a los métodos numéricos en semi-infinita:

Anderson,Edward J.; Goberna, Miguel A.; L ópez, Marco A.
Simplex-like trajectories on quasi-polyhedral sets. Math. Oper. Res.
26 (2001)
Auslender, A.; Goberna, M.A. ; L ópez, M.A.
Penalty and smoothing methods for convex semi-infinite
programming. Math. Oper. Res. (2009)

Valentín Jornet

Métodos numéricos en LSIP

Bibliografía El problema Clasificación Condiciones suficientes para los métodos de discretización Discretización mediante planos de corte Método simplex para LSIP

Presentación del problema

Aunque a estas alturas el problema de LSIP es un viejo conocido, lo
presentamos de nuevo y hacemos mención de sus elementos más
importantes:

Valentín Jornet

Métodos numéricos en LSIP

Bibliografía El problema Clasificación Condiciones suficientes para los métodos de discretización Discretización mediante planos de corte Método simplex para LSIP

Presentación del problema

Aunque a estas alturas el problema de LSIP es un viejo conocido, lo
presentamos de nuevo y hacemos mención de sus elementos más
importantes:

Problemas primal y dual

(P) mín c0x
tx ≥ bt
a0

s.a

, t ∈ T

(D) máx P
s.a P

t∈T

λtbt
λtat = c

t∈T
λ ∈ R(T)

+

Valentín Jornet

Métodos numéricos en LSIP

Bibliografía El problema Clasificación Condiciones suficientes para los métodos de discretización Discretización mediante planos de corte Método simplex para LSIP

Presentación del problema

Aunque a estas alturas el problema de LSIP es un viejo conocido, lo
presentamos de nuevo y hacemos mención de sus elementos más
importantes:

Problemas primal y dual

(P) mín c0x
tx ≥ bt
a0

s.a

, t ∈ T

(D) máx P
s.a P

t∈T

λtbt
λtat = c

t∈T
λ ∈ R(T)

+

Denotamos por F el conjunto factible del primal y por Λ el
conjunto factible del dual.

Valentín Jornet

Métodos numéricos en LSIP

Bibliografía El problema Clasificación Condiciones suficientes para los métodos de discretización Discretización mediante planos de corte Método simplex para LSIP

Presentación del problema

Aunque a estas alturas el problema de LSIP es un viejo conocido, lo
presentamos de nuevo y hacemos mención de sus elementos más
importantes:

(D) máx P
s.a P

t∈T

λtbt
λtat = c

t∈T
λ ∈ R(T)

+

Problemas primal y dual

(P) mín c0x
tx ≥ bt
a0

s.a

, t ∈ T

Denotamos por F el conjunto factible del primal y por Λ el
conjunto factible del dual.
Los conjuntos Fα = {x ∈ F | c0x ≤ α} son los conjuntos de nivel
del problema primal.

Valentín Jornet

Métodos numéricos en LSIP

Bibliografía El problema Clasificación Condiciones suficientes para los métodos de discretización Discretización mediante planos de corte Método simplex para LSIP

Presentación del problema

Aunque a estas alturas el problema de LSIP es un viejo conocido, lo
presentamos de nuevo y hacemos mención de sus elementos más
importantes:

(D) máx P
s.a P

t∈T

λtbt
λtat = c

t∈T
λ ∈ R(T)

+

Problemas primal y dual

(P) mín c0x
tx ≥ bt
a0

s.a

, t ∈ T

Denotamos por F el conjunto factible del primal y por Λ el
conjunto factible del dual.
Los conjuntos Fα = {x ∈ F | c0x ≤ α} son los conjuntos de nivel
del problema primal.
Se representa por F∗ el conjunto óptimo del primal y por Λ∗ el
conjunto óptimo del dual.

Valentín Jornet

Métodos numéricos en LSIP

Bibliografía El problema Clasificación Condiciones suficientes para los métodos de discretización Discretización mediante planos de corte Método simplex para LSIP

Clasificación

Según el texto Semi-Infinite Linear Programming, los métodos
numéricos para la resolución de un problema de LSIP pueden
clasificarse en:

Valentín Jornet

Métodos numéricos en LSIP

Bibliografía El problema Clasificación Condiciones suficientes para los métodos de discretización Discretización mediante planos de corte Método simplex para LSIP

Clasificación

Según el texto Semi-Infinite Linear Programming, los métodos
numéricos para la resolución de un problema de LSIP pueden
clasificarse en:

Métodos de discretización:

Mediante parrillas
Mediante planos de corte

Valentín Jornet

Métodos numéricos en LSIP

Bibliografía El problema Clasificación Condiciones suficientes para los métodos de discretización Discretización mediante planos de corte Método simplex para LSIP

Clasificación

Según el texto Semi-Infinite Linear Programming, los métodos
numéricos para la resolución de un problema de LSIP pueden
clasificarse en:

Métodos de discretización:

Mediante parrillas
Mediante planos de corte

Métodos de reducción local

Valentín Jornet

Métodos numéricos en LSIP

Bibliografía El problema Clasificación Condiciones suficientes para los métodos de discretización Discretización mediante planos de corte Método simplex para LSIP

Clasificación

Según el texto Semi-Infinite Linear Programming, los métodos
numéricos para la resolución de un problema de LSIP pueden
clasificarse en:

Métodos de discretización:

Mediante parrillas
Mediante planos de corte

Métodos de reducción local
Métodos de intercambio

Valentín Jornet

Métodos numéricos en LSIP

Bibliografía El problema Clasificación Condiciones suficientes para los métodos de discretización Discretización mediante planos de corte Método simplex para LSIP

Clasificación

Según el texto Semi-Infinite Linear Programming, los métodos
numéricos para la resolución de un problema de LSIP pueden
clasificarse en:

Métodos de discretización:

Mediante parrillas
Mediante planos de corte

Métodos de reducción local
Métodos de intercambio
Métodos del tipo simplex

Valentín Jornet

Métodos numéricos en LSIP

Bibliografía El problema Clasificación Condiciones suficientes para los métodos de discretización Discretización mediante planos de corte Método simplex para LSIP

Clasificación

Según el texto Semi-Infinite Linear Programming, los métodos
numéricos para la resolución de un problema de LSIP pueden
clasificarse en:

Métodos de discretización:

Mediante parrillas
Mediante planos de corte

Métodos de reducción local
Métodos de intercambio
Métodos del tipo simplex
Métodos de descenso

Valentín Jornet

Métodos numéricos en LSIP

Bibliografía El problema Clasificación Condiciones suficientes para los métodos de discretización Discretización mediante planos de corte Método simplex para LSIP

Conjuntos de nivel

Todos los métodos de discretización necesitan de la existencia de un conjunto S ⊂ T
tal que sus conjuntos de nivel sean no vacíos y acotados.
Un tal S existe si, y sólo si, F∗ es no vacío