Formulaci´ on y Ejemplos Resoluci´ on gr´ afica Resoluci´ on del problema: algoritmo del Simplex

Programaci´on Lineal Continua Elisenda Molina Universidad Carlos III de Madrid [email protected]

8 de octubre de 2008

Investigaci´ on Operativa

Programaci´ on Lineal Continua

Formulaci´ on y Ejemplos Resoluci´ on gr´ afica Resoluci´ on del problema: algoritmo del Simplex

Esquema

1

Formulaci´on y Ejemplos

2

Resoluci´on gr´afica

3

Resoluci´on del problema: algoritmo del Simplex

Investigaci´ on Operativa

Programaci´ on Lineal Continua

Formulaci´ on y Ejemplos Resoluci´ on gr´ afica Resoluci´ on del problema: algoritmo del Simplex

Ejemplo: Producci´on de carb´on Una empresa minera produce lignito y antracita. El proceso de producci´on est´a dividido en tres fases: 1 2 3

Corte del mineral, Tamizado y a la selecci´ on, Lavado.

Datos: Lignito Antracita Disponibilidad m´axima

Corte 3 4 12

Tamizado 3 3 10

Lavado 4 2 8

Beneficio 24 18

¿cu´antas toneladas de cada clase de carb´on debe producir al d´ıa para maximizar sus beneficios?

Investigaci´ on Operativa

Programaci´ on Lineal Continua

Formulaci´ on y Ejemplos Resoluci´ on gr´ afica Resoluci´ on del problema: algoritmo del Simplex

Asignaci´on y distribuci´on de recursos/Produci´on

Problemas en los que se trata de asignar o localizar un n´ umero de recursos, siempre limitados, entre diversas actividades. Se plantea un conflicto entre la funci´on objetivo, que cuantifica el beneficio derivado de cada asignaci´on, y las restricciones, que establecen los l´ımites a las asignaciones posibles.

Investigaci´ on Operativa

Programaci´ on Lineal Continua

Formulaci´ on y Ejemplos Resoluci´ on gr´ afica Resoluci´ on del problema: algoritmo del Simplex

Problema de Programaci´on Lineal Continua Clase m´as importante de problemas de optimizaci´on Base para la resoluci´on de otros problema de optimizaci´on Uno de los modelos matem´aticos m´as aplicados (ver top10.pdf) Elementos y caracter´ısticas: 1 2 3

Variables de decisi´ on continuas: xt = (x1 , . . . , xn ) Funci´on objetivo lineal: f (x1 , . . . , xn ) Restricciones lineales: para j = 1, . . . , m, aj1 x1 + aj2 x2 + · · · + ajn xn ≤ bj ,

´o

aj1 x1 + aj2 x2 + · · · + ajn xn ≥ bj ,

´o

aj1 x1 + aj2 x2 + · · · + ajn xn = bj

Investigaci´ on Operativa

Programaci´ on Lineal Continua

Formulaci´ on y Ejemplos Resoluci´ on gr´ afica Resoluci´ on del problema: algoritmo del Simplex

Programaci´on Matem´atica: alternativas

1

Programaci´on Entera (Mixta): cantidades no divisibles y enteras y/o decisiones l´ogicas.

2

Programaci´on no Lineal: relaciones no proporcionales y no aditivas.

3

Programaci´on Multiobjetivo: varios objetivos.

4

Programaci´on Estoc´astica, que permite incorporar la incertidumbre inherente en muchas situaciones reales al modelo.

5

Programaci´on Difusa, que permite trabajar con problemas en los que las restricciones no son r´ıgidas (modelizan relaciones vagamente definidas).

Investigaci´ on Operativa

Programaci´ on Lineal Continua

Formulaci´ on y Ejemplos Resoluci´ on gr´ afica Resoluci´ on del problema: algoritmo del Simplex

El problema de la dieta Aplicaci´on cl´asica de la Programaci´on Lineal y un ejemplo t´ıpico de esta familia de problemas. Se trata de alimentar a un colectivo de la forma menos costosa, satisfaciendo las necesidades nutricionales. Un veterinario aconseja a un granjero dedicado a la cr´ıa de pollos una dieta m´ınima para la alimentaci´on de las aves consistente en 3 unidades de hierro y 4 unidades de vitaminas. Dieta: mezcla de ma´ız, harina de pescado y pienso sint´etico. Datos: Ma´ız Harina Pienso

Hierro (u/kg) 2,5 3 1

Vitaminas (u/kg) 1 3 2

Coste (euro/kg) 0,3 0,5 0,2

El granjero se pregunta por la composici´on de la dieta que, satisfaciendo las necesidades alimenticias, minimice el coste total. Investigaci´ on Operativa

Programaci´ on Lineal Continua

