3108616 Definiciones Basicas en Programacion Lineal
-
Upload
carlos-martinez -
Category
Documents
-
view
241 -
download
0
Transcript of 3108616 Definiciones Basicas en Programacion Lineal
8/4/2019 3108616 Definiciones Basicas en Programacion Lineal
http://slidepdf.com/reader/full/3108616-definiciones-basicas-en-programacion-lineal 1/23
Definiciones básicas en Definiciones básicas en
Programación lineal Programación lineal M.Sc. Jorge E. Hernández H
26/05/081
8/4/2019 3108616 Definiciones Basicas en Programacion Lineal
http://slidepdf.com/reader/full/3108616-definiciones-basicas-en-programacion-lineal 2/23
Contenido.Contenido.
1. Variables de decisión 2. Función Objetivo 3. Restricciones 4. Región Factible. 5. Soluciones Factibles. 6. Propiedades.
7. Solución gráfica. 8. Análisis de Sensibilidad.
26/05/082
8/4/2019 3108616 Definiciones Basicas en Programacion Lineal
http://slidepdf.com/reader/full/3108616-definiciones-basicas-en-programacion-lineal 3/23
1. Variables de decisión.1. Variables de decisión.
Es lo que se trata dedeterminar, y para locual se requiere unadecisión.
Generalmente sedesignan con letrassubindizadas. Cadavariable debe
representar unacantidad quecorresponda con unamisma unidad demedida.
26/05/083
8/4/2019 3108616 Definiciones Basicas en Programacion Lineal
http://slidepdf.com/reader/full/3108616-definiciones-basicas-en-programacion-lineal 4/23
2. Función Objetivo.2. Función Objetivo.
El objetivo es lo quese quiere maximizaro minimizar. En el
caso de laprogramación linealestá expresado comouna función lineal.
26/05/084
1 2 1 1 2 2( , ) Z f x x a x a x
8/4/2019 3108616 Definiciones Basicas en Programacion Lineal
http://slidepdf.com/reader/full/3108616-definiciones-basicas-en-programacion-lineal 5/23
3. Restricciones.3. Restricciones.
Representan loslímites del escenariode la situación
planteada. Semuestran por mediode desigualdades detipo lineal. El sistema
completo muestrauna región del plano.
26/05/085
8/4/2019 3108616 Definiciones Basicas en Programacion Lineal
http://slidepdf.com/reader/full/3108616-definiciones-basicas-en-programacion-lineal 6/23
4. Región Factible.4. Región Factible.
Es precisamente laregión determinadapor el sistema de
restricciones de tipolineal. Es un conjuntode puntos cuyascoordenadas
satisfacen lasrestricciones delproblema.
La región estádeterminada por losejes cartesianos y lasrectas.
26/05/086
8/4/2019 3108616 Definiciones Basicas en Programacion Lineal
http://slidepdf.com/reader/full/3108616-definiciones-basicas-en-programacion-lineal 7/23
4.1 Región Factible no acotada.4.1 Región Factible no acotada.
No acotadas:
Una región es no
acotada si no sepuede encerrar enun círculo.Generalmente se
piensa que elproblema está malplanteado.
26/05/087
8/4/2019 3108616 Definiciones Basicas en Programacion Lineal
http://slidepdf.com/reader/full/3108616-definiciones-basicas-en-programacion-lineal 8/23
4.2 Región Factible acotada.4.2 Región Factible acotada.
Acotada:
Una región es
acotada si se puedeencerrar en uncírculo.
26/05/088
8/4/2019 3108616 Definiciones Basicas en Programacion Lineal
http://slidepdf.com/reader/full/3108616-definiciones-basicas-en-programacion-lineal 9/23
5. Soluciones Factibles.5. Soluciones Factibles.
Cualquier solucióndentro de la regiónfactible se denomina
solución factible, esdecir cualquier puntodentro de la regiónfactible determina
valores numéricospara las variablesque satisfacen lasrestricciones.
26/05/089
8/4/2019 3108616 Definiciones Basicas en Programacion Lineal
http://slidepdf.com/reader/full/3108616-definiciones-basicas-en-programacion-lineal 10/23
5.1 Solución Factible Optima.5.1 Solución Factible Optima.
Entre todas lassoluciones factibles,buscamos aquella
que maximice ominimice la funciónobjetivo, además deque satisfaga las
restriccionesimpuestas.
26/05/0810
8/4/2019 3108616 Definiciones Basicas en Programacion Lineal
http://slidepdf.com/reader/full/3108616-definiciones-basicas-en-programacion-lineal 11/23
6. Propiedades.6. Propiedades.
Proporcionalidad.
La contribución de
cada variable a lafunción objetivo ocualquier restriccióndebe estar en
proporción directacon los coeficientes oparámetros
Aditividad.
La contribución total
de las variables dedecisión a la funciónobjetivo o a lasrestricciones debe
estar expresada ensumas o restas.
26/05/0811
.a x Z ax by
8/4/2019 3108616 Definiciones Basicas en Programacion Lineal
http://slidepdf.com/reader/full/3108616-definiciones-basicas-en-programacion-lineal 12/23
7. Solución gráfica.7. Solución gráfica.
26/05/0812
8/4/2019 3108616 Definiciones Basicas en Programacion Lineal
http://slidepdf.com/reader/full/3108616-definiciones-basicas-en-programacion-lineal 13/23
8. Análisis de Sensibilidad.8. Análisis de Sensibilidad.
Es un estudio que sehace para conocerque tanto pueden
variar loscoeficientes de lafunción objetivo y losparámetros de las
restricciones, sinalterar el valoróptimo encontrado.
26/05/0813
8/4/2019 3108616 Definiciones Basicas en Programacion Lineal
http://slidepdf.com/reader/full/3108616-definiciones-basicas-en-programacion-lineal 14/23
8.1 Análisis de Sensibilidad.8.1 Análisis de Sensibilidad.
En el ejemplo de laclase anteriorencontramos el
siguiente gráfico,donde pudimosevaluar que lafunción objetivo
alcanza su máximoen el vértice (2,6).
26/05/0814
1 23000 5000 Z x x
8/4/2019 3108616 Definiciones Basicas en Programacion Lineal
http://slidepdf.com/reader/full/3108616-definiciones-basicas-en-programacion-lineal 15/23
8.2 Análisis de Sensibilidad.8.2 Análisis de Sensibilidad.
Grafiquemos la rectaobtenida de la funciónobjetivo, dándole a Z elvalor máximo encontrado:
Nótese que la rectasegmentada tiene unainclinación que permaneceentre los límitesestablecidos por las rectasde color rojo y verde.
26/05/0815
1 2
3000 5000 36000 x x
8/4/2019 3108616 Definiciones Basicas en Programacion Lineal
http://slidepdf.com/reader/full/3108616-definiciones-basicas-en-programacion-lineal 16/23
8.3 Análisis de Sensibilidad.8.3 Análisis de Sensibilidad. Esto se puede establecer
de la siguiente manera:
La pendiente de la rectasolución (pendiente -0.6)está entre los valores de lapendiente de la recta
horizontal (pendiente 0) yla pendiente de la rectaroja (pendiente -1.5).
Esto quiere decir que
26/05/0816
cualquier modificación a los
coeficientes de la funciónobjetivo no deben cambiar la
pendiente fuera del intervalo
establecido entre las rectas que
pasan por el punto óptimo.
8/4/2019 3108616 Definiciones Basicas en Programacion Lineal
http://slidepdf.com/reader/full/3108616-definiciones-basicas-en-programacion-lineal 17/23
8.4 Análisis de Sensibilidad.8.4 Análisis de Sensibilidad.
¿Qué pasa simodificamos ladisponibilidad, esdecir, si modificamos
los valores del ladoderecho de lasrestricciones?
Identificamos las
rectas quedeterminan el puntoóptimo:
26/05/0817
2 6 x
1 23 2 18 x x
8/4/2019 3108616 Definiciones Basicas en Programacion Lineal
http://slidepdf.com/reader/full/3108616-definiciones-basicas-en-programacion-lineal 18/23
8.5 Análisis de Sensibilidad.8.5 Análisis de Sensibilidad.
Observamos,manteniendo ladisponibilidad de larecta en 6, es posible
desplazar la rectadesde el punto (0,6)hasta el punto (4,6),evaluando la rectaen esos puntosobtenemos
y
26/05/0818
3.0 2.6 12
3.4 2.6 24
8/4/2019 3108616 Definiciones Basicas en Programacion Lineal
http://slidepdf.com/reader/full/3108616-definiciones-basicas-en-programacion-lineal 19/23
8.6 Análisis de Sensibilidad8.6 Análisis de Sensibilidad
En otras palabras, ladisponibilidad de laplanta 3 puede variarentre 12 y 24 horas.
Caso similar ocurre sidejamos ladisponibilidad de elrecurso de la planta
3 fijo en 18.Entonces, podemosmover la rectacorrespondiente a la
planta 1I desde (4,3)hasta 0,9
26/05/0819
8/4/2019 3108616 Definiciones Basicas en Programacion Lineal
http://slidepdf.com/reader/full/3108616-definiciones-basicas-en-programacion-lineal 20/23
8.7 Análisis de Sensibilidad.8.7 Análisis de Sensibilidad.
Esto nos conduce aobservar que ladisponibilidad de laplanta 1I puede ser
modificada entre 3 y9 horas.
Hay otro aspecto de
interés para elanálisis desensibilidad.
Valor por unidad deun recurso:
Tasa de cambioTasa de cambio
del valor de ladel valor de lafunción objetivofunción objetivocon respecto a loscon respecto a loscambios en lacambios en la
disponibilidad dedisponibilidad delos recursos.los recursos.
26/05/0820
8/4/2019 3108616 Definiciones Basicas en Programacion Lineal
http://slidepdf.com/reader/full/3108616-definiciones-basicas-en-programacion-lineal 21/23
8.8 Análisis de Sensibilidad.8.8 Análisis de Sensibilidad.
Se consigue usandola siguienteexpresión:
En nuestro caso,encontremos y3: los
puntos consideradosfueron (0,6) y (4,6),con lo que alsustituirlos en Z
obtenemos
para (0,6):
para (4,6)
de esta manera,cambios en Z =12000
26/05/0821
Cambios en Z
Cambios en el recursoi y
i
1 23000 5000 Z x x
3000.0 5000.6 30000
3000.4 5000.6 42000
8/4/2019 3108616 Definiciones Basicas en Programacion Lineal
http://slidepdf.com/reader/full/3108616-definiciones-basicas-en-programacion-lineal 22/23
8.9 Análisis de Sensibilidad.8.9 Análisis de Sensibilidad.
Los cambios en elrecurso 3 ya sonconocidos:
24 – 12 = 12
Luego, el valor porunidad de recurso
correspondiente a laplanta 3 es
Similarmenteestudiamos elrecurso 1I. Loslímites del recursooscilan entre 3 y 9, loque nos da uncambio de 6. Y elcambio en la funciónobjetivo es de 18, así que el valor porunidad de recursocorrespondiente a laplanta II es
26/05/0822
3
120001000
12 y
2
180003000
6 y
8/4/2019 3108616 Definiciones Basicas en Programacion Lineal
http://slidepdf.com/reader/full/3108616-definiciones-basicas-en-programacion-lineal 23/23
Fin de la presentación.Fin de la presentación.
Gracias por su atención.
26/05/0823