Metodo-tableau-y-metodo-de-matrices

Vista previa del material en texto

Método tableau y método matricial
Investigación Operativa - Segundo Cuatrimestre 2018
Nazareno Faillace Mullen - Facundo Gutierrez
1. Método tableau
El método tableau (o método de tablas) es una manera alternativa al método de diccionarios para
resolver problemas lineales utilizando SIMPLEX. Naturalmente, ambos métodos son equivalentes
y, como veremos más adelante, cada diccionario puede traducirse a una tabla y viceversa.
Presentamos el procedimiento que lleva a cabo el método tableau con un ejemplo. Supongamos
que tenemos el siguiente problema lineal:
máx 5x1 + 4x2 + 3x3
s.a: 2x1 + 3x2 + x3 ≤ 5
4x1 + x2 + 2x3 ≤ 11
3x1 + 4x2 + 2x3 ≤ 8
x1, x2, x3 ≥ 0
Tal y como haćıamos con diccionarios, antes de comenzar hay que escribir el modelo en forma
estándar:
máx z = 5x1 + 4x2 + 3x3
s.a: 2x1 + 3x2 + x3 + w1 = 5
4x1 + x2 + 2x3 + w2 = 11
3x1 + 4x2 + 2x3 + w3 = 8
x1, x2, x3, w1, w2, w3 ≥ 0
Ahora bien, para conformar la primera tabla, veamos una modificación de la manera de escribir
las ecuaciones de nuestro primer diccionario:
2x1 + 3x2 + x3 + w1 = 5
4x1 + x2 + 2x3 + w2 = 11
3x1 + 4x2 + 2x3 + w3 = 8
−z + 5x1 + 4x2 + 3x3 = 0
Armamos la primera tabla considerando los coeficientes de las variables, los valores del lado derecho
de la igualdad y cuáles son las variables básicas de la solución inicial (en el ejemplo son w1, w2, w3):
2x1 + 3x2 + x3 + w1 = 5
4x1 + x2 + 2x3 + w2 = 11
3x1 + 4x2 + 2x3 + w3 = 8
−z + 5x1 + 4x2 + 3x3 = 0
↓
Base P x1 x2 x3 w1 w2 w3
w1 5 2 3 1 1 0 0
w2 11 4 1 2 0 1 0
w3 8 3 4 2 0 0 1
−z 0 5 4 3 0 0 0
1
Aśı queda conformada la tabla inicial:
Base P x1 x2 x3 w1 w2 w3
w1 5 2 3 1 1 0 0
w2 11 4 1 2 0 1 0
w3 8 3 4 2 0 0 1
−z 0 5 4 3 0 0 0
Paso 1. Examinar los números de la última fila correspondientes a las columnas de las variables.
Si todos son nulos o negativos, entonces se ha llegado a un óptimo. De lo contrario, elegimos la
columna que tenga al mayor número positivo (columna pivote), que representa a la variable que
va a entrar a la base. En el ejemplo, la columna del 5 es la comlumna pivote:
Base P x1 x2 x3 w1 w2 w3
w1 5 2 3 1 1 0 0
w2 11 4 1 2 0 1 0
w3 8 3 4 2 0 0 1
−z 0 5 4 3 0 0 0
Paso 2. Para cada valor r positivo de la columna pivote (salvo el último que corresponde al
coeficiente en z), hallar el valor correspondiente s de la columna P . La fila con la menor proporción
s
r será la fila pivote y corresponde a la variable que va a salir de la base. Si para todas las filas r
es negativo o cero, entonces el problema es no acotado. En nuestro ejemplo, para cada una de las
filas tenemos las siguientes proporciones:
Fila 1: r = 2, s = 5 ⇒ sr =
5
2
Fila 2: r = 4, s = 11 ⇒ sr =
11
4
Fila 1: r = 3, s = 8 ⇒ sr =
8
3
Como la menor proporción es la de la fila 1, esa será la fila pivote:
Base P x1 x2 x3 w1 w2 w3
w1 5 2 3 1 1 0 0
w2 11 4 1 2 0 1 0
w3 8 3 4 2 0 0 1
−z 0 5 4 3 0 0 0
Paso 3. Dividir cada elemento de la fila pivote por el número pivote (que es el que se encuentra en
la intersección de la fila y la comuna pivote). En nuestro ejemplo, el número pivote es 2:
Base P x1 x2 x3 w1 w2 w3
w1
5
2 1
3
2
1
2
1
2 0 0
w2 11 4 1 2 0 1 0
w3 8 3 4 2 0 0 1
−z 0 5 4 3 0 0 0
Paso 4. Utilizar la fila pivote para efectuar operaciones de filas de manera tal que la columna
pivote tenga todos ceros (salvo el número pivote). Añadir la variable entrante a las variables
básicasy eliminar a la variable saliente. En nuestro ejemplo habŕıa que llevar a cabo las siguientes
operaciones de filas:
Base P x1 x2 x3 w1 w2 w3
w1
5
2 1
3
2
1
2
1
2 0 0
w2 11 4 1 2 0 1 0
w3 8 3 4 2 0 0 1
−z 0 5 4 3 0 0 0
F2−4F1
F3−3F1
F4−5F1−−−−−→
Base P x1 x2 x3 w1 w2 w3
x1
5
2 1
3
2
1
2
1
2 0 0
w2 1 0 -5 0 -2 1 0
w3
1
2 0 −
1
2
1
2 −
3
2 0 1
−z − 252 0 −
7
2
1
2 −
5
2 0 0
2
Paso 5. Efectuamos el chequeo de optimalidad: ”¿Son todos los números de la última fila no
positivos? ” En este caso, no, por lo que debemos comenzar desde el Paso 1 con nuestra nueva
tabla.
Paso 1. Identificamos la columna pivote (x3 entrará a la base):
Base P x1 x2 x3 w1 w2 w3
x1
5
2 1
3
2
1
2
1
2 0 0
w2 1 0 -5 0 -2 1 0
w3
1
2 0 −
1
2
1
2 −
3
2 0 1
−z − 252 0 −
7
2
1
2 −
5
2 0 0
Paso 2. Identificamos la fila pivote. La fila 3 es la que presenta menor proporción sr , (w3 saldrá de
la base). Observar que, como para la segunda fila r ≤ 0, ignoramos la proporción correspondiente.
Base P x1 x2 x3 w1 w2 w3
x1
5
2 1
3
2
1
2
1
2 0 0
w2 1 0 -5 0 -2 1 0
w3
1
2 0 −
1
2
1
2 −
3
2 0 1
−z − 252 0 −
7
2
1
2 −
5
2 0 0
Paso 3. Dividir la fila pivote por el número pivote ( 12 ):
Base P x1 x2 x3 w1 w2 w3
x1
5
2 1
3
2
1
2
1
2 0 0
w2 1 0 -5 0 -2 1 0
w3 1 0 -1 1 -3 0 2
−z − 252 0 −
7
2
1
2 −
5
2 0 0
Paso 4. Efectuar operaciones de filas con respecto a la fila 3, de manera tal que en la columna
correspondiente a x3 hayan ceros salvo en la fila pivote:
Base P x1 x2 x3 w1 w2 w3
x1
5
2 1
3
2
1
2
1
2 0 0
w2 1 0 -5 0 -2 1 0
w3 1 0 -1 1 -3 0 2
−z − 252 0 −
7
2
1
2 −
5
2 0 0
F1− 12F3
F4− 32F3−−−−−→
Base P x1 x2 x3 w1 w2 w3
x1 2 1 2 0 2 0 -1
w2 1 0 -5 0 -2 1 0
x3 1 0 -1 1 -3 0 2
−z -13 0 -3 0 -1 0 -1
Paso 5. Chequear criterio de optimalidad. En este caso todos los números de la última fila son no
positivos, luego, hemos llegado a un óptimo.
La solución óptima del problema es:
x1 = 2 x2 = 0 x3 = 1 w1 = 0 w2 = 1 w3 = 0
El valor óptimo de z es 13.
Observación: notar que las columnas de las variables básicas son siempre vectores canónicos.
1.1. Pasar de tabla a diccionario
El procedimiento para pasar una tabla a un diccionario es el inverso del que utilizamos para armar
la tabla inicial. Por ejemplo, la siguiente tabla:
3
Base P x1 x2 x3 w1 w2 w3
x1 2 1 2 0 2 0 -1
w2 1 0 -5 0 -2 1 0
x3 1 0 -1 1 -3 0 2
−z -13 0 -3 0 -1 0 -1
Simboliza las siguientes ecuaciones:
x1 + 2x2 + 2w1 − w3 = 2
− 5x2 − 2w1 + w2 = 1
− x2 + x3 − 3w1 + 2w3 = 1
−z + − 3x2 − w1 − w3 = −13
Como la tabla nos dice que las variables básicas son x1, x3 y w2 podemos armar el diccionario
equivalente a la tabla despejando esas variables de cada una de las ecuaciones y despejando z. Aśı,
nos queda el diccionario:
x1 = 2 − 2x2 − 2w1 + w3
w2 = 1 + 5x2 + 2w1
x3 = 1 + x2 + 3w1 − 2w3
z = 13 − 3x2 − w1 − w3
Observación. Con nuestra forma de escribir el método tableau, la tabla del Ejercicio 14 de la
Práctica 2 se expresa como:
Base P x1 x2 x3 x4 x5 x6
x1 f 1 g 0 -2 0 1
x3 d 0 -2 1 e 0 2
x5 1 0 0 0 h 1 43
−z α 0 a 0 b c 3
donde −α es lo que vale la f.o. en la solución actual. Notar que el objetivo del problema es
minimizar, por lo que el criterio de optimaliad es ”todos los coeficientes de las variables no básicas
en la función objetivo son nulos o positivos ”o, equivalentemente en la tabla, ”todos los números
de la última fila son nulos o positivos ”
2. Método matricial
El método matricial es otro método para resolver problemas con SIMPLEX. Naturalmente es
equivalente a cualquiera de los otros dos métodos vistos. El procedimiento se explicó con detalle
en las clases teóricas, por eso esta sección consistirá más que nada en mostrar el método matricial
aplicado a la resolución de un problema concreto. Se utilizará la notación de las clases teóricas.
mı́n z = −x1 − 2x2
s.a: 2x1 + x2 ≤ 2
−x1 + 2x2 ≤ 7
x1 ≤ 3
x1, x2 ≥ 0
Estandarizamos el problema con objetivo de minimizar agregando las variables slack x3, x4, x5:
mı́n z = −x1 − 2x2
s.a: 2x1 + x2 + x3 = 2
−x1 + 2x2 + x4 = 7
x1 + x5 = 3
x1, x2, x3, x4, x5 ≥ 0
4
Expresando este problema de manera matricial:
mı́n cTx
s.a: Ax = b
x ≥ 0
Siendo:
A =
 2 1 1 0 0−1 2 0 1 0