Formulaci´ on y Ejemplos Resoluci´ on gr´ afica Resoluci´ on del problema: algoritmo del Simplex

Ejemplo Una refiner´ıa de petr´oleo puede destilar 2 tipos de crudo: un crudo medio de Arabia Saud´ı y uno pesado de Venezuela, para producir gasolina, fuel de avi´on y lubricantes. Dependiendo de las caracter´ısticas del crudo el proceso de refino da lugar a distintos derivados en diferentes proporciones. Datos: Gasolina Fuel avi´on Lubricantes Disponible/d´ıa Coste

Medio 0.3 0.4 0.2 9000 20

Pesado 0.4 0.2 0.3 6000 15

Requerimientos 2000 1500 500

¿C´ omo satisfacer la demanda comprometida a coste m´ınimo?

Investigaci´ on Operativa

Programaci´ on Lineal Continua

Formulaci´ on y Ejemplos Resoluci´ on gr´ afica Resoluci´ on del problema: algoritmo del Simplex

Problemas de Mezclas Planificaci´on ´optima de la mezcla de productos a fabricar: determinar la cantidad de materia prima a comprar/producir, as´ı como la proporci´on de cada materia prima en cada producto final. Todo ello, teniendo en cuenta las caracter´ısticas t´ecnicas del producto final, las materias primas disponibles y sus componentes t´ecnicos. Las limitaciones que suelen aparecer vienen dadas por: garant´ıa m´ınima relativa, costos fijos de producci´on, n´ umero m´aximo de ingredientes, ingredientes sustitutivos, procesos sustitutivos, proporciones de mercado, proporciones en caracter´ısticas t´ecnicas, tarifas de precios, Aplicaciones: industrias de la alimentaci´on, ganadera, farmac´eutica, qu´ımica, sider´ urgica o petrol´ıfera. Investigaci´ on Operativa

Programaci´ on Lineal Continua

Formulaci´ on y Ejemplos Resoluci´ on gr´ afica Resoluci´ on del problema: algoritmo del Simplex

Regi´on Factible

Regi´ on factible: conjunto de puntos que verifican todas las restricciones del modelo  Min. 2x1 − x2     −x1 + x2 ≤ 2,  s.a x1 + x2 ≤ 4,   5x1 + 3x2 ≤ 15,    x 1 , x2 ≥ 0. Poliedro: intersecci´on finita de semiespacios, conjunto convexo

Investigaci´ on Operativa

Programaci´ on Lineal Continua

Formulaci´ on y Ejemplos Resoluci´ on gr´ afica Resoluci´ on del problema: algoritmo del Simplex

Regi´on Factible

−x1 + x2 = 2

x1 + x2 = 4

5x1 + 3x2 = 15

Investigaci´ on Operativa

Programaci´ on Lineal Continua

La

Formulaci´ on y Ejemplos Resoluci´ on gr´ afica Resoluci´ on del problema: algoritmo del Simplex

Rectas de nivel y

m´ın 2x1 − x2 , s.a −x1 + x2 ≤ 2, gradientex1 + x2 ≤ 4, 5x1 + 3x2 ≤ 15, x1 , x2 ≥ 0. 2x1 − x2 = −2

2x1 − x2 = 0 2x1 − x2 = 1 (0, 2)

El punto ´ optimo es (0, 2), en el la funci´ on objetivo vale -2. El punto ´optimo es (0, 2), en el queque la funci´ on objetivo vale -2.

Investigaci´ on Operativa

Programaci´ on Lineal Continua

Formulaci´ on y Ejemplos Resoluci´ on gr´ afica Resoluci´ on del problema: algoritmo del Simplex

Ejemplos: resoluci´on en clase

Investigaci´ on Operativa

Programaci´ on Lineal Continua

Formulaci´ on y Ejemplos Resoluci´ on gr´ afica Resoluci´ on del problema: algoritmo del Simplex

V´ertices: teorema fundamental de la PLC

Soluciones de un problema de Programaci´on Lineal: Si tiene soluci´on finita: La soluci´on se encuentra en un punto extremo. Estos existen en un n´ umero finito.

Soluci´on no acotada Direcci´on extrema de decrecimiento (m´ın.), crecimiento (m´ax.), partiendo de un punto extremo.

El problema no tiene soluci´on: la regi´on es vac´ıa y, por tanto, no existen puntos extremos.

Investigaci´ on Operativa

Programaci´ on Lineal Continua

Formulaci´ on y Ejemplos Resoluci´ on gr´ afica Resoluci´ on del problema: algoritmo del Simplex

M´etodos de resoluci´on

Las dos alternativas m´as importantes son: 1

Algoritmo del simplex.

2

M´etodos de punto interior.

