Una modificación del algoritmo revisado del simplex

              Rev.Acad.Canar.Cienc ., V (Núm. 1), 19-30 (1993)
UNA HODIFICACION DEL ALGORITMO REVISADO DEL SIHPLEX
M. Sánchez García, M. l . Sobrón Fdez. y B. Vitoriano Villanueva
Departamento de Estadistica e Investigac1on Operativa.
Universidad Complutense de Hadrid
Abstract .- The revised simplex algorithm use the inverse matrix of
all basic variables . In .this paper, we proof that the change of
basic solution, only if necessary cal culate the inverse matrix of
basic variables aren't s lack variables . We call modified revised
simplex algorithm to a lgorithm propase in this paper for to
resolve the simplex problem.
Resumen.- El algoritmo revisado del simplex utiliza, para el
c ambio de base, la inversa de la submatriz de coefi cientes
asociada a las variables básicas. En el presente artículo se
demuestra que, para di cho cambio, sólo es necesaria l a inversa de
la submatriz asoci ada a las variables básicas que no son de
holgura.
Key words . - Revised simplex algorithm. Modified revised simplex
algorithm .
Clasificación A.H.S.: 90COS .
1 . I NTRODUCC ION
Para la resolución del problema de Programación Lineal por el
algoritmo revisado de s implex (Papadimi triou-Steigli tz / 1/), es
necesario disponer de la matriz (A:b) de coeficientes de l as
restricciones del problema, del vector de costos c y, en cada
iteración, de la inversa de la submatriz de A asociada a las
variables básicas, sean o no de holgura. En el presente artí culo,
se demuestra que para resolver di cho problema es suficiente
disponer, a demás de las matrices de datos (c:A:b), de la inversa
de la submatriz de A asociada a las variables básicas que no son
19
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
de holgura. Se denomina a la técnica propuesta Algoritmo Revisado
Modificado del Simplex, pudiendo ser de gran utilidad en problemas
en los que las variables de holgura superen el 50% de las
variables básicas.
En el segundo apartado del presente trabajo, se exponen los
resultados que permiten determinar, tanto la variable que entra en
la nueva base, como la que es sustituida; en el tercero, se
explica como se realiza el cambio de base; finalizando con la
descripción del algoritmo propuesto y un ejemplo.
2. RESULTADOS FUNDAMENTALES
Se exponen a continuación los resultados fundamentales, que
permiten demostrar la suficiencia del conocimiento de la inversa
de la matriz asociada con las variables básicas que no son de
holgura, para la aplicación del método revisado del simplex.
Sin pérdida de generalidad, podemos considerar el problema de
Programación Lineal: max~cx: Ax~b. x~Or, donde A es de dimensión
mxn. Mediante la introducción de variables de holgura, se
sustituyen las restricciones por: Ax+Iy=b, x~o. y~O. Se designa
por B la submatriz de A asociada con las variables básicas, por
x!Cll' x 1 <2 >' ... , x 1 Crl' las variables básicas que no son de
holgura y por I la matriz identidad. Suponemos, por simplificar la
notación, que
siendo A la submatriz de A asociada con las variables básicas que
1
no son de holgura; expresión que se obtiene sin más que reordenar
las restricciones, si es necesario .
Teorema 2.1, Si B=[::
A es no singular.
1
20
l supuesto que
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
Demostración:
[
A- 1
-1 1 B B = -1 -A A
2 1
I
•
Corolario 2.2, Sean B=[:: ~] y a=[::]· Se verifica que a= B-'a
[~:] • donde
Demostración:
-1 B a
- -1 a =A a y a a -A a
1 1 1 2 2 21
[
-1
~: A-1
2 1 ·•
OBSERVACION: El teorema 2. 1 y el corolario 2.2 proporcionan
suficiente información para conocer a que variable básica debe
sustituir la variable xJ, con vector asociado ªJ' cuando ésta
entra en la nueva base . En efecto, dicha variable debe sustituir a
la k-ésima variable básica, si y sólo si, a >O y
kj
b / a
k kj
min~ b /a : a >O~ -
1 1 1 J 1 J
-1 Puesto que , par a calcular ªJ' sólo es necesario conocer A1 y A2 ,
-1 se sigue que s ólo es necesario conocer A1 , inversa de la matriz
aso c iada a las va riables básicas que no son de holgura, además de
los datos del problema.
Corolario 2.3: Sea c 1=(c 1 c 1 >'c 1 c2 >' .. .,c1 Crl) el vector de costos
asociado a las variables básicas que no son de holgura, entonces
los multipli cadores del simplex, A.=(A.,A., ... ,A.),
1 2 r
o valores de
las variables duales asociadas con las r primeras restricciones,
son A.=(A t )-1c .
1 1
21
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
Demostración: Sea [A1 N1] la submatriz de A correspondiente a las
r primeras restricciones, despues de reordenar las variables de
forma que ics>=s para s=l, ... ,r. Por definición A~A=c1 ,
A=(At)-1c.
por tanto
1 1 •
Las componentes del vector c'= c - [:~]'· son los costos
marginales, siendo por tanto nulos los correspondientes a las
variables básicas.
3. CAMBIO DE BASE EN EL SIMPLEX
De lo expuesto en el epígrafe precedente, se sigue el cálculo
de los costos marginales, así como la elección de la variable que
debe sustituirse cuando se produce un cambio de base. Para
determinar el proceso algorítmico basta con indicar como se
produce dicho cambio. Cuatro son las posibles situaciones que se
pueden presentar:
I. Sustitución de una variable que no es de holgura, por otra que
tampoco es de holgura.
II. Sustitución de una variable que no es de holgura, por otra que
es de holgura.
III. Sustitución de una variable de holgura, por otra que no es de
holgura.
IV. Sustitución de una variable de holgura, por otra que también
es de ho.lgura.
I. Sea x , con vector asociado a ; la variable, no de holgura, que
j . j •
entra en la nueva base. Supongamos que dicha variable sustituye a
la Variable básica no de holgura X .
. i ( k)
Sea DA-1 la inversa de la matriz asociada con la nueva base,
1
es decir, de la matriz 'obtenida sustituyendo en A los elem~ntos
1
de la columna k-ésima por los correspondientes
Representando por a 1 el vé.ctor formado por éstos últimos y
j
22
de a .
j
siendo
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
a =A-1a y a• =DA-1a se tiene:
j 1 j l(k) 1 l(k)'
• 1 O ... a . . . o o 11 ( k)
o l. .. a • ... o o 21 ( k)
DA-1 [A : a 1 ) 1 1 J •
-1 D[ I: a )
J O O ... a ... O 1
Por tanto
D
k 1 (k)
• O O ... a .. . 1 O
-
1 o. .-a
- o l. . . -a
o o ...
r 1 ( k)
/a .o
1 J kj
/a .o
2J kj
l/a ... O
kj
O O ... -a /a .. . 1
rj kj
,
y la nueva matriz inversa, correspondiente a la base actual, es
DA-1 .
1
II. Sea xJ, con vector asociado ªJ' la variable, no de holgura,
que entra en la nueva base. Supongamos que dicha variable
sustituye a la variable básica de holgura y 1 , asociada con la
k-ésima restri cción . Reordenando si es necesario las restricciones
y las variables, podemos suponer que k=r+l y que j=i(r+l)>i(r).
Sea [:: Pª~] la matriz asociada con las nuevas variables
básicas que no son de holgura y sea [E :J su inversa. Entonces
ft
se verifica:
[ EA +eht 1 l [: :J
Ea +ep
1 . J
ftA +ght t 1 f a +gp
1 J
23
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
De donde se tiene:
EA +eht=I,
1
1 Ea +ep=O,
j
t t f A +gh =O,
1
t 1 fa +gp=l .
j
Despejando convenientemente, se tiene:
lo que implica:
e =
y
lo que implica:
1
g
-1 1 t -1 1 A a -eh A a +ep=O,
1 j 1 j
E -1 A +
1
t -1 1 -gh A a +gp=l,
1 j .
Con estos cálculos se determina la inversa asociada a las nuevas
variables básicas que no son de holgura.
I I I. Sea y la variable no básica de holgura que sustituye a la
j
variable básica x que no es de holgura. La nueva matriz
i (k)
inversa se calcula como en el caso I, considerando y como si no
j
fuera de hoigura . Suponiendo que el vector asociado a y tiene su
j
único elemento no nulo en la fila r-ésima, la matriz asociada a
las nuevas variables básicas tiene nulos todos los elementos de la
columna k-ésima a excepción del que ocupa el lugar r, y por tanto
su inversa DA-1 tiene ·nulos todos los elementos de la columna
1
r-ésima a excepción del que ocupa el lugar k; en consecuencia,
prescindiendo en esta última matriz de la fila k-ésima y de la
columna r-ésima, se obtiene la nueva matriz inversa .
24
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
IV . . Sea yJ la variablé no bisica de holgura que sustituye a la
variable bisica de holgura y 1 . Se procede _primeramente como en el
caso II, introducciendo yJ como si no fuera de holgura y
calculando la inversa de la matriz ampliada de A y, a
1
continuación, se reduce la inversa hallada, como en el caso III,
obteniendo finalmente la inversa de la matriz asociada con las
nuevas variables bisicas que no son de holgura.
OBSERVACION: De los resultados expuestos se sigue que, el
conocimiento de la inversa de la matriz asociada a las variables
bisicas que no son de holgura, es suficiente para la ejecución del
proceso iterativo del algoritmo revisado del simplex. El método
propuesto, complica ligeramente las operaciones requeridas para el
cambio de base , en los casos II y IV, pero, cuando el porcentaje
de variables de holgura es significativamente superior al 50%,
creemos que es mis ripido que el método revisado del simplex.
4. ALGORITMO Y EJEMPLO
Sea el problema de Programación Lineal max~ cx: Ax~b. x~O~ .
Algori tmo
Paso 1 . Se introducen las variables de ho-lgura, pasando a
considerar las restricciones: Ax+Iy=b, x~o. y~O.
Paso 2. Si b~O. las variables de holgura proporcionan la base
inicial, en otro caso, se determina una base inicial,
preferentemente por el metodo dual del simplex. Sean x 1 Cll'
x , .. . , x las variables bisicas que no son de holgura. Se
i (2) i (r)
-1 calcula la ma triz A , inversa de la matriz asociada con dichas
1
variables, y se determina el vector f=(f ,f , . . . ,f ) que
1 ( 1) 1 ( 2) 1 ( r)
indica las filas de A correspondientes, · respectivamente, a las
restricciones asociadas con dichas variables .
Paso 3. Se calculan los multiplicadores del simplex, por la
fórmula A=(At)-1c donde c es el vector de costos asociado a las
1 1' 1
25
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
variables básicas que no son de holgura.
Paso 4. Para j=l, ... ,n+m, se calcula
c'
J
c
J
"\ t 1
- " a
J
hasta encontrar un s tal que c'>O, en cuyo caso se va al paso 5.
s
Si no existe ningún j que verifique la condición anterior, se
termina concluyendo que la solución obtenida es óptima.
Paso 5. Se determina la variable básica que debe ser sustituida
por la variable no básica de vector asociado a , o bien se
s
concluye que el problema no tiene solución. En el primer caso, se
precisa a cuál de las cuatro situaciones, I, II, III o IV,
corresponde el cambio de base .
Paso 6. Se efectua el cambio de base adecuado, calculando la
inversa de la matriz asociada a las nuevas variables básicas que
no son de holgura, y se actualiza el vector f que indica las
restricciones asociadas con dichas variables. A continuación se
vuelve al paso 3.
Ejemplo
Sea el siguiente problema de Programación Lineal:
max 3x +7x +7x +5x +4x
1 2 3 4 5
sujeto a las restricciones :
6x +3x +2x +3x +2x !> 6
1 2 3 4 5
3x +4x +3x +4x +5x !> 7
1 2 3 4 5
4x +3x +4x +5x +4x !> 7
1 2 3 4 5
5x +4x +5x +6x +3x !> 10
1 2 3 4 5
6x +3x +4x +4x +5x !> 8
1 2 3 4 5
5x +4x +2x +4x +3x !> 8
1 2 3 4 5
4x +3x +3x +5x +3x !> 7
1 2 3 4 5
X ~Q i=l,2,3,4,5
l
26
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
ler ciclo
Introducciendo las variables de holgura yi i=l, .. . '7'
obtenemos como solución inicial: X =1
1 '
y =4
2 '
y =3
3 '
y =5
4 '
y5=2,
y =3 y =3. La matriz inversa inicial es A =1/6, f=l y el
6 ' 7 1
multiplicador del simplex es i\.=1/2.
El costo marginal asociado a x es 7-(3/2) >0 , y por tanto x
2 2
entra en la nueva base. Los vectores a y b transformados son:
2
a = [112, 5/2 ,
2
b = [ 1, 4,
Por tanto X entra en la base
2
La nueva matriz inversa es:
-1 A +
1 p-h tA-1 a 1
1 j
p-h tA-1 a 1
1 j
siendo f=(l,2) .
2~ ciclo
1'
3,
en
3/2, O,
5, 2, 3,
segundo
-1 1 A a
1 J
p-htA-1 a 1
1 J
1
Los multiplicadores del simplex son:
3/2,
3]
lugar
1]
y sustituye
[
4/15
-1 / 5
-1 / 5]
2/5
a Y2·
[ ]
-· ] [ 4/15
i\. ' i\. = l3, 7
1 2 -3/15
-3/ 15]
= [-9/15,
6/15
33/15] [-3/ 5, 1115] .
El costo marginal de x 3 es 7+2(3/5)-3(11/5)>0 y, por tanto, entra
en la nueva base la variable x . Los vectores a y b transformados
3 3
son:
[
4/ 15
-1/5
27
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
Por tanto,
a-3 4 4 3 28/15
3
-3 a 5 5 4 32/15
4 ¡-1115] -3 a 4 6 3 30/15
5 4/5
-3 a 2 5 4 -13/15
6
-3 a 3 4 3 13/15
7
[-1/ 15, 4/15, 28/15, 32/15, 2, -13/15, 13/15]
bt = [115, 8/5, 715, 1315, 1015, 3/5, 115].
Como consecuencia x3 entra en tercer lugar, sustituyendo a y3 ,
siendo f=(l,2,3) y la nueva inversa la siguiente:
[
4/15
-115
+(15/28 ) [1115, 6/ 15]
-1/5] ¡-1/15]
2/5 12/15
1/28
-12/28
-7/28 -6/28 15/28
7/28 -6/28 1/28
o 16/28 -12/28
-7/28 -6/28 15/28
32 r ciclo
Los multiplicadores del simplex son:
7/28 -6/28 1/28
o 16/28 -12/28 [-1 ' 13/7' 617] .
- 7/28 -6/28 15/28
28
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
La única variable con costo marginal positivo es y 1 , que vale l.
Por tanto, en la nueva base entra la variable de holgura y 1 . Los
vectores a 6 y b son:
[7/28, O, -7/28, O, -14/28, -21/28, -7/28]
bt = [114, 1, 3/4, 1, 1/2, 5/4, 3/4]
Por tanto, la variable y sustituye en la base a x. Obteniendose
1 1
como nueva matriz inversa:
1
-6/28 1/28
[ : 417 -317
o -617 117
16/28 -12/28
o , -6/28 15/28 -317 417
Prescindiendo de la primera fila y la primera columna, obtenemos
la matriz:
[
4/7
-317
-3/7]
417
que es la inversa de la matriz asociada a las variables básicas
que no son de holgura, siendo f=(2,3).
4~ ciclo
Los nuevos multiplicadores del simplex son:
[
417 [1. 7] -3/7
y los costos marginales para esta solución son:
[-4, º· O, -4, -5, o, -1, -1, o, O, o, o]
que ponen de relieve que la actual solución es óptima, ' siendo
ésta:
29
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017
BIBLIOGRAFIA
/1/ Papadimitriou C. H. y Steiglitz, K. (1982). Combinatorial
Optimization: Algorithms and Complexity. Prentice Hall .
Recibido: 30 de Abril de 1993
30
© Del documento, de los autores. Digitalización realizada por ULPGC. Biblioteca Universitaria, 2017