clase5_solucion grafica

Universidad Nacional de Colombia
Sede Medellín

SOLUCIÓN DE PROBLEMAS DE P.L.
EL MÉTODO SIMPLEX
(Dantzig, 1947)

Clase # 5 SOLUCION GRAFICA
Ejemplo prototipo: La Wyndor Glass Co.
Introducción al Método Simplex
5-1

CONTENIDO
1. Solución gráfica
2. Ejemplo prototipo

3. Clasificación de las soluciones de P.L.
4. Casos Especiales
5. Introducción al Método Simplex
5-2

1. SOLUCIÓN GRÁFICA DE P.LCuando 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

Nota: Las soluciones de un problema de
P.L son puntos en el espacio n-dimensional
En (n variables)
5-3

2. EJEMPLO PROTOTIPO:

LA WYNDOR GLASS CORPORATION

Maximizar Z = 3X1 + 5X2
Sujeto a

X1

2X2

4
 12

3X1 + 2X2  18
X1 , X 2  0
5-4Graficando las restricciones:
x2

10
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:
Es la recta que marca el límite de lo que permite
la restricción correspondiente.

REGION FACTIBLE:
Conjunto de puntos en los
cuales todas las restricciones
se cumplen

5-6

Definición 2: 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
15 = 3X1 +5X2

Z=

Recta de isoutilidad
5-7

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 +5X2
3X1+ 2X2 = 18 (planta 3)

1 2 3 4 5 6 7 89 10

x1

5-8

Para 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:
Cuando el problema es de minimización, la
recta debe desplazarse en la dirección en que
Z decrece.
Veamos la siguiente gráfica
5-9

(2,6)
x2

10
9
8
7
6
5
4
32
1
0

R2

Z = 36
R3

1 2 3 4 5 6 7 8 9 10

x1

R1
5-10

CONCLUSIONES:
• La solución óptima es X1 = 2 , X2 = 6:
Se deben fabricar los productos 1 y 2 a
unas tasas de 2 y 6 lotes semanales,
respectivamente.

• Valor de la Función Objetivo:
Z = 3X1 + 5X2
Z(2,6) = 36
La ganancia total máxima en estas
condiciones es de US$ 36000 por semana.
5-11

3. CLASIFICACION DE LAS SOLUCIONES
(Estamosacostumbrados a que el término
solución signifique 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
5-12

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 en un 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)

5-13

soluciones factibles

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

(2,6)
soluciónfactible
(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
1
0

R1
Solución factible en un
vértice

R3

R2Solución no factible en
un vértice
1

2

3

4

5

6

7

8

9

10

x1
5-16

Soluciones factibles adyacentes:
En general, en un problema con n variables de
decisión, se puede decir que:
Dos soluciones factibles son adyacentes entre sí,
si comparten por lo menos n - 1 restricciones

Arista:
Segmento de recta que
soluciones FEV adyacentes.

conecta

2

5-17

FEV
x2
10

La arista es el segmento
de...