Pontificia Universidad Católica Escuela de Ingeniería Departamento de Ingeniería Industrial y de Sistemas

Clase 18 • Programaci´ on Lineal ICS 1102 • Optimizaci´on Profesor : Claudio Seebach 4 de octubre de 2005

Apuntes de Clases • Optimizaci´on • Claudio Seebach

Programaci´ on Lineal • 17

Introducci´ on a Programaci´ on Lineal • Todo problema de Programaci´on Lineal puede expresarse mediante el siguiente formato est´andar: s.a

min Z = c1x1 + c2x2 + ... + cnxn a11x1 + ... + a1nxn ≤ b1 .. am1x1 + ... + amnxn ≤ bm

• En notaci´on matricial: min !c · !x s.a A!x ≤ !b

Apuntes de Clases • Optimizaci´on • Claudio Seebach

Programaci´ on Lineal • 18

Terminolog´ıa de Programaci´ on Lineal

• Soluci´on ´optima

• M´ultiples ´optimos, o soluci´on no ´optima • Valor ´optimo o m´as favorable de Z • Problema no acotado • Problema infactible

Apuntes de Clases • Optimizaci´on • Claudio Seebach

Programaci´ on Lineal • 19

Casos Especiales en LP 1. Problema infactible 2. Regi´on no acotada, pero objetivo acotado 3. Regi´on no acotada y objetivo no acotado 4. M´ultiples soluciones

Apuntes de Clases • Optimizaci´ on • Claudio Seebach

Programaci´ on Lineal • 20

Caso Especial 1

Apuntes de Clases • Optimizaci´ on • Claudio Seebach

Programaci´ on Lineal • 21

Caso Especial 2

Apuntes de Clases • Optimizaci´ on • Claudio Seebach

Programaci´ on Lineal • 22

Caso Especial 3

Apuntes de Clases • Optimizaci´ on • Claudio Seebach

Programaci´ on Lineal • 23

Caso Especial 4

Apuntes de Clases • Optimizaci´ on • Claudio Seebach

Programaci´ on Lineal • 24

Resolviendo un Problema de LP • M´etodo de soluci´on basado en v´ertices • Ejemplo: max Z = 3x1 + 2x2

• Paso 1: Encontrar todos los v´ertices factibles del problema

• Paso 2: Encontrar el valor objetivo para cada v´ertice Ejemplo: CP3: (x1 = 3, x2 = 4) y Z(CP3) = 3 × 3 + 2 × 4 = 17

• Paso 3: Determinar el v´ertice con mayor Z Apuntes de Clases • Optimizaci´on • Claudio Seebach

Programaci´ on Lineal • 25

Resolviendo un Problema de LP Ejemplo: • Objetivo: max Z = 3x1 + 5x2 + x3 • Restricciones:

x1 2x2 + 4x3 3x1 + 2x2 + x3 x3

≤ ≤ ≤ ≥

4 12 18 2

• No-negatividad: x1 ≥ 0, x2 ≥ 0

Apuntes de Clases • Optimizaci´on • Claudio Seebach

Programaci´ on Lineal • 26

Resolviendo un Problema de LP • Usemos el Solver de Excel:

Apuntes de Clases • Optimizaci´ on • Claudio Seebach

Programaci´ on Lineal • 27

Resolviendo un Problema de LP

• ⇒ Soluci´on ´optima: x1 = 4, x2 = 2, x3 = 2 y Z ∗ = 24

• Un problema con 20 variables de decisi´on y 40 restricciones tiene o sea m´as de 30 millones de posibles v´ertices factibles !!!

Apuntes de Clases • Optimizaci´on • Claudio Seebach

Programaci´ on Lineal • 28

!40" 20

,

KKT y Programaci´ on Lineal • Los problemas de Programaci´on Lineal son abordables via KKT

• Problema convexo ⇒ cualquier soluci´on que cumpla con las condiciones de KKT ser´a un ´optimo global al problema • No necesariamente la soluci´on ´optima ser´a u´nica, pues las funciones objetivo lineales no son estrictamente convexas • Consideremos el problema P ) min cx s.a. Ax ≤ b

• Las condiciones de KKT de L(x, µ) = cx + µ(Ax − b) son: ∂L ∂x ∂L ∂µ ∂L µ ∂µ µ

= c + µA = 0 = Ax − b ≤ 0 = µ(Ax − b) = 0

≥ 0

Apuntes de Clases • Optimizaci´ on • Claudio Seebach

Programaci´ on Lineal • 29

KKT y Programaci´ on Lineal • Incorporando restricciones de signo en todas las variables xi ≥ 0, las condiciones KKT son: ∂L ∂x ∂L x ∂x ∂L ∂µ ∂L µ ∂µ µ x

Apuntes de Clases • Optimizaci´on • Claudio Seebach

= c + µA ≥ 0 = x(c + µA) = 0 = Ax − b ≤ 0 = µ(Ax − b) = 0

≥ 0 ≥ 0

Programaci´ on Lineal • 30

Ejemplo KKT y Programaci´ on Lineal Ejemplo 1 Una f´ abrica produce dos tipos de planchas de aluminio pintado y requiere determinar la cantidad a producir de cada tipo. Producir una plancha del tipo 1 requiere 7 m2 de aluminio bruto, 0, 3 lts de pintura y 15 min de trabajo. El costo por plancha (en aluminio y pintura) para el fabricante es de $400 y el precio unitario de venta es de $1200. Producir una plancha del tipo 2 requiere 14 m2 de aluminio bruto, 0, 3 lts de pintura y 5 min de trabajo. El costo por plancha es $900 y el precio unitario de venta es de $1500. El fabricante maneja un stock diario m´ aximo de 630 m2 de aluminio bruto y 15 lts de pintura. Trabajar´a solo y dispone de 10 hrs cada d´ıa. El fabricante no dispone de un trabajo alternativo para las horas no utilizadas en fabricar planchas de aluminio ¿Cu´ anto es lo ´optimo a producir de modo de maximizar la utilidad?

