¡La universidad para todos!

¡La Universidad para todos!

Programación Lineal

Tema: Método Gráfico

Docente: Chambergo García Alejandro Oscar

Escuela Profesional Periodo académico: 2018-1

INGENIERÍA DE SISTEMAS E INFORMÁTICA Semestre: 4
Unidad: 1
¡La universidad para todos!

Método Gráfico
 ¡La universidad para todos!

METODOS ALGORITMICOS DE SOLUCION PARA MODELOS DE PL

I. Método Gráfico (Geométrico)

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.
Región Factible. 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.
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
3
 ¡La universidad para todos!

Espacio solución de una ecuación

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 )

Ejemplo: 50 X1 + 100 X2 = 500 10

El conjunto solución son los puntos Región
de la recta que intercepta a los ejes Factible
0,5 5
del plano cartesiano en los puntos:
( 500/ 50, 0) y ( 0, 500 / 100)
( 10,0 ) ( 0,5 ) 0 5 10
10,0 4
 ¡La universidad para todos!

Espacio solución de una inecuación

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.

Ejemplo: 50 X1 + 100 X2 <= 500 10

1. Graficar la frontera (ecuación)
2. Elegir un pto.prueba [ejm. ( 0,0)]
3.Probar si satisface ó no la inecuación 0,5 5
Región
Pto. prueba (0,0) satisface la inecuación Factible
El espacio solución es el semiplano 0 5 10
que contiene al pto. prueba (0,0) Pto.prueba (0,0) 10,0
5
 ¡La universidad para todos!

Ejemplo: 7 X1 - 7 X2 <= 14 V X1,X2 >= 0 4

a) 7 X1 - 7 X2 = 14 Región
2 Factible
( 2 , 0 ) ( 0 , -2 )

b) pto. prueba ( 0 , 0) pp (0,0) 0

7 (0) - 7 (0) <= 14 2 4
e.s. : semiplano que 2, 0
contiene al pto. (0 , 0)
0, -2 -2

Ejemplo: 2 X2 >= 10 V X1,X2 >= 0

a) 2 X2 = 10 10
Región
recta // a X1, pasa ( 0 ,5 ) Factible
0, 5 5
b) pto. prueba ( 0 , 0)
2 (0) >= 10
e.s. : semiplano que pp (0,0) 0
NO contiene al pto. (0,0) 5 10 6
 ¡La universidad para todos!

Caso. Inca S.A

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
7
 ¡La universidad para todos!

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
- coeficientes de contribución
C1 = contribución a la utilidad de un estabilizador EL = S/.20
C2 = contribución a la utilidad de un estabilizador EP = S/.30
- modelo matemático de la FO
Z = C1 X1 + C2 X2 Z = 20 X1 + 30 X2
b. Restricciones
capacidad-línea-EL: X1 und. <= 60 und.
capacidad-línea-EP: X2 und. <= 50 und.
disponibilidad-hrs-labor: (1hr.)X1 +(2 hrs.)X2 <= 120 hrs.
8
 ¡La universidad para todos!

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”
9
 ¡La universidad para todos!

Máx. Z = 20 X1 + 30 X2 Región Factible para caso : Inca SA

s.a : X1 <= 60
X2 <= 50
X1 + 2 X2 <= 120 R3) X1 + 2 X2 <= 120
X1, X2 >= 0 a) X1 + 2 X2 = 120
( 120 , 0 ) ( 0 , 60 )
R1) X1 <= 60 b) pto. prueba ( 0 , 0)
a) X1 = 60 (0) + 2 (0) <= 120
recta // a X2, pasa ( 60 ,0) e.s. : semiplano que
b) pto. prueba ( 0 , 0) contiene al pto. (0 , 0)
(0) <= 60
e.s. : semiplano que 100
contiene al pto. (0,0)
R2) X2 <= 50
0, 60
a) X2 = 50
0, 50 50
recta // a X1, pasa ( 0 ,50)
b) pto. prueba ( 0 , 0) Región
(0) <= 50 Factible
pp (0,0) 0
e.s. : semiplano que 50 100
contiene al pto. (0,0) 60, 0 120, 0
 ¡La universidad para todos!

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.
11
 ¡La universidad para todos!

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.

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).
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.

12
 ¡La universidad para todos!

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 100

Z = 20 X1 + 30 X2 = 900
( 45 ,0) ( 0 ,30) RF= ABCDE
FO
b) Contorno prueba B C
50 Pto.extremo
por punto ( 0, 0) D solución óptima
Z = 20(0) + 30(0) = 0 0, 30
perjudica el Objetivo, 0 E
desplazamiento opuesto A 60 100
al contorno prueba 45, 0

Valor Optimo en el pto. D (R1 R3)

R1) X1 = 60 SO X1 = 60
R3) X1 + 2 X2 = 120 ; X2 = ( 120 - X1) / 2 X2 = 30

VO = 20 (60) + 30 (30) = 1200 + 900 VO = 2100 13

 ¡La universidad para todos!

Interpretación de resultados del modelo para caso : Inca SA

X1 = 60 ensamblar 60 estabilizadores livianos

X2 = 30 ensamblar 30 estabilizadores pesados
Z = 2100 utilidad máxima $2,100

Restricciones

Capacidad-línea-El : X1 <= 60
60 = 60
Se utiliza la capacidad total de la línea de ensamble EL
Capacidad-línea-EP : X2 <= 50
30 < 50 50 - 30 = 20
Queda una capacidad ociosa de 20 und.en línea ensamble EP
Disponibilidad-hrs-labor : 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.
14
 ¡La universidad para todos!

