Modelos de Programación Matemática “
Las proposiciones matemáticas, en cuanto tienen que ver con la realidad, no son ciertas; y en cuanto que son ciertas, no tienen nada que ver con la realidad ” A. Einstein
1
[email protected]
10/03/2011
Modelos de Programación Matemática Una clasificación de los modelos de Programación Matemática podría tener en cuenta las siguientes características:
2
Estructura objetivos y restricciones (lineal o no lineal) Características de las Variables (Reales, Discretas -enteras-, Binarias) Certidumbre de los Parámetros (Ciertos e Inciertos) Número de Objetivos (Ninguno, Uno o más de Uno) Número de Restricciones (Ninguna, Más de Cero)
[email protected]
10/03/2011
Pasos en la Construcción de un Modelo de Programación Matemático Análisis de Problema Conjuntos de Datos, y por tanto de Índices Parámetros Objetivo Variables de Control Variables de Decisión Restricciones Más Variables de Control Modelo Completo Validación
3
[email protected]
10/03/2011
Validaciones de los Modelos Validación del Modelo
Modelos Incompatibles Modelos no acotados Modelos Resolubles
Resultados Lógicos Comparación con resultados reales Modificación de Coeficientes en la función objetivo
Cómo construir un buen modelo
4
Facilidad para entender el modelo Facilidad para detectar errores en el modelo Facilidad para computar la solución
[email protected]
10/03/2011
Programación Lineal Se denomina Programación Lineal a aquel problema definido por un objetivo y un conjunto de restricciones, en los que cada una de ellas es una función lineal de variables reales. Algunos de los problemas clásicos de Programación Lineal son:
Blending (Mezcla). Product Mix (Catálogo de Productos). Decisión de Inversiones. Problema del Transporte
min ci xi i
s.a.
a
i, j
·xi b j
i
xi 0 http://thales.cica.es/rd/Recursos/rd98/Matematicas/29/intro.html 5
[email protected]
10/03/2011
Interpretación y Uso de la Solución de un Modelo de Programación Lineal Interpretaciones Económicas
El Modelo Dual Precios Sombra Costes Reducidos
Análisis de Sensibilidad y Estabilidad de un Modelo
6
Rangos en las restricciones Rangos en el objetivo Modelos Estables
[email protected]
10/03/2011
Programación Entera
Programación Entera se produce cuando el dominio de las variables no es real sino discreto.
Diferentes áreas dónde se aplica la PE
Problemas con inputs o outputs discretos
Problemas con condiciones lógicas
Problemas de combinatorias
Problemas No-Lineales
Problemas de Redes
El uso de variables discretas
z 14.2857
( x1 1)
( x1 2)
Subproblema 2 ( x1 , x2 , x3 ) (1,1.5,2.667 )
Subproblema 3
z 2 14.1667 ( x3 2)
No factible ( x3 3)
Cantidades indivisibles
Variables de decisión
Variables Indicadoras
En programación lineal cuantas más restricciones, en general, peor. En programación Entera cuantas más restricciones en general mejor.
7
Problema 1 ( x1 , x2 , x3 ) (1.1428,0,3)
Subproblema 4 ( x1 , x2 , x3 ) (0.714,1.5,2) z 4 9.42857
[email protected]
Subproblema 5 ( x1 , x2 , x3 ) (1,0,3) z5 14
10/03/2011
Programación No-Lineal Objetivos y Restricciones No Lineales
Economías de Escala y Elasticidad de Precios Relaciones entre variables
Funciones y Regiones Convexas
Región Convexa: Región del espacio entre el segmento que une dos puntos cualesquiera está en la región Función Convexa: Una función es convexa si el conjunto de puntos (x,y) donde y f(x) forma una región convexa Modelo de PM convexo: Se dice que un modelo de Programación Matemática es convexo si implica la minimización de una función convexa sobre una región convexa.
Óptimos Locales y Globales Programación Separable Se dice que una función es separable si puede expresarse como la suma de funciones de una única var. La mayor parte de las funciones pueden separarse. Convertir un modelo no-lineal en modelo separable
8
[email protected]
10/03/2011
Programación Lineal 0-1 Es un tipo especial de Programación Entera donde las variables sólo pueden adoptar 0 o 1. Reciben también el nombre de Problemas de Combinatoria. Suelen ser de muy difícil resolución. Algunos de los problemas clásicos son:
9
Problema de la Mochila Cubrimiento Partición Empaquetado Viajante de Comercio Problemas de Corte
[email protected]
10/03/2011
Programación Estocástica
La Programación Estocástica concentra el estudio, formulación y resolución de modelos de optimización que incorporan explícitamente parámetros aleatorios, ya sea a través de diferentes escenarios o de variables aleatorias con distribuciones de probabilidad discreta o continua. En particular, los modelos con recurso comprende una clase especial de modelos de programación estocástica que permiten enfrentar la presencia de parámetros aleatorios mediante el uso de dos grupos de variables de decisión, un primer grupo eligido entre aquellas variables cuyo valor se toma independiente de la realización (futura) de los parámetros y, el otro, entre aquellas decisiones en respuesta a esa realización (recurso), que permiten dar la flexibilidad necesaria al modelo, tomando en cuenta para la elección de una solución óptima las desviaciones o el valor esperado asociado a este recurso.
http://users.iems.nwu.edu/~jrbirge//html/dholmes/StoProIntro.html http://stoprog.org/ 10
[email protected]
10/03/2011
Definición de Objetivos Lineales
Objetivos Simples
Minimizar el valor absoluto
Min
x y
Minimizar el Máximo (o Maximizar el Mínimo)
Min
Max a j xij i
Objetivos de Ratio
t
a x Max b x
1 bj x j j
j i
j
i
j
j
j
wj x j t
b w j
j
d jxj
Max a j w j
j
j
d j w j et
1
j
j
11
e
[email protected]
10/03/2011
0
Programación Multiobjetivo y Objetivos No Optimizables
Múltiples Objetivos
Combinación Lineal de Objetivos:
Programación Multinivel. Goal Programming
min OBJ Obj1 Obj 2 Obj3 s.t El resto de restricciones
min Obj3 : s.t.Obj 2 1.1* Cota 2 s.t.Obj1 1.01* Cota1 s.t El resto de restricciones
Soluciones No-Dominadas. Optimos de Pareto.
Objetivos no optimizables: Por ejemplo Sobrevivir 12
[email protected]
10/03/2011
Restricciones según su relación con la realidad.
Restricciones de capacidad Disponibilidad de materia prima Limitaciones en la demanda del mercado Continuidad o Balance Restricciones de Calidad. Restricciones Lógicas
13
[email protected]
10/03/2011
Linealizando relaciones Lógicas. 1 aj xj b j
a
j
x j M M b
j
a x j
j
b 1
j
a x j
j
m· b
j
a x j
j
b 1
1 aj xj b j j
j
j
(m ) b
j
j
a x
a x
j
b 1
j
a x j
j
m m b
j
M · b
j
( M ) b
j
a x j
j
a x j
j
14
j
b 1
a x j
j
[email protected]
10/03/2011
Restricciones según su relación con otras restricciones.
Restricciones Duras y Blandas
a x j
j
b
j
a x j
j
u b
j
Restricciones Conflictivas Restricciones Redundantes (precio sombra nulo) Cotas Simples y Generalizadas.
Restricciones de Rango.
15
[email protected]
10/03/2011
Un problema sencillo?
Una empresa fabrica 2 productos P y Q.
P se vende a 90 € y Q a 100 €. La demanda de cada producto es de P=100 unidades/semana y de Q=50 unidades/semana.
Los dos productos requieren de una misma pieza central, la Materia Prima de la cual vale a 20€ la unidad. Para fabricar la pieza central hacen falta 15 minutos del recurso B y 5 minutos del recurso C. Para fabricar el componente 1 del producto P hace falta materia prima por valor de 20€/unidad, 15 minutos del recurso A y 10 minutos del recurso C. Al ensamblar la pieza central con el componente 1 utilizamos otro componente 3 que se compra al precio de 5€/unidad, lo ensambla el recurso D en 15 minutos cada unidad.
El producto Q sigue un procedimiento similar. El componente 2 utiliza Materia Prima por valor de 20€/unidad, pasa por el recurso A donde está 10 minutos y luego por el proceso B donde está 15 minutos. Finalmente es ensamblado por el recurso D en 5 minutos. El mes tiene 20 días de 8 horas. Los gastos totales son 3600€/semana
¿Cual es el mejor plan de producción para la empresa? ¿Qué beneficio le aporta?
¿Cuál es el valor de una hora más de cada recurso productivo?
Establecer un objetivo que pretenda maximizar el ratio beneficio entre horas totales de trabajo.
Establecer un objetivo que pretenda
¿Cómo incorporar limitaciones en la disponibilidad de materia prima?
¿Cómo incorporar un número indefinido de productos al modelo?
16
[email protected]
10/03/2011
Problemas de Programación Lineal
Una compañía fabrica dos modelos de sombrero: Bae y Viz. La fabricación de los sombreros se realiza en las secciones de moldeado, pintura y montaje. La fabricación de cada modelo Bae requiere 2 horas de moldeado, 3 de pintura y una de montaje. La fabricación del modelo Viz requiere tres horas de moldeado, 2 de pintura y una de montaje. Las secciones de moldeado y pintura disponen, cada una, de un máximo de 1.500 horas cada mes, y la de montaje de 600.Si el modelo Bae se vende a 10 € y el modelo Viz a 12 € ¿qué cantidad de sombreros de cada tipo ha de fabricar para maximizar el beneficio mensual?
17
[email protected]
10/03/2011
Problemas de Programación Lineal
Una persona tiene 5.000 € para invertir en dos tipos de acciones A y B. El tipo A tiene bastante riesgo con un interés anual del 10% y el tipo B es bastante seguro con un interés anual del 7%. Decide invertir como máximo 2.000 € en A y como mínimo 1.000 € en B, e invertir en A por lo menos tanto como en B. ¿Cómo deberá invertir sus 5.000 € para maximizar sus intereses anuales?
18
[email protected]
10/03/2011
Problemas de Programación Lineal
Imaginemos que las necesidades semanales mínimas de una persona en proteínas, hidratos de carbono y grasas son 10, 9, 12 unidades respectivamente. Supongamos que debemos obtener un preparado con esa composición mínima mezclando los productos A y B cuyos contenidos por kilogramo son los que se indican en la tabla ¿Cuántos kilogramos de cada producto deberán comprarse semanalmente para que el costo de preparar la dieta sea mínimo?
10/03/2011
Proteínas
Hidratos
Grasas
Coste(kg)
Producto A
2
5
2
600
Producto B
3
1
3
400
[email protected]
19
Problemas de Programación Lineal
Una empresa fabrica 7 productos distintos, para los que utiliza 5 tipos de Máquinas (Fresas(4), Tornos(2), Sierras(3), Soldadoras(1) y Rectificadoras(1)). Aunque la cantidad de ellas puede variar a lo largo del tiempo.
También varía el número de días en cada uno de los meses Se trabaja 16 horas al día y no es posible utilizar horas extras.
Cada producto utiliza cada máquina durante una cierta cantidad de tiempo. Cada unidad de producto aporta un determinado beneficio.
La demanda de cada producto es variable según los meses, cómo también lo son el número de días laborables en cada uno de ellos. Consideramos un horizonte de planificación de 6 meses.
Inicialmente no se dispone de stock de ningún producto, y el número total de unidades al final de cada mes almacenadas está limitado a 400 unidades. El coste de almacén de cada unidad que quede al final de mes es 0.5€ 20
[email protected]
10/03/2011
Mezcla de Productos
Una empresa con tres secciones productivas (tornos(3), fresas(2), Montaje (8 montadores por turno)) fabrica 5 productos distintos 6 días a la semana, 2 turnos de 8 horas al día.
Los beneficios de los productos, y la necesidad en horas de cada recurso, se expresa en la siguiente tabla PR1
PR2
PR3
PR4
PR5
550
600
350
400
200
Torno
12
20
25
15
Fresa
10
8
16
Montaje
20
20
20
20
20
Beneficio unit. Requerimientos
21
[email protected]
10/03/2011
El modelo MPL Mezcla de Productos INDEX i= 1..5 j= (torno,fresa,montaje) DATA benef[i] := (550,600,350,400,200) prodhoras[j,i] :=(12,20,0,25,15, 10,8,6,0,0, 20,20,20,20,20) rechoras[j] := (288,192,384) VARIABLES x[i] MAX SUM( i : benef*x) SUBJECT TO restr[j] : SUM(i : prodhoras*x)