Metodo simplex modificado

M´todo simplex modificado e Los pasos iterativos del m´todo simplex modificado o revisado son exactae mente a los que seguimos con la tabla. La principal diferencia es´ en que en a este m´todo se usa el algebra de matrices, con la gran ventaja que reduce el e error de redondeo. Desarrollo de las condiciones de optimalidad y factibilidad El problema lineal general se puede plantear como sigue:Maximizar o Minimizar z = n cj xj sujeta a j=1 n Pj xj = b, xj ≥ 0, j = 1, . . . , n. j=1 Para un vector b´sico dado XB con su base B y vector objetivo CB correa spondientes, la tabla general s´ ımplex (matricial) indica que toda iteraci´n o s´ ımplex se puede representar con las siguientes ecuaciones:
n

z+
j=1

(zj − cj )xj = CB B −1 b
n

(XB )i +
j=1

(B −1 Pj )i xj = (B −1 b)i

endonde zj − cj = CB B −1 Pj − cj Se usa la notaci´n (V )i , para representar al i-´simo elemento del vector V . o e Condici´n de optimalidad. En la ecuaci´n de z de arriba, un aumento o o de xj no b´sica por encima de su valor actual cero mejorar´ el valor de z en a a −1 relaci´n con su valor actual, CB B b, s´lo si zj − cj es estrictamente negativo o o en el caso de maximizaci´n, y estrictamentepositivo en caso de minimizaci´n. o o En caso contrario xj no puede mejorar la soluci´n y debe permanecer como o no b´sica de valor cero. Aunque se puede escoger cualquier variable no b´sica a a que satisfaga esta condici´n para mejorar la soluci´n, en el m´todo s´ o o e ımplex se usa una regla aproximada, que selecciona a la variable entrante como la

1

que tiene zj − cj m´s negativo si esmaximizaci´n y m´s positivo si es minia o a mizaci´n. o Condici´n de factibilidad. La determinaci´n del vector saliente se basa en o o examinar la ecuaci´n de restricci´n asociada con la i-´sima variable b´sica. o o e a En forma espec´ ıfica,
n

(XB )i +
j=1

(B −1 Pj )i xj = (B −1 b)i

Cuando se selecciona el vector Pj con la condici´n de optimalidad para entrar o a la base, su variableasociada xj aumentar´ sobre el valor cero. Al mismo a tiempo, todas las variables no b´sicas restantes quedan de valor cero. As´ la a ı, i-´sima ecuaci´n de restricci´n se reduce a e o o (XB )i = (B −1 b)i − (B −1 Pj )i xj La ecuaci´n indica que si (B −1 Pj )i > 0, un aumento de xj puede hacer o que (XB )i , se vuelva negativo, lo cual viola la condici´n de no negatividad, o (XB )i ≥ 0 para toda i.Entonces, (B −1 b)i − (B −1 Pj )i xj ≥ 0, ∀ i Esta condici´n lleva al siguiente valor m´ximo de la variable entrante xj : o a xj = m´ ın i (B −1 b)i | (B −1 Pj )i > 0 (B −1 Pj )i

La variable b´sica asociada a la relaci´n m´ a o ınima sale de la soluci´n b´sica y o a se convierte en no b´sica con valor cero. a Algoritmo s´ ımplex modificado Despu´s de desarrollar las condiciones de optimalidad yfactibilidad, ahora e presentaremos los pasos de c´mputo del m´todo s´ o e ımplex modificado (o revisado). Paso 0. Forme una soluci´n b´sica factible de arranque, y sean B y CB su o a base asociada y vector de coeficientes objetivo, respectivamente.

2

Paso 1. Calcule la inversa B −1 usando un m´todo adecuado de inversi´n. e o Paso 2. Para cada variable xj no b´sica, calcule a zj − cj = CB B −1 Pj− cj Si zj −cj ≥ 0 en maximizaci´n (≤ 0 en minimizaci´n) para toda xj no b´sica, o o a det´ngase; la soluci´n ´ptima es e o o XB = B −1 b, z = CB XB En caso contrario, aplique la condici´n de optimalidad y determine la vario able entrante xj como la variable no b´sica con el valor m´s negativo de a a zj − cj en caso de maximizaci´n, y m´s positivo en caso de minimizaci´n. o a o Paso 3. Calcule B−1 Pj . Si todos los elementos de B −1 Pj son negativos o cero, det´ngase; el problema no tiene soluci´n acotada (realmente esto es una e o no acotaci´n en el espacio, lo que en algunos problemas no afecta, como en los o de minimizaci´n. Es recomendable revisar el comportamiento de la funci´n o o −1 objetivo.). En caso contrario, calcule B b. Entonces, para todos los elementos estrictamente...