El primer m´etodo se mueve por la frontera de la regi´on factible, hasta llegar a un punto ´optimo. Se basa en un resultado b´asico: Si el problema de programaci´on lineal tiene soluci´on, entonces se alcanza en al menos un v´ertice. Los m´etodos de punto interior se mueven por el interior de la regi´on factible. Utiliza t´ecnicas de programaci´on no lineal.

Investigaci´ on Operativa

Programaci´ on Lineal Continua

Formulaci´ on y Ejemplos Resoluci´ on gr´ afica Resoluci´ on del problema: algoritmo del Simplex

V´ertices: Puntos Extremos y Soluciones B´asicas Factibles X Punto extremo o v´ertice: punto intersecci´on de al menos n caras o hiperplanos (definici´on geom´etrica). X Soluci´on B´asica Factible: Se trabaja con PLs en Forma Est´andar

Formulaci´on est´andar Funci´ on objetivo de “minimizar”, restricciones de “igualdad”, constantes del lado derecho no negativas y variables no negativas. m´ın z = ct x s.a. A x = b, x ≥ 0, con b ≥ 0 Investigaci´ on Operativa

Programaci´ on Lineal Continua

Formulaci´ on y Ejemplos Resoluci´ on gr´ afica Resoluci´ on del problema: algoritmo del Simplex

Transformaciones

Cualquier problema de programaci´on lineal se puede formular en formato est´andar. Si el objetivo es maximizar, multiplicando la funci´on objetivo por -1, se convierte en un problema de minimizaci´on: m´ax 2x1 + 3x2 ⇔ m´ın − 2x1 − 3x2

Investigaci´ on Operativa

Programaci´ on Lineal Continua

Formulaci´ on y Ejemplos Resoluci´ on gr´ afica Resoluci´ on del problema: algoritmo del Simplex

Transformaciones. Restricci´on de desigualdad a igualdad x1 + 2x2 ≤ 3, Se introduce una nueva variable, denominada variable de holgura (slack): x1 + 2x2 +s1 = 3 con s1 ≥ 0. Si la desigualdad es de tipo “mayor o igual que”, x1 + x2 ≥ 10, la variable de holgura se introduce con signo negativo en la restricci´ on. Se denomina variable de exceso (surplus) x1 + x2 −s2 = 10 Investigaci´ on Operativa

con s2 ≥ 0. Programaci´ on Lineal Continua

Formulaci´ on y Ejemplos Resoluci´ on gr´ afica Resoluci´ on del problema: algoritmo del Simplex

Transformaciones. Signo de las variables X Si una variable x no est´a restringida en signo, se hace el cambio de variable x = x + − x −, x + = m´ax{x, 0} x − = m´ax{−x, 0} y se introducen estas variables en el modelo, en lugar de x. X Si una variable debe tomar un valor negativo, se hace el cambio x 0 = −x. X Si la cota inferior de una variable no es 0: x ≥ 3, se puede hacer el cambio x 0 = x − 3. Investigaci´ on Operativa

Programaci´ on Lineal Continua

Formulaci´ on y Ejemplos Resoluci´ on gr´ afica Resoluci´ on del problema: algoritmo del Simplex

Transformaciones. Valor absoluto Es habitual que en muchos problemas aparezca el valor absoluto de una expresi´on. Por ejemplo, si aparece |x|, para eliminarlo de la formulaci´on se hace el cambio: x = x + − x −, donde x + y x − est´an definidas como en el apartado anterior. El valor absoluto es, entonces: |x| = x + + x − . Si lo que aprarece es:  |2x1 + x2 | ≤ 3 ⇒

Investigaci´ on Operativa

2x1 + x2 ≤ 3 −3 ≤ 2x1 + x2

Programaci´ on Lineal Continua

Formulaci´ on y Ejemplos Resoluci´ on gr´ afica Resoluci´ on del problema: algoritmo del Simplex

Transformaciones. Objetivo maximin/minimax Un ordenador con 2 procesadores funciona durante al menos 10 horas diarias en aplicaciones administrativas y acad´emicas. Cada tarea administrativa requiere 2 segundos de CPU si se ejecuta en el procesador 1 y 6 segundos de CPU si se ejecuta en el procesador 2. Cada tarea acad´emica requiere 5 segundos de CPU si se ejecuta en el procesador 1 y 3 segundos de CPU si se ejecuta en el procesador 2. Se requiere programar la cantidad de tareas diarias a asignar a cada procesador de manera que se minimice el tiempo que el ordenador est´a ocupado en estos trabajos.

Investigaci´ on Operativa

Programaci´ on Lineal Continua

Formulaci´ on y Ejemplos Resoluci´ on gr´ afica Resoluci´ on del problema: algoritmo del Simplex

