Programaci´on lineal (+ extensiones). Objetivos y panorama del curso.

Departamento de Matem´aticas. ITAM. 2008.

Programaci´ on lineal (+ extensiones). Objetivos y panorama del c

Introducci´on

Programaci´on lineal http://allman.rhon.itam.mx/∼jmorales La programaci´on lineal es una de las aportaciones de la matem´atica con alto impacto en las aplicaciones. El problema por resolver es el siguiente: minimizar sujeta a

f (x) = c T x Ax = b,

(1)

x ≥ 0,

Programaci´ on lineal (+ extensiones). Objetivos y panorama del c

en donde

Programaci´ on lineal (+ extensiones). Objetivos y panorama del c

en donde x ≥ 0 indica xi ≥ 0,

i = 1, 2, . . . , n

Programaci´ on lineal (+ extensiones). Objetivos y panorama del c

en donde x ≥ 0 indica xi ≥ 0,

i = 1, 2, . . . , n

c es el vector de costos

Programaci´ on lineal (+ extensiones). Objetivos y panorama del c

en donde x ≥ 0 indica xi ≥ 0,

i = 1, 2, . . . , n

c es el vector de costos A es una matriz de m × n con m < n

Programaci´ on lineal (+ extensiones). Objetivos y panorama del c

en donde x ≥ 0 indica xi ≥ 0,

i = 1, 2, . . . , n

c es el vector de costos A es una matriz de m × n con m < n b es un vector m-dimensional.

Programaci´ on lineal (+ extensiones). Objetivos y panorama del c

en donde x ≥ 0 indica xi ≥ 0,

i = 1, 2, . . . , n

c es el vector de costos A es una matriz de m × n con m < n b es un vector m-dimensional. El vector x es llamado el vector de variables de decisi´on

Programaci´ on lineal (+ extensiones). Objetivos y panorama del c

en donde x ≥ 0 indica xi ≥ 0,

i = 1, 2, . . . , n

c es el vector de costos A es una matriz de m × n con m < n b es un vector m-dimensional. El vector x es llamado el vector de variables de decisi´on la funci´on f es conocida como la funci´on objetivo

Programaci´ on lineal (+ extensiones). Objetivos y panorama del c

en donde x ≥ 0 indica xi ≥ 0,

i = 1, 2, . . . , n

c es el vector de costos A es una matriz de m × n con m < n b es un vector m-dimensional. El vector x es llamado el vector de variables de decisi´on la funci´on f es conocida como la funci´on objetivo El conjunto determinado por Ax = b, x ≥ 0 es llamado la zona factible.

Programaci´ on lineal (+ extensiones). Objetivos y panorama del c

Objetivos

En este curso nos concentraremos en los siguientes aspectos de la programaci´on lineal:

Programaci´ on lineal (+ extensiones). Objetivos y panorama del c

Objetivos

En este curso nos concentraremos en los siguientes aspectos de la programaci´on lineal: Estudiar diversos problemas que se pueden formular como (1)

Programaci´ on lineal (+ extensiones). Objetivos y panorama del c

Objetivos

En este curso nos concentraremos en los siguientes aspectos de la programaci´on lineal: Estudiar diversos problemas que se pueden formular como (1) Estudiar las condiciones te´oricas que aseguran la existencia de una soluci´on de (1)

Programaci´ on lineal (+ extensiones). Objetivos y panorama del c

Objetivos

En este curso nos concentraremos en los siguientes aspectos de la programaci´on lineal: Estudiar diversos problemas que se pueden formular como (1) Estudiar las condiciones te´oricas que aseguran la existencia de una soluci´on de (1) Utilizar las condiciones de optimalidad para dise˜ nar algoritmos pr´acticos que resuelvan eficientemente (1)

Programaci´ on lineal (+ extensiones). Objetivos y panorama del c

Contenido del curso 1

Introducci´on. Motivaci´on.

Programaci´ on lineal (+ extensiones). Objetivos y panorama del c

Contenido del curso 1

Introducci´on. Motivaci´on.

2

Propiedades de un PL. Soluciones b´asicas. El teorema fundamental de la PL.

Programaci´ on lineal (+ extensiones). Objetivos y panorama del c

Contenido del curso 1

Introducci´on. Motivaci´on.

2

Propiedades de un PL. Soluciones b´asicas. El teorema fundamental de la PL.

3

Dualidad. Teorema de dualidad. Condiciones de optimalidad de KKT.

Programaci´ on lineal (+ extensiones). Objetivos y panorama del c

Contenido del curso 1

Introducci´on. Motivaci´on.

2

Propiedades de un PL. Soluciones b´asicas. El teorema fundamental de la PL.

3

Dualidad. Teorema de dualidad. Condiciones de optimalidad de KKT.

4

M´etodo simplex I. Teor´ıa.

