Story Transcript
Programaci´ on Matem´ atica Programaci´ on lineal
Programaci´on lineal Jes´ us Get´an y Eva Boj Facultat d’Economia i Empresa Universitat de Barcelona
Marzo de 2014
Jes´ us Get´ an y Eva Boj
Programaci´ on lineal
1 / 18
Programaci´ on Matem´ atica Programaci´ on lineal
Programaci´on lineal Formulaci´on de un Programa lineal Caracter´ısticas del Programas lineal Sobre la regi´on factible Propiedades de los programas lineales
Jes´ us Get´ an y Eva Boj
Programaci´ on lineal
2 / 18
Programaci´ on Matem´ atica Programaci´ on lineal
Formulaci´ on de un Programa lineal Caracter´ısticas del Programas lineal Sobre la regi´ on factible Propiedades de los programas lineales
Un Programa lineal consta de: I
Funci´on objetivo.
I
Modeliza el problema econ´ omico.
I
Restricciones.
I
Nos marcan las limitaciones del modelo.
I
Restricciones de positividad.
I
Caracter´ıstica de los modelos econ´ omicos.
Jes´ us Get´ an y Eva Boj
Programaci´ on lineal
3 / 18
Programaci´ on Matem´ atica Programaci´ on lineal
Formulaci´ on de un Programa lineal Caracter´ısticas del Programas lineal Sobre la regi´ on factible Propiedades de los programas lineales
Un Programa lineal consta de: I
Funci´on objetivo.
I
Modeliza el problema econ´ omico.
I
Restricciones.
I
Nos marcan las limitaciones del modelo.
I
Restricciones de positividad.
I
Caracter´ıstica de los modelos econ´ omicos.
Jes´ us Get´ an y Eva Boj
Programaci´ on lineal
3 / 18
Programaci´ on Matem´ atica Programaci´ on lineal
Formulaci´ on de un Programa lineal Caracter´ısticas del Programas lineal Sobre la regi´ on factible Propiedades de los programas lineales
Un Programa lineal consta de: I
Funci´on objetivo.
I
Modeliza el problema econ´ omico.
I
Restricciones.
I
Nos marcan las limitaciones del modelo.
I
Restricciones de positividad.
I
Caracter´ıstica de los modelos econ´ omicos.
Jes´ us Get´ an y Eva Boj
Programaci´ on lineal
3 / 18
Programaci´ on Matem´ atica Programaci´ on lineal
Formulaci´ on de un Programa lineal Caracter´ısticas del Programas lineal Sobre la regi´ on factible Propiedades de los programas lineales
Un Programa lineal consta de: I
Funci´on objetivo.
I
Modeliza el problema econ´ omico.
I
Restricciones.
I
Nos marcan las limitaciones del modelo.
I
Restricciones de positividad.
I
Caracter´ıstica de los modelos econ´ omicos.
Jes´ us Get´ an y Eva Boj
Programaci´ on lineal
3 / 18
Programaci´ on Matem´ atica Programaci´ on lineal
Formulaci´ on de un Programa lineal Caracter´ısticas del Programas lineal Sobre la regi´ on factible Propiedades de los programas lineales
Un Programa lineal consta de: I
Funci´on objetivo.
I
Modeliza el problema econ´ omico.
I
Restricciones.
I
Nos marcan las limitaciones del modelo.
I
Restricciones de positividad.
I
Caracter´ıstica de los modelos econ´ omicos.
Jes´ us Get´ an y Eva Boj
Programaci´ on lineal
3 / 18
Programaci´ on Matem´ atica Programaci´ on lineal
Formulaci´ on de un Programa lineal Caracter´ısticas del Programas lineal Sobre la regi´ on factible Propiedades de los programas lineales
Un Programa lineal consta de: I
Funci´on objetivo.
I
Modeliza el problema econ´ omico.
I
Restricciones.
I
Nos marcan las limitaciones del modelo.
I
Restricciones de positividad.
I
Caracter´ıstica de los modelos econ´ omicos.
Jes´ us Get´ an y Eva Boj
Programaci´ on lineal
3 / 18
Programaci´ on Matem´ atica Programaci´ on lineal
max c1 x1 + · · · cn xn sujeta a: a11 x1 + · · · + a1n xn ≤ b1 .. . am1 x1 + · · · + amn xn ≤ bm x1 , . . . , xn ≥ 0
Jes´ us Get´ an y Eva Boj
Formulaci´ on de un Programa lineal Caracter´ısticas del Programas lineal Sobre la regi´ on factible Propiedades de los programas lineales
cT x max sujeta a: Ax ≤ b ⇒ x ≥ 0.
Programaci´ on lineal
4 / 18
Programaci´ on Matem´ atica Programaci´ on lineal
Formulaci´ on de un Programa lineal Caracter´ısticas del Programas lineal Sobre la regi´ on factible Propiedades de los programas lineales
El PL se presenta en forma est´andar cuando todas sus restricciones son de igualdad y todas sus variables no negativas. La formulaci´on est´andar del PL es como sigue: m´ın cT x m´ax cT x sujeta a: Ax = b ´ o sujeta a: Ax = b x ≥0 x ≥0
Jes´ us Get´ an y Eva Boj
Programaci´ on lineal
5 / 18
Programaci´ on Matem´ atica Programaci´ on lineal
Formulaci´ on de un Programa lineal Caracter´ısticas del Programas lineal Sobre la regi´ on factible Propiedades de los programas lineales
Para realizar el paso de can´ onica a est´andar se seguir´an las siguientes reglas: 1) Las desigualdades se transforman en igualdades introduciendo unas nuevas variables llamadas variables de holgura con el signo + si la restricci´on es ≤ y con el signo - si la restricci´ on es ≥ .
Jes´ us Get´ an y Eva Boj
Programaci´ on lineal
6 / 18
Programaci´ on Matem´ atica Programaci´ on lineal
Formulaci´ on de un Programa lineal Caracter´ısticas del Programas lineal Sobre la regi´ on factible Propiedades de los programas lineales
Para realizar el paso de can´ onica a est´andar se seguir´an las siguientes reglas: 1) Las desigualdades se transforman en igualdades introduciendo unas nuevas variables llamadas variables de holgura con el signo + si la restricci´on es ≤ y con el signo - si la restricci´ on es ≥ . a11 x1 + · · · + a1n xn ≤ b1 −→ a11 x1 + · · · + a1n xn + h1 = b1 con h1 ≥ 0 a11 x1 + · · · + a1n xn ≥ b1 −→ a11 x1 + · · · + a1n xn − h1 = b1 con h1 ≥ 0
Jes´ us Get´ an y Eva Boj
Programaci´ on lineal
6 / 18
Programaci´ on Matem´ atica Programaci´ on lineal
Formulaci´ on de un Programa lineal Caracter´ısticas del Programas lineal Sobre la regi´ on factible Propiedades de los programas lineales
2) En el caso de las variables libres, es decir, el caso que no este sometida a restricciones de positividad, se introducir´an dos variables positivas.
Jes´ us Get´ an y Eva Boj
Programaci´ on lineal
7 / 18
Programaci´ on Matem´ atica Programaci´ on lineal
Formulaci´ on de un Programa lineal Caracter´ısticas del Programas lineal Sobre la regi´ on factible Propiedades de los programas lineales
2) En el caso de las variables libres, es decir, el caso que no este sometida a restricciones de positividad, se introducir´an dos variables positivas. xi libre −→ xi = hi − pi con que hi ≥ 0,
Jes´ us Get´ an y Eva Boj
Programaci´ on lineal
pi ≥ 0
7 / 18
Programaci´ on Matem´ atica Programaci´ on lineal
Formulaci´ on de un Programa lineal Caracter´ısticas del Programas lineal Sobre la regi´ on factible Propiedades de los programas lineales
3) Si multiplicamos por -1 los dos miembros de la restricci´on de desigualdad, esta cambia de sentido.
Jes´ us Get´ an y Eva Boj
Programaci´ on lineal
8 / 18
Programaci´ on Matem´ atica Programaci´ on lineal
Formulaci´ on de un Programa lineal Caracter´ısticas del Programas lineal Sobre la regi´ on factible Propiedades de los programas lineales
Caracter´ısticas del Programas lineal El problema de PL lleva impl´ıcitos una serie de hip´otesis sobre el comportamiento del fen´ omeno que permiten dar a este una representaci´on lineal.
Jes´ us Get´ an y Eva Boj
Programaci´ on lineal
9 / 18
Programaci´ on Matem´ atica Programaci´ on lineal
Formulaci´ on de un Programa lineal Caracter´ısticas del Programas lineal Sobre la regi´ on factible Propiedades de los programas lineales
Suposici´on de Aditividad y Proporcionalidad. 1. Respecto a la funci´ on objetivo: El hecho de que la funci´ on objetivo en un PL sea lineal implica: a) La contribuci´on a la funci´ on objetivo por parte de cada variable es proporcional al valor de la variable. b) La contribuci´on a la funci´ on objetivo por parte de cada variable es independiente de los valores de las otras variables de decisi´on. 2. Respecto a las restricciones: El hecho de que las restricciones en un PL sea lineal implica: a) La contribuci´on a parte izquierda de cada restricci´on por cada una de las variables es proporcional al valor de dicha variable. b) La contribuci´on de una variable a la parte izquierda de cada restricci´on es independiente de los valores de las otras variables. Jes´ us Get´ an y Eva Boj
Programaci´ on lineal
10 / 18
Programaci´ on Matem´ atica Programaci´ on lineal
Formulaci´ on de un Programa lineal Caracter´ısticas del Programas lineal Sobre la regi´ on factible Propiedades de los programas lineales
Suposici´on de Aditividad y Proporcionalidad. 1. Respecto a la funci´ on objetivo: El hecho de que la funci´ on objetivo en un PL sea lineal implica: a) La contribuci´on a la funci´ on objetivo por parte de cada variable es proporcional al valor de la variable. b) La contribuci´on a la funci´ on objetivo por parte de cada variable es independiente de los valores de las otras variables de decisi´on. 2. Respecto a las restricciones: El hecho de que las restricciones en un PL sea lineal implica: a) La contribuci´on a parte izquierda de cada restricci´on por cada una de las variables es proporcional al valor de dicha variable. b) La contribuci´on de una variable a la parte izquierda de cada restricci´on es independiente de los valores de las otras variables. Jes´ us Get´ an y Eva Boj
Programaci´ on lineal
10 / 18
Programaci´ on Matem´ atica Programaci´ on lineal
Formulaci´ on de un Programa lineal Caracter´ısticas del Programas lineal Sobre la regi´ on factible Propiedades de los programas lineales
Suposici´on de Divisibilidad y de Certeza. 1. La suposici´on de divisibilidad en un problema de PL requiere que todas las variables puedan tomar valores fraccionarios. Frecuentemente no se satisface en los problemas reales. Si en un problema de programaci´ on lineal las variables (todas o en parte) deben tomar valores enteros no negativos, se debe pasar a un problema de programaci´ on entera. En muchas situaciones en las cuales la divisibilidad no est´a presente, el redondeo puede dar una soluci´ on aceptable. (e.i. n´ umero de coches a fabricar), sin embargo, si quisi´eramos encontrar el n´ umero de silos a construir y el resultado fuese 0.4 no se puede redondear y, tenemos que pasar a programaci´ on entera. 2. La suposici´on de certeza indica que el valor de cada par´ametro (coeficiente de la funci´ on objetivo, ...) se conoce con exactitud. Jes´ us Get´ an y Eva Boj
Programaci´ on lineal
11 / 18
Programaci´ on Matem´ atica Programaci´ on lineal
Formulaci´ on de un Programa lineal Caracter´ısticas del Programas lineal Sobre la regi´ on factible Propiedades de los programas lineales
Suposici´on de Divisibilidad y de Certeza. 1. La suposici´on de divisibilidad en un problema de PL requiere que todas las variables puedan tomar valores fraccionarios. Frecuentemente no se satisface en los problemas reales. Si en un problema de programaci´ on lineal las variables (todas o en parte) deben tomar valores enteros no negativos, se debe pasar a un problema de programaci´ on entera. En muchas situaciones en las cuales la divisibilidad no est´a presente, el redondeo puede dar una soluci´ on aceptable. (e.i. n´ umero de coches a fabricar), sin embargo, si quisi´eramos encontrar el n´ umero de silos a construir y el resultado fuese 0.4 no se puede redondear y, tenemos que pasar a programaci´ on entera. 2. La suposici´on de certeza indica que el valor de cada par´ametro (coeficiente de la funci´ on objetivo, ...) se conoce con exactitud. Jes´ us Get´ an y Eva Boj
Programaci´ on lineal
11 / 18
Programaci´ on Matem´ atica Programaci´ on lineal
Formulaci´ on de un Programa lineal Caracter´ısticas del Programas lineal Sobre la regi´ on factible Propiedades de los programas lineales
Sobre la regi´ on factible La regi´on factible para un problema de PL es el conjunto de todos los puntos que cumplen todas las restricciones, as´ı como las restricciones de signo. Es posible que la regi´on factible sea vac´ıa. Tambi´en es posible que la regi´on factible sea no acotada. Una soluci´on ´optima para un PL es un punto de la regi´on factible tal que se obtiene el valor ´ o m´aximo (m´ınimo) de la funci´on objetivo.
Jes´ us Get´ an y Eva Boj
Programaci´ on lineal
12 / 18
Programaci´ on Matem´ atica Programaci´ on lineal
Formulaci´ on de un Programa lineal Caracter´ısticas del Programas lineal Sobre la regi´ on factible Propiedades de los programas lineales
Propiedades de los programas lineales 1. La funci´on objetivo es siempre c´ oncava y convexa. 2. El dominio es un conjunto convexo. 3. Los ´optimos locales son siempre globales.
Jes´ us Get´ an y Eva Boj
Programaci´ on lineal
13 / 18
Programaci´ on Matem´ atica Programaci´ on lineal
Formulaci´ on de un Programa lineal Caracter´ısticas del Programas lineal Sobre la regi´ on factible Propiedades de los programas lineales
Propiedades de los programas lineales 1. La funci´on objetivo es siempre c´ oncava y convexa. 2. El dominio es un conjunto convexo. 3. Los ´optimos locales son siempre globales.
Jes´ us Get´ an y Eva Boj
Programaci´ on lineal
13 / 18
Programaci´ on Matem´ atica Programaci´ on lineal
Formulaci´ on de un Programa lineal Caracter´ısticas del Programas lineal Sobre la regi´ on factible Propiedades de los programas lineales
Propiedades de los programas lineales 1. La funci´on objetivo es siempre c´ oncava y convexa. 2. El dominio es un conjunto convexo. 3. Los ´optimos locales son siempre globales.
Jes´ us Get´ an y Eva Boj
Programaci´ on lineal
13 / 18
Programaci´ on Matem´ atica Programaci´ on lineal
Formulaci´ on de un Programa lineal Caracter´ısticas del Programas lineal Sobre la regi´ on factible Propiedades de los programas lineales
Example Resuelve de forma geom´etrica m´ax 3x1 + 2x2 sujeta a: 2x1 + 1x2 ≤ 100 x1 + x2 ≤ 80 x1 ≤ 40 x1 , x2 ≥ 0
Jes´ us Get´ an y Eva Boj
Programaci´ on lineal
14 / 18
Programaci´ on Matem´ atica Programaci´ on lineal
Formulaci´ on de un Programa lineal Caracter´ısticas del Programas lineal Sobre la regi´ on factible Propiedades de los programas lineales
Existencia de soluci´ on 1. Si el dominio es cerrado y acotado siempre existen ´optimos y se encuentran en los v´ertices o en combinaciones convexas de ellos. 2. Si el dominio no es compacto, el PL puede no tener ´optimos. 3. Si el dominio no es compacto (no cerrado o no acotado) pero el PL tiene ´optimos, estos est´an en los v´ertices o en combinaciones convexas de los mismos. 4. Si el dominio es vac´ıo, el PL no tiene sentido. 5. El umero de v´ertices del dominio es siempre menor o igual a n´ n donde n es el n´ umero de restriciones y m el n´ umero de m restricciones necesarias para encontrar un v´ertice.
Jes´ us Get´ an y Eva Boj
Programaci´ on lineal
15 / 18
Programaci´ on Matem´ atica Programaci´ on lineal
Formulaci´ on de un Programa lineal Caracter´ısticas del Programas lineal Sobre la regi´ on factible Propiedades de los programas lineales
Existencia de soluci´ on 1. Si el dominio es cerrado y acotado siempre existen ´optimos y se encuentran en los v´ertices o en combinaciones convexas de ellos. 2. Si el dominio no es compacto, el PL puede no tener ´optimos. 3. Si el dominio no es compacto (no cerrado o no acotado) pero el PL tiene ´optimos, estos est´an en los v´ertices o en combinaciones convexas de los mismos. 4. Si el dominio es vac´ıo, el PL no tiene sentido. 5. El umero de v´ertices del dominio es siempre menor o igual a n´ n donde n es el n´ umero de restriciones y m el n´ umero de m restricciones necesarias para encontrar un v´ertice.
Jes´ us Get´ an y Eva Boj
Programaci´ on lineal
15 / 18
Programaci´ on Matem´ atica Programaci´ on lineal
Formulaci´ on de un Programa lineal Caracter´ısticas del Programas lineal Sobre la regi´ on factible Propiedades de los programas lineales
Existencia de soluci´ on 1. Si el dominio es cerrado y acotado siempre existen ´optimos y se encuentran en los v´ertices o en combinaciones convexas de ellos. 2. Si el dominio no es compacto, el PL puede no tener ´optimos. 3. Si el dominio no es compacto (no cerrado o no acotado) pero el PL tiene ´optimos, estos est´an en los v´ertices o en combinaciones convexas de los mismos. 4. Si el dominio es vac´ıo, el PL no tiene sentido. 5. El umero de v´ertices del dominio es siempre menor o igual a n´ n donde n es el n´ umero de restriciones y m el n´ umero de m restricciones necesarias para encontrar un v´ertice.
Jes´ us Get´ an y Eva Boj
Programaci´ on lineal
15 / 18
Programaci´ on Matem´ atica Programaci´ on lineal
Formulaci´ on de un Programa lineal Caracter´ısticas del Programas lineal Sobre la regi´ on factible Propiedades de los programas lineales
Existencia de soluci´ on 1. Si el dominio es cerrado y acotado siempre existen ´optimos y se encuentran en los v´ertices o en combinaciones convexas de ellos. 2. Si el dominio no es compacto, el PL puede no tener ´optimos. 3. Si el dominio no es compacto (no cerrado o no acotado) pero el PL tiene ´optimos, estos est´an en los v´ertices o en combinaciones convexas de los mismos. 4. Si el dominio es vac´ıo, el PL no tiene sentido. 5. El umero de v´ertices del dominio es siempre menor o igual a n´ n donde n es el n´ umero de restriciones y m el n´ umero de m restricciones necesarias para encontrar un v´ertice.
Jes´ us Get´ an y Eva Boj
Programaci´ on lineal
15 / 18
Programaci´ on Matem´ atica Programaci´ on lineal
Formulaci´ on de un Programa lineal Caracter´ısticas del Programas lineal Sobre la regi´ on factible Propiedades de los programas lineales
Existencia de soluci´ on 1. Si el dominio es cerrado y acotado siempre existen ´optimos y se encuentran en los v´ertices o en combinaciones convexas de ellos. 2. Si el dominio no es compacto, el PL puede no tener ´optimos. 3. Si el dominio no es compacto (no cerrado o no acotado) pero el PL tiene ´optimos, estos est´an en los v´ertices o en combinaciones convexas de los mismos. 4. Si el dominio es vac´ıo, el PL no tiene sentido. 5. El umero de v´ertices del dominio es siempre menor o igual a n´ n donde n es el n´ umero de restriciones y m el n´ umero de m restricciones necesarias para encontrar un v´ertice.
Jes´ us Get´ an y Eva Boj
Programaci´ on lineal
15 / 18
Programaci´ on Matem´ atica Programaci´ on lineal
Formulaci´ on de un Programa lineal Caracter´ısticas del Programas lineal Sobre la regi´ on factible Propiedades de los programas lineales
Sobre las soluciones 1. Los ´optimos, si existen, se encuentran en los v´ertices o en combinaciones convexas de ellos. 2. En un Programa lineal pasa una de las siguientes afirmaciones: o no existe soluci´ on, o la soluci´on es u ´nica, o tiene infinitas soluciones.
Jes´ us Get´ an y Eva Boj
Programaci´ on lineal
16 / 18
Programaci´ on Matem´ atica Programaci´ on lineal
Formulaci´ on de un Programa lineal Caracter´ısticas del Programas lineal Sobre la regi´ on factible Propiedades de los programas lineales
Sobre las soluciones 1. Los ´optimos, si existen, se encuentran en los v´ertices o en combinaciones convexas de ellos. 2. En un Programa lineal pasa una de las siguientes afirmaciones: o no existe soluci´ on, o la soluci´on es u ´nica, o tiene infinitas soluciones.
Jes´ us Get´ an y Eva Boj
Programaci´ on lineal
16 / 18
Programaci´ on Matem´ atica Programaci´ on lineal
Formulaci´ on de un Programa lineal Caracter´ısticas del Programas lineal Sobre la regi´ on factible Propiedades de los programas lineales
Soluci´ on del ejemplo
Figure: Dibujo
Jes´ us Get´ an y Eva Boj
Programaci´ on lineal
17 / 18
Programaci´ on Matem´ atica Programaci´ on lineal
Formulaci´ on de un Programa lineal Caracter´ısticas del Programas lineal Sobre la regi´ on factible Propiedades de los programas lineales
Hay 5 v´ertices. (0, 0) → f (0, 0) = 0, (40, 0) → f (40, 0) = 120, (0, 80) → f (0, 80) = 160, (20,60) → f (20,60) = 180, (40, 20) → f (40, 20) = 160. El m´aximo valor de la funci´ on objetivo es 180 y se alcanza para los valores de las variables de decisi´ on (x ∗ , y ∗ ) = (20,60).
Jes´ us Get´ an y Eva Boj
Programaci´ on lineal
18 / 18