Caso: El instituto del Deporte

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.
15
 ¡La universidad para todos!

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
- coeficientes de contribución
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
- modelo matemático de la FO
Z = c1 X1 + c2 X2
Z = 1.0 X1 + 1.5 X2
16
 ¡La universidad para todos!

b. Restricciones
req-minerales ( 50u / onz) ( X1 onz) + ( 100u / onz) ( X2 onz) >= 500u
req.proteínas (200u / onz) ( X1 onz) + ( 125u / onz) ( X2 onz) >= 1,000u
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
17
 ¡La universidad para todos!

Mín. Z = 1.0 X1 + 1.5 X2 Solución por método geométrico:

s.a : 50 X1 + 100 X2 >= 500 Inst. Peruano de Deportes
200 X1 + 125 X2 >= 1,000
100 X1 + 100 X2 >= 750 R3) 100 X1 + 100 X2 >= 750
X1, X2 >= 0 a) 100 X1 + 100 X2 = 750
( 7.5 , 0 ) ( 0 ,7.5 )
R1) 50 X1 + 100 X2 >= 500 b) pto. prueba ( 0 , 0)
a) 50 X1 + 100 X2 = 500 (0) + (0) >= 750
( 10 ,0) ( 0 ,5) e.s. : semiplano que NO
b) pto. prueba ( 0 , 0) contiene al pto. (0 , 0)
(0) + (0) >= 500
e.s. : semiplano que NO 10
contiene al pto. (0,0) 0,8
R2) 200 X1 + 125 X2 >= 1,000 0,7.5
a) 200 X1 + 125 X2 = 1,000 Región
0, 5 5
( 5 ,0) ( 0 ,8) Factible
b) pto. prueba ( 0 , 0)
(0) + (0) >= 1,000 pp (0,0) 0
e.s. : semiplano que NO 5 18 10
contiene al pto. (0,0) 5,0 7.5, 0 10,0
 ¡La universidad para todos!

Determinación de la Solución Optima (SO) y el Valor Optimo (VO) para: IPD

Min Z = 1.0 X1 + 1.5 X2

RF= ..ABCD...
a) Grafo de un contorno FO No acotada

Z = 1.0 X1 + 1.5 X2 = 15 0, 10 10
( 15 ,0) ( 0 ,10) A

b) Contorno prueba
por punto ( 0, 0) B
Z = 1.0 (0) + 1.5 (0) = 0 5

cumple el Objetivo, C
desplazamiento hacia 0
al contorno prueba 5 D 10 15, 0

Valor Optimo en el pto. C(R1 R3)

R1) 50X1 + 100X2 = 500 SO X1 = 5
R3) 100X1 + 100X2 = 750 X2 = 2.5
VO = 1.0 ( 5) + 1.5 (2.5) = 8.75 VO = 8.75 19
 ¡La universidad para todos!

Interpretación de resultados del modelo para caso : IPD

El suplemento alimenticio debe obtenerse mezclando:

X1 = 5 5 onz. de suplemento alimenticio S1
X2 = 2.5 2.5 onz. de suplemento alimenticio S2
Z = 8.75 costo del suplemento obtenido $8.75

Restricciones
Requerimiento de minerales : 50 X1 + 100 X2 >= 500
50( 5) + 100( 2.5) = 500
Se satisface exactamente el requerimiento
Requerimiento de proteínas : 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.
Requerimiento de hidratos : 100 X1 + 100 X2 >= 750
100( 5) + 100(2.5) = 750
Se satisface exactamente el requerimiento 20
 ¡La universidad para todos!

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.

21
 ¡La universidad para todos!

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.

22
 ¡La universidad para todos!

Horas necesarias para

producir una unidad
MP4 TV Horas
Departamento X1 X2 disponibles
Electrónica 4 3 240

Montaje 2 1 100
Beneficio Unitario 7 5

23
 ¡La universidad para todos!

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
24
 ¡La universidad para todos!

X2
Restricción A:
4X1 + 3X2 = 240
100
Número de Televisores

80 X1=0, X2=80

60 Restricción A

40

20
X1=60, X2=0
0 20 40 60 80 100 X1 25
Número de MP4
 ¡La universidad para todos!

X2
Restricción B:
2X1 + 1X2 = 100
100 X1=0, X2=100
Número de Televisores

80

60 Restricción B

40

20
X1=50, X2=0
0 20 40 60 80 100 X1 26
Número de MP4
 ¡La universidad para todos!

X2
Restricción B:

100 X1=0, X2=100

Número de Televisores

80

60

40 Restricción A
Conjunto
de
20 soluciones
factibles X1=50, X2=0
0 20 40 60 80 100 X1 27
Número de MP4
 ¡La universidad para todos!

X2 A medida que me alejo

aumenta el beneficio

100
350$=7X1 + 5X2
Número de Televisores

80
280$=7X1 + 5X2
60
210$=7X1 + 5X2
40
400$=7X1 + 5X2
20

0 20 40 60 80 100 X1 28
Número de MP4
 ¡La universidad para todos!

X2

100
La línea de máximo beneficio pasa
2
Número de Televisores

por este punto X1=30, X2=40, se

80 denominará Punto Óptimo

60

40 3

20

1
0 20 40 4 60 80 100 X1 29
Número de MP4
 ¡La universidad para todos!

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.

30
 ¡La universidad para todos!

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.

31
 ¡La universidad para todos!

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.
32
¡La universidad para todos!

¡Gracias!