V´ertices: Puntos Extremos y Soluciones B´asicas Factibles Sea el sistema de ecuaciones lineales Ax = b, donde A ∈ Mm×n (m ≤ n), es la matriz del sistema: A = (a1 , . . . , an ) aj = (a1j , . . . , aij , . . . , amj )t ∈ IR m , j–´esima columna de A rg (A) = m < n b ∈ IR m y x ∈ IR n . Soluciones B´asicas del sistema X Seleccionar m variables con columnas asociadas linealmente independientes ⇒ B=matriz b´asica El resto de columnas de A se denotan por N. Despu´es de un posible reordenamiento de las columnas de A: A = (B, N) con B ∈ Mm×m Investigaci´ on Operativa

Programaci´ on Lineal Continua

Formulaci´ on y Ejemplos Resoluci´ on gr´ afica Resoluci´ on del problema: algoritmo del Simplex

Soluciones B´asicas del sistema (cont.) X Se separa el vector x en dos subvectores: variables b´asicas y variables no b´asicas.   xB x= xN X Asignar el valor 0 a las variables no b´asicas: xN = 0 Y resolver las m ecuaciones con m inc´ognitas que queda: BxB = b ⇒ xB = B−1 b Soluciones B´asicas Factibles: Si adem´as xB = B−1 b ≥ 0 ⇒ x = Soluci´on B´asica Factible≡ punto extremo (v´ertice)
n ¿Cu´antos puntos extremos tenemos? como mucho m Investigaci´ on Operativa

Programaci´ on Lineal Continua

Formulaci´ on y Ejemplos Resoluci´ on gr´ afica Resoluci´ on del problema: algoritmo del Simplex

Soluciones B´asicas del sistema: terminolog´ıa

Soluci´on b´asica factible: si xB ≥ 0. B: matriz b´asica (o base) N: matriz no b´asica Componentes de xB : variables b´asicas Componentes de xN : variables no b´asicas Soluci´on b´asica factible no degenerada: si xB > 0. Soluci´on b´asica factible degenerada: si alguna de las componentes de xB es 0.

Investigaci´ on Operativa

Programaci´ on Lineal Continua

Formulaci´ on y Ejemplos Resoluci´ on gr´ afica Resoluci´ on del problema: algoritmo del Simplex

Algoritmo del simplex (Dantzig, 1949) George Dantzig es el padre de la PL. Desarroll´o el algoritmo del Simplex en 1947. El primer problema de PL fue el problema de la dieta (9 restricciones y 77 variables). Se necesitaron 9 trabajadores durante aproximadamente 15 d´ıas para realizar los c´alculos electr´onicos que resolvieron el problema. La primera implementaci´on del Simplex en ordenador es de 1952. Se resolvi´o un PL con 48 restricciones y 71 variables en 18 horas. Actualmente se pueden resolver PL’s con millones de variables y restricciones en horas o minutos.

Investigaci´ on Operativa

Programaci´ on Lineal Continua

Formulaci´ on y Ejemplos Resoluci´ on gr´ afica Resoluci´ on del problema: algoritmo del Simplex

Algoritmo del simplex (Dantzig, 1949) Procedimiento que permite moverse de un punto extremo a otro, mejorando cada vez (o, por lo menos, no empeorando) el objetivo. Detecta si la regi´on factible es vac´ıa o si la soluci´on ´optima es no acotada. A pesar de que han aparecido otros algoritmos, sigue siendo el m´as utilizado: Hay implementaciones muy eficientes del algoritmo. Proporciona mucha informaci´on sobre la estructura de la regi´on factible. Si el n´ umero de variables (n) es muy superior al de restricciones (m), el n´ umero de iteraciones oscila entre 32 m y 3m (n = 60 y m = 20, 30-60 iteraciones).

Investigaci´ on Operativa

Programaci´ on Lineal Continua

Formulaci´ on y Ejemplos Resoluci´ on gr´ afica Resoluci´ on del problema: algoritmo del Simplex

Algoritmo del simplex (Dantzig, 1949)

Clave del algoritmo Reconoce la optimalidad de un punto extremo sin tener que enumerar todos los puntos extremos. Utiliza CONDICIONES DE OPTIMALIDAD LOCALES

Investigaci´ on Operativa

Programaci´ on Lineal Continua

Formulaci´ on y Ejemplos Resoluci´ on gr´ afica Resoluci´ on del problema: algoritmo del Simplex

Algoritmo del simplexAlgoritmo (Dantzig, 1949) del simplex Punto extremo Sol. B´ asica factible

¿Es factible? ¿Hay redundancia algebraica?

Contraste de Optimalidad

´ Soluci´ on Optima

FIN

Contraste de no acotaci´ on

Soluci´ on no acotada

FIN

Nuevo punto extremo (cambio de base)

7

Investigaci´ on Operativa

Programaci´ on Lineal Continua