Apuntes de Clases • Optimizaci´on • Claudio Seebach

Programaci´ on Lineal • 31

Ejemplo KKT y Programaci´ on Lineal • Definamos dos variables x1 y x2 que representan el n´umero de planchas pintadas diarias a producir de cada tipo: P ) max 800x1 + 600x2 s.a. 15x1 + 5x2 ≤ 600 (minutos disponibles) 7x1 + 14x2 ≤ 630 (m2 de aluminio) 0, 3x1 + 0, 3x2 ≤ 15 (lts de pintura) x 1 , x2 ≥ 0 • El objetivo es identificar la combinaci´on de x1 y x2 que, satisfaciendo las restricciones del modelo, maximiza las utilidades para la empresa. • El problema tiene soluci´on ´optima ya que en un problema de programaci´on lineal basta determinar una soluci´on factible: – Producir 20 planchas tipo 1 y 20 del tipo 2. Esto consume s´olo 6 hrs 40 min, 420 m2 de aluminio y 12 lts de pintura de las disponibles, lo que alcanza. Su utilidad ser´ıa de $28.000 diarios, pero claramente no ser´ıa ´optimo (sobran insumos de todo tipo!). Apuntes de Clases • Optimizaci´ on • Claudio Seebach

Programaci´on Lineal • 32

Tipo 2

Soluci´ on Gr´ afica

min disponibles m2 de aluminio lts de pintura

x*2

(35,15) x*1

Tipo 1

• La soluci´on ´optima corresponde a la combinaci´on de x1 y x2 en que la primera y tercera restricci´on est´an activas, es decir, se utiliza toda la pintura y las horas disponibles. • Esta soluci´on corresponde a x∗1 = 35 y x∗2 = 15, con una utilidad de $37.000. Apuntes de Clases • Optimizaci´on • Claudio Seebach

Programaci´ on Lineal • 33

Ejemplo KKT y Programaci´ on Lineal • Escribamos este problema como un problema de KKT:

L = −800x1 − 600x2 + µ1(15x1 + 5x2 − 600) +µ2(7x1 + 14x2 − 630) + µ3(0, 3x1 + 0, 3x2 − 15)

• Por lo tanto, un punto m´ınimo del problema equivalente (o m´aximo del original) debe cumplir con: −800 + 15µ1 + 7µ2 + 0, 3µ3 x1(−800 + 15µ1 + 7µ2 + 0, 3µ3) µ1(15x1 + 5x2 − 600) µ3(0, 3x1 + 0, 3x2 − 15) 15x1 + 5x2 − 600 0, 3x1 + 0, 3x2 − 15 x1 x2 µ1 µ3 Apuntes de Clases • Optimizaci´on • Claudio Seebach

≥ = = = ≤ ≤ ≥ ≥ ≥ ≥

0 −600 + 5µ1 + 14µ2 + 0, 3µ3 0 x2(−600 + 5µ1 + 14µ2 + 0, 3µ3) 0 µ2(7x1 + 14x2 − 630) 0 0 7x1 + 14x2 − 630 0 0 0 0 µ2 0 Programaci´on Lineal • 34

≥ 0 = 0 = 0 ≤ 0

≥ 0

Ejemplo KKT y Programaci´ on Lineal • Identifiquemos los multiplicadores µ1, µ2 y µ3 asociados al punto x∗1 = 35 y x∗2 = 15 y verifiquemo que esta soluci´on satisface las condiciones de KKT. • Las condiciones de complementariedad de las holguras en este punto exigen: −800 + 15µ1 + 7µ2 + 0, 3µ3 = 0 −600 + 5µ1 + 14µ2 + 0, 3µ3 = 0 µ2 = 0 • As´ı se obtiene: µ1 = 20 µ3 = 1666, 6 • El punto x∗1 = 35 , x∗2 = 15, µ1 = 20, µ2 = 0, µ3 = 1666, 6 satisface todas las condiciones de KKT y por lo tanto corresponde a un ´optimo global del problema. Apuntes de Clases • Optimizaci´on • Claudio Seebach

Programaci´ on Lineal • 35

KKT y Programaci´ on Lineal • Observaci´ on 1: Los multiplicadores obtenidos no dependen de los insumos disponibles. Cambios menores en el vector de insumos b modifican la combinaci´on ´optima de planchas (x∗1 , x∗2 ), pero no modifican los multiplicadores ´optimos. • Observaci´ on 2: Como se trata de un problema de programaci´on lineal, el impacto en el valor ´optimo de aumentar en una unidad el insumo disponible de una restricci´on activa ser´a el mismo independiente de el valor del lado derecho (en la medida que el conjunto restante de restricciones activas en el punto ´optimo no cambie). • Observaci´ on 3: Si la restricci´on est´a inactiva, el multiplicador permanecer´a nulo ante cambios en el total de insumos disponibles que la mantengan inactiva. • Observaci´ on 4: Como se trata de un problema de programaci´on lineal, la estimaci´on de primer orden del impacto en el valor ´optimo es exacta para perturbaciones menores. Apuntes de Clases • Optimizaci´on • Claudio Seebach

Programaci´ on Lineal • 36