Ingenieria de operaciones

INVESTIGACIÓN DE
OPERACIONES I

MÉTODO SIMPLEX
PARTE 3
OTRAS FORMAS

INVESTIGACIÓN DE OPERACIONES I

1.
2.
3.
4.

ROMPIMIENTO DE EMPATES
EN EL MÉTODO SIMPLEX
Empate de la variable básica entrante
Empate de la variable básica saliente
No hay variable básica que sale
Soluciones óptimas múltiples

INVESTIGACIÓN DE OPERACIONES I

1. Empate de la variable básica entranteEcuación (0):

Z = 3X1 + 3X2
Z - 3X1 - 3X2 = 0

X1 y X2 tienen el valor negativo más grande ,
¿ cuál escoger?
** Cualquiera de las 2, tarde o temprano se llegará
a la solución óptima. No hay manera de saber
con cual de las 2 se llegará más rápido al final.

INVESTIGACIÓN DE OPERACIONES I

2.

Empate de la variable básica saliente (DEGENERACIÓN)

Sucede cuando la prueba del cocientemínimo da dos
resultados iguales (2 números iguales como mínimos).
La que no se escogiera como variable saliente también
tomaría el valor de cero (a pesar de ser variable básica)
y se denominaría “variable degenerada”.
Lo que podría suceder es que se crearan “ciclos” sin
que Z cambie. No hay que preocuparse, es muy raro,
seleccionar cualquier variable como variable básica saliente.INVESTIGACIÓN DE OPERACIONES I
3.

No hay variable básica que sale: Z no acotada

Sucede cuando ninguna variable califica como variable básica
que sale. En la forma tabular sería el caso que todos los
coeficientes de la columna pivote (excluyendo el renglón 0) son
negativos o cero y por lo tanto no podemos seguir el paso 2 que
se inicia escogiendo los coeficientes mayores que cero.

Elmétodo simplex no podría continuar y se asumiría
que se cometió un error:
•
•
•

Modelo mal formulado
Faltan restricciones
Errores en los cálculos

INVESTIGACIÓN DE OPERACIONES I

4. Soluciones Óptimas Múltiples
Al encontrar una solución óptima siempre verificar si
existe en el renglón (0) una variable no básica que
tenga un valor de cero (0). Si esto sucede, se puede
encontrar por lomenos otra solución óptima mediante
iteraciones adicionales (cada vez se elige una variable no
básica con coeficiente cero como variable básica
entrante) .
Modificando la Función Objetivo del problema de la
Wyndor a Z = 3X1 + 2X2 se tendría:

INVESTIGACIÓN DE OPERACIONES I

FUNCIÓN OBJETIVO
Maximizar Z = 3X1 + 2X2
Sujeto a las siguientes RESTRICCIONES
(funcionales y de nonegatividad) :

X1  4
2X2  12
3X1 + 2X2  18
X1  0
X2  0
VARIABLES DE DECISIÓN: X1 y X2
En la segunda y tercera iteración (esta sería una
iteración adicional) tendríamos:

Soluciones Óptimas Múltiples
ITERACIÓN

Variable

Lado
Coeficiente de:
Ec.

Z

X1

X2

X3

X4

X5

derecho

Z
X1

(0)

1

0

0

0

0

0

18

(1)

0

1

0

1

0

0

4X4

(2)

0

0

0

3

1

-1

6

X2

2

básica

(3)

0

0

1

- 3/2

0

1/2

3

ES SOLUCIÓN ÓPTIMA: NINGÚN COEF EN (0) ES NEGATIVO.
HAY OTRAS SOLUCIONES ÓPTIMAS: X3 QUE ES NO BÁSICA EN ESA ITERACIÓN TIENE COEF = 0
EN LA ECUACIÓN (0)

Z
X1

1
0

0
1

0
0

0
0

0
- 1/3

1
1/3

18
2

X3

(2)

0

0

0

1

1/3

- 1/3

2X2

3

(0)
(1)
(3)

0

0

1

0

1/2

0

6

Si seguimos, regresamos a la iteración 2

X4

INVESTIGACIÓN DE OPERACIONES I

4. Soluciones Óptimas Múltiples
Hemos encontrado las 2 soluciones BF óptimas:
(4,3,0,6,0) y (2,6,2,0,0).
En este caso especial, la combinación de estas soluciones
nos proporcionan todas las demás soluciones que hay:
( X1,X2,X3,X4,X5 ) = w1(4,3,0,6,0) + w2 (2,6,2,0,0)
w1 + w2 = 1
w1 ≥ 0 w2 ≥ 0
Ejemplo: 0.5 (4,3,0,6,0) + 0.5 (2,6,2,0,0) = (3,4.5,1,3,0)
Esto se da porque los sumandos de la función objetivo
coinciden exactamente con los sumandos de la tercera
restricción funcional, VER GRÁFICA:

INVESTIGACIÓN DE OPERACIONES I

Z = 3X1 +2 X2

ADAPTACIÓN A OTRAS
FORMAS DEL MODELO
FORMA ESTÁNDAR
•
Maximizar Z
•...