1 0 0 0 1
 b =
27
3
 c =

−1
−2
0
0
0
 x =

x1
x2
x3
x4
x5

Como en este problema podemos comenzar tomando como variables básicas a las variables slack,
se tiene que:
xTB = (x3, x4, x5) x
T
R = (x1, x2)
Por lo tanto:
B =
1 0 00 1 0
0 0 1
 R =
 2 1−1 2
1 0

cTB = (0, 0, 0) c
T
R = (−1,−2)
Es claro que B−1 = B. Recordar que para que la solución básica seafactible, necesitamos que
xB = b̄ = B
−1b ≥ 0. En nuestro caso:
xB = b̄ = B
−1b =
1 0 00 1 0
0 0 1
27
3
 =
27
3

Luego, se tiene que x3 = 2, x4 = 7, x5 = 3. A continuación se calculan los costos reducidos de las
variables no básicas:
c̄TR = c
T
R − cTBB−1R = (−1,−2)− (0, 0, 0)
1 0 00 1 0
0 0 1
 2 1−1 2
1 0
 = (−1,−2)
Como estamos minimizando, queremos que entre a la base la variable con menor coeficiente negativo
en la f.o. En este caso, como la segunda coordenada de c̄TR le corresponde a x2, x2 entra a la base.
Ahora hay que decidir qué variable sale de la base.
Como x2 entra a la base, calculamos Ā
(2):
Ā(2) = B−1A·2 =
1 0 00 1 0
0 0 1
12
0
 =
