semana 3.2 metodo grafico.pdf
Post on 10-Apr-2016
24 Views
Preview:
TRANSCRIPT
CHAMBERGO GARCIA,
ALEJANDRO
INVESTIGACIÓN DE OPERACIONES I
Módulo: I Unidad: I Semana: 2
Método Gráfico
Orientaciones
Se requiere de su puntualidad al iniciar cada tutoría,
participación e integración a todas las actividades que
se realicen.
Es importante que usted realice y participe de todas las
actividades.
La participación en la clase y asistencia es fundamental
para su aprendizaje.
Visita el Blog del curso para que mandes tus
comentarios y también comentes las aportaciones de
tus compañeros.
Participa en el foro del curso
4
en general una ecuación o inecuación lineal de 2 variables
tiene un espacio solución en el plano cartesiano conformado por todos los
puntos con coordenadas (x1,x2) que satisfagan la ecuación ó inecuación.
METODOS ALGORITMICOS DE SOLUCION PARA MODELOS DE PL
I. Método Gráfico (Geométrico)
Región Factible.
Es la aplicación de los conceptos de la geometría, para relacionar gráfica-
mente los componentes de un modelo de PL como base para su solución.
El método es aplicable hasta para representaciones tridimensionales (ca-
cada variable es una dimensión). Para facilitar la comprensión de los con-
ceptos involucrados, aplicaremos el método a modelos bidimensionales.
Ya que, un modelo de PL puede contener m restricciones (<=, =, >=) el
espacio solución del conjunto (Región Factible) debe resultar de la inter-
sección de los espacios solución de cada una de las restricciones
5
Espacio solución de una ecuación
Ejemplo:
En un modelo de PL una restricción de igualdad, se representa por :
a1 X1 + a2 X2 = b
cuya pendiente es p = - (a1 / a2) , si a2 =/= 0 .
El conjunto solución son los puntos de la recta que intersecta a
los ejes del plano cartesiano en los ptos. ( b / a1, 0) y ( 0, b / a2)
si a2 = 0 entonces el conjunto solución son los puntos de la rec
ta paralela a X2 que pasa por el punto ( b / a1, 0 )
50 X1 + 100 X2 = 500
El conjunto solución son los puntos
de la recta que intercepta a los ejes
del plano cartesiano en los puntos:
( 500/ 50, 0) y ( 0, 500 / 100)
( 10,0 ) ( 0,5 ) 10
10
5
5 0 10,0
0,5
Región
Factible
6
Espacio solución de una inecuación
Ejemplo:
a1 X1 + a2 X2 <= ( ó >= ) b
El espacio solución de una inecuación es el conjunto de puntos que pertenecen a
de uno de los semiplanos cerrados, definidos por la ecuación : a1 X1 + a2 X2 = b
Una manera de determinar el medio plano solución, es graficar la frontera y probar
que: si un punto cualquiera del plano [ejm.( 0,0)] satisface la inecuación, entonces
el semiplano que lo contiene es el espacio solución, sino es el otro semiplano.
50 X1 + 100 X2 <= 500
1. Graficar la frontera (ecuación)
2. Elegir un pto.prueba [ejm. ( 0,0)]
3.Probar si satisface ó no la inecuación
10
10
5
5 0 10,0
0,5 Región
Factible
Pto.prueba (0,0)
Pto. prueba (0,0) satisface la inecuación
El espacio solución es el semiplano
que contiene al pto. prueba (0,0)
7
Ejemplo: 7 X1 - 7 X2 <= 14 V X1,X2 >= 0
b) pto. prueba ( 0 , 0)
7 (0) - 7 (0) <= 14
4
4
2
2 0
0, -2
Región
Factible
pp (0,0)
a) 7 X1 - 7 X2 = 14
( 2 , 0 ) ( 0 , -2 )
-2
2, 0 e.s. : semiplano que
contiene al pto. (0 , 0)
Ejemplo: 2 X2 >= 10 V X1,X2 >= 0
b) pto. prueba ( 0 , 0)
2 (0) >= 10
a) 2 X2 = 10
recta // a X1, pasa ( 0 ,5 )
e.s. : semiplano que
NO contiene al pto. (0,0) 10
10
5
5 0
Región
Factible
pp (0,0)
0, 5
8
IncaS.A ensambla dos tipos de estabilizadores para Pc’s, liviano y pesado
(EL y EP). Se cuenta con dos líneas de ensamble. La línea de ensamble de
EL tiene una capacidad de 60 und. por día y la línea de EP de 50 und.
Un EL requiere 1 hr. de labor y un EP 2 hrs. A lo mas 120 hrs labor están
disponibles para asignarse al ensamble de los 2 tipos de estabilizadores.
Si cada EL deja una utilidad de S/.20 y cada EP S/.30 ¿Cuál debe ser la
producción diaria, para obtener la mayor ganancia posible?
1- Objetivo Verbal. Maximizar las utilidades, determinando el número de
unidades a ensamblar de estabilizadores EL y EP
2- Restricciones verbal
capacidad-linea-EL: a lo mas 60 und. diarias
capacidad-linea-EP: como máximo 50 und.diarias.
disponibilidad-hrs-labor : a lo sumo 120 und. diarias
no negatividad : los valores de las variables deben ser no negativos
Caso. IncaS.A
9
3-.Transformando a definiciones matemáticas
a. FO
- variables de decisión
X1 = número de und. a ensamblar de estabilizadores EL
X2 = número de und. a ensamblar de estabilizadores EP
C1 = contribución a la utilidad de un estabilizador EL = S/.20
C2 = contribución a la utilidad de un estabilizador EP = S/.30
Z = C1 X1 + C2 X2 Z = 20 X1 + 30 X2
- coeficientes de contribución
- modelo matemático de la FO
b. Restricciones
capacidad-línea-EL:
capacidad-línea-EP:
disponibilidad-hrs-labor:
X1 und. <= 60 und.
X2 und. <= 50 und.
(1hr.)X1 +(2 hrs.)X2 <= 120 hrs.
10
4-.Construcción del modelo de PL
Máx. Z = 20 X1 + 30 X2
s.a : X1 <= 60
X2 <= 50
X1 + 2 X2 <= 120
X1, X2 >= 0
Podemos concluir que los modelos de PL están formados de dos partes
importantes una función Objetivo que debe ser optimizada y un conjunto
de restricciones que deben ser satisfechas.
Un modelo de PL ( modelo cuantitativo de decisión restringida ) se utiliza
para asignar “recursos” limitados de manera tal, que se logre un objetivo
de manera “óptima”
R1) X1 <= 60 a) X1 = 60
Región Factible para caso : Inca SA Máx. Z = 20 X1 + 30 X2
s.a : X1 <= 60
X2 <= 50
X1 + 2 X2 <= 120
X1, X2 >= 0
b) pto. prueba ( 0 , 0)
(0) <= 60
recta // a X2, pasa ( 60 ,0)
e.s. : semiplano que
contiene al pto. (0,0)
R2) X2 <= 50 a) X2 = 50
b) pto. prueba ( 0 , 0)
(0) <= 50
recta // a X1, pasa ( 0 ,50)
e.s. : semiplano que
contiene al pto. (0,0)
R3) X1 + 2 X2 <= 120
b) pto. prueba ( 0 , 0)
(0) + 2 (0) <= 120
a) X1 + 2 X2 = 120 ( 120 , 0 ) ( 0 , 60 )
e.s. : semiplano que
contiene al pto. (0 , 0)
100
100
50
50 0
0, 50
Región
Factible pp (0,0)
60, 0 120, 0
0, 60
12
Representación de la Función Objetivo en el espacio solución de un modelo PL
En el espacio bidimensional , la FO de un modelo de PL es de la forma:
c1 X1 + c2 X2 ; f(X1,X2)
Un contorno de esta función representa un conjunto de puntos ( X1,X2) que corres-
ponden a un valor constante de la función f(X1,X2) y representan una línea recta.
Cada punto del contorno evaluado en la función f(X1,X2) resulta en un valor
constante, en consecuencia, la línea contorno es denominada línea ISOCUANTA.
Si £ representa un dominio de valores para la función, entonces en la FO
c1 X1 + c2 X2 = £ , cada valor de £ es un contorno.
si c2 =/=0, variando el valor de £ , cada contorno obtenido tendrá la misma pendien-
te pero diferentes puntos de intersección en el plano. Eso implica que los contornos
son paralelos unos con otros, es entonces, posible pasar de una línea isocuanta a
otra por un deslizamiento paralelo en la dirección de incremento o decremento.
Si el objetivo es maximizar la línea ISOCUANTA se denomina de ISOUTILIDAD, si es
minimizar se denomina de ISOCOSTO.
13
La idea del desplazamiento, sugiere una manera para identificar el valor óptimo de
la función objetivo. Suponiendo que el objetivo es maximizar, entonces se debe
desplazar la línea de ISOUTILIDAD desde una posición inicial £0 en la dirección de
incrementar £ ( que es el valor total de la utilidad) hasta intersectar la RF en su (s)
punto(s) mas extremo(s) ( cuyos valores (X1,X2) producen el valor óptimo en la FO).
Dado que los valores de las variables de la FO, son limitados por las restricciones
cuya representación es una Región Factible, entonces son sólo significativos los
desplazamientos de la línea de ISOCUANTA que intersecten dicha Región Factible.
Una manera de determinar la dirección del desplazamiento, es graficar un contorno
(cualquiera) de la FO y luego evaluar el valor de la FO en otro contorno [ejm. el que
pasa por el pto( 0,0)] si este valor mejora la obtención del Objetivo la dirección del
desplazamiento es hacia ese contorno, sino es hacia el lado opuesto.
14
Determinación de la Solución Optima (SO) y el Valor Optimo (VO) para Inca
Máx. Z = 20 X1 + 30 X2
a) Grafo de un contorno
( 45 ,0) ( 0 ,30)
Z = 20 X1 + 30 X2 = 900
b) Contorno prueba
por punto ( 0, 0)
Z = 20(0) + 30(0) = 0
perjudica el Objetivo,
desplazamiento opuesto
al contorno prueba
100
100
50
60 0
RF= ABCDE FO
45, 0
0, 30
Pto.extremo
solución óptima
Valor Optimo en el pto. D (R1 R3)
A
B C
D
E
R1) X1 = 60
R3) X1 + 2 X2 = 120 ; X2 = ( 120 - X1) / 2
SO X1 = 60
X2 = 30
VO = 20 (60) + 30 (30) = 1200 + 900 VO = 2100
15
Interpretación de resultados del modelo para caso : Inca SA
X1 = 60
Z = 2100
X2 = 30
Restricciones
X1 <= 60
60 = 60
Se utiliza la capacidad total de la línea de ensamble EL
X2 <= 50
30 < 50 50 - 30 = 20
Queda una capacidad ociosa de 20 und.en línea ensamble EP
X1 + 2X2 <= 120
60 + 2( 30) = 120 120 - 120 = 0
Se utiliza la capacidad total de mano de obra
En una restricción <= la diferencia entre el ST y el primero se denomina HOLGURA.
ensamblar 60 estabilizadores livianos
ensamblar 30 estabilizadores pesados
utilidad máxima $2,100
Capacidad-línea-El :
Capacidad-línea-EP :
Disponibilidad-hrs-labor :
16
El instituto del Deporte, ha firmado un contrato ventajoso para comprar suple-
mentos alimenticios para los deportistas. Estos vienen en 2 presentaciones:
S1 cuyo precio es de $16 la libra( provee 50u de minerales,200u de proteínas y
100u de hidratos por onza) y S2 que cuesta $24 la lb ( provee 100u minerales,
125u de proteínas y 100u de hidratos por onza ). En base a estos 2 productos
se desea obtener un suplemento para la dieta de los atletas peruanos que pro-
vea como mínimo de 500u de minerales, 1000u de proteínas y 750u de hidratos
al menor costo posible.
Formular y construir el modelo para solucionar el problema.
1- Objetivo Verbal. Minimizar el costo del suplemento alimenticio que
cumpla con los requerimientos mínimos exigidos,
determinando el número de onzas a mezclar de los
productos S1 y S2.
Caso: El instituto del Deporte
17
2- Restricciones verbal
Requerimiento de minerales: debe proveer por lo menos 500u Requerimiento de proteínas : debe contener como mínimo 1,000u
Requerimiento de hidratos : debe tener al menos 750u no negatividad : los valores deben ser no negativos
3-.Transformando a definiciones matemáticas
a. FO - variables de decisión X1 = número de onzas de suplemento S1 a mezclar
X2 = número de onzas de suplemento S2 a mezclar
c1 = contribución al costo por onz de suplemento S1 = 16/16 = $1.0
c2 = contribución al costo por onz de suplemento S2 = 24/16 = $1.5
- coeficientes de contribución
Z = c1 X1 + c2 X2
Z = 1.0 X1 + 1.5 X2
- modelo matemático de la FO
18
( 50u / onz) ( X1 onz) + ( 100u / onz) ( X2 onz) >= 500u
(200u / onz) ( X1 onz) + ( 125u / onz) ( X2 onz) >= 1,000u
req-minerales
req.proteínas
req.-hidratos ( 100u / onz) ( X1 onz) + ( 100u / onz) ( X2 onz) >= 750u
4-.Construcción del modelo de PL
Mín. Z = 1.0 X1 + 1.5 X2
s.a : 50 X1 + 100 X2 >= 500
200 X1 + 125 X2 >= 1,000
100 X1 + 100 X2 >= 750
X1, X2 >= 0
b. Restricciones
19
R1) 50 X1 + 100 X2 >= 500 a) 50 X1 + 100 X2 = 500
Solución por método geométrico:
Inst. Peruano de Deportes
b) pto. prueba ( 0 , 0)
(0) + (0) >= 500
( 10 ,0) ( 0 ,5)
e.s. : semiplano que NO
contiene al pto. (0,0)
R2) 200 X1 + 125 X2 >= 1,000 a) 200 X1 + 125 X2 = 1,000
b) pto. prueba ( 0 , 0)
(0) + (0) >= 1,000
( 5 ,0) ( 0 ,8)
e.s. : semiplano que NO
contiene al pto. (0,0)
R3) 100 X1 + 100 X2 >= 750
b) pto. prueba ( 0 , 0)
(0) + (0) >= 750
a) 100 X1 + 100 X2 = 750 ( 7.5 , 0 ) ( 0 ,7.5 )
e.s. : semiplano que NO
contiene al pto. (0 , 0)
10
10
5
5 0
0, 5 Región
Factible
pp (0,0)
5,0 10,0 7.5, 0
Mín. Z = 1.0 X1 + 1.5 X2
s.a : 50 X1 + 100 X2 >= 500
200 X1 + 125 X2 >= 1,000
100 X1 + 100 X2 >= 750
X1, X2 >= 0
0,7.5 0,8
20
Determinación de la Solución Optima (SO) y el Valor Optimo (VO) para: IPD
Min Z = 1.0 X1 + 1.5 X2
a) Grafo de un contorno
( 15 ,0) ( 0 ,10)
Z = 1.0 X1 + 1.5 X2 = 15
b) Contorno prueba
por punto ( 0, 0)
Z = 1.0 (0) + 1.5 (0) = 0
cumple el Objetivo,
desplazamiento hacia
al contorno prueba
FO
Valor Optimo en el pto. C(R1 R3)
R1) 50X1 + 100X2 = 500 R3) 100X1 + 100X2 = 750
SO X1 = 5
X2 = 2.5
VO = 1.0 ( 5) + 1.5 (2.5) = 8.75 VO = 8.75
10
10
5
5 0
15, 0
0, 10 A
B
RF= ..ABCD...
No acotada
C
D
21
Interpretación de resultados del modelo para caso : IPD
El suplemento alimenticio debe obtenerse mezclando:
X1 = 5
Z = 8.75
X2 = 2.5
Restricciones
50 X1 + 100 X2 >= 500
50( 5) + 100( 2.5) = 500
Se satisface exactamente el requerimiento
200 X1 + 125 X2 >= 1,000
200( 5) + 125(2.5) >= 1,000
1,312.5 > 1,000
Se satisface el requerimiento con un exceso de 312.5 u.
100 X1 + 100 X2 >= 750
100( 5) + 100(2.5) = 750
Se satisface exactamente el requerimiento
5 onz. de suplemento alimenticio S1
2.5 onz. de suplemento alimenticio S2 costo del suplemento obtenido $8.75
Requerimiento de minerales :
Requerimiento de proteínas :
Requerimiento de hidratos :
22
Ejemplo
Shader Electronics fabrica 2 productos:
1. El MP4 Shader, un reproductor MP4 y
2. El Shader Watch TV, TV color del tamaño de un reloj de pulsera.
El proceso de fabricación de ambos productos se asemeja en que los
2 necesitan un cierto número de horas de trabajo en el departamento
de electrónica y un cierto número de horas de mano de obra en el
departamento de montaje.
Cada MP4 necesita 4 horas de trabajo en electrónica y 2 en montaje.
23
Cada TV necesita 3 horas de electrónica y 1 en montaje.
Durante el actual periodo se dispone de 240 horas en el
departamento de electrónica y 100 horas en el montaje.
Cada MP4 vendido supone un beneficio de $7 mientras
que para un TV el beneficio unitario es de $5.
Se quiere determinar la mejor combinación posible de MP4
y TVs que debe producir para alcanzar el máximo
beneficio.
24
Horas necesarias para
producir una unidad
Departamento
MP4
X1
TV
X2
Horas
disponibles
Electrónica 4 3 240
Montaje 2 1 100
Beneficio Unitario 7 5
25
Definir variables
X1= número de MP4 a producir
X2= número de televisores a producir
Función objetivo
Maximizar Beneficio = 7*X1 + 5*X2
Restricciones
4X1 + 3X2 240 (horas de trabajo en electrónica)
2X1 + 1X2 100 (horas de trabajo en montaje)
Rangos de existencia
X1 0
X2 0
26
X2
X1
Número de MP4
Nú
mero
de
Tel
evis
ore
s
100
80
60
40
20
0 20 40 60 80 100
X1=0, X2=80
X1=60, X2=0
Restricción A
Restricción A:
4X1 + 3X2 = 240
27
X2
X1 Número de MP4
Nú
mero
de
Tel
evis
ore
s
100
80
60
40
20
0 20 40 60 80 100
X1=0, X2=100
X1=50, X2=0
Restricción B
Restricción B:
2X1 + 1X2 = 100
28
X2
X1 Número de MP4
Nú
mero
de
Tel
evis
ore
s
100
80
60
40
20
0 20 40 60 80 100
X1=0, X2=100
X1=50, X2=0
Restricción A
Restricción B:
Conjunto
de
soluciones
factibles
29
X2
X1 Número de MP4
Nú
mero
de
Tel
evis
ore
s
100
80
60
40
20
0 20 40 60 80 100
400$=7X1 + 5X2
210$=7X1 + 5X2
280$=7X1 + 5X2
350$=7X1 + 5X2
A medida que me alejo
aumenta el beneficio
30
X2
X1
Número de MP4
Nú
mero
de
Tel
evis
ore
s
100
80
60
40
20
0 20 40 60 80 100
La línea de máximo beneficio pasa
por este punto X1=30, X2=40, se
denominará Punto Óptimo
2
1 4
3
31
Punto Óptimo:
Matemáticamente se calcula resolviendo el sistema de ecuaciones:
4X1 + 3X2 = 240 (restricción A)
2X1 + 1X2 = 100 (restricción B)
Multiplicando y sumando tenemos:
4X1 + 3X2 = 240
-4X1 - 2X2= -200
X2 = 40, Entonces X1 = 30 (reemplazando en
restricción A o B)
Reemplazando en la Función objetivo, el Beneficio mayor será:
7*30 + 5* 40 = U$ 410
Esto se logra produciendo X1=30 MP4 y X2= 40 televisores.
32
Problemas de Minimización
Kodak SA, fabrica dos tipos de líquidos de revelado de fotografía. El
primero un producto químico para el revelado en blanco y negro, tiene
un coste de producción de US $ 2,500 por tonelada. El segundo, un
producto químico para el revelado en color, cuesta 3,000$ por
tonelada.
Basándose en el nivel actual de inventario y los pedidos pendientes
de servir, el director de producción ha especificado que, para el
próximo mes, se deben producir al menos 30 TM de líquido para
revelado en blanco y negro, y 20 para el revelado color. Además el
director ha constatado la existencia de un stock de materia prima
altamente perecedero, necesario para los dos productos, que debe
utilizarse en los próximos 30 días. Con el objeto de no desperdiciar
una materia prima tan cara, Kodak debe producir al menos 60 TM de
líquido de revelado durante el próximo mes.
33
X1= N° de Tn producidas de líquido revelado blanco y negro
X2= N° de Tn producidas de líquido revelado color
F.O. Minimizar costos Z = 2500X1 + 3000X2
X1 30 (prod. Min. De liq. Rev. Blanco y negro)
X2 20 (prod. Mín. de liq. Rev. Color)
X1+X2 60 (prod. Mín. para no desperdiciar materia prima)
X1, X2 0 (condiciones de no negatividad)
Usar método gráfico.
En este caso existen dos vértices a(40,20) y b(30,30)
Para a: F.O. = 160,000$
Para b: F.O. = 165,000$
Por lo tanto el coste más barato se dá en el punto a, por lo que Kodak
SA deberá producir 40 Tn L.R. Blanco y negro y 20 Tn L.R.color.
GRACIAS
top related