investigacion de operaciones

investigación de operaciones i

Módulo 2
Solución de problemas de PL
•
•
•

Solución gráfica
Casos especiales
Simplex gráfico

Información importante
• Parcial 1: Marzo 1
– Abuchar Correa a Muñoz Morera: M8 – 102
(aquí!)
– Ortega Muñoz a Zuluaga Meneses:M3-113

• Clase de hoy: Entra en el quiz (10%)
– Miércoles 13 de marzo

Solución gráfica de PL
• Las soluciones de unproblema de P.L son
puntos en el espacio n-dimensional
(n variables)
• Cuando el problema tiene sólo 2 variables de
decisión y por lo tanto está en sólo 2
dimensiones, puede utilizarse un método
gráfico para resolverlo

Recordemos
• Ejemplo prototipo (Windor Glass)
Maximizar Z = 3X1 + 5X2
Sujeto a:
X1
2X2
3X1 + 2X2
X1 , X2

≤ 4
≤ 12
≤ 18
≥0

Graficando las restricciones:
x210
9
8
7
6
5
4
3
2
1
0

X1 = 4 (planta 1)

X2 = 6
(planta2)
Región Factible

3X1+ 2X2 = 18 (planta 3)

1 2 3 4 5 6 7 8 9 10

x1

5-5

Definiciones
• Restricción frontera:
– Recta que marca el límite de lo que permite la
restricción correspondiente

• Región factible
– Conjunto de puntos en los cuales todas las
restricciones se cumplen

Definiciones
•Solución óptima
– Punto dentro de la región factible que maximiza
el valor de la F. O. (Z = 3X1 + 5X2)
– Para hallar la solución óptima, puede utilizarse un
procedimiento por prueba y error.
• Por ejemplo, puede elegirse el valor Z = 15 = 3X1 + 5X2

Recta de isoutilidad

Gráficamente, se tiene:
x2

10
9
8
7
6
5
4
3
2
1
0

X1 = 4 (planta 1)

X2 = 6
(planta2)

Z = 15 = 3X1 +5X23X1+ 2X2 = 18 (planta 3)

1 2 3 4 5 6 7 8 9 10

x1

5-8

Cómo hallar la solución óptima
• Se desplaza la función objetivo paralelamente
a sí misma en la dirección en que aumenta su
valor, hasta que toque el último punto de la
región factible, antes de abandonarla.
• OBSERVACIÓN:
– ¿Qué pasa si el problema es de minimización?
– Cuando el problema es de minimización, la recta
debedesplazarse en la dirección en que Z decrece.

(2,6)
x2

10
9
8
7
6
5
4
3
2
1
0

R2

Z = 36
R3

1 2 3 4 5 6 7 8 9 10

x1

R1
5-10

Conclusiones
• Cuál es la solución óptima?
– X1 = 2 , X2 = 6
– Es decir, se deben fabricar los productos 1 y 2 a unas
tasas de 2 y 6 lotes semanales, respectivamente.

• Cuál es el valor de la función objetivo?
– Z = 3X1 + 5X2,Reemplazando la solución óptima
Z(2,6)=36
– Es decir, la ganancia total máxima en estas
condiciones es de US$ 36000 por semana

Clasificación de las soluciones
• ¡OJO!: Solución NO significa la respuesta final
• Solución factible: Solución que cumple con todas
las restricciones funcionales y de signo.
• Solución no factible: Solución para la que al
menos una restricción no se cumple.
•Solución Básica o Solución en un vértice: Punto
donde se interceptan las restricciones de frontera

Ejemplo – tipo de soluciones
• Solución Básica Factible:
– Solución factible en un vértice (FEV): Punto Extremo:
• Solución que se encuentra en uno de los vértices de la
región factible.
• Ejemplo: (0,6); (0,0); (4,0); (4,3); (2,6)

• Solución Básica No Factible:
– Solución no factible enun vértice:
• Punto que se encuentra en uno de los vértices que no
corresponden a la región factible.
• Ejemplo: (0,9); (4,6); (6,0)

soluciones factibles

x2
10
9
8
7
6
5
4
3
2
1
0

(2,6)
solución factible
(4,6)
óptima
solución no factible en
un vértice

R2
(8,3)
solución no factible

R3
1 2 3 4 5 6 7 8 9 10
R1

x1
5-14

En el ejemplo de la Wyndor
(0,9)(0,6)

x2

10
9
8
7
6
5
4
3
2
1
0

(0,0)

X1=4
Planta 1

(2,6)
(4,6)
X2=6
Planta 2

(6,0)

(4,3)
3X1+2X2=18

Planta 3

1 2 3 4 5 6 7 8 9 10
(4,0)

x1
5-15

Gráficamente
x2
10
9
8
7
6
5
4
3
2

R1

Solución factible en un
vértice

R3

R2

Solución no factible en
un vértice

1
0

1

2

3

4

5

6

7

8

9

10...