12
0

Ahora, calculamos la proporción
b̄i
Ā
(2)
i
para cada i tal que Ā
(2)
i > 0:
b̄1
Ā
(2)
1
=
2
1
= 2
b̄2
Ā
(2)
2
=
7
2
Como 2 < 72 , y b̄1 le corresponde al primer elemento de xB , entonces x3 sale de la base. Esto es
equivalente a encontrar la fila pivote en el método tableau o encontrar qué variable básica impone
la restricción más ajustada en el método de diccionarios.
Como x2 ingresó a la base y x3 salió, ahora se tiene que:
xTB = (x2, x4, x5) x
T
R = (x1, x3)
5
B =
1 0 02 1 0
0 0 1
 B−1 =
 1 0 0−2 1 0
0 0 1
 R =
 2 1−1 0
1 0

cTB = (−2, 0, 0) cTR = (−1, 0)
Es decir, B se obtiene a partir de las columnas que corresponden a las variables básicas (que ahora
son x2, x5 y x4). Ahora podemos calcular el costo reducido de las variables no básicas. Si son todos
no negativos habremos llegado al óptimo.
c̄TR = c
T
R − cTBB−1R = (−1, 0)− (−2, 0, 0)
 1 0 0−2 1 0
0 0 1
 2 1−1 0
