0B81_0NmqiwCfM2o0cXBpZHR0Zms - Anahí Mónaco

Vista previa del material en texto

Método SIMPLEX
Su introducción a través de un ejemplo
0 x2x1,
2 x2 
1 x2x1- 
6 x22 x1
24 x24 x16
: 
x4 x5 z 21
≥
≤
≤+
≤⋅+
≤⋅+⋅
⋅+⋅=
tosubject
Maximize
Método SIMPLEX
Su introducción a través de un ejemplo
0 x2x1,
2 x2 
1 x2x1- 
6 x22 x1
24 x24 x16
: 
x4 x5 z 21
≥
≤
≤+
≤⋅+
≤⋅+⋅
⋅+⋅=
tosubject
Maximize
0 s4 s3, s2, s1, x2,x1,
2 s4 x2 
1 s3 x2x1- 
6 s2 x22 x1
24 s1 x24 x16
: 
s40 s30 s20 s10 x4 x5 z 21
≥
=+
=++
=+⋅+
=+⋅+⋅
⋅+⋅+⋅+⋅+⋅+⋅=
tosubject
Maximize
0 s0 - s0- s0 - s0 -x4 -x5 -z
 
s0 s0 s0 s0 x4 x5 z
43211
432121
=⋅⋅⋅⋅⋅⋅
↓
⋅+⋅+⋅+⋅+⋅+⋅=
Reescribir la función objetivo a la siguiente forma:
2 s x 
1 s xx- 
6 s x2 x
24 s x4 x6 
0 s0 -s0- s0 - s0 -x4 - x5 - z
42
321
221
121
432121
=+
=++
=+⋅+
=+⋅+⋅
=⋅⋅⋅⋅⋅⋅
Por consiguiente:
2 s x 
1 s xx- 
6 s x2 x
24 s x4 x6 
0 s0 -s0- s0 - s0 -x4 - x5 - z
42
321
221
121
432121
=+
=++
=+⋅+
=+⋅+⋅
=⋅⋅⋅⋅⋅⋅
El problema puede ser escrito de la forma indicada en la Tabla 1. Esta forma se denomina canónica y se 
caracteriza porque existe una variable con coef. igual a 1 en cada restricción y esa misma variable aparece en 
las restantes restricciones con coeficiente 0. Si el lado derecho de las restricciones es positivo, se puede 
obtener una solución básica factible por inspección.
Por simple inspección, haciendo X1 = X2 = 0 (Variables No Básicas) se obtiene 
z=0, s1=24, s2=6, s3=1, s4=2 (Variables básicas). Ésta es la primera Solución Básica Factible del problema.
Verificación del Optimo:
Verificar si existe una forma de mejorar FO. Si la sbf no es óptima se debe buscar una sbf adyacente que mejore 
la FO. Debemos determinar la Variable No Básica (V.N.B.) que incrementa más la FO manteniendo el resto de las 
V.N.B. en 0. 
Reescribiendo la FO: Z = 5 X1 + 4 X2 resulta que X1 es la V.N.B. que produce el mayor aumento de la FO.
Ahora, ¿Qué variable debe salir?. 
Tabla 1 Variable Básica
Fila 0 Z -5 X1 -4 X2 = 0 Z = 0 
Fila 1 6 X1 +4 X2 + S1 =24 S1 = 24
Fila 2 X1 + 2 X2 + S2 = 6 S2 = 6 
Fila 3 - X1 + X2 + S3 = 1 S3 = 1
Fila 4 X2 + S4 = 2 S4 = 2
• 1.- Calcular la relación entre el valor del lado derecho de cada restricción (columna “Var. Básica”) y el 
valor del coeficiente de esa restricción que está debajo la variable entrante.
• 2.- Identificar la mínima relación no negativa. La variable básica que muestre esa particularidad es la 
variable saliente. Condición de factibilidad. En este caso es s1.
• 3.- Asignar a la variable entrante x1 el valor de la mínima relación no negativa calculado en (2)
TABLA 2 Var. Básica
Fila 0 Z -5 X1 -4 X2 = 0 Z = 0
Fila 1 6 X1 +4 X2 + S1 =24 S1 = 24 24/6 = 4
Fila 2 X1 + 2 X2 + S2 = 6 S2 = 6 6/1 = 6 
Fila 3 - X1 + X2 + S3 = 1 S3 = 1 1/(-1)= -1 
Fila 4 X2 + S4 = 2 S4 = 2 2/0
Cálculo de la Nueva S.B.F. Para hacer que X1 sea la V.B en la Fila 1 se debe emplear operaciones fila elementales 
para conseguir que X1 tenga coeficiente 1 en dicha fila y 0 en las restantes (Método por reducción). 
Paso 1: Se crea un coeficiente 1 para X1 en la fila 1 multiplicando la fila completa por (1/6). La fila resultante es:
X1 + 4/6 X2 + 1/6 S1 =24/6
Paso 2: Se crea un coef. =0 para X1 en todas las filas restantes. Por ej. para la fila 0 basta multiplicar por 5 la fila 1 y 
sumarla a la fila 0 actual, resultando: Z – 0X1 - 2/3X2 + 5/6 S1=20. Procediendo de la misma manera con las filas
restantes se obtiene la Tabla 3
TABLA 3 Var. Básica
Fila 0 Z -2/3 X2 + 5/6 S1 = 20 Z = 20
Fila 1 X1 +2/3 X2 + 1/6 S1 = 4 X1 = 4 24/6 = 4
Fila 2 + 4/3 X2 -1/6 S1 + S2 = 2 S2 = 2 6/1 = 6 
Fila 3 + 5/3 X2 + 1/6 S1 + S3 = 5 S3 = 5 1/(-1)= -1 
Fila 4 X2 + S4 = 2 S4 = 2 2/0
Verificación del Optimo: Z = 20 + 2/3 X2 – 5/6 S1, se observa que X2 produce un amento de la FO
• Ahora, ¿Qué variable debe salir y con qué valor debe ingresar X2?. 
Cálculo de la Nueva S.B.F. Para hacer que X2 sea la V.B en la Fila 2 se debe emplear operaciones fila elementales 
para conseguir que X2 tenga coeficiente 1 en dicha fila y 0 en las restantes. 
Paso 1: Se crea un coeficiente 1 para X2 en la fila 2 multiplicando la fila completa por (3/4). La fila resultante es:
X2 -1/8 S1 + 3/4 S2 =3/2
Paso 2: Se crean coeficientes 0 para X2 en todas las filas restantes. Por ej. para la fila 0 basta multiplicar por 2/3 la fila 
2 y restarla a la fila 0 actual, resultando: Z – 0X1 - 0 X2 + 3/4 S1 + 1/2 S2 =21. Procediendo para las filas restantes:
TABLA 4 Var. Básica
Fila 0 Z -2/3 X2 + 5/6 S1 = 20 Z = 20
Fila 1 X1 +2/3 X2 + 1/6 S1 = 4 X1 = 4 4/(2/3) = 6
Fila 2 + 4/3 X2 -1/6 S1 + S2 = 2 S2 = 2 2/(4/3) = 3/2
Fila 3 + 5/3 X2 + 1/6 S1 + S3 = 5 S3 = 5 5/(5/3)= 3 
Fila 4 X2 + S4 = 2 S4 = 2 2/1 = 2
TABLA 
5
Var. Básica
Fila 0 Z + 3/4S1 +1/2 S2 = 21 Z = 21
Fila 1 X1 + 1/4 S1 -1/2 S2 = 3 X1 = 3
Fila 2 X2 -1/8 S1 + 3/4 S2 = 3/2 X2 = 3/2
Fila 3 + 3/8 S1 - 5/4 S2 + S3 = 5/2 S3 = 5/2
Fila 4 1/8 S1 -3/4 S2 + S4 = 1/ 2 S4 = 1/2
Condición de Optimo: Z = 21 -3/2 S1 -1/2 S2 , no hay manera de mejorar el valor de la FO.
La solución óptima al problema resulta: X1 = 3, X2 = 3/2, S3 = 5/2, S4 = ¼, con valor en Z = 21
¿Por qué esa relación determina la variable saliente y el valor de la entrante?
Esas relaciones son las intercepciones de las restricciones con el eje de la variable entrante (aquí el eje x1).
El valor de x1 debe incrementarse hasta 4 en el vértice B, que es la intercepción no-negativa más pequeña. 
Un incremento de x1 mayor a 4 (más allá del vértice B) es infactible.
En B, la variable básica actual s1 asociada con la rest1 (filas1 del tableau) asume el valor 0 y se convierte 
en la variable saliente (su valor anterior era 24).
-1 0 1 2 3 4 5 6
0
2
4
6
x2=0
x1=0
C
B
1/-1=-1 6/1=6
rest 4
s4=0
rest 3
s3=0
rest 2
s2=0
x2
x1
6x1 + 4 x2 + s1 = 24 (rest 1)
x1 + 2 x2 + s2 = 6 (rest 2)
-x1 + x2 + s3 =1 (rest 3)
x2 + s4 =2 (rest 4)
x1, x2, s2, s3 >= 0 
rest 1
s1=0
24/6=4
A
región 
factible
Coeficiente de Costo de Oportunidad
2 s x 
1 s xx- 
6 s x2 x
24 s x4 x6 
0 s0 -s0- s0 - s0 -x4 - x5 - z
42
321
221
121
432121
=+
=++
=+⋅+
=+⋅+⋅
=⋅⋅⋅⋅⋅⋅Retomando el problema anterior:
TABLA 1 X1 X2 S1 S2 S3 S4
Base V.B Cj 5 4 0 0 0 0 bi
S1 0 6 4 1 0 0 0 24
S2 0 1 2 0 1 0 0 6
S3 0 -1 1 0 0 1 0 1
S4 0 0 1 0 0 0 1 2
E.I.j
E.D.j – E.I.j
Columnas no básicas: El aumento de la FO será apoyado mediante una interpretación física de las columnas no 
básicas de la Tabla. Entenderemos como columna no básica las que estén encabezadas por las V.N.B. Para el 
caso planteado en la Tabla 1 las V.N.B. son X1, X2 
Columna X1 = (6, 1, -1, 0) Columna X2 = (4, 2, 1, 1)
Para explicar la información específica relativa a dichas columnas, expresamos las ecuaciones presentes en la Tabla 
1, en la sig. forma y analicemos que ocurre cuando X1 (Var. No Básica) aumenta en 1 unidad manteniendo X2=0 :
S1 = 24 – 6 X1 – 4 X2 ……………….. S1 (var. Básica) disminuirá en 6 unidades (18) 
S2 = 6 – X1 – 2 X2 …….…………. S2 (var. Básica) disminuirá en 1 unidad (5)
S3 = 1 + X1 – X2 ……………….. S3 (var. Básica) aumentará en 1 unidad (2)
S4 = 2– X2 ……………….. S4 (var. Básica) = 0 (2) permanece inalterable.
Nótese que esa misma información está contenida en la columna 1 correspondiente a X1. Del mismo modo asignado 
una unidad a X2 (V.N.B.) y manteniendo a X1 en 0, obtenemos las modificaciones en las variables básicas (S1=20 
(4), S2=4 (2), S3=0 (1) , S4=1 (1) 
Los datos de las columnas de X1 y X2 muestran la cantidad en la que los valores actuales de las variables básicas 
deben ser reducidos (o aumentados) cuando se “produce” otra unidad de X1 (ó X2) manteniendo a X2 (ó X1) en 
cero. 
Coeficientes de sustitución y su relación con la FO.
La FO está definida como z = 5 X1 + 4 X2 + 0 S1 + 0 S2 + 0 S3 + 0 S4
Supongamos que X1 (V.N.B.) aumenta una unidad y X2 = 0. Hemos visto que esto inducirá cambios en las 
variables básicas. En otras palabras, los valores de las variables básicas se reducirán (aumentarán) en los 
coeficientes de la columna X1, precisamente en los valores (6, 1, -1, 0). 
Si se pasa por alto el “efecto directo” sobre la FO del aumento de la V.N.B (X1, -5*X1-) y se considera solo el 
“efecto indirecto” de los cambios inducidos en las Variables Básicas (S1, S2, S3, S4), la FO se verá reducida en:
E.I.(X1) = (Columna X1 * Coeficientes Básicos) = 0 (6) + 0 (1) – 0 * (1) + 0 (0) = 0.
Así, en este caso, los cambios resultantes en las V.B. no afectarán a la FO. Por el contrario, analizando el efecto 
directo de X1 sobre la FO, se puede observar una ganancia potencial de $5. 
Costo de Oportunidad de la V.N.B. “j” [E.D. – E.I.] = [Ganancia Potencial – Reducción Potencial]
(E.D.) – (E.I.)
Retomando la Tabla 1, procedemos a calcular los E.I. y los valores de (E.D. – E.I.)
TABLA 1 X1 X2 S1 S2 S3 S4
Base Cj 5 4 0 0 0 0 bi
S1 0 6 4 1 0 0 0 24
S2 0 1 2 0 1 0 0 6
S3 0 -1 1 0 0 1 0 1
S4 0 0 1 0 0 0 1 2
E.I (Indirecto) 0 0 0 0 0 0
[E.D. – E.I.] (Neto) 5 4 0 0 0 0
Habiendo calculado los costos de oportunidad [E.D.(j)-E.I.(j)] para cada una de las variables no básicas se debe 
escoger aquella V.N.B. que reporte el máximo valor de costo de oportunidad (si se trata de un problema de 
maximización). 
TABLA 2 X1 X2 S1 S2 S3 S4
Base Cj 5 4 0 0 0 0 bi
S1 0 6 4 1 0 0 0 24
S2 0 1 2 0 1 0 0 6
S3 0 -1 1 0 0 1 0 1
S4 0 0 1 0 0 0 1 2
E.I.(j) 0 0 0 0 0 0 0
[E.D.(j)-E.I.(j)] 5 4 0 0 0 0
TABLA 3 X1 X2 S1 S2 S3 S4
Base Cj 5 4 0 0 0 0 bi
S1 0 6 4 1 0 0 0 24 24/6=4
S2 0 1 2 0 1 0 0 6 6/1=6
S3 0 -1 1 0 0 1 0 1 1/(-1)
S4 0 0 1 0 0 0 1 2 2/0
E.I.(j) 0 0 0 0 0 0 0
[E.D.(j)-E.I.(j)] 5 4 0 0 0 0
¿Por qué esa relación determina la variable saliente y el valor de la entrante?
Esas relaciones son las intercepciones de las restricciones con el eje de la variable entrante (aquí el eje x1).
El valor de x1 debe incrementarse hasta 4 en el vértice B, que es la intercepción no-negativa más pequeña. 
Un incremento de x1 mayor a 4 (más allá del vértice B) es infactible.
En B, la variable básica actual s1 asociada con la rest1 (filas1 del tableau) asume el valor 0 y se convierte 
en la variable saliente (su valor anterior era 24).
-1 0 1 2 3 4 5 6
0
2
4
6
x2=0
x1=0
C
B
1/-1=-1 6/1=6
rest 4
s4=0
rest 3
s3=0
rest 2
s2=0
x2
x1
6x1 + 4 x2 + s1 = 24 (rest 1)
x1 + 2 x2 + s2 = 6 (rest 2)
-x1 + x2 + s3 =1 (rest 3)
x2 + s4 =2 (rest 4)
x1, x2, s2, s3 >= 0 
rest 1
s1=0
24/6=4
A
región 
factible
TABLA 4 X1 X2 S1 S2 S3 S4
Base Cj 5 4 0 0 0 0 bi
X1 5 1 2/3 1/6 0 0 0 4 4/(2/3)=6
S2 0 0 4/3 -1/6 1 0 0 2 2/(4/3)=3/2
S3 0 0 5/3 1/6 0 1 0 5 5/(5/3)=3
S4 0 0 1 0 0 0 1 2 2/1
E.I.(j) 5 10/3 5/6 0 0 0 20
[E.D.(j)-E.I.(j)] 0 4–10/3=2/3 -5/6 0 0 0
TABLA 5 X1 X2 S1 S2 S3 S4
Base Cj 5 4 0 0 0 0 bi
X1 5 1 0 1/4 -1/2 0 0 3
X2 4 0 1 -1/8 3/4 0 0 3/2
S3 0 0 0 -1/24 -5/4 1 0 5/2
S4 0 0 1 0 3/4 0 1 1/2
E.I.(j) 0 0 0 0 0 0 15+6=21
[E.D.(j)-E.I.(j)] 5 4 0 0 0 0
X1 = 4 – [2/3 X2 + 1/6 S1] , el ingreso de X2=1 produce una disminución de 2/3 en X1 
S2 = 2 - [4/3 X2 - 1/6 S1] el ingreso de X2=1 produce una disminución de 4/3 en S2 
S3 = 5 – [5/3 X2 + 1/6 S1] el ingreso de X2=1 produce una disminución de 5/3 en S3 
S4 = 2 – [X2] , el ingreso de X2=1 produce una disminución de 1 en S4 
E.I.(X2) = (2/3) * 5 +(4/3) * 0 + (5/3) *0 + (1) * 0 = 10/3
E.I.(S1) = (1/6) * 5 - (1/6) * 0 + (1/6) *0 + (0) * 0 = 5/6
Generalización del Método Simplex. Inclusión de restricciones del tipo ≥ e =. 
El Método Simplex busca óptimos adyacentes a partir de una solución básica factible. Hasta aquí, se 
propusieron restricciones del tipo ≤.
Minimice Z = 2 X1 + 3 X2 (FO)
Sujeto a:
0,5 X1 + 0,25 X2 ≤ 4 (a) 
X1 + 3 X2 ≥ 20 (b) 
X1 + X2 = 10 (c)
Su versión estándar:
Minimice Z = 2 X1 + 3 X2 (FO)
Sujeto a:
0,5 X1 + 0,25 X2 + S1 = 4 (a) 
X1 + 3 X2 - E2 = 20 (b) (B)
X1 + X2 = 10 (c)
Buscando una S.B.F a partir de (B) con X1 = X2 = 0, obtendríamos S1 = 4 en la restric. (a), E2 = -
20 en la restric. (b) mientras que la restric. (c) sería infactible. 
Variables artificiales
Minimice Z = 2 X1 + 3 X2 + M A2 + M A3 (FO)
Sujeto a:
0,5 X1 + 0,25 X2 + S1 = 4 (a) 
X1 + 3 X2 - E2 + A2 = 20 (b) 
X1 + X2 + A3 = 10 (c)
S.B.I.F = [S1=4, A2=20, A3=10]
TABLA X1 X2 S1 E2 A2 A3
Base Cj 2 3 0 0 M M bi bi/aij
S1 0 0,5 0,25 1 0 0 0 4
A2 M 1 3 0 -1 1 0 20
A3 M 1 1 0 0 0 1 10
E.I.(j) 2M 4M 0 -M M M 30 M
[E.D.(j)-E.I.(j)] 2 – 2M 3 - 4M 0 M 0 0
TABLA X1 X2 S1 E2 A2 A3
Base Cj 2 3 0 0 M M bi bi/aij
S1 0 0,5 0,25 1 0 0 0 4 4/0,25 = 16
A2 M 1 3 0 -1 1 0 20 20/3
A3 M 1 1 0 0 0 1 10 10/1
E.I.(j) 2M 4M 0 -M M M 30 M
[E.D.(j)-E.I.(j)] 2 – 2M 3 - 4M 0 M 0 0
TABLA X1 X2 S1 E2 A2 A3
Base Cj 2 3 0 0 M M bi
bi/aij
S1 0 5/12 0 1 1/12 -1/12 0 7/3
X2 3 1/3 1 0 -1/3 1/3 0 20/3
A3 M 2/3 0 0 1/3 -1/3 1 10/3
E.I.(j) 1+2/3M 3 0 1M+1/3M M M 20+10/3M
[E.D.(j)-E.I.(j)] 1-2/3M 0 0 1-1/3M 4/3M-1 0
TABLA X1 X2 S1 E2 A2 A3
Base Cj 5 4 0 0 0 0 bi bi/aij
S1 0 5/12 0 1 1/12 -1/12 0 7/3 28/5
X2 3 1/3 1 0 -1/3 1/3 0 20/3 20
A3 M 2/3 0 0 1/3 -1/3 1 10/3 5
E.I.(j) 1+2/3M 3 0 -M M M 20+10/3M
[E.D.(j)-E.I.(j)] 1-2/3M 0 0 1-1/3M 4/3M-1 0
TABLA X1 X2 S1 E2 A2 A3
Base Cj 2 3 0 0 M M bi
S1 0 0 0 1 -1/8 1/8 -5/8 1/4
X2 3 0 1 0 -1/2 1/2 -1/2 5
X1 2 1 0 0 1/2 -1/2 3/2 5
E.I.(j) 2 3 0 -1/2 ½ M 25
[E.D.(j)-E.I.(j)] 0 0 0 1/2 M -1/2 0
- No existen costos de oportunidad negativos.
- Variables Artificiales A2 y A3 no pertenecen a la Base.
- Solución Optima: X1 = X2 = 5, S1=1/4 con FO = 25
Casos Especiales
1. Soluciones Alternativas1. Soluciones Alternativas
Max. Z = 60 X1 + 35 X2 + 20 X3
Sujeto a: 8 X1 + 6 X2 + X3 + S1 = 48
4 X1 + 2 X2 + 1,5 X3 + S2 = 20
2 X1 + 1,5 X2 + 0,5 X3 + S3 = 48
X2 + S4 = 5
TABLA X1 X2 X3 S1 S2 S3 S4
Base Cj 60 35 20 0 0 0 0 bi
S1 0 8 6 1 1 0 0 0 48
S2 0 4 2 1,5 0 1 0 0 20
S3 0 2 1,5 0,5 0 0 1 0 48
S4 0 0 1 0 0 0 0 1 5
E.I.(j) 0 0 0 0 0 0 0 0
[E.D.(j)-E.I.(j)] 60 35 20 0 0 0 0
Aplicando el M. S. después de dos iteraciones, se obtiene:
TABLA X1 X2 X3 S1 S2 S3 S4
Base Cj 60 35 20 0 0 0 0 bi
S1 0 0 -2 0 1 2 -8 0 24
X3 20 0 -2 1 0 2 -4 0 8
X1 60 1 1,25 0 0 -0,5 1,5 0 2
S4 0 0 1 0 0 0 0 1 5
E.I.(j) 60 35 20 0 10 10 0 280
[E.D.(j)-E.I.(j)] 0 0 0 0 -10 -10 0
Observando la Tabla se observa que existe una V.N.B. (X2) que posee un costo de oportunidad nulo. Esto indica 
que su incorporación a la base no mejora la FO, sin embargo su ingreso modificara los valores de las restantes 
Var. Bá sicas que se mantengan en la base. Recordar que si ingresa X2 debe salir una Variable Básica de la 
Base. 
Realizando una iteración adicional para el ingreso de X2 se obtiene la siguiente Tabla:
TABLA X1 X2 X3 S1 S2 S3 S4
Base Cj 60 35 20 0 0 0 0 bi
S1 0 1,6 0 0 1 1,2 -5,6 0 27,2
X3 20 1,6 0 1 0 1,2 -1,6 0 11,2
X2 35 0,8 1 0 0 -0,4 1,2 0 1,6
S4 0 -0,8 0 0 0 0,4 -1,2 1 3,4
E.I.(j) 60 35 20 0 10 10 0 280
[E.D.(j)-E.I.(j)] 0 0 0 0 -10 -10 0
Punto Extremo 1 = [x1, x2, x3] = [2,0, 8] 
Punto Extremo 2 = [x1, x2, x3] = [0, 1.6, 11.2]
Luego, uniendo ambos extremos mediante una ecuación paramétrica de una recta es posible incluir todas las 
soluciones al problema:
( )
10
2,32,11
6,16,1
2
2,11
6,1
0
1
8
0
2
3X
2X
1X
≤α≤
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
α−
α−
α
=
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
α−+
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
α=
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎣
⎡
Resumiendo, siempre que exista un Cj-Zj =0 para una V.N.B. puede que exista una solución alternativa si esa 
variable es capaz de ingresar a la base. En el caso que NO existan costo de oportunidad nulos para variables 
no básicas se puede asegurar que la solución es óptima. 
2. LP No Acotados
En algunos PL pueden que existan puntos de la región factible en el que los valores de la FO sean 
arbitrariamente grandes (max.) o arbitrariamente pequenos (min.)
Max. z = 36 X1 + 30 X2 – 3 X3 – 4 X4
Sujeto a: X1 + X2 – X3 ≤ 5
6 X1 +5X2-X4 ≤ 10
X1, X2, X3, X4 ≥ 0
Estandarizando
Max. z = 36 X1 + 30 X2 – 3 X3 – 4 X4
X1 + X2 – X3 + S1 = 5
6 X1 +5X2-X4 + S2 = 10
X1, X2, X3, X4, S1, S2 ≥ 0
Se construye la Tabla
TABLA X1 X2 X3 X4 S1 S2
Base Cj 36 30 -3 -4 0 0 bi bi/aij
S1 0 1 1 -1 0 1 0 5 5/1 = 5
S2 0 6 5 0 -1 0 1 10 10/6 = 5/3
E.I.(j) 0 0 0 0 0 0 0
[E.D.(j)-E.I.(j)] 36 30 -3 -4 0 0
TABLA X1 X2 X3 X4 S1 S2
Base Cj 36 30 -3 -4 0 0 bi bi/aij
X4 -4 0 1 -6 1 6 -1 20 -- ?
X1 36 1 1 -1 0 1 0 5 -- ?
E.I.(j) 36 32 -12 -4 12 4 100
[E.D.(j)-E.I.(j)] 0 -2 9 0 -12 -4
TABLA X1 X2 X3 X4 S1 S2
Base Cj 36 30 -3 -4 0 0 bi bi/aij
S1 0 0 1/6 -1 1/6 1 -1/6 10/3 20
X1 36 1 5/6 0 -1/6 0 1/6 5/3 --
E.I.(j) 36 30 0 -6 0 6 0
[E.D.(j)-E.I.(j)] 0 0 -3 2 0 -6
Al intentar incorporar X3 a la base se encuentra que no existe un valor máximo. Se puede entender la situación 
escribiendo las dos restricciones que muestra la Tabla:
X1 = 5 + X3 y X4 = 20 + 6 X3
Luego, cualquier incremento positivo en X3 (a la cual solo se le exige que sea positiva) provoca un aumento en 
X1 y X4, por lo tanto sin importar el valor que adopte X3 las variables X1 y X4 seguiran siendo positivas. 
Resumiendo, un problema de max. no está acotado si existe una variable no básica con costo de oportunidad 
positivo sin que exista un límite para el valor máximo que pueda adoptar. Esto ocurre cuando una variable tiene 
precio sombra positivo y coeficientes negativos en todas las restricciones que aparezca dicha variable. 
3. Solución Infactible
Sea el Problema: Min. Z = 2 X1 + 3 X2 + M a1 + Ma2
Sujeto a: ½ X1 + ¼ X2 + S1 = 4 (a)
X1 + 3 X2 – e2 + a2 = 36 (b)
X1 + X2 + a3 = 10 (c)
Tabla 1. Primera iteración del Tableu 
TABLA X1 X2 S1 E2 A2 A3 bi
Base Cj 2 3 0 0 M M
S1 0 ½ ¼ 1 0 0 0 4 16
A2 M 1 3 0 -1 1 0 36 12
A3 M 1 1 0 0 0 1 10 10
E.I.(j) 2M 4M 0 - M M M 46M
[E.D.(j)-E.I.(j)] 2 – 2M 3 – 4M 0 M 0 0
Tabla 2. Tableu Final
TABLA X1 X2 S1 E2 A2 A3 bi
Base Cj 2 3 0 0 M M
S1 0 ¼ 0 1 0 0 - ¼ 3/2 
A2 M -2 0 0 -1 1 -3 6
X2 3 1 1 0 0 0 1 10
E.I.(j) 3–2M 3 0 - M M 3–3M 6M+30
[E.D.(j)-E.I.(j)] 2M–1 0 0 M 0 4M–3
La solución resultaría:
S1 = 3/2
A2 = 6
X2 = 10
A3 = 0
E2 = 0
X1 = 0
Como la base óptima contiene una variable artificial la solución resulta infactible. En este caso 
no existe región factible para el problema tal como se ilustra en la sig. Fig.. En resumen, cuando 
existe una variable artificial con valor positivo en el “óptimo”, el PL no posee región factible.
(a)
(b)
(c)
x2
x1
	Método SIMPLEX��Su introducción a través de un ejemplo
	Método SIMPLEX��Su introducción a través de un ejemplo