Programaci´ on lineal (+ extensiones). Objetivos y panorama del c

Contenido del curso 1

Introducci´on. Motivaci´on.

2

Propiedades de un PL. Soluciones b´asicas. El teorema fundamental de la PL.

3

Dualidad. Teorema de dualidad. Condiciones de optimalidad de KKT.

4

M´etodo simplex I. Teor´ıa.

5

M´etodo simplex II. Aspectos num´ericos.

Programaci´ on lineal (+ extensiones). Objetivos y panorama del c

Contenido del curso 1

Introducci´on. Motivaci´on.

2

Propiedades de un PL. Soluciones b´asicas. El teorema fundamental de la PL.

3

Dualidad. Teorema de dualidad. Condiciones de optimalidad de KKT.

4

M´etodo simplex I. Teor´ıa.

5

M´etodo simplex II. Aspectos num´ericos.

6

M´etodos de puntos interiores I. Aspectos b´asicos. Condiciones de KKT modificadas. La trayectoria central.

Programaci´ on lineal (+ extensiones). Objetivos y panorama del c

Contenido del curso 1

Introducci´on. Motivaci´on.

2

Propiedades de un PL. Soluciones b´asicas. El teorema fundamental de la PL.

3

Dualidad. Teorema de dualidad. Condiciones de optimalidad de KKT.

4

M´etodo simplex I. Teor´ıa.

5

M´etodo simplex II. Aspectos num´ericos.

6

M´etodos de puntos interiores I. Aspectos b´asicos. Condiciones de KKT modificadas. La trayectoria central.

7

M´etodos de puntos interiores II. Aspectos num´ericos.

Programaci´ on lineal (+ extensiones). Objetivos y panorama del c

Contenido del curso 1

Introducci´on. Motivaci´on.

2

Propiedades de un PL. Soluciones b´asicas. El teorema fundamental de la PL.

3

Dualidad. Teorema de dualidad. Condiciones de optimalidad de KKT.

4

M´etodo simplex I. Teor´ıa.

5

M´etodo simplex II. Aspectos num´ericos.

6

M´etodos de puntos interiores I. Aspectos b´asicos. Condiciones de KKT modificadas. La trayectoria central.

7

M´etodos de puntos interiores II. Aspectos num´ericos.

8

Extensiones. Complementariedad lineal. Programaci´on cuadr´atica convexa.

Programaci´ on lineal (+ extensiones). Objetivos y panorama del c

Condiciones de optimalidad (KKT). Forma est´andar

c − AT λ − s = 0 Ax − b = 0 xi si

= 0,

i = 1, 2, . . . , n

(x, s) ≥ 0 en donde λ es el vector de multiplicadores de Lagrange asociados con las igualdades Ax − b = 0 s es el vector de multiplicadores de Lagrange asociados con las desigualdades x ≥ 0.

Programaci´ on lineal (+ extensiones). Objetivos y panorama del c

Condiciones de optimalidad (KKT) . minimizar

f (x) = c T x

sujeta a

Ax − b ≥ 0,

(2)

c − AT π = 0 (Ax − b)i πi

= 0,

i = 1, 2, . . . , m

Ax − b ≥ 0 π ≥ 0

en donde π es el vector de multiplicadores de Lagrange asociados con las desigualdades Ax − b ≥ 0

Programaci´ on lineal (+ extensiones). Objetivos y panorama del c

Ejemplo de un PL

minimizar sujeta a

− 2x1 − x2 x1 + (8/3)x2 ≤ 4 x1 + x 2 ≤ 2 2x1

≤ 3 x

≥ 0,

Programaci´ on lineal (+ extensiones). Objetivos y panorama del c

Forma est´andar de un PL

minimizar sujeta a

− 2x1 − x2 x1 + (8/3)x2 + x3 = 4 x1 + x 2 + x 4 = 2 2x1

+ x5 = 3 x

≥ 0,

Programaci´ on lineal (+ extensiones). Objetivos y panorama del c

Puntos extremos de un PL

2

x =0

x =0 5

1

x =0

4

x =0

1

3

Ω

1

x2 = 0

2

Programaci´ on lineal (+ extensiones). Objetivos y panorama del c

Zona factible de un PL

2

x +x =2

2x = 3

2

1

1

x =0

1

x + (8/3)x = 4

1

1

2

Ω

1

x2 = 0

2

Programaci´ on lineal (+ extensiones). Objetivos y panorama del c

Zona factible e isol´ıneas de un PL x2 2.5

5

2.2 6.7 5

2 4.5

f = 2x1 + x2 1.5

5

2.2 4.5

1

Ω

x*

0.5 5 2.2

4.5

0

0

0.5

1

1.5

2

2.5

x1

Programaci´ on lineal (+ extensiones). Objetivos y panorama del c