1 0
 = (−5, 2)
El vector de costos reducidos de las variables no básicas indica que entrará el primer elemento de
xR a la base, o sea, x1, puesto que tiene el costo reducido más negativo.
Calculamos el valor de b̄:
xB = b̄ = B
−1b =
 1 0 0−2 1 0
0 0 1
27
3
 =
23
3

Ahora hay que decidir qué variable sale de la base: Ā(1):
Ā(1) = B−1A·1 =
1 0 00 1 0
0 0 1
12
0
 =
12
0

b̄2
Ā
(1)
2
= 1
b̄3
Ā
(1)
3
= 3
Esto indica que el segundo elemento de xB saldrá de la base, o sea, x4. Ahora tenemos que:
xTB = (x2, x1, x5) x
T
R = (x3, x4)
B =
1 −2 02 −1 0
0 1 1
 B−1 =
− 13 23 0− 23 13 0
2
3 −
1
3 1
 R =
1 00 1
0 0

cTB = (−2,−1, 0) cTR = (0, 0)
Calculamos los costos reducidos de las variables no básicas para chequear el criterio de optimalidad
y b̄:
c̄TR = c
T
R − cTBB−1R = (0, 0)− (−2,−1, 0)
− 13 23 0− 23 13 0
2
3 −
1
3 1
1 00 1
0 0
 = (−4
3
, 2
)
xB = b̄ = B
−1b =
− 13 23 0− 23 13 0
2
3 −
1
3 1
27
3
 =
41
3

Luego, esto indica que x3 debe entrar a la base. Veamos quién debe salir de la base:
Ā(3) = B−1A·3 =
− 13 23 0− 23 13 0
2
3 −
1
3 1
10
0
 =
− 13− 23
2
3

b̄3
Ā
(3)
3
= 3
Luego, sale x5 de la base. Entonces, se tiene que:
xTB = (x1, x2, x3) x
T
R = (x4, x5)
6
B =
 2 1 1−1 2 0
1 0 0
 B−1 =
0 12 120 0 1
1 − 12
3
2
 R =
0 01 0
0 1

cTB = (−1,−1, 0) cTR = (0, 0)
Calculamos los costos reducidos de las variables no básicas y b̄:
c̄TR = c
T
R − cTBB−1R = (0, 0)− (−2,−1, 0)
0 12 120 0 1
1 − 12
3
2
0 01 0
0 1
 = (1, 2)
xB = b̄ = B
−1b =
0 12 120 0 1
1 − 12
3
2
27
3
 =
53
3

Como los costos reducidos son todos no negativos, entonces llegamos a una solución óptima:
(5, 3, 3, 0, 0)
En resumen, el método matricial procede de la siguiente manera:
1. Encontrar una solución básica factible inicial (tal vez necesitemos Fase I o Big-M).
2. Armar la matriz B a partir de las columnas de A que les corresponden a las variables básicas
y R a partir de las columnas que les corresponden a las no básicas. De la misma manera
obtener cB y cR a partir de c.
3. Calcular los costos reducidos de las variables no básicas: c̄TR = c
T
R − cTBB−1R
4. Chequear el criterio de optimalidad:
Si estoy maximizando y c̄TR ≤ 0, entonces llegué al óptimo. Parar.
De lo contrario, continuar a paso 5.
Si estoy minimizando y c̄TR ≥ 0, entonces llegué al óptimo. Parar.
De lo contrario, continuar a paso 5.
5. Elegir la variable que entra a la base según mi objetivo:
Si estoy maximizando, elijo la variable correspondiente a la coordenada más positiva de
c̄TR.
Si estoy minimizando, elijo la variable correspondiente a la coordenada más negativa de
c̄TR.
6. Elegir la variable que sale de la base: calcular b̄ = B−1b y A(j) = B−1A·j (siendo xj la
variable que entrará a la base).
Si A
(j)
i ≤ 0 ∀i, el problema es no acotado. Parar.
De lo contrario, para cada i tal que A
(j)
i > 0 calcular
b̄i
A
(j)
i
. El i correspondiente al
mı́nimo de las proporciones es el ı́ndice de la variable que sale de la base. Volver al paso
2.
7