m Co i Program Acionm Ate Matic A
Transcript of m Co i Program Acionm Ate Matic A
-
7/25/2019 m Co i Program Acionm Ate Matic A
1/22
Modelos de Programacin
Matemtica
Las proposiciones matemticas, 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
10/03/20111 [email protected]
-
7/25/2019 m Co i Program Acionm Ate Matic A
2/22
Modelos de Programacin Matemtica
Una clasificacin de los modelos de ProgramacinMatemtica podra tener en cuenta las siguientescaractersticas: Estructura objetivos y restricciones (lineal o no lineal) Caractersticas de las Variables (Reales, Discretas -enteras-,
Binarias) Certidumbre de los Parmetros (Ciertos e Inciertos) Nmero de Objetivos (Ninguno, Uno o ms de Uno) Nmero de Restricciones (Ninguna, Ms de Cero)
10/03/20112 [email protected]
-
7/25/2019 m Co i Program Acionm Ate Matic A
3/22
Pasos en la Construccin de un Modelo de
Programacin Matemtico
Anlisis de Problema Conjuntos de Datos, y por tanto de ndices Parmetros Objetivo Variables de Control Variables de Decisin Restricciones Ms Variables de Control Modelo Completo Validacin
10/03/20113 [email protected]
-
7/25/2019 m Co i Program Acionm Ate Matic A
4/22
Validaciones de los Modelos
Validacin del Modelo Modelos Incompatibles
Modelos no acotados
Modelos Resolubles Resultados Lgicos
Comparacin con resultados reales
Modificacin de Coeficientes en la funcin objetivo
Cmo construir un buen modelo Facilidad para entender el modelo Facilidad para detectar errores en el modelo
Facilidad para computar la solucin
10/03/20114 [email protected]
-
7/25/2019 m Co i Program Acionm Ate Matic A
5/22
Programacin Lineal
Se denomina Programacin Lineal a aquel problema definidopor un objetivo y un conjunto de restricciones, en los quecadaunadeellasesunafuncinlineal devariablesreales.
Algunosde losproblemasclsicosdeProgramacinLineal son: Blending(Mezcla).
Product Mix (Catlogo deProductos). Decisin de Inversiones.
ProblemadelTransporte
http://thales.cica.es/rd/Recursos/rd98/Matematicas/29/intro.html
10/03/20115 [email protected]
,
min
. .
0
i ii
i j i j
i
i
c x
s a
a x b
x
-
7/25/2019 m Co i Program Acionm Ate Matic A
6/22
Interpretacin y Uso de la Solucin de un
Modelo de Programacin Lineal
Interpretaciones Econmicas El Modelo Dual
Precios Sombra
Costes Reducidos
Anlisis de Sensibilidad y Estabilidad de un Modelo Rangos en las restricciones
Rangos en el objetivo Modelos Estables
10/03/20116 [email protected]
-
7/25/2019 m Co i Program Acionm Ate Matic A
7/22
Programacin Entera Programacin Entera se produce cuando el dominio de las variables no es real sino discreto.
Diferentes reas dnde se aplica la PE Problemas con inputs o outputs discretos
Problemas con condiciones lgicas
Problemas de combinatorias
Problemas No-Lineales
Problemas de Redes
El uso de variables discretas Cantidades indivisibles
Variables de decisin
Variables Indicadoras
En programacin lineal cuantas ms restricciones, en general, peor.
En programacin Entera cuantas ms restricciones en general mejor.
10/03/20117 [email protected]
2857.14
)3,0,1428.1(),,(321
z
xxx
Problema 1
1667.14
)667.2,5.1,1(),,(
2
321
z
xxx
Subproblema 2
42857.9
)2,5.1,714.0(),,(
4
321
z
xxx
Subproblema 4
14
)3,0,1(),,(
5
321
z
xxx
Subproblema 5
Subproblema 3
No factible
)1( 1x )2( 1x
)2( 3 x )3( 3 x
-
7/25/2019 m Co i Program Acionm Ate Matic A
8/22
Programacin No-Lineal Objetivos y Restricciones No Lineales
Economas de Escala y Elasticidad de Precios Relaciones entre variables
Funciones y Regiones Convexas Regin Convexa: Regin del espacio entre el segmento que une dos puntos cualesquiera
est en la regin Funcin Convexa: Una funcin es convexa si el conjunto de puntos (x,y) donde y f(x)
forma una regin convexa Modelo de PM convexo: Se dice que un modelo de Programacin Matemtica es convexo
si implica la minimizacin de una funcin convexa sobre una regin convexa.
ptimos Locales y Globales Programacin Separable
Se dice que una funcin es separable si puede expresarse como la suma defunciones de una nica var.
La mayor parte de las funciones pueden separarse. Convertir un modelo no-lineal en modelo separable
10/03/20118 [email protected]
-
7/25/2019 m Co i Program Acionm Ate Matic A
9/22
Programacin Lineal 0-1
Es un tipo especial de Programacin Entera donde las variablesslo pueden adoptar 0 o 1.
Reciben tambin el nombre de Problemas de Combinatoria.
Suelen ser de muy difcil resolucin.
Algunos de los problemas clsicos son: Problema de la Mochila Cubrimiento
Particin
Empaquetado
Viajante de Comercio
Problemas de Corte
10/03/20119 [email protected]
-
7/25/2019 m Co i Program Acionm Ate Matic A
10/22
Programacin Estocstica
La Programacin Estocstica concentra el estudio, formulacin y resolucinde modelos de optimizacin que incorporan explcitamente parmetrosaleatorios, ya sea a travs de diferentes escenarios o de variables aleatoriascon distribuciones de probabilidad discreta o continua. En particular, losmodelos con recurso comprende una clase especial de modelos deprogramacin estocstica que permiten enfrentar la presencia deparmetros aleatorios mediante el uso de dos grupos de variables dedecisin, un primer grupo eligido entre aquellas variables cuyo valor setoma independiente de la realizacin (futura) de los parmetros y, el otro,entre aquellas decisiones en respuesta a esa realizacin (recurso), quepermiten dar la flexibilidad necesaria al modelo, tomando en cuenta para laeleccin de una solucin ptima las desviaciones o el valor esperadoasociado a este recurso.
http://users.iems.nwu.edu/~jrbirge//html/dholmes/StoProIntro.html
http://stoprog.org/
10/03/201110 [email protected]
-
7/25/2019 m Co i Program Acionm Ate Matic A
11/22
Definicin de Objetivos Lineales
Objetivos Simples Minimizar el valor absoluto
Minimizar el Mximo (o Maximizar el Mnimo)
Objetivos de Ratio
j
ji
jij
xb
xaMax
1
j
jjxbt
1j
jj wb
txwjj
exdj
jj
0
etwd
j
jj
jjj waMax
10/03/201111 [email protected]
Min x y
j
ijjxaMini
Max
-
7/25/2019 m Co i Program Acionm Ate Matic A
12/22
Programacin Multiobjetivo y Objetivos No
Optimizables
Mltiples Objetivos Combinacin Lineal de Objetivos:
Programacin Multinivel. Goal Programming
Soluciones No-Dominadas.Optimos de Pareto.
Objetivos no optimizables: Por ejemplo Sobrevivir
min 3 :
. . 2 1.1* 2
. . 1 1.01* 1
.
Obj
s t Obj Cota
s t Obj Cota
s t El resto de restricciones
10/03/201112 [email protected]
min 1 2 3
.
OBJ Obj Obj Obj
s t El resto de restricciones
-
7/25/2019 m Co i Program Acionm Ate Matic A
13/22
Restricciones segn su relacin con la
realidad.
Restriccionesdecapacidad
Disponibilidaddemateriaprima
Limitaciones en la demanda del mercado Continuidad o Balance
Restricciones de Calidad.
Restricciones Lgicas
10/03/201113 [email protected]
-
7/25/2019 m Co i Program Acionm Ate Matic A
14/22
Linealizando relaciones Lgicas.
10/03/[email protected]
1 j jj
a x b bMMxaj
jj
1j jj
a x b j jj
a x m b
1j j
j
a x b ( )j jj
a x m b
1 j jj
a x b j jj
a x m m b
1j jj
a x b
j j
j
a x M b
1j jj a x b
( )
j jj
a x M b
-
7/25/2019 m Co i Program Acionm Ate Matic A
15/22
Restricciones segn su relacin con
otras restricciones.
Restricciones Duras y Blandas
Restricciones Conflictivas
Restricciones Redundantes (precio sombra nulo)
Cotas Simples y Generalizadas.
Restricciones de Rango.
bxaj
jj buxaj
jj
10/03/201115 [email protected]
-
7/25/2019 m Co i Program Acionm Ate Matic A
16/22
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 yde Q=50 unidades/semana.
Los dos productos requieren de una misma pieza central, la Materia Prima de la cual vale a20 la unidad. Para fabricar la pieza central hacen falta 15 minutos del recurso B y 5 minutosdel recurso C. Para fabricar el componente 1 del producto P hace falta materia prima porvalor de 20/unidad, 15 minutos del recurso A y 10 minutos del recurso C. Al ensamblar lapieza 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 Bdonde est 15 minutos. Finalmente es ensamblado por el recurso D en 5 minutos. El mestiene 20 das de 8 horas. Los gastos totales son 3600/semana Cual es el mejor plan de produccin para la empresa? Qu beneficio le aporta?
Cul es el valor de una hora ms de cada recurso productivo?
Establecer un objetivo que pretenda maximizar el ratio beneficio entre horas totales de trabajo. Establecer un objetivo que pretenda
Cmo incorporar limitaciones en la disponibilidad de materia prima?
Cmo incorporar un nmero indefinido de productos al modelo?
10/03/[email protected]
-
7/25/2019 m Co i Program Acionm Ate Matic A
17/22
Problemas de Programacin Lineal
Una compaa fabrica dos modelos de sombrero: Bae yViz. La fabricacin de los sombreros se realiza en lassecciones de moldeado, pintura y montaje. La fabricacinde cada modelo Bae requiere 2 horas de moldeado, 3 depintura y una de montaje. La fabricacin del modelo Viz
requiere tres horas de moldeado, 2 de pintura y una demontaje. Las secciones de moldeado y pintura disponen,cada una, de un mximo de 1.500 horas cada mes, y la demontaje de 600.Si el modelo Bae se vende a 10 y elmodelo Viz a 12 qu cantidad de sombreros de cada
tipo ha de fabricar para maximizar el beneficio mensual?
10/03/201117 [email protected]
-
7/25/2019 m Co i Program Acionm Ate Matic A
18/22
Problemas de Programacin Lineal
Una persona tiene 5.000 para invertir en dos tipos deacciones A y B. El tipo A tiene bastante riesgo con uninters anual del 10% y el tipo B es bastante seguro conun inters anual del 7%. Decide invertir como mximo2.000 en A y como mnimo 1.000 en B, e invertir en
A por lo menos tanto como en B. Cmo deber invertirsus 5.000 para maximizar sus intereses anuales?
10/03/201118 [email protected]
-
7/25/2019 m Co i Program Acionm Ate Matic A
19/22
Problemas de Programacin Lineal
Imaginemos que las necesidades semanales mnimas deuna persona en protenas, hidratos de carbono y grasasson 10, 9, 12 unidades respectivamente. Supongamos quedebemos obtener un preparado con esa composicinmnima mezclando los productos A y B cuyos contenidos
por kilogramo son los que se indican en la tabla Cuntoskilogramos de cada producto debern comprarsesemanalmente para que el costo de preparar la dieta seamnimo?
Protenas Hidratos Grasas Coste(kg)
Producto A 2 5 2 600
Producto B 3 1 3 400
10/03/2011 [email protected]
-
7/25/2019 m Co i Program Acionm Ate Matic A
20/22
Problemas de Programacin Lineal
Una empresa fabrica 7 productos distintos, para los que utiliza 5 tipos deMquinas (Fresas(4), Tornos(2), Sierras(3), Soldadoras(1) yRectificadoras(1)). Aunque la cantidad de ellas puede variar a lo largo deltiempo.
Tambin vara el nmero de das en cada uno de los meses Se trabaja 16horas al da y no es posible utilizar horas extras.
Cada producto utiliza cada mquina durante una cierta cantidad de tiempo.Cada unidad de producto aporta un determinado beneficio.
La demanda de cada producto es variable segn los meses, cmo tambinlo son el nmero de das laborables en cada uno de ellos. Consideramos unhorizonte de planificacin de 6 meses.
Inicialmente no se dispone de stock de ningn producto, y el nmero total
de unidades al final de cada mes almacenadas est limitado a 400 unidades.El coste de almacn de cada unidad que quede al final de mes es 0.5
10/03/201120 [email protected]
-
7/25/2019 m Co i Program Acionm Ate Matic A
21/22
Mezcla de Productos
Una empresa con tres secciones productivas (tornos(3), fresas(2),Montaje (8 montadores por turno)) fabrica 5 productos distintos 6das a la semana, 2 turnos de 8 horas al da.
Los beneficios de los productos, y la necesidad en horas de cadarecurso, se expresa en la siguiente tabla
PR1 PR2 PR3 PR4 PR5
Beneficio unit. 550 600 350 400 200
Requerimientos
Torno 12 20 25 15
Fresa 10 8 16
Montaje 20 20 20 20 20
10/03/201121 [email protected]
-
7/25/2019 m Co i Program Acionm Ate Matic A
22/22
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)